@ Loup's Impossible? Like that would stop me.

01/2020

128 Bits of Security and 128 Bits of Security: Know the Difference

It might save some CPU. :-)

When I started working on Monocypher, I quickly noticed something strange about Daniel J. Bernstein’s choices of ciphers and curves. On the one hand, he favoured (and designed) ciphers that have 256 bits of security, and explained in painstaking details that 128-bit encryption keys may not be quite enough for all applications. On the other hand, he designed Curve25519, whose security goal is… 128 bits.

That apparent contradiction stumped me for months, during which I simply chose to blindly trust DJB’s reputation. Unsurprisingly, it turned out he thought this through, and there’s no contradiction. “128 bits of security” just means different things in different contexts.

Naive brute force

It goes pretty much like this:

Finding a 128-bit key requires about 2¹²⁸ tries.

Hash preimage

Finding a preimage of a given hash is very similar:

Finding the preimage of a 128-bit hash requires about 2¹²⁸ tries (note: 128-bit hashes are generally too small, because of collisions).

Hash collisions

Hash collisions are different. They’re much easier to find than preimages. You basically take advantage of the birthday paradox to perform a birthday attack.

Okay, I lied. If we did it like that, we’d have to remember every hash, which would then take humongous amounts of memory. To avoid that, we can use Pollard’s rho method: repeatedly hash a value until you spot a cycle (which you will, since the number of possible hashes is finite). The point where you enter the cycle is where you’ll find your collision. (Hence the name “rho”: the path is like a straight line of dots, ending in a loop.) Let’s try again:

There are efficient ways to run this in parallel, with little memory. They’re about as fast as a naive birthday attack, even if we ignore memory accesses. Overall, finding a collision on a 256-bit hash requires about 2¹²⁸ hash computations, and little else.

Breaking elliptic curves (ECDLP)

To break an elliptic curve (that is, to solve the Discrete Logarithm Problem in the elliptic curve’s cyclic group), you’d actually use the same methods as you’d use to break a hash.

Let’s say you want to find the private key k of the public key K. With elliptic curves, K = [k]B, where B is the base point of the curve (a generator of the group). One way to do it is to find a, b, a’, and b’ such that: [a]B + [b]K = [a’]B + [b’]K, and b ≠ b’. From there:

[a]B + [b]K      = [a']B + [b']K
[a]B - [a']B     = [b']K - [b]K
[a-a']B          = [b'-b]K
[(a-a')/(b'-b)]B = [(b'-b)/(b'-b)]K = K = [k]B
[(a-a')/(b'-b)]B = [1]K
[(a-a')/(b'-b)]B = [k]B
 (a-a')/(b'-b)   =  k

First though, we have to find that collision. One way to find it is to define two random mappings m and n from curve points to scalars, and use them to perform a random walk:

The same optimisations used for hash collisions apply. In addition, there are more efficient walks, that use point addition instead of full blown scalar multiplications. When all known optimisations are applied, breaking a curve of order 2²⁵⁶ requires about 2¹²⁸ point additions, just like hashes. (Or a large quantum computer. As of 2020, we have yet to build one, so let’s ignore the issue for now.)

“128 bits of security”

Depending on context, “128 bits of security” can mean:

Computing a cipher, a hash, or a point addition takes a comparable amount of work (like within an order of magnitude or so). The algorithms involved all have massively parallel versions, whose memory and time overhead is minimal. So at a first approximation, any of the above will require as much resources.

At first sight, “128 bits of security” does mean the same thing everywhere. But that’s only so from a narrow point of view.

Scaling down key search (and hash preimages)

In the context of ciphers, we’re not just worried about an attacker finding our key with reasonable certainty. We’re often worried about an attacker having any chance of finding any key.

For a key space of size K, searching N keys at once, while tolerating 1/C chances of success, means you need about K/NC cipher computations. (Most ciphers target a security level equal to the length of their keys. There are some exceptions, though.) Simply put:

DJB gave an excellent example in Understanding Brute Force:

Consider again the standard parallel machine in Section2, with 2³² AES circuits. Recall that, after 2⁶⁴ AES computations [per circuit], this machine has chance close to 2⁻³² of finding a target key k1, and chance close to 2⁻²² of finding at least one of the 2¹⁰ target keys

Is this an acceptable level of security? Many people don’t think so.

(For reference, 2⁻²² is a little under 1 over 4 millions. Such odds are better than many national lotteries.)

Brute forcing hash preimages works basically the same: for a hash space of size H, trying to find preimages of N hashes at once, while tolerating 1/C chances of success, means you need about H/NC hash computations.

Scaling down hash collisions (and ECDLP)

Hash collisions are much easier to find than specific preimages, because of the birthday paradox. Achieving 128-bits of security requires a 256-bit hash. The search space is much bigger than the complexity of the best attack. This kinda changes everything.

First, there’s no such thing as a multi-hash attack when talking about collisions. Finding any collision with reasonable certainty on a 256-bit hash is going to require approximately 2¹²⁸ hash computations. (In a sense, we could say that collision attacks are a degenerate case of multi-hash second preimage attacks, where we’re searching preimages for every possible hash. This is as “multi-hash” as you’ll ever get.)

Second, reducing the cost have even more drastic effects on your chances of success. Cutting down the search space in half divides your chances by four. The drop off is now quadratic (the drop off for key search was linear).

If we used that 2³² circuits standard parallel machine for 2⁶⁴ cycles, our chances of finding a collision in a 256-bit hash would only be 2⁻⁶⁴. Much less scary than the 2⁻²² chance of finding a 128-bit key, even though both ostensibly offer “128 bits of security”.

As we’ve seen, breaking an elliptic curve is like finding a hash collision. Same structure, same optimisations, same chances. Like hash collision, no significant advantage can be gained by attacking several keys at once. Finding the first key among many will still require about 2¹²⁸ point additions (assuming a 256-bit curve).

Conclusion

“128 bits of security” means something much stronger when it’s about hash collisions and elliptic curves, compared to ciphers and hash preimages.

My conclusions as of 2020, are:

(Discuss on Reddit, Lobsters, or Hacker News)