Re: [Cfrg] HMAC-MD5
From: [EMAIL PROTECTED] Sent: Mar 30, 2006 3:38 PM To: cryptography@metzdowd.com Subject: Re: [Cfrg] HMAC-MD5 I think that we have the evidence. The security MD5 depends heavily on a lot of nonlinearities in functions F,G,I and on carries in arithmetic additions. Nonlinearities in F,G,I are bitwise and very weak. Carries are much stronger, but the collision attacks showed that it is possible to controll them also. The question is, can these still be controlled when the attacker doesn't know the internal state of the chaining variables? If not, we may end up with second preimage attacks (which would finish off MD5 for most hashing applications!), but still not know how to attack HMAC. The attack model is really different! For what it's worth, though, I agree that we need to get rid of MD5 anywhere it's still in place, since the only thing we know about its security is that it's a lot less than anyone expected it to be even a year ago. In fact, we should have started this when Dobbertin had his free-start collision result. If we had, we'd be able to regard the devastating MD5 collisions we're seeing now in the same way we regard devastating attacks on FEAL. (If someone extends the best attack on FEAL to 64 rounds, that will be cool, but nobody will be scrambling to replace FEAL in their products and protocols.) Vlastimil Klima --John Kelsey, NIST - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [Cfrg] HMAC-MD5
I (Hal Finney) wrote: A couple of (rather uninformed) thoughts regarding HMAC-MD5: First, how could collision attacks be extended to preimage attacks? And second, how would preimage attacks affect HMAC-MD5? I have to apologize for that message; I was totally confused particularly in the second part where I discussed the impact of an MD5 preimage break on HMAC-MD5. What I described was completely wrong and had nothing to do with an attack on HMAC-MD5. Luckily the message was so long and poorly written that hopefully few people were able to follow it well enough to be misled. Again, apologies. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [Cfrg] HMAC-MD5
I think that we have the evidence. The security MD5 depends heavily on a lot of nonlinearities in functions F,G,I and on carries in arithmetic additions. Nonlinearities in F,G,I are bitwise and very weak. Carries are much stronger, but the collision attacks showed that it is possible to controll them also. New differential schemes (paths) could be proposed, new ways of controlling the interior variables of MD5 could be discovered. It could lead to the second preimage attacks and maybe further. Vlastimil Klima - PŮVODNÍ ZPRÁVA - Od: Victor Duchovni [EMAIL PROTECTED] Komu: cryptography@metzdowd.com Předmět: Re: [Cfrg] HMAC-MD5 Datum: 29.3.2006 - 21:14:06 On Wed, Mar 29, 2006 at 10:51:08AM +0200, [EMAIL PROTECTED] wrote: In am nearly sure that a preimage attack (MD5) will be found in the next two or three years. Is there already evidence of progress in that direction? -- Viktor. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] -- ! NOVINKA ! Vybruslete z jarni unavy! Inline brusle Nike za fantasticke ceny od 1999 Kc! http://www.sportobchod.cz/Prehled.php?kat1=10 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [Cfrg] HMAC-MD5
I agree with Steven´s I'd rather avoid HMAC-MD5, just as a matter of future-proofing. And more. In am nearly sure that a preimage attack (MD5) will be found in the next two or three years. Vlastimil Klima http:/cryptography.hyperlink.cz - PŮVODNÍ ZPRÁVA - Od: Steven M. Bellovin [EMAIL PROTECTED] Komu: Russ Housley [EMAIL PROTECTED] Předmět: Re: [Cfrg] HMAC-MD5 Datum: 29.3.2006 - 1:11:25 On Tue, 28 Mar 2006 16:20:59 -0500, Russ Housley [EMAIL PROTECTED] wrote: At the SAAG session last week, Sam and I were asked about HMAC-MD5. Is it safe to keep using it? Should we encourage people to use HMAC-SHA1 or HMAC-SHA256 instead? Why? Please provide advice on this matter in the next two weeks. We have on working group that needs this advice very soon. There are no risks from HMAC-MD5 from collision attacks. Hash function design has suddenly become a very hot topic, though. Collision- finding attacks on MD5 have gotten a lot faster, and people are starting to look very hard at the basic design. I personally will not be surprised if a preimage attack is found in the next two or three years, in which case all bets are off. (I've made this statement before; others have disagreed with me on the likelihood of collision attacks.) I'd rather avoid HMAC-MD5, just as a matter of future-proofing. --Steven M. Bellovin, http://www.cs.columbia.edu/~smb ___ Cfrg mailing list [EMAIL PROTECTED] https://www1.ietf.org/mailman/listinfo/cfrg - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [Cfrg] HMAC-MD5
On Wed, Mar 29, 2006 at 10:51:08AM +0200, [EMAIL PROTECTED] wrote: In am nearly sure that a preimage attack (MD5) will be found in the next two or three years. Is there already evidence of progress in that direction? -- Viktor. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [Cfrg] HMAC-MD5
A couple of (rather uninformed) thoughts regarding HMAC-MD5: First, how could collision attacks be extended to preimage attacks? And second, how would preimage attacks affect HMAC-MD5? For a preimage attack, consider the simplest case, a single input block of 64 bytes. Then Hash = IV + Compress(IV,Input). We can try to run this backwards: Decompress(Hash-IV,Input). We need to choose Input such that the result of this backwards run equals IV, the fixed magic number that MD5 starts with. This is the hard part. One idea is to split the compression function into two halves: Compress1 and Compress2, such that Compress() = Compress2(Compress1()). Then Decompress, which is backwards, is Decompress1(Decompress2()). We could aim for a meet-in-the-middle attack, where we would run Compress1(IV,Input) and Decompress2(Hash-IV,Input) and try to get them to match. Then this value of Input would be a preimage of the desired Hash. The problem is that Input affects both Compress1 and Decompress2 in complicated ways. The solution would perhaps be to aim to find a family of Input values which caused only moderate changes to the outputs of Compress1 and Decompress2. This is similar to what happens now with the hash collision attacks. They find pairs of Inputs that have almost no change through the various sub-parts of the compression functions. If this could be extended so that there were not just a pair of Inputs, but larger numbers of them that produced almost-collisions after halfway through the compression function, then this could be a direction towards making this MITM work. At the most extreme case, if we could find 2^64 inputs which all collided through half the compression and half the decompression functions, then we'd have success, we'd have a preimage in 2^64 work. In practice we would not reach this extreme perfection, but perhaps we could approximate it enough that with much more work and good ideas, a preimage could still be found with substantially less than 2^128 work. As for the other question, the impact of preimages on HMAC-MD5: The goal of breaking a MAC is, given a bunch of known or chosen MAC'd inputs, but not knowing the MAC key, generate a valid MAC on a new input. Using preimages we would aim to generate an input which matched an output value we chose. The structure of HMAC is to hash one block (64 bytes) of the secret key xored a fixed repeated pad value, then the block(s) of the message. We take the output of that hash and do it again, hashing one block of the secret key xor a (different) fixed pad, then the output of the first hash. This is the HMAC. To reverse this, we would first need to invert the outer (second) hash. The tricky part here is that the input block (after the key) has a special form, consisting of the hash from the first step, padded per the MD5 spec. This padding will force fixed values (mostly zeros) into most of the input block and only give us 16 bytes to manipulate. So probably we would just fix the value from the input hash, fix the IV that results from hashing the outer key block, and find the output from this second block as the MAC value we will show an input for. Then we will turn our attention to the first block, which is key xor pad. We have its output value (the fixed intermediate IV we just chose) and so we would apply the inversion algorithm to find the input. This can be xored with the pad to get the key. Note that this is not the user's key, this is just a key that works for the outer hash. Now we do the inner hash. We use the key we found, xor with the appropriate fixed pad value, and hash to do the first block of the inner MD5. This gives us the IV for the second block, and we have the output for that block - it is the fixed value we chose above. We apply the inversion function again to get an Input value that works. Now we have succeeded: this Input value, along with the key we found in the first step, will produce the MAC we also found in the first step. It is not a MAC we have seen before so we have an official break. Therefore the ability to invert single blocks of MD5 will likely lead to an effective break of HMAC-MD5. Whether the current attacks against MD5 can be advanced to that point remains to be seen. If it works it will certainly be one of the premier cryptographic accomplishments of recent years. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
