[HN Gopher] Learn How to Break AES
___________________________________________________________________
Learn How to Break AES
Author : baby
Score : 128 points
Date : 2025-03-04 17:25 UTC (5 hours ago)
(HTM) web link (davidwong.fr)
(TXT) w3m dump (davidwong.fr)
| Retr0id wrote:
| 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.
| oulipo wrote:
| Cool! Would be nice to also include side-channel attacks
| tptacek wrote:
| 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.
| alabhyajindal wrote:
| 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!
| zelphirkalt wrote:
| 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.
| __alexander wrote:
| 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.
| alabhyajindal wrote:
| Thank you! I'll take a look! Yes, I agree with the suggestion
| on math notation - I should start doing that.
| MontagFTB wrote:
| 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/
| cinntaile wrote:
| You also have https://cryptohack.org/
| secret-noun wrote:
| 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?"
| underdeserver wrote:
| Just in case anyone's wondering, AES - the regular AES-128, 192
| or 256 - is not publicly broken (yet).
| tialaramex wrote:
| 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.
| randomtoast wrote:
| 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.
| metacritic12 wrote:
| 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.
| hinkley wrote:
| 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.
| bluGill wrote:
| 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)
| hinkley wrote:
| 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
| adgjlsfhk1 wrote:
| 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).
| hinkley wrote:
| > 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.
| bluGill wrote:
| 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.
| hinkley wrote:
| 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.
| cakealert wrote:
| 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.
| tptacek wrote:
| 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.
| cakealert wrote:
| 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.
| adrian_b wrote:
| 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.
| cakealert wrote:
| 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
| upofadown wrote:
| >...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.
| userbinator wrote:
| Certainly one of the most clickbaity titles I've seen.
| tptacek wrote:
| David Wong hasn't been at NCC Cryptography for a long time, so I
| assume we'll be waiting a long time before we get to Linear and
| Differential cryptanalysis, but if that's a thing you're
| interested in, what you want is the Heys tutorial:
|
| 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.
| pbsd wrote:
| 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.
___________________________________________________________________
(page generated 2025-03-04 23:00 UTC)