It is based on the idea of branchless implementations of = the field and group operations.

Multiprecision = arithmetic can be implemented branch-free by assuming fixed sized limbs = and always performing dummy carry operations even when they aren't = needed.

The most critical field operation that = could potentially leak data is the modular inverse. Again, if we don't = mind a slow implementation, a simple constant-time implementation = involves exponentiation by the field modulus minus two - which is a = known constant.

As for group operations in = secp256k1, the main sources of leaks are the branchings that exist in = typical implementations as well as optimizations for special = inputs,

i.e. http://en.wikibooks.org/wiki/Cryptography/Prime_Curve/Jacobian_C= oordinates

To avoid leaking any information, we can use = the most general operation, Point Addition, in the following = way:

Always carry through the full point = addition algorithm even if we get POINT_AT_INFINITY. Also, always carry = through the POINT_DOUBLE operation even on unequal inputs. Store the = three possible results (POINT_ADDITION, POINT_AT_INFINITY, and = POINT_DOUBLE) and then do a branchless conditional swap with the output = location as a final step.

Branchless swaps can = be performed using bitwise operations such as the examples here: = https://github.com/CodeShark/cmp/blob/master/src/constant-time.h

--------------

In the case = of bitcoin, signature verification is where performance optimization is = really helpful - and here there are no risks of sidechannel leaks, so we = can go ahead and use the most optimal implementations. But for signing, = the amount of throughput required is generally not that large and = constant-time implementations will be more than adequate on typical = hardware.

-Eric = Lombrozo

On Mar 5, 2014, at 4:49 AM, = Mike Hearn <mike@plan99.net> = wrote:

A new practical technique has been = published that can recover secp256k1 private keys after observing = OpenSSL calculate as little as 200 signatures:

http://eprint.iacr.org/2014/1= 61.pdf

This attack is based on the FLUSH+RELOAD = technique published last year. It works by observing L3 CPU cache = timings and forcing cache line flushes using the clflush opcode. As a = result, it is applicable to any x86 environment where an attacker may be = able to run on the same hardware i.e. virtualised hosting environments = where keys are being reused.

I am not currently aware of any efforts to make = OpenSSL's secp256k1 implementation completely side channel free in all = aspects. Also, unfortunately many people have reimplemented ECDSA = themselves and even if OpenSSL gets fixed, the custom implementations = probably won't.

So, IMHO this is a sign for hot wallet users to = start walking (but not running) towards the exits of these shared cloud = services: it doesn't feel safe to sign transactions on these = platforms, so hot wallets should be managed by dedicated hardware. Of = course other parts of the service, like the website, are less sensitive = and can still run in the cloud. I doubt the researchers will release = their code to do the side channel attack and it's rather complex to = reimplement, so this gives some time for mitigation. Unfortunately the = huge sums being held in some "bitbank" style hot wallets mean that = attackers are well motivated to pull off even quite complex = attacks.

= --------------------------------------------------------------------------= ----
Subversion Kills Productivity. Get off Subversion & Make the = Move to Perforce.
With Perforce, you get hassle-free workflows. Merge = that actually works.
Faster operations. Version large binaries. = Built-in WAN optimization and the
freedom to use Git, Perforce = or both. Make the move to Perforce.
http://p= ubads.g.doubleclick.net/gampad/clk?id=3D122218951&iu=3D/4140/ostg.clkt= rk_______________________________________________
Bitcoin-developme= nt mailing = list
Bitcoin-development@lists.sourceforge.net
https://lists.sourcef= orge.net/lists/listinfo/bitcoin-development

= --Apple-Mail=_38FDF086-1B73-48BA-9A6B-458C4B89A9A1-- --Apple-Mail=_0153D336-805C-4DCA-ABCB-A2B314209E1C Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename=signature.asc Content-Type: application/pgp-signature; name=signature.asc Content-Description: Message signed with OpenPGP using GPGMail -----BEGIN PGP SIGNATURE----- iQIcBAEBAgAGBQJTF5eVAAoJEAA1EyJsW9n+XzcQAOj5Ew3iq4B/4r5qI+CK9WKt vaMoCarAYGfplXprrt/pWcNkT8VKZ78Cz3CbdE5nQMN5H6lVMpod0bmX3qo0bI9m flN25yCE9ZCNqAOJqW5Dyi71eAuTabiH2RFLrJtvKhjBLupTjNkaRJ9u3Lr8Qowb pVCp3g1YNEiq4IQPfw17dD+i+iaE/tt9TgkGaUhnV3NiOc2DuNmg0FFkgFtD6c8+ eoccNmacv9Uuz7dh7Y52AuKxpYdG0vtgttmrGrL2iK5PnYllC1anYQ0E93LD1p/T AaCQju7ODmTK9e9oH78TGNneoCV4/GZsEYB3tZJ0rih6AVc6c170H6JJJcpDB2WV /t7J1MzU93tuydDA417ZLH0DDQChMzrVhC2Q0eN8XXHxnCdMTl9VhBxlgYrHDDHv zksce6FOo0XlmOyDydPGfHhCKDkrLgBVl1oQIV0ze3x1GudiCS3SIbuj8b4rnXsQ o13N/hgaj/9fsAdywMFRZ00EA7dSP+4s3iw/97AnyFD748H2hqFod0UkMvtXRFy2 U69IBSAZ/27ZZwqskvHvOubMtOxiJu/r6o/ZDF2cp2mqh8aoX9iICbVfYRIN22IB wTQbiVjZwqfH40tCrCLHlcbspdpHAOa+hjdgGqhWRHhdyjyBAfcBw0pqPev2eve2 0uZ5ydm6ehlkzOuE8IQi =Ue6V -----END PGP SIGNATURE----- --Apple-Mail=_0153D336-805C-4DCA-ABCB-A2B314209E1C--