Re: attack against AES-256 with complexity 2^119
On 8/7/09 19:52, Eddy Nigg wrote: On 07/08/2009 08:35 PM, Paul Hoffman: At 8:08 PM +0300 7/8/09, Eddy Nigg wrote: Funny that today it's better to use AES-128. Why do you say that? It's the opposite of what the people who wrote the paper say. I've not read it today, but IIRC AES-128 remained 2^128 because the attack doesn't work on AES-128? Although I haven't read it at all, normally what happens is that the strength of an algorithm of X bits is X/2. So the strength of AES 256 is 128, and this attack suggests they can drop it down 9 bits to 119. For cryptographers that is a significant issue, but for the rest of us, not, because AES was built with substantial surplus. (Alternatively, if it was 256 - 119, then that would cause a revolution in affairs. But I feel we can rule that out simply by observing the lack of panic in the cryptographic community.) iang -- dev-tech-crypto mailing list dev-tech-crypto@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-tech-crypto
Re: attack against AES-256 with complexity 2^119
AFAIK, 2^119 is the worst-time complexity of the attack. Breaking a 256-bit key through a brute-force attack takes 2^256 operations in the worst case. The 'X/2' you are talking about is the average case, right? We are not looking for collisions here, so the birthday paradox doesn't apply... Best Regards, Peter Djalaliev -- dev-tech-crypto mailing list dev-tech-crypto@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-tech-crypto
Re: attack against AES-256 with complexity 2^119
On 9/7/09 17:33, Peter Djalaliev wrote: AFAIK, 2^119 is the worst-time complexity of the attack. Breaking a 256-bit key through a brute-force attack takes 2^256 operations in the worst case. The 'X/2' you are talking about is the average case, right? We are not looking for collisions here, so the birthday paradox doesn't apply... Yeah, I wondered about that too. So I skimmed their paper just now (no clues, just crypto bla bla) and found their faq: https://cryptolux.org/FAQ_on_the_attacks The weakness was discovered when we looked at AES as a hash function, and tried to find weaknesses that are specific for hash functions. We think that most cryptographers used only blockcipher-oriented techniques, against which AES was well protected by the designers. So as a hash, birthday paradox applies, and 2^119 should be compared to 2^128. (I guess.) Although they say careful things like the above, they are (typical of all cryptographers and all techies and all professions and also all children and all grandmamas and all ...) not being too careful to reduce the size and scope of the marketing around their product. They are not explaining very carefully how to interpret these numbers. They are allowing us to be hyper-impressed, potentially by making a mistake. In order to gain the maximum press, of course. This is their career, and no cryptographer will call them on it, because they all play the same game, because funding comes from publicity. The attack is still notable for cryptographic reasons. iang -- dev-tech-crypto mailing list dev-tech-crypto@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-tech-crypto
Re: attack against AES-256 with complexity 2^119
The weakness was discovered when we looked at AES as a hash function, and tried to find weaknesses that are specific for hash functions. We think that most cryptographers used only blockcipher-oriented techniques, against which AES was well protected by the designers. All this quote says, I think, is that they approached the algorithm using attacks normally applied against hash functions, while cryptanalysts used attacks normally used against block ciphers. So as a hash, birthday paradox applies, and 2^119 should be compared to 2^128. (I guess.) The attack is clearly to recover a key uses for AES-256 and not to find collisions. Since this is supposedly the first known attack against full AES-256 (other than brute force search), they would be comparing to 2^256. 2^119 should be the worst-case complexity, even though the authors do not say so. AFAIK, the convention in theory papers is to report worst-time complexity unless stated otherwise. This paper is currently submitted to a conference and not yet published. We'll see of the theory community verifies the authors' statements :) -- dev-tech-crypto mailing list dev-tech-crypto@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-tech-crypto
Re: attack against AES-256 with complexity 2^119
At 3:16 PM +0200 7/9/09, Ian G wrote: Although I haven't read it at all, normally what happens is that the strength of an algorithm of X bits is X/2. Say what!?! AES is an encryption function, not a hash function. AES-256 has a strength of 256 bits. -- dev-tech-crypto mailing list dev-tech-crypto@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-tech-crypto
attack against AES-256 with complexity 2^119
There has been an attack on the full AES-256 algorithm with space and time complexity of 2^119. Reportedly, the attack works on all keys. https://cryptolux.uni.lu/mediawiki/uploads/1/1a/Aes-192-256.pdf Bruce Schneier mentions this in his blog: http://www.schneier.com/blog/archives/2009/07/new_attack_on_a.html Some of the new SHA-3 algorithm candidates may be affected, too... Best Regards, Peter Djalaliev -- dev-tech-crypto mailing list dev-tech-crypto@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-tech-crypto
Re: attack against AES-256 with complexity 2^119
On 07/08/2009 08:03 PM, Peter Djalaliev: There has been an attack on the full AES-256 algorithm with space and time complexity of 2^119. Reportedly, the attack works on all keys. Funny that today it's better to use AES-128. -- Regards Signer: Eddy Nigg, StartCom Ltd. Jabber: start...@startcom.org Blog: https://blog.startcom.org -- dev-tech-crypto mailing list dev-tech-crypto@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-tech-crypto
Re: attack against AES-256 with complexity 2^119
At 8:08 PM +0300 7/8/09, Eddy Nigg wrote: On 07/08/2009 08:03 PM, Peter Djalaliev: There has been an attack on the full AES-256 algorithm with space and time complexity of 2^119. Reportedly, the attack works on all keys. The title of the paper (and the body, of course) says otherwise. Funny that today it's better to use AES-128. Why do you say that? It's the opposite of what the people who wrote the paper say. -- dev-tech-crypto mailing list dev-tech-crypto@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-tech-crypto
Re: attack against AES-256 with complexity 2^119
This is a related-key attack of only theoretical interest at the moment. It is believed that related-key attack are very hard to stage in applications like SSL/TLS. Some of the NIST SHA-3 candidates however, seem to use the input data (directly or indirectly) to get a key for AES. Hash algorithm input data may be related, which may make related-key attacks plausible against those SHA-3 candidates. The authors have not shown that the attack is effective against AES-128. However, in many real-world applications, such as TLS, AES-256 is still more secure than AES-128. Best Regards, Peter Djalaliev -- dev-tech-crypto mailing list dev-tech-crypto@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-tech-crypto
Re: attack against AES-256 with complexity 2^119
On 07/08/2009 08:35 PM, Paul Hoffman: At 8:08 PM +0300 7/8/09, Eddy Nigg wrote: Funny that today it's better to use AES-128. Why do you say that? It's the opposite of what the people who wrote the paper say. I've not read it today, but IIRC AES-128 remained 2^128 because the attack doesn't work on AES-128? -- Regards Signer: Eddy Nigg, StartCom Ltd. Jabber: start...@startcom.org Blog: https://blog.startcom.org -- dev-tech-crypto mailing list dev-tech-crypto@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-tech-crypto
