summaryrefslogtreecommitdiff
path: root/doc
diff options
context:
space:
mode:
authorJeff Burdges <burdges@gnunet.org>2016-05-25 00:27:11 +0200
committerJeff Burdges <burdges@gnunet.org>2016-05-25 00:27:11 +0200
commit8dc035b237ad3b6f97b1430c5803826ef72310f4 (patch)
treebbdf16d2cb0f17ae61d03fa784227b2c06e642c1 /doc
parent32bb3b14bf5cd623714985c8ca7fed0c5a923336 (diff)
downloadexchange-8dc035b237ad3b6f97b1430c5803826ef72310f4.tar.gz
exchange-8dc035b237ad3b6f97b1430c5803826ef72310f4.tar.bz2
exchange-8dc035b237ad3b6f97b1430c5803826ef72310f4.zip
Add my mail about the PRNG attack on blinding
I imagine this will develop further shortly
Diffstat (limited to 'doc')
-rw-r--r--doc/paper/blinding_prng.txt53
1 files changed, 53 insertions, 0 deletions
diff --git a/doc/paper/blinding_prng.txt b/doc/paper/blinding_prng.txt
new file mode 100644
index 000000000..39ec038f4
--- /dev/null
+++ b/doc/paper/blinding_prng.txt
@@ -0,0 +1,53 @@
+
+We should try to be rigorous about this, which seemingly shows an
+issue.
+
+
+There is 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 fear 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.
+
+
+I suspect we need a more uniform deterministic pseudo-random number
+generator for blinding factors. Just fyi, our old call to
+gcry_mpi_randomize had this same problem.
+
+As I said before, I do not believe this to be a problem for the full
+domain hash, but maybe my setting that second to high bit makes it worse
+or something, not sure.
+
+
+It's late, maybe I've worked out some probabilities wrong, but looks
+right.
+
+