Authentication protocol

Question

Alice and Bob share a secret key K. Suppose that someone suggests the following methods to allow Alice to securely authenticate to Bob.

Bob generates a random message r, enciphers it using K under a secure block cipher scheme and sends the encrypted message to Alice. Alice decrypts it, adds 1 to it and sends the result encrypted with K under the same block cipher to Bob. Bob decrypts the message and compares it with r. If the difference is 1, then he is sure he is communicating with Alice; or else, as no one else knows the secret K, he is talking to an impersonator. Is this protocol secure?

Is this secure based on the difference of 1 or is that still prone to attack?

Answer 1

TL;DR: It's not secure, due to MITM attacks

Just because Bob receives r + 1, it doesn't mean that he is really talking to Alice. What if Mallory intercepted the key exchange of k and intercepts messages like so:

• Mallory intercepts Bob's key exchange to Alice.

• Bob and Mallory do the key exchange, Bob thinks that Mallory is Alice.

• Mallory and Alice do the key exchange, Alice thinks that Mallory is Bob.

• Bob sends r to Alice, but it's intercepted by Mallory.

• Mallory forwards the message to Alice and Alice computes r + 1, sends this to Bob (inadvertently via Mallory)

• Any data send from Bob to Alice will go via Mallory, without either party knowing.

This way it appears that Alice did r + 1, but Mallory can still read all messages between them. This is solved with authenticated encryption.

For the key exchange, use authenticated (EC)DHE, and for encryption either sign-then-encrypt or encrypt-then-mac for data integrity (though this is more important for stream ciphers, as editing the ciphertext will edit the plaintext correspondingly).

So for example, using ECDSA you could do SymmetricEncrypt(message + ECDSA(message)) for sending data, and for the key exchange, you could use ephemeral key pairs for the (EC)DHE, and use static key pairs to sign the ephemeral ones.

Either party then verifies the signatures of the data received in order to check that they are talking with the person that they think they are.

Here's a worked example, using ECC:

• Assume Bob owns sPK1, and sSK1

• Assume Alice owns sPK2, and sSK2

Where s means static, PK and SK standing for public key and private key respectively.

• Bob creates ePK1, and eSK1

• Alice creates ePK2, and eSK2

Where e stands for ephemeral.

• Bob sends Alice ePK1, sSK1(ePK1). Bob sends Alice his ephemeral public key and a signature of it, proving Bob is the sender of the key.

• Alice sends Bob ePK2, sSK2(ePK2).

• Both parties receive and verify the others ephemeral public key. Both parties then combine their own ephemeral private key with the others ephemeral public key, yielding the same result either side. (In this example, this is done with EC Point Multiplication - ECDHE)

• Alice and Bob then run the result through SHA(3)_256 for a 256 bit symmetric key.

• All messages can be send like: AES-256-GCM(message, sSKn(message)), producing a ciphertext and MAC tag.

Side note: For symmetric encryption, AES-GCM is recommended, as it uses CTR as the underlying AES mode, which is fast as its paralellizable, and produces a MAC tag without the need for a second key to be derived / generated.

EDIT In order to make sure the static keys (for signing) belong to who they should do, a CA would issue certificates to Alice and Bob, so the static keys are definitely correct, and not forged.