Re: Propping up SHA-1 (or MD5)
If it's just HMAC with K = h(m) then it's currently (or just recently) been discussed on cfrg: http://www.irtf.org/cfrg/, starting here: http://www1.ietf.org/mail-archive/web/cfrg/current/msg00708.html. -- Michael On Mon, 21 Mar 2005 11:56:44 +, Ben Laurie [EMAIL PROTECTED] wrote: It was suggested at the SAAG meeting at the Minneapolis IETF that a way to deal with weakness in hash functions was to create a new hash function from the old like so: H'(x)=Random || H(Random || x) However, this allows an attacker to play with Random (the advice I've seen is that if one is going to use an IV with a hash function, then one should transfer the IV with integrity checks to deny attackers this freedom). Another objection is that this construction changes the API at the sender end, which could lead to a great deal of complexity when the use of the hash API is deeply embedded. A third is that the length of the hash is changed, which could break existing protocols. Musing on these points, I wondered about the construction: H'(x)=H(H(x) || H(H(x) || x)) which doesn't allow an attacker any choice, doesn't change APIs and doesn't change the length of the hash. Does this have any merit? Note that this is essentially an HMAC where the key is H(x). I omitted the padding because it seems to me that this actually makes HMAC weaker against the current attacks. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Propping up SHA-1 (or MD5)
Ben Laurie writes: It was suggested at the SAAG meeting at the Minneapolis IETF that a way to deal with weakness in hash functions was to create a new hash function from the old like so: H'(x)=Random || H(Random || x) Yes. Suppose we use this for signing. The crucial part is to have the *signer* choose the Random value when computing the signature. This may be secure even if H fails to be collision-resistant, because even if an attacker finds a collision for H, he doesn't know which Random value the signer is going to use. More generally, we could try to use any universal one-way hash function (UOWHF). This concept is also known as target collision resistant (TCR). It is natural to conjecture that H' is a UOWHF, i.e., is TCR, and this may be true even if H is not collision-resistant. Of course, there is no proof of this, and this conjecture is speculative, but it does weaken the assumptions we are making about our hash. I have been advocating this kind of construction ever since hearing about the hash cryptanalysis results last August. Not everyone agrees with me, and there is a lengthy discussion going on about this on the IRTF CFRG working group. http://www1.ietf.org/mail-archive/web/cfrg/current/threads.html http://www1.ietf.org/mail-archive/web/cfrg/current/thrd2.html http://www1.ietf.org/mail-archive/web/cfrg/current/thrd3.html However, this allows an attacker to play with Random (the advice I've seen is that if one is going to use an IV with a hash function, then one should transfer the IV with integrity checks to deny attackers this freedom). No, not if you use it right. The way to use this is to have the signer choose the value of Random, not anyone else. A signer can play with Random and maybe find collisions M,M', but in this case the signer will be viewed as having signed both M and M', so this doesn't help the signer at all. Another objection is that this construction changes the API at the sender end, which could lead to a great deal of complexity when the use of the hash API is deeply embedded. Shouldn't be a big deal for signing. A much bigger deal is that this changes the on-the-wire format. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Propping up SHA-1 (or MD5)
Dan Kaminsky wrote: Ben, x can equal either test vector released by Wang, and H(x) will be identical. With H(x) identical, the rest of the HMAC stays identical too. This does not appear to be correct - in my construction, i.e. without padding, then the fact that x and x' differ means that the first blocks are different, but not the colliding kind of different (since the first blocks will be 20 bytes of H(x) and blocksize-20 bytes of x or x' [or, to be pedantic, the first 20 bytes of the next block will be different]). Even if padding were included, x and x' would still not collide, because the chaining values would not be as needed at the start of the second block. As a couple people pointed out, it's OK that HMAC is vulnerable to the Wang attack, since in order to execute the attack the key is required (and like AES, if the key is compromised, all bets are off). But you're not using HMAC as a MAC; you're using it to prop up a broken hash. Regarding the Random appendage, people don't seem to realize how important syncronized initial states are to many hashing algorithms. One of the major uses of a hashing algorithm is to act as an *exchangable* handle to data, in other words, you and I can both hash our respective datasets and see if they're identical. If we're each using different initial states, that process fails utterly. Obviously. But I don't understand your point. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [saag] Propping up SHA-1 (or MD5)
Nicolas Williams wrote: On Mon, Mar 21, 2005 at 11:56:44AM +, Ben Laurie wrote: It was suggested at the SAAG meeting at the Minneapolis IETF that a way to deal with weakness in hash functions was to create a new hash function from the old like so: H'(x)=Random || H(Random || x) Eric proposed sending Random, Signature(H(Random || M)) and I then proposed sending Random || Signature(H(Random || M)) to avoid having to add a slot in existing protocols for Random. Another alternative: send Random-Key || Signature(HMAC(H(), Random-Key, M). However, this allows an attacker to play with Random (the advice I've seen is that if one is going to use an IV with a hash function, then one should transfer the IV with integrity checks to deny attackers this freedom). This proposal is specific to the use of hashes in signatures. Another objection is that this construction changes the API at the sender end, which could lead to a great deal of complexity when the use of the hash API is deeply embedded. Yes. A third is that the length of the hash is changed, which could break existing protocols. Tie this to new algorithm OIDs and this problem goes away. You still have to figure out how to deploy new software. Musing on these points, I wondered about the construction: H'(x)=H(H(x) || H(H(x) || x)) Note that this is not on-line. which doesn't allow an attacker any choice, doesn't change APIs and doesn't change the length of the hash. Does this have any merit? Note that this is essentially an HMAC where the key is H(x). I omitted the padding because it seems to me that this actually makes HMAC weaker against the current attacks. Yes. Now that we know that the attack is a differential cryptanalysis where the attacker has to control the first pair of blocks of the original message anything that makes it hard for the attacker to do this helps. H'(x) = H(H(x))) might do that trick, and on-line, but surely there's problems with that too (IANAC). This construction cannot solve the problem since H(x)=H(x') = H(H(x))=H(H(x')). Note that the attack implies that there exist weak messages, and Wang et. al. explicitly mention this in the paper on breaking MD4, and they mention the use of weak messages in second pre-image computation -- if a given message begins with a weak block pair then you can construct second pre-images. It'd be nice to know what the weak message distribution is for MD5 and SHA-1... Wouldn't it? -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [saag] Re: Propping up SHA-1 (or MD5)
Ken Raeburn wrote: On Mar 22, 2005, at 11:51, Ben Laurie wrote: This can be fixed quite easily: H'(x)=H(H(x || H(x)) || H(x)) Doesn't this take us back to the original problem, by factoring in x only at the start of hash computations, so H'(x') will generate the same H(x') and the same internal state for H(x'||...) as for H(x||...) and thus the same H(x'||H(x')) etc, resulting in the same final value? Doh. Yes. Slightly less elegantly, then: H'(x)=H(H(x || H(0 || x) || H(0 || x)) Then you need two hashes running in parallel, but at least it is still online. Or, with three parallel streams: H'(x)=H(H(x || H(0 || x) || H(1 || x)) I don't feel as comfortable with either as the original construction, though. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [saag] Propping up SHA-1 (or MD5)
Nicolas Williams wrote: On Tue, Mar 22, 2005 at 05:31:44PM +, Ben Laurie wrote: Nicolas Williams wrote: Now that we know that the attack is a differential cryptanalysis where the attacker has to control the first pair of blocks of the original message anything that makes it hard for the attacker to do this helps. H'(x) = H(H(x))) might do that trick, and on-line, but surely there's problems with that too (IANAC). This construction cannot solve the problem since H(x)=H(x') = H(H(x))=H(H(x')). But it changes the attacker's problem. Currently the attacker has to find a first block of a weak message, then find the second block of the same, then he can generate collisions at will. The weak message generation requires some effort, and surely -- huge assumption here -- it takes more effort to find a weak message whose hash is also a weak message. The hash does not need to be weak, since the two hashes are the same, and so their hashes are also the same. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: Propping up SHA-1 (or MD5)
All hash functions I'm aware of consist of an inner compression function that hashes a fixed size block of data into a smaller fixed size block and an outer composition function that applies the inner function iteratively to the variable length data to be hashed. Essentially you're proposing a modification to the outer layer of the hash construction. All of the standard hash functions since MD4 have been constructed so that a collision in the inner compression function is likely to lead to a collision in the hash function. MD2 did not have that property. It computed a cheap checksum of the variable length data in parallel with the digesting process and digested the checksum following the data. I have often wondered whether such a cheap addition would strengthen the newer hashes. (It would fix the suffixing attacks that motivated the development of HMAC). It's not obvious whether this would make the functions more secure or just make them harder to analyze. Perhaps someone from the research community could comment on why the checksum was removed in the evolution from MD2 to MD4. Your proposed encoding has the disadvantage that it would require two passes over the message being digested. This would be bad news for hardware implementations and should be avoided if possible. You note with the construction: H'(x)=Random || H(Random || x) (reminiscent of the salted hash calculation for UNIX passwords) that the hash gets longer. The hash need not get longer. If you have 40 random bits and the first 120 bits of H(Random || x), you match the size of SHA-1 and get improved security against most practical attacks. If your system depends on a fixed length hash, you're in trouble already because the fixed length is probably 128 bits and the world is headed toward 256. A problem that does exist with this construction is that some uses of hash functions assume that if you hash the same data you get the same hash (or indirectly, that if you sign the same data you get the same signature). In particular, you now need separate functions for generating a hash and for checking one. --Charlie Kaufman -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Ben Laurie Sent: Monday, March 21, 2005 3:57 AM To: Cryptography; [EMAIL PROTECTED] Subject: Propping up SHA-1 (or MD5) It was suggested at the SAAG meeting at the Minneapolis IETF that a way to deal with weakness in hash functions was to create a new hash function from the old like so: H'(x)=Random || H(Random || x) However, this allows an attacker to play with Random (the advice I've seen is that if one is going to use an IV with a hash function, then one should transfer the IV with integrity checks to deny attackers this freedom). Another objection is that this construction changes the API at the sender end, which could lead to a great deal of complexity when the use of the hash API is deeply embedded. A third is that the length of the hash is changed, which could break existing protocols. Musing on these points, I wondered about the construction: H'(x)=H(H(x) || H(H(x) || x)) which doesn't allow an attacker any choice, doesn't change APIs and doesn't change the length of the hash. Does this have any merit? Note that this is essentially an HMAC where the key is H(x). I omitted the padding because it seems to me that this actually makes HMAC weaker against the current attacks. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Propping up SHA-1 (or MD5)
Charlie Kaufman wrote: All hash functions I'm aware of consist of an inner compression function that hashes a fixed size block of data into a smaller fixed size block and an outer composition function that applies the inner function iteratively to the variable length data to be hashed. Essentially you're proposing a modification to the outer layer of the hash construction. All of the standard hash functions since MD4 have been constructed so that a collision in the inner compression function is likely to lead to a collision in the hash function. MD2 did not have that property. It computed a cheap checksum of the variable length data in parallel with the digesting process and digested the checksum following the data. I have often wondered whether such a cheap addition would strengthen the newer hashes. (It would fix the suffixing attacks that motivated the development of HMAC). It's not obvious whether this would make the functions more secure or just make them harder to analyze. Perhaps someone from the research community could comment on why the checksum was removed in the evolution from MD2 to MD4. Your proposed encoding has the disadvantage that it would require two passes over the message being digested. This would be bad news for hardware implementations and should be avoided if possible. I suggested in a later version these two constructions: H'(x)=H(H(x || H(0 || x) || H(0 || x)) or: H'(x)=H(H(x || H(0 || x) || H(1 || x)) which only require a single pass (but, unfortunately, two or three different instances of the hash). This seems similar to the mechanism used in MD2, except the checksum is expensive. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [saag] Re: Propping up SHA-1 (or MD5)
Blumenthal, Uri wrote: Ernie Brickell suggested the following construct: H'(x) = H( H(x) || H(0 || x) ) Like him, I see no reason in going (H(x) || H(0||x) || ... || H(n||x)). Sorry, I got my parentheses wrong. I meant... H'(x)=H(H(x || H(0 || x)) || H(0 || x)) or: H'(x)=H(H(x || H(0 || x)) || H(1 || x)) the former being almost the same construction as suggested, except that H(0 || x) is appended to the first inner hash. I used this construction because nested keyed hashes have provable security properties (which is why HMAC is made the way it is). The second form is the one required to get those properties, I should point out. I will confess that I have punted on whether those properties are actually useful. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: Propping up SHA-1 (or MD5)
Whether these various tricks help depends on the technical details of the attacks found. I hope that the bit twiddling crypto types who are finding the attacks are going to propose something to fix them. There are probably cheaper fixes than the 2x or 3x performance loss of your algorithm down in the inner loops of these algorithms (such as the change from SHA to SHA-1) and that these will come out. I'm reluctant to jump on the SHA-256 bandwagon or to come up with some ad hoc fix until a more thorough analysis is done. SHA-256 was designed before these attacks were known and probably has related flaws (though they are even less likely to be practically exploitable). We have the luxury of having the current break being largely theoretical, so waiting even a year for the mathematicians is probably OK. But it's never too early to start preparing for a new algorithm - perhaps with a new hash size - in our protocols. Further, given that lots of attacks (past and present) are not exploitable if every hashed quantity includes some value chosen by a trusted party and unpredictable by an attacker, it seems reasonable to consider that as a desirable characteristic as we design our protocols. --Charlie Kaufman p.s. Your formulae below have unbalanced parentheses, but I can guess what you probably meant. -Original Message- From: Ben Laurie [mailto:[EMAIL PROTECTED] Sent: Thursday, March 24, 2005 2:39 AM To: Charlie Kaufman Cc: Cryptography; [EMAIL PROTECTED] Subject: Re: Propping up SHA-1 (or MD5) Charlie Kaufman wrote: All hash functions I'm aware of consist of an inner compression function that hashes a fixed size block of data into a smaller fixed size block and an outer composition function that applies the inner function iteratively to the variable length data to be hashed. Essentially you're proposing a modification to the outer layer of the hash construction. All of the standard hash functions since MD4 have been constructed so that a collision in the inner compression function is likely to lead to a collision in the hash function. MD2 did not have that property. It computed a cheap checksum of the variable length data in parallel with the digesting process and digested the checksum following the data. I have often wondered whether such a cheap addition would strengthen the newer hashes. (It would fix the suffixing attacks that motivated the development of HMAC). It's not obvious whether this would make the functions more secure or just make them harder to analyze. Perhaps someone from the research community could comment on why the checksum was removed in the evolution from MD2 to MD4. Your proposed encoding has the disadvantage that it would require two passes over the message being digested. This would be bad news for hardware implementations and should be avoided if possible. I suggested in a later version these two constructions: H'(x)=H(H(x || H(0 || x) || H(0 || x)) or: H'(x)=H(H(x || H(0 || x) || H(1 || x)) which only require a single pass (but, unfortunately, two or three different instances of the hash). This seems similar to the mechanism used in MD2, except the checksum is expensive. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: Propping up SHA-1 (or MD5)
Ben, I believe the fatal flaw here is not the crypto, but losing the ability to hash a stream without keeping all of it. Both the hashes and HMAC have this sometimes-vital property. This can be fixed quite easily: H'(x)=H(H(x || H(x)) || H(x)) I think this construction doesn't provide any additional security. If someone manages to find x1 and x2 such that H(x1)=H(x2), he will have also broken H'(X). If you get h=H(x1)=H(x2) (of course we are talking about hash functions using the same iterative model as SHA-1), then you would end calculating H(H(x1 || h) || h) vs H(H(x2 || h) || h), but since both x1 and x2 leave the internal state of the hash function the same, H(x1 || h) = H(x2 || h) and hence H'(x1) = H'(x2) Cheers, Pablo - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Propping up SHA-1 (or MD5)
It was suggested at the SAAG meeting at the Minneapolis IETF that a way to deal with weakness in hash functions was to create a new hash function from the old like so: H'(x)=Random || H(Random || x) However, this allows an attacker to play with Random (the advice I've seen is that if one is going to use an IV with a hash function, then one should transfer the IV with integrity checks to deny attackers this freedom). Another objection is that this construction changes the API at the sender end, which could lead to a great deal of complexity when the use of the hash API is deeply embedded. A third is that the length of the hash is changed, which could break existing protocols. Musing on these points, I wondered about the construction: H'(x)=H(H(x) || H(H(x) || x)) which doesn't allow an attacker any choice, doesn't change APIs and doesn't change the length of the hash. Does this have any merit? Note that this is essentially an HMAC where the key is H(x). I omitted the padding because it seems to me that this actually makes HMAC weaker against the current attacks. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit. - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
