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