Broadband Tech > Security > Security > Understanding crypto hashes

Understanding crypto hashes

• you download a file from a website, and they post the checksums of the data (example here), and you can run a checksum after you've downloaded it. If the checksum doesn't match, then either the file was damaged in transit, or the file was tampered with at the download site. Good thing you verified the checksum!
  
  
• when Linux stores user passwords in the password file, it doesn't store them in cleartext (or anybody could easily get all the passwords). Instead, it can run an MD5 checksum on the password and produce a 128-bit checksum:
  

  testuser:$1$pTJhZVZ6$iLoDMnbPSekU.lot59fQx/:
  

  This long string (starting with $1$) is the MD5 checksum, and when you're attempting to login, the password you type is hashed and compared with this string: if they match, you must have typed the right password so it lets you in.

1. they are "one way" hashes, meaning that given a hash, you can't recover any knowledge of the original input data (even if the input data was smaller than the output data). If you know somebody's MD5 password hash, you can't get the cleartext password back.
   
2. given a random checksum, you can't easily create a different stream of data taht produces the same checksum

Excellent summary Steve!

reply to Steve

quote:

---

But if I'm a bad guy, I could take the XP/SP2 distribution, modify it to contain bad stuff, and tweak it to create the same checksum and post it on a download site somewhere. Because the checksums match, everybody would assume the file was OK. Oops.

The security of one-way crypto hashes positively relies on the inability to intentionally create a collision, and this is what the researchers seem to be able to do. I suspect it's always been possible to create a collision with brute-force means, but it requires iterating over 2^128 possible values, and this is simply computationally infeasable.

---

said by x539:

---

Not unless you're a bad guy with a time machine or a bad guy that knows more than any living cryptographer at this point in time.

---

quote:

---

I generally agree with your overall sentiment, though I think that once things start falling apart at the edges of an algorithm, it's hard to say what happens next.

---

said by x539:

---

My point was ...

---

reply to Steve
What's really funny to me is that I used to say that this was possible (even somewhere on BBR) and was chided quite brutally for it. Thing is...my "modest" 14 years in all facets of IT has taught me one thing...

"That which is done, can always be undone. The problem is time."

It may not be prophetic, but I think it holds true. How can the human mind stump itself?? It can't. Anything someone can create, someone else can destroy. (More so if you by into the whole "4th dimension" thought process where certain persons can think beyond the boundaries of our understanding.)

Software language and distribution is going to get interesting from here out...
--
-CK
Q: "What does a cold air intake, headers, catback, highflow cat , & Port Polish give you??
A: "Ricer on a plate!" lol. Visit SportCompactMiami.com

reply to Steve
I would like to clarify some things.

A "checksum," as its name implies, is a sum. It is really only used to refer to that class of hashes that use simple summing of data. The algorithms used to generate a checksum vary a little (number of bits in the result, number of data bits in each datum, whether signed or unsigned arithmetic is used to compute the checksum, what is done with an overflow/carry when the output bit size is exceeded, etc.), but it's all basically the same. This is not suitable for any more than a preliminary check of the data because it is susceptible to lots of errors. For example, if a bit is inverted in one datum, and the same bit is also inverted in the next datum, the checksum may come out the same despite two bits being inverted in the data. Similarly, if the order of two data are rearranged, the checksum will still be the same. CRCs (cyclical redundancy checks), MD5s, SHAs and so on make the order of the data significant.

Ironically enough, "SHA" means "secure hash algorithm"

Considering the recent discoveries, if arbitrary data are allowed, it may be possible (albeit difficult) to produce a collision (also sometimes called a "clash") by altering data in more than one place in the file. But what would be difficult in that case would be keeping the file size the same. Consider too that some of the data could be compressed from the original, which would provide a bigger "canvas" for one's arbitrary data to make the computed hash the same while retaining the same file size.

I'll also second another poster's notion that security it seems is at best long term but nonetheless temporary. I am not aware of a lock that's been devised that can't be picked if given enough time. _The Adolenscence Of P-1_ is a novel where this is one of the central themes. Thomas J. Ryan describes security as being a dynamic delaying device. Invention of new locks (hash algorithms) is needed constantly to stay as many steps ahead of the pickers (crackers) as possible. Moore's Law has held for a while, so that which is computationally infeasible now (or too expensive) might not necessarily be so in a few years or a decade.
--
English is a difficult enough language to interpret correctly when its rules are followed, let alone when a writer chooses not to follow those rules. Blog is here
Jeopardy! replies REALLY suck!

reply to x539


i guess i'm not so much worried about someone inserting malware (into a service pack, for example) as someone just inserting incorrect data. if this news is saying that the latter is possible, then even just that is enough to get in a little tizzy about. a program not working correctly can be just as bad or worse than someone's attempt at a working program that purposefully does harm (malware).

reply to Steve
This is maybe stating the obvious, but if the data whose hash-key you are trying to emulate includes something free-form, like an image or icon, or a compressed image file, the task of making hask keys match after a specific code change will be much simpler than if the data is all executable code and constant data.

Whether it would take 1 week or 10 years elapsed time on a dedicated 3GHz P4 I have no idea.

reply to jig

said by jig:

---

i guess i'm not so much worried about someone inserting malware (into a service pack, for example) as someone just inserting incorrect data. if this news is saying that the latter is possible, then even just that is enough to get in a little tizzy about. a program not working correctly can be just as bad or worse than someone's attempt at a working program that purposefully does harm (malware).

---

said by ghost16825:

---

But as has been stated repeatedly, would it still be a working program (executable)?
More that likely nothing would execute at all and you would get "This program is not a valid application" kind of errors. The result is a "junk" file which simply doesn't execute. (full stop) (period) (dot)

---

reply to ghost16825
"But as has been stated repeatedly, would it still be a working program (executable)?

I'd guess not always, but I believe it would be reasonable to expect something, to unexpectedly occur.
Interesting topic.
--
Dave said "By the way, 4294967295 is just another way to write -1".

reply to Steve
In my research this evening I've found a bit more on attributes of cryptographic hash functions, and I'll summarize what I found. I love learning new terms

Note that "very hard" means "computationally infeasible", which is pretty much the same as "brute force".

Collision resistance means that it's very hard to find two inputs that have the same hash value, but you get to pick both inputs.

Preimage resistance means it's very hard to create an input that matches a given hash (but you don't know the input that led to the hash of interest).

Second preimage resistance means it's very hard to create an input that matches a given hash, but you do know the input stream that led to that hash.

Very nice thread, Steve. Thank you!

-- B
--
In a realm outside causality and function

I'm here only to serve...

would you like fries with that?

reply to Steve

said by Steve:

---

so I'm waiting for the cryptorati like my hero Bruce Schneier to provide practical, informed, non-hyped guidance on this.

---

reply to Steve
Whew, I think I'm finished.

I have spent much of the last three days working on a much more comprehensive Tech Tip to provide background that anybody can understand crypto hashes, how they are used, what "breaking them" means, and what the implications are for the latest news.

Unixwiz.net Tech Tip: An Illustrated Guide to Cryptographic Hashes

Feedback and comments - even typos and spelling errors - are welcome.

Steve
--
Stephen J. Friedl * Security Consultant * Tustin, California USA * my web site

Nicely done. And thanks.

reply to Steve

#!/usr/bin/perl -w

use strict;
use Digest::MD5 qw(md5_hex);

# Create a stream of bytes from hex.
my $bytes1 = map {chr(hex($_))} qw(
  d1 31 dd 02 c5 e6 ee c4 69 3d 9a 06 98 af f9 5c
  2f ca b5 87 12 46 7e ab 40 04 58 3e b8 fb 7f 89
  55 ad 34 06 09 f4 b3 02 83 e4 88 83 25 71 41 5a
  08 51 25 e8 f7 cd c9 9f d9 1d bd f2 80 37 3c 5b
  d8 82 3e 31 56 34 8f 5b ae 6d ac d4 36 c9 19 c6
  dd 53 e2 b4 87 da 03 fd 02 39 63 06 d2 48 cd a0
  e9 9f 33 42 0f 57 7e e8 ce 54 b6 70 80 a8 0d 1e
  c6 98 21 bc b6 a8 83 93 96 f9 65 2b 6f f7 2a 70
);

# Create a second stream of bytes from hex.
my $bytes2 = map {chr(hex($_))} qw(
  d1 31 dd 02 c5 e6 ee c4 69 3d 9a 06 98 af f9 5c
  2f ca b5 07 12 46 7e ab 40 04 58 3e b8 fb 7f 89
  55 ad 34 06 09 f4 b3 02 83 e4 88 83 25 f1 41 5a
  08 51 25 e8 f7 cd c9 9f d9 1d bd 72 80 37 3c 5b
  d8 82 3e 31 56 34 8f 5b ae 6d ac d4 36 c9 19 c6
  dd 53 e2 34 87 da 03 fd 02 39 63 06 d2 48 cd a0
  e9 9f 33 42 0f 57 7e e8 ce 54 b6 70 80 28 0d 1e
  c6 98 21 bc b6 a8 83 93 96 f9 65 ab 6f f7 2a 70
);

# Print MD5 hashes
print md5_hex($bytes1), "\n";
print md5_hex($bytes2), "\n";