aboutsummaryrefslogtreecommitdiff
path: root/doc/paper/blinding_prng.txt
blob: 39ec038f4c70594daffdf58c3a4ce85bdb6509b5 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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.