1 /*
2 * Licensed Materials - Property of IBM
3 *
4 * trousers - An open source TCG Software Stack
5 *
6 * (C) Copyright International Business Machines Corp. 2006
7 *
8 */
9
10 #include <stdlib.h>
11 #include <stdio.h>
12 #include <string.h>
13
14 // for little-big endian conversion
15 #include <arpa/inet.h>
16 // for message digest
17 #include <openssl/evp.h>
18
19 #include "bi.h"
20
21 #include "daa_parameter.h"
22 #include "list.h"
23 #include "daa_structs.h"
24
25 #include "issuer.h"
26
27 //standard bit length extension to obtain a uniformly distributed number [0,element]
28 static const int SAFETY_PARAM = 80;
29
get_generators(const TSS_DAA_PK_internal * pk)30 static bi_array_ptr get_generators( const TSS_DAA_PK_internal *pk) {
31 bi_array_ptr result = ALLOC_BI_ARRAY();
32 int i;
33
34 bi_new_array( result, 3 + pk->capitalY->length );
35 for(i = 0; i<result->length; i++) {
36 result->array[i] = pk->capitalS;
37 }
38 return result;
39 }
40
get_verifiable_numbers(const TSS_DAA_PK_internal * pk)41 static bi_array_ptr get_verifiable_numbers( const TSS_DAA_PK_internal *pk) {
42 bi_array_ptr result = ALLOC_BI_ARRAY();
43 int i;
44
45 bi_new_array( result, 3 + pk->capitalY->length);
46 result->array[0] = pk->capitalZ;
47 result->array[1] = pk->capitalR0;
48 result->array[2] = pk->capitalR1;
49 // CAPITAL Y ( capitalRReceiver + capitalRIssuer)
50 for( i=0; i<pk->capitalY ->length; i++)
51 result->array[ 3+i] = pk->capitalY->array[i];
52 return result;
53 }
54
55 /* computes an array of random numbers in the range of [1,element] */
compute_random_numbers(bi_array_ptr result,int quantity,const bi_ptr element)56 void compute_random_numbers( bi_array_ptr result, int quantity, const bi_ptr element) {
57 int i=0;
58
59 for( i=0; i<quantity; i++) {
60 compute_random_number( result->array[i], element);
61 bi_inc( result->array[i]); // array[i]++
62 }
63 }
64
test_bit(int pos,BYTE * array,int length)65 int test_bit( int pos, BYTE* array, int length) {
66 return (((int)array[ length - (pos / 8) - 1]) & (1 << (pos % 8))) != 0;
67 }
68
toByteArray(BYTE * result,int length,bi_ptr bi,char * logMsg)69 void toByteArray( BYTE *result, int length, bi_ptr bi, char *logMsg) {
70 LogDebug("-> toByteArray <%d> %s",(int)bi, logMsg);
71 LogDebug("lenghts <%d|%d>",length, (int)bi_nbin_size(bi));
72 bi_2_byte_array( result, length, bi);
73 LogDebug("<- toByteArray result=%s [<%d|%d>] ",
74 dump_byte_array( length, result),
75 length,
76 (int)bi_nbin_size(bi));
77 }
78
79 /*
80 Compute the message digest used in the proof. (from DAA_Param, the digest
81 algorithm is RSA, but this is not available in openssl, the successor of RSA is SHA1
82 */
83 TSS_RESULT
generateMessageDigest(BYTE * md_value,int * md_len,const TSS_DAA_PK_internal * pk,bi_array_ptr * commitments,const int commitments_size)84 generateMessageDigest(BYTE *md_value,
85 int *md_len,
86 const TSS_DAA_PK_internal *pk,
87 bi_array_ptr *commitments,
88 const int commitments_size
89 ) {
90 EVP_MD_CTX *mdctx;
91 const EVP_MD *md;
92 int i, j;
93 int length = DAA_PARAM_SIZE_RSA_MODULUS / 8;
94 BYTE *array;
95
96 // 10000 to be sure, and this memory will be released quite quickly
97 array = (BYTE *)malloc( 10000);
98 if (array == NULL) {
99 LogError("malloc of %d bytes failed", 10000);
100 return TSPERR(TSS_E_OUTOFMEMORY);
101 }
102 OpenSSL_add_all_digests();
103 md = EVP_get_digestbyname( DAA_PARAM_MESSAGE_DIGEST_ALGORITHM);
104 EVP_MD_CTX_create(mdctx);
105 EVP_DigestInit_ex(mdctx, md, NULL);
106 #ifdef DAA_DEBUG
107 fprintf(stderr, "modulus=%s\n", bi_2_hex_char( pk->modulus));
108 #endif
109 toByteArray( array, length, pk->modulus,
110 "!! [generateMessageDigest modulus] current_size=%d length=%d\n");
111 EVP_DigestUpdate(mdctx, array , length);
112 toByteArray( array, length, pk->capitalS,
113 "!! [generateMessageDigest capitalS] current_size=%d length=%d\n");
114 EVP_DigestUpdate(mdctx, array , length);
115 // add capitalZ, capitalR0, capitalR1, capitalY
116 LogDebug("capitalZ capitalR0 capitalY");
117 toByteArray( array, length, pk->capitalZ,
118 "!! [generateMessageDigest capitalZ] current_size=%d length=%d\n");
119 EVP_DigestUpdate(mdctx, array , length);
120 toByteArray( array, length, pk->capitalR0,
121 "!! [generateMessageDigest capitalR0] current_size=%d length=%d\n");
122 EVP_DigestUpdate(mdctx, array , length);
123 toByteArray( array, length, pk->capitalR1,
124 "!! [generateMessageDigest capitalR1] current_size=%d length=%d\n");
125 EVP_DigestUpdate(mdctx, array , length);
126 // CAPITAL Y ( capitalRReceiver )
127 LogDebug("capitalRReceiver");
128 for( i=0; i<pk->capitalRReceiver->length; i++) {
129 toByteArray( array, length, pk->capitalRReceiver->array[i],
130 "!![generateMessageDigest capitalRReceiver] current_size=%d length=%d\n");
131 EVP_DigestUpdate(mdctx, array , length);
132 }
133 LogDebug("capitalRIssuer");
134 // CAPITAL Y ( capitalRIssuer)
135 for( i=0; i<pk->capitalRIssuer->length; i++) {
136 toByteArray( array, length, pk->capitalRIssuer->array[i],
137 "!![generateMessageDigest capitalRReceiver] current_size=%d length=%d\n");
138 EVP_DigestUpdate(mdctx, array , length);
139 }
140 LogDebug("commitments");
141 for( i=0; i<commitments_size; i++) {
142 for( j=0; j<commitments[i]->length; j++) {
143 toByteArray( array, length, commitments[i]->array[j],
144 "!! [generateMessageDigest commitments] current_size=%d length=%d\n");
145 EVP_DigestUpdate(mdctx, array , length);
146 }
147 }
148 EVP_DigestFinal_ex(mdctx, md_value, md_len);
149 EVP_MD_CTX_destroy(mdctx);
150 free( array);
151 return TSS_SUCCESS;
152 }
153
is_range_correct(bi_ptr b,bi_ptr range)154 int is_range_correct( bi_ptr b, bi_ptr range) {
155 return bi_cmp( b, range) < 0 && bi_cmp( b, bi_0) >= 0;
156 }
157
158 /*
159 Verifies if the parameters Z,R0,R1,RReceiver and RIssuer of the public key
160 were correctly computed.
161 pk: the public key, which one wants to verfy.
162 */
163 TSS_RESULT
is_pk_correct(TSS_DAA_PK_internal * public_key,TSS_DAA_PK_PROOF_internal * proof,int * isCorrect)164 is_pk_correct( TSS_DAA_PK_internal *public_key,
165 TSS_DAA_PK_PROOF_internal *proof,
166 int *isCorrect
167 ) {
168 int bit_size_message_digest = DAA_PARAM_SIZE_MESSAGE_DIGEST;
169 bi_ptr n = public_key->modulus;
170 int num_of_variables;
171 int i,j;
172 TSS_RESULT result = TSS_SUCCESS;
173 BYTE verifiable_challenge[EVP_MAX_MD_SIZE];
174 int length_challenge;
175 bi_array_ptr verifiable_numbers;
176 bi_array_ptr *verification_commitments = NULL;
177 bi_array_ptr generators = NULL;
178 bi_t tmp;
179 bi_t tmp1;
180 #ifdef DAA_DEBUG
181 FILE *f;
182 bi_array_ptr *commitments;
183 #endif
184
185 bi_new( tmp);
186 bi_new( tmp1);
187 *isCorrect = 0;
188 #ifdef DAA_DEBUG
189 f=fopen("/tmp/commits", "r");
190 commitments = (bi_array_ptr *)malloc( sizeof(bi_array_ptr) * num_of_variables);
191 if (commitments == NULL) {
192 LogError("malloc of %d bytes failed", sizeof(bi_array_ptr) * num_of_variables);
193 result = TSPERR(TSS_E_OUTOFMEMORY);
194 goto close;
195 }
196 for( i=0; i<num_of_variables; i++) {
197 commitments[i] = ALLOC_BI_ARRAY();
198 BI_LOAD_ARRAY( commitments[i], f);
199 }
200 fclose(f);
201 DUMP_BI( n);
202 #endif
203 LogDebug("STEP 1 ( Tspi_DAA_IssuerKeyVerification spec.)");
204 if( !bi_is_probable_prime( public_key->capitalGamma)) {
205 LogError( "pk->capitalGamma not prime\ncapitalGamma=\n%s",
206 bi_2_hex_char( public_key->capitalGamma));
207 result = TSS_E_BAD_PARAMETER;
208 goto close;
209 }
210 if( !bi_is_probable_prime( public_key->rho)) {
211 LogError( "pk->rho not prime\nrho=\n%s",
212 bi_2_hex_char( public_key->rho));
213 result = TSS_E_BAD_PARAMETER;
214 goto close;
215 }
216 // (capitalGamma - 1) % rho should be equal to 0
217 if( !bi_equals( bi_mod( tmp1, bi_sub( tmp1, public_key->capitalGamma, bi_1),
218 public_key->rho),
219 bi_0)) {
220 LogError( "(capitalGamma - 1) %% rho != 0\nActual value:\n%s",
221 bi_2_hex_char( tmp1));
222 result = TSS_E_BAD_PARAMETER;
223 }
224 // (gamma ^ rho) % capitalGamma should be equals to 1
225 if ( !bi_equals( bi_mod_exp( tmp1, public_key->gamma,
226 public_key->rho,
227 public_key->capitalGamma),
228 bi_1) ) {
229 LogError( "(gamma ^ rho) %% capitalGamma != 1\nActual value:\n%s",
230 bi_2_hex_char( tmp1));
231 result = TSS_E_BAD_PARAMETER;
232 goto close;
233 }
234 // (gamma ^ rho) % capitalGamma should be equal to 1
235 if ( !bi_equals( bi_mod_exp( tmp1,
236 public_key->gamma,
237 public_key->rho,
238 public_key->capitalGamma),
239 bi_1) ) {
240 LogError( "(gamma ^ rho) %% capitalGamma != 1\nActual value:\n%s",
241 bi_2_hex_char( tmp1));
242 result = TSS_E_BAD_PARAMETER;
243 goto close;
244 }
245 LogDebug("STEP 2 check whether all public key parameters have the required length");
246 if( bi_nbin_size( n) != DAA_PARAM_SIZE_RSA_MODULUS / 8) {
247 LogError( "size( n)[%ld] != DAA_PARAM_SIZE_RSA_MODULUS[%d]",
248 bi_nbin_size( n),
249 DAA_PARAM_SIZE_RSA_MODULUS / 8);
250 result = TSS_E_BAD_PARAMETER;
251 goto close;
252 }
253 if( bi_cmp( n, bi_shift_left( tmp1, bi_1, DAA_PARAM_SIZE_RSA_MODULUS))
254 >= 0) {
255 LogError( "n[%ld] != DAA_PARAM_SIZE_RSA_MODULUS[%d]",
256 bi_nbin_size( n),
257 DAA_PARAM_SIZE_RSA_MODULUS);
258 result = TSS_E_BAD_PARAMETER;
259 goto close;
260 }
261 if( bi_cmp( n, bi_shift_left( tmp1, bi_1, DAA_PARAM_SIZE_RSA_MODULUS - 1 ))
262 <= 0) {
263 LogError( "n[%ld] != DAA_PARAM_SIZE_RSA_MODULUS[%d]",
264 bi_nbin_size( n),
265 DAA_PARAM_SIZE_RSA_MODULUS);
266 result = TSS_E_BAD_PARAMETER;
267 goto close;
268 }
269 // rho
270 if( bi_nbin_size( public_key->rho) * 8 != DAA_PARAM_SIZE_RHO) {
271 LogError( "size( rho)[%ld] != DAA_PARAM_SIZE_RHO[%d]",
272 bi_nbin_size( public_key->rho) * 8,
273 DAA_PARAM_SIZE_RHO);
274 result = TSS_E_BAD_PARAMETER;
275 goto close;
276 }
277 // Gamma
278 if( bi_nbin_size( public_key->capitalGamma) * 8 != DAA_PARAM_SIZE_MODULUS_GAMMA) {
279 LogError( "size( rho)[%ld] != DAA_PARAM_SIZE_MODULUS_GAMMA[%d]",
280 bi_nbin_size( public_key->capitalGamma) * 8,
281 DAA_PARAM_SIZE_MODULUS_GAMMA);
282 result = TSS_E_BAD_PARAMETER;
283 goto close;
284 }
285 if( is_range_correct( public_key->capitalS, n) == 0) {
286 LogError( "range not correct( pk->capitalS)\ncapitalS=\n%s\nn=\n%s",
287 bi_2_hex_char( public_key->capitalS),
288 bi_2_hex_char( n));
289 result = TSS_E_BAD_PARAMETER;
290 goto close;
291 }
292 if( is_range_correct( public_key->capitalZ, n) == 0) {
293 LogError( "range not correct( pk->capitalZ)\ncapitalZ=\n%s\nn=\n%s",
294 bi_2_hex_char( public_key->capitalZ),
295 bi_2_hex_char( n));
296 result = TSS_E_BAD_PARAMETER;
297 goto close;
298 }
299 if( is_range_correct( public_key->capitalR0, n) == 0) {
300 LogError( "range not correct( pk->capitalR0)\ncapitalR0=\n%s\nn=\n%s",
301 bi_2_hex_char( public_key->capitalR0),
302 bi_2_hex_char( n));
303 result = TSS_E_BAD_PARAMETER;
304 goto close;
305 }
306 if( is_range_correct( public_key->capitalR1, n) == 0) {
307 LogError( "range not correct( pk->capitalR1)\ncapitalR1=\n%s\nn=\n%s",
308 bi_2_hex_char( public_key->capitalR1),
309 bi_2_hex_char( n));
310 result = TSS_E_BAD_PARAMETER;
311 goto close;
312 }
313 for( i=0; i<public_key->capitalY->length; i++) {
314 if( is_range_correct( public_key->capitalY->array[i], n) == 0) {
315 LogError( "range not correct(pk->capitalY[%d])\ncapitalY[%d]=\n%s\nn=\n%s",
316 i, i,
317 bi_2_hex_char( public_key->capitalY->array[i]),
318 bi_2_hex_char( n));
319 result = TSS_E_BAD_PARAMETER;
320 goto close;
321 }
322 }
323 LogDebug("STEP 3 - compute verification commitments");
324 // only the array is allocated, but all refs are pointing to public_key numbers
325 generators = get_generators( public_key);
326 verifiable_numbers = get_verifiable_numbers( public_key);
327 num_of_variables = verifiable_numbers->length;
328 verification_commitments = (bi_array_ptr *)malloc( sizeof(bi_array_ptr)*num_of_variables);
329 if (verification_commitments == NULL) {
330 LogError("malloc of %d bytes failed", sizeof(bi_array_ptr)*num_of_variables);
331 result = TSPERR(TSS_E_OUTOFMEMORY);
332 goto close;
333 }
334 for( i = 0; i<num_of_variables; i++) {
335 verification_commitments[i] = ALLOC_BI_ARRAY();
336 bi_new_array( verification_commitments[i], bit_size_message_digest);
337 for( j = 0; j<bit_size_message_digest; j++) {
338 #ifdef DAA_DEBUG
339 printf( "[# i=%d j=%d test_bit:%d]",
340 i, j, test_bit( j, proof->challenge, proof->length_challenge));
341 #endif
342 bi_mod_exp( verification_commitments[i]->array[j],
343 generators->array[i],
344 proof->response[i]->array[j], n);
345 if( test_bit( j, proof->challenge, proof->length_challenge)) {
346 bi_mul( verification_commitments[i]->array[j],
347 verification_commitments[i]->array[j],
348 verifiable_numbers->array[i]);
349 #ifdef DAA_DEBUG
350 DUMP_BI( verification_commitments[i]->array[j]);
351 #endif
352 bi_mod( verification_commitments[i]->array[j],
353 verification_commitments[i]->array[j],
354 n);
355 }
356 #ifdef DAA_DEBUG
357 if( commitments != NULL &&
358 bi_equals( verification_commitments[i]->array[j],
359 commitments[i]->array[j]) ==0) {
360 LogError( "!! ERROR i=%d j=%d\n", i, j);
361 DUMP_BI( commitments[i]->array[j]);
362 DUMP_BI( verification_commitments[i]->array[j]);
363 DUMP_BI( generators->array[i]);
364 DUMP_BI( proof->response[i]->array[j]);
365 DUMP_BI( verifiable_numbers->array[i]);
366 }
367 printf( "o"); fflush( stdout);
368 #endif
369 }
370 }
371 // STEP 3 - d
372 generateMessageDigest( verifiable_challenge,
373 &length_challenge,
374 public_key,
375 verification_commitments,
376 num_of_variables);
377 LogDebug("verifiable challenge=%s",
378 dump_byte_array( length_challenge, verifiable_challenge));
379 LogDebug(" challenge=%s",
380 dump_byte_array( proof->length_challenge, proof->challenge));
381 if( length_challenge != proof->length_challenge) {
382 result = TSS_E_BAD_PARAMETER;
383 goto close;
384 }
385 for( i=0; i<length_challenge; i++) {
386 if( verifiable_challenge[i] != proof->challenge[i]) {
387 result = TSS_E_BAD_PARAMETER;
388 goto close;
389 }
390 }
391 *isCorrect = ( memcmp( verifiable_challenge, proof->challenge, length_challenge) == 0);
392 close:
393 if( verification_commitments != NULL) {
394 for( i = 0; i<num_of_variables; i++) {
395 bi_free_array( verification_commitments[i]);
396 }
397 free( verification_commitments);
398 }
399 if( generators != NULL) free( generators);
400 bi_free( tmp1);
401 bi_free( tmp);
402 return result;
403 }
404
405
generate_proof(const bi_ptr product_PQ_prime,const TSS_DAA_PK_internal * public_key,const bi_ptr xz,const bi_ptr x0,const bi_ptr x1,bi_array_ptr x)406 TSS_DAA_PK_PROOF_internal *generate_proof(const bi_ptr product_PQ_prime,
407 const TSS_DAA_PK_internal *public_key,
408 const bi_ptr xz,
409 const bi_ptr x0,
410 const bi_ptr x1,
411 bi_array_ptr x
412 ) {
413 int i, j;
414 bi_array_ptr generators = get_generators( public_key);
415 bi_ptr n = public_key->modulus;
416 int num_of_variables;
417 int bit_size_message_digest = DAA_PARAM_SIZE_MESSAGE_DIGEST;
418 bi_array_ptr *xTildes = NULL;
419 BYTE *challenge_param;
420
421 bi_array_ptr exponents = ALLOC_BI_ARRAY();
422 bi_new_array2( exponents, 3 + x->length);
423 exponents->array[0] = xz; exponents->array[1] = x0; exponents->array[2] = x1;
424 bi_copy_array( x, 0, exponents, 3, x->length);
425 num_of_variables = exponents->length;
426 LogDebug("Step a - choose random numbers");
427 LogDebug("\nchoose random numbers\n");
428 xTildes = (bi_array_ptr *)malloc( sizeof(bi_array_ptr) * num_of_variables);
429 if (xTildes == NULL) {
430 LogError("malloc of %d bytes failed", sizeof(bi_array_ptr) * num_of_variables);
431 return NULL;
432 }
433 for( i=0; i<num_of_variables; i++) {
434 #ifdef DAA_DEBUG
435 printf("*");
436 fflush(stdout);
437 #endif
438 xTildes[i] = ALLOC_BI_ARRAY();
439 bi_new_array( xTildes[i], bit_size_message_digest);
440 compute_random_numbers( xTildes[i], bit_size_message_digest, product_PQ_prime);
441 }
442 // Compute commitments
443 LogDebug("\ncompute commitments");
444 bi_array_ptr *commitments =
445 (bi_array_ptr *)malloc( sizeof(bi_array_ptr) * num_of_variables);
446 if (commitments == NULL) {
447 LogError("malloc of %d bytes failed", sizeof(bi_array_ptr) * num_of_variables);
448 return NULL;
449 }
450 for( i=0; i<num_of_variables; i++) {
451 commitments[i] = ALLOC_BI_ARRAY();
452 bi_new_array( commitments[i], bit_size_message_digest);
453 for( j=0; j<bit_size_message_digest; j++) {
454 #ifdef DAA_DEBUG
455 printf("#");
456 fflush(stdout);
457 #endif
458 bi_mod_exp( commitments[i]->array[j],
459 generators->array[i],
460 xTildes[i]->array[j],
461 n);
462 }
463 }
464 #ifdef DAA_DEBUG
465 FILE *f=fopen("/tmp/commits", "w");
466 for( i=0; i<num_of_variables; i++) {
467 BI_SAVE_ARRAY( commitments[i], f);
468 }
469 fclose(f);
470 #endif
471 LogDebug("Step b: compute challenge (message digest)");
472 BYTE challenge[EVP_MAX_MD_SIZE];
473 int length_challenge;
474 generateMessageDigest( challenge,
475 &length_challenge,
476 public_key,
477 commitments,
478 num_of_variables);
479 // STEP c - compute response
480 LogDebug("Step c: compute response\n");
481 bi_array_ptr *response = (bi_array_ptr *)malloc( sizeof(bi_array_ptr) * num_of_variables);
482 if (response == NULL) {
483 LogError("malloc of %d bytes failed", sizeof(bi_array_ptr) * num_of_variables);
484 return NULL;
485 }
486 for( i=0; i<num_of_variables; i++) {
487 response[i] = ALLOC_BI_ARRAY();
488 bi_new_array( response[i], bit_size_message_digest);
489 for( j=0; j<bit_size_message_digest; j++) {
490 if( test_bit( j, challenge, length_challenge)) {
491 bi_sub( response[i]->array[j],
492 xTildes[i]->array[j],
493 exponents->array[i]);
494 } else {
495 bi_set( response[i]->array[j],
496 xTildes[i]->array[j]);
497 }
498 bi_mod( response[i]->array[j], response[i]->array[j], product_PQ_prime);
499 #ifdef DAA_DEBUG
500 printf("#");
501 fflush(stdout);
502 #endif
503 }
504 }
505 challenge_param = (BYTE *)malloc( length_challenge);
506 if (challenge_param == NULL) {
507 LogError("malloc of %d bytes failed", length_challenge);
508 return NULL;
509 }
510 memcpy( challenge_param, challenge, length_challenge);
511
512 return create_DAA_PK_PROOF( challenge_param,
513 length_challenge,
514 response,
515 num_of_variables);
516 }
517