src/util/crypto_rsa.c

   1 /*
   2    This file is part of GNUnet
   3    Copyright (C) 2014,2016,2019 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 GNUNET_NETWORK_STRUCT_BEGIN
 313
 314 /**
 315  * Format of the header of a serialized RSA public key.
 316  */
 317 struct GNUNET_CRYPTO_RsaPublicKeyHeaderP
 318 {
 319   /**
 320    * length of modulus 'n' in bytes, in NBO
 321    */
 322   uint16_t modulus_length GNUNET_PACKED;
 323
 324   /**
 325    * length of exponent in bytes, in NBO
 326    */
 327   uint16_t public_exponent_length GNUNET_PACKED;
 328
 329   /* followed by variable-size modulus and
 330      public exponent follows as big-endian encoded
 331      integers */
 332 };
 333
 334 GNUNET_NETWORK_STRUCT_END
 335
 336
 337 /**
 338  * Encode the public key in a format suitable for
 339  * storing it into a file.
 340  *
 341  * @param key the private key
 342  * @param[out] buffer set to a buffer with the encoded key
 343  * @return size of memory allocated in @a buffer
 344  */
 345 size_t
 346 GNUNET_CRYPTO_rsa_public_key_encode (const struct
 347                                      GNUNET_CRYPTO_RsaPublicKey *key,
 348                                      char **buffer)
 349 {
 350   gcry_mpi_t ne[2];
 351   size_t n_size;
 352   size_t e_size;
 353   size_t rsize;
 354   size_t buf_size;
 355   char *buf;
 356   struct GNUNET_CRYPTO_RsaPublicKeyHeaderP hdr;
 357   int ret;
 358
 359   ret = key_from_sexp (ne, key->sexp, "public-key", "ne");
 360   if (0 != ret)
 361     ret = key_from_sexp (ne, key->sexp, "rsa", "ne");
 362   if (0 != ret)
 363   {
 364     GNUNET_break (0);
 365     *buffer = NULL;
 366     return 0;
 367   }
 368   gcry_mpi_print (GCRYMPI_FMT_USG,
 369                   NULL,
 370                   0,
 371                   &n_size,
 372                   ne[0]);
 373   gcry_mpi_print (GCRYMPI_FMT_USG,
 374                   NULL,
 375                   0,
 376                   &e_size,
 377                   ne[1]);
 378   if ( (e_size > UINT16_MAX) ||
 379        (n_size > UINT16_MAX) )
 380   {
 381     GNUNET_break (0);
 382     *buffer = NULL;
 383     gcry_mpi_release (ne[0]);
 384     gcry_mpi_release (ne[1]);
 385     return 0;
 386   }
 387   buf_size = n_size + e_size + sizeof (hdr);
 388   buf = GNUNET_malloc (buf_size);
 389   hdr.modulus_length = htons ((uint16_t) n_size);
 390   hdr.public_exponent_length = htons ((uint16_t) e_size);
 391   memcpy (buf, &hdr, sizeof (hdr));
 392   GNUNET_assert (0 ==
 393                  gcry_mpi_print (GCRYMPI_FMT_USG,
 394                                  (unsigned char *) &buf[sizeof (hdr)],
 395                                  n_size,
 396                                  &rsize,
 397                                  ne[0]));
 398
 399   GNUNET_assert (0 ==
 400                  gcry_mpi_print (GCRYMPI_FMT_USG,
 401                                  (unsigned char *) &buf[sizeof (hdr) + n_size],
 402                                  e_size,
 403                                  &rsize,
 404                                  ne[1]));
 405   *buffer = buf;
 406   gcry_mpi_release (ne[0]);
 407   gcry_mpi_release (ne[1]);
 408   return buf_size;
 409 }
 410
 411
 412 /**
 413  * Compute hash over the public key.
 414  *
 415  * @param key public key to hash
 416  * @param hc where to store the hash code
 417  */
 418 void
 419 GNUNET_CRYPTO_rsa_public_key_hash (const struct GNUNET_CRYPTO_RsaPublicKey *key,
 420                                    struct GNUNET_HashCode *hc)
 421 {
 422   char *buf;
 423   size_t buf_size;
 424
 425   buf_size = GNUNET_CRYPTO_rsa_public_key_encode (key,
 426                                                   &buf);
 427   GNUNET_CRYPTO_hash (buf,
 428                       buf_size,
 429                       hc);
 430   GNUNET_free (buf);
 431 }
 432
 433
 434 /**
 435  * Decode the public key from the data-format back
 436  * to the "normal", internal format.
 437  *
 438  * @param buf the buffer where the public key data is stored
 439  * @param len the length of the data in @a buf
 440  * @return NULL on error
 441  */
 442 struct GNUNET_CRYPTO_RsaPublicKey *
 443 GNUNET_CRYPTO_rsa_public_key_decode (const char *buf,
 444                                      size_t len)
 445 {
 446   struct GNUNET_CRYPTO_RsaPublicKey *key;
 447   struct GNUNET_CRYPTO_RsaPublicKeyHeaderP hdr;
 448   size_t e_size;
 449   size_t n_size;
 450   gcry_mpi_t n;
 451   gcry_mpi_t e;
 452   gcry_sexp_t data;
 453
 454   if (len < sizeof (hdr))
 455   {
 456     GNUNET_break_op (0);
 457     return NULL;
 458   }
 459   memcpy (&hdr, buf, sizeof (hdr));
 460   n_size = ntohs (hdr.modulus_length);
 461   e_size = ntohs (hdr.public_exponent_length);
 462   if (len != sizeof (hdr) + e_size + n_size)
 463   {
 464     GNUNET_break_op (0);
 465     return NULL;
 466   }
 467   if (0 !=
 468       gcry_mpi_scan (&n,
 469                      GCRYMPI_FMT_USG,
 470                      &buf[sizeof (hdr)],
 471                      n_size,
 472                      NULL))
 473   {
 474     GNUNET_break_op (0);
 475     return NULL;
 476   }
 477   if (0 !=
 478       gcry_mpi_scan (&e,
 479                      GCRYMPI_FMT_USG,
 480                      &buf[sizeof (hdr) + n_size],
 481                      e_size,
 482                      NULL))
 483   {
 484     GNUNET_break_op (0);
 485     gcry_mpi_release (n);
 486     return NULL;
 487   }
 488
 489   if (0 !=
 490       gcry_sexp_build (&data,
 491                        NULL,
 492                        "(public-key(rsa(n %m)(e %m)))",
 493                        n,
 494                        e))
 495   {
 496     GNUNET_break (0);
 497     gcry_mpi_release (n);
 498     gcry_mpi_release (e);
 499     return NULL;
 500   }
 501   gcry_mpi_release (n);
 502   gcry_mpi_release (e);
 503   key = GNUNET_new (struct GNUNET_CRYPTO_RsaPublicKey);
 504   key->sexp = data;
 505   return key;
 506 }
 507
 508
 509 /**
 510  * Test for malicious RSA key.
 511  *
 512  * Assuming n is an RSA modulous and r is generated using a call to
 513  * GNUNET_CRYPTO_kdf_mod_mpi, if gcd(r,n) != 1 then n must be a
 514  * malicious RSA key designed to deanomize the user.
 515  *
 516  * @param r KDF result
 517  * @param n RSA modulus
 518  * @return True if gcd(r,n) = 1, False means RSA key is malicious
 519  */
 520 static int
 521 rsa_gcd_validate (gcry_mpi_t r, gcry_mpi_t n)
 522 {
 523   gcry_mpi_t g;
 524   int t;
 525
 526   g = gcry_mpi_new (0);
 527   t = gcry_mpi_gcd (g, r, n);
 528   gcry_mpi_release (g);
 529   return t;
 530 }
 531
 532
 533 /**
 534  * Create a blinding key
 535  *
 536  * @param len length of the key in bits (i.e. 2048)
 537  * @param bks pre-secret to use to derive the blinding key
 538  * @return the newly created blinding key, NULL if RSA key is malicious
 539  */
 540 static struct RsaBlindingKey *
 541 rsa_blinding_key_derive (const struct GNUNET_CRYPTO_RsaPublicKey *pkey,
 542                          const struct GNUNET_CRYPTO_RsaBlindingKeySecret *bks)
 543 {
 544   char *xts = "Blinding KDF extrator HMAC key";  /* Trusts bks' randomness more */
 545   struct RsaBlindingKey *blind;
 546   gcry_mpi_t n;
 547
 548   blind = GNUNET_new (struct RsaBlindingKey);
 549   GNUNET_assert (NULL != blind);
 550
 551   /* Extract the composite n from the RSA public key */
 552   GNUNET_assert (0 == key_from_sexp (&n, pkey->sexp, "rsa", "n"));
 553   /* Assert that it at least looks like an RSA key */
 554   GNUNET_assert (0 == gcry_mpi_get_flag (n, GCRYMPI_FLAG_OPAQUE));
 555
 556   GNUNET_CRYPTO_kdf_mod_mpi (&blind->r,
 557                              n,
 558                              xts, strlen (xts),
 559                              bks, sizeof(*bks),
 560                              "Blinding KDF");
 561   if (0 == rsa_gcd_validate (blind->r, n))
 562   {
 563     GNUNET_free (blind);
 564     blind = NULL;
 565   }
 566
 567   gcry_mpi_release (n);
 568   return blind;
 569 }
 570
 571
 572 /*
 573    We originally added GNUNET_CRYPTO_kdf_mod_mpi for the benifit of the
 574    previous routine.
 575
 576    There was previously a call to GNUNET_CRYPTO_kdf in
 577    bkey = rsa_blinding_key_derive (len, bks);
 578    that gives exactly len bits where
 579    len = GNUNET_CRYPTO_rsa_public_key_len (pkey);
 580
 581    Now r = 2^(len-1)/pkey.n is the probability that a set high bit being
 582    okay, meaning bkey < pkey.n.  It follows that (1-r)/2 of the time bkey >
 583    pkey.n making the effective bkey be
 584    bkey mod pkey.n = bkey - pkey.n
 585    so the effective bkey has its high bit set with probability r/2.
 586
 587    We expect r to be close to 1/2 if the exchange is honest, but the
 588    exchange can choose r otherwise.
 589
 590    In blind signing, the exchange sees
 591    B = bkey * S mod pkey.n
 592    On deposit, the exchange sees S so they can compute bkey' = B/S mod
 593    pkey.n for all B they recorded to see if bkey' has it's high bit set.
 594    Also, note the exchange can compute 1/S efficiently since they know the
 595    factors of pkey.n.
 596
 597    I suppose that happens with probability r/(1+r) if its the wrong B, not
 598    completely sure.  If otoh we've the right B, then we've the probability
 599    r/2 of a set high bit in the effective bkey.
 600
 601    Interestingly, r^2-r has a maximum at the default r=1/2 anyways, giving
 602    the wrong and right probabilities 1/3 and 1/4, respectively.
 603
 604    I feared this gives the exchange a meaningful fraction of a bit of
 605    information per coin involved in the transaction.  It sounds damaging if
 606    numerous coins were involved.  And it could run across transactions in
 607    some scenarios.
 608
 609    We fixed this by using a more uniform deterministic pseudo-random number
 610    generator for blinding factors.  I do not believe this to be a problem
 611    for the rsa_full_domain_hash routine, but better safe than sorry.
 612  */
 613
 614
 615 /**
 616  * Compare the values of two signatures.
 617  *
 618  * @param s1 one signature
 619  * @param s2 the other signature
 620  * @return 0 if the two are equal
 621  */
 622 int
 623 GNUNET_CRYPTO_rsa_signature_cmp (struct GNUNET_CRYPTO_RsaSignature *s1,
 624                                  struct GNUNET_CRYPTO_RsaSignature *s2)
 625 {
 626   char *b1;
 627   char *b2;
 628   size_t z1;
 629   size_t z2;
 630   int ret;
 631
 632   z1 = GNUNET_CRYPTO_rsa_signature_encode (s1,
 633                                            &b1);
 634   z2 = GNUNET_CRYPTO_rsa_signature_encode (s2,
 635                                            &b2);
 636   if (z1 != z2)
 637     ret = 1;
 638   else
 639     ret = memcmp (b1,
 640                   b2,
 641                   z1);
 642   GNUNET_free (b1);
 643   GNUNET_free (b2);
 644   return ret;
 645 }
 646
 647
 648 /**
 649  * Compare the values of two public keys.
 650  *
 651  * @param p1 one public key
 652  * @param p2 the other public key
 653  * @return 0 if the two are equal
 654  */
 655 int
 656 GNUNET_CRYPTO_rsa_public_key_cmp (struct GNUNET_CRYPTO_RsaPublicKey *p1,
 657                                   struct GNUNET_CRYPTO_RsaPublicKey *p2)
 658 {
 659   char *b1;
 660   char *b2;
 661   size_t z1;
 662   size_t z2;
 663   int ret;
 664
 665   z1 = GNUNET_CRYPTO_rsa_public_key_encode (p1,
 666                                             &b1);
 667   z2 = GNUNET_CRYPTO_rsa_public_key_encode (p2,
 668                                             &b2);
 669   if (z1 != z2)
 670     ret = 1;
 671   else
 672     ret = memcmp (b1,
 673                   b2,
 674                   z1);
 675   GNUNET_free (b1);
 676   GNUNET_free (b2);
 677   return ret;
 678 }
 679
 680
 681 /**
 682  * Compare the values of two private keys.
 683  *
 684  * @param p1 one private key
 685  * @param p2 the other private key
 686  * @return 0 if the two are equal
 687  */
 688 int
 689 GNUNET_CRYPTO_rsa_private_key_cmp (struct GNUNET_CRYPTO_RsaPrivateKey *p1,
 690                                    struct GNUNET_CRYPTO_RsaPrivateKey *p2)
 691 {
 692   char *b1;
 693   char *b2;
 694   size_t z1;
 695   size_t z2;
 696   int ret;
 697
 698   z1 = GNUNET_CRYPTO_rsa_private_key_encode (p1,
 699                                              &b1);
 700   z2 = GNUNET_CRYPTO_rsa_private_key_encode (p2,
 701                                              &b2);
 702   if (z1 != z2)
 703     ret = 1;
 704   else
 705     ret = memcmp (b1,
 706                   b2,
 707                   z1);
 708   GNUNET_free (b1);
 709   GNUNET_free (b2);
 710   return ret;
 711 }
 712
 713
 714 /**
 715  * Obtain the length of the RSA key in bits.
 716  *
 717  * @param key the public key to introspect
 718  * @return length of the key in bits
 719  */
 720 unsigned int
 721 GNUNET_CRYPTO_rsa_public_key_len (const struct GNUNET_CRYPTO_RsaPublicKey *key)
 722 {
 723   gcry_mpi_t n;
 724   unsigned int rval;
 725
 726   if (0 != key_from_sexp (&n, key->sexp, "rsa", "n"))
 727   {   /* Not an RSA public key */
 728     GNUNET_break (0);
 729     return 0;
 730   }
 731   rval = gcry_mpi_get_nbits (n);
 732   gcry_mpi_release (n);
 733   return rval;
 734 }
 735
 736
 737 /**
 738  * Destroy a blinding key
 739  *
 740  * @param bkey the blinding key to destroy
 741  */
 742 static void
 743 rsa_blinding_key_free (struct RsaBlindingKey *bkey)
 744 {
 745   gcry_mpi_release (bkey->r);
 746   GNUNET_free (bkey);
 747 }
 748
 749
 750 /**
 751  * Print an MPI to a newly created buffer
 752  *
 753  * @param v MPI to print.
 754  * @param[out] newly allocated buffer containing the result
 755  * @return number of bytes stored in @a buffer
 756  */
 757 static size_t
 758 numeric_mpi_alloc_n_print (gcry_mpi_t v,
 759                            char **buffer)
 760 {
 761   size_t n;
 762   char *b;
 763   size_t rsize;
 764
 765   gcry_mpi_print (GCRYMPI_FMT_USG,
 766                   NULL,
 767                   0,
 768                   &n,
 769                   v);
 770   b = GNUNET_malloc (n);
 771   GNUNET_assert (0 ==
 772                  gcry_mpi_print (GCRYMPI_FMT_USG,
 773                                  (unsigned char *) b,
 774                                  n,
 775                                  &rsize,
 776                                  v));
 777   *buffer = b;
 778   return n;
 779 }
 780
 781
 782 /**
 783  * Computes a full domain hash seeded by the given public key.
 784  * This gives a measure of provable security to the Taler exchange
 785  * against one-more forgery attacks.  See:
 786  *   https://eprint.iacr.org/2001/002.pdf
 787  *   http://www.di.ens.fr/~pointche/Documents/Papers/2001_fcA.pdf
 788  *
 789  * @param hash initial hash of the message to sign
 790  * @param pkey the public key of the signer
 791  * @param rsize If not NULL, the number of bytes actually stored in buffer
 792  * @return MPI value set to the FDH, NULL if RSA key is malicious
 793  */
 794 static gcry_mpi_t
 795 rsa_full_domain_hash (const struct GNUNET_CRYPTO_RsaPublicKey *pkey,
 796                       const struct GNUNET_HashCode *hash)
 797 {
 798   gcry_mpi_t r, n;
 799   char *xts;
 800   size_t xts_len;
 801   int ok;
 802
 803   /* Extract the composite n from the RSA public key */
 804   GNUNET_assert (0 == key_from_sexp (&n, pkey->sexp, "rsa", "n"));
 805   /* Assert that it at least looks like an RSA key */
 806   GNUNET_assert (0 == gcry_mpi_get_flag (n, GCRYMPI_FLAG_OPAQUE));
 807
 808   /* We key with the public denomination key as a homage to RSA-PSS by  *
 809   * Mihir Bellare and Phillip Rogaway.  Doing this lowers the degree   *
 810   * of the hypothetical polyomial-time attack on RSA-KTI created by a  *
 811   * polynomial-time one-more forgary attack.  Yey seeding!             */
 812   xts_len = GNUNET_CRYPTO_rsa_public_key_encode (pkey, &xts);
 813
 814   GNUNET_CRYPTO_kdf_mod_mpi (&r,
 815                              n,
 816                              xts, xts_len,
 817                              hash, sizeof(*hash),
 818                              "RSA-FDA FTpsW!");
 819   GNUNET_free (xts);
 820
 821   ok = rsa_gcd_validate (r, n);
 822   gcry_mpi_release (n);
 823   if (ok)
 824     return r;
 825   gcry_mpi_release (r);
 826   return NULL;
 827 }
 828
 829
 830 /**
 831  * Blinds the given message with the given blinding key
 832  *
 833  * @param hash hash of the message to sign
 834  * @param bkey the blinding key
 835  * @param pkey the public key of the signer
 836  * @param[out] buf set to a buffer with the blinded message to be signed
 837  * @param[out] buf_size number of bytes stored in @a buf
 838  * @return #GNUNET_YES if successful, #GNUNET_NO if RSA key is malicious
 839  */
 840 int
 841 GNUNET_CRYPTO_rsa_blind (const struct GNUNET_HashCode *hash,
 842                          const struct GNUNET_CRYPTO_RsaBlindingKeySecret *bks,
 843                          struct GNUNET_CRYPTO_RsaPublicKey *pkey,
 844                          char **buf, size_t *buf_size)
 845 {
 846   struct RsaBlindingKey *bkey;
 847   gcry_mpi_t data;
 848   gcry_mpi_t ne[2];
 849   gcry_mpi_t r_e;
 850   gcry_mpi_t data_r_e;
 851   int ret;
 852
 853   BENCHMARK_START (rsa_blind);
 854
 855   GNUNET_assert (buf != NULL && buf_size != NULL);
 856   ret = key_from_sexp (ne, pkey->sexp, "public-key", "ne");
 857   if (0 != ret)
 858     ret = key_from_sexp (ne, pkey->sexp, "rsa", "ne");
 859   if (0 != ret)
 860   {
 861     GNUNET_break (0);
 862     *buf = NULL;
 863     *buf_size = 0;
 864     return 0;
 865   }
 866
 867   data = rsa_full_domain_hash (pkey, hash);
 868   if (NULL == data)
 869     goto rsa_gcd_validate_failure;
 870
 871   bkey = rsa_blinding_key_derive (pkey, bks);
 872   if (NULL == bkey)
 873   {
 874     gcry_mpi_release (data);
 875     goto rsa_gcd_validate_failure;
 876   }
 877
 878   r_e = gcry_mpi_new (0);
 879   gcry_mpi_powm (r_e,
 880                  bkey->r,
 881                  ne[1],
 882                  ne[0]);
 883   data_r_e = gcry_mpi_new (0);
 884   gcry_mpi_mulm (data_r_e,
 885                  data,
 886                  r_e,
 887                  ne[0]);
 888   gcry_mpi_release (data);
 889   gcry_mpi_release (ne[0]);
 890   gcry_mpi_release (ne[1]);
 891   gcry_mpi_release (r_e);
 892   rsa_blinding_key_free (bkey);
 893
 894   *buf_size = numeric_mpi_alloc_n_print (data_r_e, buf);
 895   gcry_mpi_release (data_r_e);
 896
 897   BENCHMARK_END (rsa_blind);
 898
 899   return GNUNET_YES;
 900
 901 rsa_gcd_validate_failure:
 902   /* We know the RSA key is malicious here, so warn the wallet. */
 903   /* GNUNET_break_op (0); */
 904   gcry_mpi_release (ne[0]);
 905   gcry_mpi_release (ne[1]);
 906   *buf = NULL;
 907   *buf_size = 0;
 908   return GNUNET_NO;
 909 }
 910
 911
 912 /**
 913  * Convert an MPI to an S-expression suitable for signature operations.
 914  *
 915  * @param value pointer to the data to convert
 916  * @return converted s-expression
 917  */
 918 static gcry_sexp_t
 919 mpi_to_sexp (gcry_mpi_t value)
 920 {
 921   gcry_sexp_t data = NULL;
 922
 923   GNUNET_assert (0 ==
 924                  gcry_sexp_build (&data,
 925                                   NULL,
 926                                   "(data (flags raw) (value %M))",
 927                                   value));
 928   return data;
 929 }
 930
 931
 932 /**
 933  * Sign the given MPI.
 934  *
 935  * @param key private key to use for the signing
 936  * @param value the MPI to sign
 937  * @return NULL on error, signature on success
 938  */
 939 static struct GNUNET_CRYPTO_RsaSignature *
 940 rsa_sign_mpi (const struct GNUNET_CRYPTO_RsaPrivateKey *key,
 941               gcry_mpi_t value)
 942 {
 943   struct GNUNET_CRYPTO_RsaSignature *sig;
 944   gcry_sexp_t data;
 945   gcry_sexp_t result;
 946   int rc;
 947
 948   data = mpi_to_sexp (value);
 949
 950   if (0 !=
 951       (rc = gcry_pk_sign (&result,
 952                           data,
 953                           key->sexp)))
 954   {
 955     LOG (GNUNET_ERROR_TYPE_WARNING,
 956          _ ("RSA signing failed at %s:%d: %s\n"),
 957          __FILE__,
 958          __LINE__,
 959          gcry_strerror (rc));
 960     GNUNET_break (0);
 961     return NULL;
 962   }
 963
 964   /* Lenstra protection was first added to libgcrypt 1.6.4
 965    * with commit c17f84bd02d7ee93845e92e20f6ddba814961588.
 966    */
 967 #if GCRYPT_VERSION_NUMBER < 0x010604
 968   /* verify signature (guards against Lenstra's attack with fault injection...) */
 969   struct GNUNET_CRYPTO_RsaPublicKey *public_key =
 970     GNUNET_CRYPTO_rsa_private_key_get_public (key);
 971   if (0 !=
 972       gcry_pk_verify (result,
 973                       data,
 974                       public_key->sexp))
 975   {
 976     GNUNET_break (0);
 977     GNUNET_CRYPTO_rsa_public_key_free (public_key);
 978     gcry_sexp_release (data);
 979     gcry_sexp_release (result);
 980     return NULL;
 981   }
 982   GNUNET_CRYPTO_rsa_public_key_free (public_key);
 983 #endif
 984
 985   /* return signature */
 986   gcry_sexp_release (data);
 987   sig = GNUNET_new (struct GNUNET_CRYPTO_RsaSignature);
 988   sig->sexp = result;
 989   return sig;
 990 }
 991
 992
 993 /**
 994  * Sign a blinded value, which must be a full domain hash of a message.
 995  *
 996  * @param key private key to use for the signing
 997  * @param msg the message to sign
 998  * @param msg_len number of bytes in @a msg to sign
 999  * @return NULL on error, signature on success
1000  */
1001 struct GNUNET_CRYPTO_RsaSignature *
1002 GNUNET_CRYPTO_rsa_sign_blinded (const struct GNUNET_CRYPTO_RsaPrivateKey *key,
1003                                 const void *msg,
1004                                 size_t msg_len)
1005 {
1006   gcry_mpi_t v = NULL;
1007   struct GNUNET_CRYPTO_RsaSignature *sig;
1008
1009   BENCHMARK_START (rsa_sign_blinded);
1010
1011   GNUNET_assert (0 ==
1012                  gcry_mpi_scan (&v,
1013                                 GCRYMPI_FMT_USG,
1014                                 msg,
1015                                 msg_len,
1016                                 NULL));
1017
1018   sig = rsa_sign_mpi (key, v);
1019   gcry_mpi_release (v);
1020   BENCHMARK_END (rsa_sign_blinded);
1021   return sig;
1022 }
1023
1024
1025 /**
1026  * Create and sign a full domain hash of a message.
1027  *
1028  * @param key private key to use for the signing
1029  * @param hash the hash of the message to sign
1030  * @return NULL on error, including a malicious RSA key, signature on success
1031  */
1032 struct GNUNET_CRYPTO_RsaSignature *
1033 GNUNET_CRYPTO_rsa_sign_fdh (const struct GNUNET_CRYPTO_RsaPrivateKey *key,
1034                             const struct GNUNET_HashCode *hash)
1035 {
1036   struct GNUNET_CRYPTO_RsaPublicKey *pkey;
1037   gcry_mpi_t v = NULL;
1038   struct GNUNET_CRYPTO_RsaSignature *sig;
1039
1040   pkey = GNUNET_CRYPTO_rsa_private_key_get_public (key);
1041   v = rsa_full_domain_hash (pkey, hash);
1042   GNUNET_CRYPTO_rsa_public_key_free (pkey);
1043   if (NULL == v)   /* rsa_gcd_validate failed meaning */
1044     return NULL;   /* our *own* RSA key is malicious. */
1045
1046   sig = rsa_sign_mpi (key, v);
1047   gcry_mpi_release (v);
1048   return sig;
1049 }
1050
1051
1052 /**
1053  * Free memory occupied by signature.
1054  *
1055  * @param sig memory to freee
1056  */
1057 void
1058 GNUNET_CRYPTO_rsa_signature_free (struct GNUNET_CRYPTO_RsaSignature *sig)
1059 {
1060   gcry_sexp_release (sig->sexp);
1061   GNUNET_free (sig);
1062 }
1063
1064
1065 /**
1066  * Encode the given signature in a format suitable for storing it into a file.
1067  *
1068  * @param sig the signature
1069  * @param[out] buffer set to a buffer with the encoded key
1070  * @return size of memory allocated in @a buffer
1071  */
1072 size_t
1073 GNUNET_CRYPTO_rsa_signature_encode (const struct
1074                                     GNUNET_CRYPTO_RsaSignature *sig,
1075                                     char **buffer)
1076 {
1077   gcry_mpi_t s;
1078   size_t buf_size;
1079   size_t rsize;
1080   unsigned char *buf;
1081   int ret;
1082
1083   ret = key_from_sexp (&s,
1084                        sig->sexp,
1085                        "sig-val",
1086                        "s");
1087   if (0 != ret)
1088     ret = key_from_sexp (&s,
1089                          sig->sexp,
1090                          "rsa",
1091                          "s");
1092   GNUNET_assert (0 == ret);
1093   gcry_mpi_print (GCRYMPI_FMT_USG,
1094                   NULL,
1095                   0,
1096                   &buf_size,
1097                   s);
1098   buf = GNUNET_malloc (buf_size);
1099   GNUNET_assert (0 ==
1100                  gcry_mpi_print (GCRYMPI_FMT_USG,
1101                                  buf,
1102                                  buf_size,
1103                                  &rsize,
1104                                  s));
1105   GNUNET_assert (rsize == buf_size);
1106   *buffer = (char *) buf;
1107   gcry_mpi_release (s);
1108   return buf_size;
1109 }
1110
1111
1112 /**
1113  * Decode the signature from the data-format back to the "normal", internal
1114  * format.
1115  *
1116  * @param buf the buffer where the public key data is stored
1117  * @param len the length of the data in @a buf
1118  * @return NULL on error
1119  */
1120 struct GNUNET_CRYPTO_RsaSignature *
1121 GNUNET_CRYPTO_rsa_signature_decode (const char *buf,
1122                                     size_t len)
1123 {
1124   struct GNUNET_CRYPTO_RsaSignature *sig;
1125   gcry_mpi_t s;
1126   gcry_sexp_t data;
1127
1128   if (0 !=
1129       gcry_mpi_scan (&s,
1130                      GCRYMPI_FMT_USG,
1131                      buf,
1132                      len,
1133                      NULL))
1134   {
1135     GNUNET_break_op (0);
1136     return NULL;
1137   }
1138
1139   if (0 !=
1140       gcry_sexp_build (&data,
1141                        NULL,
1142                        "(sig-val(rsa(s %M)))",
1143                        s))
1144   {
1145     GNUNET_break (0);
1146     gcry_mpi_release (s);
1147     return NULL;
1148   }
1149   gcry_mpi_release (s);
1150   sig = GNUNET_new (struct GNUNET_CRYPTO_RsaSignature);
1151   sig->sexp = data;
1152   return sig;
1153 }
1154
1155
1156 /**
1157  * Duplicate the given public key
1158  *
1159  * @param key the public key to duplicate
1160  * @return the duplicate key; NULL upon error
1161  */
1162 struct GNUNET_CRYPTO_RsaPublicKey *
1163 GNUNET_CRYPTO_rsa_public_key_dup (const struct GNUNET_CRYPTO_RsaPublicKey *key)
1164 {
1165   struct GNUNET_CRYPTO_RsaPublicKey *dup;
1166   gcry_sexp_t dup_sexp;
1167   size_t erroff;
1168
1169   /* check if we really are exporting a public key */
1170   dup_sexp = gcry_sexp_find_token (key->sexp, "public-key", 0);
1171   GNUNET_assert (NULL != dup_sexp);
1172   gcry_sexp_release (dup_sexp);
1173   /* copy the sexp */
1174   GNUNET_assert (0 == gcry_sexp_build (&dup_sexp, &erroff, "%S", key->sexp));
1175   dup = GNUNET_new (struct GNUNET_CRYPTO_RsaPublicKey);
1176   dup->sexp = dup_sexp;
1177   return dup;
1178 }
1179
1180
1181 /**
1182  * Unblind a blind-signed signature.  The signature should have been generated
1183  * with #GNUNET_CRYPTO_rsa_sign() using a hash that was blinded with
1184  * #GNUNET_CRYPTO_rsa_blind().
1185  *
1186  * @param sig the signature made on the blinded signature purpose
1187  * @param bks the blinding key secret used to blind the signature purpose
1188  * @param pkey the public key of the signer
1189  * @return unblinded signature on success, NULL if RSA key is bad or malicious.
1190  */
1191 struct GNUNET_CRYPTO_RsaSignature *
1192 GNUNET_CRYPTO_rsa_unblind (const struct GNUNET_CRYPTO_RsaSignature *sig,
1193                            const struct GNUNET_CRYPTO_RsaBlindingKeySecret *bks,
1194                            struct GNUNET_CRYPTO_RsaPublicKey *pkey)
1195 {
1196   struct RsaBlindingKey *bkey;
1197   gcry_mpi_t n;
1198   gcry_mpi_t s;
1199   gcry_mpi_t r_inv;
1200   gcry_mpi_t ubsig;
1201   int ret;
1202   struct GNUNET_CRYPTO_RsaSignature *sret;
1203
1204   BENCHMARK_START (rsa_unblind);
1205
1206   ret = key_from_sexp (&n, pkey->sexp, "public-key", "n");
1207   if (0 != ret)
1208     ret = key_from_sexp (&n, pkey->sexp, "rsa", "n");
1209   if (0 != ret)
1210   {
1211     GNUNET_break_op (0);
1212     return NULL;
1213   }
1214   ret = key_from_sexp (&s, sig->sexp, "sig-val", "s");
1215   if (0 != ret)
1216     ret = key_from_sexp (&s, sig->sexp, "rsa", "s");
1217   if (0 != ret)
1218   {
1219     gcry_mpi_release (n);
1220     GNUNET_break_op (0);
1221     return NULL;
1222   }
1223
1224   bkey = rsa_blinding_key_derive (pkey, bks);
1225   if (NULL == bkey)
1226   {
1227     /* RSA key is malicious since rsa_gcd_validate failed here.
1228      * It should have failed during GNUNET_CRYPTO_rsa_blind too though,
1229      * so the exchange is being malicious in an unfamilair way, maybe
1230      * just trying to crash us.  */
1231     GNUNET_break_op (0);
1232     gcry_mpi_release (n);
1233     gcry_mpi_release (s);
1234     return NULL;
1235   }
1236
1237   r_inv = gcry_mpi_new (0);
1238   if (1 !=
1239       gcry_mpi_invm (r_inv,
1240                      bkey->r,
1241                      n))
1242   {
1243     /* We cannot find r mod n, so gcd(r,n) != 1, which should get *
1244     * caught above, but we handle it the same here.              */
1245     GNUNET_break_op (0);
1246     gcry_mpi_release (r_inv);
1247     rsa_blinding_key_free (bkey);
1248     gcry_mpi_release (n);
1249     gcry_mpi_release (s);
1250     return NULL;
1251   }
1252
1253   ubsig = gcry_mpi_new (0);
1254   gcry_mpi_mulm (ubsig, s, r_inv, n);
1255   gcry_mpi_release (n);
1256   gcry_mpi_release (r_inv);
1257   gcry_mpi_release (s);
1258   rsa_blinding_key_free (bkey);
1259
1260   sret = GNUNET_new (struct GNUNET_CRYPTO_RsaSignature);
1261   GNUNET_assert (0 ==
1262                  gcry_sexp_build (&sret->sexp,
1263                                   NULL,
1264                                   "(sig-val (rsa (s %M)))",
1265                                   ubsig));
1266   gcry_mpi_release (ubsig);
1267   BENCHMARK_END (rsa_unblind);
1268   return sret;
1269 }
1270
1271
1272 /**
1273  * Verify whether the given hash corresponds to the given signature and
1274  * the signature is valid with respect to the given public key.
1275  *
1276  * @param hash hash of the message to verify to match the @a sig
1277  * @param sig signature that is being validated
1278  * @param pkey public key of the signer
1279  * @returns #GNUNET_YES if ok, #GNUNET_NO if RSA key is malicious, #GNUNET_SYSERR if signature is invalid
1280  */
1281 int
1282 GNUNET_CRYPTO_rsa_verify (const struct GNUNET_HashCode *hash,
1283                           const struct GNUNET_CRYPTO_RsaSignature *sig,
1284                           const struct GNUNET_CRYPTO_RsaPublicKey *pkey)
1285 {
1286   gcry_sexp_t data;
1287   gcry_mpi_t r;
1288   int rc;
1289
1290   BENCHMARK_START (rsa_verify);
1291
1292   r = rsa_full_domain_hash (pkey, hash);
1293   if (NULL == r)
1294   {
1295     GNUNET_break_op (0);
1296     /* RSA key is malicious since rsa_gcd_validate failed here.
1297      * It should have failed during GNUNET_CRYPTO_rsa_blind too though,
1298      * so the exchange is being malicious in an unfamilair way, maybe
1299      * just trying to crash us.  Arguably, we've only an internal error
1300      * though because we should've detected this in our previous call
1301      * to GNUNET_CRYPTO_rsa_unblind. */return GNUNET_NO;
1302   }
1303
1304   data = mpi_to_sexp (r);
1305   gcry_mpi_release (r);
1306
1307   rc = gcry_pk_verify (sig->sexp,
1308                        data,
1309                        pkey->sexp);
1310   gcry_sexp_release (data);
1311   if (0 != rc)
1312   {
1313     LOG (GNUNET_ERROR_TYPE_WARNING,
1314          _ ("RSA signature verification failed at %s:%d: %s\n"),
1315          __FILE__,
1316          __LINE__,
1317          gcry_strerror (rc));
1318     return GNUNET_SYSERR;
1319     BENCHMARK_END (rsa_verify);
1320   }
1321   BENCHMARK_END (rsa_verify);
1322   return GNUNET_OK;
1323 }
1324
1325
1326 /**
1327  * Duplicate the given private key
1328  *
1329  * @param key the private key to duplicate
1330  * @return the duplicate key; NULL upon error
1331  */
1332 struct GNUNET_CRYPTO_RsaPrivateKey *
1333 GNUNET_CRYPTO_rsa_private_key_dup (const struct
1334                                    GNUNET_CRYPTO_RsaPrivateKey *key)
1335 {
1336   struct GNUNET_CRYPTO_RsaPrivateKey *dup;
1337   gcry_sexp_t dup_sexp;
1338   size_t erroff;
1339
1340   /* check if we really are exporting a private key */
1341   dup_sexp = gcry_sexp_find_token (key->sexp, "private-key", 0);
1342   GNUNET_assert (NULL != dup_sexp);
1343   gcry_sexp_release (dup_sexp);
1344   /* copy the sexp */
1345   GNUNET_assert (0 == gcry_sexp_build (&dup_sexp, &erroff, "%S", key->sexp));
1346   dup = GNUNET_new (struct GNUNET_CRYPTO_RsaPrivateKey);
1347   dup->sexp = dup_sexp;
1348   return dup;
1349 }
1350
1351
1352 /**
1353  * Duplicate the given private key
1354  *
1355  * @param key the private key to duplicate
1356  * @return the duplicate key; NULL upon error
1357  */
1358 struct GNUNET_CRYPTO_RsaSignature *
1359 GNUNET_CRYPTO_rsa_signature_dup (const struct GNUNET_CRYPTO_RsaSignature *sig)
1360 {
1361   struct GNUNET_CRYPTO_RsaSignature *dup;
1362   gcry_sexp_t dup_sexp;
1363   size_t erroff;
1364   gcry_mpi_t s;
1365   int ret;
1366
1367   /* verify that this is an RSA signature */
1368   ret = key_from_sexp (&s, sig->sexp, "sig-val", "s");
1369   if (0 != ret)
1370     ret = key_from_sexp (&s, sig->sexp, "rsa", "s");
1371   GNUNET_assert (0 == ret);
1372   gcry_mpi_release (s);
1373   /* copy the sexp */
1374   GNUNET_assert (0 == gcry_sexp_build (&dup_sexp, &erroff, "%S", sig->sexp));
1375   dup = GNUNET_new (struct GNUNET_CRYPTO_RsaSignature);
1376   dup->sexp = dup_sexp;
1377   return dup;
1378 }
1379
1380
1381 /* end of util/rsa.c */