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] 28static const int SAFETY_PARAM = 80; 29 30static 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 41static 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] */ 56void 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 65int test_bit( int pos, BYTE* array, int length) { 66 return (((int)array[ length - (pos / 8) - 1]) & (1 << (pos % 8))) != 0; 67} 68 69void 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/* 80Compute the message digest used in the proof. (from DAA_Param, the digest 81algorithm is RSA, but this is not available in openssl, the successor of RSA is SHA1 82*/ 83TSS_RESULT 84generateMessageDigest(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 154int 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/* 159Verifies if the parameters Z,R0,R1,RReceiver and RIssuer of the public key 160were correctly computed. 161pk: the public key, which one wants to verfy. 162*/ 163TSS_RESULT 164is_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); 392close: 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 406TSS_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