[curves] Point validation (was: Twist security for elliptic curves)

[D. J. Bernstein]

Trevor Perrin writes:
> I think Lochter et al would argue for point validation at the *start*
> of the computation, since they're thinking about fault and sidechannel
> attacks.

No. One of the reasons that the Lochter--Wiemers "attack" doesn't work
is that it starts from the delusion that you're simply _giving away_ nQ
to the attacker, where n is your long-term secret key and Q is an
attacker-supplied point.

The paper says that "Static multiplication with a secret value is used,
for example, with static ECDH". But in static ECDH the resulting point
nQ is a _shared secret_ (typically hashed and used as a secret key for,
say, AES-GCM), not something shown to the attacker. The paper doesn't
make the wild claim that side-channel attacks magically see nQ while
having trouble seeing n; the paper simply tries to fool readers into
believing that static ECDH shows nQ to the attacker.

(The paper also claims a "compromise" of the "secret signature key" for
deterministic signature schemes. There are even more reasons that this
"attack" doesn't work, where the most obvious is that the "attack" needs
the signer to replace the standard base point P with an attacker-visible
point Q. One can of course imagine faults producing any result that the
attacker wants---but that's also why there's an extensive literature
explaining how to robustly defend against faults.)

The only reasonable part of the paper is what the paper actually asks
side-channel attacks to do, namely extract noisy bits of n+rl, where r
is chosen randomly and l is the order of the standard base point P. This
is also what previous papers do. This reasonable assumption, combined
with the Lochter--Wiemers delusion, produces the following "attack":

   * The attacker sends you a point Q on the twist.

   * You use a ladder. (Even for Weierstrass curves this is a reasonable
     assumption: consider, e.g., the Lochter--Merkle--Schmidt--Schuetze
     statement that the Brier--Joye ladder is "commonly used in"
     high-assurance smartcards.)
   
   * You don't check whether Q is on the twist. (This is a reasonable
     assumption, and it's _exactly_ why twist security is so important:
     in the same situation, brainpoolP256t1 is completely broken by an
     easy attack taking just 2^45 additions.)

   * You randomize the ladder: i.e., what you compute as the shared
     secret is actually (n+rl)Q. The attacker sees noisy bits of n+rl.

   * The delusion: You send your shared secret (n+rl)Q to the attacker.

   * The delusion, iterated: By repeating this process the attacker sees
     (n+r_1 l)Q, (n+r_2 l)Q, (n+r_3 l)Q, etc.

   * The attacker subtracts to obtain (r_1-r_2)Q, (r_1-r_3)Q, etc., and
     then performs small-interval discrete-logarithm computations to
     obtain r_1-r_2, r_1-r_3, etc. (Another reason that the attack
     doesn't work is that my recommended 256-bit r's for Curve25519
     aren't in a small interval. Note that Curve25519 with this
     super-conservative size of r is still faster than Brainpool with
     minimum-size r.)

   * The attacker adds (r_1-r_2)l to the noisy n+r_2 l to obtain a noisy
     n+r_1 l, adds (r_1-r_3)l to the noisy n+r_3 l to obtain another
     noisy n+r_1 l, etc. Trivial averaging then produces the correct
     n+r_1 l, and reducing mod l then produces n.

The conclusion claims that the paper has "described vulnerabilities of
implementations of ECC-algorithms using blinded static point
multiplications that may result from unjustified trust into twist
security. These algorithms include static Diffie-Hellman and
deterministic ECDSA as well as the ECIES decryption." But _none_ of
these cryptographic systems show the attacker nQ for a long-term secret
n and an attacker-controlled point Q.

As I wrote before, one can of course invent protocols that reveal nQ for
a long-term n and an attacker-controlled Q, but these protocols are so
rarely used (even in software, never mind hardware) that I can't find
any ECC standards considering them. Lochter, in the Brainpool standard,
explicitly _refused_ to consider the security of such protocols. Even
worse, various Brainpool curves would suffer serious security losses if
they were used in these protocols. For example:

   * Lochter claimed 2^80 security from brainpoolP160r1. However, the
     same delusion implies that brainpoolP160r1 is broken in just 2^69
     additions (a clearly feasible attack) after 3850536 points Q.

   * Lochter claimed 2^160 security for brainpoolP320r1. However, the
     same delusion implies that brainpoolP320r1 loses 2^10 security
     after 1003135 points Q, and loses 2^15 security after 1181119810
     points Q.

Why hasn't Lochter issued a security alert for brainpoolP160r1,
brainpoolP320r1, etc.? I'm again cc'ing him to ask for an explanation.

There are other problems with the Lochter--Wiemers paper, but the fact
that the attack doesn't work is ample reason to disregard the paper.

---Dan