# Hashing - Digital Signing and Trivial Stretching

Two very basic questions:

## 1. Digital Signing

Why is it not possible to just simply replace the hash value from the request?

Examples:

 - Mallory creates two different documents A and B, that have an
identical hash value (collision).
- Mallory then sends document A to Alice, who agrees to what the
document says, signs its hash and sends it back to Mallory.
- Mallory copies the signature sent by Alice from document A to
document B. Then she sends document B to Bob, claiming that Alice
signed the other document (document B).
- Because the digital signature matches the document hash, Bob's
software is unable to detect the modification.


It's not transmitted, a secret and at the same time you just send the hash eventually? How does this work out?

Hash functions are also great for signing data. For example, if you're using HMAC, you sign a piece of data by taking a hash of the data concatenated with a known but not transmitted value (a secret value). So you send the plain-text and the hmac hash. Then, the receiver simply hashes the submitted data with the known value and checks to see if it matches the transmitted hmac. If it's the same, you know it wasn't tampered with by a party without the secret value. This is commonly used in secure cookie systems by HTTP frameworks, as well as in message transmission of data over HTTP where you want some validity to the data.

## 2. Digital Signing

I can't see why this code produces less colitions than the second one As soon as you have a conflict with two inputs, how does it help to append the same two values for the next recursive loops?

Not recommended:

hash = sha512(password + salt);
for (i = 0; i < 1000; i++) {
hash = sha512(hash); // <-- Do NOT do this!
}


Recommended:

hash = sha512(password + salt);
for (i = 0; i < 1000; i++) {
hash = sha512(hash + password + salt);
}


I was reading that part five times and although it kind of makes sense I am having a hard time fully comprehending it.

Now, hash1 has a probability of collision of 0.001%. But when we do the next hash2 = sha1(hash1);, all collisions of hash1 automatically become collisions of hash2. So now, we have hash1's rate at 0.001%, and the 2nd sha1 call adds to that.

Response to Question 2 :

algorithm 1 : change the algorithm into this, it will be easier to explain

hash1 = sha512(password + salt1);
for (i = 0; i < 1000; i++) {
hash1 = sha512(hash1); // <-- Do NOT do this!
hash2 = sha512(hash2); // <-- Do NOT do this!
}


For 2 different inputs hash1 and hash2, if there is a collision on iteration 10 then the next 990 iterations will crunch the very same work and output the same hash1 and hash2.

The more you hash, the more intermediate collisions you could create at iteration 12, 15, 20, 100, 101, 314 .... Every additional iteration increase the probability of collision.

if Bob run this code (half of the previous loop)

hash1 = sha512(password + salt1);
for (i = 0; i < 1000; i++) {
hash1 = sha512(hash1); // <-- Do NOT do this!
}


And if Alice run this code (half of the previous loop)

hash2 = sha512(password + salt2);
for (i = 0; i < 1000; i++) {
hash2 = sha512(hash2); // <-- Do NOT do this!
}


As of previous comment, security decreases, because Bob and Alice could impersonate each other because of the increased collision probability. When the algorithms complete

P(hash1 == hash2) > 1000 * P(sha512(password + salt2) == sha512(password + salt1) )


If there are more than Bob And Alice, John, Joe, Jack and Jeremy are running this loop, then the probability of collision is still increased by devastating effects of the "birthday paradox".

algorithm 2: something is different on each iteration, that is the big difference.

hash1 = sha512(password + salt1);
for (i = 0; i < 1000; i++) {
hash1 = sha512(hash + password + salt1);
hash2 = sha512(hash + password + salt2);
}


If there is a collision at iteration i, then the next iteration i+1 is more than likely to produce a non-collision. Every iteration has provably the very low collision probabilities of sha512 when provided with different input. Split the algorithm between Bob and Alice, when the algorithm completes

P(hash1 == hash2) == P( sha512(password + salt2) == sha512(password + salt1) )


Note : It is possible to have different values of salt at each iteration, as suggested by the referenced page.

• Thank you very much for the explanation! Unfortunately, I cant vote it up due to my lack of the required reputation points. – HansMusterWhatElse Feb 16 '15 at 7:26
• Regarding the second algorithm, this makes perfectly sense but how are you able to verify a password later? Is the salt used for the password hashing stored with it in the db? Otherwise you couldn't guarante the same result? – HansMusterWhatElse Feb 16 '15 at 7:41
• Sorry about not responding to the question 1, I was not sure how to understand it. It starts from a unfeasible task: create 2 documents with the same signature. Once this is possible, then everything built over digital signatures based on that hash algorithm crumbles down. – Pierre Feb 16 '15 at 7:44
• In the simplest of the encryption scenarios, the salt is stored unencrypted. At decryption time the user is asked for the passwd and the loop is ran again (same number of iteration, same salt). crypto.stackexchange.com/questions/3484/pbkdf2-and-salt provides more details. – Pierre Feb 16 '15 at 8:00
• thank you very much - as soon as I have my 15 points, you will get the up votes! – HansMusterWhatElse Feb 16 '15 at 9:13