Re: MD5 collisions found - alternative?
On Thu, Aug 26, 2004 at 01:04:21AM +0200, Almut Behrens wrote: > ...and I think somewhere in between lie hashing functions like crc32, > as used for detecting transmission errors, for example. Those are > not cryptographic, but possess a sufficiently large output space, so we > can expect few random collisions for most practical purposes. I wouldn't call CRC a hash code although you can use it that way I guess. It is really an error detecting and correction code that does have the ability, in a sense, to go backwards. It stands for Cyclic Redundancy Check. Such codes are redudant data, to be included with a transmission, not a hash. Some of them allow correction of multiple bit errors; typically you can detect 1 bit of error more than you can correct. > Right, but I believe that a uniform mapping _also_ is a desirable > property (besides speed, of course) of hashing functions as used to > compute table lookup indices -- as this property assures that the data > storage locations will be spread as evenly as possible across the > available buckets, which in turn minimizes the time spent on resolving > collisions (on average). And, as practical considerations in this case > always enforce a rather small output space (i.e. number of buckets) > we're certainly expecting collisions here. [1] Well, in theory yes. In practice you usually aren't much fussed if you've got a variance in the bucket utilization unless you're working on something with a real need for speed. For example, I would bet there are some really, really good uniform hash functions used inside of gcc. > > * randomness. Input strings which differ by 1 bit in any > > position generate hash keys a random distance apart > > I'd add: > * huge size of the output space (with its upper limit corresponding > to the number of bits of the hash value). The probability of > accidentally finding a collision is of course directly related to > the size of the output space (assuming a uniform mapping). Yes, can't argue there. That is where the basic difference between a typical hash function and a cryptographic hash comes. You want small keyspaces and very simple functions to generate lookup keys, whereas you don't much care about the function overhead for a cryptographic key as you tend not to do the encodings as often. > If anyone knows of any other requirements, please feel free to chime > in... Well, OTOH, this would probably be getting a little off-topic for > debian-security (especially the debian aspect). -- -- Dale Amon [EMAIL PROTECTED]+44-7802-188325 International linux systems consultancy Hardware & software system design, security and networking, systems programming and Admin "Have Laptop, Will Travel" -- signature.asc Description: Digital signature
Re: MD5 collisions found - alternative?
On Wed, Aug 25, 2004 at 10:01:25AM +0100, Dale Amon wrote: > On Wed, Aug 25, 2004 at 06:02:22AM +0200, Almut Behrens wrote: > > Somewhat more seriously: are there generally any defining criteria for > > something one would call a 'hash function', saying that it always must > > map some larger input space to some smaller output space? > > Yes. A hash function is any mapping function > > y = map(x) > > where the space y is smaller than the space x. Hashing (think of > cornbeef hash with things all chopped up into bits) is a technique > to generate fast lookup keys. The discussion here is about > cryptographic hash functions. I believe the primary difference is > that a cryptographic hash is: > > * a uniform mapping. For input space n and output space m, > there are on average n/m strings with the same hash key. > * randomness. Input strings which differ by 1 bit in any > position generate hash keys a random distance apart Add to that: * An output dependence on both the value and position of *every* input byte. Kind of implied by your second postulate, but worth mentioning explicitly. Especially when people think that a simple sum is cryptographically sound -- any combination of the input letters (or other matching combinations) will produce the same hash value. - Matt signature.asc Description: Digital signature
Re: MD5 collisions found - alternative?
On Wed, Aug 25, 2004 at 09:24:01AM -0400, Phillip Hofmeister wrote: > On Tue, 24 Aug 2004 at 06:18:50PM -0400, Matthew Palmer wrote: > > In the case of hashing algorithms, there's one 'key' involved -- the > > plaintext -- and for password security, you don't need to retrieve the key > > necessarily, just an equivalent one. There's no guarantee that XORing MD5 > > and SHA-1 isn't going to produce something that is quite simple to generate > > equivalent plaintext for, by, for example, making it mathematically > > impossible for one bit in the resultant hash value to be a certain value > > (because MD5 and SHA-1 always set the same bit to the same value given the > > same input). That cuts your hash search space in half right there. > > I agree. There is value in maintaining two completely different data > points by hashing the item with two functions though (but not XORing the > result together). For example: EVEN IF hash1(x) == hash1(y), it is > HIGHLY unlikely hash2(x) == hash2(y). Keeping a record of both hashes > on hand provides value and strengthens your certainty of integrity on > very large orders of magnitude. Indeed. Hence the crawling horror that is 'HMAC'... Holding multiple hashes is quite useful for avoiding collisions, and can help even if one hash is weak (so equivalent plaintext is easily found), but it can be tricky if one hash is found to be dangerously weak... - Matt signature.asc Description: Digital signature
Re: MD5 collisions found - alternative?
On Thu, 26 Aug 2004, Almut Behrens wrote: On Wed, Aug 25, 2004 at 01:15:13AM -0400, Hubert Chan wrote: ... So the only useful notion of oneway is that the hash is not easily invertible (i.e. you can't easily find some string that produces a given hash value). So, if you can somehow come up with an input string (except by brute force search), which computes to some given hash, that means you inverted the function, and it's thus not oneway -- nothing more and nothing less. It has nothing to do with whether there exists some theoretic backward mapping from output to input that would uniquely retrieve the string originally used to compute the hash. confirmed. for those who are interested in this topic, I can recommend the handbook of applied cryptography. the book's chapters are available for free download at http://www.cacr.math.uwaterloo.ca/hac/ chapter 9 focuses on cryptographic hash functions. the first chapter gives an excellent general overview of cryptographic aspects in human readable form. Thanks again everyone for taking the time. you are welcome, g. - expert in just too late deliveries and applied cryptography - mail: decockd:at:esat:dot:kuleuven:dot:ac:dot:be http://godot.be godot:at:advalvas:dot:be http://godot.studentenweb.org godot:at:godot:dot:be web: http://www.esat.kuleuven.ac.be/~decockd -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On Wed, Aug 25, 2004 at 01:15:13AM -0400, Hubert Chan wrote: > > Ah, but then using that definition of "oneway", every hash is oneway, > since there must always be some hash value corresponding to two > different input strings (assuming the input space is larger than the > output space, which is generally the case). Since every hash is oneway, > this renders the term meaningless. So the only useful notion of oneway > is that the hash is not easily invertible (i.e. you can't easily find > some string that produces a given hash value). Okay, I guess I finally got it. Thanks for the clarifications. Let me just rephrase it in my own words to make sure my updated understanding now matches the notion commonly held in cryptography circles. No need to respond unless you still find some flaws in it :) So, if you can somehow come up with an input string (except by brute force search), which computes to some given hash, that means you inverted the function, and it's thus not oneway -- nothing more and nothing less. It has nothing to do with whether there exists some theoretic backward mapping from output to input that would uniquely retrieve the string originally used to compute the hash. The crucial point here simply was my rather different conception of invertability. So, now, the addition operation I mentioned is clearly _not_ oneway, in contrast to what I proclaimed originally ;) Makes sense now -- and makes much of what's been said so far appear in a different light. (And it hopefully explains some of the objections I had, that presumably must have seemed a little weird to anyone with a 'cryptographic' mindset...) Thanks again everyone for taking the time. -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On Wed, Aug 25, 2004 at 10:01:25AM +0100, Dale Amon wrote: > > Hashing (think of cornbeef hash with things all chopped up into bits) > is a technique to generate fast lookup keys. The discussion here is > about cryptographic hash functions. ...and I think somewhere in between lie hashing functions like crc32, as used for detecting transmission errors, for example. Those are not cryptographic, but possess a sufficiently large output space, so we can expect few random collisions for most practical purposes. > I believe the primary difference is that a cryptographic hash is: > > * a uniform mapping. For input space n and output space m, > there are on average n/m strings with the same hash key. Right, but I believe that a uniform mapping _also_ is a desirable property (besides speed, of course) of hashing functions as used to compute table lookup indices -- as this property assures that the data storage locations will be spread as evenly as possible across the available buckets, which in turn minimizes the time spent on resolving collisions (on average). And, as practical considerations in this case always enforce a rather small output space (i.e. number of buckets) we're certainly expecting collisions here. [1] > * randomness. Input strings which differ by 1 bit in any > position generate hash keys a random distance apart I'd add: * huge size of the output space (with its upper limit corresponding to the number of bits of the hash value). The probability of accidentally finding a collision is of course directly related to the size of the output space (assuming a uniform mapping). I think those are the basic properties that allow for the two desirable features 'collision resistance' and 'onewayness', which we've been discussing in this thread -- but I guess I'm not really telling you anything new... ;) If anyone knows of any other requirements, please feel free to chime in... Well, OTOH, this would probably be getting a little off-topic for debian-security (especially the debian aspect). Almut [1] for anyone who doesn't know it already, I'd recommend Bob Jenkins page on hashing: http://burtleburtle.net/bob/hash/ -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On Tue, 24 Aug 2004 at 06:18:50PM -0400, Matthew Palmer wrote: > > If I understand your postulate correctly: > > > > If I, the user, encrypt a message with algorithm X and the cipher text > > is intercepted by the attacker. The attacker can make his chances of > > brute forcing the text BETTER by encrypting my cipher text with algorithm > > Y. This simply does not hold up. > > However, the weakness typically occurs when the same (or otherwise > equivalent or transformed) key is used for both algorithms. You don't so > much brute-force the text as the key in most attacks, and application of the > same (or equivalent) key multiple times often has the effect of weakening > the key's "secretness". This often occurs by being able to analyse the > resultant message and cutting out large swathes of keyspace to search based > on the properties of the ciphertext. Ahh...now we are talking apples to apples. Yes, the same key applied over different algorithms could create problems and provide easier crypt-analysis. I was under the impression we were talking about taking something and encrypting it with two different keys and two different algorithms. > So an attacker applying another algorithm after the fact, not knowing the > original key used (if he did, why would he need to break the ciphertext the > hard way?) is unlikely to make it any easier on himself. > > In the case of hashing algorithms, there's one 'key' involved -- the > plaintext -- and for password security, you don't need to retrieve the key > necessarily, just an equivalent one. There's no guarantee that XORing MD5 > and SHA-1 isn't going to produce something that is quite simple to generate > equivalent plaintext for, by, for example, making it mathematically > impossible for one bit in the resultant hash value to be a certain value > (because MD5 and SHA-1 always set the same bit to the same value given the > same input). That cuts your hash search space in half right there. I agree. There is value in maintaining two completely different data points by hashing the item with two functions though (but not XORing the result together). For example: EVEN IF hash1(x) == hash1(y), it is HIGHLY unlikely hash2(x) == hash2(y). Keeping a record of both hashes on hand provides value and strengthens your certainty of integrity on very large orders of magnitude. -- Phillip Hofmeister pgpLWjIwGrvEX.pgp Description: PGP signature
Re: MD5 collisions found - alternative?
On Wed, Aug 25, 2004 at 11:24:00AM +1000, Matthew Palmer wrote: I imagine that the garbage would be to bring the md5sum back to the original to hide the trojan, rather than "hey, look, I can stick garbage on the end of the .deb and still keep the same md5sum! whee!". Well, that's the part nobody's demonstrated. Mike Stone -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
* Quoting Matthew Palmer ([EMAIL PROTECTED]): > On Tue, Aug 24, 2004 at 09:11:34PM -0400, Michael Stone wrote: > > On Wed, Aug 25, 2004 at 12:39:57AM +0200, Rolf Kutz wrote: > > >This depends on how the attack really works. If > > >you just need to flip a few bits in a document it > > >might just look like typos (think crc32). If your > > >document is a tarball or a .deb you might be able > > >to insert a lot of "garbage" to it without being > > >noticed. > > > > Right, but is someone inserting garbage into a .deb really a threat? I'd > > be more concerned about the insertion of malicious code... > > I imagine that the garbage would be to bring the md5sum back to the original > to hide the trojan, rather than "hey, look, I can stick garbage on the end > of the .deb and still keep the same md5sum! whee!". Right! - Rolf -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On Wed, Aug 25, 2004 at 06:02:22AM +0200, Almut Behrens wrote: > Somewhat more seriously: are there generally any defining criteria for > something one would call a 'hash function', saying that it always must > map some larger input space to some smaller output space? Yes. A hash function is any mapping function y = map(x) where the space y is smaller than the space x. Hashing (think of cornbeef hash with things all chopped up into bits) is a technique to generate fast lookup keys. The discussion here is about cryptographic hash functions. I believe the primary difference is that a cryptographic hash is: * a uniform mapping. For input space n and output space m, there are on average n/m strings with the same hash key. * randomness. Input strings which differ by 1 bit in any position generate hash keys a random distance apart While these features are also useful in writing assembler and compilers, they are not *that* important. I've often used hash functions as simple as: "add the first 8 chars and take the low byte of the integer summand." Obviously not cryptographic. -- -- Dale Amon [EMAIL PROTECTED]+44-7802-188325 International linux systems consultancy Hardware & software system design, security and networking, systems programming and Admin "Have Laptop, Will Travel" -- -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
> "Almut" == Almut Behrens <[EMAIL PROTECTED]> writes: Almut> On Tue, Aug 24, 2004 at 11:09:39PM +0200, Danny De Cock wrote: [...] Danny> being able to invert a hash function clearly means that the Danny> function is not collision-resistant, Almut> does it? (presuming that retrieving that x from hash(x) is not Almut> considered 'finding a collision' -- there might not necessarily Almut> exist another input value with the same hash, after all) But there must exist some hash value that is mapped from multiple inputs. And most likely, most hash values would be mapped from multiple inputs. Of course finding a collision still involves some luck, but not nearly as much as if you didn't have an inverse. Basically, if you take a random string, hash it, and take the inverse, the odds are pretty low that the inverse is the same as the original string. If you repeat multiple times with different random initial strings, you'll be very unlucky to have to do that for a long time. Almut> On a related note, as hash functions typically are many-to-one Almut> type of mappings, how can they ever be inverted anyway? I assume it to mean: find any string for which the hash value is the same as the given hash value. The string does not have to be the same as the original. (Of course, any hash function is invertible by using brute force. So when Danny says "being able to invert a hash function", there's an implicit "efficiently" or "easily" in there.) [...] Almut> Let me just use a trivial example - the simple addition operation Almut> - to elaborate on my notions of 'onewayness' and 'collision Almut> resistance': When we add 2+3, we get 5. Great. :) That sum kind Almut> of represents the 'hash' or checksum. This operation is clearly Almut> not reversible (i.e. when only being given the 5, you can never Almut> tell for sure whether 2+3, 1+4, -13+18, etc. were being added Almut> up). Thus, it's 'oneway', as I understand the term. Ah, but then using that definition of "oneway", every hash is oneway, since there must always be some hash value corresponding to two different input strings (assuming the input space is larger than the output space, which is generally the case). Since every hash is oneway, this renders the term meaningless. So the only useful notion of oneway is that the hash is not easily invertible (i.e. you can't easily find some string that produces a given hash value). -- Hubert Chan <[EMAIL PROTECTED]> - http://www.uhoreg.ca/ PGP/GnuPG key: 1024D/124B61FA Fingerprint: 96C5 012F 5F74 A5F7 1FF7 5291 AF29 C719 124B 61FA Key available at wwwkeys.pgp.net. Encrypted e-mail preferred. -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On Tue, Aug 24, 2004 at 11:01:58PM +0200, Moritz Schulte wrote: > > (...) But if your hash function is pretty good in respect to > collision-resistance but is not one-way (being similar to a 1:1 > mapping between hash input and hash output), you could simply apply > the inverse function to your hash output and are already done. If that was possible for md5, it would be an ingenius compression algorithm, as you could sqeeze several hundred Megs or more into 128 bits, and still be able to retrieve the original data... ;) Somewhat more seriously: are there generally any defining criteria for something one would call a 'hash function', saying that it always must map some larger input space to some smaller output space? I'm thinking of something like the following: a trivial, reversible 1:1 mapping would be to simply rotate every ASCII value in a string by some N (e.g. 1->2, 2->3, ..., 255->1). That procedure would fit the above mentioned properties, in that it's perfectly reversible, and also pretty collision-resistant -- at least, from the top of my head, I couldn't think of any reason why there should be any two inputs mapping to the same output. But I don't think that that'd be considered a hash function... (BTW, I'm not making any claims whatsoever about its usefulness in the context of computing checksums, so please don't get me wrong there.) Anyway, it's 6 a.m. here, and I got to get some sleep now... so, I won't pester you any further :) Thanks everyone for the input! Almut -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On Wed, Aug 25, 2004 at 12:39:57AM +0200, Rolf Kutz wrote: > > If you can calculate a collision from the hash and > the known password, that would be a lack off > collision resistance. Is knowing the password really a prerequisite? I'd have said that if you can find a collision at all, or calculate a collision for a given hash, that would be lack of collision resistance... > > The difference between a hash for a signature and > a hash for a password is that you know the plain > text in the first case. Sure. But does it really make such a difference for finding a collision, if you know the plaintext, rather than its hash? The latter can always be computed trivially in the usual forward fashion. (Just asking out of curiosity, not to argue in any direction whatsoever...) > > documents, you'd probably have some very specific message in mind (at > > least not some random string) that you'd like to fake as originating > > from someone else. > > This depends on how the attack really works. If > you just need to flip a few bits in a document it > might just look like typos (think crc32). If your > document is a tarball or a .deb you might be able > to insert a lot of "garbage" to it without being > noticed. I agree, in general. OTOH, if you have something like a tar.gz file, I'd presume it's rather challenging to make some change to the content being packaged in such a way that both tar.gz's still have the same md5, same size -- and unpack without error. And even more challenging, if that change is supposed to achieve a certain predefined effect... ;) Almut -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On Tue, Aug 24, 2004 at 11:09:39PM +0200, Danny De Cock wrote: > >>for password schemes, it is important that the hash function used is > >>one-way: if one knows the password, it must be very simple/easy to > >>compute the hash of that password, but if someone obtained the hash of > >>a password, it must be very difficult to find something, say z, so that > >>hash(z) equals the hash of the password. > > > >but that's property 1 then (i.e. collision resistance), isn't it? > > not exactly the same, but it is true that the two properties are somehow > related: if you can find a z so that hash(z) equals hash(x), and x and z > are different, then you have found a collision, if not, you have inverted > the hash function. I totally agree so far. > being able to invert a hash function clearly means that the function is > not collision-resistant, does it? (presuming that retrieving that x from hash(x) is not considered 'finding a collision' -- there might not necessarily exist another input value with the same hash, after all) On a related note, as hash functions typically are many-to-one type of mappings, how can they ever be inverted anyway? > > summarizing: > an attack relying on the collision-resistance takes as > input two values x and y and results in an > output hash(x) which equals hash(y), but > an attack on the one-way property of the hash function takes as > input hash(x) and produces an > output z so that hash(z) equals hash(x). > > this is quite different, isn't it? :) hmm, well, I guess that's where our notions/terminology start to differ slightly... The main difference I see there is in the intent of the attacks, not so much in the property they're trying a attack (or the lack of a property the attack tries to exploit). The first type aims at finding some y for some given x, so that their hashes do not differ, but it's irrelevant what the specific hash value is. The second type starts from some given hash(x), and tries to find some z that yields the same hash (as in the password cracking case). But both types of attacks are based on the existence of collisions. Only trying to find that very x that originally produced hash(x) would be an attack on the one-way property, IMHO. I don't quite see why the second attack must have anything to do with the function being one-way or not: even if the function was perfectly one-way, but not collision-resistant, you might still find that z (z is not necessarily the inverse of hash(x) after all -- at least not as I understand the term... :) Let me just use a trivial example - the simple addition operation - to elaborate on my notions of 'onewayness' and 'collision resistance': When we add 2+3, we get 5. Great. :) That sum kind of represents the 'hash' or checksum. This operation is clearly not reversible (i.e. when only being given the 5, you can never tell for sure whether 2+3, 1+4, -13+18, etc. were being added up). Thus, it's 'oneway', as I understand the term. But it's more than trivial to come up with many, many pairs of input values adding up to the same sum. That's essentially what I thought is called 'finding a collision' -- leaving it entirely open whether this can generally be done for some given hash (sum), or only for some prior unknown hash... Anyhow, as open as my definitions currently are, just as open am I to adjust them as required :) I guess we're basically all having the same concepts in the back of our minds. We're just using different terminology (or the same terminology in different ways) to talk about them -- which is always an unfailing recipe for causing confusion... Almut -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On 25 Aug 2004, Matthew Palmer wrote: > On Tue, Aug 24, 2004 at 12:20:24PM -0400, Phillip Hofmeister wrote: >> On Tue, 24 Aug 2004 at 10:50:38AM -0400, Daniel Pittman wrote: >>> Be aware that this sort of technique "multi-encryption" technique can >>> lead to significant exposures when applied to traditional crypto; it can >>> produce results that allow a vastly simpler attack on the protected >>> information. >>> >>> I would not put my name to a recommendation about how to make a >>> cryptographic product or protocol "more secure" unless I had sufficient >>> background in the area to know the full implications of my recommended >>> actions. >> >> If I understand your postulate correctly: >> >> If I, the user, encrypt a message with algorithm X and the cipher text >> is intercepted by the attacker. The attacker can make his chances of >> brute forcing the text BETTER by encrypting my cipher text with algorithm >> Y. This simply does not hold up. > > For random values of X and Y, you are correct, there is no reason to assume > that you will get an easier time of it. However, there are plenty of > examples where (for instance) applying the same algorithm N times > does not produce N times the security, or even the same level of security. > The same adverse interaction occurs when you mix different algorithms. [...] > It's those sorts of tricky interactions (which aren't immediately obvious) > which I'm sure led Daniel to warn of the dangers of simplistic "security > upgrades". Matt is entirely correct in his statements - this is *precisely* the issue that I am concerned with. I cannot say that "SHA1(f) xor MD5(f)" is weaker or stronger than either of those two on their own, because I don't know cryptographic algorithm design well enough. It is very hard to design a good cryptographic algorithm, though, and even harder to build a useful cryptographic system around a good algorithm. To quote from memory, unless you happen to be Bruce Schneier you probably can't design a secure cryptographic system on the back of a napkin, and you are almost certainly better off not trying. :) Regards, Daniel -- Crying loud, you're crawling on the floor Just a beautiful baby, You're nothing more -- Switchblade Symphony, _Clown_ -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On Tue, Aug 24, 2004 at 09:11:34PM -0400, Michael Stone wrote: > On Wed, Aug 25, 2004 at 12:39:57AM +0200, Rolf Kutz wrote: > >This depends on how the attack really works. If > >you just need to flip a few bits in a document it > >might just look like typos (think crc32). If your > >document is a tarball or a .deb you might be able > >to insert a lot of "garbage" to it without being > >noticed. > > Right, but is someone inserting garbage into a .deb really a threat? I'd > be more concerned about the insertion of malicious code... I imagine that the garbage would be to bring the md5sum back to the original to hide the trojan, rather than "hey, look, I can stick garbage on the end of the .deb and still keep the same md5sum! whee!". - Matt signature.asc Description: Digital signature
Re: MD5 collisions found - alternative?
On Wed, Aug 25, 2004 at 12:39:57AM +0200, Rolf Kutz wrote: This depends on how the attack really works. If you just need to flip a few bits in a document it might just look like typos (think crc32). If your document is a tarball or a .deb you might be able to insert a lot of "garbage" to it without being noticed. Right, but is someone inserting garbage into a .deb really a threat? I'd be more concerned about the insertion of malicious code... Mike Stone -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
* Quoting Almut Behrens ([EMAIL PROTECTED]): > On Tue, Aug 24, 2004 at 09:18:46PM +0200, Danny De Cock wrote: > > > > a cryptographic hash function, such as md5, sha1, ripemd-160, to name the > > most commonly used cryptographic hash functions are constructed to have at > > least the following properties: > > > > 1. it is hard to find two distinct inputs to the hash function, say x and > > y, so that hash(x) equals hash(y) > > > > 2. they are one-way, i.e., it is hard to find the value x given hash(x) > > just to make sure we're using the same terminology: 1. is what I'd > consider collision resistance, whereas the oneway aspect (2.) refers to > the difficulty of retrieving the original string (x above) used in > computing the hash in the first place. ACK. > > for password schemes, it is important that the hash function used is > > one-way: if one knows the password, it must be very simple/easy to compute > > the hash of that password, but if someone obtained the hash of a password, > > it must be very difficult to find something, say z, so that hash(z) equals > > the hash of the password. > > but that's property 1 then (i.e. collision resistance), isn't it? > And that's essentially what I was trying to point out, as I don't think > that, WRT password verification, you'll ever need to know the original x. > It's completely sufficient to find some other password y, z, or > whatever, such that > > hash(some_password) == stored_hash > > where the stored/given hash has originally been computed as hash(x). > > Thus, I'd still say it's not the oneway aspect that matters here, but > rather the collision resistance of the hash function... If you can calculate the password from the hash it would be a flaw in the one way funktion. If you can calculate a collision from the hash and the known password, that would be a lack off collision resistance. > Of course, as Mike has already pointed out, it's a completely different > story whether you can find _any_ collision (for an arbitray hash > value), or a collision for some _given_ cryptographic hash value. The difference between a hash for a signature and a hash for a password is that you know the plain text in the first case. > > does this clarify things a bit more? :)) > > not so sure... :) -- i.e. I don't really see a huge conceptual > difference between two 'passwords' or 'documents' hashing to the same > value... See above. > Also, here again, as I tried to point out in my previous post, I'd say > that with finding passwords, you have more degrees of freedom. All But less knowledge. > that matters is that their hashes are identical, when you want to get > access -- the string itself is totally irrelevant. While with signing It has to meet certain criterias like being printable characters and having a certain length, but it doesn't have to have a meaning. > documents, you'd probably have some very specific message in mind (at > least not some random string) that you'd like to fake as originating > from someone else. This depends on how the attack really works. If you just need to flip a few bits in a document it might just look like typos (think crc32). If your document is a tarball or a .deb you might be able to insert a lot of "garbage" to it without being noticed. - Rolf -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On Wed, Aug 25, 2004 at 12:44:43AM +1000, Daniel Pittman wrote: > Also, while there are issues with those hash algorithms, I don't think > they are quite bad enough that there is a significant *immediate* risk > to my systems; the cost of breaking in through the detected collisions > is lower than the risk of a bad password, etc. I think you meant s/cost/risk/ there. And I thoroughly agree -- it still appears to be far easier to brute-force check the poor-password-space than it is to reverse-generate an equivalent plaintext given a random MD5 hash. - Matt signature.asc Description: Digital signature
Re: MD5 collisions found - alternative?
On Tue, Aug 24, 2004 at 12:20:24PM -0400, Phillip Hofmeister wrote: > On Tue, 24 Aug 2004 at 10:50:38AM -0400, Daniel Pittman wrote: > > Be aware that this sort of technique "multi-encryption" technique can > > lead to significant exposures when applied to traditional crypto; it can > > produce results that allow a vastly simpler attack on the protected > > information. > > > > I would not put my name to a recommendation about how to make a > > cryptographic product or protocol "more secure" unless I had sufficient > > background in the area to know the full implications of my recommended > > actions. > > If I understand your postulate correctly: > > If I, the user, encrypt a message with algorithm X and the cipher text > is intercepted by the attacker. The attacker can make his chances of > brute forcing the text BETTER by encrypting my cipher text with algorithm > Y. This simply does not hold up. For random values of X and Y, you are correct, there is no reason to assume that you will get an easier time of it. However, there are plenty of examples where (for instance) applying the same algorithm N times does not produce N times the security, or even the same level of security. The same adverse interaction occurs when you mix different algorithms. However, the weakness typically occurs when the same (or otherwise equivalent or transformed) key is used for both algorithms. You don't so much brute-force the text as the key in most attacks, and application of the same (or equivalent) key multiple times often has the effect of weakening the key's "secretness". This often occurs by being able to analyse the resultant message and cutting out large swathes of keyspace to search based on the properties of the ciphertext. So an attacker applying another algorithm after the fact, not knowing the original key used (if he did, why would he need to break the ciphertext the hard way?) is unlikely to make it any easier on himself. In the case of hashing algorithms, there's one 'key' involved -- the plaintext -- and for password security, you don't need to retrieve the key necessarily, just an equivalent one. There's no guarantee that XORing MD5 and SHA-1 isn't going to produce something that is quite simple to generate equivalent plaintext for, by, for example, making it mathematically impossible for one bit in the resultant hash value to be a certain value (because MD5 and SHA-1 always set the same bit to the same value given the same input). That cuts your hash search space in half right there. It's those sorts of tricky interactions (which aren't immediately obvious) which I'm sure led Daniel to warn of the dangers of simplistic "security upgrades". - Matt signature.asc Description: Digital signature
Re: MD5 collisions found - alternative?
On Tue, 24 Aug 2004, Almut Behrens wrote: On Tue, Aug 24, 2004 at 09:18:46PM +0200, Danny De Cock wrote: On Tue, 24 Aug 2004, Almut Behrens wrote: On Tue, Aug 24, 2004 at 12:44:53PM +0200, Danny De Cock wrote: (...) but the verification of password hashes, such as used in pam, rely on the hash function's oneway-feature rather than on its collision-resistance... a cryptographic hash function, such as md5, sha1, ripemd-160, to name the most commonly used cryptographic hash functions, are constructed to have at least the following properties: 1. it is hard to find two distinct inputs to the hash function, say x and y, so that hash(x) equals hash(y) 2. they are one-way, i.e., it is hard to find the value x given hash(x) just to make sure we're using the same terminology: 1. is what I'd consider collision resistance, whereas the oneway aspect (2.) refers to the difficulty of retrieving the original string (x above) used in computing the hash in the first place. confirmed. for password schemes, it is important that the hash function used is one-way: if one knows the password, it must be very simple/easy to compute the hash of that password, but if someone obtained the hash of a password, it must be very difficult to find something, say z, so that hash(z) equals the hash of the password. but that's property 1 then (i.e. collision resistance), isn't it? not exactly the same, but it is true that the two properties are somehow related: if you can find a z so that hash(z) equals hash(x), and x and z are different, then you have found a collision, if not, you have inverted the hash function. being able to invert a hash function clearly means that the function is not collision-resistant, but finding collisions does not mean that the hash function is not one-way :) summarizing: an attack relying on the collision-resistance takes as input two values x and y and results in an output hash(x) which equals hash(y), but an attack on the one-way property of the hash function takes as input hash(x) and produces an output z so that hash(z) equals hash(x). this is quite different, isn't it? :) And that's essentially what I was trying to point out, as I don't think that, WRT password verification, you'll ever need to know the original x. It's completely sufficient to find some other password y, z, or whatever, such that hash(some_password) == stored_hash where the stored/given hash has originally been computed as hash(x). this is true, but this relies on the one-way property of the hash function, not on its collision-resistance: in userid/password verification schemes, one is given an output of the hash function, namely hash(password), and even if there were a collision for the hash function, chances are slim that the password equals the particular input which produces the collision... the attack scenario is different... Thus, I'd still say it's not the oneway aspect that matters here, but rather the collision resistance of the hash function... Of course, as Mike has already pointed out, it's a completely different story whether you can find _any_ collision (for an arbitray hash value), or a collision for some _given_ cryptographic hash value. Otherwise, I hardly have any objections to what you wrote :) does this clarify things a bit more? :)) not so sure... :) -- i.e. I don't really see a huge conceptual difference between two 'passwords' or 'documents' hashing to the same value... there is a difference: the passwords are not directly fed to the hash function. they are first encoded/expanded to make them of the proper size (i.e., 512 bits) for the hash function. in what I said/wrote, `document' one might read `input block for the hash function' ];-) the attacks described in the papers referred to in the original post deal with input blocks which are crafted to produce a collision, and these input blocks can be preceded by any number of `document' content, so the attacks do not really apply to password-based schemes, but they do on documents... cu, g. Thanks, Almut -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED] -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On Tue, Aug 24, 2004 at 10:40:45PM +0200, Almut Behrens wrote: > > for password schemes, it is important that the hash function used is > > one-way: if one knows the password, it must be very simple/easy to compute > > the hash of that password, but if someone obtained the hash of a password, > > it must be very difficult to find something, say z, so that hash(z) equals > > the hash of the password. > > but that's property 1 then (i.e. collision resistance), isn't it? The one-way property of our hash function makes it difficult to *compute* a valid hash input (password) for a given hash output (password hash). If it was not one-way, you could apply the inverse of the hash function to the hash output to yield the hash input. If it would be easy to find collisions, you could construct a *new* hash input for a given hash output. > And that's essentially what I was trying to point out, as I don't think > that, WRT password verification, you'll ever need to know the original x. > It's completely sufficient to find some other password y, z, or > whatever, such that > > hash(some_password) == stored_hash > > where the stored/given hash has originally been computed as hash(x). You are right - you are referring to the finding of "some other password[s]". But if your hash function is pretty good in respect to collision-resistance but is not one-way (being similar to a 1:1 mapping between hash input and hash output), you could simply apply the inverse function to your hash output and are already done. Thanks, Moritz pgppSx7IqWsL3.pgp Description: PGP signature
Re: MD5 collisions found - alternative?
On Tue, Aug 24, 2004 at 09:18:46PM +0200, Danny De Cock wrote: > On Tue, 24 Aug 2004, Almut Behrens wrote: > > >On Tue, Aug 24, 2004 at 12:44:53PM +0200, Danny De Cock wrote: > >> > >>(...) but the verification of password hashes, such as used in pam, > >>rely on the hash function's oneway-feature rather than on its > >>collision-resistance... > > > >not sure I understand -- so, if someone would like to explain this > >aspect to the non-cryptographist, please go ahead :) > > a cryptographic hash function, such as md5, sha1, ripemd-160, to name the > most commonly used cryptographic hash functions are constructed to have at > least the following properties: > > 1. it is hard to find two distinct inputs to the hash function, say x and > y, so that hash(x) equals hash(y) > > 2. they are one-way, i.e., it is hard to find the value x given hash(x) just to make sure we're using the same terminology: 1. is what I'd consider collision resistance, whereas the oneway aspect (2.) refers to the difficulty of retrieving the original string (x above) used in computing the hash in the first place. > for password schemes, it is important that the hash function used is > one-way: if one knows the password, it must be very simple/easy to compute > the hash of that password, but if someone obtained the hash of a password, > it must be very difficult to find something, say z, so that hash(z) equals > the hash of the password. but that's property 1 then (i.e. collision resistance), isn't it? And that's essentially what I was trying to point out, as I don't think that, WRT password verification, you'll ever need to know the original x. It's completely sufficient to find some other password y, z, or whatever, such that hash(some_password) == stored_hash where the stored/given hash has originally been computed as hash(x). Thus, I'd still say it's not the oneway aspect that matters here, but rather the collision resistance of the hash function... Of course, as Mike has already pointed out, it's a completely different story whether you can find _any_ collision (for an arbitray hash value), or a collision for some _given_ cryptographic hash value. Otherwise, I hardly have any objections to what you wrote :) > > does this clarify things a bit more? :)) not so sure... :) -- i.e. I don't really see a huge conceptual difference between two 'passwords' or 'documents' hashing to the same value... Also, here again, as I tried to point out in my previous post, I'd say that with finding passwords, you have more degrees of freedom. All that matters is that their hashes are identical, when you want to get access -- the string itself is totally irrelevant. While with signing documents, you'd probably have some very specific message in mind (at least not some random string) that you'd like to fake as originating from someone else. Thanks, Almut -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On Tue, 24 Aug 2004, Almut Behrens wrote: On Tue, Aug 24, 2004 at 12:44:53PM +0200, Danny De Cock wrote: (...) but the verification of password hashes, such as used in pam, rely on the hash function's oneway-feature rather than on its collision-resistance... not sure I understand -- so, if someone would like to explain this aspect to the non-cryptographist, please go ahead :) a cryptographic hash function, such as md5, sha1, ripemd-160, to name the most commonly used cryptographic hash functions are constructed to have at least the following properties: 1. it is hard to find two distinct inputs to the hash function, say x and y, so that hash(x) equals hash(y) 2. they are one-way, i.e., it is hard to find the value x given hash(x) note that these properties have nothing to do with encryption mechanisms. that is a complete other business. for password schemes, it is important that the hash function used is one-way: if one knows the password, it must be very simple/easy to compute the hash of that password, but if someone obtained the hash of a password, it must be very difficult to find something, say z, so that hash(z) equals the hash of the password. for digital signature schemes, we need the first property: if I have someone sign a document, say A, the document itself is not signed, but the hash of that document. if a hash function which is not collision-resistant is used in an application where that property matters, the attack scenario goes as follows: if I know there are two documents, say B and C, which hash to the same hash value, i.e., hash(B) = hash(C), and I have you sign hash(B), you have also produced a digital signature on document C. the meaning of `the hash function is not collision-resistant' is this: I know these documents B and C exist, and they are more or less easy to find. if the hash function were collision-resistant, I know they exist, but they are *not* easy to find. the attacks described in the paper referred to in the original post do give examples of different inputs which hash to the same output. for some of the hash algorithms that have been broken, this requires *very* limited resources. the authors refer to `calculations by hand' ];-> the exact procedure to find these inputs does not really matter: showing the existance of even a single pair of inputs is sufficient to show the hash function is not collision-resistant, and that is what the authors did, i.e., full stop. therefore, the broken hash functions should not be used for schemes where the collision-resistance is important. all this means that these functions can still be used for applications if one only needs the one-way property of the function, e.g., to hash passwords. does this clarify things a bit more? :)) Almut - expert in just too late deliveries and applied cryptography - mail: decockd:at:esat:dot:kuleuven:dot:ac:dot:be http://godot.be godot:at:advalvas:dot:be http://godot.studentenweb.org godot:at:godot:dot:be web: http://www.esat.kuleuven.ac.be/~decockd -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On Tue, Aug 24, 2004 at 08:22:54PM +0200, Almut Behrens wrote: I always thought that the oneway-feature is not particularly relevant when verifying passwords... In other words, if you can find (within a reasonable amount of time) any input string that produces the same given digest, then any password verification system will let you in, independently of whether you ever get to know the original password... Right. But since we know basically nothing about how the collision was generated we don't know if there's a way to find a message that has a given md5 hash value. IOW, the mechanism to generate the collision may only work with certain carefully chosen input data. Until more details are given it's all speculation. Mike Stone -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On Tue, Aug 24, 2004 at 12:44:53PM +0200, Danny De Cock wrote: > > (...) but the verification > of password hashes, such as used in pam, rely on the hash function's > oneway-feature rather than on its collision-resistance... not sure I understand -- so, if someone would like to explain this aspect to the non-cryptographist, please go ahead :) I always thought that the oneway-feature is not particularly relevant when verifying passwords... In other words, if you can find (within a reasonable amount of time) any input string that produces the same given digest, then any password verification system will let you in, independently of whether you ever get to know the original password... In that case, I believe, you'd even have less constraints to satisfy, than when trying to find a collision for a message digest used to verify the integrity of some executable, for example (to protect against trojans, etc.). In the latter case, a large portion of the input would have to be identical (so the trojan will essentially do the same thing as the real program). This means you're only left with some smaller fraction of the binary to fiddle with in an attempt to yield the same message digest for both program versions (compensating for the modifications you made to the code). I'd suspect that the reduced degrees of freedom in the latter case would make it harder to find an appropriate collision. Or am I completely on the wrong track? Just wondering... Almut -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On Tue, 24 Aug 2004 at 10:50:38AM -0400, Daniel Pittman wrote: > Be aware that this sort of technique "multi-encryption" technique can > lead to significant exposures when applied to traditional crypto; it can > produce results that allow a vastly simpler attack on the protected > information. > > I would not put my name to a recommendation about how to make a > cryptographic product or protocol "more secure" unless I had sufficient > background in the area to know the full implications of my recommended > actions. If I understand your postulate correctly: If I, the user, encrypt a message with algorithm X and the cipher text is intercepted by the attacker. The attacker can make his chances of brute forcing the text BETTER by encrypting my cipher text with algorithm Y. This simply does not hold up. -- Phillip Hofmeister -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
Robert Trebula <[EMAIL PROTECTED]> writes: > My question is: Is there an easy way to make my debian sid > installation use something else (better) than md5 for various things? > Namely SHA-1 with some longer output in PAM. Not sure what you mean by that, but sid has the libpam-unix2 package which might be what you're looking for: Package: libpam-unix2 Priority: extra Section: admin Installed-Size: 168 Maintainer: Ivan Kohler <[EMAIL PROTECTED]> Architecture: i386 Version: 1.23-1 Depends: libc6 (>= 2.3.2.ds1-4), libpam0g (>= 0.76), libxcrypt1 Filename: pool/main/libp/libpam-unix2/libpam-unix2_1.23-1_i386.deb Size: 37480 MD5sum: 405b2ec82ec0a59ffb77c0cbd58d24b6 Description: Blowfish-capable PAM module This is a PAM module, backward-compatible with pam_unix, that additionally supports bcrypt Blowfish-based password hashing. -- ,''`. : :' :Romain Francoise <[EMAIL PROTECTED]> `. `' http://people.debian.org/~rfrancoise/ `- -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On 24 Aug 2004, Sam Vilain wrote: > Robert Trebula wrote: > >> Maybe you have already noticed - collisions have been found in MD5 >> hashing algorithm: [...] > I think cryptanalysts have 'cracked' pretty much all of them, though > with practically prohibitive costs of cracking them (eg, 2^50 for > SHA-0). [...] > My personal thought is that you could make the hash more secure simply > by running md5 and SHA1 (maybe pepper on another one for good luck) > across a single stream at the same time, and simply xor the resultant > hashes together. You could pretty much add up the "cost" of the attacks > against the keys. Be aware that this sort of technique "multi-encryption" technique can lead to significant exposures when applied to traditional crypto; it can produce results that allow a vastly simpler attack on the protected information. I would not put my name to a recommendation about how to make a cryptographic product or protocol "more secure" unless I had sufficient background in the area to know the full implications of my recommended actions. Regards, Daniel -- If a joke is worth telling, it's worth telling once. -- Ollie MacNoonan -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On 24 Aug 2004, Robert Trebula wrote: > Maybe you have already noticed - collisions have been found in MD5 > hashing algorithm: > > http://eprint.iacr.org/2004/199.pdf > http://www.freedom-to-tinker.com/archives/000664.html > http://www.unixwiz.net/techtips/iguide-crypto-hashes.html > > My question is: Is there an easy way to make my debian sid installation > use something else (better) than md5 for various things? Namely SHA-1 > with some longer output in PAM. The SHA family have also been found to be weaker than expected also, so it looks like both common crypto hash sets are on somewhat shaky ground at the moment. The best current answer is probably to wait a month or two as the dust settles and the crypto community, especially through the IETF, move forward with recommendations about where we go from here. Jumping half-prepared to some other hash opens the door to a second costly migration if your hash of choice turns out to be the wrong one. ;) Also, while there are issues with those hash algorithms, I don't think they are quite bad enough that there is a significant *immediate* risk to my systems; the cost of breaking in through the detected collisions is lower than the risk of a bad password, etc. Daniel -- In protocol design, perfection has been reached not when there is nothing left to add, but when there is nothing left to take away. -- RFC 1925 -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
Bartosz Fenski aka fEnIo wrote: Collisions have been found? Collisions were always. Every hashing algorithm makes collisions... that's just natural. They found way to generate two input values that makes the same hash. That's still long way before they can generate input having hash of another input. That's exactly what they did - found two matching values using substantially less than the square root of the key space of iterations. They reckoned ~~2^50 iterations to find a matching block for a given SHA-0 checksum. With some heavy duty FPGA's you can build circuits to crack that space pretty quickly, today, with enough money. ie, they found an algorithm and beat the birthday paradox by a few orders of magnitude. Sam. -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
Robert Trebula wrote: Maybe you have already noticed - collisions have been found in MD5 hashing algorithm: http://eprint.iacr.org/2004/199.pdf http://www.freedom-to-tinker.com/archives/000664.html http://www.unixwiz.net/techtips/iguide-crypto-hashes.html My question is: Is there an easy way to make my debian sid installation use something else (better) than md5 for various things? Namely SHA-1 with some longer output in PAM. I think cryptanalysts have 'cracked' pretty much all of them, though with practically prohibitive costs of cracking them (eg, 2^50 for SHA-0). http://www.mail-archive.com/[EMAIL PROTECTED]/msg02554.html http://www.freedom-to-tinker.com/archives/000661.html However, a 2^50 chance, as opposed to the ideal 2^160 still strikes me as pretty good chances. Maybe I'm just not paranoid enough to be a cryptographer ;-). My personal thought is that you could make the hash more secure simply by running md5 and SHA1 (maybe pepper on another one for good luck) across a single stream at the same time, and simply xor the resultant hashes together. You could pretty much add up the "cost" of the attacks against the keys. An exploration of this approach has just been uploaded to CPAN as Digest::SV1. It's at; http://search.cpan.org/dist/Digest-SV1 Sam. -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On Tue, Aug 24, 2004 at 01:51:57PM +0200, Jan Minar wrote: Look at the URLs from the OP. I'd seen them before he posted. It doesn't change what I said. The possibility of md5 collisions has always been present. What we have now is a confirmed collision. Ok. There's no indication of how the collision was generated, so it's not clear that you can generate a collision for arbitrary data, or that you can generate a "valid" string with a colliding value, or that you can generate data to match an arbitrary hash value. So the question remains, what are you using md5 for? This definately requires some more research, but that should be done in a deliberate fashion rather than running around chicken-little style shouting "a collision has been found". Mike Stone -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
On Tue, Aug 24, 2004 at 12:44:53PM +0200, Danny De Cock wrote: > it is true that collisions have been found in md5 (and a lot of other hash > functions of that `family', cfr. the links you mention). Collisions have been found? Collisions were always. Every hashing algorithm makes collisions... that's just natural. They found way to generate two input values that makes the same hash. That's still long way before they can generate input having hash of another input. regards fEnIo ps. could you please stop toppost? -- _ Bartosz Fenski | mailto:[EMAIL PROTECTED] | pgp:0x13fefc40 | IRC:fEnIo _|_|_ 32-050 Skawina - Glowackiego 3/15 - w. malopolskie - Polska (0 0) phone:+48602383548 | Slackware - the weakest link ooO--(_)--Ooo http://skawina.eu.org | JID:[EMAIL PROTECTED] | RLU:172001 signature.asc Description: Digital signature
Re: MD5 collisions found - alternative?
On Tue, Aug 24, 2004 at 07:36:36AM -0400, Michael Stone wrote: > That is expected--a hashing algorithm will always have collisions if the > number of inputs is greater than the output space. As for your question, This seems to be different. Look at the URLs from the OP. pgpDz6ryj9TpL.pgp Description: PGP signature
Re: MD5 collisions found - alternative?
On Tue, Aug 24, 2004 at 01:13:43PM +0300, Robert Trebula wrote: Maybe you have already noticed - collisions have been found in MD5 hashing algorithm: That is expected--a hashing algorithm will always have collisions if the number of inputs is greater than the output space. As for your question, the answer depends on what you are using md5 for. Mike Stone -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Re: MD5 collisions found - alternative?
hi, it is true that collisions have been found in md5 (and a lot of other hash functions of that `family', cfr. the links you mention). this means that the hash functions should certainly no longer be used in applications relying on the collision-resistance of the hash function, e.g., everything where md5withRsa is used should be replaced (note that md5 was considered deprecated already mid-nineties), but the verification of password hashes, such as used in pam, rely on the hash function's oneway-feature rather than on its collision-resistance... cu, g. - expert in just too late deliveries and applied cryptography - mail: decockd:at:esat:dot:kuleuven:dot:ac:dot:be http://godot.be godot:at:advalvas:dot:be http://godot.studentenweb.org godot:at:godot:dot:be web: http://www.esat.kuleuven.ac.be/~decockd On Tue, 24 Aug 2004, Robert Trebula wrote: Hi, Maybe you have already noticed - collisions have been found in MD5 hashing algorithm: http://eprint.iacr.org/2004/199.pdf http://www.freedom-to-tinker.com/archives/000664.html http://www.unixwiz.net/techtips/iguide-crypto-hashes.html My question is: Is there an easy way to make my debian sid installation use something else (better) than md5 for various things? Namely SHA-1 with some longer output in PAM. Thanks, Robert -- http://deepblue.sk/~r0b0/web/ PGP fingerprint: FEB3 D653 F918 8B07 83B1 E4BD A3ED B11E 1DD5 ACD7 -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
