Re: More problems with hash functions
On Wed, 25 Aug 2004, Hal Finney wrote: Dan Carosone writes: My immediate (and not yet further considered) reaction to the description of Joux' method was that it might be defeated by something as simple as adding a block counter to the input each time. Right after the talk, Scott Fluhrer (I think it was) spoke up with several quick ideas for avoiding the attacks, some along these lines, some involving overlapping blocks, and so on. There was some rapid back-and-forth between him and Joux which I could not follow, Joux saying that these things could be dealt with, and Fluhrer finally seemed to agree. Nobody I spoke with afterwards had a simple fix. It seems like, for every obvious thing you can do to get around it, it can be rearranged and applied in a different way. And the less obvious things, which actually do work, are all CPU-expensive. One interesting idea which I came up with and haven't seen a way past yet is to XOR each block with a value computed from its sequence number, then compute the hash function on the blocks in a nonsequential order based on the plaintext of the blocks. In concrete terms, you have a message of n blocks, p1 through pn. you xor each block with a value computed by a nonlinear function from its sequence number to get q1 through qn. Now rearrange q1 through qn by imposing a total ordering on p1 through pn: for example if p4 sorted before p7, you put q4 in front of q7. Finally, you compute the hash value on the blocks q1 through qn in their new order. Now the attack doesn't work; collisions against individual blocks don't combine to produce a collision on the sequence because the colliding values wouldn't have been fed into the hash function in the same order as the actual blocks. Bear - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: More problems with hash functions
Bear writes: One interesting idea which I came up with and haven't seen a way past yet is to XOR each block with a value computed from its sequence number, then compute the hash function on the blocks in a nonsequential order based on the plaintext of the blocks. In concrete terms, you have a message of n blocks, p1 through pn. you xor each block with a value computed by a nonlinear function from its sequence number to get q1 through qn. Now rearrange q1 through qn by imposing a total ordering on p1 through pn: for example if p4 sorted before p7, you put q4 in front of q7. Finally, you compute the hash value on the blocks q1 through qn in their new order. This is an interesting idea, but it does not fully prevent the Joux attack. This is seen most obviously in the two block case, where your method can at most increase the attacker's work by a factor of 2. Joux shows how to find a 4-collision using 2*2^(n/2) work, while it should take 2^(3n/4) work. In the case of a 160 bit hash this is the difference between 2^81 and 2^120. Doubling the work to find the 4-collision will not do much to address this discrepency. Even in the more general case, where Joux puts k blocks together to generate 2^k multicollisions, I can see a way to attack your method, with an increase in the work by only a factor of k^2. The attacker could choose an ordering of the blocks ahead of time, and find collisions which preserve that order. Specifically, he can start searching for collisions in the first one, which WOLOG we will call q1. He can continue to search until he finds a collision which puts p1 into the first 1/k of block address space, which will guarantee that this block will sort first. This will increase his work by a factor of k^2 (because only 1/k of the time will he get lucky, for each of the two blocks in the collision). Then he can find a collision in q2 which puts p2 into the 2nd 1/k of block-address space, guaranteeing that p2 will sort as the second block. Again this increases the work by k^2. Proceeding down the line he produces a collision which leaves the blocks in his pre-chosen order, at a cost of k^2 more work. Joux shows that finding an 2^k collision takes k times the work to find a single block collision. Among other things he shows how this reduces the work to find a collision in the output of two independent n-bit hashes from 2^n to n*2^(n/2). Your approach effectively makes this (n^3)*2^(n/2) which is an improvement, but still not attaining the exponential security increase expected from ideal hash functions. Hal Finney - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: More problems with hash functions
On Wed, 25 Aug 2004, Hal Finney wrote: Bear writes: One interesting idea which I came up with and haven't seen a way past yet is to XOR each block with a value computed from its sequence number, then compute the hash function on the blocks in a nonsequential order based on the plaintext of the blocks. snip This is an interesting idea, but it does not fully prevent the Joux attack. snip The attacker could choose an ordering of the blocks ahead of time, and find collisions which preserve that order. snip Joux shows that finding an 2^k collision takes k times the work to find a single block collision. Among other things he shows how this reduces the work to find a collision in the output of two independent n-bit hashes from 2^n to n*2^(n/2). Your approach effectively makes this (n^3)*2^(n/2) which is an improvement, but still not attaining the exponential security increase expected from ideal hash functions. You are correct. Thank you for your quick and clear thought regarding the proposal. Increasing the attacker's work by a factor of n^2 where n is the number of blocks preserves the strength only where n^2 = (2^k)/2 where k is the block size. So, for a 160-bit hash, (2^k)/2 is 2^159, and that means the proposed method preserves nominal strength only for messages longer than 2^80 blocks. Which in practical terms will not happen; I don't think 2^80 bits of storage have yet been manufactured by all the computer hardware makers on earth. I guess I momentarily forgot that with a hash function the attacker has access to the plaintext and can therefore tell unambiguously the result of the permutation of the blocks. I'll continue to think about it. Maybe I'll come up with something better. Bear - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: HMAC?
Amir Herzberg wrote: Perry E. Metzger wrote: So the question now arises, is HMAC using any of the broken hash functions vulnerable? Considering that HMAC goal is `only` a MAC (shared key authentication), the existence of any collision is not very relevant to its use. But furthermore, what HMAC needs from the hash function is only that it will be hard to find collision when using an unknown, random key; clearly the current collisions are far off from this situation. So, finding specific collisions in the hash function should not cause too much worry about its use in HMAC. Of course, if this would lead to finding many collisions easily, including to messages with random prefixes, this could be more worrying... Hmmm ... if you could persuade your victim to use a key that was known to be a suitable prefix for finding collisions... 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: HMAC?
From: Ben Laurie [EMAIL PROTECTED] Sent: Aug 26, 2004 7:41 AM To: Amir Herzberg [EMAIL PROTECTED] Cc: Perry E. Metzger [EMAIL PROTECTED], [EMAIL PROTECTED] Subject: Re: HMAC? Amir Herzberg wrote: So, finding specific collisions in the hash function should not cause too much worry about its use in HMAC. Of course, if this would lead to finding many collisions easily, including to messages with random prefixes, this could be more worrying... Hmmm ... if you could persuade your victim to use a key that was known to be a suitable prefix for finding collisions... The big question is what the probability is of getting a successful colliding message pair when you have complete control over the message, but don't know the IV. For repeated queries, you can know it's always the *same* IV, if that helps, just not what it is. I don't think we can know that until we've seen the full explanation in the Wang, et. al. paper, which hasn't been released yet. --John Kelsey - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: How thorough are the hash breaks, anyway?
On Thu, 26 Aug 2004, Trei, Peter wrote: While any weakness is a concern, and I'm not going to use any of the compromised algorithms in new systems, this type of break seems to be of limited utility. It allows you (if you're fortunate) to modify a signed message and have the signature still check out. However, if you don't know the original plaintext it does not seem to allow you construct a second message with the same hash. The Wikipedia article on hashes is pretty good on this topic: http://en.wikipedia.org/wiki/Cryptographic_hash_function So far, we know that the affected hashes are not collision resistant. They may still be at least somewhat one way and second preimage resistant, in which case systems which only require those properties might still be safe. But any system which specifies a secure hash in the general sense would have to come under very close scrutiny to see if it makes any assumptions at all about collision resistance. -J - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: titles
At 12:34 AM 8/27/04 +0100, Ian Grigg wrote: David Honig wrote: Security Engineer, according to Schneier... I don't like that term for 3 reasons: firstly, when we build stuff, security should be top-to-bottom, integrated in, and not seen as an add-on, an after-thought. That is, the overall engineer should build in the security as required from the beginning, so it is a skill that all need, and not something thrown over the wall to the guy with security in his title. It should be, but usually isn't. In fact, the security dude often has to make recommendations out of his prescribed niche, to others. Often on a project which is already under way. E.g., I recently contracted to implement a crypto protocol. When I suggested that, if a pad of paper be provided for folks to write their passphrases down, it be a single glass-backed sheet (lest impressions be taken), much laughter ensued. But if its worth encrypting, it must be interesting, right? Secondly, anything to do with security has a very strong hype-to-value ratio, so much so that it's quite hard to find a security company selling good security stuff. Security is much more than crypto, I've learned, so I don't have a problem with the word. Security includes human and physical security, and although they're not cool comp sci or math, they are vital. Crypto being fairly refined, its not the weakest link any more. And a 'security' mindset (being able to think like the adversary, much like in tic-tac-toe or chess) is important, but not so common. Its not like things titled crypto aren't often marianated in snake oil... :-) Thirdly, good security engineering, as it should be done, doesn't necessarily involve crypto. The art is in using as little crypto as possible - in precise and well placed doses. IMHO. Yes. Applications can't be any more secure than their operating system. -Bram Cohen Oftentimes, however, security engineers start from the pov that crypto is a hammer, and their job is to go find a nail to encrypt. I'll admit to this tunnel vision when I started my interest, over a decade ago when I learned how the IP worked and got into dissecting crypto algorithms to find the magic. Since then I've learned that other things are more important to understand; crypto components are just black boxes to an engineer, like a sorting routine or the like. Cryptoplumber is cute, in a self-depreciating way, but its all engineering, albeit less mature than say civil engineering, which stopped building bridges that collapse some time ago. The ultimate in paranoia is not when everyone is against you but when everything is against you. --PKD = 36 Laurelwood Dr Irvine CA 92620-1299 VOX: (714) 544-9727 (home) mnemonic: P1G JIG WRAP ICBM: -117.7621, 33.7275 HTTP: http://68.5.216.23:81 (back up, but not 99.999% reliable) PGP PUBLIC KEY: by arrangement Send plain ASCII text not HTML lest ye be misquoted -- Don't 'sir' me, young man, you have no idea who you're dealing with Tommy Lee Jones, MIB No, you're not 'tripping', that is an emu ---Hank R. Hill - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
