Notes on Mythos breaking AES

Just some interesting tidbits from Claude's attack on cryptography

Recently Mythos was able to make the 7 round AES easier to break by 200-800x.

In short the crux was, during the attack Mythos realized one of its attack byte only permutes the output. So proceeded with a fingerprint accounting for that invariant, reducing the computation by 256x.

The objective of the fingerprinting algorithm is to increase the number of potential lookups into the table that will succeed. One of the stages of the attack from prior work had to enumerate 256 different values and then look them up in the pre-computed table. Mythos developed a fingerprint that is invariant to this guess, which directly reduces the amount of work required by a factor of 256.

The speed up is simply because one of the ‘byte’ - “a character/alphabet” if you will, no longer needs iteration for every other bytes. — that’s the basic insight mythos found.

for k1 in 256:
  for k2 in 256:
    for k3 in 256:
       check()

That’s 256³ checks.

After noticing the invariant, you no longer iterate over that.

for k1 in 256:
    for k3 in 256:
       check_fingerprint()

That’s 256² checks.

After the attack figures our k1 and k3. You just need one additional 256 checks to run AES (or verify a stage).

I was wondering, it is bizarre that such an old algorithm and we still didn’t spot this invariant in the algorithm!

See in AES,

1. XOR with a constant is a permutation

2. The AES S-box is a permutation

3. ShiftRows is a permutation

None of that was new.

What was not known until someone (Mythos) analyzed this specific attack, was this:

That after several pages of “attack-specific” derivation, the dependence on one guessed key byte simplifies to:

Table[index xor guessed_key_byte]

Once you derive that expression, it’s clear that the guessed byte is just changing where to look!

The attack was not analyzed in such detail earlier (or was missed), AES algo is analyzed to death.

Why didn’t we find it earlier?

In simple words, it is just not obvious from AES specification, it’s that the “attack” specific nuances needed more probing.

Think of it like this:

We all know this algebraic property (say this is the AES algo),

A(x + y) = Ax + Ay

Now suppose a research paper has an algorithm (like our Mythos’s attack on AES) like:

Result = A((x + y) - y)

At first glance it looks like both x and y are important. But if we simplify:

(x + y) - y = x

so,

Result = Ax

If you would have blindly just brute forced x and y, you would end up with O(n²).. but if you just see that its only x that needs resolving then its O(n).

So, that’s how the 256x speedup is coming.

It’s important to reiterate that this was only possible while attacking the 7 round version of AES, it doesn’t work (or haven’t been checked if it does) on the 10 round version!

Fun facts from the blog post, they spent around $100k in API token cost over a course of a week. The verification if the attack is genuinely correct took two researchers 1 month.

Some real prompts used are also shared - I really liked how the researchers are prompting it just like us. Trying to steer, convince like it’s a human - https://www.anthropic.com/research/discovering-cryptographic-weaknesses