Re: [CFRG] Curve25519 security level is better than stated in RFC 7748

["D. J. Bernstein" <[e-mail]>]

John Mattsson writes:
> When using AES-128 and Curve25519 together, AES-128 is the weakest
> link (considering known classical attacks). Comparing asymmetric and
> symmetric "operations" are like comparing apples to oranges. When you
> make a fair comparison, it is very clear that Curve25519 is stronger
> than AES-128 based on known classical attacks.

Just writing to fill in some numbers here.

First of all, a standard negating rho attack takes about sqrt(pi l/4)
iterations on average.

https://cr.yp.to/papers.html#grumpy showed that the constant sqrt(pi/4)
isn't optimal in cost models that allow free memory access, and it's
conceivable that the same is true in realistic cost models, but the
potential improvement here was already well known to be limited by
Nechaev--Shoup: a generic negating attack can't do better than 2/3.
Let's assume 2/3 is achievable, so 2^125.4 iterations for Curve25519.

This number 2^125.4 is below the number of AES-128 keys, namely 2^128.
More to the point, it's below the average number of guesses in a
brute-force AES-128 key search, which is about 2^127.

However, as John notes, the 2^125.4 and 2^127 here have different units.
For a valid comparison, we need the same units. Let's count bit
operations.

An unrolled 255-bit multiplication circuit, including Karatsuba and many
lower-layer speedups, uses 95126 XORs and 78828 ANDs/ORs, for a total of
173954 bit operations. https://cr.yp.to/papers.html#qisog includes code
to count this.

An optimized elliptic-curve attack iteration costs 5 multiplications
plus overhead, about 2^20 bit operations overall. Footnote 5 of
https://cr.yp.to/papers.html#sect113r2 is tantamount to reducing 5 to
4.5+o(1) asymptotically (if one ignores the bit operations involved in
RAM access), but it's structurally clear that the o(1) is positive, so
this is below 0.2 bits of difference in security.

To summarize, the ~2^125.4 iterations are above ~2^145.2 bit operations.
The only gap I see in the literature is that there's a missing analysis
of bit operations for more complicated multipliers; I'd guess that Toom
does _marginally_ better than Karatsuba at this size.

For comparison, there are more gaps in the literature analyzing the cost
of AES-128 attacks (e.g., how many bit operations can be shared across
key guesses? what's the impact of bicliques on bit-operation counts?),
but it's reasonably clear that plugging existing AES-128 single-input
optimizations into a naive AES-128 attack brings each iteration below
2^15 bit operations, so the average ~2^127 AES-128 attack iterations are
below 2^142 bit operations.

In short, an X25519 key is an order of magnitude more costly to break
than an AES-128 key by known attacks. (Until the attacker has a quantum
computer, a big caveat noted in the Curve25519 paper.)

Bitcoin is currently around 2^111 bit operations per year, which might
make 2^142 sound safe. An important cautionary note is that multi-target
AES-128 attacks are already feasible for large-scale attackers today;
see generally https://blog.cr.yp.to/20151120-batchattacks.html. As the
Curve25519 paper explains, low-probability attacks and multi-target
attacks have less impact on X25519 security than on cipher security.

Beyond bit operations, there's more to say about exact hardware costs. I
expect a detailed analysis to show that hardware overheads are a bigger
issue for Curve25519 attacks than for AES-128 attacks, most importantly
because of routing overheads. This prediction is based on considering
the high-level data flow in a rho attack against Curve25519 (see the
diagrams in https://cr.yp.to/papers.html#opb for the similar case of
binary elliptic curves), the low-level data flow inside multipliers, the
low-level data flow inside an AES attack, and the mix of bit operations
(which can matter: e.g., NAND is cheaper than XOR in hardware). It would
be interesting to see papers analyzing this.

---D. J. Bernstein