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
 789   BENCHMARK_END (rsa_blind);
 790
 791   return GNUNET_YES;
 792
 793 rsa_gcd_validate_failure:
 794   /* We know the RSA key is malicious here, so warn the wallet. */
 795   /* GNUNET_break_op (0); */
 796   gcry_mpi_release (ne[0]);
 797   gcry_mpi_release (ne[1]);
 798   *buf = NULL;
 799   *buf_size = 0;
 800   return GNUNET_NO;
 801 }
 802
 803
 804 /**
 805  * Convert an MPI to an S-expression suitable for signature operations.
 806  *
 807  * @param value pointer to the data to convert
 808  * @return converted s-expression
 809  */
 810 static gcry_sexp_t
 811 mpi_to_sexp (gcry_mpi_t value)
 812 {
 813   gcry_sexp_t data = NULL;
 814
 815   GNUNET_assert (0 ==
 816                  gcry_sexp_build (&data,
 817                                   NULL,
 818                                   "(data (flags raw) (value %M))",
 819                                   value));
 820   return data;
 821 }
 822
 823
 824 /**
 825  * Sign the given MPI.
 826  *
 827  * @param key private key to use for the signing
 828  * @param value the MPI to sign
 829  * @return NULL on error, signature on success
 830  */
 831 static struct GNUNET_CRYPTO_RsaSignature *
 832 rsa_sign_mpi (const struct GNUNET_CRYPTO_RsaPrivateKey *key,
 833               gcry_mpi_t value)
 834 {
 835   struct GNUNET_CRYPTO_RsaSignature *sig;
 836   gcry_sexp_t data;
 837   gcry_sexp_t result;
 838   int rc;
 839
 840   data = mpi_to_sexp (value);
 841
 842   if (0 !=
 843       (rc = gcry_pk_sign (&result,
 844                           data,
 845                           key->sexp)))
 846   {
 847     LOG (GNUNET_ERROR_TYPE_WARNING,
 848          _("RSA signing failed at %s:%d: %s\n"),
 849          __FILE__,
 850          __LINE__,
 851          gcry_strerror (rc));
 852     GNUNET_break (0);
 853     return NULL;
 854   }
 855
 856   /* Lenstra protection was first added to libgcrypt 1.6.4
 857    * with commit c17f84bd02d7ee93845e92e20f6ddba814961588.
 858    */
 859 #if GCRYPT_VERSION_NUMBER < 0x010604
 860   /* verify signature (guards against Lenstra's attack with fault injection...) */
 861   struct GNUNET_CRYPTO_RsaPublicKey *public_key = GNUNET_CRYPTO_rsa_private_key_get_public (key);
 862   if (0 !=
 863       gcry_pk_verify (result,
 864                       data,
 865                       public_key->sexp))
 866   {
 867     GNUNET_break (0);
 868     GNUNET_CRYPTO_rsa_public_key_free (public_key);
 869     gcry_sexp_release (data);
 870     gcry_sexp_release (result);
 871     return NULL;
 872   }
 873   GNUNET_CRYPTO_rsa_public_key_free (public_key);
 874 #endif
 875
 876   /* return signature */
 877   gcry_sexp_release (data);
 878   sig = GNUNET_new (struct GNUNET_CRYPTO_RsaSignature);
 879   sig->sexp = result;
 880   return sig;
 881 }
 882
 883
 884 /**
 885  * Sign a blinded value, which must be a full domain hash of a message.
 886  *
 887  * @param key private key to use for the signing
 888  * @param msg the message to sign
 889  * @param msg_len number of bytes in @a msg to sign
 890  * @return NULL on error, signature on success
 891  */
 892 struct GNUNET_CRYPTO_RsaSignature *
 893 GNUNET_CRYPTO_rsa_sign_blinded (const struct GNUNET_CRYPTO_RsaPrivateKey *key,
 894                                 const void *msg,
 895                                 size_t msg_len)
 896 {
 897   gcry_mpi_t v = NULL;
 898   struct GNUNET_CRYPTO_RsaSignature *sig;
 899
 900   BENCHMARK_START (rsa_sign_blinded);
 901
 902   GNUNET_assert (0 ==
 903                  gcry_mpi_scan (&v,
 904                                 GCRYMPI_FMT_USG,
 905                                 msg,
 906                                 msg_len,
 907                                 NULL));
 908
 909   sig = rsa_sign_mpi (key, v);
 910   gcry_mpi_release (v);
 911   BENCHMARK_END (rsa_sign_blinded);
 912   return sig;
 913 }
 914
 915
 916 /**
 917  * Create and sign a full domain hash of a message.
 918  *
 919  * @param key private key to use for the signing
 920  * @param hash the hash of the message to sign
 921  * @return NULL on error, including a malicious RSA key, signature on success
 922  */
 923 struct GNUNET_CRYPTO_RsaSignature *
 924 GNUNET_CRYPTO_rsa_sign_fdh (const struct GNUNET_CRYPTO_RsaPrivateKey *key,
 925                             const struct GNUNET_HashCode *hash)
 926 {
 927   struct GNUNET_CRYPTO_RsaPublicKey *pkey;
 928   gcry_mpi_t v = NULL;
 929   struct GNUNET_CRYPTO_RsaSignature *sig;
 930
 931   pkey = GNUNET_CRYPTO_rsa_private_key_get_public (key);
 932   v = rsa_full_domain_hash (pkey, hash);
 933   GNUNET_CRYPTO_rsa_public_key_free (pkey);
 934   if (NULL == v)   /* rsa_gcd_validate failed meaning */
 935     return NULL;   /* our *own* RSA key is malicious. */
 936
 937   sig = rsa_sign_mpi (key, v);
 938   gcry_mpi_release (v);
 939   return sig;
 940 }
 941
 942
 943 /**
 944  * Free memory occupied by signature.
 945  *
 946  * @param sig memory to freee
 947  */
 948 void
 949 GNUNET_CRYPTO_rsa_signature_free (struct GNUNET_CRYPTO_RsaSignature *sig)
 950 {
 951   gcry_sexp_release (sig->sexp);
 952   GNUNET_free (sig);
 953 }
 954
 955
 956 /**
 957  * Encode the given signature in a format suitable for storing it into a file.
 958  *
 959  * @param sig the signature
 960  * @param[out] buffer set to a buffer with the encoded key
 961  * @return size of memory allocated in @a buffer
 962  */
 963 size_t
 964 GNUNET_CRYPTO_rsa_signature_encode (const struct GNUNET_CRYPTO_RsaSignature *sig,
 965                                     char **buffer)
 966 {
 967   size_t n;
 968   char *b;
 969
 970   n = gcry_sexp_sprint (sig->sexp,
 971                         GCRYSEXP_FMT_ADVANCED,
 972                         NULL,
 973                         0);
 974   b = GNUNET_malloc (n);
 975   GNUNET_assert ((n - 1) ==     /* since the last byte is \0 */
 976                  gcry_sexp_sprint (sig->sexp,
 977                                    GCRYSEXP_FMT_ADVANCED,
 978                                    b,
 979                                    n));
 980   *buffer = b;
 981   return n;
 982 }
 983
 984
 985 /**
 986  * Decode the signature from the data-format back to the "normal", internal
 987  * format.
 988  *
 989  * @param buf the buffer where the public key data is stored
 990  * @param len the length of the data in @a buf
 991  * @return NULL on error
 992  */
 993 struct GNUNET_CRYPTO_RsaSignature *
 994 GNUNET_CRYPTO_rsa_signature_decode (const char *buf,
 995                                     size_t len)
 996 {
 997   struct GNUNET_CRYPTO_RsaSignature *sig;
 998   int ret;
 999   gcry_mpi_t s;
1000
1001   sig = GNUNET_new (struct GNUNET_CRYPTO_RsaSignature);
1002   if (0 !=
1003       gcry_sexp_new (&sig->sexp,
1004                      buf,
1005                      len,
1006                      0))
1007   {
1008     GNUNET_break_op (0);
1009     GNUNET_free (sig);
1010     return NULL;
1011   }
1012   /* verify that this is an RSA signature */
1013   ret = key_from_sexp (&s, sig->sexp, "sig-val", "s");
1014   if (0 != ret)
1015     ret = key_from_sexp (&s, sig->sexp, "rsa", "s");
1016   if (0 != ret)
1017   {
1018     /* this is no RSA Signature */
1019     GNUNET_break_op (0);
1020     gcry_sexp_release (sig->sexp);
1021     GNUNET_free (sig);
1022     return NULL;
1023   }
1024   gcry_mpi_release (s);
1025   return sig;
1026 }
1027
1028
1029 /**
1030  * Duplicate the given public key
1031  *
1032  * @param key the public key to duplicate
1033  * @return the duplicate key; NULL upon error
1034  */
1035 struct GNUNET_CRYPTO_RsaPublicKey *
1036 GNUNET_CRYPTO_rsa_public_key_dup (const struct GNUNET_CRYPTO_RsaPublicKey *key)
1037 {
1038   struct GNUNET_CRYPTO_RsaPublicKey *dup;
1039   gcry_sexp_t dup_sexp;
1040   size_t erroff;
1041
1042   /* check if we really are exporting a public key */
1043   dup_sexp = gcry_sexp_find_token (key->sexp, "public-key", 0);
1044   GNUNET_assert (NULL != dup_sexp);
1045   gcry_sexp_release (dup_sexp);
1046   /* copy the sexp */
1047   GNUNET_assert (0 == gcry_sexp_build (&dup_sexp, &erroff, "%S", key->sexp));
1048   dup = GNUNET_new (struct GNUNET_CRYPTO_RsaPublicKey);
1049   dup->sexp = dup_sexp;
1050   return dup;
1051 }
1052
1053
1054 /**
1055  * Unblind a blind-signed signature.  The signature should have been generated
1056  * with #GNUNET_CRYPTO_rsa_sign() using a hash that was blinded with
1057  * #GNUNET_CRYPTO_rsa_blind().
1058  *
1059  * @param sig the signature made on the blinded signature purpose
1060  * @param bks the blinding key secret used to blind the signature purpose
1061  * @param pkey the public key of the signer
1062  * @return unblinded signature on success, NULL if RSA key is bad or malicious.
1063  */
1064 struct GNUNET_CRYPTO_RsaSignature *
1065 GNUNET_CRYPTO_rsa_unblind (const struct GNUNET_CRYPTO_RsaSignature *sig,
1066                            const struct GNUNET_CRYPTO_RsaBlindingKeySecret *bks,
1067                            struct GNUNET_CRYPTO_RsaPublicKey *pkey)
1068 {
1069   struct RsaBlindingKey *bkey;
1070   gcry_mpi_t n;
1071   gcry_mpi_t s;
1072   gcry_mpi_t r_inv;
1073   gcry_mpi_t ubsig;
1074   int ret;
1075   struct GNUNET_CRYPTO_RsaSignature *sret;
1076
1077   BENCHMARK_START (rsa_unblind);
1078
1079   ret = key_from_sexp (&n, pkey->sexp, "public-key", "n");
1080   if (0 != ret)
1081     ret = key_from_sexp (&n, pkey->sexp, "rsa", "n");
1082   if (0 != ret)
1083   {
1084     GNUNET_break_op (0);
1085     return NULL;
1086   }
1087   ret = key_from_sexp (&s, sig->sexp, "sig-val", "s");
1088   if (0 != ret)
1089     ret = key_from_sexp (&s, sig->sexp, "rsa", "s");
1090   if (0 != ret)
1091   {
1092     gcry_mpi_release (n);
1093     GNUNET_break_op (0);
1094     return NULL;
1095   }
1096
1097   bkey = rsa_blinding_key_derive (pkey, bks);
1098   if (NULL == bkey)
1099   {
1100     /* RSA key is malicious since rsa_gcd_validate failed here.
1101      * It should have failed during GNUNET_CRYPTO_rsa_blind too though,
1102      * so the exchange is being malicious in an unfamilair way, maybe
1103      * just trying to crash us.  */
1104     GNUNET_break_op (0);
1105     gcry_mpi_release (n);
1106     gcry_mpi_release (s);
1107     return NULL;
1108   }
1109
1110   r_inv = gcry_mpi_new (0);
1111   if (1 !=
1112       gcry_mpi_invm (r_inv,
1113                      bkey->r,
1114                      n))
1115   {
1116     /* We cannot find r mod n, so gcd(r,n) != 1, which should get *
1117      * caught above, but we handle it the same here.              */
1118     GNUNET_break_op (0);
1119     gcry_mpi_release (r_inv);
1120     rsa_blinding_key_free (bkey);
1121     gcry_mpi_release (n);
1122     gcry_mpi_release (s);
1123     return NULL;
1124   }
1125
1126   ubsig = gcry_mpi_new (0);
1127   gcry_mpi_mulm (ubsig, s, r_inv, n);
1128   gcry_mpi_release (n);
1129   gcry_mpi_release (r_inv);
1130   gcry_mpi_release (s);
1131   rsa_blinding_key_free (bkey);
1132
1133   sret = GNUNET_new (struct GNUNET_CRYPTO_RsaSignature);
1134   GNUNET_assert (0 ==
1135                  gcry_sexp_build (&sret->sexp,
1136                                   NULL,
1137                                   "(sig-val (rsa (s %M)))",
1138                                   ubsig));
1139   gcry_mpi_release (ubsig);
1140   BENCHMARK_END (rsa_unblind);
1141   return sret;
1142 }
1143
1144
1145 /**
1146  * Verify whether the given hash corresponds to the given signature and
1147  * the signature is valid with respect to the given public key.
1148  *
1149  * @param hash hash of the message to verify to match the @a sig
1150  * @param sig signature that is being validated
1151  * @param pkey public key of the signer
1152  * @returns #GNUNET_YES if ok, #GNUNET_NO if RSA key is malicious, #GNUNET_SYSERR if signature is invalid
1153  */
1154 int
1155 GNUNET_CRYPTO_rsa_verify (const struct GNUNET_HashCode *hash,
1156                           const struct GNUNET_CRYPTO_RsaSignature *sig,
1157                           const struct GNUNET_CRYPTO_RsaPublicKey *pkey)
1158 {
1159   gcry_sexp_t data;
1160   gcry_mpi_t r;
1161   int rc;
1162
1163   BENCHMARK_START (rsa_verify);
1164
1165   r = rsa_full_domain_hash (pkey, hash);
1166   if (NULL == r) {
1167     GNUNET_break_op (0);
1168     /* RSA key is malicious since rsa_gcd_validate failed here.
1169      * It should have failed during GNUNET_CRYPTO_rsa_blind too though,
1170      * so the exchange is being malicious in an unfamilair way, maybe
1171      * just trying to crash us.  Arguably, we've only an internal error
1172      * though because we should've detected this in our previous call
1173      * to GNUNET_CRYPTO_rsa_unblind. */
1174     return GNUNET_NO;
1175   }
1176
1177   data = mpi_to_sexp(r);
1178   gcry_mpi_release (r);
1179
1180   rc = gcry_pk_verify (sig->sexp,
1181                        data,
1182                        pkey->sexp);
1183   gcry_sexp_release (data);
1184   if (0 != rc)
1185   {
1186     LOG (GNUNET_ERROR_TYPE_WARNING,
1187          _("RSA signature verification failed at %s:%d: %s\n"),
1188          __FILE__,
1189          __LINE__,
1190          gcry_strerror (rc));
1191     return GNUNET_SYSERR;
1192     BENCHMARK_END (rsa_verify);
1193   }
1194   BENCHMARK_END (rsa_verify);
1195   return GNUNET_OK;
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_RsaPrivateKey *
1206 GNUNET_CRYPTO_rsa_private_key_dup (const struct GNUNET_CRYPTO_RsaPrivateKey *key)
1207 {
1208   struct GNUNET_CRYPTO_RsaPrivateKey *dup;
1209   gcry_sexp_t dup_sexp;
1210   size_t erroff;
1211
1212   /* check if we really are exporting a private key */
1213   dup_sexp = gcry_sexp_find_token (key->sexp, "private-key", 0);
1214   GNUNET_assert (NULL != dup_sexp);
1215   gcry_sexp_release (dup_sexp);
1216   /* copy the sexp */
1217   GNUNET_assert (0 == gcry_sexp_build (&dup_sexp, &erroff, "%S", key->sexp));
1218   dup = GNUNET_new (struct GNUNET_CRYPTO_RsaPrivateKey);
1219   dup->sexp = dup_sexp;
1220   return dup;
1221 }
1222
1223
1224 /**
1225  * Duplicate the given private key
1226  *
1227  * @param key the private key to duplicate
1228  * @return the duplicate key; NULL upon error
1229  */
1230 struct GNUNET_CRYPTO_RsaSignature *
1231 GNUNET_CRYPTO_rsa_signature_dup (const struct GNUNET_CRYPTO_RsaSignature *sig)
1232 {
1233   struct GNUNET_CRYPTO_RsaSignature *dup;
1234   gcry_sexp_t dup_sexp;
1235   size_t erroff;
1236   gcry_mpi_t s;
1237   int ret;
1238
1239   /* verify that this is an RSA signature */
1240   ret = key_from_sexp (&s, sig->sexp, "sig-val", "s");
1241   if (0 != ret)
1242     ret = key_from_sexp (&s, sig->sexp, "rsa", "s");
1243   GNUNET_assert (0 == ret);
1244   gcry_mpi_release (s);
1245   /* copy the sexp */
1246   GNUNET_assert (0 == gcry_sexp_build (&dup_sexp, &erroff, "%S", sig->sexp));
1247   dup = GNUNET_new (struct GNUNET_CRYPTO_RsaSignature);
1248   dup->sexp = dup_sexp;
1249   return dup;
1250 }
1251
1252
1253 /* end of util/rsa.c */