Re: Pin generation algorithm question

From: Ernst Lippe (ernstl-at-planet-dot-nl_at_ignore.this)
Date: 04/24/04 

Date: Sat, 24 Apr 2004 11:13:08 +0200

On Sat, 24 Apr 2004 02:48:21 +0100, Peter Fairbrother wrote:

> Ernst Lippe wrote:
>
>
>> One obvious solution is to simply keep a list of all currently valid numbers
>> at the central server, and to remove a number from this list when it has been
>> used.
>
> You would probably want to keep a record of the number and it's use, for a
> while, to help detect cheating.
>
>> One of the remarks that I made was that such a list is a big security
>> risk. Such a list has a very high monetary value so it will be very difficult
>> to secure it.
>
> Sure the list is a big target. Alternatively, the keys would be a big
> target. What's the difference? You can fit either on a USB pen drive.
>
> You have to have a big, valuable target somewhere, you can't avoid it. How
> are keys better?

There is a major difference between securing an entire database and
securing a single key. Obviously in this case, both have the same
value, in this case the value of each number is probably at least
ten uhh pounds.

Suppose that we have a database that contains all valid numbers, as you and
most others have proposed. This database must be kept confidential, because
if anyone could read it the company would loose real money. But when you look
at the entire system this is almost impossible because there are a large
number of persons and systems that require access to this database.

Let's first look at the computer systems that need the database. Of course the
primary database "user" is the central verification server. When the load of
the system is too high for any single server, you will need to distribute the
load among several servers that all need access to this database. Also for
disaster recovery, you will need another set of hot stand-by servers at a
different location. This is an important part of the system and you will
certainly need such emergency back-ups. But the list of numbers must be
synchronized among all servers. Because not all servers are in the same
location you need some form of secure data exchange. How can you be
certain that all these information exchanges are actually secure?

Now because this is a computer system you can be certain that at some point in
time the automatic synchronization will fail and some technician will be
called in to examine the differences between these database. How can you
be certain that he does not leak information?

The database will be running on some general purpose computers,
so there will be multiple system administrators that have legitimate
access to these systems. How are you going to prevent them from
examining/copying the database?

Obviously, you will also have to make back-ups of the system. They should be
encrypted but how are you going to manage the keys that are used for this. The
back-ups should be stored in a different location than the servers, how are
you going to secure the transport and storage?

There are other parties that require access to this database as well, think
about customer service and the fraud department. How can you make certain
that they cannot leak information?

So the whole problem with this database is that it must be kept confidential,
this is an extremely difficult task.

Now, let's examine the case where we use keys that are stored
in some dedicated crypto box.

First of all we have some physical security here. The keys are stored in a
known location, and you can't move the box because then it will erase all
keys.

So the only real problem is which systems are accessing this crypto box. In
order to detect security problems, the crypto box should maintain counters for
the number of times that each key has been used. Other parts of the system
should also maintain logs and this will help to detect and trace illegal
access to the cryptobox. Something that may not be obvious to persons that
never worked with crypto hardware, is that normally they use symmetrical keys
in an "asymmetrical" way, i.e. they will either encrypt or decrypt with a
given key but not both. So in this case the crypto box can be used efficiently
to verify a given number, but you will have to issue a large number of
requests to the box for finding a new valid number. It depends on the way that
the system is used, but it seems safe to assume that the number of crypto
requests to find a single valid number is much larger than the number of
legitimate requests that are made by the system. So when you watch the
statistics of the cryptobox carefully you will detect strange behaviour
quickly. Fishing attempts that can remain below the detection limits will
never generate a large number of valid ticket numbers, so they are not a real
risk.

Back-ups and replication across multiple cryptoboxes are not a problem. The
keys will change only infrequently, and all good cryptoboxes have good key
management facilities to securely transport keys between boxes. It is probably
wise to let some box generate the keys as well, in this way the keys are only
available inside some cryptobox.

Obviously, there also has to be a different crypto box that is used for the
generation of the ticket numbers. This box is a lot more valuable than the
other ones. Fortunately, it is needed only for a very limited period, when a
new batch of tickets is generated. At all other times, this box should be
physically disconnected from the outside world.

Now let's look at the other attacks against the boxes. Physical attacks are
difficult. These things are built like safes, and they are normally placed in
some very visible location, so successful physical attacks are extremely
unlikely. Logical attacks are a much greater risk, but are still very
difficult. Remember, even though it contains a normal CPU, the crypto box is
very different from a normal general-purpose computer. The crypto-box only
supports a very limited number of operations, essentially you only need the
following set:
* handle verification requests
* give statistics about key usage
* key management functions
Because of this limited functionality, it is a whole lot easier to have a
secure implementation than it is for other computer systems.

In my proposal with crypto boxes, there must be a database of used
numbers. This database is a lot easier to secure than your database. The
essential difference is that this database need not be confidential, we only
need a limited form of integrity. The contents of this database will not
really help an attacker find valid numbers, it only helps eliminating a very
small fraction of the potential candidates. Also there is no absolute
requirement that this database is always up-to-date, loosing some of the
updates to this database (e.g. a few days) is not a major problem.

To sum it up, there is major difference in security between securing
a small set of keys and securing an entire database.

Ernst Lippe

Relevant Pages

  • Re: imperial screwcutting on metric lathe
    ... I don't often talk about crypto on non-crypto fora, 'cos I think it's fantastically interesting but most people just go uh?, but - Diffie-Hellman really is astounding. ... Some other amazing things you can do with crypto: You can query a database and get an exact number of bits from the database - but the database operator can't tell which bits of the database you got. ... Keys are too short and subject to various attacks, including brute force, rubber hose and the nice truncheon attacks. ...
    (uk.rec.models.engineering)
  • Re: Key attributes with list values was Re: What are the differences ...KEY
    ... Jane Harper is married. ... And a constraint that states that single people cannot become divorced. ... database, or users, for that matter, to distinguish between them. ... That's the whole point of keys. ...
    (comp.databases.theory)
  • Re: Database design, Keys and some other things
    ... >> Or 'the database has no opinion as what Donald Trump's e-mail address might ... some keys can be wrong or a data can ... Meaning is not related to just one number. ... > is concerned a VIN is not a surrogate key, ...
    (comp.databases.theory)
  • Re: Key attributes with list values was Re: What are the differences ...KEY
    ... database, or users, for that matter, to distinguish between them. ... That's the whole point of keys. ... But that is true of any constraint. ... keys can change, then either updates must be singular, that is, must affect ...
    (comp.databases.theory)
  • RE: Permissions
    ... servers are available to service the logon request. ... - Make certain that WINS database replication is successful between WINS ... Domainregistrations that are not listed in the ... If you are logged on as an administrator at a Domain Controller, ...
    (microsoft.public.win2000.security)