Re: Pin generation algorithm question
From: Ernst Lippe (ernstl-at-planet-dot-nl_at_ignore.this)
Date: 04/23/04
- Next message: privacy.at Anonymous Remailer: "Frog-Admin nominates Len 'skunk' Sassaman 'most repugnant creature on Internet'"
- Previous message: Peter Fairbrother: "Re: Pin generation algorithm question"
- In reply to: Kees Snijders: "Re: Pin generation algorithm question"
- Next in thread: Paul Rubin: "Re: Pin generation algorithm question"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Fri, 23 Apr 2004 17:25:25 +0200
On Fri, 23 Apr 2004 01:24:44 -0700, Kees Snijders wrote:
> Ernst Lippe <ernstl-at-planet-dot-nl@ignore.this> wrote in message news:<pan.2004.04.22.14.17.17.507406@ignore.this>...
>> On Thu, 22 Apr 2004 05:35:14 -0700, Kees Snijders wrote:
>>
>> > I could use some help in coming up with a pin generation algorithm.
> More about the infrastructure.
> These pins will be printed on cards and used by customers to recharge
> their prepaid airtime accounts. Pin verification will happen as part
> of a 'recharge request' sent to us via a cellular bearer service, for
> starters USSD (Unstructured supplimentary data service), later IVR and
> perhaps SMS.
I am glad I asked, this looks like an interesting system. With this background
your requirements make a lot more sense. (BTW, the term PIN is not a very
good one, normally it refers to some number that a known person can use to
authenticate himself. In this case you are only concerned with the
authenticity of your tickets, and not in the identity of that person. But I
expect that it will be difficult to switch to a different term).
Obviously, this is a serious application where you need real security. A small
amount of fraud can probably be tolerated. I think that the main threat to
your system, is that some attacker could obtain a very large number of valid
ticket numbers. When the situation in your country is even slightly similar to
ours, large number of tickets have a very high monetary value, so attackers
could make large investments to break your system. It seems very likely that
at some point in time your system will be (partially) compromised.
I think that the following goals should be very important for your system:
* Limit the total number of ticket number that can be obtained by
any single attack.
* Mechanism to detect and analyze every attack, so that you know
which numbers have been compromised.
* Handling and recovery after a successful attack.
For the design of the system, the security should be upgradable. You should
generate the numbers in batches, where each batch has its own security
parameters. In this case, when any single batch has been compromised you could
switch to a new one.
A practical note, it seems advisable to include the batch identification as
part of the ticket number. Try to minimize the maximum period that any ticket
number is valid. In this way you can limit the of currently active batches and
you will need fewer bits for the batch identification. You could reuse
any batch number after some length of time, I seen no good reason why they
should be unique over the entire lifetime of the application.
> I suppose crypto hardware is an option, just thought since everything
> is centralised, software is the easier option.
Using software only solutions seems a bad idea, there are probably multiple
persons who have access to the algorithm and its parameters (keys), and you
should expect that attackers will try to bribe them. So I think that you
should definitely use crypto hardware. Physical security with crypto devices
is fairly straightforward. In your case you should probably select devices
with motion detectors that automatically erase their keys when they are
removed. One important point with selecting it are audit options, make sure
that you select some hardware that can maintain some form of logging,
e.g. that can count how many times certain key operations have been
performed. At regular intervals these logs should be compared to other logs in
the system to check for irregularities. Even when you decide not to use crypto
hardware in the first version of your system, make sure that you switch to
crypto at a later point in time (e.g. after the first serious compromise).
The main security bottle-neck in your system is the verification part. You
will need a database to determine if a certain ticket is valid. There are two
steps in this process: a) is the ticket number potentially valid b) has it
already been used. It seems a bad idea to simply store all potentially valid
ticket numbers in the database and record which ones have already been used.
In that case when the database is compromised, an attacker will have access to
all currently valid tickets. It is better to record only the ticket numbers
that have been used in the database. When you have a good algorithm for
generating the ticket numbers, this database by itself is not useful for an
attacker because it only contains ticket numbers that can no longer be
used. Now the task of determining if a given ticket number is valid should be
delegated to the crypto box. Basically, the validation server should send the
ticket number to the crypto box (possibly together with some information about
the batch if that cannot be stored in the crypto box) which returns if the
number is valid or not. Even when you decide not to use dedicated crypto
hardware (or if you cannot find suitable hardware), it seems wise to use a
dedicated server for this component, whose sole task is to determine if ticket
numbers are valid.
Now, this is already a rather long-winded reply, and I even have not started
to answer your original question about the number generation algorithm :)
So what do we need? When you agree with my suggestions so far, we still need a
verification algorithm that is cryptographically secure: given a ticket number
plus some additional parameters (some of these are secret keys) it should
answer if the ticket number is valid for this batch. The constraints on the
algorithm are that the size of the parameters that describe the batch should
be fairly small (e.g. the parameters cannot contain an encrypted database of
all numbers in the batch) and that there must exist an efficient algorithm for
generating valid ticket numbers (i.e. it is not acceptable to try all possible
ticket numbers during generation to determine which ones are valid).
I believe that the following algorithm should work: The algorithm uses a
strong block cipher. Apart from the key, the other parameter of the batch is
its size. The ticket number consists of the rank number within the batch
encrypted with the block cipher. If you want to determine if a ticket number
is valid you decrypt the ticket number (without the batch number of course)
with the key and see if the result is less than the batch size. When you use
a strong block cipher this should be secure. The remaining problem is which
block cipher should be used? We can't use any of the traditional block
ciphers because their block size is too large. Normal block ciphers will use a
block size of 8/16 bytes and that does not fit in a ticket
number. Fortunately, there is a trick that we can use to build a strong block
cipher with an arbitrary block size: the Luby-Rackoff construction.
Since this post is already far too long I won't describe it here,
but you can find the details on the web and there are several
people in this newsgroup who could describe it much better than
I could.
(I just noted that Mike Amling posted the same solution.)
> When pins are generated they get assigned to a voucher with a serial
> number.
> Said cards can be sitting on shelves for a long time before they are
> used to recharge.
How long do these cards remain valid? Like I said, from a security
point of view you make this as short as possible but that is
not very desirable from the point of view of many of your
partners.
Also, think about the measures that you could take to prevent and
detect counterfeited cards that have valid ticket numbers (because
of a compromise in other parts of the system).
>> > No reliance on the 'secrecy' of the algorithm can be made.
>> It is sound cryptographical practice to assume that attackers
>> know your algorithms, but it seems that you would need
>> some secret key that they cannot know. How can you securely
>> store such keys, e.g. can you use crypto hardware or are
>> these keys stored in some (probably not very secure) server?
>>
> We can store and secure everything centrally.
> Excuse my ignorance here, but if we're using a pseudo random number
> generator to generate our pins and the seed data used to initialise it
> is secured and varied each time we run it what would we need a key for
> since we're not actually encrypting anything? I suppose we'd have
> added security if we used a one-way hash function and only stored the
> encrypted pin...
Using keys is virtually always a good idea. In most cases
there are lots of reasons, I will mention a few. You can concentrate
on the way that these keys are handled, without keys you will have
to be paranoid about everyone that has some form of access.
Also having keys makes it a lot easier to test and verify your
system. With keys it is easy to switch between batches without
changing your algorithms.
>> > Nice to have:
>> > Some characteristic which could be used to recognise a pin with some
>> > degree of certainty.
>> Why do you want this? You must have some secure form of PIN
>> verification (that depends on cryptography) and when it is
>> possible to verify a PIN without this, this will only weaken
>> your system, because an attacker could use the same trick
>> for generating fake PIN's.
>>
> We're not looking at 100% verification, just the ability to reject
> dodgy pins based on a simple function we could apply up front. So we
> have 2-pass verification and few dodgy pins making it past the 1st
> pass.
> This isn't a must have, just something that would help us cut down on
> load during peak-processing times.
Something that you could do without really lowering the security of your
system is to obscure the batch numbers. So instead of using the initial digits
of the ticket number as the batch number, you could use a fixed set of bits
that are scattered trough the whole ticket number as the batch number. This is
only security by obscurity, since the position of these bits must be the same
for the entire lifetime of your system, so you can be certain that this will
become public after some time. Your ticket numbers will need to contain the
batch number anyhow, but you really should not try to use more bits for quick
checks, because this will lower your security. Also, you should think
really carefully about the consequences of accepting "dodgy" numbers.
Allowing them will both complicate your system and the security procedures
of your organization. End-users will definitely not like it when
at some later point in time you will lower their balance because of
an illegal ticket number, but your organization cannot tolerate that users
can get away with dodgy numbers all too often.
One final piece of advice, get some good security experts (as many as you can
afford) to review your system. This appears to be a system that really needs
good security.
Ernst Lippe
- Next message: privacy.at Anonymous Remailer: "Frog-Admin nominates Len 'skunk' Sassaman 'most repugnant creature on Internet'"
- Previous message: Peter Fairbrother: "Re: Pin generation algorithm question"
- In reply to: Kees Snijders: "Re: Pin generation algorithm question"
- Next in thread: Paul Rubin: "Re: Pin generation algorithm question"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
