6 ms·

Researchers identify first flaws in AES

155 points by fogus 15y ago

dchest 15y ago
Paper and slides: http://research.microsoft.com/en-us/projects/cryptanalysis/aes.aspx http://research.microsoft.com/en-us/projects/cryptanalysis/a...
- phillmv 15y ago
  Ah! Novel cryptanalysis technique reduces practical AES key length by about 2 bits.
  - eru 15y ago
    Which is quite an achievement.
seagaia 15y ago
Well, we certainly won't have to worry about it for now. But that doesn't mean we shouldn't worry about it, of course. It's a ways off in terms of orders of magnitude for how fast our computers now, and I don't think computers will be growing at that rate in terms of power unless new breakthroughs are found.
- m0nastic 15y ago
  The general rule of thumb for cryptanalysis attacks is that they become cheaper over time (usually quicker than initially proposed), which is why finding issues (even mathematical issues that aren't yet practical) is so important. Considering the length of time that it takes for new encryption standards to be proposed and accepted, it's important to try and stay ahead of the curve.
- sp332 15y ago
  If you couldn't crack it before, you still can't crack it now. This attack only makes it 4 times easier to break, not even an order of magnitude.
  - eru 15y ago
    If you count in binary, 2 bits are two orders of magnitude.
- tptacek 15y ago
  If you are using AES directly in your code, you should be very, very worried no matter what the research says, because you are vanishingly unlikely to have gotten it right. Use TLS or GPG.
deleted 15y ago
[deleted]
bonzoesc 15y ago
I guess once SHA-3 is done, NIST better start research on the next symmetric cipher. The attack only knocks off two bits now, but attacks only get better with time. Note that you should be using accepted standards for key management anyways. NIST believes that AES-128 has 128 bits of strength, and AES-256 has 256 bits of strength [1, page 63], which they find "Acceptable" until 2031 [1, page 65]; the catch is that any individual key should be expired after a few years. This is called a "cryptoperiod," and the longest they recommend using a key is five years [1, page 55]. By this standard, keep using AES-256, but change your keys every year, and be prepared to migrate to a new cipher at some point within the next decade or two. [1]: http://csrc.nist.gov/publications/drafts/800-57/Draft_SP800-57-Part1-Rev3_May2011.pdf http://csrc.nist.gov/publications/drafts/800-57/Draft_SP800-...
- dchest 15y ago
  Speaking of SHA-3, "biclique cryptanalysis was ﬁrst introduced for hash cryptanalysis". Here's an interesting quote from the paper regarding the relationship between attacks on block ciphers and hash functions: "... the block cipher standard AES is almost as secure as it was 10 years ago in the strongest and most practical model with a single unknown key. The former standard DES has not seen a major improvement since Matsui’s seminal paper in 1993. In contrast, the area of hash function cryptanalysis is growing quickly, encouraged by the cryptanalysis MD5, of SHA-0 and SHA-1, followed by a practical attack on protocols using MD5, preimage attacks on Tiger and MD5, etc. As differential cryptanalysis, a technique originally developed for ciphers, was carried over to hash function analysis, cryptanalysts are now looking for the opposite: a hash analysis method that would give new results on block ciphers."
- tptacek 15y ago
  The total cost to the industry of adopting AES was enormous. That implies that deprecating it would at present impose costs that far outweigh the benefits, because replacing AES will be expensive, and there are at present minimal practical benefits to doing so. Remember, plenty of critical systems have been fielded that rely on RC4 and DES-EDE, both of which are also (for all intents and purposes) unbroken in their most common usage. For Hacker News, the far more important thing to point out is that no matter what block cipher you use, you are never going to get burnt by research like this, but you are almost certain to be completely boned by implementation errors.
cperciva 15y ago
Note: This attack requires a large amount of RAM. They may have saved a few operations, but they increased the total cost by many orders of magnitude over a brute-force search because they need a larger machine. Also note: An attack taking 2^126.1 operations to break AES-128 is not 2^1.9 times faster than brute force; it's 2^0.9 times faster than brute force. A brute force search on a 128-bit key takes on average 2^127 operations. In short, this is definitely in the "interesting new method to explore" column rather than the "interesting attack" column.
- burgerbrain 15y ago
  "Note: This attack requires a large amount of RAM. They may have saved a few operations, but they increased the total cost by many orders of magnitude over a brute-force search because they need a larger machine." Is this terribly relevant though? Deep Crack was a quarter of a million dollars (90s dollars) as I recall.
  - kragen 15y ago
    It depends on whether "a large amount of RAM" means "a quarter of a million dollars' worth of RAM" or "an amount of RAM substantially larger than the Milky Way galaxy".
  - tptacek 15y ago
    Yes. The entire concept of cryptanalysis revolves around cost factors. It is very relevant when a new avenue of attack costs more than brute force in its best known mode of implementation. That doesn't make the research a dead end, but it further reduces the relevance of this work to engineers.
- tomp 15y ago
  I don't know the details of the attack, but the article says, "AES-128 is more like AES-126", so you should therefore need 2^125 operations in average, which is 4 times faster. On the other hand, I may be wrong... do you mind linking to the original source?
  - 15y ago
nikcub 15y ago
Does anybody remember or have a citation for the story about how the NSA made some recommended changes to Rijndael, but nobody understood them at the time? This was back in the mid-90s, during the AES/DES replacement assesment and competition period. It was then only years later that the NSA changes were understood to be strengthening the cypher against an attack type that was unknown to the public at the time, but that the NSA obviously knew about. I remember there were also suspicions that the NSA were attempting to weaken the algorithm, much as they did with DES. It was the case that the NSA were always 10-15 years ahead of the public in crypto (or even longer in terms of the discovery of public key crypto). I wonder if their old proposed changes to Rijndael have anything to do with this, or if they knew about this type of attack but still recommended AES. Apologies for being vague about the story - but I do remember those details. I can't recall where I heard about it.
- dchest 15y ago
  You're misremembering, twice. There was a story about mysterious S-boxes selected by NSA for DES http://en.wikipedia.org/wiki/Data_Encryption_Standard#NSA.27s_involvement_in_the_design http://en.wikipedia.org/wiki/Data_Encryption_Standard#NSA.27.... Those S-boxes turned out to be designed to resist differential attacks, which were only known to NSA at that time. This doesn't count as weakening at all. The difference between AES and Rijndael is only in that AES has a fixed block size of 128 bits and a key size of 128, 192, or 256 bits, whereas Rijndael can be specified with block and key sizes in any multiple of 32 bits, with a minimum of 128 bits and a maximum of 256 bits. (http://en.wikipedia.org/wiki/Advanced_Encryption_Standard#Description_of_the_cipher http://en.wikipedia.org/wiki/Advanced_Encryption_Standard#De...)
snorkel 15y ago
Don't panic yet. It still requires a trillion machines for billions of years to brute force.

155 points by fogus 15y ago

Paper and slides: http://research.microsoft.com/en-us/projects/cryptanalysis/aes.aspx http://research.microsoft.com/en-us/projects/cryptanalysis/a...

phillmv 15y ago
Ah! Novel cryptanalysis technique reduces practical AES key length by about 2 bits.
- eru 15y ago
  Which is quite an achievement.

seagaia 15y ago

Well, we certainly won't have to worry about it for now. But that doesn't mean we shouldn't worry about it, of course. It's a ways off in terms of orders of magnitude for how fast our computers now, and I don't think computers will be growing at that rate in terms of power unless new breakthroughs are found.

m0nastic 15y ago
The general rule of thumb for cryptanalysis attacks is that they become cheaper over time (usually quicker than initially proposed), which is why finding issues (even mathematical issues that aren't yet practical) is so important. Considering the length of time that it takes for new encryption standards to be proposed and accepted, it's important to try and stay ahead of the curve.
sp332 15y ago
If you couldn't crack it before, you still can't crack it now. This attack only makes it 4 times easier to break, not even an order of magnitude.
- eru 15y ago
  If you count in binary, 2 bits are two orders of magnitude.
tptacek 15y ago
If you are using AES directly in your code, you should be very, very worried no matter what the research says, because you are vanishingly unlikely to have gotten it right. Use TLS or GPG.

deleted 15y ago

[deleted]

bonzoesc 15y ago

I guess once SHA-3 is done, NIST better start research on the next symmetric cipher. The attack only knocks off two bits now, but attacks only get better with time. Note that you should be using accepted standards for key management anyways. NIST believes that AES-128 has 128 bits of strength, and AES-256 has 256 bits of strength [1, page 63], which they find "Acceptable" until 2031 [1, page 65]; the catch is that any individual key should be expired after a few years. This is called a "cryptoperiod," and the longest they recommend using a key is five years [1, page 55]. By this standard, keep using AES-256, but change your keys every year, and be prepared to migrate to a new cipher at some point within the next decade or two. [1]: http://csrc.nist.gov/publications/drafts/800-57/Draft_SP800-57-Part1-Rev3_May2011.pdf http://csrc.nist.gov/publications/drafts/800-57/Draft_SP800-...

dchest 15y ago
Speaking of SHA-3, "biclique cryptanalysis was ﬁrst introduced for hash cryptanalysis". Here's an interesting quote from the paper regarding the relationship between attacks on block ciphers and hash functions: "... the block cipher standard AES is almost as secure as it was 10 years ago in the strongest and most practical model with a single unknown key. The former standard DES has not seen a major improvement since Matsui’s seminal paper in 1993. In contrast, the area of hash function cryptanalysis is growing quickly, encouraged by the cryptanalysis MD5, of SHA-0 and SHA-1, followed by a practical attack on protocols using MD5, preimage attacks on Tiger and MD5, etc. As differential cryptanalysis, a technique originally developed for ciphers, was carried over to hash function analysis, cryptanalysts are now looking for the opposite: a hash analysis method that would give new results on block ciphers."
tptacek 15y ago
The total cost to the industry of adopting AES was enormous. That implies that deprecating it would at present impose costs that far outweigh the benefits, because replacing AES will be expensive, and there are at present minimal practical benefits to doing so. Remember, plenty of critical systems have been fielded that rely on RC4 and DES-EDE, both of which are also (for all intents and purposes) unbroken in their most common usage. For Hacker News, the far more important thing to point out is that no matter what block cipher you use, you are never going to get burnt by research like this, but you are almost certain to be completely boned by implementation errors.

cperciva 15y ago

Note: This attack requires a large amount of RAM. They may have saved a few operations, but they increased the total cost by many orders of magnitude over a brute-force search because they need a larger machine. Also note: An attack taking 2^126.1 operations to break AES-128 is not 2^1.9 times faster than brute force; it's 2^0.9 times faster than brute force. A brute force search on a 128-bit key takes on average 2^127 operations. In short, this is definitely in the "interesting new method to explore" column rather than the "interesting attack" column.

burgerbrain 15y ago
"Note: This attack requires a large amount of RAM. They may have saved a few operations, but they increased the total cost by many orders of magnitude over a brute-force search because they need a larger machine." Is this terribly relevant though? Deep Crack was a quarter of a million dollars (90s dollars) as I recall.
- kragen 15y ago
  It depends on whether "a large amount of RAM" means "a quarter of a million dollars' worth of RAM" or "an amount of RAM substantially larger than the Milky Way galaxy".
- tptacek 15y ago
  Yes. The entire concept of cryptanalysis revolves around cost factors. It is very relevant when a new avenue of attack costs more than brute force in its best known mode of implementation. That doesn't make the research a dead end, but it further reduces the relevance of this work to engineers.
tomp 15y ago
I don't know the details of the attack, but the article says, "AES-128 is more like AES-126", so you should therefore need 2^125 operations in average, which is 4 times faster. On the other hand, I may be wrong... do you mind linking to the original source?
- 15y ago

nikcub 15y ago

Does anybody remember or have a citation for the story about how the NSA made some recommended changes to Rijndael, but nobody understood them at the time? This was back in the mid-90s, during the AES/DES replacement assesment and competition period. It was then only years later that the NSA changes were understood to be strengthening the cypher against an attack type that was unknown to the public at the time, but that the NSA obviously knew about. I remember there were also suspicions that the NSA were attempting to weaken the algorithm, much as they did with DES. It was the case that the NSA were always 10-15 years ahead of the public in crypto (or even longer in terms of the discovery of public key crypto). I wonder if their old proposed changes to Rijndael have anything to do with this, or if they knew about this type of attack but still recommended AES. Apologies for being vague about the story - but I do remember those details. I can't recall where I heard about it.

dchest 15y ago
You're misremembering, twice. There was a story about mysterious S-boxes selected by NSA for DES http://en.wikipedia.org/wiki/Data_Encryption_Standard#NSA.27s_involvement_in_the_design http://en.wikipedia.org/wiki/Data_Encryption_Standard#NSA.27.... Those S-boxes turned out to be designed to resist differential attacks, which were only known to NSA at that time. This doesn't count as weakening at all. The difference between AES and Rijndael is only in that AES has a fixed block size of 128 bits and a key size of 128, 192, or 256 bits, whereas Rijndael can be specified with block and key sizes in any multiple of 32 bits, with a minimum of 128 bits and a maximum of 256 bits. (http://en.wikipedia.org/wiki/Advanced_Encryption_Standard#Description_of_the_cipher http://en.wikipedia.org/wiki/Advanced_Encryption_Standard#De...)

snorkel 15y ago

Don't panic yet. It still requires a trillion machines for billions of years to brute force.