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