src/util/crypto_rsa.c

   1 /*
   2   This file is part of GNUnet
   3   Copyright (C) 2014,2016 GNUnet e.V.
   4
   5   GNUnet is free software: you can redistribute it and/or modify it
   6   under the terms of the GNU Affero General Public License as published
   7   by the Free Software Foundation, either version 3 of the License,
   8   or (at your option) any later version.
   9
  10   GNUnet is distributed in the hope that it will be useful, but
  11   WITHOUT ANY WARRANTY; without even the implied warranty of
  12   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13   Affero General Public License for more details.
  14 */
  15
  16 /**
  17  * @file util/crypto_rsa.c
  18  * @brief Chaum-style Blind signatures based on RSA
  19  * @author Sree Harsha Totakura <sreeharsha@totakura.in>
  20  * @author Christian Grothoff
  21  * @author Jeffrey Burdges <burdges@gnunet.org>
  22  */
  23 #include "platform.h"
  24 #include <gcrypt.h>
  25 #include "gnunet_crypto_lib.h"
  26
  27 #define LOG(kind,...) GNUNET_log_from (kind, "util-crypto-rsa", __VA_ARGS__)
  28
  29
  30 /**
  31  * The private information of an RSA key pair.
  32  */
  33 struct GNUNET_CRYPTO_RsaPrivateKey
  34 {
  35   /**
  36    * Libgcrypt S-expression for the RSA private key.
  37    */
  38   gcry_sexp_t sexp;
  39 };
  40
  41
  42 /**
  43  * The public information of an RSA key pair.
  44  */
  45 struct GNUNET_CRYPTO_RsaPublicKey
  46 {
  47   /**
  48    * Libgcrypt S-expression for the RSA public key.
  49    */
  50   gcry_sexp_t sexp;
  51 };
  52
  53
  54 /**
  55  * @brief an RSA signature
  56  */
  57 struct GNUNET_CRYPTO_RsaSignature
  58 {
  59   /**
  60    * Libgcrypt S-expression for the RSA signature.
  61    */
  62   gcry_sexp_t sexp;
  63 };
  64
  65
  66 /**
  67  * @brief RSA blinding key
  68  */
  69 struct RsaBlindingKey
  70 {
  71   /**
  72    * Random value used for blinding.
  73    */
  74   gcry_mpi_t r;
  75 };
  76
  77
  78 /**
  79  * Extract values from an S-expression.
  80  *
  81  * @param array where to store the result(s)
  82  * @param sexp S-expression to parse
  83  * @param topname top-level name in the S-expression that is of interest
  84  * @param elems names of the elements to extract
  85  * @return 0 on success
  86  */
  87 static int
  88 key_from_sexp (gcry_mpi_t *array,
  89                gcry_sexp_t sexp,
  90                const char *topname,
  91                const char *elems)
  92 {
  93   gcry_sexp_t list;
  94   gcry_sexp_t l2;
  95   const char *s;
  96   unsigned int idx;
  97
  98   if (! (list = gcry_sexp_find_token (sexp, topname, 0)))
  99     return 1;
 100   l2 = gcry_sexp_cadr (list);
 101   gcry_sexp_release (list);
 102   list = l2;
 103   if (! list)
 104     return 2;
 105   idx = 0;
 106   for (s = elems; *s; s++, idx++)
 107   {
 108     if (! (l2 = gcry_sexp_find_token (list, s, 1)))
 109     {
 110       for (unsigned int i = 0; i < idx; i++)
 111       {
 112         gcry_free (array[i]);
 113         array[i] = NULL;
 114       }
 115       gcry_sexp_release (list);
 116       return 3;                 /* required parameter not found */
 117     }
 118     array[idx] = gcry_sexp_nth_mpi (l2, 1, GCRYMPI_FMT_USG);
 119     gcry_sexp_release (l2);
 120     if (! array[idx])
 121     {
 122       for (unsigned int i = 0; i < idx; i++)
 123       {
 124         gcry_free (array[i]);
 125         array[i] = NULL;
 126       }
 127       gcry_sexp_release (list);
 128       return 4;                 /* required parameter is invalid */
 129     }
 130   }
 131   gcry_sexp_release (list);
 132   return 0;
 133 }
 134
 135
 136 /**
 137  * Create a new private key. Caller must free return value.
 138  *
 139  * @param len length of the key in bits (i.e. 2048)
 140  * @return fresh private key
 141  */
 142 struct GNUNET_CRYPTO_RsaPrivateKey *
 143 GNUNET_CRYPTO_rsa_private_key_create (unsigned int len)
 144 {
 145   struct GNUNET_CRYPTO_RsaPrivateKey *ret;
 146   gcry_sexp_t s_key;
 147   gcry_sexp_t s_keyparam;
 148
 149   GNUNET_assert (0 ==
 150                  gcry_sexp_build (&s_keyparam,
 151                                   NULL,
 152                                   "(genkey(rsa(nbits %d)))",
 153                                   len));
 154   GNUNET_assert (0 ==
 155                  gcry_pk_genkey (&s_key,
 156                                  s_keyparam));
 157   gcry_sexp_release (s_keyparam);
 158 #if EXTRA_CHECKS
 159   GNUNET_assert (0 ==
 160                  gcry_pk_testkey (s_key));
 161 #endif
 162   ret = GNUNET_new (struct GNUNET_CRYPTO_RsaPrivateKey);
 163   ret->sexp = s_key;
 164   return ret;
 165 }
 166
 167
 168 /**
 169  * Free memory occupied by the private key.
 170  *
 171  * @param key pointer to the memory to free
 172  */
 173 void
 174 GNUNET_CRYPTO_rsa_private_key_free (struct GNUNET_CRYPTO_RsaPrivateKey *key)
 175 {
 176   gcry_sexp_release (key->sexp);
 177   GNUNET_free (key);
 178 }
 179
 180
 181 /**
 182  * Encode the private key in a format suitable for
 183  * storing it into a file.
 184  *
 185  * @param key the private key
 186  * @param[out] buffer set to a buffer with the encoded key
 187  * @return size of memory allocated in @a buffer
 188  */
 189 size_t
 190 GNUNET_CRYPTO_rsa_private_key_encode (const struct GNUNET_CRYPTO_RsaPrivateKey *key,
 191                                       char **buffer)
 192 {
 193   size_t n;
 194   char *b;
 195
 196   n = gcry_sexp_sprint (key->sexp,
 197                         GCRYSEXP_FMT_DEFAULT,
 198                         NULL,
 199                         0);
 200   b = GNUNET_malloc (n);
 201   GNUNET_assert ((n - 1) ==     /* since the last byte is \0 */
 202                  gcry_sexp_sprint (key->sexp,
 203                                    GCRYSEXP_FMT_DEFAULT,
 204                                    b,
 205                                    n));
 206   *buffer = b;
 207   return n;
 208 }
 209
 210
 211 /**
 212  * Decode the private key from the data-format back
 213  * to the "normal", internal format.
 214  *
 215  * @param buf the buffer where the private key data is stored
 216  * @param len the length of the data in @a buf
 217  * @return NULL on error
 218  */
 219 struct GNUNET_CRYPTO_RsaPrivateKey *
 220 GNUNET_CRYPTO_rsa_private_key_decode (const char *buf,
 221                                       size_t len)
 222 {
 223   struct GNUNET_CRYPTO_RsaPrivateKey *key;
 224   key = GNUNET_new (struct GNUNET_CRYPTO_RsaPrivateKey);
 225   if (0 !=
 226       gcry_sexp_new (&key->sexp,
 227                      buf,
 228                      len,
 229                      0))
 230   {
 231     LOG (GNUNET_ERROR_TYPE_WARNING,
 232          "Decoded private key is not valid\n");
 233     GNUNET_free (key);
 234     return NULL;
 235   }
 236   if (0 != gcry_pk_testkey (key->sexp))
 237   {
 238     LOG (GNUNET_ERROR_TYPE_WARNING,
 239          "Decoded private key is not valid\n");
 240     GNUNET_CRYPTO_rsa_private_key_free (key);
 241     return NULL;
 242   }
 243   return key;
 244 }
 245
 246
 247 /**
 248  * Extract the public key of the given private key.
 249  *
 250  * @param priv the private key
 251  * @retur NULL on error, otherwise the public key
 252  */
 253 struct GNUNET_CRYPTO_RsaPublicKey *
 254 GNUNET_CRYPTO_rsa_private_key_get_public (const struct GNUNET_CRYPTO_RsaPrivateKey *priv)
 255 {
 256   struct GNUNET_CRYPTO_RsaPublicKey *pub;
 257   gcry_mpi_t ne[2];
 258   int rc;
 259   gcry_sexp_t result;
 260
 261   rc = key_from_sexp (ne, priv->sexp, "public-key", "ne");
 262   if (0 != rc)
 263     rc = key_from_sexp (ne, priv->sexp, "private-key", "ne");
 264   if (0 != rc)
 265     rc = key_from_sexp (ne, priv->sexp, "rsa", "ne");
 266   if (0 != rc)
 267   {
 268     GNUNET_break_op (0);
 269     return NULL;
 270   }
 271   rc = gcry_sexp_build (&result,
 272                         NULL,
 273                         "(public-key(rsa(n %m)(e %m)))",
 274                         ne[0],
 275                         ne[1]);
 276   gcry_mpi_release (ne[0]);
 277   gcry_mpi_release (ne[1]);
 278   pub = GNUNET_new (struct GNUNET_CRYPTO_RsaPublicKey);
 279   pub->sexp = result;
 280   return pub;
 281 }
 282
 283
 284 /**
 285  * Free memory occupied by the public key.
 286  *
 287  * @param key pointer to the memory to free
 288  */
 289 void
 290 GNUNET_CRYPTO_rsa_public_key_free (struct GNUNET_CRYPTO_RsaPublicKey *key)
 291 {
 292   gcry_sexp_release (key->sexp);
 293   GNUNET_free (key);
 294 }
 295
 296
 297 /**
 298  * Encode the public key in a format suitable for
 299  * storing it into a file.
 300  *
 301  * @param key the private key
 302  * @param[out] buffer set to a buffer with the encoded key
 303  * @return size of memory allocated in @a buffer
 304  */
 305 size_t
 306 GNUNET_CRYPTO_rsa_public_key_encode (const struct GNUNET_CRYPTO_RsaPublicKey *key,
 307                                      char **buffer)
 308 {
 309   size_t n;
 310   char *b;
 311
 312   n = gcry_sexp_sprint (key->sexp,
 313                         GCRYSEXP_FMT_ADVANCED,
 314                         NULL,
 315                         0);
 316   b = GNUNET_malloc (n);
 317   GNUNET_assert ((n -1) ==      /* since the last byte is \0 */
 318                  gcry_sexp_sprint (key->sexp,
 319                                    GCRYSEXP_FMT_ADVANCED,
 320                                    b,
 321                                    n));
 322   *buffer = b;
 323   return n;
 324 }
 325
 326
 327 /**
 328  * Compute hash over the public key.
 329  *
 330  * @param key public key to hash
 331  * @param hc where to store the hash code
 332  */
 333 void
 334 GNUNET_CRYPTO_rsa_public_key_hash (const struct GNUNET_CRYPTO_RsaPublicKey *key,
 335                                    struct GNUNET_HashCode *hc)
 336 {
 337   char *buf;
 338   size_t buf_size;
 339
 340   buf_size = GNUNET_CRYPTO_rsa_public_key_encode (key,
 341                                                   &buf);
 342   GNUNET_CRYPTO_hash (buf,
 343                       buf_size,
 344                       hc);
 345   GNUNET_free (buf);
 346 }
 347
 348
 349 /**
 350  * Decode the public key from the data-format back
 351  * to the "normal", internal format.
 352  *
 353  * @param buf the buffer where the public key data is stored
 354  * @param len the length of the data in @a buf
 355  * @return NULL on error
 356  */
 357 struct GNUNET_CRYPTO_RsaPublicKey *
 358 GNUNET_CRYPTO_rsa_public_key_decode (const char *buf,
 359                                      size_t len)
 360 {
 361   struct GNUNET_CRYPTO_RsaPublicKey *key;
 362   gcry_mpi_t n;
 363   int ret;
 364
 365   key = GNUNET_new (struct GNUNET_CRYPTO_RsaPublicKey);
 366   if (0 !=
 367       gcry_sexp_new (&key->sexp,
 368                      buf,
 369                      len,
 370                      0))
 371   {
 372     GNUNET_break_op (0);
 373     GNUNET_free (key);
 374     return NULL;
 375   }
 376   /* verify that this is an RSA public key */
 377   ret = key_from_sexp (&n, key->sexp, "public-key", "n");
 378   if (0 != ret)
 379     ret = key_from_sexp (&n, key->sexp, "rsa", "n");
 380   if (0 != ret)
 381   {
 382     /* this is no public RSA key */
 383     GNUNET_break (0);
 384     gcry_sexp_release (key->sexp);
 385     GNUNET_free (key);
 386     return NULL;
 387   }
 388   gcry_mpi_release (n);
 389   return key;
 390 }
 391
 392
 393 /**
 394  * Test for malicious RSA key.
 395  *
 396  * Assuming n is an RSA modulous and r is generated using a call to
 397  * GNUNET_CRYPTO_kdf_mod_mpi, if gcd(r,n) != 1 then n must be a
 398  * malicious RSA key designed to deanomize the user.
 399  *
 400  * @param r KDF result
 401  * @param n RSA modulus
 402  * @return True if gcd(r,n) = 1, False means RSA key is malicious
 403  */
 404 static int
 405 rsa_gcd_validate(gcry_mpi_t r, gcry_mpi_t n)
 406 {
 407   gcry_mpi_t g;
 408   int t;
 409
 410   g = gcry_mpi_new (0);
 411   t = gcry_mpi_gcd(g,r,n);
 412   gcry_mpi_release (g);
 413   return t;
 414 }
 415
 416
 417 /**
 418  * Create a blinding key
 419  *
 420  * @param len length of the key in bits (i.e. 2048)
 421  * @param bks pre-secret to use to derive the blinding key
 422  * @return the newly created blinding key, NULL if RSA key is malicious
 423  */
 424 static struct RsaBlindingKey *
 425 rsa_blinding_key_derive (const struct GNUNET_CRYPTO_RsaPublicKey *pkey,
 426                          const struct GNUNET_CRYPTO_RsaBlindingKeySecret *bks)
 427 {
 428   char *xts = "Blinding KDF extrator HMAC key";  /* Trusts bks' randomness more */
 429   struct RsaBlindingKey *blind;
 430   gcry_mpi_t n;
 431
 432   blind = GNUNET_new (struct RsaBlindingKey);
 433   GNUNET_assert( NULL != blind );
 434
 435   /* Extract the composite n from the RSA public key */
 436   GNUNET_assert( 0 == key_from_sexp (&n, pkey->sexp, "rsa", "n") );
 437   /* Assert that it at least looks like an RSA key */
 438   GNUNET_assert( 0 == gcry_mpi_get_flag(n, GCRYMPI_FLAG_OPAQUE) );
 439
 440   GNUNET_CRYPTO_kdf_mod_mpi (&blind->r,
 441                              n,
 442                              xts,  strlen(xts),
 443                              bks,  sizeof(*bks),
 444                              "Blinding KDF");
 445   if (0 == rsa_gcd_validate(blind->r, n))  {
 446     GNUNET_free (blind);
 447     blind = NULL;
 448   }
 449
 450   gcry_mpi_release (n);
 451   return blind;
 452 }
 453
 454
 455 /*
 456 We originally added GNUNET_CRYPTO_kdf_mod_mpi for the benifit of the
 457 previous routine.
 458
 459 There was previously a call to GNUNET_CRYPTO_kdf in
 460   bkey = rsa_blinding_key_derive (len, bks);
 461 that gives exactly len bits where
 462   len = GNUNET_CRYPTO_rsa_public_key_len (pkey);
 463
 464 Now r = 2^(len-1)/pkey.n is the probability that a set high bit being
 465 okay, meaning bkey < pkey.n.  It follows that (1-r)/2 of the time bkey >
 466 pkey.n making the effective bkey be
 467   bkey mod pkey.n = bkey - pkey.n
 468 so the effective bkey has its high bit set with probability r/2.
 469
 470 We expect r to be close to 1/2 if the exchange is honest, but the
 471 exchange can choose r otherwise.
 472
 473 In blind signing, the exchange sees
 474   B = bkey * S mod pkey.n
 475 On deposit, the exchange sees S so they can compute bkey' = B/S mod
 476 pkey.n for all B they recorded to see if bkey' has it's high bit set.
 477 Also, note the exchange can compute 1/S efficiently since they know the
 478 factors of pkey.n.
 479
 480 I suppose that happens with probability r/(1+r) if its the wrong B, not
 481 completely sure.  If otoh we've the right B, then we've the probability
 482 r/2 of a set high bit in the effective bkey.
 483
 484 Interestingly, r^2-r has a maximum at the default r=1/2 anyways, giving
 485 the wrong and right probabilities 1/3 and 1/4, respectively.
 486
 487 I feared this gives the exchange a meaningful fraction of a bit of
 488 information per coin involved in the transaction.  It sounds damaging if
 489 numerous coins were involved.  And it could run across transactions in
 490 some scenarios.
 491
 492 We fixed this by using a more uniform deterministic pseudo-random number
 493 generator for blinding factors.  I do not believe this to be a problem
 494 for the rsa_full_domain_hash routine, but better safe than sorry.
 495 */
 496
 497
 498 /**
 499  * Compare the values of two signatures.
 500  *
 501  * @param s1 one signature
 502  * @param s2 the other signature
 503  * @return 0 if the two are equal
 504  */
 505 int
 506 GNUNET_CRYPTO_rsa_signature_cmp (struct GNUNET_CRYPTO_RsaSignature *s1,
 507                                  struct GNUNET_CRYPTO_RsaSignature *s2)
 508 {
 509   char *b1;
 510   char *b2;
 511   size_t z1;
 512   size_t z2;
 513   int ret;
 514
 515   z1 = GNUNET_CRYPTO_rsa_signature_encode (s1,
 516                                            &b1);
 517   z2 = GNUNET_CRYPTO_rsa_signature_encode (s2,
 518                                            &b2);
 519   if (z1 != z2)
 520     ret = 1;
 521   else
 522     ret = memcmp (b1,
 523                   b2,
 524                   z1);
 525   GNUNET_free (b1);
 526   GNUNET_free (b2);
 527   return ret;
 528 }
 529
 530
 531 /**
 532  * Compare the values of two public keys.
 533  *
 534  * @param p1 one public key
 535  * @param p2 the other public key
 536  * @return 0 if the two are equal
 537  */
 538 int
 539 GNUNET_CRYPTO_rsa_public_key_cmp (struct GNUNET_CRYPTO_RsaPublicKey *p1,
 540                                   struct GNUNET_CRYPTO_RsaPublicKey *p2)
 541 {
 542   char *b1;
 543   char *b2;
 544   size_t z1;
 545   size_t z2;
 546   int ret;
 547
 548   z1 = GNUNET_CRYPTO_rsa_public_key_encode (p1,
 549                                             &b1);
 550   z2 = GNUNET_CRYPTO_rsa_public_key_encode (p2,
 551                                             &b2);
 552   if (z1 != z2)
 553     ret = 1;
 554   else
 555     ret = memcmp (b1,
 556                   b2,
 557                   z1);
 558   GNUNET_free (b1);
 559   GNUNET_free (b2);
 560   return ret;
 561 }
 562
 563
 564 /**
 565  * Compare the values of two private keys.
 566  *
 567  * @param p1 one private key
 568  * @param p2 the other private key
 569  * @return 0 if the two are equal
 570  */
 571 int
 572 GNUNET_CRYPTO_rsa_private_key_cmp (struct GNUNET_CRYPTO_RsaPrivateKey *p1,
 573                                    struct GNUNET_CRYPTO_RsaPrivateKey *p2)
 574 {
 575   char *b1;
 576   char *b2;
 577   size_t z1;
 578   size_t z2;
 579   int ret;
 580
 581   z1 = GNUNET_CRYPTO_rsa_private_key_encode (p1,
 582                                             &b1);
 583   z2 = GNUNET_CRYPTO_rsa_private_key_encode (p2,
 584                                             &b2);
 585   if (z1 != z2)
 586     ret = 1;
 587   else
 588     ret = memcmp (b1,
 589                   b2,
 590                   z1);
 591   GNUNET_free (b1);
 592   GNUNET_free (b2);
 593   return ret;
 594 }
 595
 596
 597 /**
 598  * Obtain the length of the RSA key in bits.
 599  *
 600  * @param key the public key to introspect
 601  * @return length of the key in bits
 602  */
 603 unsigned int
 604 GNUNET_CRYPTO_rsa_public_key_len (const struct GNUNET_CRYPTO_RsaPublicKey *key)
 605 {
 606   gcry_mpi_t n;
 607   unsigned int rval;
 608
 609   if (0 != key_from_sexp (&n, key->sexp, "rsa", "n"))
 610   { /* Not an RSA public key */
 611     GNUNET_break (0);
 612     return 0;
 613   }
 614   rval = gcry_mpi_get_nbits (n);
 615   gcry_mpi_release (n);
 616   return rval;
 617 }
 618
 619
 620 /**
 621  * Destroy a blinding key
 622  *
 623  * @param bkey the blinding key to destroy
 624  */
 625 static void
 626 rsa_blinding_key_free (struct RsaBlindingKey *bkey)
 627 {
 628   gcry_mpi_release (bkey->r);
 629   GNUNET_free (bkey);
 630 }
 631
 632
 633 /**
 634  * Print an MPI to a newly created buffer
 635  *
 636  * @param v MPI to print.
 637  * @param[out] newly allocated buffer containing the result
 638  * @return number of bytes stored in @a buffer
 639  */
 640 static size_t
 641 numeric_mpi_alloc_n_print (gcry_mpi_t v,
 642                            char **buffer)
 643 {
 644   size_t n;
 645   char *b;
 646   size_t rsize;
 647
 648   gcry_mpi_print (GCRYMPI_FMT_USG,
 649                   NULL,
 650                   0,
 651                   &n,
 652                   v);
 653   b = GNUNET_malloc (n);
 654   GNUNET_assert (0 ==
 655                  gcry_mpi_print (GCRYMPI_FMT_USG,
 656                                  (unsigned char *) b,
 657                                  n,
 658                                  &rsize,
 659                                  v));
 660   *buffer = b;
 661   return n;
 662 }
 663
 664
 665 /**
 666  * Computes a full domain hash seeded by the given public key.
 667  * This gives a measure of provable security to the Taler exchange
 668  * against one-more forgery attacks.  See:
 669  *   https://eprint.iacr.org/2001/002.pdf
 670  *   http://www.di.ens.fr/~pointche/Documents/Papers/2001_fcA.pdf
 671  *
 672  * @param hash initial hash of the message to sign
 673  * @param pkey the public key of the signer
 674  * @param rsize If not NULL, the number of bytes actually stored in buffer
 675  * @return MPI value set to the FDH, NULL if RSA key is malicious
 676  */
 677 static gcry_mpi_t
 678 rsa_full_domain_hash (const struct GNUNET_CRYPTO_RsaPublicKey *pkey,
 679                       const struct GNUNET_HashCode *hash)
 680 {
 681   gcry_mpi_t r,n;
 682   char *xts;
 683   size_t xts_len;
 684   int ok;
 685
 686   /* Extract the composite n from the RSA public key */
 687   GNUNET_assert( 0 == key_from_sexp (&n, pkey->sexp, "rsa", "n") );
 688   /* Assert that it at least looks like an RSA key */
 689   GNUNET_assert( 0 == gcry_mpi_get_flag(n, GCRYMPI_FLAG_OPAQUE) );
 690
 691   /* We key with the public denomination key as a homage to RSA-PSS by  *
 692    * Mihir Bellare and Phillip Rogaway.  Doing this lowers the degree   *
 693    * of the hypothetical polyomial-time attack on RSA-KTI created by a  *
 694    * polynomial-time one-more forgary attack.  Yey seeding!             */
 695   xts_len = GNUNET_CRYPTO_rsa_public_key_encode (pkey, &xts);
 696
 697   GNUNET_CRYPTO_kdf_mod_mpi (&r,
 698                              n,
 699                              xts,  xts_len,
 700                              hash,  sizeof(*hash),
 701                              "RSA-FDA FTpsW!");
 702   GNUNET_free (xts);
 703
 704   ok = rsa_gcd_validate(r,n);
 705   gcry_mpi_release (n);
 706   if (ok)
 707     return r;
 708   gcry_mpi_release (r);
 709   return NULL;
 710 }
 711
 712
 713 /**
 714  * Blinds the given message with the given blinding key
 715  *
 716  * @param hash hash of the message to sign
 717  * @param bkey the blinding key
 718  * @param pkey the public key of the signer
 719  * @param[out] buf set to a buffer with the blinded message to be signed
 720  * @param[out] buf_size number of bytes stored in @a buf
 721  * @return #GNUNET_YES if successful, #GNUNET_NO if RSA key is malicious
 722  */
 723 int
 724 GNUNET_CRYPTO_rsa_blind (const struct GNUNET_HashCode *hash,
 725                          const struct GNUNET_CRYPTO_RsaBlindingKeySecret *bks,
 726                          struct GNUNET_CRYPTO_RsaPublicKey *pkey,
 727                          char **buf, size_t *buf_size)
 728 {
 729   struct RsaBlindingKey *bkey;
 730   gcry_mpi_t data;
 731   gcry_mpi_t ne[2];
 732   gcry_mpi_t r_e;
 733   gcry_mpi_t data_r_e;
 734   int ret;
 735
 736   GNUNET_assert (buf != NULL && buf_size != NULL);
 737   ret = key_from_sexp (ne, pkey->sexp, "public-key", "ne");
 738   if (0 != ret)
 739     ret = key_from_sexp (ne, pkey->sexp, "rsa", "ne");
 740   if (0 != ret)
 741   {
 742     GNUNET_break (0);
 743     *buf = NULL;
 744     *buf_size = 0;
 745     return 0;
 746   }
 747
 748   data = rsa_full_domain_hash (pkey, hash);
 749   if (NULL == data)
 750     goto rsa_gcd_validate_failure;
 751
 752   bkey = rsa_blinding_key_derive (pkey, bks);
 753   if (NULL == bkey) {
 754     gcry_mpi_release (data);
 755     goto rsa_gcd_validate_failure;
 756   }
 757
 758   r_e = gcry_mpi_new (0);
 759   gcry_mpi_powm (r_e,
 760                  bkey->r,
 761                  ne[1],
 762                  ne[0]);
 763   data_r_e = gcry_mpi_new (0);
 764   gcry_mpi_mulm (data_r_e,
 765                  data,
 766                  r_e,
 767                  ne[0]);
 768   gcry_mpi_release (data);
 769   gcry_mpi_release (ne[0]);
 770   gcry_mpi_release (ne[1]);
 771   gcry_mpi_release (r_e);
 772   rsa_blinding_key_free (bkey);
 773
 774   *buf_size = numeric_mpi_alloc_n_print (data_r_e, buf);
 775   gcry_mpi_release (data_r_e);
 776   return GNUNET_YES;
 777
 778 rsa_gcd_validate_failure:
 779   /* We know the RSA key is malicious here, so warn the wallet. */
 780   /* GNUNET_break_op (0); */
 781   gcry_mpi_release (ne[0]);
 782   gcry_mpi_release (ne[1]);
 783   *buf = NULL;
 784   *buf_size = 0;
 785   return GNUNET_NO;
 786 }
 787
 788
 789 /**
 790  * Convert an MPI to an S-expression suitable for signature operations.
 791  *
 792  * @param value pointer to the data to convert
 793  * @return converted s-expression
 794  */
 795 static gcry_sexp_t
 796 mpi_to_sexp (gcry_mpi_t value)
 797 {
 798   gcry_sexp_t data = NULL;
 799
 800   GNUNET_assert (0 ==
 801                  gcry_sexp_build (&data,
 802                                   NULL,
 803                                   "(data (flags raw) (value %M))",
 804                                   value));
 805   return data;
 806 }
 807
 808
 809 /**
 810  * Sign the given MPI.
 811  *
 812  * @param key private key to use for the signing
 813  * @param value the MPI to sign
 814  * @return NULL on error, signature on success
 815  */
 816 static struct GNUNET_CRYPTO_RsaSignature *
 817 rsa_sign_mpi (const struct GNUNET_CRYPTO_RsaPrivateKey *key,
 818               gcry_mpi_t value)
 819 {
 820   struct GNUNET_CRYPTO_RsaSignature *sig;
 821   gcry_sexp_t data;
 822   gcry_sexp_t result;
 823   int rc;
 824
 825   data = mpi_to_sexp (value);
 826
 827   if (0 !=
 828       (rc = gcry_pk_sign (&result,
 829                           data,
 830                           key->sexp)))
 831   {
 832     LOG (GNUNET_ERROR_TYPE_WARNING,
 833          _("RSA signing failed at %s:%d: %s\n"),
 834          __FILE__,
 835          __LINE__,
 836          gcry_strerror (rc));
 837     GNUNET_break (0);
 838     return NULL;
 839   }
 840
 841   /* Lenstra protection was first added to libgcrypt 1.6.4
 842    * with commit c17f84bd02d7ee93845e92e20f6ddba814961588.
 843    */
 844 #if GCRYPT_VERSION_NUMBER < 0x010604
 845   /* verify signature (guards against Lenstra's attack with fault injection...) */
 846   struct GNUNET_CRYPTO_RsaPublicKey *public_key = GNUNET_CRYPTO_rsa_private_key_get_public (key);
 847   if (0 !=
 848       gcry_pk_verify (result,
 849                       data,
 850                       public_key->sexp))
 851   {
 852     GNUNET_break (0);
 853     GNUNET_CRYPTO_rsa_public_key_free (public_key);
 854     gcry_sexp_release (data);
 855     gcry_sexp_release (result);
 856     return NULL;
 857   }
 858   GNUNET_CRYPTO_rsa_public_key_free (public_key);
 859 #endif
 860
 861   /* return signature */
 862   gcry_sexp_release (data);
 863   sig = GNUNET_new (struct GNUNET_CRYPTO_RsaSignature);
 864   sig->sexp = result;
 865   return sig;
 866 }
 867
 868
 869 /**
 870  * Sign a blinded value, which must be a full domain hash of a message.
 871  *
 872  * @param key private key to use for the signing
 873  * @param msg the message to sign
 874  * @param msg_len number of bytes in @a msg to sign
 875  * @return NULL on error, signature on success
 876  */
 877 struct GNUNET_CRYPTO_RsaSignature *
 878 GNUNET_CRYPTO_rsa_sign_blinded (const struct GNUNET_CRYPTO_RsaPrivateKey *key,
 879                                 const void *msg,
 880                                 size_t msg_len)
 881 {
 882   gcry_mpi_t v = NULL;
 883   struct GNUNET_CRYPTO_RsaSignature *sig;
 884
 885   GNUNET_assert (0 ==
 886                  gcry_mpi_scan (&v,
 887                                 GCRYMPI_FMT_USG,
 888                                 msg,
 889                                 msg_len,
 890                                 NULL));
 891
 892   sig = rsa_sign_mpi (key, v);
 893   gcry_mpi_release (v);
 894   return sig;
 895 }
 896
 897
 898 /**
 899  * Create and sign a full domain hash of a message.
 900  *
 901  * @param key private key to use for the signing
 902  * @param hash the hash of the message to sign
 903  * @return NULL on error, including a malicious RSA key, signature on success
 904  */
 905 struct GNUNET_CRYPTO_RsaSignature *
 906 GNUNET_CRYPTO_rsa_sign_fdh (const struct GNUNET_CRYPTO_RsaPrivateKey *key,
 907                             const struct GNUNET_HashCode *hash)
 908 {
 909   struct GNUNET_CRYPTO_RsaPublicKey *pkey;
 910   gcry_mpi_t v = NULL;
 911   struct GNUNET_CRYPTO_RsaSignature *sig;
 912
 913   pkey = GNUNET_CRYPTO_rsa_private_key_get_public (key);
 914   v = rsa_full_domain_hash (pkey, hash);
 915   GNUNET_CRYPTO_rsa_public_key_free (pkey);
 916   if (NULL == v)   /* rsa_gcd_validate failed meaning */
 917     return NULL;   /* our *own* RSA key is malicious. */
 918
 919   sig = rsa_sign_mpi (key, v);
 920   gcry_mpi_release (v);
 921   return sig;
 922 }
 923
 924
 925 /**
 926  * Free memory occupied by signature.
 927  *
 928  * @param sig memory to freee
 929  */
 930 void
 931 GNUNET_CRYPTO_rsa_signature_free (struct GNUNET_CRYPTO_RsaSignature *sig)
 932 {
 933   gcry_sexp_release (sig->sexp);
 934   GNUNET_free (sig);
 935 }
 936
 937
 938 /**
 939  * Encode the given signature in a format suitable for storing it into a file.
 940  *
 941  * @param sig the signature
 942  * @param[out] buffer set to a buffer with the encoded key
 943  * @return size of memory allocated in @a buffer
 944  */
 945 size_t
 946 GNUNET_CRYPTO_rsa_signature_encode (const struct GNUNET_CRYPTO_RsaSignature *sig,
 947                                     char **buffer)
 948 {
 949   size_t n;
 950   char *b;
 951
 952   n = gcry_sexp_sprint (sig->sexp,
 953                         GCRYSEXP_FMT_ADVANCED,
 954                         NULL,
 955                         0);
 956   b = GNUNET_malloc (n);
 957   GNUNET_assert ((n - 1) ==     /* since the last byte is \0 */
 958                  gcry_sexp_sprint (sig->sexp,
 959                                    GCRYSEXP_FMT_ADVANCED,
 960                                    b,
 961                                    n));
 962   *buffer = b;
 963   return n;
 964 }
 965
 966
 967 /**
 968  * Decode the signature from the data-format back to the "normal", internal
 969  * format.
 970  *
 971  * @param buf the buffer where the public key data is stored
 972  * @param len the length of the data in @a buf
 973  * @return NULL on error
 974  */
 975 struct GNUNET_CRYPTO_RsaSignature *
 976 GNUNET_CRYPTO_rsa_signature_decode (const char *buf,
 977                                     size_t len)
 978 {
 979   struct GNUNET_CRYPTO_RsaSignature *sig;
 980   int ret;
 981   gcry_mpi_t s;
 982
 983   sig = GNUNET_new (struct GNUNET_CRYPTO_RsaSignature);
 984   if (0 !=
 985       gcry_sexp_new (&sig->sexp,
 986                      buf,
 987                      len,
 988                      0))
 989   {
 990     GNUNET_break_op (0);
 991     GNUNET_free (sig);
 992     return NULL;
 993   }
 994   /* verify that this is an RSA signature */
 995   ret = key_from_sexp (&s, sig->sexp, "sig-val", "s");
 996   if (0 != ret)
 997     ret = key_from_sexp (&s, sig->sexp, "rsa", "s");
 998   if (0 != ret)
 999   {
1000     /* this is no RSA Signature */
1001     GNUNET_break_op (0);
1002     gcry_sexp_release (sig->sexp);
1003     GNUNET_free (sig);
1004     return NULL;
1005   }
1006   gcry_mpi_release (s);
1007   return sig;
1008 }
1009
1010
1011 /**
1012  * Duplicate the given public key
1013  *
1014  * @param key the public key to duplicate
1015  * @return the duplicate key; NULL upon error
1016  */
1017 struct GNUNET_CRYPTO_RsaPublicKey *
1018 GNUNET_CRYPTO_rsa_public_key_dup (const struct GNUNET_CRYPTO_RsaPublicKey *key)
1019 {
1020   struct GNUNET_CRYPTO_RsaPublicKey *dup;
1021   gcry_sexp_t dup_sexp;
1022   size_t erroff;
1023
1024   /* check if we really are exporting a public key */
1025   dup_sexp = gcry_sexp_find_token (key->sexp, "public-key", 0);
1026   GNUNET_assert (NULL != dup_sexp);
1027   gcry_sexp_release (dup_sexp);
1028   /* copy the sexp */
1029   GNUNET_assert (0 == gcry_sexp_build (&dup_sexp, &erroff, "%S", key->sexp));
1030   dup = GNUNET_new (struct GNUNET_CRYPTO_RsaPublicKey);
1031   dup->sexp = dup_sexp;
1032   return dup;
1033 }
1034
1035
1036 /**
1037  * Unblind a blind-signed signature.  The signature should have been generated
1038  * with #GNUNET_CRYPTO_rsa_sign() using a hash that was blinded with
1039  * #GNUNET_CRYPTO_rsa_blind().
1040  *
1041  * @param sig the signature made on the blinded signature purpose
1042  * @param bks the blinding key secret used to blind the signature purpose
1043  * @param pkey the public key of the signer
1044  * @return unblinded signature on success, NULL if RSA key is bad or malicious.
1045  */
1046 struct GNUNET_CRYPTO_RsaSignature *
1047 GNUNET_CRYPTO_rsa_unblind (const struct GNUNET_CRYPTO_RsaSignature *sig,
1048                            const struct GNUNET_CRYPTO_RsaBlindingKeySecret *bks,
1049                            struct GNUNET_CRYPTO_RsaPublicKey *pkey)
1050 {
1051   struct RsaBlindingKey *bkey;
1052   gcry_mpi_t n;
1053   gcry_mpi_t s;
1054   gcry_mpi_t r_inv;
1055   gcry_mpi_t ubsig;
1056   int ret;
1057   struct GNUNET_CRYPTO_RsaSignature *sret;
1058
1059   ret = key_from_sexp (&n, pkey->sexp, "public-key", "n");
1060   if (0 != ret)
1061     ret = key_from_sexp (&n, pkey->sexp, "rsa", "n");
1062   if (0 != ret)
1063   {
1064     GNUNET_break_op (0);
1065     return NULL;
1066   }
1067   ret = key_from_sexp (&s, sig->sexp, "sig-val", "s");
1068   if (0 != ret)
1069     ret = key_from_sexp (&s, sig->sexp, "rsa", "s");
1070   if (0 != ret)
1071   {
1072     gcry_mpi_release (n);
1073     GNUNET_break_op (0);
1074     return NULL;
1075   }
1076
1077   bkey = rsa_blinding_key_derive (pkey, bks);
1078   if (NULL == bkey)
1079   {
1080     /* RSA key is malicious since rsa_gcd_validate failed here.
1081      * It should have failed during GNUNET_CRYPTO_rsa_blind too though,
1082      * so the exchange is being malicious in an unfamilair way, maybe
1083      * just trying to crash us.  */
1084     GNUNET_break_op (0);
1085     gcry_mpi_release (n);
1086     gcry_mpi_release (s);
1087     return NULL;
1088   }
1089
1090   r_inv = gcry_mpi_new (0);
1091   if (1 !=
1092       gcry_mpi_invm (r_inv,
1093                      bkey->r,
1094                      n))
1095   {
1096     /* We cannot find r mod n, so gcd(r,n) != 1, which should get *
1097      * caught above, but we handle it the same here.              */
1098     GNUNET_break_op (0);
1099     gcry_mpi_release (r_inv);
1100     rsa_blinding_key_free (bkey);
1101     gcry_mpi_release (n);
1102     gcry_mpi_release (s);
1103     return NULL;
1104   }
1105
1106   ubsig = gcry_mpi_new (0);
1107   gcry_mpi_mulm (ubsig, s, r_inv, n);
1108   gcry_mpi_release (n);
1109   gcry_mpi_release (r_inv);
1110   gcry_mpi_release (s);
1111   rsa_blinding_key_free (bkey);
1112
1113   sret = GNUNET_new (struct GNUNET_CRYPTO_RsaSignature);
1114   GNUNET_assert (0 ==
1115                  gcry_sexp_build (&sret->sexp,
1116                                   NULL,
1117                                   "(sig-val (rsa (s %M)))",
1118                                   ubsig));
1119   gcry_mpi_release (ubsig);
1120   return sret;
1121 }
1122
1123
1124 /**
1125  * Verify whether the given hash corresponds to the given signature and
1126  * the signature is valid with respect to the given public key.
1127  *
1128  * @param hash hash of the message to verify to match the @a sig
1129  * @param sig signature that is being validated
1130  * @param pkey public key of the signer
1131  * @returns #GNUNET_YES if ok, #GNUNET_NO if RSA key is malicious, #GNUNET_SYSERR if signature is invalid
1132  */
1133 int
1134 GNUNET_CRYPTO_rsa_verify (const struct GNUNET_HashCode *hash,
1135                           const struct GNUNET_CRYPTO_RsaSignature *sig,
1136                           const struct GNUNET_CRYPTO_RsaPublicKey *pkey)
1137 {
1138   gcry_sexp_t data;
1139   gcry_mpi_t r;
1140   int rc;
1141
1142   r = rsa_full_domain_hash (pkey, hash);
1143   if (NULL == r) {
1144     GNUNET_break_op (0);
1145     /* RSA key is malicious since rsa_gcd_validate failed here.
1146      * It should have failed during GNUNET_CRYPTO_rsa_blind too though,
1147      * so the exchange is being malicious in an unfamilair way, maybe
1148      * just trying to crash us.  Arguably, we've only an internal error
1149      * though because we should've detected this in our previous call
1150      * to GNUNET_CRYPTO_rsa_unblind. */
1151     return GNUNET_NO;
1152   }
1153
1154   data = mpi_to_sexp(r);
1155   gcry_mpi_release (r);
1156
1157   rc = gcry_pk_verify (sig->sexp,
1158                        data,
1159                        pkey->sexp);
1160   gcry_sexp_release (data);
1161   if (0 != rc)
1162   {
1163     LOG (GNUNET_ERROR_TYPE_WARNING,
1164          _("RSA signature verification failed at %s:%d: %s\n"),
1165          __FILE__,
1166          __LINE__,
1167          gcry_strerror (rc));
1168     return GNUNET_SYSERR;
1169   }
1170   return GNUNET_OK;
1171 }
1172
1173
1174 /**
1175  * Duplicate the given private key
1176  *
1177  * @param key the private key to duplicate
1178  * @return the duplicate key; NULL upon error
1179  */
1180 struct GNUNET_CRYPTO_RsaPrivateKey *
1181 GNUNET_CRYPTO_rsa_private_key_dup (const struct GNUNET_CRYPTO_RsaPrivateKey *key)
1182 {
1183   struct GNUNET_CRYPTO_RsaPrivateKey *dup;
1184   gcry_sexp_t dup_sexp;
1185   size_t erroff;
1186
1187   /* check if we really are exporting a private key */
1188   dup_sexp = gcry_sexp_find_token (key->sexp, "private-key", 0);
1189   GNUNET_assert (NULL != dup_sexp);
1190   gcry_sexp_release (dup_sexp);
1191   /* copy the sexp */
1192   GNUNET_assert (0 == gcry_sexp_build (&dup_sexp, &erroff, "%S", key->sexp));
1193   dup = GNUNET_new (struct GNUNET_CRYPTO_RsaPrivateKey);
1194   dup->sexp = dup_sexp;
1195   return dup;
1196 }
1197
1198
1199 /**
1200  * Duplicate the given private key
1201  *
1202  * @param key the private key to duplicate
1203  * @return the duplicate key; NULL upon error
1204  */
1205 struct GNUNET_CRYPTO_RsaSignature *
1206 GNUNET_CRYPTO_rsa_signature_dup (const struct GNUNET_CRYPTO_RsaSignature *sig)
1207 {
1208   struct GNUNET_CRYPTO_RsaSignature *dup;
1209   gcry_sexp_t dup_sexp;
1210   size_t erroff;
1211   gcry_mpi_t s;
1212   int ret;
1213
1214   /* verify that this is an RSA signature */
1215   ret = key_from_sexp (&s, sig->sexp, "sig-val", "s");
1216   if (0 != ret)
1217     ret = key_from_sexp (&s, sig->sexp, "rsa", "s");
1218   GNUNET_assert (0 == ret);
1219   gcry_mpi_release (s);
1220   /* copy the sexp */
1221   GNUNET_assert (0 == gcry_sexp_build (&dup_sexp, &erroff, "%S", sig->sexp));
1222   dup = GNUNET_new (struct GNUNET_CRYPTO_RsaSignature);
1223   dup->sexp = dup_sexp;
1224   return dup;
1225 }
1226
1227
1228 /* end of util/rsa.c */