SHA-1 Broken 751
Nanolith writes "From Bruce Schneier's weblog: 'SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing. The research team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu (mostly from Shandong University in China) have been quietly circulating a paper announcing their results...'" Note, though, that Schneier also writes "The paper isn't generally available yet. At this point I can't tell if the attack is real, but the paper looks good and this is a reputable research team."
Sigh (Score:5, Funny)
Re:Sigh (Score:5, Funny)
About a month ago, I needed a mechanism for password hashes.
After some research, I decided that SHA1 was more secure than MD5.
So I hunted down some good public domain SHA1 code, read through it, and added it to my code.
Thanks /.!
Re:Sigh (Score:3, Insightful)
Maybe its easier to upgrade from SHA1 than it was from MD5.
Re:Sigh (Score:3)
Re:Sigh (Score:4, Funny)
A mechanism to find collisions does not affect SHA-1's strength as a password hashing algorithm or its use in a hashed message authentication code. So you'll be just fine.Z
really? well, i'm not the real frymaster. what do you say to that?
-----BEGIN PGP SIGNATURE----- Version: GnuPG v1.2.4 (Darwin) iD8DBQFCEsqV7Kzi+hL3je0RAl7iAJ41SsgjgwMvrS5+1OLLYp pYkXUPOgCgzSQS
c42DLVAjebLYs2VTPkT/iIc=
=8699
-----END PGP SIGNATURE-----
Re:Sigh (Score:5, Insightful)
Re:Sigh (Score:5, Funny)
Imagine tens of thousands of way-overpowered virus-infected 3Ghz Dell machines chewing threw the data?
Then imagine a beowulf cluster of those.
Re:Sigh (Score:4, Informative)
Let's say you have 2^20 (1048576) machines. Let's say each can do 2^20 hashes per second (this is optimistic). Then it will take you 2^29 seconds to find a hash collision-- this is about 17 years.
This doesn't even let you collide with an arbitrary thing-- rather, you can provide something to someone to sign, and have another message that hashes to the same thing.
It is worrisome, though, because perhaps attacks will improve and it'll continue to get cheaper.
Re:Sigh (Score:4, Informative)
That is not how it works. THey are using the birthday paradox, that is why brute force is 2^80 not 2^160. Put simple the birthday paradox finds two pieces of data with the same hash. It does NOT (as so many posts believe) allow you to find a matching hash to a fixed piece of data. (This would take 2^160, perhaps less with the weaknesses discovered but not close to 2^69). Hence this does not allow you to break passwords.
Re:Sigh (Score:4, Informative)
Lets say I have an ISO disk image. I hack it, and want to modify some of the 'junk' bits using their algorithm. I'd still need to perform 590295810358705651712 hash operations on that image. Computing the hash of a disc is a slow operation. That's not something I could do in a day, week, or even a few months. Perhaps if I had a massivly parallel computer available, I could do it, but not as an individual.
No need to compute the hash of a whole disc. You can calculate the internal state of SHA-1 after processing the whole image except - lets say - the last kilobyte (you do it ONCE) and find a collision by modifying only this last kilobyte with great chance of succeeding. There are 2^8192 variants of the last kilobyte, but only 2^160 variants of the hash - that's why you'll probably succeed.
Not a problem (yet) (Score:5, Informative)
OTOH, this attack indicates that other types of attacks may be found sooner than was previously thought. So it is still a good idea to move away from SHA-1 in the medium to long term. Though it's not entirely clear what you should move to. And it is not certain that more attacks will be found soon.
Re:Not a problem (yet) (Score:4, Informative)
SHA1(data1) == SHA2(data2) where data1!=data2
because SHA1 maps from a large space to 160bits. There WILL be collisions for any maping like that. The question is can you make,
SHA1(data1)==SHA2(data2) && data1.length==data2.length) ?
Can you make the length of the hashed data to be equal?
If you cannot, then most of the signed hashes cannot be compromised anyway.
Re:Not a problem (yet) (Score:5, Informative)
Re:Not a problem (yet) (Score:5, Informative)
--Pat / zippy@cs.brandeis.edu
Re:Not a problem (yet) (Score:5, Informative)
With this technique, you can create 2 files, by modifying both of them, that have the same hash. That does not mean that you can create a file with a given hash.
Re:Not a problem (yet) (Score:5, Insightful)
Maybe you don't realise where he is coming from.
With a digital signature, you can easily have knowledge of the signed message (input to message digest function) and thus change the message while retaining the signature.
With a hashed password, you don't have access to the password (input to message digest function).
The hashed password would require figuring out the password so as to allow changing it to make the same hash. This requires going the wrong way against this one way hash algorithm. If you were able to do this, then you would not bother generating an equivalent password, because you would know the original.
I think the point is, that the one way nature of SHA-1 might still be strong. Meaning digital signatures are weak, but hashed passwords are not.
There is no logic flaw in his comment.
Both statements are fine -- salt explained (Score:4, Informative)
For example, if my password is "foobar", then the server does not store "8843d7f92416211de9ebb963ff4ce28125932878" as the hash, but perhaps the hash of "foobarDKTUHRAOHL" or "19747e26b86ee7939c046c0171a991926f0e01ae". The salt value "DKTUHRAOHL" is stored on the server and never revealed to anyone. So, even if somebody knows the hash value "19747...e01ae", they cannot come up with another string of characters that hashes to the same value, because even if they could, the value they enter in an attempt to hack my account is appended with "DKTUHRAOHL", rendering (almost certainly) a different hash value.
Now, if they know the salt value, the problem becomes equivalent to finding a string ending with "DKTUHRAOHL" that hashes to "19747...e01ae." However, if someone has gained access to a properly secured server's salt values, you have a large problem on your hands indeed.
Re:Both statements are fine -- salt explained (Score:5, Insightful)
Re:Not a problem (yet) (Score:5, Interesting)
Re:Not a problem (yet) (Score:5, Interesting)
Don't panic! 'Broken' is not Cracked (Score:5, Insightful)
MD5 was 'broken' in 1995 by Hans Dobbertin who discovered compressor function collisions. It was almost another 10 years before the compressor function collisions were turned into an attack which produced hash collisions.
So there is a serious security problem here but it does not mean that everything that uses SHA-1 is now vulnerable. There are many applications where MD5 is completely adequate. If you have a really good reason to do so and a really good understanding of the security requirements and risks you can use even something like MD2.
Today paul Kocher complained that Microsoft was using MD5 in its anti-spyware to identify known bad software. This is not actually a major problem, much worse would be using MD5 to identify known good software to keep, that is when a collision would bite. For known bad programs well i don't want any variant of the program to run...
But if you are writing an entirely new application then use SHA-256 or SHA-512, more rounds, more bits.
Meanwhile we need to research some new hash functions pronto.
Re:Well... (Score:5, Funny)
Re:Well... (Score:3, Funny)
Re:Well... (Score:5, Funny)
Re:Well... (Score:5, Funny)
Re:Well... (Score:4, Funny)
Hah! (Score:5, Funny)
better yet-- (Score:5, Funny)
Re:better yet-- (Score:5, Funny)
Re:better yet-- (Score:5, Funny)
Info on what exactly SHA-1 is ... (Score:5, Informative)
Re:Info on what exactly SHA-1 is ... (Score:5, Interesting)
Re: (Score:3, Insightful)
Re:Info on what exactly SHA-1 is ... (Score:5, Insightful)
There's a significant difference.
Re:Info on what exactly SHA-1 is ... (Score:5, Informative)
Encryption is not in any way hashing, and hashing is not in any way encryption.
A one way hash cannot in any way be decrypted, thats why it's called one way. It's physically not possible.
A hash is not used to "protect" the data you are hashing, it's used to identify the data you are hashing. You can take an unhashed value, hash it and compare it with another hashed value to identify that the two original values were very likely the same value
The strength of a hash is simply how likely it is that the two values were the same value, or conversly, how likely it is that they were not the same value.
When two distinct values have the same resultant hash, we call that a "collision". It should be obvious that there are an infinite number of collisions for a fixed-length hash value - pidgeon hole principle shows you that.
And SHA1 is not "broken", not yet, to be "broken" we would have to have a feasible way to generate a string of data that when hashed produces the same hash as an *already known* hash.
If we could generate collisions for KNOWN hashes, in a reasonable time, then we could use those collisions to falsly identify to systems that use a hash of the original (still unknown) value.
Re:Info on what exactly SHA-1 is ... (Score:5, Interesting)
For quite a few applications the hash is broken even if I cannot easily find a second string with the same hash as one given. Even if I can "only" at will find two strings with the same hash, that is a pretty serious weakness.
I could, for example, create two documents with the same hash, have you sign one, and then claim you signed the other one. Since the hashes are the same your digital signature will be valid for both.
For other applications, like replacing a signed document with another without being detected you're rigth -- that would only work if one could easily find a document with a given hash.
Re:Info on what exactly SHA-1 is ... (Score:3, Funny)
Re:Info on what exactly SHA-1 is ... (Score:5, Interesting)
Re:Info on what exactly SHA-1 is ... (Score:5, Interesting)
You know, of course, that the NSA did the same thing with SHA right? The original algorithm submitted was SHA-0, then the NSA recommended an unexplained minor change.
Last August SHA-0 was broken, so their tweak appears to have added about 6 months of extra life for SHA-1.
Re:Info on what exactly SHA-1 is ... (Score:5, Interesting)
I don't know about this, but when SHA (the Secure Hash Algorithm) was submitted as an approved algorithm for government use, the NSA reviewed it and suggested a minor change. That modified algorithm is what we now know as SHA-1. It was a few years before public-sector cryptographers caught on to what the significance of the changes was (I wish I could explain it, but it is beyond me).
Re:Info on what exactly SHA-1 is ... (Score:5, Informative)
Note quite right. The NSA invented SHA, but then a couple of years later discovered a weakness and made a slight change, to create SHA-1. The older version is now called SHA-0. According to Schneier's report, SHA-0 was broken even worse by the Chinese team, 2^39 work for a collision vs 2^69 for SHA-1. So the NSA's change was important and made a major increase in the strength of the algorithm.
It was a few years before public-sector cryptographers caught on to what the significance of the changes was (I wish I could explain it, but it is beyond me).
They just added a 1 bit rotate in one phase of the algorithm. Without it, SHA tends to keep the bits lined up and there is less mixing.
Re:Info on what exactly SHA-1 is ... (Score:5, Insightful)
Not true. (Score:3, Interesting)
Where've you been?
Re:Not true. (Score:3, Informative)
For more info (Score:3, Informative)
http://www.itl.nist.gov/fipspubs/fip180-1.htm [nist.gov]
Prison. (Score:5, Funny)
Oh great... (Score:3, Funny)
Time to switch.... (Score:4, Funny)
Re:Time to switch.... (Score:4, Informative)
FYI, SHA-224, SHA-256, SHA-384, and SHA-512 are all referred to as SHA-2.
Re:Time to switch.... (Score:4, Informative)
FYI, SHA-224, SHA-256, SHA-384, and SHA-512 are all referred to as SHA-2.
Doesn't matter. The only difference is key length. The algorithm is the same.
Time to start a panic (Score:5, Funny)
Brought to You By (Score:5, Informative)
Re:Please explain further. (Score:4, Informative)
the next step up is to, for any data X and hash Z determine a Y which does not equal X which has hash Z. THe ultimate breakage is when you can, for any data X with hash Z and arbitrary data Y generate M which has the property of Y+M has a hash of Z. At this point you can substitute a conrolled and malicious piece of data which can substitute for X.
May be a big deal... (Score:3, Interesting)
Re:May be a big deal... (Score:5, Informative)
You do not quite understand correctly. MD5 and SHA-1 are hashing algorithms, and as such it is expected (and accepted) that there are collisions. That is, you might find that your
That is, you can either keep a backup copy of your filesystem to compare against or you can keep a list of hashes, and mathematically, all this "break" has demonstrated is that the chances are 1:590295810358705651712 not 1:1208925819614629174706176 of a collision. In other words, don't lose sleep.
Now, for secure cryptographic signatures, the implications are much more unpleasant. It's not the end of the world, but this is that big red light that says: switch to SHA-512 (or something equally secure) ASAP!
What a hash is/does (Score:4, Informative)
Re:May be a big deal... (Score:3, Informative)
I think what you are thinking of is a digital signature system, where the document is hashed and then the hash is signed. Any tampering would invalidate the signature. The hash is used because it takes a lot of random data to encrypt an arbitrary file, while it takes quite a bit less to encrypt a short, fixed-length hash like SHA-1. Since (in theory)
Now what do we use? (Score:3, Interesting)
Re:Now what do we use? (Score:5, Informative)
The Hashing Function Lounge [terra.com.br] also lists Cellhash, Parallel FFT-Hash , RIPEMD-128, RIPEMD-160, Subhash and Tiger as (so far) unbroken.
Re:Now what do we use? (Score:3, Funny)
Re:Now what do we use? (Score:3, Informative)
SHA-256
SHA-384
SHA-512
The numbers refer to the bit length of the generated hash. SHA-1 uses only a 160 bit length, called a message digest. But then, you'd know all that if you would have rtfa.
--I wish there was some way to automatically append a line of text to messages posted on slashdot.
US Secure Hash Algorithm 1 (Score:5, Informative)
SHA-1 Hash Algorithm [ietf.org] and Source Code [cr0.net].
Bittorrent? (Score:5, Interesting)
How hard is it going to be for people to provide garbage data with correct SHA-1 hashes to screw up downloads?
Re:Bittorrent? (Score:4, Insightful)
Judging from what's been said about how difficult it is to break SHA-1 even with this discovery, I would think it's fine for now, but a new hash should probably be included with BitTorrent2.
Broken, but not for everything... (Score:5, Insightful)
Sure, for signatures, it means that you can't trust the algorithm 100% anymore.
But for storing passwords, and other operations where collisions are not important, it doesn't matter much, even if there's another password that can generate the same hash, you still need to brute-force it.
Re:Broken, but not for everything... (Score:4, Insightful)
It's an assurance, that's all. The only guarantee is a one-time pad, and Bruce Schneier's website is full of info on why these aren't practical!
Re:Broken, but not for everything... (Score:3, Interesting)
Suppose you're signing a tar.gz file. If the NSA could find a collision, the collision will still need to fit:
- filesize has to stay the same
- you don't want to get errors with gzip
- you don't want to get errors with tar
- the files in the archive needs to make sense
What's the probability of all this happening?
So what's the big deal for the rest of us? (Score:5, Interesting)
I'm not a cryptographer, just a nerdy engineer, but let me explain my rationale: a hash algorithm takes an arbitrary message and generates a fixed-length signature that has a high probability (10**50 or better for most modern algorithms) of being the original.
Let's assume that your hash algorithm generates a 128-bit hash. Anyone who knows anything about probability can see that is the original message is greater than 128 bits, there MUST be more than one message that will generate the same hash. For long messages, there may be thousands or millions of messages out of a filed of 10**50 (or better) that have the same hash, although many of them will be meaningless garbage.
So SHA-1 has been broken by a group of cryptographers/mathematicians. Does this really mean that they can generate can alter any message in a way that will generate the same hash as the original, thus fooling the math that we use to validate content? No Way! I read Bruce Scheier's Cryptogram every month and he often makes the same argument.
So yes, this means that from a long-term systems security standpoint, we should all move to stronger hashes. Does it mean that SHA-1-based transactions are inherently secure right now?
I think not!
Re:So what's the big deal for the rest of us? (Score:5, Insightful)
Essentially, don't sign anything that someone else has given you without changing it in some way, or your signature might also apply to some other document they have chosen.
Re:So what's the big deal for the rest of us? (Score:4, Informative)
Right, this is important.
Decent digital signature protocols (as opposed to just the algorithms) require that you hash more than just the document. For example, you might pick a small amount of random data ("salt"), add that to the message, hash the combination and sign that. You then put the salt in the signature packet so that your signature can be verified.
OpenPGP, for example, requires that certain signature subpackets be part of the hash, such as the signature creation time. It probably should require random salt.
Re:So what's the big deal for the rest of us? (Score:4, Informative)
Let's say someone trusts a digital signature, signed with SHA-1, to the point of allowing money to be predicated on the validity of this signature. If the message is signed and valid, the payer pays the payee $X dollars, where X is some very large amount.
Message #1 is generated and sent. It validates.
The money is paid. At which point the payee produces a second message which hashes the same as the first but claims to be turning down the deal, or modifying the terms of the deal s.t. they don't have to do anything to earn that money, and they claim that's what was actually sent.
This is a problem, since the break apparently allows the construction of two (relatively) arbitrary message sequences that hash to the same value, which is an easier and much different problem from constructing an arbitrary message that hashes the same as a pre-existing message.
Unfortunately the SHA series seems to be suspect (Score:5, Interesting)
If this definite break is confirmed, I think we will need to conclude that the entire family is suspect for any genuinely important purpose.
There are a bunch of hashing algorithms on the Hashing Function Lounge that are listed as having no known attacks. At present, the most widespread is Whirlpool. I think it likely that one of these will replace SHA as the hashing function of choice in major cryptographic areas.
I Can See Bruce Now.... (Score:4, Funny)
Bruce sits at his desk, reading over the encrypted e-mail sent to him about breaking SHA-1, when a loud scream echoes from his office
I JUST SENT OUT MY NEWSLETTER THIS MORNING!
Brought to you also by.... (Score:3, Funny)
http://www.md5crk.com/ [archive.org] (wayback archive)
Just do as federal agencies ave started doing... (Score:3, Informative)
Some background (Score:3, Informative)
This affects all applications using SHA-1 for signature, that is signed email (whether PKIX or PGP), server certificates (which are signed documents). This should be mitigated by the fact that in order to be really usable in some cases, the collision must also be meaningful. That is if you find a collision to a signed email but if it is meaningless, you won't really be able to use it to spoof an email. It depends on the attack quality whether collisions are "meaningful" or not.
Some applications that should not be broken are the use of SHA-1 for key derivation, i.e. where one uses SHA-1 essentially as the basis of a random function to generate deterministic new keys from a pre-shared key. (I think that's what Schneier meant by HMAC applications.)
Also, some short-lived signatures should still not be realistically breakable in the time that they would need to be for an attack to be successful; short-lived signatures are typically used in protocols such as IPsec or SSL for authentication. Additionally, to mount an attack on some of these protocols an attacker would need to generate a collision involving "unpredictable" data coming from another party, which the attack may or may not allow.
Someone set us up the bomb (Score:3, Funny)
Now where did I leave my nukes....
Is it that bad? (Score:4, Insightful)
In order for the time to be something to be concerned about (~10 years), you would need a machine capable of doing 1.87e12 hashing operations per second. Thats 1.87 TRILLION hashing operations per second.
Ah, but what about distributed computing?
Let's assume that there are 1 billion desktop computers working on this project. Then they must be able to do 1870 hashing operations per second. This is a ridiculously large number for today's implementations (mine gets 100 per second, most could do about twice that).
So is it bad? Somewhat. Further breaks could make it worse.
We should move away from SHA-1. But this isn't not the end of the world.
Cryptographic break =/= practical break (Score:5, Informative)
In this case, the researchers from Shandong University (supposedly) reduced the work required to find a collision from 2**80 to 2**69; this is a major cryptographic result. It is major because SHA-1, as a "cryptographically strong hash", is not supposed to have any attacks better then random. A factor of 2**11 reduction shows SHA-1 to be very far from ideal; and since lots of clever people have tried to show this, the research team should be proud.
Does this mean the bad-guy-of-your-choice can now start forging digital contracts? Not yet - there is no guarantee that the collision will be meaningful (as least their earlier papers didn't show that result). For a forgery to be useful, the forger needs to make the fake message say something useful - may be change the $1 to $1 million, or change the name, or something. A collision at a random place (or a non-sensical string) is essentially useless as a forgery (there may be some interested DOS attacks, but I am talking about outright forgery which is the point of the hash functions).
And lastly, 2**69 (roughly 10**21) is still a big number! Assume that some clever people wrote a super-duper hand-optimized code that does a whole SHA-1 in a micro-second on a late model 4 Ghz PC, that is 10**6 hashes/sec. A grad-student using all the PC's on a campus, say ten thousand, that's another 10**4. This would take 10**11 seconds (or roughly 20K years). Note that for SHA-0, their break is 2**39 operations, which *is* practical - it would take the grad student only a minute, or a single PC a week.
This break is yet *practical* for *most* people. (Would I still use SHA-1? Not in new application, and I make sure that existing applications get changed over eventually.)
Lest I be accused of ignoring the big boys, the equation changes for them. If a Three Letter Agency is willing to invest a lot of money and design some cool chips that has awsome parallelism and everything, then each break may take only a week. For example, assume these chips has a bunch of pipes that can do a hash every nano-second (or 10**9 hash/second). Further, say there are 100 of these pipes per chip, 100 chips per board, 100 board per rack (or 10**6 pipes/rack). Each rack can then do 10**15 hash/sec, With such a magical rack, it would take 10**6 seconds (or just under two weeks) to find a collision. This would cost Some Real Dollars, but is it within the budget of some three letter agency? You bet. Hack, I would be willing to sell you one for under a billion dollar US. On the other hand, for that kind of money, cryptanalysis takes on different textures - why spend a billion to crack SHA-1 when you can buy the right wet-ware unit for a million?
Re:Cryptographic break =/= practical break (Score:5, Insightful)
I might be paranoid but it wouldn't be inconceivably difficult for **AA to upload single blocks of corrupted data and destroy every torrent as it streams, they certainly have the resources.
Poly1305-AES (Score:5, Informative)
(This is not meant as a comment on the security of HMAC-SHA-1.)
What do those numbers mean? (Score:4, Informative)
That's 2**11 less operations. Let's say breaking this (2**69 ops) takes the NSA a week. If it had been 2**80, it would have taken 2048 weeks, or 39 years. If it would have taken the NSA (or whomever) a year to break SHA-1 before, it could be broken in 4 hours.
My guess would be it would still take a lot longer than a week - but would now be in the realm of possibility, whereas before it would have been in the lifetime(s) range. However, this is totally a wild-assed-guess, based on the assumption that it was expected to take 100+ years before this to crack.
Important info on crypto hashes (Score:4, Interesting)
First: MD* SHA-* etc - they are all basically the SAME algorithm! The are just minor modifications of the same exact thing, so a break in one is a break in all.
Second: Tons and tons of people ask: can't we merge two hashes together and get a stronger one? Yes you can that's EXACTLY what MD* and HA-* DO! They are a combination of different hashes! That's how they work.
So if you really did have a good combo of hashes then just give them a name and use them as a hash - don't bother just plain merging existing ones.
Also, merging say MD5 and SHA-1 is pointless - they are both based on the same hashing code! You are gaining nothing by merging them.
Well whatever it is... (Score:5, Funny)
unpublished paper reveals unspecified hole (Score:4, Funny)
Let's wait for the actual paper. If it takes more CPU power to force a collision within a year than the whole of what IBM sells in that year, I think that the hash is doing its job...
Re:Hmm (Score:3, Insightful)
Is it so hard to look it up? [wikipedia.org]
Re:Hmm (Score:5, Informative)
Not true. SHA-1 is the hashing algorithm of practically all common security standards. It's found in SSL/TLS, X.509, PGP (the protocol, not the program, so that means GPG also!), S/MIME, etc. In other words... everything. Replacing this is going to suck.
Re:Hmm (Score:5, Informative)
Regards,
Steve
Re:what's left (Score:3, Funny)
Re:Damn it (Score:3, Informative)
Re:Damn it (Score:5, Informative)
Some attacker would have to be REALLY dedicated to use this vulnerability to harm you, and they would still require hideous amounts of processor time to mount an effective attack. Digests are a quick and easy way to verify that some message or file is correct. If the hash is signed as well, then you can verify the sender, too. When you download something like a Linux ISO, there is often another file on the server containing the hashes of the files, so you can verify that everything downloaded correctly. If you want to make sure that nobody other than a trusted person modified the files, then that trusted person could encrypt the digest with their private key, allowing anybody with their public key to verify that everything's correct.
A person can, with a broken hash, create another ISO file, perhaps with malicious code inserted, that has the same digest, meaning you can no longer trust the signed digest. Let's say that this vulnerability reduces the average time needed to find a collision from 2^48 tries via the Birthday paradox (If this isn't a 96-bit hash, then I really need to get more sleep) to 2^32 tries. That's over 65,000 times faster, but you know why I'm not worried? That's still over 4,000,000,000 ISO files that the attacker would have to try before hitting on one that's got the wanted characteristics and the correct digest to boot, and if it requires equivalent memory usage to its time usage, then I'd expect it to use at least 48 gigabytes of memory to store all of the previous attempted hashes. If it takes 15 seconds to compute one digest, then you're looking at a mere 2,000 processor years to find a vulnerability, compared to the much more comfortable 130,000,000 processor years that it would have required using the brute force method.
Feel better now? If I really got mixed up, and was wrong about the size, then just multiply all the listed times by 2^32, and wake me in 8 trillion AD.
Re:And they scoffed at my continued reliance on MD (Score:3, Informative)
RTFA.
Re:And they scoffed at my continued reliance on MD (Score:4, Insightful)
Re:Well (Score:5, Informative)
No algorithm is all-powerful - it only withstands attacks for so long.
No, it didn't. In fact, this is the most important problem in CS. The theory is that there are certainly problems where checking a solution is easy (2 and 3 are unique factors of 6 because it's easy to see that 2*3 == 6) but where the only possible way to find the solution given the answer is to compute the solution for every possible answer.
It's not been proven whether hashing is this type of problem (whether it's NP-complete). Moreover, it's never been proven that there isn't a solution for problems we think are NP.
What's more, it *has* been proven that once we find a solution to an NP-complete problem we'll instantly have solutions for *every* NP-complete problem.
Not necessarily (Score:5, Informative)
In general, we can say that there are infinitely fewer hashes than there are possible data objects you may wish to hash, and therefore there are infinitely many collisions. We can also say that for an N bit hash, at least one collision must occur over a range of (2^N)+1 values for the initial data object.
However, if the collisions occur on a totally cyclic basis, it doesn't matter if there's only ever one within that range. You know where it is, without the bother of looking.
Therefore, the strength of a hash can be measured as a function of two properties:
Bit operations have tended to be used, because they're fast and they allow some control over these two parameters. Other than that, there is no particular merit in using them.
Cellular automata can produce some excellent one-way functions. Their behaviour can also be far harder to predict, if the algorithm is good. However, they are computationally very expensive and getting a usefully strong algorithm is much harder than with bit manipulations.
Transforms are not generally considered one-way, because 99.9% of the time they are only useful because they are two-way. I've not really looked into how transform operations are used in hashes, but they presumably have some strengths.
(Transforms in cryptography, where you want to go from one domain to another and then back again, would make sense. They would also be useful for encryption modes, for generating the new encryption key for the next block.)
Re:Yeah... (Score:5, Informative)
I'm not sure if you are talking about retrieving the original file from the hash, but if you are, then you don't understand what hash functions are for. In this case, there are an infinite number of combinations of bytes that have the same SHA-1 hash. The goal is to find one that has the same hash value, regardless of whether it is actually the same file. SHA-1 is not a cipher.
Re:My Research team broke RSA! (Score:3, Funny)
Re:Broken or not? (Score:3, Funny)
Re:Start recoding (Score:3, Funny)
One more crippling bombshell hit the already beleaguered cryptohash community when IDC confirmed that cryptohash market share has dropped yet again, now down to less than a fraction of 1 percent of all cryptographic algorithms. Coming on the heels of a recent Netcraft survey which plainly states that SHA1 has lost more market share, this news serves to reinforce what we've known all along. SHA1 is collapsing in complete disarray, as fittingly exemplified by
Re:So the concern is..... (Score:3, Informative)
SHA1 is not 'broken' in any real sense. Someone claims to have reduced the collission rate to 1 in 2**69. That's still bloody small. It'd take your PC a couple of thousand years to check the hashes to generate a collission.