TechGenix and SolarWinds have partnered to provide a fully-functional, free 21-day trial version of SolarWinds ipMonitor, the WindowsNetworking.com Readers' Choice Award Winner for monitoring applications, servers, and network devices to all visitors who join Security Forums. Sign up to Security Forums and get your copy today! Existing members can pick up a copy from the Members Area.
| View previous topic :: View next topic |
| Author |
Message |
ghost16825
Regular Member
Joined: 24 Nov 2003
Posts: 97
|
 Posted: Mon Aug 16, 2004 9:57 am Post subject: Collision found in SHA-0 |
 |
|
I found this in the netscape.public.mozilla.crypto newsgroup. It's basically a repost of another post in another newsgroup:
-------- Original Message --------
Subject: Joux found a collision for SHA-0 !
Date: Fri, 13 Aug 2004 15:32:29 +0200
From: Pascal Junod <pascal.junod@epfl.ch>
Organization: EPFL - LASEC
To: cryptography@metzdowd.com
Hi !
This has appeared on a french mailing-list related to crypto. The results of
Joux improve on those of Chen and Biham which will be presented next week at
CRYPTO'04.
Enjoy !
<quote>
Thursday 12th, August 2004
We are glad to announce that we found a collision for SHA-0.
First message (2048 bits represented in hex):
a766a602 b65cffe7 73bcf258 26b322b3 d01b1a97 2684ef53 3e3b4b7f 53fe3762
24c08e47 e959b2bc 3b519880 b9286568 247d110f 70f5c5e2 b4590ca3 f55f52fe
effd4c8f e68de835 329e603c c51e7f02 545410d1 671d108d f5a4000d cf20a439
4949d72c d14fbb03 45cf3a29 5dcda89f 998f8755 2c9a58b1 bdc38483 5e477185
f96e68be bb0025d2 d2b69edf 21724198 f688b41d eb9b4913 fbe696b5 457ab399
21e1d759 1f89de84 57e8613c 6c9e3b24 2879d4d8 783b2d9c a9935ea5 26a729c0
6edfc501 37e69330 be976012 cc5dfe1c 14c4c68b d1db3ecb 24438a59 a09b5db4
35563e0d 8bdf572f 77b53065 cef31f32 dc9dbaa0 4146261e 9994bd5c d0758e3d
Second message:
a766a602 b65cffe7 73bcf258 26b322b1 d01b1ad7 2684ef51 be3b4b7f d3fe3762
a4c08e45 e959b2fc 3b519880 39286528 a47d110d 70f5c5e0 34590ce3 755f52fc
6ffd4c8d 668de875 329e603e 451e7f02 d45410d1 e71d108d f5a4000d cf20a439
4949d72c d14fbb01 45cf3a69 5dcda89d 198f8755 ac9a58b1 3dc38481 5e4771c5
796e68fe bb0025d0 52b69edd a17241d8 7688b41f 6b9b4911 7be696f5 c57ab399
a1e1d719 9f89de86 57e8613c ec9e3b26 a879d498 783b2d9e 29935ea7 a6a72980
6edfc503 37e69330 3e976010 4c5dfe5c 14c4c689 51db3ecb a4438a59 209b5db4
35563e0d 8bdf572f 77b53065 cef31f30 dc9dbae0 4146261c 1994bd5c 50758e3d
Common hash value (can be found using for example "openssl sha file.bin"
after creating a binary file containing any of the messages)
c9f160777d4086fe8095fba58b7e20c228a4006b
This was done by using a generalization of the attack presented at Crypto'98
by Chabaud and Joux. This generalization takes advantage of the iterative
structure of SHA-0. We also used the "neutral bit" technique of Biham and
Chen (To be presented at Crypto'2004).
The computation was performed on TERA NOVA (a 256 Intel-Itanium2 system
developped by BULL SA, installed in the CEA DAM open laboratory
TERA TECH). It required approximatively 80 000 CPU hours.
The complexity of the attack was about 251.
We would like to thank CEA DAM, CAPS Entreprise and BULL SA for
their strong support to break this challenge.
Antoine Joux(*) (DCSSI Crypto Lab)
Patrick Carribault (Bull SA)
Christophe Lemuet, William Jalby
(Universit'e de Versailles/Saint-Quentin en Yvelines)
(*) The theoretical cryptanalysis was developped by this author.
The three others authors ported and optimized the attack on the TERA NOVA
supercomputer, using CAPS Entreprise tools.
$hexdump fic1.bin
0000000 66a7 02a6 5cb6 e7ff bc73 58f2 b326 b322
0000010 1bd0 971a 8426 53ef 3b3e 7f4b fe53 6237
0000020 c024 478e 59e9 bcb2 513b 8098 28b9 6865
0000030 7d24 0f11 f570 e2c5 59b4 a30c 5ff5 fe52
0000040 fdef 8f4c 8de6 35e8 9e32 3c60 1ec5 027f
0000050 5454 d110 1d67 8d10 a4f5 0d00 20cf 39a4
0000060 4949 2cd7 4fd1 03bb cf45 293a cd5d 9fa8
0000070 8f99 5587 9a2c b158 c3bd 8384 475e 8571
0000080 6ef9 be68 00bb d225 b6d2 df9e 7221 9841
0000090 88f6 1db4 9beb 1349 e6fb b596 7a45 99b3
00000a0 e121 59d7 891f 84de e857 3c61 9e6c 243b
00000b0 7928 d8d4 3b78 9c2d 93a9 a55e a726 c029
00000c0 df6e 01c5 e637 3093 97be 1260 5dcc 1cfe
00000d0 c414 8bc6 dbd1 cb3e 4324 598a 9ba0 b45d
00000e0 5635 0d3e df8b 2f57 b577 6530 f3ce 321f
00000f0 9ddc a0ba 4641 1e26 9499 5cbd 75d0 3d8e
$ hexdump fic2.bin
0000000 66a7 02a6 5cb6 e7ff bc73 58f2 b326 b122
0000010 1bd0 d71a 8426 51ef 3bbe 7f4b fed3 6237
0000020 c0a4 458e 59e9 fcb2 513b 8098 2839 2865
0000030 7da4 0d11 f570 e0c5 5934 e30c 5f75 fc52
0000040 fd6f 8d4c 8d66 75e8 9e32 3e60 1e45 027f
0000050 54d4 d110 1de7 8d10 a4f5 0d00 20cf 39a4
0000060 4949 2cd7 4fd1 01bb cf45 693a cd5d 9da8
0000070 8f19 5587 9aac b158 c33d 8184 475e c571
0000080 6e79 fe68 00bb d025 b652 dd9e 72a1 d841
0000090 8876 1fb4 9b6b 1149 e67b f596 7ac5 99b3
00000a0 e1a1 19d7 899f 86de e857 3c61 9eec 263b
00000b0 79a8 98d4 3b78 9e2d 9329 a75e a7a6 8029
00000c0 df6e 03c5 e637 3093 973e 1060 5d4c 5cfe
00000d0 c414 89c6 db51 cb3e 43a4 598a 9b20 b45d
00000e0 5635 0d3e df8b 2f57 b577 6530 f3ce 301f
00000f0 9ddc e0ba 4641 1c26 9419 5cbd 7550 3d8e
$ diff fic1.bin fic2.bin
Binary files fic1.bin and fic2.bin differ
$ openssl sha fic1.bin
SHA(fic1.bin)= c9f160777d4086fe8095fba58b7e20c228a4006b
$ openssl sha fic2.bin
SHA(fic2.bin)= c9f160777d4086fe8095fba58b7e20c228a4006b
</quote>
--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* Pascal Junod <pascal.junod@epfl.ch> http://crypto.junod.info *
* Security and Cryptography Laboratory (LASEC) *
* Swiss Federal Institute of Technology (EPFL), CH-1015 Lausanne *
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
---------------------------------------------------------------------------------
|
|
| Back to top |
|
 |
data
Forum Junky
Joined: 08 May 2004
Posts: 650
Location: India
|
| Posted: Mon Aug 16, 2004 1:59 pm Post subject: |
|
|
hi,
I saw it too. I haven't heard of SHA-0 nor seen the algorithm. What I cannot understand is that whats special of finding collsions.
The example posted shows two messages, one 2048 bit long and another message of similar length being hashed to the same message digest of length 160 bit.
Its obvious that all hashing algorithm gives collisions. Thats what the pigeon hole principle says-
'if you have m pigeons and n pigeon holes and m>n, then you have atleast two pigeons in one pigeon hole'
A perfect hash function for a input message M should be
f:M->H(M), such that its a bijection (one to one and onto).
We have H(M), a short fixed length bit string. If the input size is larger than the size of the message digest, we have collisions by the pigeon hole principle. Also look at the birthday paradox,if you like to.
Data.
|
|
| Back to top |
|
|
Matt Crypto
Lurker
Joined: 17 May 2004
Posts: 15
|
| Posted: Tue Aug 17, 2004 2:07 am Post subject: |
|
|
| datah wrote: |
I saw it too. I haven't heard of SHA-0 nor seen the algorithm. What I cannot understand is that whats special of finding collsions.
...
Its obvious that all hashing algorithm gives collisions.
|
Yes, you're right when you say that it's obvious that all hashing algorithms have collisions; what's not normally obvious is an easy way to find collisions -- in a cryptographic hash function, there should be no computationally feasible way to generate collisions. This is important for security -- if you can generate collisions, you can attack hash functions used in certain ways, e.g. tricking people into signing documents.
See:
http://en.wikipedia.org/wiki/Birthday_attack
for more info on how the ability to find collisions can be used in an attack, and:
http://en.wikipedia.org/wiki/SHA_family
for more on SHA-0.
|
|
| Back to top |
|
|
mjuarez
Regular Member
Joined: 15 Jun 2004
Posts: 96
|
| Posted: Tue Aug 17, 2004 7:36 am Post subject: |
|
|
The NSA designed SHA-0, but later tossed it in favor of SHA-1, which is the currently supported SHS (Security Hash Standard) algorithm, along with the SHA-2 family (SHA-224, SHA-256, SHA-384, SHA-512). So the results above don't mean much, except for academic analysis.
Now, if the results are reproducible with the SHA-1 compression function, we might have a problem. I didn't get that from the article posted above, however.
Marcos
|
|
| Back to top |
|
|
JustinT
Trusted SF Member
Joined: 17 Apr 2003
Posts: 1227
Location: Charlotte, NC, US / Uberlāndia, MG, Brazil
|
| Posted: Tue Aug 17, 2004 9:14 am Post subject: SHA-0, SHA-1, and collisions. |
|
|
| datah wrote: |
I saw it too. I haven't heard of SHA-0 nor seen the algorithm. What I cannot understand is that whats special of finding collsions.
|
SHA-0 was the predecessor to SHA-1, obviously. It was specified by NIST, in FIPS-180, around 1993; the design principles behind it, just as many hash functions of this era, were based heavily off of MD4 and MD5, so you'll notice structural similarities between the SHA and MD family. Just as SHA-1, it has a 160-bit state. The NSA identified a technicality that prompted a revision; hence, NIST specifies SHA-1 in FIPS-180-1, around 1995. This revision adds a rotate operation that is boasted as an "improvement" to the security of the SHA structure. Of course, no extensive information was disclosed, but recent analyses by Chabaud and Joux (around 1998) and Biham and Chen (around 2004) echo the probable reasoning behind this alteration, as much of the cryptanalysis is applicable to significantly attacking SHA-0, but not SHA-1.
The reason that this current production of a collision is "special" is because of the methodology they applied, and the incredibly small margin of complexity the attack posed. We assume, because of collision attacks (birthday paradox, most notably) that a 160-bit hash function would render a complexity of 2^80; the complexity of the collision attack demonstrated by Joux, Carribault, Lemuet, and Jalby was around 2^51, which is far below the generic assumption. You may have even noticed that recent improved attacks, by Biham and Chen, producing collisions and near-collisions have been extended to smaller round variants of SHA-1. It's not entirely likely that they'll be able to compromise the full SHA-1 algorithm, presently, but I expect to see extensions to variants of larger size than current, and a paved way leading to analysis that may eventually attack the full function.
Our idealized hash function is one that behaves as a random mapping of all possible input values to a set of possible output values; this doesn't exist, in practice, so we shoot for a realized hash function, which accepts the fact that there are an infinite number of inputs, but only a finite number of outputs, so collisions exist, point blank. However, collision-resistance is the most desired property of a hash function. This refers to the internal semantics of the hash function; it doesn't refer to the generic assumption of a birthday paradox-based attack, which is a very broad, extrinsic approach. This is where we define a distinguishing attack on a hash function, or an attack on the structure of a hash function that distinguishes the function from a sufficiently random mapping. The question that must be asked is whether or not a distinguishing attack exists that operates on a smaller complexity than a generic attack, such as relying on the birthday paradox.
In other words, if our hash function produces an n-bit output, we expect no practical attack to exist that carries a complexity lower than 2^n/2, or the complexity of a collision attack based on the birthday paradox. This ultimately determines the usefulness of a distinguishing attack and qualifies as a determining factor in the overall security of the hash function. By any good standard, a hash function should make it practically infeasible to produce collisions; SHA-0 has been show to fall far short of this requirement. This is definitely a demonstratable "break." Collision attacks may not apply to some practical applications, but because we can't be certain, at this point, that this method for producing collisions won't indirectly aid a pre-image attack (generically, 2^n and related to many commonplace applications) that may apply to those practical applications, it's wise to treat it as a failure to meet the design requirements of a secure hash function. The expected criteria is short, but strict, and rightfully so.
Aside from demonstrating the practical susceptibility of SHA-0 to such efficient collision attacks, it also signifies a preliminary look into new avenues of attack that could possibly be applied to SHA-1 as a whole, in the foreseeable future. Looking at it from a wider angle, consider it an inside look into cryptanalyzing the structure of the SHA family, in such a way that may lead to the practical facilitation for practical attacks against the modern applications of a hash function. There was no good cryptographic reason to use SHA-0 over SHA-1 in the first place, but the fact that SHA-1 is so closely related in design sparks a general eye of attention. We don't have an overly abundant supply of secure hash functions at our disposal, and because so many of these designs are based upon the principles of the MD and SHA families, any cryptanalysis revolving around these two is significant, in regards to our philosophy for what we believe to be secure design criteria for a cryptographic hash function. Our knowledge and insight into their design is rapidly growing, and there are a lot of promising primitives having been proposed in recent years, but MD and SHA-based designs (assuming the relatively secure choices) have been the cornerstone of both official and de facto standardization, so considering practical breaks in either is considering the realization that a plethora of systems that implement them will need to be redesigned.
Just to put this in perspective, look at current analytical research on reduced-round variants of these hash functions, just as we commonly do with block ciphers. The compression function of SHA-1 contains a "block cipher"-like component, with a round function that is, essentially, a generalized Feistel network-like structure, so using this perspective is easier, because of that relevance; this is no surprise, as the structures of both block ciphers and hash functions allow for the interchangeable application of both encryption and hashing, oftentimes. Shortly after the time of Biham and Chen's published cryptanalysis of SHA-0 and SHA-1, they were able to produce millions of collisions on 34-round SHA-1 and a collision on 36-round SHA-1; SHA-1, when considering the steps it performs as "rounds", consists of 80 rounds. This is approaching close to 50% of the performed steps. Near-collisions were produced for 45-round SHA-1, which exceeds half of the steps, percentage-wise. Near-collisions can be effectively used in finding collisions, so the chances that the bar on producing collisions for larger round variants will be raised are potentially favorable. This isn't, by any means, a suggestion that SHA-1 is broken, or even will be any time soon, but because attacks such as these usually get better over time, one should recognize the mediocre margin of security provided, as well as the rate in which it could diminish, given further improvements in this area of analysis. This is all just a current observation of the situation currently at hand; it is, at least, to what is widely known throughout the general public community.
We can conclude two things from all of this: Do not use SHA-0 in any new cryptographic designs and consider using SHA-256, at bare minimum, as SHA-1 does not provide a conservative margin of security. It's a good tactic, when being conservative, to realize the extended application of new theory and demonstratable results; this way, you can design in such a way as to allow yourself a lot of breathing room within the margin of security you wish to achieve. Overall, the whole argument over SHA-0 is predominantly academic, I agree; the potential for its application to SHA-1 is of much more interest.
_________________
"Strict Avalanche Criterion n. Restrictive clause in ski-insurance policy."
Last edited by JustinT on Tue Aug 17, 2004 9:37 am; edited 1 time in total |
|
| Back to top |
|
|
Dunceor
Frequent Member
Joined: 05 Sep 2003
Posts: 219
Location: Sweden
|
|
| Back to top |
|
|
data
Forum Junky
Joined: 08 May 2004
Posts: 650
Location: India
|
| Posted: Tue Aug 17, 2004 11:03 am Post subject: |
|
|
|
i see,thanks.
|
|
| Back to top |
|
|
sn3fru
Regular Member
Joined: 20 Jul 2004
Posts: 77
Location: Europe, EU
|
| Posted: Fri Aug 20, 2004 11:15 pm Post subject: |
|
|
Yes, the collisions have been confirmed for the following hash functions:
MD4, MD5, HAVAL-128 and RIPEMD.
http://eprint.iacr.org/2004/199.pdf
RIPEMD is the predecessor to RIPEMD-128 and RIPEMD-160 (which are strengthened versions that have not been broken).
Regards,
_________________
"If it's provably secure, it's probably not." - Lars Knudsen
|
|
| Back to top |
|
|
jupi
Just Arrived
Joined: 21 Aug 2004
Posts: 1
|
| Posted: Sat Aug 21, 2004 2:35 pm Post subject: |
|
|
Here is another link for good md5 collision with only 6 byte difference:
http://www.tcs.hut.fi/~mjos/md5/
I am making password authentication system. Passwords are currently stored in a file as hashes, in the same way as in Unix md5Crypt does. Do you think that I should dump the md5 and use SHA256 instead? Is it enough if I make the password hashes in a same way as md5Crypt, except I replace the MD5 hash with SHA256 in the crypt algorithm?
|
|
| Back to top |
|
|
JustinT
Trusted SF Member
Joined: 17 Apr 2003
Posts: 1227
Location: Charlotte, NC, US / Uberlāndia, MG, Brazil
|
| Posted: Mon Aug 23, 2004 3:08 am Post subject: Password authentication. |
|
|
| jupi wrote: |
I am making password authentication system. Passwords are currently stored in a file as hashes, in the same way as in Unix md5Crypt does. Do you think that I should dump the md5 and use SHA256 instead? Is it enough if I make the password hashes in a same way as md5Crypt, except I replace the MD5 hash with SHA256 in the crypt algorithm?
|
In any new system where security is concerned, I would suggest using SHA-256, as it provides a 128-bit level of security and boasts a structure that is based on a tremendous amount of cryptanalysis; do not use MD5 in new designs, as its low margin of security is much too insufficient. It fails to satisfy the level of collision resistance that a secure hash function should. However, because poor password-choosing etiquette common, an HMAC construction, or something similar, would be a bit more robust, rather than just storing the hash output values of passwords. Or, consider one of the protocols mentioned below.
Might I ask for what reason you wish to design your own password authentication system? There are numerous protocols around, which are based on cryptographic concepts that you may wish to borrow, if indeed you wish to design this yourself in the case that none of them are entirely suitable for your needs. Or, to save yourself the work involved with design and analysis of your own system, use one of these existing protocols, if applicable. Among these include SRP, EC-SRP, SRP-4, SRP-6, SPEKE, B-SPEKE, AuthA, AMP, PAK, SNAPI, et cetera, and their respective variants.
There are many options to go about authentication, but if you're considering a hash-based construction, at least ensure that you're using a 256-bit hash function; the most analyzed construction of this type, at this point, is SHA-256, which conservatively meets the general requirements of a secure hash function and provides the aforementioned 128-bit level of security. There are other good hash functions, of which deserve a look, but the SHA family carries with it the most analysis, alongside the less secure MD family, so it's probably best to choose it, for now. Of course, hash function cryptanalysis has taken a surprising turn, here in recent days, which is evidence of our minimal knowledge in hash function design, as opposed to other cryptographic primitives.
_________________
"Strict Avalanche Criterion n. Restrictive clause in ski-insurance policy."
|
|
| Back to top |
|
|
|
