Re:Don't panic! 'Broken' is not Cracked
on
SHA-1 Broken
·
· Score: 2, Insightful
Humm, no.
Differentials in SHA-256 can be found with the new techniques.
The problem is with the new differential attack our Chinese friends discoverd. Fidning differentials through addition mod 2^32.
SHA-256 uses the same. For now, yes, it's safe. But as of right now, the crypto community is hugerly trying to build new hashs with more complex compression function chaining. Whirlpool is an example of this newer view on hash functions.
It's based heavily on AES's core operations which would make me feel uneasy. Diversity in the underlying techniques for crypto algos is exemplified here by how just about every hash we use today fell because of a lack of diversity.
In short:
- Use SHA-256 for now.
- In 2-3 years, upgrade to whatever becomes the standard, it'll be stronger than SHA-256
My cell phone provider (Fido.ca) gives me 150 free email messages a month which I can send out from my basic SMS enabled phone. I format an SMS just right and it'll turn into an email. I send this email to my an aliased email address on my home machine which pipes it into a perl script. I can request weather information, system uptime, etc. And yes, I can download the slashdot XML news page and parse it up, tokenize it into emails 160charactors long and EMAIL it back to my cell phone.
"new SMS to 003436". "CMD S" for slashdot news command. 10 seconds later I get 2-4 SMS messages giving me the slashdot headlines. I've done this from a cottage, a highway coach, toilets in dingy bathrooms.
The Moon is a gravity well. To fall into the well, you must then climb back out. You effectivly need to bring with you fuel to:
a) leave earth orbit - which accounts for over 75% of current lift-off mass of space shuttle (even more for Saturn V)
b) Burn fuel for a safe landing on the moon
c) Burn more fuel to leave Moon orbit
d) Burn still more fuel for a safe landing on Mars
e) Burn yet still more fuel to leave Mars orbit
f) Burn yet still again more fuel to slow down for a safe landing on Earth
The Saturn V was a "cockroach strapped to a gas can" to begin with. And that was for a Lunar trip that crashed into the Earth. You want to do this 3 times you say?
Modern hash functions use a compression routine on buffered data to produce a hash. This compression function is performed repeatadly on - say 512 bit - blocks.
Dobbertin found a collision in the MD5 compression function. This is not the entire MD5 hash which includes padding and length added in the final compression.
The "term" significant is relative. If a mathmatical algorithm is 100% slower when dealing with purly CPU bound data and in real-life you use it on I/O bound data - I don't consider it to be significant.
10mins producing 1000's of hashs of files vs 13-15mins isn't going to kill you IMHO.
3DES is 200% slower than DES (1 + 200% == 3). Yet people have accepted that penalty. Why not 50% or 100%?
For the record - if you're really sensitive about performance and not concerned with cryptographic level of security - you should be using MD4 which is faster then MD5 and provides 128 bits of hash.
Google for MD4 collisions, you'll see people have infact inverted MD4 for certain inputs.
Almost forgot your comment about speed. SHA-1 is slightly slower then MD5. SHA-256 is slightly slower then SHA-1. SHA-384/512 use 64 bit operations so it is much slower on 32bit systems. In short, you concerns about speed are unfounded. Read on.
Run this command:
openssl speed md5 sha1
I get:... The 'numbers' are in 1000s of bytes per second processed. type 16 bytes 64 bytes 256 bytes 1024 bytes 8192 bytes md5 13426.71k 46361.18k 124663.83k 222340.64k 286203.62k sha1 11175.12k 30058.96k 69783.42k 104107.06k 121809.96k
I also ran "time md5sum file94mb" and "time sha1sum file94mb" file 3 times in succession. The performance is much closer.
a959b7de4f11fe89ba57ecc6fe2f6a07 file94mb real 0m1.070s user 0m0.860s sys 0m0.060s
a959b7de4f11fe89ba57ecc6fe2f6a07 file94mb real 0m1.070s user 0m0.850s sys 0m0.070s
a959b7de4f11fe89ba57ecc6fe2f6a07 file94mb real 0m1.071s user 0m0.810s sys 0m0.110s
5d926755ef975a8900b89b514feac9ded29c4477 file94mb real 0m1.538s user 0m1.260s sys 0m0.060s
5d926755ef975a8900b89b514feac9ded29c4477 file94mb real 0m1.524s user 0m1.270s sys 0m0.040s
5d926755ef975a8900b89b514feac9ded29c4477 file94mb real 0m1.520s user 0m1.280s sys 0m0.030s
The argument boils down to this:
- A cryptographic hash function must to meet three criteria: non-invertible, 1st image collision resistance (given m, finding m' such that h(m) = h(m')) and 2nd collision resistance (finding m and m' such that h(m) = h(m')).
- There are some applications where 1st or 2nd collision resistance is not required - file integrity, web certificate verification and several others are not one of them.
- If I can find over $100,000USD worth stealing by producing a collision in MD5 (inspect your bank's website certificate, most US firms use MD5) than it's a business proposition, not an egghead research idea.
- Is a 56bit key secure? Bet you can't find the one I'm thinking of in the next 24 hrs. Is a 128bit hash secure when its effective strength is 64 bits? If you're a bank, no. If you're joe slashdotter, yes.
No respectable cryptographer uses MD5 for signatures anymore, they havn't for years - the industry hasn't caught up yet (TripWire, VeriSign,.rpm,.deb, md5sum, some PRNGs, etc)
This is the essance of why I'm doing this.
Look around for evidance of this movment in crypto circles (ie don't listen to/. posters...:) )
read the sci.crypt post, I site a paper from van oorschot from 1994 describing exactly how to get MD5 collision. In today dollars/moores law, it would cost $100,000....anyone with good credit can find collisions in MD5.
Slashdot Mirror
link http://groups.google.ca/groups?q=author:cooke+sha- 1+2005&hl=en&lr=&selm=2IwkQ-2gU-1%40gated-at.bofh. it&rnum=1
Should have listend to me.
h a- 1+2005&hl=en&lr=&selm=2IwkQ-2gU-1%40gated-at.bofh. it&rnum=1
http://groups.google.ca/groups?q=author:cooke+s
I said SHA-1 would fall around now.
Humm, no.
Differentials in SHA-256 can be found with the new techniques.
The problem is with the new differential attack our Chinese friends discoverd. Fidning differentials through addition mod 2^32.
SHA-256 uses the same. For now, yes, it's safe. But as of right now, the crypto community is hugerly trying to build new hashs with more complex compression function chaining. Whirlpool is an example of this newer view on hash functions.
It's based heavily on AES's core operations which would make me feel uneasy. Diversity in the underlying techniques for crypto algos is exemplified here by how just about every hash we use today fell because of a lack of diversity.
In short:
- Use SHA-256 for now.
- In 2-3 years, upgrade to whatever becomes the standard, it'll be stronger than SHA-256
http://jlcooke.ca/oclug/oprimes.c
Give this a whirl. Cross platform (afaik). Send feedback to: jlcooke@certainkey.com
Encryption of files using AES128-CBC, no MACing sorry.
Key used for encryption is:
key = SHA256(pswd)
Password verification is stored as: {pswdEnc, pswdHashEnc}
Where pswdEnc = AESEncrypt(key, key)
pswdHashEnc = AESEncrypt(key, HASH(key))
Provided password "test" is considerd to be the orginal "pswd" if:
key' = SHA256(test)
t1 = AESDecrypt(key', pswdEnc)
t2 = AESDecrypt(key', pswdHashEnc)
t2 == SHA256(t1)
It's written in Java, so no promises about memory attacks (I did my best). But at least file-based attacks are much more difficult.
JLC
bork bork bork? That's sweedish.
That's fun is the Muppetizer that was on the www.muppets.com website before the evil Disney took it over. I have a copy of it here.
Even funnier are the swear words they replaced!!!
http://www.certainkey.com/md5challenge/
The creators are welcome to apply.
My cell phone provider (Fido.ca) gives me 150 free email messages a month which I can send out from my basic SMS enabled phone. I format an SMS just right and it'll turn into an email. I send this email to my an aliased email address on my home machine which pipes it into a perl script. I can request weather information, system uptime, etc. And yes, I can download the slashdot XML news page and parse it up, tokenize it into emails 160charactors long and EMAIL it back to my cell phone.
"new SMS to 003436". "CMD S" for slashdot news command. 10 seconds later I get 2-4 SMS messages giving me the slashdot headlines. I've done this from a cottage, a highway coach, toilets in dingy bathrooms.
well, interesting thing.
All alcohol, drugs and ammunition in the states is in metric.
"Give me 10 CCs of sneezy-zol" CC = Cubic Centimetre (aka. mililitre)
The correct spelling is Metre (since SI is French).
... on that one's ok.
http://www1.bipm.org/en/si/base_units/
Litre not liter
Metre not meter
Gram not grahm
Kelvin not calvin
Ampere not amper
Candela not candle
Second not second
You idiots.
It reached 100km and the press release rounded it off to 328,491 feet not the other way around.
This is pure americanizum at work.
To be 100% correct - it's not weightlessness, it's micro-gravity.
Yes. Basic interferrence patterns emerge. I think even Encarta (MSoft blasphemer!) has a good explaination of it.
Try it in your bath tube tonight.
Dudes. Been reading your posts. And yes my birth name is "Jean-Luc" - so please cut the StarTrek references.
Schrodinger's equation describes in simple but effective terms how QM objects behave (or more accuratly, objects in a QM scale).
First year Physics student asks the Prof. "If the inputs to the Schrodinger equation is spacial co-ordinates, what is the output?"
Prof forseeing the futility of explaining the response: "Probability".
Student perplexed: "Gah?"
Prof: "The probability of existance"
Student: "Oh, so once you know it's there, it's 100% right?"
Prof: "Yes, but that doesn't matter. Untill you actually look at it, it's everywhere in varying amounts."
Student: "Amounts of what?"
Prof: "Sigh. PROBABILITY!"
Student: "My brain hurts."
Prof brilliantly squashes a vile of poison hidden in the student's bag with a hammer like the quantum mechanical Schrodinger Cat he is.
The Moon is a gravity well. To fall into the well, you must then climb back out. You effectivly need to bring with you fuel to:
a) leave earth orbit - which accounts for over 75% of current lift-off mass of space shuttle (even more for Saturn V)
b) Burn fuel for a safe landing on the moon
c) Burn more fuel to leave Moon orbit
d) Burn still more fuel for a safe landing on Mars
e) Burn yet still more fuel to leave Mars orbit
f) Burn yet still again more fuel to slow down for a safe landing on Earth
The Saturn V was a "cockroach strapped to a gas can" to begin with. And that was for a Lunar trip that crashed into the Earth. You want to do this 3 times you say?
What, is George Bush's science advisor the same science advisor as Lost In Space, An American Werewolf in Paris, or Armageddon?
... listening to the CBC talking about the t-dot being without power ... premenition of their impending loss to Ottawa? Only time will tell.
Cryptanalysis of MD5 Compress.
Modern hash functions use a compression routine on buffered data to produce a hash. This compression function is performed repeatadly on - say 512 bit - blocks.
Dobbertin found a collision in the MD5 compression function. This is not the entire MD5 hash which includes padding and length added in the final compression.
MD5CRK is simply "the next step" from this paper.
the calculation time would not 'skyrocket'... but it does increase to a point where software is not the proper medium.
In hardware, a 128bit collision can be accomplished in 24 days on a $100,000USD peice of hardware. Read more about this on The site.
The "term" significant is relative. If a mathmatical algorithm is 100% slower when dealing with purly CPU bound data and in real-life you use it on I/O bound data - I don't consider it to be significant.
10mins producing 1000's of hashs of files vs 13-15mins isn't going to kill you IMHO.
3DES is 200% slower than DES (1 + 200% == 3). Yet people have accepted that penalty. Why not 50% or 100%?
For the record - if you're really sensitive about performance and not concerned with cryptographic level of security - you should be using MD4 which is faster then MD5 and provides 128 bits of hash.
Google for MD4 collisions, you'll see people have infact inverted MD4 for certain inputs.
Almost forgot your comment about speed. SHA-1 is slightly slower then MD5. SHA-256 is slightly slower then SHA-1. SHA-384/512 use 64 bit operations so it is much slower on 32bit systems. In short, you concerns about speed are unfounded. Read on.
...
Run this command:
openssl speed md5 sha1
I get:
The 'numbers' are in 1000s of bytes per second processed.
type 16 bytes 64 bytes 256 bytes 1024 bytes 8192 bytes
md5 13426.71k 46361.18k 124663.83k 222340.64k 286203.62k
sha1 11175.12k 30058.96k 69783.42k 104107.06k 121809.96k
I also ran "time md5sum file94mb" and "time sha1sum file94mb" file 3 times in succession. The performance is much closer.
a959b7de4f11fe89ba57ecc6fe2f6a07 file94mb
real 0m1.070s
user 0m0.860s
sys 0m0.060s
a959b7de4f11fe89ba57ecc6fe2f6a07 file94mb
real 0m1.070s
user 0m0.850s
sys 0m0.070s
a959b7de4f11fe89ba57ecc6fe2f6a07 file94mb
real 0m1.071s
user 0m0.810s
sys 0m0.110s
5d926755ef975a8900b89b514feac9ded29c4477 file94mb
real 0m1.538s
user 0m1.260s
sys 0m0.060s
5d926755ef975a8900b89b514feac9ded29c4477 file94mb
real 0m1.524s
user 0m1.270s
sys 0m0.040s
5d926755ef975a8900b89b514feac9ded29c4477 file94mb
real 0m1.520s
user 0m1.280s
sys 0m0.030s
The argument boils down to this:
- A cryptographic hash function must to meet three criteria: non-invertible, 1st image collision resistance (given m, finding m' such that h(m) = h(m')) and 2nd collision resistance (finding m and m' such that h(m) = h(m')).
- There are some applications where 1st or 2nd collision resistance is not required - file integrity, web certificate verification and several others are not one of them.
- If I can find over $100,000USD worth stealing by producing a collision in MD5 (inspect your bank's website certificate, most US firms use MD5) than it's a business proposition, not an egghead research idea.
- Is a 56bit key secure? Bet you can't find the one I'm thinking of in the next 24 hrs. Is a 128bit hash secure when its effective strength is 64 bits? If you're a bank, no. If you're joe slashdotter, yes.
No respectable cryptographer uses MD5 for signatures anymore, they havn't for years - the industry hasn't caught up yet (TripWire, VeriSign, .rpm, .deb, md5sum, some PRNGs, etc)
/. posters... :) )
This is the essance of why I'm doing this.
Look around for evidance of this movment in crypto circles (ie don't listen to
Read van oorschot's paper cited in my sci.crypt post. You'll start gettign mad at VeriSign, Amazon, SourceForge, et al for using MD5.
read the sci.crypt post, I site a paper from van oorschot from 1994 describing exactly how to get MD5 collision. In today dollars/moores law, it would cost $100,000....anyone with good credit can find collisions in MD5.
a collision in MD5's transform was found. But not on the whole hash.
h tm l
Difference? The md5() function includes padding. The md5_compress() collision is cited here:
http://citeseer.nj.nec.com/denboer93collisions.