|
Title: Successful timing attack on ECDSA - maybe it's already time to switch algorithms Post by: Mononofu on May 23, 2011, 01:14:45 PM 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? Title: Re: Successful timing attack on ECDSA - maybe it's already time to switch algorithms Post by: Mike Hearn on May 23, 2011, 01:20:02 PM 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. Title: Re: Successful timing attack on ECDSA - maybe it's already time to switch algorithms Post by: m0Ray on May 23, 2011, 01:22:51 PM multiplication depends on the size of the operands. TL;DRWhat is multiplication time range? Title: Re: Successful timing attack on ECDSA - maybe it's already time to switch algorithms Post by: Gavin Andresen on May 23, 2011, 02:29:28 PM 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. Title: Re: Successful timing attack on ECDSA - maybe it's already time to switch algorithms Post by: Mononofu on May 23, 2011, 03:58:02 PM 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. Title: Re: Successful timing attack on ECDSA - maybe it's already time to switch algorithms Post by: Mike Hearn on May 23, 2011, 06:25:21 PM 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. Title: Re: Successful timing attack on ECDSA - maybe it's already time to switch algorithms Post by: twobitcoins on May 23, 2011, 06:59:18 PM 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. Title: Re: Successful timing attack on ECDSA - maybe it's already time to switch algorithms Post by: ByteCoin on May 23, 2011, 07:45:49 PM 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 Title: Re: Successful timing attack on ECDSA - maybe it's already time to switch algorithms Post by: vuce on May 31, 2011, 11:00:37 AM another attack on ecdsa (http://www.cacr.math.uwaterloo.ca/~ajmeneze/anotherlook/definitions.pdf). (don't think it's a threat to bitcoin though)
|