Slashdot Mirror
SHA-1 Broken
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."
And I just got done upgrading from MD5.
For those interested, here is the actual detailed/lengthy FIPS PUB 180-1 from NIST, as typical, Wikipedia has a nice summary, and the W3 Folks have a short snippet ...
I'm not sure if this post is news or what, but for more info, click here:
http://www.itl.nist.gov/fipspubs/fip180-1.htm
A lot of companies and products use SHA1 in some form or another. Does this mean that we can arrest and imprison these "researchers" if they ever step foot in America?
Time to change the VPN policies
... to SHA-2!
If you don't switch to the newest, latest hashing algorithm, you will die horribly when your corrupted emacs RPM performs malicious code!!! Everyone, delete everything and log off of the Internets now!!! We're all gonna die!!! HELP!!!
"Anyone who attempts to generate random numbers by deterministic means is living in a state of sin." -- John von Neumann
Same group of people that found the MD5 Hash Collision. Self references and the MD5 paper.
Steal This Sig
This may be a big deal, because if I understand correctly, SHA-1 is a similiar algorithm to MD5, which is commonly used to uniquely identify files. If that could be cracked using a similiar technique, a better method of hashing files may have to be found.
thisnukes4u.net
/me /me wishes security were easier
Log into VPN Firewall
Check VPN settings
Notices SHA for authentication type
Swears
Checks other option, notices {none} and {md5}
scratches head
decides to go with MD5 until that too is broken
There are 4 boxes to use in the defense of liberty: soap, ballot, jury, ammo. Use in that order. Starting now.
With SHA-1 being MD5's replacement after that was broken, which hash function do we use now?
boldly going forward, 'cause we can't find reverse
It's a hashing algorithm - SHA stands for Secure Hashing Algorithm.
Is it so hard to look it up?
wait a sec....no MD5 and no SHA-1. what is going to take the place of those things? something like anubis or whirlpool?
maybe more people will use GPG now!
Keep the faith, share the code
SHA-1 Hash Algorithm and Source Code.
Creative Demolition
...at least we still have SHA256, SHA384 and SHA512.
That said...PWN3D!!1!
You can hold down the "B" button for continuous firing.
If your system has an md5sum command, it will also have a sha1sum command. Same idea, different output: feed each of them a file and they will give you a hash of that file that fits in 128-bits (md5) or 160-bits (sha1).
In practice, no two files (or period of a data stream) will have the same signature. Hashing algorithms are used in data integrity checks and authentication.
An sha1 crack likely means that they found a way to make tampered data still hash to a desired value, maybe.
sha1 and md5 are generally considered so weak that they should only be used to combat error or accidents, not fraud.
Long live ROT-13.
Maybe crackers would stop messing with our encryption if it was extremely easy to deal with.
SupahLeetCodah: d00d i just cracked SHA-1 and MD5,6 AND 7!!!1
Steve: So did my grandma and my proctologist.
ItWasFree.com - Take the mystery
Is it time to update bittorrent?
How hard is it going to be for people to provide garbage data with correct SHA-1 hashes to screw up downloads?
Rats would be more funny if they could fart.
Fucking Google It
One collision in 2**69 operations... that's quite minimal...
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.
Ya.. 20 years ago we used a hashing algorithm at college. Not sure how secure it was but we got really messed up.
Doest not affect HMAC. So it does not affect IPSEC and WEP.
RTFA.
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!
Of course they're not supposed to be all-powerful, but considering details as to how exactly the algorithm is broken are not available, I'm quite interested as to how they broke it.
I'm particularly worried about BT users, personally. The breaking of SHA-1 will essentially allow the RIAA and others to corrupt many bittorrent downloads.
oops I accidentally highlighted 'fucking' from your post instead and searched for that
I am outraged! Does this disgusting thing called 'fucking' really happen ? I must know.
Is SHA-1 used in x509 digital certificates, and if so does this mean that people can forge digital certificates ?
If someone can do this, then what are the liability concerns for certificate issuers (or even their customers) ?
Well, no. Not exactly. SHA-1 is supposed to be a one-way function, meaning that you can't just reverse the operation. So you can't just "crack" it like solving an equation.
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.
www.timcoleman.com is a total waste of your time. Never go there.
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.
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
No, that would be one application of a hash (and not a very good one, because someone wanting to mess with it enroute could just re-hash the doctored version and pass on the new hash. What you discribe could be a way to check for accidental errors, though.). A hash is a function that given data gives a smaller amount of data. This smaller amount of data is then also called the hash of the origonal data. A good hash function has the property that if you know the hash for a file, you shouldn't be able to come up with another file that has the same hash without a prohibitive amount of work. A hash function is broken if this property stops holding.
This post written under Gentoo-linux with an SCO IP license.
Finding a single collision after a huge search isn't the same as being able to generate a collision on demand, which is what the SHA-1 breakage apparently purports to be.
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!
Slackware, what else when it must be secure, stable, and easy?
And it's elegant. But it won't fit in the margin of a post on slashdot.
7 November 2006: The day Americans realized corruption and incompetence weren't addressing 11 September 2001
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.
main(c,r){for(r=32;r;) printf(++c>31?c=!r--,"\n":c<r?" ":~c&r?" `":" #");}
Fucking Google It
We cannot reasonably move to H(x)=MD5(SHA-1(x)). If you have a pair x, y such that SHA-1(x)=SHA-1(y) (i.e. a collision of SHA-1), then MD5(SHA(x))=MD5(SHA(y)). So H(x)=H(y) (a collision of H).
But don't worry (yet). There's still no known practical way to produce SHA-1 collisions.
I love how you link that like you're mister high and mighty and you don't spell his name in the link right. I didn't either, but I have ethos. I'd never heard of him before. =)
ACs are modded -6. I don't read you, I don't mod you, I don't see you. Don't like it? Don't be a coward.
The MD5 crack team....
http://www.md5crk.com/ (wayback archive)
Clinton signed a bill that ceased the definition of cryptographic algorithms as munitions. Now there is no strength requirements, checking by the NSA, nothing. Like since 96.
Where've you been?
THIS THING CAN TURN ON A DIME, MACROSSZERO STYLE ALSO FUCK BETA, ~NYORON
So even if the SHA-1 family is flawed for the reason given in the article, all is not lost since they just reduced the work by a couple of orders of magnitude. If you go to 256 bit or 512 bit hashes, you're definitively going to be safe for much, much longer (since even if the given attack works twice as good for 512 bits, you would need many more centuries to try out the same percentage of the keyspace).
However, the real problem is that todays OpenSSL and libgcrypt (gnupg) libraries don't even have support for SHA-2 (I just tried to find it). So it will actually take quite a while before this can be adopted. And that's the real problem.
Check this article: Federal agencies have been put on notice that National Institute of Standards and Technology officials plan to phase out a widely used cryptographic hash function known as SHA-1 in favor of larger and stronger hash functions such as SHA-256 and SHA-512.
It is official; Netcraft confirms: SHA1 is dying
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 failing dead last in the recent Sys Admin comprehensive cryptography test.
You don't need to be a Kreskin to predict SHA1's future. The hand writing is on the wall: SHA1 faces a bleak future. In fact there won't be any future at all for SHA1 because SHA1 is dying. Things are looking very bad for SHA1. As many of us are already aware, SHA1 continues to lose market share. Red ink flows like a river of blood.
SHA1 is the most endangered of them all, having lost 93% of its core developers. The sudden and unpleasant departures of long time SHA1 developers Jordan Hubbard and Mike Smith only serve to underscore the point more clearly. There can no longer be any doubt: SHA1 is dying.
Let's keep to the facts and look at the numbers.
MD4 leader Theo states that there are 7000 users of MD4. How many users of MD5 are there? Let's see. The number of MD4 versus MD5 posts on Usenet is roughly in ratio of 5 to 1. Therefore there are about 7000/5 = 1400 MD5 users. SHA2 posts on Usenet are about half of the volume of MD5 posts. Therefore there are about 700 users of SHA2. A recent article put SHA1 at about 80 percent of the cryptohash market. Therefore there are (7000+1400+700)*4 = 36400 SHA1 users. This is consistent with the number of SHA1 Usenet posts.
Due to the troubles of Walnut Creek, abysmal sales and so on, SHA1 went out of business and was taken over by RSA who sell another troubled cryptohash. Now RSA is also dead, its corpse turned over to yet another charnel house.
All major surveys show that SHA1 has steadily declined in market share. SHA1 is very sick and its long term survival prospects are very dim. If SHA1 is to survive at all it will be among cryptographic dilettante dabblers. SHA1 continues to decay. Nothing short of a miracle could save it at this point in time. For all practical purposes, SHA1 is dead.
Fact: SHA1 is dying
Applications that would be broken by this are long-lived cryptographic signatures. Indeed, when a document is "signed", usually only a hash of the document is signed. Finding collisions means one can find two different documents with the same signature.
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.
Had to happen, didn't it?
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.
... it looks to me the only solution is wipe Jinan city off the map.
Now where did I leave my nukes....
"can we reasonably move to H(x)=MD5(SHA-1(x))?"
No. The composition of two compromized functions isn't going to solve anything.
sha1 and md5 are generally considered so weak that they should only be used to combat error or accidents, not fraud.
:(
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.
Factoring the public key for signed XBE files might now be the best option in running arbitrary code (i.e. Linux) on unmodded XBoxes.
5 5993606274 88352673195511324110900735 43623741289960962910463535723067421103054569468248 62203867115042369878729703 47576511228016749818904643779460296616881241942336 51969796694319295889511268 04648743029387833666031765734337165949634731375592 47167029424618087781510481 26746269674500970450051175466570687005452630641050 24888769118032059917845867 65304041940400368455988250919539863092282405040537 96205135896999939802056942 66973236095772153476388267418476533663512746243310 31785386194643005307289050 29493197037650237921611449426113236294444096001738 94963797156859916567288947 565058003
Have: Public key (it's inside the Xbox kernel), in decimal:
207401193272587237602760235090630171384
That's not what's been broken. It's impossible to get the cleartext from a hash - that's why it's called one way (there are an infinite number of cleartexts which can generate that hash, so in theory you can get it, but you've got a 1/infinity probability of picking the right one...)
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.
Of course if you had a big enough cluster you could get that down to a year or two I guess.
Man in the middle attacks are *not* what this is about.
Maybe his sense of humour fell through a one-way hash function some time back, but it's pretty clear from context that he's kidding.
--MarkusQ
Now I know why my site doesn't work anymore. SHA-1 is broken. Digest::SHA1 won't produce any hashes for me anymore, and I tried to debug the issue but couldn't work out what was going on. Thanks for letting us know SHA-1 is broken Slashdot. I wonder when it will be fixed?
That any algorithm is vulnerable to brute-force attacks is totally uninteresting. It's a given in cryptography that given encrypted data, you can try all the possible keys, or re-hash lots of data, until you find one that works. It's up to you to pick a key long enough that it will take anyone else an impractically long time to crack it.
Now, that has nothing to do with this article. These guys are alleging that SHA-1 can be defeated significantly faster than brute-force. This would be a defect in the algorithm and potentially a bad thing. So did this "have to happen"? No, absolutely not. Some algorithms are provably secure for certain purposes.
I'm not a smorgasbord.
Realistically, if I gave any of you people a .txt file encrypted with DES and said that if you can crack it in 3 months I'll give you $15k.. would you be able to? I rather doubt it.
2^69 is still a plenty big number for me. I'll worry in a few years when CPUs are faster
It never fails to crack me up how people freak out about theoretical weaknesses in cryptography but have $25 locks on their homes that any crook with a fork and a nail could open.... and steal your computer if not axe you to bits.
but, but.. SHA-2 will save me!!
CommentBot 0.7a running with args "-module irritate,disagree -target random"
The article says that 2**69 hash operations are needed to find a collision. If you have a SuperHashOMatic that can do 1 Billion hashing operations per second, thats still an average time of about 18700 years.
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.
Note that what cryptographers consider a "break" is not necessarily the same as what users consider a break. (Neither is more strict, they are just different criteria for different people).
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?
.... So these hashes are still good for uniqueness out to 2^32 size fingerprints?
What's the best hash for file fingerprinting, for stuff like version databases, tripwire, etc?
Surely you mean 'unhashed' values, not value. A 160-bit hash value can map to about 4 billion 'unhashed' values of length 192-bits - good luck finding the right one :-)
No. SHA1 can still not be reversed, they found a COLLISION. That is, with 2^69 tries, they can come up with a value that will have the same SHA-1 hash as the password.
For passwords, this is nearly meaningless.
For digital signatures, it's a different thing.
It's gone from being a billion times easier, to a half a billion times easier, to just simply find the person responsible and beat any necessary data out of them with a baseball bat and/or knife. Which is cheaper? Extensive studying of cryptography, thousands of dollars of computers, and an extremely long waiting time in order to brute-force something? Or just buying plane tickets, a blunt object, looking up the person's address on MapQuest, and having Cousin Luigi pay a friendly visit?
Pretty fucking hard. The NSA doesn't lend out CPU time on classified supercomputers to anyone but a select few government organizations. As much as I think the congress and various others are in cahoots with the RI/MPAA, the NSA would probably not stand for such a thing.
Relax... it still takes 2^69 tries. That is 590,295,810,358,705,651,712 hash operations. To brute force sha-1 it takes 2**80. This is only 2**11 times faster then a brute force attack... thats 2048 times faster. Its significant but it's not that big of a deal. It is no more significant then if someone with a 2000 node cluster tried to brute force your hash (which is completely feasible...especially for large government agencies like the NSA). In other words, if you were capable of performing 1 trillion (1,000,000,000,000) hash operations per second, it'd still take nearly 19 years for a collision to be found. I assume the NSA can knock that number down to under 24 hours, but thats expected of them. For anyone else in the world, assuming your not being followed by the NSA... and god help you if you are... sha-1 will still be fine and the entire internet security infastructure will not need to be redesigned.
Regards,
Steve
I think the point here is not that collisions exist, but that there is now a way to generate a collision reliably with fewer operations.
But as said earlier - not only must a collision be generated, that collision must be meaningful. A good example was that while it might become easy to generate "collision" data for a gzipped tar file's hash, it would still be extremely difficult to generate a collision that had the following properties:
Understood by gzip without errors
Understood by tar after gunzipping
Had meaningful files after being untarred
retrorocket.o not found, launch anyway?
What someone really ought to do is use ROT-7.5 twice to decrypt ROT-13.
Si la vida me da palo, yo la voy a soportar Si la vida me da palo, yo la voy a espabilar
both papers were (IIRC) generate two datasets X and Y with the same hash Z
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.
Snowden and Manning are heroes.
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.
(This is not meant as a comment on the security of HMAC-SHA-1.)
I have barely any cryptography knowledge, but would the SHA series be any safer if the size of the data was part of the signature? From glancing over Bruce's post (and remembering how MD5 and others were broken), data has to be padded. You can't just change arbitrary bits and produce the same signature. So, couldn't you just add the size of the file to the signature? Does that decrease security, because the size is now known?
It would greatly add to the security in theory except that it wouldn't really work well in practice. I am not an expert on cryto algorithms but the limitations of this approach can be seen even without knowing anything about the actual has algorithm.
The trick with forging messages is that you need to add some amount of garbage to the forged message to make it match the hash of the original (there are other ways in theory that are likely to be less practical). This is why the length inforormation would appear to help. Then you have to disguise the purpose of the garbage so it doesn't draw attention to itself. Perhaps as another fake signature or an uncompressed image. Steganography would give you the requisite number of bits while still letting you include an image (of a hand written signature, a document page, or a company logo)that wasn't obviously junk but the bits would not be consequtive which makes it harder). Instead of hiding them in low order bit steganography, you could replace a number of consequtive pixels; the result would be visable but would be mistaken for a smudge. By including the length in the signature, you make it much harder to make a message that says what you want it to say and still matches the hash.However, the problem with your suggestion is protecting the new size information. If you include the size in the message before hashing, then you simply search for a hash that matches the forged message with modified size which could be about the same amount of work as forging in the first place for a brute force attack though it may well add additional constraints that might prevent taking particular shortcuts vs. a brute force attack in which case it would help. It would really depend on whether the hash crack is bothered by this constraint. If the crack algorithm knows in advance how many extra bits will be generated then running the length through the hash doesn't help at all. If you just add some message size bits to the end of the hash, then the information is unprotected and can be changed to match the message. So, you probably would want to sign the length separately. But if you are going to do that, you could use a hash with twice as many bits in the first place or hash the same message twice with two different initial values for the hash (cracking the first hash may or may not provide a shortcut to cracking the second). Both of these approaches would probably be much more secure than adding the length. Even more secure would be to hash the message with two different hash algorithms.
There are also ways of returning to the original message length even when adding garbage. Suppose I want to change a contract to say you will pay me $100,000 instead of $10,000. To make room for the extra hash fooling bits, I can delete an entire paragraph from the contract that is of no importance to me (or even makes it more favorable to me by its absence). Longer hashes or double hashes would effectively prevent this but length information would not.
In my opinion, a "real world" attack would be one which given a blob which has already been hashed, would come up with another blob which results in the same hash. To my knowledge, nobody has any useful attacks in that direction yet, although some would argue based upon this research that it may just be a matter of time.
Then we of course need to get into whether that is really useful either. If I find out that and results in the same hash, how helpful is that to me? How is a lawyer is going to prove to a jury that I may have actually signed the garbage instead of the purchase agreement? So, there is even more work to be done to make it a useful real world attack, wherein you might take the original signed text (modified for your evil purposes), append a null character, and then add garbage until the hashes are equal--and hope the UI was poorly written and just displays up to the first null.
Check out our infosecurity industry blog: http://securitymusings.com/
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.)
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
They reduced it from 2**80 to 2**69. And the paper hasnt even been released yet so noone knows if that is even accurate.
Regards,
Steve
I read on one site - in answer to the question "What's the big deal - is 2**69 really all that bad?"
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.
This sig donated to Pater. Long live
Same researchers announced some vulnerabilities in MD5 and SHA-1:
f p;512;fpid;710205681
3 8
See:
http://www.arnnet.com.au/index.php/id;1503863220;
Researchers have discovered a flaw in the MD5 algorithm that is used to provide a unique signature for data.
Xiaoyun Wang, a Chinese expert, and three colleagues have discovered the flaw in the hash function algorithm, which is used in applications, such as EMC's Centera content-addressable file store. The flaw was revealed at the Crypto 2004 conference.
Also:
http://www.rsasecurity.com/rsalabs/node.asp?id=27
* The hash function collisions recently discovered have minimal practical impact at this time due to the limitations discussed further. It is not clear that these research results can be turned into practical exploits on most typical uses of these hash functions, so there is no immediate need to replace hash algorithms.
* As a precaution, applications using a legacy hash function described as vulnerable should upgrade to the NIST-approved SHA1 or SHA2 family of algorithms (RSA Laboratories suggested a migration to SHA1 in 1996).
* Applications using SHA1 do not appear to be at risk, but conservatively, developers may also consider planning an upgrade to the SHA2 family in the next few years.
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.
Your example doesn't really make too much sense, and your definition of NP-complete is purely wrong. There are easily demonstrable problems that are not NP-complete where you have to compute the solution for every possible answer, because they are not even in NP to begin with. Example: "If I removed a city from a set of cities in the traveling salesman problem, which city removal would cause the largest reduction in the shortest path length?" In this problem, each possible "answer" (to use your terminology) is NP-complete, thus yielding a non-NP and therefore non-NP-complete solution (unless P==NP).
Furthermore, an NP-complete problem is not unsolvable as you state -- in fact, to be labeled as NP-complete, a solution has to be known. The solution must be formed in terms of a polynomial-time "reduction" from another NP-complete problem. To be NP-complete means merely that the only known solutions would require a non-deterministic "computer" to solve them in polynomial time. As we don't exactly have such machines sitting around, we have to rely on non-polynomial solutions.
Now if we can figure out a way to compute an NP-complete problem in deterministic polynomial time, then all NP-complete problems will be able to be solved in deterministic polynomial time (since all NP-complete problems are declared NP-complete by relating them to each other). But there was always a known solution.
No, it didn't. In fact, this is the most important problem in CS.
Nahh.. The most important problem in CS are those annoying campers.
I am not a cryptographer but shouldn't it be possible to use MD5 and SHA-1 for the same piece of text together. How likely is the hash sum for a particular text to be cracked for both the algos and have the same modified text. Will it make it a bit more tougher to be cracked?
No. Hashes like SHA-1 are lossy; there is less information in the hash than in the plaintext. Lost information like that cannot be recovered unless just about everything we know from information theory (and thermodynamics) is wrong.
All's true that is mistrusted
What you have to figure is that with any hash thats shorter than the max amount of data, then the possibility of collisions will occur;
figure that if you could represent every possible combination in 128 bits, you would never need to have 129 bits of data.
Because this is not true all hashes will have collisions. However the chances of multiple hashes all having collisions with altered data is 'pretty damn slim'. So therefore the best solution, most likely in the future, and presently is to authenticate messages, identification (ala ssl certificates**) and binaries with multiple hashs known to be reasonably strong. One doesnt need to be a cryptologist to realize that using something like md5, sha256 and like ripemd160, the chances of collision in all 3 hashes are quite slim, and within the range of acceptable risk.
A better idea is to use UUIDs, where these problems have already been considered, and systematically handled. On Linux, just read from /proc/sys/kernel/random/uuid.
as long as they show the results, it can be verified.
in theory, given a hash number, it takes centuries to find the collision.
given the hash number, if you could come up with a collision in days or even in months on your PC. that means you break the code.
in order to believe it is broken, you don't need to know the details of the alorithm.
sha1 and md5 are generally considered so weak that they should only be used to combat error or accidents, not fraud.
Do you have any evidence for that? SSL, PGP and NTLM all depend on them, as far as I know.
More than 6 months ago, papers were going around telling people to 1. Stop using MD5 as a secure checksum immediately, and start moving away from SHA-1 as it's security was becoming more vulnerable by the day. Researchers reccomended moving to SHA-256 to prevent accidental breach of data security (sooner, rather than later). There have been many different cracks involving SHA-1 (albiet simplified versions, but you just knew more would eventually be coming). Well it's here now! SHA-512 here we come!
Explain to me why this isn't useful for compression?
I know it's next to impossible to create the data from the hash but shouldn't it be theoretically possible?
If the hash reduces the possible files which match it by 99.999% then shouldn't it be possible to send that much less data?
I'm actually working on an app that was going to use SHA-1 for integrity verification. I may just stick with SHA-1 because I'm not terribly familiar with the other options out there in this realm. So ideally, what should new apps use these days? What would be the recommended "safe" algorithm? And can I find a nice, tested C library/code for it? :-)
Hexy - a strategy game for iPhone/iPod Touch
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.
Looking for an Information Security student project suggestion?
Try http://dotcrimeManifesto.com/
That is nothing. This post has been encrypted with an unbreakable one-time-pad! TWICE!
For password hashes this attack shouldn't be a problem, if it is as described in the article. The attack does only one thing: allows an attacker to generate two streams of data which hash to the same value. This is a problem for digital signatures, because somebody can sign one data stream, then distribute another with the same signature. So the signature doesn't guarantee the data has not been modified
Even for signatures, it depends on the application. There are two types of collision resistance:
- Weak collision resistance: Given x, I cannot coumpute y s.t. H(x)=H(y)
- Strong collision resistance: I cannot compute arbitrary x,y s.t. H(x)=H(y)
Usually collision results show that a hash algorithm is not strong resistant.
So if I want to create random data (a nonce) and sign it there is a problem, I can create x,y with the same signature. However if I want to sign something specific, say an email, then I have to break weak resistance, random x,y won't do since x is unlikely to be the email I wrote.
I guess I missed posting this before the bulk of the posts, but maybe it'll help someone.
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.
-Ariel
Why not make two hashes of a password using different algorithms, one using MD5 and the other using SHA-1. If an attacker was able to produce a password where the hash matched one it would be very unlikely to get the correct hash using the other algorithm unless the attacker had found the original password.
I hope they get it fixed soon.
If you have "openssl" installed, you could also use openssl to generate the hashes. (supported hashes)
For md5 hashes:
$ openssl md5 filenames...
Output: MD5(filename)= hash
For sha1 hashes:
$ openssl sha1 filenames...
Output: SHA1(filename)= hash
Ok, if my file consists of the line "Hello World." then I get the following hashes:
1 7c 971f1b1b667e0732944df7
770b95bb61d5b0406c135b6e42260580 for MD5
b924c2f360b572e17c971f1b1b667e0732944df7 for SHA-1
Trying to tinker around with the file and make both hashes come out the same as above would presumably be much more difficult than for any single hashing algorithm, and it might very well be nigh impossible. The little light bulb has finally come on. Now I get it. Yeah using two hash algorithms together would probably work nicely. Don't combine the results mathematically, just append the keys together into a big long string. The final MD5+SHA1 hash key for my file would be:
770b95bb61d5b0406c135b6e42260580b924c2f360b572e
I don't know whether this would be stronger than a SHA-2 of equivalent bit length or not, but now I get what some of you have been saying. From a common sense view, it would seem that something like this would be pretty darn tough to crack, because you would have to make two different algorithms compute matching keys for a given dataset.
Clickety Click
Maybe we should start encoding meta-data along with the hash, so instead of trusting only on the hash to confirm that the message is from who sign it, we would encode along the message, the size, type and whatever characteristic could define the message.
For instance, suppose I sign the message "Hi, I'm Victor", along with the hash it would contain the size (14 bytes), type (English text), encoding (7bits ASCII) and how about the range of codes used in the messages (from U+0027 - U+0074).
A good hash would give a uniformly distributed random hash for the message, so it is safe to assume that even if we could find a collision, it would be highly unprovable that it would satisfy all the meta-data. In some cases it could be provable that this kind of hash is unbreakable, since there is a finite number of messages that satisfy the meta-data (if you could hash all possibilities and verify that there were no collisions you're 100% safe).
[]'s Victor Bogado da Silva Lins
^[:wq
To nit-pick further, the pigeon-hole principle says nothing about not reusing any slot. It states that if you place n items in to n slots, either every slot is filled, or (at least) one slot has more than one item.
Equivalently, if there are n+1 items, there must be a slot with more than one item. Your statement is a special case of the principle, but not as general.
It is possible to prove (by induction) that there are an infinite number of collisions for some hash value using this. However, proving that collisions exist for every hash value requires detailed knowledge of the algorithm, and doesn't follow directly from the pigeon-hole principle.
That's an awfully vague term. We've got an Ethernet hub with a corner knocked off its case, so theoretically you could say it's "broken", but it still works as well as it ever did. A lot of cryptologic results are like that: we know more than we did before about X, but X is not suddenly rendered useless or even worrisomely less strong. Whereas, in the movies, "we broke their code" generally means, "we have the key and can read their secret messages as quickly and easily as they can."
Now I can type a simple password, and produce a complex password that has the same hash.
I'd type the complex one "32l;lkd49fj32*93f-FR" just once: When I create my account on the web site that demands that I have at least 8 characters, and some of them must be numeric and some must be non-alpha and so on.
After that, I can just type my usual "foo" as password and it'll accept it because the hash fits.
Huray.
Musicians don't die. They just decompose.
This doesn't seem likely even with my tinfoil hat mode fully engated.
If we were talking about an encryption scheme, the temptation would be there. If it were and encryption scheme adopted by The Bad Guys (tm) then NSA would of course be able to read their secret communications.
But that's not what SHA is for. It's to allow a piece of data to be authenticated. You can satisfy that that this file is indeed from me based on a simple number computed from it and a secret we both share. When thegovernment procures a piece of software that is going to do something like launch nuclear missiles, it would be nice if that software could figure out whether the order really came from PotUS. On the other hand, when the order comes from Osama to fly the plane into the WTC, authentication of that order, while useful, is not as critical.
So, the national security interests here are clearly in favor of their being a publicly available, secure hash function.
Post may contain irony: discontinue use if experiencing mood swings, nausea or elevated blood pressure.
As others have pointed out, I can create 2 documents, X and Y, have a target sign one, then substitute the other. His digital signature will be valid for both. Great - it takes only 2^69 attempts to get a collision - I'm sure the chances that the X and Y found will both be valid English documents, one of which I could convince a target to sign, the other allowing me to scam him out of enough money to make the whole ordeal worthwhile.
However, people keep copies of what they sign. Even if I did find a collision, and even if both documents were valid English text, the guy could say "I didn't sign Y - look, my signature is valid for X - he scammed me". Great.
The more likely scenario is someone signing their own document, then claiming it was fraudulent. They could create their own X and Y, sign X that somehow involves another party, then claim they actually signed Y and this other party was the scammer. But they still have to find X and Y in 2^69 steps such that both make logical sense in the English language - no simple task.
This is cool in a theoretical sense, but in a practical sense, its like saying you don't need a million monkeys on a million typewriters typing for a million years to generate Shakespeare; it'll only take 999,999 monkeys on 999,999 typewriters...
Or, to go back to the theoretical world: with processor speeds doubling every 1.5 years, and this team shaving 11 factors of 2 off of the break time, the lifetime of SHA-1 just shortened by about 16.5 years. Not quite the end of the world as we know it.
Step 1: Break SHA-1
Step 2: ?
Step 3: Profit!
At least they gave the algorithm. If their synopsis is indicative of the paper, they illustrate that SHA-1 has collisions, and collisions can be discovered through the awesomely sophisticated technique of brute force. Pardon me while I dust off my bomb shelter.
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...
I am no longer wasting my time with slashdot