Re: PIN System
From: William L. Bahn (william_at_toomuchspam.net)
Date: 09/14/05
- Next message: newstome_at_comcast.net: "Re: Good Starting Book"
- Previous message: Unruh: "Re: Incompetent design of CryptoSMS; was: Re: All known english words"
- In reply to: Thinus Pollard: "PIN System"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Wed, 14 Sep 2005 00:37:09 -0600
"Thinus Pollard" <thinus@erlfinsys.net> wrote in message
news:dg6kt6$qrf$1@ctb-nnrp2.saix.net...
> Hi there
>
> I need to do the following:
>
> There is a system that issues tickets. Each ticket contains a
PIN. This PIN
> needs to be unique and only I should be able to issue valid
PINs.
>
> The PIN contains an issue date, an expiry date, a unique serial
number and
> an amount. All this data should be encoded into a 16 digit
string.
>
> Validation should take the following form:
> 1. When entered the system should check if the entered string
is valid. This
> is easy, use 15 digits and append a check as the 16th.
> 2. When verified the system should check if the data inside the
PIN "makes
> sense".
>
> I was thinking about packing all the data into some bits and
then encrypting
> it with a cipher (public key or symmetrical). The problem with
this idea is
> how to map the data to a 15 digit string, without losing
information? From
> the 16 digits you should be able to extract the information if
you have the
> cypher keys.
>
> To be honest, I've got no idea where to start reading on this
topic. I do
> have some abstract algebra knowledge. Any pointers to
documentation will be
> appreciated.
Can what you want to do even be done? In other words, what is the
minimum amount of digits that you need to encode the information
you want? If you want to start off blindly, then you might figure
that you need 8 digits for each date YYYYMMDD x 2. Right there
you are over budget so you have to encode the two dates
differently. What is the range of potential issue dates over the
life of the system? How long do you want a ticket to be good for?
If your system will only be around for about 27 years, then you
can declare a particular date to be Day 0 and then use a four
digit offset from that date as the issue date (three digits would
only get you less than three years and I image you hope it will
at least continue to be useful longer than that). If the longest
that a ticket will be valid for is about three months from the
issue date, then you can use a two digit offset to indicate this.
If it will be longer, then you either need more digits or can
decrease the resolution. For instance, if you say that tickets
will always be good for a number of days that is divisible by
four, then a two digit offset is good for tickets that last a bit
over a year. You could play the same game with the issue date if
you wanted to. But, without playing games, then you are looking
at six digits for the two date values and are not likely to
reduce that by much.
What is the range of the amounts (I'm assuming they are prices)
that you need to include and at what precision? If you only have
to have amounts less than $100 in $1 increments, then you only
need to burn two digits to do this. But if you want to have
tickets that go for $19.99 and you anticipate this system still
being used when a loaf of bread is $40, then you will probably
need five digits for just the amount. Here you've got some
flexibility to adjust for inflation. For instance, you might
start off by using four digits and allowing for prices that are
less than $100 but in $0.01 increments. When you have to start
encoding larger amounts, you simply use a scale factor that go
into effect on a particular date. For instance, if you decided
that one or after 01 JAN 2012 that you will sell tickets in
increments of $0.25. Then four digits would allow you to indicate
ticket prices all the way up to just shy of $2500 and the readers
would know to multiply the price encoded on the ticket by 25 if
the ticket was issued on or after that date. Of course, all of
the readers have to know these scale factors and their effective
dates, including readers that went into the field on day one -
but there are ways of dealing with this. The simplest would be to
decide up front what the scale factor schedule will be and
include this in the original firmware, but that may require more
fortune telling than you are comfortable with. Another way would
be to program the readers with an expiry date beyond which they
can't be used to read tickets unless they receive a firmware
update. Then you pick price scale change date that is beyond the
expiry date of the most recent firmware version. Another way
would be to embed the scale factor as part of the serial number.
So now you have used up ten of your fifteen digits leaving you
only five more for your unique serial number. If you really want
them to be unique, then that means that you can only issue
100,000 tickets. Is that enough?
And what does it mean for a ticket to be "valid". For instance,
with the coding scheme I have described, you can pick a random 15
digit number it will be a valid ticket. Now, it may be valid for
three days starting sometime in October of the year 2020, but it
would still be "valid". Adding a 16th digit as a check digit
still means that one in ten randomly generated tickets will still
come back as being valid. If your intent it to make it difficult
for someone to forge tickets then you have to make it so that the
vast overwhelming majority of 16 digit sequences are not valid
tickets and that either chews into the number of valid serial
numbers you have or it means foregoing a serial number in favor
of some kind of message authentication code. Even if all six of
the remaining digits are a MAC, a randomly generated ticket still
has a one in a million chance of being read as valid (but you can
probably live with that). The problem there is that ALL of the
tickets that have the same issue date, expiry date, and price
will have identical strings which means that someone can buy one
ticket and then reproduce it as much as they want. So you have to
trade off between serializing the tickets and adding
authentication. But will serializing really help? If two people
come up with the same valid ticket number, how will you detect
it? What will you do about it?
Here's the bigger problem. You have to assume that your readers
will eventually get compromised. Either someone will get their
hands on one of the readers (perhaps even for just a few hours)
or that the algorithm they use will get into the wild. That means
that I can generate a 16 digit string and then test to see if it
is valid. Since one in a million will validate even if I pick
them randomly, I can generate valid ticket strings at the rate of
several a second, just on a single computer (more if they are
serialized). I dump the valid ones I find out to a file and then
sort them according to issue date. Since sixteen decimal digits
is only 53 bits, a brute force attack to catalog all of the valid
ticket numbers is feasible with today's technology. I set up ten
machines (perhaps purpose-built hardware checkers) that run
through a subset of the sample space at the rate of several
hundred million a second each. That means that I am, overall,
checking in excess of a billion possible ticket numbers a second
and generating about a thousand valid ones a second. When a valid
one is found it is piped out to a main machine for further
examination. I can check every possible combination in less than
four months and it would take a couple of hundred gigabytes to
store the catalog, but I don't even have to do that. Let's say
that I want to black market valid tickets. I don't need to
catalog tickets that have already expired or that will not be
issued for another ten years. So I filter those out. I don't
really even have to catalog them at all - the odds are in my
favor for doing it quasi real-time. If I know that someone is
going to want a $50 ticket that is good on a particular date,
then just based on the dates there are 5000 ticket numbers that
will work for me (all having that exact price). I expect to find
such a ticket number every two days.
So I think your scheme has holes that encryption isn't going to
solve.
- Next message: newstome_at_comcast.net: "Re: Good Starting Book"
- Previous message: Unruh: "Re: Incompetent design of CryptoSMS; was: Re: All known english words"
- In reply to: Thinus Pollard: "PIN System"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
