Learn How to Break AES(davidwong.fr)
davidwong.fr
Learn How to Break AES
https://davidwong.fr/blockbreakers/
56 comments
Interestingly enough, the Square attack (otherwise more generally known as integral cryptanalysis) is much more powerful than regular linear or differential cryptanalysis when applied to the AES.
I'm actually looking for an intern to reboot this project :) if anybody is interested https://blog.zksecurity.xyz/posts/internship-2025/
Just in case anyone's wondering, AES - the regular AES-128, 192 or 256 - is not publicly broken (yet).
In fact it is IMO unlikely this primitive will ever be broken. Its predecessor, DES was "broken" only in the sense that it was intended to be possible to break it with enough computing power when it shipped, as a NOBUS (Nobody But Us can break it) by the US government. In 1975 this is a NOBUS, in 2025 it's basically saying "Please hack us China" so we don't do that any more.
Although cryptanalysis of DES did reveal some flaws, the actual breaks, including ones you'd use today if tasked to break DES at scale, all target exactly the two deliberately chosen weaknesses from when it was designed 50 years ago - its keys are too small and its block sizes are too short, that's all, and that's enough.
In AES neither of these flaws is present, hence I am not alone in thinking we probably won't ever build another one.
You might think well, in 50 years we'll have better computers so that's dumb. Nope. Unless there's an actual mathematical break what runs out isn't mere human ingenuity, it's plain physics.
Although cryptanalysis of DES did reveal some flaws, the actual breaks, including ones you'd use today if tasked to break DES at scale, all target exactly the two deliberately chosen weaknesses from when it was designed 50 years ago - its keys are too small and its block sizes are too short, that's all, and that's enough.
In AES neither of these flaws is present, hence I am not alone in thinking we probably won't ever build another one.
You might think well, in 50 years we'll have better computers so that's dumb. Nope. Unless there's an actual mathematical break what runs out isn't mere human ingenuity, it's plain physics.
Modern ciphers including AES subscribe to the philosophy of using a simple round and then repeat it a bunch of times.
While this is most likely sound (due to the sensitivity to initial conditions aka avalanche effect) there is a small chance that this creates a mathematical structure that will one day get exploited.
AES is even more vulnerable to this chance than usual because it actually uses mathematical functions for several of its components (the sbox and the 32-bit linear permutation). No one has been able to exploit this combination yet though.
Contrast this with SHA-2 for example, it's an unbalanced Feistel permutation that had a lot of 'random' nonlinear crap thrown in. SHA-2 can actually be used as a block cipher (SHACAL-2) however there is no HW acceleration for the inverse permutation - so you would be limited to CTR-like modes.
While this is most likely sound (due to the sensitivity to initial conditions aka avalanche effect) there is a small chance that this creates a mathematical structure that will one day get exploited.
AES is even more vulnerable to this chance than usual because it actually uses mathematical functions for several of its components (the sbox and the 32-bit linear permutation). No one has been able to exploit this combination yet though.
Contrast this with SHA-2 for example, it's an unbalanced Feistel permutation that had a lot of 'random' nonlinear crap thrown in. SHA-2 can actually be used as a block cipher (SHACAL-2) however there is no HW acceleration for the inverse permutation - so you would be limited to CTR-like modes.
While what you say about the vulnerabilities of AES is true, it is very easy to modify AES to remove these weaknesses, and in a way that still allows the use of the special AES instructions of CPU ISAs like Intel/AMD x86-64 or ARM Aarch64, so that the decreasing of the encryption/decryption throughput would be very small.
There are several ways to achieve this. An example would be to replace a few of the XOR (additions modulo 2) operations that introduce subkeys between the AES rounds with another kind of addition instructions, e.g. with addition modulo 2^64.
These additions do not commute with the operations in the Galois field used by AES and they completely destroy the system of equations in that Galois field that is equivalent with the standard AES, making impossible any algebraic attempts at breaking AES. Moreover, if the additions would replace XOR in irregular places, that would make some of the rounds distinct from the others, breaking an attack that depends on all the rounds being identical. By replacing quasi-randomly the XOR operations with either addition modulo 2^64 or addition modulo 2^32 it is possible to make all the AES rounds distinct, with no pair of identical rounds and with only a negligible throughput decrease.
Also using the usual hardware AES instructions, it is simple to implement the Rijndael variant with a block size of 256 bits, which is much stronger than the standard AES with a block size of 128 bits (this has been described in an Intel application note when they have introduced the AES instructions in the Intel Westmere CPUs, in 2010).
So any possible advances in the cryptanalysis of AES will have effects only for the decryption of old recordings of encrypted information.
Future encrypted information will be easily protected against any advances with only software changes.
There are several ways to achieve this. An example would be to replace a few of the XOR (additions modulo 2) operations that introduce subkeys between the AES rounds with another kind of addition instructions, e.g. with addition modulo 2^64.
These additions do not commute with the operations in the Galois field used by AES and they completely destroy the system of equations in that Galois field that is equivalent with the standard AES, making impossible any algebraic attempts at breaking AES. Moreover, if the additions would replace XOR in irregular places, that would make some of the rounds distinct from the others, breaking an attack that depends on all the rounds being identical. By replacing quasi-randomly the XOR operations with either addition modulo 2^64 or addition modulo 2^32 it is possible to make all the AES rounds distinct, with no pair of identical rounds and with only a negligible throughput decrease.
Also using the usual hardware AES instructions, it is simple to implement the Rijndael variant with a block size of 256 bits, which is much stronger than the standard AES with a block size of 128 bits (this has been described in an Intel application note when they have introduced the AES instructions in the Intel Westmere CPUs, in 2010).
So any possible advances in the cryptanalysis of AES will have effects only for the decryption of old recordings of encrypted information.
Future encrypted information will be easily protected against any advances with only software changes.
I don't think there is much to be gained by Rijndael-256 (it requires 2 AES-NI operations with a shuffle in between anyway).
There are more promising Feistel-like constructions on top of AES operations such as Areion: https://eprint.iacr.org/2023/794
There are more promising Feistel-like constructions on top of AES operations such as Areion: https://eprint.iacr.org/2023/794
Any extension of AES to a 256-bit block size would need to use at least a double number of AES-NI operations, but it will also process a double amount of data, so that is not the problem.
The shuffle of Rijndael-256 is suboptimal, being a derivative of the shuffle designed for an 128-bit block, so it is certainly possible to devise something better than that when designing specifically for a 256-bit size. Rijndael-256 has only the advantage that it is a quasi-standard mode, which has passed some cryptanalysis during the AES competition.
I have not studied Areion, but at a first glance I agree with you that it seems promising.
The shuffle of Rijndael-256 is suboptimal, being a derivative of the shuffle designed for an 128-bit block, so it is certainly possible to devise something better than that when designing specifically for a 256-bit size. Rijndael-256 has only the advantage that it is a quasi-standard mode, which has passed some cryptanalysis during the AES competition.
I have not studied Areion, but at a first glance I agree with you that it seems promising.
Exploitable mathematical structure arising purely from the concept of an iterated cipher is probably what Nick meant there by "an actual mathematical break". SHACAL-2 is also an iterated cipher with a relatively simple round structure.
Pretty much all block ciphers (and therefore their derivative constructions) are iterated.
The SHACAL-2 permutation though is much more mathematically unstructured than AES. It's an augmented ARX unbalanced Feistel design (w/ additional non-linearities). Hard to imagine you could reconstruct any usable mathematical structure in that mess. It also has a strong key schedule which is not vulnerable to related-key attacks (AES is) which is by design due to its hashing application. 512-bit key space too which allows for easy nonce integration.
The SHACAL-2 permutation though is much more mathematically unstructured than AES. It's an augmented ARX unbalanced Feistel design (w/ additional non-linearities). Hard to imagine you could reconstruct any usable mathematical structure in that mess. It also has a strong key schedule which is not vulnerable to related-key attacks (AES is) which is by design due to its hashing application. 512-bit key space too which allows for easy nonce integration.
Most block ciphers iterate the same round function, but this regularity is destroyed by using distinct round keys in each round.
The only vulnerabilities of the iterated construction appear when a weak method is used for generating the round keys from the cipher key (i.e. when the so-called key schedule is weak), so that there are predictable relationships between the round keys.
There exists an alternative (and equivalent) construction for a block cipher, when the same key is introduced in all rounds, but in this case all the round functions must be different from each other (instead of iterating the same function).
The only vulnerabilities of the iterated construction appear when a weak method is used for generating the round keys from the cipher key (i.e. when the so-called key schedule is weak), so that there are predictable relationships between the round keys.
There exists an alternative (and equivalent) construction for a block cipher, when the same key is introduced in all rounds, but in this case all the round functions must be different from each other (instead of iterating the same function).
Ironically, the reason SHA2 isn't reachable by the attacks that broke SHA1 is the simplicity of the SHA1 message schedule, which was also by design due to its hashing application.
SHA1 has a sloppy key/msg schedule. They could have just done a random permutation of words and been safe - it would have even been cheaper than what the ended up doing. Such as what BLAKE does.
> in 2025 it's basically saying "Please hack us China" so we don't do that any more.
It took almost two decades to explain that to sitting presidents and Congress.
'We' have been telling 'them' that shit won't scale since at least the 90's.
Everyone forgets about Al Gore's black sheep - the Clipper Chip.
It took almost two decades to explain that to sitting presidents and Congress.
'We' have been telling 'them' that shit won't scale since at least the 90's.
Everyone forgets about Al Gore's black sheep - the Clipper Chip.
That is in the US. Major European countries still haven't figured that out. (I'm not sure if US congress really has either, but at least I haven't seen any backdoor movements come out in the past few years)
BTW, if you are keeping score: stop. Every country has things they do well and things they do bad. Look for and fix your local bads, this isn't a game of who is better, it is a game everyone should win.
BTW, if you are keeping score: stop. Every country has things they do well and things they do bad. Look for and fix your local bads, this isn't a game of who is better, it is a game everyone should win.
I donated money to EFF every year until Gore switched to bothering fossil fuel industries instead of the software industry.
I had my first tech job thanks to his NSF funding as Senator Gore but he was also a spook and in the end it ended up evening out.
> BTW, if you are keeping score: stop.
Yeah maybe not doing so good at that. But you always have to watch out for that time when your 'friends' will accidentally sell you out if you don't reiterate your social and professional boundaries with them from time to time.
I had my first tech job thanks to his NSF funding as Senator Gore but he was also a spook and in the end it ended up evening out.
> BTW, if you are keeping score: stop.
Yeah maybe not doing so good at that. But you always have to watch out for that time when your 'friends' will accidentally sell you out if you don't reiterate your social and professional boundaries with them from time to time.
I suspect we might move to some sort of cipher that uses the AES round function but isn't full AES, like AEGIS, for performance benefits. Same permutation, but arguably a different primitive. That move won't be because AES got broken though, it'd be because AES wasn't as fast as desired.
>...all target exactly the two deliberately chosen weaknesses from when it was designed 50 years ago...
I would quibble the deliberate part for the block length (and perhaps strengthen your point). DES came out in the 70's and people were still designing 64 bit ciphers in the 90's. Examples: IDEA, CAST5, Blowfish. I think that it is most likely that the the 56 bit key length was really the only factor intended to make DES deliberately weak. Gigabyte scale files/sessions were just not a thing back then.
I would quibble the deliberate part for the block length (and perhaps strengthen your point). DES came out in the 70's and people were still designing 64 bit ciphers in the 90's. Examples: IDEA, CAST5, Blowfish. I think that it is most likely that the the 56 bit key length was really the only factor intended to make DES deliberately weak. Gigabyte scale files/sessions were just not a thing back then.
The ancestor of DES at IBM, Lucifer, had both an 128-bit block length and 128-bit keys.
Therefore there is no doubt that both the reduction of the key length and of the block length have been deliberate.
The only thing that can be argued is that perhaps the motivation for the reduction in the block length could have been less for weakening the cipher, but more for reducing the cost of the hardware, based on the assumption that the cipher will be used only for the encryption of amounts of data that are very small for today, but which could have seemed big during the mid seventies.
Therefore there is no doubt that both the reduction of the key length and of the block length have been deliberate.
The only thing that can be argued is that perhaps the motivation for the reduction in the block length could have been less for weakening the cipher, but more for reducing the cost of the hardware, based on the assumption that the cipher will be used only for the encryption of amounts of data that are very small for today, but which could have seemed big during the mid seventies.
To make a 64 bit block size be helpful for signals intelligence in the '70s the following things would have to be true:
1. Someone would have an encrypted session or file that ran into the 10s of GB.
2. The signals intelligence entity would have to somehow have gotten access that much data. Did they tap a telephone line and intercept a 300 bps modem connection for 30 years straight? Did they get access to half a billion encrypted punch cards?
3. The signals intelligence entity would have enough processing power and memory to actually find the collisions.
4. The signals intelligence entity would be able to extract some useful information out of 1 or 2 colliding 8 byte blocks randomly chosen out of billions in the same file/session. The extreme unlikeliness of that is why such collisions are still of little practical use today.
1. Someone would have an encrypted session or file that ran into the 10s of GB.
2. The signals intelligence entity would have to somehow have gotten access that much data. Did they tap a telephone line and intercept a 300 bps modem connection for 30 years straight? Did they get access to half a billion encrypted punch cards?
3. The signals intelligence entity would have enough processing power and memory to actually find the collisions.
4. The signals intelligence entity would be able to extract some useful information out of 1 or 2 colliding 8 byte blocks randomly chosen out of billions in the same file/session. The extreme unlikeliness of that is why such collisions are still of little practical use today.
When using a block cipher function solely for encryption, it is difficult to exploit a small block size.
On the other hand, a short block size complicates a lot the use of a block cipher function in other useful algorithms, e.g. key derivation algorithms, RNG algorithms, MAC algorithms etc.
The necessity of using a block cipher function also for such purposes has become very obvious almost immediately after the standardization of DES, but then it was too late.
Such applications have been seriously hindered for a couple of decades, until the mid nineties, by the lack of any other publicly known strong block cipher functions. Many workarounds have been published with the purpose of using DES even where its short block length was unacceptable, but all such workarounds were more inefficient than using a block cipher with a greater block size. They were designed only because it was expected that using the already existing hardware integrated circuits that computed DES would be more efficient than implementing a block cipher function in software, on the slower computers of that time.
On the other hand, a short block size complicates a lot the use of a block cipher function in other useful algorithms, e.g. key derivation algorithms, RNG algorithms, MAC algorithms etc.
The necessity of using a block cipher function also for such purposes has become very obvious almost immediately after the standardization of DES, but then it was too late.
Such applications have been seriously hindered for a couple of decades, until the mid nineties, by the lack of any other publicly known strong block cipher functions. Many workarounds have been published with the purpose of using DES even where its short block length was unacceptable, but all such workarounds were more inefficient than using a block cipher with a greater block size. They were designed only because it was expected that using the already existing hardware integrated circuits that computed DES would be more efficient than implementing a block cipher function in software, on the slower computers of that time.
Grovers algorithm can brute-force a 128-bit symmetric cryptographic key in roughly 2^64 iterations (on a quantum computer which we likely have in 50 years), instead of 2^128. Now, lets find another attack vector (maybe with the help of AI) that reduces the 64 a bit and you are in the realm of feasibility.
2^64 work that is non-paralellizable isn't a threat. 64 bits of classical security is insufficient because computers can do thousands of operations in parallel, and you can combine the effort of millions of computers. Grover's algorithm gives you a sequential complexity of 2^64, so if you have a quantum comptuer with a clock speed of 20GHZ (current quantum computers are in the khz to low mhz range), and you pretend that the quantum computer can process 14 rounds of AES per clock cycle (in reality it would be hundreds of cycles), it will take a quantum computer running for 30 years continuously to crack a single key (and if the temperature ever rises 1 millionth of a degree or the computer loses power for a nanosecond, you have to start over).
But everyone will upgrade to AES-256 (many system already has), and that truly will be the final symmetric algo even with moore's law.
MD-5 died the same way. We had to scare people into investing into upgrading to SHA-1 by showing them the slope of hardware and the variability in new breakthroughs and ask if they'd rather have an emergency that lasted for over a month or work it into the schedule among the other requirements now?
Yes, people can upgrade but nobody fucking will until you impress upon them how stupid they're being by gambling the entire company on carrying that debt for another year.
Yes, people can upgrade but nobody fucking will until you impress upon them how stupid they're being by gambling the entire company on carrying that debt for another year.
Only those who can change. In work in embedded systems - we still have to talk to machines that were built with exportable encryption in the 90's (read if it isn't broken that is only because nobody who has a clue has bothered to try). They can't be upgraded anymore so I have to keep those algorithms building just in case someone wants to mix new with old. (fortunately the old machines are never internet connected so vulnerability requires local access - but the vulnerability is in safety critical functions so I don't rest too easy)
I use the SHA-1 example in part because that was the newest hash that a bunch of smart cards someone wanted to try to use with our system supported.
Of course the max RSA key lengths on the card weren't up to it anyway (kids: if you by crypto hardware and don't use it immediately, don't warehouse it looking for a problem for your solution), but at least I got to put my foot down and we only shipped with SHA-1 and SHA-2 support
Of course the max RSA key lengths on the card weren't up to it anyway (kids: if you by crypto hardware and don't use it immediately, don't warehouse it looking for a problem for your solution), but at least I got to put my foot down and we only shipped with SHA-1 and SHA-2 support
Certainly one of the most clickbaity titles I've seen.
If you're interested in this sort of thing, I cannot recommend the cryptopals crypto challenges enough. They are a series of project that take you from XOR up through breaking AES and beyond:
https://cryptopals.com/
https://cryptopals.com/
You also have https://cryptohack.org/
The writing of Cryptopals is unclear. I've made it about half-way through the challenges twice over the past decade. I get that it's prompting me to learn on my own, as if I was a real cryptanalyst encountering a system for the first time, but I literally do not understand what is being asked or the constraints of the problems sometimes. It's like author is trying to be clever and curt and gate-keeper-y on purpose. "You should be able to do this with a shitty, hastily-written problem description, right?"
We ran these challenges at Matasano with the public, under a system where you could only get the next 8 challenges after demonstrating that you'd solved the previous 8, after I wrote an internal guide for our consultants on the cryptographic vulnerabilities they should be capable of addressing on engagements. What you're reading there is basically an internal README. They got very popular (many, many people have solved all of them without additional prompting), but we didn't really invest any extra time in cleaning them up or refining their pedagogy.
…and thank you (all) for doing so. It’s my go-to motivation when teaching Rust to experienced programmers. It’s a raging success every time.
I'm blown away by the response. In Sean and Alex's defense (especially Sean's), the writing got better in set 7 and, especially, set 8, which Sean was really careful about and which is clearly the crown jewel of the whole series.
[deleted]
Neat, I'm looking forward to the Differential Cryptanalysis portion! It's something I've tried to learn in the past but I've been struggling to find approachable resources.
This looks very nice! Thank you!
I'm currently taking Cryptography at university and I find the resources online to be quite scarce. I mostly find myself reading Wikipedia. I don't know if I'm missing some background knowledge but some of the math notations tend to be quite difficult to understand. I have spent around 10 hours trying to understand Differential Cryptanalysis unsuccessfully!
I'm currently taking Cryptography at university and I find the resources online to be quite scarce. I mostly find myself reading Wikipedia. I don't know if I'm missing some background knowledge but some of the math notations tend to be quite difficult to understand. I have spent around 10 hours trying to understand Differential Cryptanalysis unsuccessfully!
If you haven’t seen it already, check out “Understanding Cryptography: A Textbook for Students and Practitioners”. Probably one of the best and approachable books on cryptography. Plus all the lectures are on YouTube so you can read a chapter and then watch the lecture. Also with the math notation, you a take a photo of it and ask ChatGPT to try to explain it.
Thank you! I'll take a look! Yes, I agree with the suggestion on math notation - I should start doing that.
I can highly recommend Cryptography Engineering by Bruce Schneier. I read it years ago and to this day it still helps me regularly.
Cryptography Engineering definitely does not hold up. It predates (almost willfully, given the chronology) modern notions of AEAD, key derivation, random number generation, and elliptic curve asymmetric cryptography.
The standard recommendation these days is Aumasson's Serious Cryptography. I like David Wong's Real-World Cryptography as well.
The standard recommendation these days is Aumasson's Serious Cryptography. I like David Wong's Real-World Cryptography as well.
I really enjoyed the book and it certainly helped me, but it's also the only cryptography book I've ever read. I appreciate you challenging my suggestion!
I just checked and it has been a whooping 12 years since I purchased/read the book, so I retract my recommendation.
I just checked and it has been a whooping 12 years since I purchased/read the book, so I retract my recommendation.
Sorry, you're right, I should have been less clinical about this. Practical Cryptography (which is essentially the exact same book by the same authors) was also the first cryptography book that clicked in any meaningful way for me, and really lit me up about the prospect of finding vulnerabilities in cryptosystems.
I would actively recommend against using it as a guide in 2025. But you're not crazy to have liked it before. Funny enough, 12 years ago, I wrote a blog post about this:
https://sockpuppet.org/blog/2013/07/22/applied-practical-cry...
I would actively recommend against using it as a guide in 2025. But you're not crazy to have liked it before. Funny enough, 12 years ago, I wrote a blog post about this:
https://sockpuppet.org/blog/2013/07/22/applied-practical-cry...
I read the beginning of the post and it looks quite interesting. I'll read the rest tomorrow when my mind is sharper.
I checked my blog and I also wrote a post about some crypto related things shortly after I purchased the book. It's a post about a bug in the JDK that I stumbled across, which I am certain I would not have understood without Bruce's book:
https://blog.heckel.io/2014/03/01/cipherinputstream-for-aead...
Btw, I was a bit of a fan boy back then and I got the signed copy of the book, haha.
I checked my blog and I also wrote a post about some crypto related things shortly after I purchased the book. It's a post about a bug in the JDK that I stumbled across, which I am certain I would not have understood without Bruce's book:
https://blog.heckel.io/2014/03/01/cipherinputstream-for-aead...
Btw, I was a bit of a fan boy back then and I got the signed copy of the book, haha.
I am a lot more cynical about Schneier's influence on the practice of cryptography engineering today than I was when he and Ferguson (who I am not cynical about at all) wrote the book back in 2003.
Yeah when it comes to math Wikipedia is rarely a good introduction to any topic. Maybe if one studied mathematics before or something, but definitely not for most other people.
that's really a shame actually, I think many people try to use wikipedia for Math and it's almost never a good idea
Not so long ago I wrote the book I wish I had when I was studying cryptography back in uni: https://livebook.manning.com/book/real-world-cryptography/ch...
Cool! Would be nice to also include side-channel attacks
Side channels aren't block cipher cryptanalysis. There's some very basic side channel stuff in Cryptopals, but modern side channel analysis is primarily microarchitectural, which is a significant change in focus, and someone should do a standalone resource on that.
Well it's very connected, you're using the knowledge about block cipher to attack them, even though it's not the "pure mathematical attack", it's still the most widespread attack against current cryptographic systems
That's not true, there are plenty of side-channel attacks that fall squarely within the realm of block cipher cryptanalysis. Examples include Differential Fault Analysis (DFA), Correlation Power Analysis (CPA) and more.
It's true that practical side-channel leaks on software block cipher implementations tend to be microarchitectural (e.g. cache timing), but that's only because the "easier" attacks are already mitigated or considered out of scope (e.g. no physical access).
It's true that practical side-channel leaks on software block cipher implementations tend to be microarchitectural (e.g. cache timing), but that's only because the "easier" attacks are already mitigated or considered out of scope (e.g. no physical access).
Eh, fair enough. Something like differential fault analysis would make a lot of sense in a block cipher cryptanalysis sequence.
I recently did a CTF challenge write-up for an AES timing side-channel, which I tried to make similarly approachable: https://www.da.vidbuchanan.co.uk/blog/uoftctf-timed-aes.html
It's not quite the same "lab exercises" format but the CTF challenge files are public, so you can try it for yourself.
It's not quite the same "lab exercises" format but the CTF challenge files are public, so you can try it for yourself.
http://www.cs.bc.edu/~straubin/crypto2017/heys.pdf
My recommendation: print it out to a PDF with huge margins so you can make notes, and then work through all the worked examples.