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