Hashing - Digital Signing and Trivial Stretching

Question

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.

Reference: http://en.wikipedia.org/wiki/Collision_attack

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.

Reference : https://stackoverflow.com/questions/4948322/fundamental-difference-between-hashing-and-encryption-algorithms

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.

Reference : https://stackoverflow.com/questions/4948322/fundamental-difference-between-hashing-and-encryption-algorithms

Answer 1

Response to Question 2 :

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

hash1 = sha512(password + salt1); 
hash2 = sha512(password + salt2); 
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);
hash2 = sha512(password + salt2);
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.