Successful timing attack on ECDSA - maybe it's already time to switch algorithms

[Mononofu]

I just stumbled on this very interesting paper: http://eprint.iacr.org/2011/232.pdf

Basically, it's possible to calculate the private key from the timing of the responses, since multiplication depends on the size of the operands.

I don't think this attack is going to be used just now, but it is definitely a possibility. What do you think?

[1714047288]

1714047288

[1714047288]

1714047288

[Mike Hearn]

I think it would be a concern if you could make a node sign transactions over and over again, in response to a request from yourself. It isn't possible today. If such a feature were to be added in future timing attacks would become a concern.

BitCoin uses OpenSSL so it will benefit from the researchers implemented countermeasures.

[m0Ray]

multiplication depends on the size of the operands.

TL;DR
What is multiplication time range?

[Gavin Andresen]

If I understood the paper correctly (I skimmed it very quickly), this is a timing attack that requires the attacker send a bunch of things to be signed with the same ECDSA private key.

The good news is it they also give a patch to OpenSSL to fix it.  The other good news is bitcoin only signs things with private keys when you send coins, and if you have the ability to ask bitcoin to send coins then we don't really care if you can get the private key.

We do have a patch in the "pull queue" that adds a RPC command to let bitcoin sign stuff ( https://github.com/bitcoin/bitcoin/pull/183 ), but, again assuming I read the paper correctly, even that doesn't worry me, since if you have the ability to run that RPC command you could either go through all the trouble of the timing attack to figure out the private key... or you could just issue a "send" command to steal all the bitcoins out of the wallet.

[Mononofu]

You're right, the only way I see for this to work is if you are on the same physical network - either an old hub which broadcasts all packets or a WiFi network. (note that encryption doesn't always help - using WPA2-PSK it's trivial to decrypt transmission of other users)

However, WiFi alone might introduce enough randomness to foil this attack.

[Mike Hearn]

Timing attacks aren't usually foiled by randomness, at least in theory, you just need more samples.

SSL is susceptible to this type of attack even over long distances because most servers won't limit the number of times you can try to set up a connection. You can just keep trying over and over until you have a huge number of samples, which average out to the right answer.

[twobitcoins]

You could get Bitcoin to sign something with a private key that you don't control by requesting a withdrawal from an online wallet service or other site that holds bitcoins for users.

With repeated deposits and withdrawals, it is at least plausible that such a site could be vulnerable.

[ByteCoin]

You could also launch a differential power analysis attack on the site by sending a carefully crafted flood of transactions and correlating it with the fluctuations in the share price of the local electricity company.

Because of the lack of reuse of keys, the number of signatures that are likely to be generated with a particular private key is small. This would make any remote timing attacks hard even when all other conditions are ideal.

The key point is that cryptographers must be aware of possible side-channel attacks on a particular implementation and appropriate steps must be taken to thwart them.

ByteCoin

[vuce]

another attack on ecdsa. (don't think it's a threat to bitcoin though)