Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

For the purposes of signing and verifying signatures, what is the value of the hash function?

Why would it matter if SHA1 is later determined to be easy to break? Since a Public/Private key process is still used, is SHA1 only a utility to create smaller data to sign?

The data itself is also sent in the clear most of the time.

share|improve this question

migrated from stackoverflow.com Sep 28 '11 at 18:15

This question came from our site for professional and enthusiast programmers.

    
Welcome to Cryptography Stack Exchange. Your question was migrated here because of being not directly related to software development (the topic of Stack Overflow), and being fully on-topic here. Please register your account here, too, to be able to comment and accept an answer. –  Paŭlo Ebermann Sep 28 '11 at 18:36

2 Answers 2

up vote 8 down vote accepted

A digital signature scheme has some size on which it works (e.g. what kind of messages can be signed). This message size is usually related to the key size, and smaller than most interesting messages you would want to sign.

So we use a hash function, which maps an arbitrary-length message (there is some theoretical upper size limit with most hash functions, but this is not relevant in practice) to a fixed length hash, and then use this hash as input to the signing function.

For the use for digital signatures, we need the collision resistance property of the hash function:

  • It should be very hard to find a pair of messages $x \neq x'$ such that $H(x) = H(x')$.

Without this property, an adversary could produce two different messages with the same hash, give me one (innocent looking one) to sign, and later come and show the other one (for which the same signature will fit, too).

Other interesting properties for cryptographic hash functions are preimage resistance (given a hash $h$, it should be hard to find a message $x$ with $h = H(x)$) – this is not that interesting by itself, since we usually already know the signed message – and second-preimage resistance (given a message $x$, it should be difficult to find a message $x' \neq x$ with $H(x) = H(x')$) – this is needed to prevent the attacker to create a second message which has the same hash as one I already signed.

Rob in his answer elaborated a bit about whether or not the found collisions (or second preimages) would be of a valid message format. While it might be that collisions with invalid messages are easier to find, with a brute-force collision search we can principally create messages of any valid format (as long as there are enough bits left to manipulate) with any given hash. If the hash function is secure, brute-force is the best way to find (second) preimages or collisions, and then the hash output size (as well as the time for one hash evaluation) becomes the limiting factor for security. (Assuming, of course, that the signature scheme itself is secure.)

For MD5, the collision resistance is effectively broken, i.e. it is not that hard to create two messages, which only differ in some part in the middle, and have the same hash. This was used in a famous attack to let a CA sign a bogus certificate.

As SHA-1 has a similar structure as MD5, it is expected that there will be found weaknesses, too, and SHA-2 (i.e. SHA-256 or SHA-512) are preferred today.

There was a competition running to define SHA-3, which should be even more secure than SHA-2. The Keccak hash function family won this competition, though there is still no final definition of the SHA-3 standard (expected to be finalized in the first half of 2014). SHA-3 has a quite different structure than MD5, SHA-1 and SHA-2, so it is expected that any weaknesses there will not carry over.

share|improve this answer
    
What if I control the signing totally? By this I mean, I create the Public, Private, Message, and Hash all behind closed doors ... then I sign the message. Next, I give away the message and public key. I will never "sign" again or even try to verify. Only people with the Public Key and Message will try to verify with what I just gave them on a silver platter. In this context, I'm unsure how I could be effected by SHA 1 weaknesses. If this sounds silly, it is just because I don't have my head around it yet. –  pcunite Sep 28 '11 at 19:34
1  
If the hash is broken (in the second-preimage sense), anyone who has the message can construct a second message which has the same hash, where thus the same signature will be valid. This person doesn't even need the public key or the original signature. –  Paŭlo Ebermann Sep 28 '11 at 19:39
1  
Yes, exactly. (Or you could say you signed something else, showing the forged document.) –  Paŭlo Ebermann Sep 28 '11 at 20:06
2  
"For MD5, the preimage resistance is effectively broken" I think you meant to say "collision resistance". –  CodesInChaos Jul 30 '12 at 12:28
1  
btw. not every signature scheme requires collision resistance of the underlying hash function. For example if the scheme prefixes the message by a value that the attacker can't predict before hashing, normal collisions won't work. –  CodesInChaos Jul 30 '12 at 12:30

In theory, you could "sign" the entire document by encrypting the full document with the private key. This would make the signature roughly the same size as the document, which is impractical. Instead, we sign documents by encrypting a hash of the document using the private key. This makes the signature small, which is much more practical in most cases.

There are an infinite number of documents that have the same hash. This is inherent in the definition of a hash. What makes a good hash is that (a) given a hash it should be exceedingly difficult to find the document that generates it, and (b) two documents that generate the same hash should be wildly different. By "wildly different" I mean "one is a spreadsheet, and the other is a 100 petabyte blob of noise."

A poor hash function is one that allows you to find two "reasonable" documents that have the same hash. A very poor hash function is one that allows you to craft an apparently meaningful document that generates a desired hash.

So imagine I could modify your spreadsheet, and by adding an extra megabyte of crafted data to the end, it would generate the same hash as the original. That would be a very bad hash function, especially if the spreadsheet program were willing to ignore the additional information.

A good hash function is one that makes that attack extremely difficult for all kinds of data. We hope that SHA-1 is that kind of hash function.

Note that cryptography is like bridge-building. It's all about safety margins. Just because an attack is impractical today, doesn't mean it will be impractical tomorrow (attacks only ever get better, they never get worse). When we start to see even small cracks in our algorithms, its time to start developing the next one. For most practical problems, MD5 is still adequate, but it started showing cracks, so it was time to replace it with SHA-0 (which had a bug in it, and was replaced with SHA-1). SHA-1 is starting to show a few cracks, so SHA-3 is being developed to replace it. (SHA-2 already exists, but it will probably be skipped over by most developers.)

share|improve this answer
    
Actually, the "should be wildly different" is more like "it is hard to find two such documents at all" (but then you could quite likely have lots of spreadsheets differing only in some of the numbers in the cells). –  Paŭlo Ebermann Sep 28 '11 at 17:18
    
I agree with the "it is hard to find two such documents," but part of the point is that "wildly different" means "only one of the infinite hash-equivalent documents should conceivably map to a meaningful data encoding." If one were an MP3 and the other a word processing document, that would still be far too similar. To your point: "and even given that, the unintelligible blob that is hash equivalent should be practically impossible to find." –  Rob Napier Sep 28 '11 at 17:50
1  
Nah, there are infinitely many possible meaningful documents, but only 2^160 different possible SHA-1 hashes. By only varying some short sections of a document (in total a bit over 80 bits long, for example some numbers in non-important cells of the spreadsheet), you are bound to get collisions with sensible documents. Of course, this (with a secure hash function) still takes too much time to be done in the attacker's lifetime. –  Paŭlo Ebermann Sep 28 '11 at 17:57
1  
In addition, it is absolutely not true that SHA-2 is being skipped over; if you need a secure hash function, a SHA-2 hash is often what is used (as SHA-1 has known weaknesses, and SHA-3 isn't available). –  poncho Sep 28 '11 at 18:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.