Are there any serious problems with this method for generating single-use tokens?

Question

I need your advice on the security of this design.

I have a scenario whereby a server application and a smart card application need to share a value e.g. 52, which has been encoded in a long decimal token but there is no direct network connection between the two applications.

The token is 20 digits long and is transmitted via SMS to a recipient who keys it into a terminal, which relays it to the smart card.

The question is what is the best way to authenticate the token.

Here is what I came up with:

1. We create a unique symmetric key (K) and store it securely in the server and the smart card's secure element.
2. We generate 10000 random 32 digit numbers and store them securely in the server and the smart card's secure element.
3. To generate a token, the server selects one index (n) out of the 10000 random numbers e.g 4821
4. It maps its value (v) to 7 separate indexes (x0, x1...x6) in the base64 format of the symmetric key (K).
5. Finally, it creates the token by appending
   • the base 10 forms of the 7 characters (K[x0], K[x1]...K[x6]),
   • the index (n), and
   • the original two digit value ie 52

For example if the 7 characters in step 5 are represented by "19-24-45-22-34-99-45", then the final token will be "19-24-45-22-34-99-45-48-21-52"

The smart card authenticates the token by performing steps 3-5 using 4821 as its value for n, then comparing its token with the incoming token.

Note: To prevent replays, both the server and smart card will null index 4821 so that the set of characters mapped to it cannot be selected or used again.

Essentially what I believe we've achieved is an ability to transfer a 20-digit authenticated single use token.

Assuming that the data stored on the server and in the smart card's secure element are both secure, are there any kinks in the armour that I need to be aware of?

Any advice will be welcome.

Thanks

- - - EDIT (24-Apr-2013 14:45pm GMT) - - -

It must have been a long day and a late night and after reading all the great responses (i.e. sanity checks) below, I seem to have come back to my senses and jettisoned the poorly thought out, home-made crypto idea. :)

As a bit of background, this solution is meant to be used in rural areas with little or no GPRS or 3G network coverage, and virtually everybody has cheap ol' feature phones that only support GSM and SMS (as opposed to smart phones). In addition, the networks are very unreliable.

Anyway, here is what I've got now:

Setup

1. Generate a unique shared symmetric key (K)
2. Generate a TAN (Transaction Authentication Number) File (S)
3. Copy K and S into the server's database and the smart card's secure element

Transaction

If a server needs to send an amount (v) to a smart card,

1. It loads the S file and selects a nonce (n) i.e. n = S[0]
2. It invalidates the nonce by deleting it from the S file (prevents replay attacks)
3. It creates a message by concatenating the amount and the nonce i.e. m = v || n
4. It creates an enciphered text (e1) i.e. e1 = H(K,m) where H = "HMAC-SHA-1" or "CBC-MAC-Y" i.e ISO/IEC 9791-1 Algorithm 3
5. It converts the enciphered text to base 10 and sends it (via SMS) to the user's mobile phone
6. It deducts the amount from the user's server-side balance

When the user' receives the code via SMS, she types the amount (v) and the code into the terminal which relays it to the smart card app, which in turn does the following:

1. It loads the S file and selects a nonce (n) i.e. n = S[i] where i = 0
2. It creates a message by concatenating the amount and the nonce i.e. m = v || n
3. It creates an enciphered text (e2) i.e. e2 = H(K,m) where H = "HMAC-SHA-1" or "CBC-MAC-Y" i.e ISO/IEC 9791-1 Algorithm 3
4. If e1 != e2, it repeats steps (1)-(3) whilst incrementing (i) up to 20 times (to allow for drift). If a match does not exist, if outputs an error message and quits
5. If e1 == e2, it accepts the value as a credit to the user's client-side balance
6. Finally, it invalidates all the nonces tried in step (1) by deleting them from the S file

TAN Files

A TAN File is a list of 1000 random nonces each of which is a 8 character, hexadecimal transaction authentication numbers (TAN). It will be is used to determine the nonce value that will be appended to a message to ensure its uniqueness and thereby prevent replay attacks.

Answer 1

I don't know the reasons behind your design, but I'd suggest taking a look at HMAC before implementing a custom solution. Assuming the server and the smart card share a strong key, you can generate a message authentication code for your value (plus an incrementing index, to prevent replays), so both the authencity and integrity of the message will be ensured. This won't grant any confidentiality, though, but neither would your proposed method, so I'm assuming it's not a concern in your case.

That said, here's what I have to say about your proposed solution:

From what I understood, at each exchange some parts of your key K will be exposed, is that right? (K[x0], K[x1], ...) After some iterations[1] an eavesdropper will have seen (with a high probability) all parts of your key, even though: a) not their order, since the indices (x0, x1, ...) will be unknown; b) it won't matter, since the random 32 bit numbers are what makes your protocol secure (since they're never reused, it's as strong as a one-time password). However, if secrecy of K is important I'd suggest simply sending the 32 bit number (with its index), since it alone is enough to authenticate the sender.

Also, while your protocol is resilient against replay attacks, man-in-the-middle is still a possibility[2]: suppose the server sends Alice "19-24-45-22-34-99-45-48-21-52" (nullifying 4821) but Mallory intercepts it (so the smart card still accepts 4821). Then Mallory sends Alice "19-24-45-22-34-99-45-48-21-42", who inputs it to the terminal. The smart card will happily accept it, but it's Mallory's value (42) which was inputted, not the server's (52), though both agree that the index 4821 was used only once.

[1] How many would depend on the size of K. A 128-bit key would reveal all its parts after 12 iterations with >97% probability, and those parts can be recombined with about the same effort as brute-forcing a 65-bit key. A 512-bit key OTOH would reveal its parts after 50 iterations, but the number of permutations needed to recombine the key is so large (larger than brute-forcing the key itself) that it doesn't matter.

[2] Assuming one can perform MitM attacks on SMS. I'm not knowledgeable enough about this protocol to say whether it can happen or not, so I'd play at the safe side...

Answer 2

This is very VERY much rolling your own and is not a good idea. Why is the existing standard of using a hash of an encryption of a timestamp derived value sufficient for your needs? The first attack that comes to mind is simply masquerading as the server to obtain codes from the card. The victim wouldn't have a good way to know it wasn't the server and the server would have no way to know that the code had been compromised. Since it isn't tied to a particular time window, the token could be reused at any point in the future.