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