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]
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: [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)
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)
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)
* Ben Laurie: > 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 Unfortunately, it does, in a rather fundamental way: streamed processing is no longer possible. - 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: Propping up SHA-1 (or MD5)
Barney Wolff wrote: On Mon, Mar 21, 2005 at 11:56:44AM +, Ben Laurie wrote: 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. 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)) 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)
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: 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]
Re: Propping up SHA-1 (or MD5)
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. 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. --Dan P.S. Your construction *will* work if you replace H(x) with H(x xor ipad) and H(x xor opad), with ipad and opad as defined in the HMAC spec. (We can collide against either permutation of our block data, but not both simultaneously.) This does end up rather significantly reducing throughput though. 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) > > 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. > - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
