| Commit message (Collapse) | Author | Age |
|---|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| |
|
|
| |
type/size/source for gnunet-logread
|
| | |
|
| | |
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Much thanks to CodesInChaos <codesinchaos@gmail.com> from the
cryptography@metzdowd.com list for observing this flaw!
On Tue, 2016-06-07 at 13:39 +0200, CodesInChaos wrote:
> How do you handle the case where GCD(m, n) != 1 where m is the message
> (i.e. the full domain hash) and n the modulus? Do you reject that
> message and generate a new one?
If I understand the attack you have in mind, it goes roughly :
First, an evil exchange creates a 2048 bit RSA key pq, but issues n = p
q r_1 r_2 ... r_k as say a 4096 bit RSA key where r_i is a smallish but
preferably not so obvious primes, like not 2, 3, or 5.
Next, our evil exchange detects and records when the various r_i appear
during blinding and spending. As m is 4096 bits, then some always do
since we took the r_i smallish.
Each appearing r_i factor leaks I think several bits about the
customer's identity. If enough coins are involved in a transaction,
especially say through repeated transactions, then the customer will
quickly be deanonymized.
I could've fixed this in crypto_kdf.c but I descided it was specific
to RSA, so I did it when calling the KDF. It should be abstracted
into a common routine probably.
Also fixes a pair of memory leaks.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
the blinding factor and the full domain hash.
This resolves an attack against the blinding factor in Taler:
There was 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.
I do not believe this caused a problem for the full domain hash, but
we can fix it easily enough anyways.
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| |
|
|
| |
whitespace remover
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| |
|
