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-&gt;D2: C1
D2-&gt;D1: C2, AES(key, C1 || C2)
D1-&gt;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?
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.