3 files changed, 119 insertions, 0 deletions

diff --git a/src/util/Makefile.am b/src/util/Makefile.am
index 22471ffda..fe8ab01ea 100644
--- a/src/util/Makefile.am
+++ b/src/util/Makefile.am
@@ -283,6 +283,7 @@ check_PROGRAMS = \
  test_crypto_hash \
  test_crypto_hash_context \
  test_crypto_hkdf \
+ test_crypto_kdf \
  test_crypto_paillier \
  test_crypto_random \
  test_crypto_rsa \
@@ -468,6 +469,11 @@ test_crypto_hkdf_SOURCES = \
 test_crypto_hkdf_LDADD = \
  libgnunetutil.la
 
+test_crypto_kdf_SOURCES = \
+ test_crypto_kdf.c
+test_crypto_kdf_LDADD = \
+ libgnunetutil.la -lgcrypt
+
 test_crypto_paillier_SOURCES = \
  test_crypto_paillier.c
 test_crypto_paillier_LDADD = \
diff --git a/src/util/crypto_rsa.c b/src/util/crypto_rsa.c
index 4415f20f6..ae96a99ad 100644
--- a/src/util/crypto_rsa.c
+++ b/src/util/crypto_rsa.c
@@ -422,6 +422,49 @@ rsa_blinding_key_derive (const struct GNUNET_CRYPTO_RsaPublicKey *pkey,
 }
 
 
+/* 
+We originally added GNUNET_CRYPTO_kdf_mod_mpi for the benifit of the
+previous routine.
+
+There was previously a call to GNUNET_CRYPTO_kdf in 
+  bkey = rsa_blinding_key_derive (len, bks);
+that gives exactly len bits where 
+  len = GNUNET_CRYPTO_rsa_public_key_len (pkey);
+
+Now r = 2^(len-1)/pkey.n is the probability that a set high bit being
+okay, meaning bkey < pkey.n.  It follows that (1-r)/2 of the time bkey >
+pkey.n making the effective bkey be 
+  bkey mod pkey.n = bkey - pkey.n
+so the effective bkey has its high bit set with probability r/2.
+
+We expect r to be close to 1/2 if the exchange is honest, but the
+exchange can choose r otherwise.
+
+In blind signing, the exchange sees  
+  B = bkey * S mod pkey.n
+On deposit, the exchange sees S so they can compute bkey' = B/S mod
+pkey.n for all B they recorded to see if bkey' has it's high bit set.
+Also, note the exchange can compute 1/S efficiently since they know the
+factors of pkey.n.
+
+I suppose that happens with probability r/(1+r) if its the wrong B, not
+completely sure.  If otoh we've the right B, then we've the probability
+r/2 of a set high bit in the effective bkey.
+
+Interestingly, r^2-r has a maximum at the default r=1/2 anyways, giving
+the wrong and right probabilities 1/3 and 1/4, respectively.
+
+I feared this gives the exchange a meaningful fraction of a bit of
+information per coin involved in the transaction.  It sounds damaging if
+numerous coins were involved.  And it could run across transactions in
+some scenarios. 
+
+We fixed this by using a more uniform deterministic pseudo-random number
+generator for blinding factors.  I do not believe this to be a problem
+for the rsa_full_domain_hash routine, but better safe than sorry.
+*/
+
+
 /**
  * Compare the values of two signatures.
  *
diff --git a/src/util/test_crypto_kdf.c b/src/util/test_crypto_kdf.c
new file mode 100644
index 000000000..f75bafbb1
--- /dev/null
+++ b/src/util/test_crypto_kdf.c
@@ -0,0 +1,70 @@
+/*
+    Copyright (c) 2010 Jeffrey Burdges
+
+    Permission is hereby granted, free of charge, to any person obtaining a copy
+    of this software and associated documentation files (the "Software"), to deal
+    in the Software without restriction, including without limitation the rights
+    to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+    copies of the Software, and to permit persons to whom the Software is
+    furnished to do so, subject to the following conditions:
+
+    The above copyright notice and this permission notice shall be included in
+    all copies or substantial portions of the Software.
+
+    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+    IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+    FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+    AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+    LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+    OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+    THE SOFTWARE.
+*/
+
+/**
+ * @file src/util/test_crypt_kdf.c
+ * @brief Testcases for KDF mod n
+ * @author Jeffrey Burdges <burdges@gnunet.org>
+ */
+
+#include <gcrypt.h>
+
+#include "platform.h"
+#include "gnunet_crypto_lib.h"
+
+
+int
+main ()
+{
+#define RND_BLK_SIZE 4096
+  unsigned char rnd_blk[RND_BLK_SIZE];
+  int i;
+  gcry_mpi_t r,n;
+
+  GNUNET_log_setup ("test-crypto-kdf", "WARNING", NULL);
+
+  GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_WEAK,
+                              rnd_blk,
+                              RND_BLK_SIZE);
+
+  /* test full domain hash size */
+  for (i=0; i<100; i++) {
+    gcry_mpi_scan (&n,
+                   GCRYMPI_FMT_USG,
+                   rnd_blk, RND_BLK_SIZE,
+                   NULL);
+    GNUNET_CRYPTO_kdf_mod_mpi (&r, n,
+                               "", 0,
+                               "", 0,
+                               "");
+    GNUNET_assert( 0 > gcry_mpi_cmp(r,n) );
+
+    /* Is it worth checking that it's not too small? */
+    /* GNUNET_assert (gcry_mpi_get_nbits(r) > 3*RND_BLK_SIZE/4); */
+    /* This test necessarily randomly fails with probability 2^(3 - RND_BLK_SIZE/4) */
+
+    gcry_mpi_release(n);
+    gcry_mpi_release(r);
+  }
+
+  return 0;
+}