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                                       void **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 buf_size the size 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 void *buf,
 231                                       size_t buf_size)
 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                      buf_size,
 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 (
 347   const struct GNUNET_CRYPTO_RsaPublicKey *key,
 348   void **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   void *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   void *b1;
 627   void *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   void *b1;
 660   void *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   void *b1;
 693   void *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   void *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                          void **buf,
 845                          size_t *buf_size)
 846 {
 847   struct RsaBlindingKey *bkey;
 848   gcry_mpi_t data;
 849   gcry_mpi_t ne[2];
 850   gcry_mpi_t r_e;
 851   gcry_mpi_t data_r_e;
 852   int ret;
 853
 854   BENCHMARK_START (rsa_blind);
 855
 856   GNUNET_assert (buf != NULL);
 857   GNUNET_assert (buf_size != NULL);
 858   ret = key_from_sexp (ne, pkey->sexp, "public-key", "ne");
 859   if (0 != ret)
 860     ret = key_from_sexp (ne, pkey->sexp, "rsa", "ne");
 861   if (0 != ret)
 862   {
 863     GNUNET_break (0);
 864     *buf = NULL;
 865     *buf_size = 0;
 866     return 0;
 867   }
 868
 869   data = rsa_full_domain_hash (pkey, hash);
 870   if (NULL == data)
 871     goto rsa_gcd_validate_failure;
 872
 873   bkey = rsa_blinding_key_derive (pkey, bks);
 874   if (NULL == bkey)
 875   {
 876     gcry_mpi_release (data);
 877     goto rsa_gcd_validate_failure;
 878   }
 879
 880   r_e = gcry_mpi_new (0);
 881   gcry_mpi_powm (r_e,
 882                  bkey->r,
 883                  ne[1],
 884                  ne[0]);
 885   data_r_e = gcry_mpi_new (0);
 886   gcry_mpi_mulm (data_r_e,
 887                  data,
 888                  r_e,
 889                  ne[0]);
 890   gcry_mpi_release (data);
 891   gcry_mpi_release (ne[0]);
 892   gcry_mpi_release (ne[1]);
 893   gcry_mpi_release (r_e);
 894   rsa_blinding_key_free (bkey);
 895
 896   *buf_size = numeric_mpi_alloc_n_print (data_r_e,
 897                                          (char **) buf);
 898   gcry_mpi_release (data_r_e);
 899
 900   BENCHMARK_END (rsa_blind);
 901
 902   return GNUNET_YES;
 903
 904 rsa_gcd_validate_failure:
 905   /* We know the RSA key is malicious here, so warn the wallet. */
 906   /* GNUNET_break_op (0); */
 907   gcry_mpi_release (ne[0]);
 908   gcry_mpi_release (ne[1]);
 909   *buf = NULL;
 910   *buf_size = 0;
 911   return GNUNET_NO;
 912 }
 913
 914
 915 /**
 916  * Convert an MPI to an S-expression suitable for signature operations.
 917  *
 918  * @param value pointer to the data to convert
 919  * @return converted s-expression
 920  */
 921 static gcry_sexp_t
 922 mpi_to_sexp (gcry_mpi_t value)
 923 {
 924   gcry_sexp_t data = NULL;
 925
 926   GNUNET_assert (0 ==
 927                  gcry_sexp_build (&data,
 928                                   NULL,
 929                                   "(data (flags raw) (value %M))",
 930                                   value));
 931   return data;
 932 }
 933
 934
 935 /**
 936  * Sign the given MPI.
 937  *
 938  * @param key private key to use for the signing
 939  * @param value the MPI to sign
 940  * @return NULL on error, signature on success
 941  */
 942 static struct GNUNET_CRYPTO_RsaSignature *
 943 rsa_sign_mpi (const struct GNUNET_CRYPTO_RsaPrivateKey *key,
 944               gcry_mpi_t value)
 945 {
 946   struct GNUNET_CRYPTO_RsaSignature *sig;
 947   gcry_sexp_t data;
 948   gcry_sexp_t result;
 949   int rc;
 950
 951   data = mpi_to_sexp (value);
 952
 953   if (0 !=
 954       (rc = gcry_pk_sign (&result,
 955                           data,
 956                           key->sexp)))
 957   {
 958     LOG (GNUNET_ERROR_TYPE_WARNING,
 959          _ ("RSA signing failed at %s:%d: %s\n"),
 960          __FILE__,
 961          __LINE__,
 962          gcry_strerror (rc));
 963     GNUNET_break (0);
 964     return NULL;
 965   }
 966
 967   /* Lenstra protection was first added to libgcrypt 1.6.4
 968    * with commit c17f84bd02d7ee93845e92e20f6ddba814961588.
 969    */
 970 #if GCRYPT_VERSION_NUMBER < 0x010604
 971   /* verify signature (guards against Lenstra's attack with fault injection...) */
 972   struct GNUNET_CRYPTO_RsaPublicKey *public_key =
 973     GNUNET_CRYPTO_rsa_private_key_get_public (key);
 974   if (0 !=
 975       gcry_pk_verify (result,
 976                       data,
 977                       public_key->sexp))
 978   {
 979     GNUNET_break (0);
 980     GNUNET_CRYPTO_rsa_public_key_free (public_key);
 981     gcry_sexp_release (data);
 982     gcry_sexp_release (result);
 983     return NULL;
 984   }
 985   GNUNET_CRYPTO_rsa_public_key_free (public_key);
 986 #endif
 987
 988   /* return signature */
 989   gcry_sexp_release (data);
 990   sig = GNUNET_new (struct GNUNET_CRYPTO_RsaSignature);
 991   sig->sexp = result;
 992   return sig;
 993 }
 994
 995
 996 /**
 997  * Sign a blinded value, which must be a full domain hash of a message.
 998  *
 999  * @param key private key to use for the signing
1000  * @param msg the message to sign
1001  * @param msg_len number of bytes in @a msg to sign
1002  * @return NULL on error, signature on success
1003  */
1004 struct GNUNET_CRYPTO_RsaSignature *
1005 GNUNET_CRYPTO_rsa_sign_blinded (const struct GNUNET_CRYPTO_RsaPrivateKey *key,
1006                                 const void *msg,
1007                                 size_t msg_len)
1008 {
1009   gcry_mpi_t v = NULL;
1010   struct GNUNET_CRYPTO_RsaSignature *sig;
1011
1012   BENCHMARK_START (rsa_sign_blinded);
1013
1014   GNUNET_assert (0 ==
1015                  gcry_mpi_scan (&v,
1016                                 GCRYMPI_FMT_USG,
1017                                 msg,
1018                                 msg_len,
1019                                 NULL));
1020
1021   sig = rsa_sign_mpi (key, v);
1022   gcry_mpi_release (v);
1023   BENCHMARK_END (rsa_sign_blinded);
1024   return sig;
1025 }
1026
1027
1028 /**
1029  * Create and sign a full domain hash of a message.
1030  *
1031  * @param key private key to use for the signing
1032  * @param hash the hash of the message to sign
1033  * @return NULL on error, including a malicious RSA key, signature on success
1034  */
1035 struct GNUNET_CRYPTO_RsaSignature *
1036 GNUNET_CRYPTO_rsa_sign_fdh (const struct GNUNET_CRYPTO_RsaPrivateKey *key,
1037                             const struct GNUNET_HashCode *hash)
1038 {
1039   struct GNUNET_CRYPTO_RsaPublicKey *pkey;
1040   gcry_mpi_t v = NULL;
1041   struct GNUNET_CRYPTO_RsaSignature *sig;
1042
1043   pkey = GNUNET_CRYPTO_rsa_private_key_get_public (key);
1044   v = rsa_full_domain_hash (pkey, hash);
1045   GNUNET_CRYPTO_rsa_public_key_free (pkey);
1046   if (NULL == v)   /* rsa_gcd_validate failed meaning */
1047     return NULL;   /* our *own* RSA key is malicious. */
1048
1049   sig = rsa_sign_mpi (key, v);
1050   gcry_mpi_release (v);
1051   return sig;
1052 }
1053
1054
1055 /**
1056  * Free memory occupied by signature.
1057  *
1058  * @param sig memory to freee
1059  */
1060 void
1061 GNUNET_CRYPTO_rsa_signature_free (struct GNUNET_CRYPTO_RsaSignature *sig)
1062 {
1063   gcry_sexp_release (sig->sexp);
1064   GNUNET_free (sig);
1065 }
1066
1067
1068 /**
1069  * Encode the given signature in a format suitable for storing it into a file.
1070  *
1071  * @param sig the signature
1072  * @param[out] buffer set to a buffer with the encoded key
1073  * @return size of memory allocated in @a buffer
1074  */
1075 size_t
1076 GNUNET_CRYPTO_rsa_signature_encode (
1077   const struct GNUNET_CRYPTO_RsaSignature *sig,
1078   void **buffer)
1079 {
1080   gcry_mpi_t s;
1081   size_t buf_size;
1082   size_t rsize;
1083   unsigned char *buf;
1084   int ret;
1085
1086   ret = key_from_sexp (&s,
1087                        sig->sexp,
1088                        "sig-val",
1089                        "s");
1090   if (0 != ret)
1091     ret = key_from_sexp (&s,
1092                          sig->sexp,
1093                          "rsa",
1094                          "s");
1095   GNUNET_assert (0 == ret);
1096   gcry_mpi_print (GCRYMPI_FMT_USG,
1097                   NULL,
1098                   0,
1099                   &buf_size,
1100                   s);
1101   buf = GNUNET_malloc (buf_size);
1102   GNUNET_assert (0 ==
1103                  gcry_mpi_print (GCRYMPI_FMT_USG,
1104                                  buf,
1105                                  buf_size,
1106                                  &rsize,
1107                                  s));
1108   GNUNET_assert (rsize == buf_size);
1109   *buffer = (void *) buf;
1110   gcry_mpi_release (s);
1111   return buf_size;
1112 }
1113
1114
1115 /**
1116  * Decode the signature from the data-format back to the "normal", internal
1117  * format.
1118  *
1119  * @param buf the buffer where the public key data is stored
1120  * @param buf_size the size of the data in @a buf
1121  * @return NULL on error
1122  */
1123 struct GNUNET_CRYPTO_RsaSignature *
1124 GNUNET_CRYPTO_rsa_signature_decode (const void *buf,
1125                                     size_t buf_size)
1126 {
1127   struct GNUNET_CRYPTO_RsaSignature *sig;
1128   gcry_mpi_t s;
1129   gcry_sexp_t data;
1130
1131   if (0 !=
1132       gcry_mpi_scan (&s,
1133                      GCRYMPI_FMT_USG,
1134                      buf,
1135                      buf_size,
1136                      NULL))
1137   {
1138     GNUNET_break_op (0);
1139     return NULL;
1140   }
1141
1142   if (0 !=
1143       gcry_sexp_build (&data,
1144                        NULL,
1145                        "(sig-val(rsa(s %M)))",
1146                        s))
1147   {
1148     GNUNET_break (0);
1149     gcry_mpi_release (s);
1150     return NULL;
1151   }
1152   gcry_mpi_release (s);
1153   sig = GNUNET_new (struct GNUNET_CRYPTO_RsaSignature);
1154   sig->sexp = data;
1155   return sig;
1156 }
1157
1158
1159 /**
1160  * Duplicate the given public key
1161  *
1162  * @param key the public key to duplicate
1163  * @return the duplicate key; NULL upon error
1164  */
1165 struct GNUNET_CRYPTO_RsaPublicKey *
1166 GNUNET_CRYPTO_rsa_public_key_dup (const struct GNUNET_CRYPTO_RsaPublicKey *key)
1167 {
1168   struct GNUNET_CRYPTO_RsaPublicKey *dup;
1169   gcry_sexp_t dup_sexp;
1170   size_t erroff;
1171
1172   /* check if we really are exporting a public key */
1173   dup_sexp = gcry_sexp_find_token (key->sexp, "public-key", 0);
1174   GNUNET_assert (NULL != dup_sexp);
1175   gcry_sexp_release (dup_sexp);
1176   /* copy the sexp */
1177   GNUNET_assert (0 == gcry_sexp_build (&dup_sexp, &erroff, "%S", key->sexp));
1178   dup = GNUNET_new (struct GNUNET_CRYPTO_RsaPublicKey);
1179   dup->sexp = dup_sexp;
1180   return dup;
1181 }
1182
1183
1184 /**
1185  * Unblind a blind-signed signature.  The signature should have been generated
1186  * with #GNUNET_CRYPTO_rsa_sign() using a hash that was blinded with
1187  * #GNUNET_CRYPTO_rsa_blind().
1188  *
1189  * @param sig the signature made on the blinded signature purpose
1190  * @param bks the blinding key secret used to blind the signature purpose
1191  * @param pkey the public key of the signer
1192  * @return unblinded signature on success, NULL if RSA key is bad or malicious.
1193  */
1194 struct GNUNET_CRYPTO_RsaSignature *
1195 GNUNET_CRYPTO_rsa_unblind (const struct GNUNET_CRYPTO_RsaSignature *sig,
1196                            const struct GNUNET_CRYPTO_RsaBlindingKeySecret *bks,
1197                            struct GNUNET_CRYPTO_RsaPublicKey *pkey)
1198 {
1199   struct RsaBlindingKey *bkey;
1200   gcry_mpi_t n;
1201   gcry_mpi_t s;
1202   gcry_mpi_t r_inv;
1203   gcry_mpi_t ubsig;
1204   int ret;
1205   struct GNUNET_CRYPTO_RsaSignature *sret;
1206
1207   BENCHMARK_START (rsa_unblind);
1208
1209   ret = key_from_sexp (&n, pkey->sexp, "public-key", "n");
1210   if (0 != ret)
1211     ret = key_from_sexp (&n, pkey->sexp, "rsa", "n");
1212   if (0 != ret)
1213   {
1214     GNUNET_break_op (0);
1215     return NULL;
1216   }
1217   ret = key_from_sexp (&s, sig->sexp, "sig-val", "s");
1218   if (0 != ret)
1219     ret = key_from_sexp (&s, sig->sexp, "rsa", "s");
1220   if (0 != ret)
1221   {
1222     gcry_mpi_release (n);
1223     GNUNET_break_op (0);
1224     return NULL;
1225   }
1226
1227   bkey = rsa_blinding_key_derive (pkey, bks);
1228   if (NULL == bkey)
1229   {
1230     /* RSA key is malicious since rsa_gcd_validate failed here.
1231      * It should have failed during GNUNET_CRYPTO_rsa_blind too though,
1232      * so the exchange is being malicious in an unfamilair way, maybe
1233      * just trying to crash us.  */
1234     GNUNET_break_op (0);
1235     gcry_mpi_release (n);
1236     gcry_mpi_release (s);
1237     return NULL;
1238   }
1239
1240   r_inv = gcry_mpi_new (0);
1241   if (1 !=
1242       gcry_mpi_invm (r_inv,
1243                      bkey->r,
1244                      n))
1245   {
1246     /* We cannot find r mod n, so gcd(r,n) != 1, which should get *
1247     * caught above, but we handle it the same here.              */
1248     GNUNET_break_op (0);
1249     gcry_mpi_release (r_inv);
1250     rsa_blinding_key_free (bkey);
1251     gcry_mpi_release (n);
1252     gcry_mpi_release (s);
1253     return NULL;
1254   }
1255
1256   ubsig = gcry_mpi_new (0);
1257   gcry_mpi_mulm (ubsig, s, r_inv, n);
1258   gcry_mpi_release (n);
1259   gcry_mpi_release (r_inv);
1260   gcry_mpi_release (s);
1261   rsa_blinding_key_free (bkey);
1262
1263   sret = GNUNET_new (struct GNUNET_CRYPTO_RsaSignature);
1264   GNUNET_assert (0 ==
1265                  gcry_sexp_build (&sret->sexp,
1266                                   NULL,
1267                                   "(sig-val (rsa (s %M)))",
1268                                   ubsig));
1269   gcry_mpi_release (ubsig);
1270   BENCHMARK_END (rsa_unblind);
1271   return sret;
1272 }
1273
1274
1275 /**
1276  * Verify whether the given hash corresponds to the given signature and
1277  * the signature is valid with respect to the given public key.
1278  *
1279  * @param hash hash of the message to verify to match the @a sig
1280  * @param sig signature that is being validated
1281  * @param pkey public key of the signer
1282  * @returns #GNUNET_YES if ok, #GNUNET_NO if RSA key is malicious, #GNUNET_SYSERR if signature is invalid
1283  */
1284 int
1285 GNUNET_CRYPTO_rsa_verify (const struct GNUNET_HashCode *hash,
1286                           const struct GNUNET_CRYPTO_RsaSignature *sig,
1287                           const struct GNUNET_CRYPTO_RsaPublicKey *pkey)
1288 {
1289   gcry_sexp_t data;
1290   gcry_mpi_t r;
1291   int rc;
1292
1293   BENCHMARK_START (rsa_verify);
1294
1295   r = rsa_full_domain_hash (pkey, hash);
1296   if (NULL == r)
1297   {
1298     GNUNET_break_op (0);
1299     /* RSA key is malicious since rsa_gcd_validate failed here.
1300      * It should have failed during GNUNET_CRYPTO_rsa_blind too though,
1301      * so the exchange is being malicious in an unfamilair way, maybe
1302      * just trying to crash us.  Arguably, we've only an internal error
1303      * though because we should've detected this in our previous call
1304      * to GNUNET_CRYPTO_rsa_unblind. */return GNUNET_NO;
1305   }
1306
1307   data = mpi_to_sexp (r);
1308   gcry_mpi_release (r);
1309
1310   rc = gcry_pk_verify (sig->sexp,
1311                        data,
1312                        pkey->sexp);
1313   gcry_sexp_release (data);
1314   if (0 != rc)
1315   {
1316     LOG (GNUNET_ERROR_TYPE_WARNING,
1317          _ ("RSA signature verification failed at %s:%d: %s\n"),
1318          __FILE__,
1319          __LINE__,
1320          gcry_strerror (rc));
1321     return GNUNET_SYSERR;
1322     BENCHMARK_END (rsa_verify);
1323   }
1324   BENCHMARK_END (rsa_verify);
1325   return GNUNET_OK;
1326 }
1327
1328
1329 /**
1330  * Duplicate the given private key
1331  *
1332  * @param key the private key to duplicate
1333  * @return the duplicate key; NULL upon error
1334  */
1335 struct GNUNET_CRYPTO_RsaPrivateKey *
1336 GNUNET_CRYPTO_rsa_private_key_dup (const struct
1337                                    GNUNET_CRYPTO_RsaPrivateKey *key)
1338 {
1339   struct GNUNET_CRYPTO_RsaPrivateKey *dup;
1340   gcry_sexp_t dup_sexp;
1341   size_t erroff;
1342
1343   /* check if we really are exporting a private key */
1344   dup_sexp = gcry_sexp_find_token (key->sexp, "private-key", 0);
1345   GNUNET_assert (NULL != dup_sexp);
1346   gcry_sexp_release (dup_sexp);
1347   /* copy the sexp */
1348   GNUNET_assert (0 == gcry_sexp_build (&dup_sexp, &erroff, "%S", key->sexp));
1349   dup = GNUNET_new (struct GNUNET_CRYPTO_RsaPrivateKey);
1350   dup->sexp = dup_sexp;
1351   return dup;
1352 }
1353
1354
1355 /**
1356  * Duplicate the given private key
1357  *
1358  * @param key the private key to duplicate
1359  * @return the duplicate key; NULL upon error
1360  */
1361 struct GNUNET_CRYPTO_RsaSignature *
1362 GNUNET_CRYPTO_rsa_signature_dup (const struct GNUNET_CRYPTO_RsaSignature *sig)
1363 {
1364   struct GNUNET_CRYPTO_RsaSignature *dup;
1365   gcry_sexp_t dup_sexp;
1366   size_t erroff;
1367   gcry_mpi_t s;
1368   int ret;
1369
1370   /* verify that this is an RSA signature */
1371   ret = key_from_sexp (&s, sig->sexp, "sig-val", "s");
1372   if (0 != ret)
1373     ret = key_from_sexp (&s, sig->sexp, "rsa", "s");
1374   GNUNET_assert (0 == ret);
1375   gcry_mpi_release (s);
1376   /* copy the sexp */
1377   GNUNET_assert (0 == gcry_sexp_build (&dup_sexp, &erroff, "%S", sig->sexp));
1378   dup = GNUNET_new (struct GNUNET_CRYPTO_RsaSignature);
1379   dup->sexp = dup_sexp;
1380   return dup;
1381 }
1382
1383
1384 /* end of util/rsa.c */