Quote from: Peter R on December 23, 2014, 11:29:24 PM

Quote from: sickpig on December 23, 2014, 10:27:00 PM

Quote from: cypherdoc on December 23, 2014, 06:24:34 PM

what is "constant time"?

Improved signing security

For 0.10 the security of signing against unusual attacks has been improved by making the signatures constant time and deterministic.

This change is a result of switching signing to use libsecp256k1 instead of OpenSSL. Libsecp256k1 is a cryptographic library optimized for the curve Bitcoin uses which was created by Bitcoin Core developer Pieter Wuille.

There exist attacks[1] against most ECC implementations where an attacker on shared virtual machine hardware could extract a private key if they could cause a target to sign using the same key hundreds of times. While using shared hosts and reusing keys are inadvisable for other reasons, it's a better practice to avoid the exposure.

OpenSSL has code in their source repository for derandomization and reduction in timing leaks, and we've eagerly wanted to use it for a long time but this functionality has still not made its way into a released version of OpenSSL. Libsecp256k1 achieves significantly stronger protection: As far as we're aware this is the only deployed implementation of constant time signing for the curve Bitcoin uses and we have reason to believe that libsecp256k1 is better tested and more thoroughly reviewed than the implementation in OpenSSL.

[1] https://eprint.iacr.org/2014/161.pdf

A countermeasure against

http://en.m.wikipedia.org/wiki/Timing_attack

?

Although I can't think of a practical scenario where a typical user would ever be exposed to this, yes, the concern is side-channel attacks (e.g., a timing attack):

Quote from: N Benger et al

ABSTRACT. We apply the Flush+Reload side-channel attack based on cache hits/misses to extract a small amount of data from OpenSSL ECDSA signature requests. We then apply a standard lattice technique to extract the private key, but unlike previous attacks we are able to make use of the side-channel information from almost all of the observed executions. This means we obtain private key recovery by observing a relatively small number of executions, and by expending a relatively small amount of post-processing via lattice reduction. We demonstrate our analysis via experiments using the curve secp256k1 used in the Bitcoin protocol. In particular we show that with as little as 200 signatures we are able to achieve a reasonable level of success in recovering the secret key for a 256-bit curve. This is significantly better than prior methods of applying lattice reduction techniques to similar side channel information.

From: N. Benger, J van de Pol, N.P. Smart, Y. Yar, Ooh Aah... Just a Little Bit: A small amount of side channel can go a long way, from International Association for Cryptologic Research, 2014.

Basically, there's a bunch of number crunching done by your CPU each time your wallet signs a bitcoin transaction. If a "constant time" algorithm is used, it takes the same amount of time to produce an ECDSA signature regardless of the message being signed (or the k value or private key used). If the signing time is always the same, then an attacker cannot learn anything about your private keys by inspecting the timing variations (since there are none) when you sign various messages.

Where does "timing variation" come from? As one example, your wallet needs to perform the following elliptic curve point multiplication as part of the ECDSA signing process:

(x₁, y₁) = k x G

There's several different algorithms that can be used to carry out this multiplication. The simplest is probably the "double and add" method. However, the amount of time it takes this algorithm to execute depends on the specific value of k (G is always constant for bitcoin). On the other hand, the "Montgomery Ladder" approach computes the point multiplication in a fixed amount of time (regardless of the specific value of k). So a wallet would use a constant-time approach like the Montgomery Ladder technique rather than the double-and-add method as part of ensuring "constant time" ECDSA signatures.

Why does "constant time" matter? In most cases I don't think it really does. But let's imagine a contrived scenario where an attacker can get my wallet to produce several bitcoin-signed message with one of its funded private keys. The attacker can pass it any piece of text, and my wallet will sign that text and relay the signature back to the attacker. Normally this shouldn't be a problem because bitcoin-signed messages are safe. But if the attacker can somehow accurately time how long my CPU takes to produce each signature, and then fiddle with the messages that it's requesting my wallet to sign, perhaps it can leach out enough information to determine my private key

I think deterministic signatures are much more important than constant-time signatures (there's been a non-trivial amount of funds lost due to the repeat k-value problem but I doubt a single satoshi has ever been lost due to a genuine side-channel attack). Someone like gmaxwell could comment better on the practical risks here

I take it the time to do the multiplication varies directly with the size of the number k? Would it be linearly related?

And this applies whether or not we use deterministic signatures?