Encrypt challenge instead of storing it on the server My server and my smartcard (MIFARE DESFire) want to establish that they have the same shared AES key. They want to do that with an untrusted client in the middle.

Usually it works like this:



Now this requires that I store RndA on the server between Generate RndA and Decrypt and compare RndA' with Rotate(RndA).

My question is: Instead of storing RndA on the server, can I safely use the same AES key to encrypt RndA and pass it on to the client for storing?

The sequence becomes:



I feel uneasy about providing the Client with both AES(RndA || RndB') and AES(RndA), but I'm not sure if that is justified.

If that is unsafe, what about the alternatives? Encrypt RndA with a fixed key shared among all smartcards? Or store one more key per smartcard to encrypt RndA?
Short version:  No it is probably not safe; it will likely allow for a replay attack.  

Longer version:  Defining what "safe" means is always a little tricky and dependent on a lot of other context.  With what you have showing in your sequence diagrams, the approach of sending AES(RndA) and not storing it on the server would allow your untrusted client to reuse that same data in a future transaction.  

If the server simply compares the AES(RndA') and AES(RndA) that is receives from the client, there is nothing that ties it to this particular transaction.  Once a malicious client has done a single valid transaction, it can just send back the results for any future transactions.  Because the server doesn't keep the random value, it has no way to tie a given pair of AES(RndA') and AES(RndA) to a particular transaction.  

You can add additional data like serial numbers, user ids, timestamps, etc to the encrypted values so that there is some state.  Those will help in some scenarios as supplemental checks, but they will never be as strong as simply keeping the full random value.