Ideas about Generating Untraceable Invoice IDs

Question

I want to print invoices for customers in my app. Each invoice has an Invoice ID. I want IDs to be:

• Sequential (ids entered lately come late)
• 32 bit integers
• Not easily traceable like 1 2 3 so that people can't tell how many items we sell.

An idea of my own: Number of seconds since a specific date & time (e.g. 1/1/2010 00 AM).

Any other ideas how to generate these numbers ?

Answer 1

If the orders sit in an inbox until a single person processes them each morning, seeing that it took that person till 16:00 before he got round to creating my invoice will give me the impression that he's been busy. Getting the 9:01 invoice makes me feel like I'm the only customer today.

But if you generate the ID at the time when I place my order, the timestamp tells me nothing.

I think I therefore actually like the timestamps, assuming that collisions where two customers simultaneously need an ID created are rare.

Answer 2

There are two problems in your question. One is solvable, one isn't (with the constraints you give).

Solvable: Unguessable numbers

The first one is quite simple: It should be hard for a customer to guess a valid invoice number (or the next valid invoice number), when the customer has access to a set of valid invoice numbers.

You can solve this with your constraint:

Split your invoice number in two parts:

1. A 20 bit prefix, taken from a sequence of increasing numbers (e.g. the natural numbers 0,1,2,...)
2. A 10 bit suffix that is randomly generated

With these scheme, there are a bout 1 million valid invoice numbers. You can precalculate them and store them in the database. When presented with a invoice number, check if it is in your database. When it isn't, it's not valid.

Use a SQL sequence for handing out numbers. When issuing a new (i.e. unused) invoice number, increment the seuqnce and issue the n-th number from the precalculated list (order by value).

Not solvable: Guessing the number of customers

When you want to prevent a customer having a number of valid invoice numbers from guessing how much invoice numbers you have issued yet (and there for how much customers you have): This is not possible.

You have hare a variant form the so called "German tank problem". I nthe second world war, the allies used serial numbers printed on the gear box of german tanks to guestimate, how much tanks Germany had produced. This worked, because the serial number was increasing without gaps.

But even when you increase the numbers with gaps, the solution for the German tank problem still works. It is quite easy:

1. You use the method described here to guess the highest issued invoice number
2. You guess the mean difference between two successive invoice numbers and divide the number through this value
3. You can use linear regression to get a stable delta value (if it exists).

Now you have a good guess about the order of magnitude of the number of invoices (200, 15000, half an million, etc.).

This works as long there (theoretically) exists a mean value for two successive invoice numbers. This is usually the case, even when using a random number generator, because most random number generators are designed to have such a mean value.

There is a counter measure: You have to make sure that there exists no mean value for the gap of two successive numbers. A random number generator with this property can be constructed very easy.

Example:

1. Start with the last invoice number plus one as current number
2. Multiply the current number with a random number >=2. This is your new current number.
3. Get a random bit: If the bit is 0, the result is your current number. Otherwise go back to step 2.

While this will work in theory, you will very soon run out of 32 bit integer numbers.

I don't think there is a practical solution for this problem. Either the gap between two successive number has a mean value (with little variance) and you can guess the amount of issued numbers easily. Or you will run out of 32 bit numbers very quickly.

Snakeoil (non working solutions)

Don't use any time based solution. The timestamp is usually easy guessable (probably an approximately correct timestamp will be printed somewhere on invoice). Using timestamps usually makes it easier for the attacker, not harder.

Don't use insecure random numbers. Most random number generators are not cryptographically safe. They usually have mathematical properties that are good for statistics but bad for your security (e.g. a predicable distribution, a stable mean value, etc.)