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