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