Can Pre-Paid Cards be cracked?

Question

Is it possible to deduce the original function that used to generate those prepaid cards number that are used for charging your mobile phone credits?

For example: If I've collected about 1000 of those cards, how can I analyze those numbers so that I can re-generate the generated numbers again using my own software?

Answer 1

If the people who generated the pre-paid card numbers did their job properly, then no, it is not possible to reconstruct these numbers.

The simplest pre-paid card number generation system is to use purely random numbers, and store generated numbers in a database. To verify a generated number, simply look it up in the database. The function which can then rebuild the numbers is the RNG -- if that is /dev/urandom from a Linux/*BSD/MacOS/Solaris system, or CryptGenRandom() from a Windows system, then there is no known weakness which would allow an attacker to merely recognize the RNG as being that specific system (as opposed to, say, someone flipping a coin repeatedly), let alone predict the next number with a non-trivial probability of success.

The method with random numbers and a database has two main drawbacks:

• You can get collisions. E.g., if you use 16-digit numbers, you can expect to reach your first collision after 10⁸ (100 millions) generated numbers. You can deal with that by checking your generated numbers against the database, but this can make the industrial process more complex (i.e. you have to talk to the database before deciding whether the card is worth printing).

• Each number verification entails a database lookup. With millions of customers, this may imply an heavy load, especially if there are people who routinely try random numbers, just in case they get lucky (apparently, people do that). Database access is unavoidable at some point, if the card is genuine (if only to update the customer account), but one would prefer to have a lighter way to filter out most invalid card numbers.

So a slightly more complex method involves symmetric encryption. Namely, you use a block cipher operating over the space of $n$-digit integers. So you have a secret key $K$; let $E_K$ be the encryption function, and $D_K$ the decryption. You keep a counter $c$ of generated card numbers. To get a new card number:

1. Increment $c$.
2. Encode $c$ into a sequence of $m$ digits and pad it with $n-m$ zeros.
3. Encrypt the whole thing with $E_K$.

Then, when it comes to verify a number, try first decrypting it with $D_K$: if the result does not end with $n-m$ zeros, then you know that it is not a genuine number, and can be rejected without involving the database. This method also guarantees the total absence of collisions.

The tricky part in this method is having the appropriate $E_K$ / $D_K$ function. It must be a pseudo-random permutation; anything like a stream cipher is inadequate (including AES in CTR mode). If the number length ($n$) is 19 or less (but close to 19), then this is easily done with a 64-bit block cipher $B$ such as IDEA or the venerable 3DES (apparently, the IDEA patents expired, which is why it becomes recommendable again). Then, to encrypt a sequence $d$ of $n$ digits:

1. Encode $d$ into 64 bits (interpret $d$ as an integer, write down the value in binary); call $x$ the resulting sequence.
2. Set $x \leftarrow B_K(x)$ (encryption with the 64-bit block cipher).
3. Interpret $x$ as an integer value $e$.
4. If $e ≥ 10^n$, loop to step 2. Otherwise, define $E_K(d) = e$.

In plain words, we use the block cipher repeatedly until it gets us back to the appropriate space of integers between $0$ and $10^n-1$. If the block cipher is a secure pseudo-random permutation, the this process is also a secure pseudo-random permutation. The average number of iterations will be $2^{64}/10^n$; for instance, with $n = 16$, this will require on average about 1845 invocations of the underlying block cipher: a very small amount, since a cheap PC can do millions of those per second, with a single core.

With this method, predicting valid numbers with success probability higher than $10^{m-n}$ would require breaking the 64-bit block cipher (that is, there mere existence of such a predictor would be viewed as an unredeemable weakness of the block cipher). So, with IDEA or 3DES, no worry. With practical figures: with $n = 16$ (16-digit card numbers) and $m = 11$ (you have room for one hundred billions of valid numbers), then only one random number in 100000 will require actual database lookup.

If $n$ is much smaller (e.g. $n = 12$), the computational cost can become excessive, but the core principle can still be applied, provided that you design a custom block cipher which runs over sequences of digits -- this is a difficult task (don't do this at home ! I.e., do not deploy such a system in production without getting some professional advice from a trained cryptographer), but there are existing tools (see this question for details).