Re: Questions about generating keys (hash firewalls)
Oskar L. schrieb: No, in my example I used two, not one messages (pictures) and created permutations of both, and then compared both groups of hashes against each other. This appears to be somewhere in the middle between a birthday attack and a preimage attack. It looks like a preimage attack on a large set of preimages. Thinking it in the terms of the classical birthday paradoxon would mean to put men and women in a room and check all couples of both sexes for a matching birthday. I am not sure how many, but it definitely needs more people than checking for the same birthday within the whole group. NOT having a hash firewall would reduce the complexity of that attack by a constant factor: You can try all available hash functions to find the collision. This makes a difference in practice only if you can do the hash calculations in parallel (it doesn't really help you to try both SHA-1 and RIPEMD-160, if you could do two SHA-1 calculations in the same time). Thinking this in the classical setting again, it would mean to associate more than one date to each person, besides the birthdate (say, birthdate of boyfriend/girlfriend, etc). This appears to reduce the amount of needed persons in proportion to the number of dates that you associate to each (to keep the same number of dates/hashes available to compare). Given the complexities of the task of finding collisions in cryptography and the number of available hash functions, this reduction does not appear to be very significant. It makes mainly sense if you can actually substitute a weak hash function. cu, Sven ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Questions about generating keys (hash firewalls)
On Sun, 26 Aug 2007, Robert J. Hansen wrote: Doug Barton wrote: It almost sounds from what you're saying above that there actually is an argument for RSA's hash firewall being better than DSA[2] here, but if I correctly understood what you said later in the thread, the margin by which it's better is so small as to not be worth considering. Is that more or less correct? I think I was the one who made that argument and said the margin was ultimately not worth considering, so I hope you'll forgive me answering this one despite it being addressed to David. Of course, I appreciate the response. Anyway. Yeah, I think that's a fair assessment. Is there a benefit? Yes. Does the benefit matter? Not really. Or, as David said, if your property is surrounded by a 1000-foot fence, a 1001-foot fence is not going to be much better. If the bad guy can clear a 1000-foot fence, the additional foot probably isn't going to stop him. Ok, got it, thanks. Doug -- If you're never wrong, you're not trying hard enough ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Questions about generating keys (hash firewalls)
On Sat, 25 Aug 2007, Doug Barton wrote: The other question I had is about what you said above regarding truncating hashes with DSA2. Am I understanding correctly that even with DSA2 the hash size can be no larger than 160 bits? *sigh* Never mind this bit, I just re-re-read a later part of the thread where you said that it was possible to generate a DSA2 key that can use a full 256 bit hash. I'm still curious about the issue of whether the hash firewall issue makes a significant difference or not though. Doug -- If you're never wrong, you're not trying hard enough ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Questions about generating keys (hash firewalls)
Doug Barton wrote: It almost sounds from what you're saying above that there actually is an argument for RSA's hash firewall being better than DSA[2] here, but if I correctly understood what you said later in the thread, the margin by which it's better is so small as to not be worth considering. Is that more or less correct? I think I was the one who made that argument and said the margin was ultimately not worth considering, so I hope you'll forgive me answering this one despite it being addressed to David. Anyway. Yeah, I think that's a fair assessment. Is there a benefit? Yes. Does the benefit matter? Not really. Or, as David said, if your property is surrounded by a 1000-foot fence, a 1001-foot fence is not going to be much better. If the bad guy can clear a 1000-foot fence, the additional foot probably isn't going to stop him. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Questions about generating keys (hash firewalls)
Is there a comprehensive list of hashes used in encryption that can help me choose which is the best to use? ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Questions about generating keys (hash firewalls)
Allen Schultz wrote: Is there a comprehensive list of hashes used in encryption that can help me choose which is the best to use? If all you want is to provide a very high level of authentication for your messages, just stick with the defaults and you'll do just fine. Seriously. GnuPG is specifically designed so that the defaults are sensible for the overwhelming majority of users. There is no best hash. My usual metaphor is that arguments over the best hash function, the best key, the best encryption algorithm, etc., are about as meaningful as debating whether Godzilla or Mechagodzilla is more effective at flattening Tokyo. No matter which one you choose, Tokyo gets flattened. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Questions about generating keys (hash firewalls)
Allen Schultz wrote: Is there a comprehensive list of hashes used in encryption that can help me choose which is the best to use? I'm sure there is, but such a list would not do you much good. The application you use probably only supports a few. Some are old and insecure, and should not be used. I suggest you check what hashes your application supports, then read about them on Wikipedia. Here's a few: http://en.wikipedia.org/wiki/SHA1 http://en.wikipedia.org/wiki/RIPEMD160 http://en.wikipedia.org/wiki/WHIRLPOOL Oskar ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Questions about generating keys (hash firewalls)
On Fri, 24 Aug 2007 20:06, [EMAIL PROTECTED] said: Do hash firewalls have any drawbacks (performance decrease, difficult to implement, patent issues etc.)? What's the reason DSA doesn't have one? DSA ist the signature algorithm used with DSS, the Digital Signature Standard. DSS requires the use of DSA along with SHA-1 as the hash algorithms. Similar provisions have been setup for DSA1 i.e. the combination of certain key sizes with certain hash algorithms. Thus there is no need for the hash firewall. OpenPGP OTOH allows to use any suitable hash algorithms with DSA. Salam-Shalom, Werner -- Die Gedanken sind frei. Auschnahme regelt ein Bundeschgesetz. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Questions about generating keys (hash firewalls)
On Fri, Aug 24, 2007 at 09:06:24PM +0300, Oskar L. wrote: Do hash firewalls have any drawbacks (performance decrease, difficult to implement, patent issues etc.)? What's the reason DSA doesn't have one? I suspect a major reason is the main use of DSA is really DSS - and DSS was never intended to be used with any hash other than SHA-1. It gets a little stickier with DSA2/DSS2 where there are several possible hashes. For example, a 1024/160 DSA key can use SHA1, but also SHA224, SHA256, SHA384, or SHA512, by truncating them to 160 bits. David ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Questions about generating keys (hash firewalls)
Oskar L. wrote: So if we start with Bob, we need to have 253 more people, to be able to make 253 different pairs of which Bob is part of. We need 22 more people. In a room of 23 people, there are C(23, 2) different pairs, or 253. You should probably refresh your knowledge of combinatorics before talking about the birthday paradox. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Questions about generating keys (hash firewalls)
Robert J. Hansen wrote: In a room of 23 people, there are C(23, 2) different pairs, or 253. D'oh. This will teach me to read things quickly. Oskar was specifically saying pairs of which Bob was a part, not total pairs in the room. (gets out the brown paper bag) ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Questions about generating keys (hash firewalls)
Oskar L. wrote: calculators designed to show very large numbers can show the result. Now I compare all the hashes from one picture to all the hashes from the other. Doing a birthday attack is highly nontrivial. E.g., to do a birthday attack on SHA256 requires a minimum, a _minimum_, of over 10**17 joules to be liberated as heat. That's about as much as you'd get from an entire full-out strategic nuclear exchange between the US and Russia. You're talking global climate change at that point, along with potential mass extinction of humanity. It's not pretty. Do hash firewalls have any drawbacks (performance decrease, difficult to implement, patent issues etc.)? What's the reason DSA doesn't have one? Historical reasons. Nobody ever thought DSA would be used with anything other than SHA-1, so if there's only one approved hash function, there's no need for a hash firewall. DSS explicitly requires SHA-1 as a hash. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Questions about generating keys (hash firewalls)
Oskar L. wrote: I only meant to point out that a birthday attack would have a much better chance of finding a collision than a second preimage attack. I'm sorry if I made it sound trivial, I know it's not. I just tried to give an example of how it works that would be easy to understand. Well, except that your attack isn't a birthday attack. A birthday attack involves making a ton of different messages and checking _all_ messages created to find _any_ collision. Your attack involves taking one particular message and creating permutations of it, one after another, looking for a collision with your particular message. ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users
Re: Questions about generating keys (hash firewalls)
Well, except that your attack isn't a birthday attack. A birthday attack involves making a ton of different messages and checking _all_ messages created to find _any_ collision. Your attack involves taking one particular message and creating permutations of it, one after another, looking for a collision with your particular message. No, in my example I used two, not one messages (pictures) and created permutations of both, and then compared both groups of hashes against each other. Oskar ___ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users