# 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? Commented Feb 9, 2016 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. Commented Feb 9, 2016 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? Commented Feb 9, 2016 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. Commented Feb 9, 2016 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? Commented Feb 9, 2016 at 19:47