# Alice and Bob authentication and integrity problem

Suppose Alice needs to send a file to Bob, guaranteeing her identity and the file integrity (no confidentiality required); the two parties are sharing a secret `w` and make use of a hash function `H` that outputs 40-bit numbers. Each time they use the following (pre-agreed) protocol.

A → B: w{nA}, where nA is a nonce (Alice sends a challenge)

B → A: w{nA+1} (Bob proves he knows the secret, providing response to challenge)

A → B: (F, H(F),w{H(F)}) (Bob, given F, computes H(F) and w{H(F)}, and then compare his results to data actually received)

Can an attacker act in place of Alice and send a file to Bob tricking him into believing that the file is coming from Alice ?

Yes, Mallory, a Man-In-The-Middle could intercept communications as follows, and pretend to be Bob to Alice, and Alice to Bob:

``````A → M → B: w{nA}

B → M → A: w{nA+1}

A → M → B: (F, H(F), w{H(F)})
``````

Step three requires a hash collision in order to substitute a file - Mallory could have created an evil file, E, and can calculate `H(E)`.

Mallory observes traffic and waits to see a file transfer happen where `H(F) = H(E)`.

Once this happens, Mallory manipulates the traffic so instead of

``````(F, H(F), w{H(F)})
``````

being sent to Bob,

``````(E, H(F), w{H(F)})
``````

is sent instead. Note that as `H(F) = H(E)`, `w{H(F)}` will also equal `w{H(E)}`.

The protocol can be fixed by the nonce and secret being part of the file transfer stage:

``````A → B: (nA, F, H(nA | w | F))
``````

Steps one and two are no longer required. As Mallory cannot hash their own file with `w`, they have no way of detecting a collision.

Of course, Mallory could replace every file transfer F with E in the hope that a hash collision occurs, however Bob would notice that something was amiss.

In order to fix that in the protocol, HMAC(SHA-256) could be used rather than a weak 40 bit hash.

My idea was that if output of an hash function is less than 160 bit we can perform a succesfull birthday attack, so this is what i thought.So the attack occurs on the step 3. Anything else flows in my mind even because ,for everything, the attacker must know w and he can't retrieve w from any pass.

You are right in thinking that a birthday attack can be performed. An attacker, Oscar, could intercept the communication between Alice and Bob an modify the message that bob receives.

• But the birthday attack affect only the Hash function in step 3. How can Oscar send the w{H(F)} without knowing w? – rollotommasi Feb 9 '16 at 19:06
• The only way for them to be sure of the identity being secure is by using a Certificate Authority (CA). This way, their identities are guaranteed. – CSstudent Feb 9 '16 at 19:14
• Yes sure. So the only way to fix this problem without a CA is to increment the output of the hash to any value bigger than 160 bit? – rollotommasi Feb 9 '16 at 19:18
• That would certainly help. The larger the output, the harder it is to break/replace. Hash functions don't really supply much security by themselves, they're just good for data integrity. If you want really good security between Alice and Bob, then use DHKE instead. – CSstudent Feb 9 '16 at 19:20
• Yes sure. This is one of my homework so i need to answer both question. 1) Where the attacker can occur and 2) how to fix the protocol. Is everything here? – rollotommasi Feb 9 '16 at 19:47