From 8dc035b237ad3b6f97b1430c5803826ef72310f4 Mon Sep 17 00:00:00 2001 From: Jeff Burdges Date: Wed, 25 May 2016 00:27:11 +0200 Subject: Add my mail about the PRNG attack on blinding I imagine this will develop further shortly --- doc/paper/blinding_prng.txt | 53 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 53 insertions(+) create mode 100644 doc/paper/blinding_prng.txt (limited to 'doc') 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. + + -- cgit v1.2.3