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