8
$\begingroup$

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?

|improve this question
$\endgroup$
  • $\begingroup$ It can't be done. The generation algorithms are carefully chosen specifically to make this impossible. $\endgroup$ – David Schwartz Oct 2 '11 at 23:59
  • $\begingroup$ Just out of curiosity (and partially playing devil's advocate), how do you know this? Are the algorithms publicly available or do you have insider knowledge? $\endgroup$ – mikeazo Oct 3 '11 at 16:23
  • $\begingroup$ You don't need to be an insider to know that. It's like knowing that bridges are designed to support the weight of trucks. (If they weren't, "bridge collapses" would be the headline every day.) $\endgroup$ – David Schwartz Oct 3 '11 at 16:42
  • 2
    $\begingroup$ I suppose this will depend on the algorithm used by your mobile phone provider. Without any details, this will give only speculation. $\endgroup$ – Paŭlo Ebermann Oct 3 '11 at 16:56
  • $\begingroup$ Actually, if bridges would collapse every day, this wouldn't be in the headlines anymore :-) $\endgroup$ – Paŭlo Ebermann Oct 3 '11 at 16:57
16
$\begingroup$

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 108 (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).

|improve this answer
$\endgroup$
  • $\begingroup$ I don't believe there's any requirement to use the whole space of $n$-digit strings: knowing that numbers greater than $2^k$ are never used will only help an attacker by a factor of $10^n/2^k<2$, assuming that $k=\lfloor\log_210^n\rfloor$. That way, we can just work in the space of $k$-bit binary strings, and won't need to resort to any "hasty pudding tricks". (In any case, a bigger issue with this design is that, because it's based on symmetric encryption, any device that can validate a number can also generate one. This is obviously a problem if such a device might be cracked.) $\endgroup$ – Ilmari Karonen Oct 7 '11 at 17:48
  • $\begingroup$ If you just want to decrease database lookups, a simple solution is to add a Verhoeff digit. $\endgroup$ – didest Oct 11 '11 at 3:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.