How to verify a shared secret using only AES?

I have two devices that need to verify that they both are in possesion of the same secret key. One of the devices is a very limited embedded device that only has AES128 available, no SHA or other hash variants.

My idea is a basic two-way challenge-response scheme:

• Device 1 generates 8 bytes of random data (C1), and sends it to Device 2
• Device 2 generates 8 bytes of random data (C2), and calculates R1 == AES(key, C1 || C2)
• Device 2 sends R1 and C2 to Device 1
• Device 1 calculates AES(key, C1 || C2) and verifies that this matches R1
• Device 1 calculates R2 == AES(key, R1)
• Device 1 sends R2 to Device 2
• Device 2 calculates AES(key, R1) and verifies that this matches R2

Or put another way:

D1->D2: C1
D2->D1: C2, AES(key, C1 || C2)
D1->D2: AES(key, AES(key, C1 || C2))


My thinking is that this is a form of CBC-MAC, where each device offers a random challenge to the other that prevents replay attacks. Since it's just one block of data being processed, the CBC-MAC weaknesses aren't a problem.

Is this a sensible way of verifying the shared secret, or should I be doing something different?

-
Looks good to me. –  TonyK May 4 at 14:23

Why over-complicate it like that,

• D1 and D2 generates random 64-bit P (half the block size of AES)

• they send it to each other

• both generate AES(key,P_own||P_other) and again send to each other (note that these are different for each)

• then both can verify that what they received is equal to AES(key,P_other||P_own)

Upside here is that it is a fully symmetric protocol.

-
Communication takes place over a 9600 baud half duplex serial line, and speed is an important aspect. But on second thought your suggestion takes as many round trips as mine… Hm. –  m_eiman May 28 '13 at 12:49
Be careful if you choose an unauthenticated mode to encrypt P_own||P_other - for example if you use CTR (or CFB with a 1 block size message) an attacker can subvert the protocol by computing E(k, P_b||P_a) from P_a, P_b and E(k,P_a||P_b); if using ECB and P_a and P_b are each a multiple of the block size, a trivial rearranging of the messages is all that is needed. –  Michael May 28 '13 at 18:16
@Michael AES has a block size of 128 bits P_own and P_other both are 8 byte (64 bits) so no worries there –  ratchet freak May 28 '13 at 18:18
Indeed; suggested update to answer to make that constraint clear. –  Michael May 28 '13 at 18:20