Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
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:
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, and in 2015 the SHA-3 standard was officially released in FIPS 202. 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.
When designing a new protocol, try to do it in a way that the hash function can switched out, so you can use either SHA-2 or SHA-3 when the other one shows creaks.
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.)
