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