Hacker News Reader

Comment by tptacek | Hacker News Reader

Elliptic curves offer plenty of side channel opportunities; they aren't intrinsic to RSA.

ECC is good, better than RSA, but what this paper militates for is leak-resistant cryptography implementations, not ECC in particular.

View on HN

RSA is difficult to make constant time, but there are plenty of constant-time elliptic curve implementations out there. Curve25519/Ed25519 is one of them, and this paper suggests that they will be strongly resistant to these sort of attacks.

RSA is actually one of the easiest algorithm to protect from side-channel attacks (though nothing gives you 100% protection), thanks to the various kinds of blindings you can immediately apply.

Blinding techniques are not constant-time, but what you really want in the end is to reduce the Signal-to-Noise ratio on the radiated energy.

For ECC it is more difficult, and it becomes very hard for most symmetric ciphers.

Blinding ECC is as easy as RSA, if not easier. Coron's classic paper has 3 easy measures to blind a scalar multiplication, and more have appeared since then:

http://link.springer.com/chapter/10.1007%2F3-540-48059-5_25

The problem with GnuPG is not that it's using RSA/ElGamal instead of ECC; it's that it's using a general-purpose large integer arithmetic package, MPI, whose purpose is to optimize speed for a wide range of input arguments.

On the specific case of RSA (or rather, CRT-RSA), I've mostly studied fault-injection attacks, which can be considered a kind of side-channel attack. And I agree with you that it is possible to protect RSA (see my most recent paper [1] on that subject, which will be published at FDTC 2014, the day just before CHES 2014, where the paper being discussed in this HN thread will appear).

I also agree with you on the fact that ECC is not immune to side-channel attacks at all: for proof this cool paper [2] by Barthe, Dupressoir, Fouque, Grégoire, and Zapalowicz, which will appear at CCS 2014 which shows working fault-injection attacks on both RSA and ECDSA.

[1] http://pablo.rauzy.name/research.html#hofa

[2] http://eprint.iacr.org/2014/436

FDTC 2014: http://conferenze.dei.polimi.it/FDTC14/

CHES 2014: http://www.chesworkshop.org/ches2014/start.php

CCS 2014: http://www.sigsac.org/ccs/CCS2014/

Curve25519 was designed specifically to be leak-resistant, by one of the world's foremost experts in leak-resistant cryptography. Most elliptic curve software is not. Like RSA, elliptic curve also involves exponentiation and modular reduction.

Reply on news.ycombinator.com