blinding_prng.txt (1892B)
1 2 We should try to be rigorous about this, which seemingly shows an 3 issue. 4 5 6 There is a call to GNUNET_CRYPTO_kdf in 7 bkey = rsa_blinding_key_derive (len, bks); 8 that gives exactly len bits where 9 len = GNUNET_CRYPTO_rsa_public_key_len (pkey); 10 11 Now r = 2^(len-1)/pkey.n is the probability that a set high bit being 12 okay, meaning bkey < pkey.n. It follows that (1-r)/2 of the time bkey > 13 pkey.n making the effective bkey be 14 bkey mod pkey.n = bkey - pkey.n 15 so the effective bkey has its high bit set with probability r/2. 16 17 We expect r to be close to 1/2 if the exchange is honest, but the 18 exchange can choose r otherwise. 19 20 In blind signing, the exchange sees 21 B = bkey * S mod pkey.n 22 On deposit, the exchange sees S so they can compute bkey' = B/S mod 23 pkey.n for all B they recorded to see if bkey' has it's high bit set. 24 Also, note the exchange can compute 1/S efficiently since they know the 25 factors of pkey.n. 26 27 I suppose that happens with probability r/(1+r) if its the wrong B, not 28 completely sure. If otoh we've the right B, then we've the probability 29 r/2 of a set high bit in the effective bkey. 30 31 Interestingly, r^2-r has a maximum at the default r=1/2 anyways, giving 32 the wrong and right probabilities 1/3 and 1/4, respectively. 33 34 35 I fear this gives the exchange a meaningful fraction of a bit of 36 information per coin involved in the transaction. It sounds damaging if 37 numerous coins were involved. And it could run across transactions in 38 some scenarios. 39 40 41 I suspect we need a more uniform deterministic pseudo-random number 42 generator for blinding factors. Just fyi, our old call to 43 gcry_mpi_randomize had this same problem. 44 45 As I said before, I do not believe this to be a problem for the full 46 domain hash, but maybe my setting that second to high bit makes it worse 47 or something, not sure. 48 49 50 It's late, maybe I've worked out some probabilities wrong, but looks 51 right. 52 53