Re: Pin generation algorithm question

From: Peter Fairbrother (zenadsl6186_at_zen.co.uk)
Date: 04/23/04 

Date: Fri, 23 Apr 2004 16:19:51 +0100

As I understand it, you don't need an algorithm, you need randomness.

Do I have this right?

You want to generate numbers (which are not pin's btw) to issue as tokens
exchangeable for airtime.

You'll have to keep a record of all the tokens in issue. You can't get
around that. What you will do is check whether a presented token is on the
list, if it is you add airtime and remove the token from the list of issued
tokens, if not you deny it.

If you have 10^8 tokens in issue and 10^16 space, the chance that a random
token will be accepted is 1 in 10^8. If 20% of entry attempts are not for
valid tokens (it is hard to enter a 16 digit number on a mobile without
error, ignoring attempted fraud for now) and you issue 10^8 tokens per year,
you will only get a few random false acceptances to upset your customers.

Note that any false acceptance will annoy at least one customer (the one who
later gets refused). You need to keep fraud especially low here, it's not
just loss of money.

What you _want_ to do is to include a method of quickly checking candidate
tokens, from some structure in the token, perhaps an included hash. You will
have to keep that structure secret - an attacker who has access to the quick
check can use it to pre-screen candidates, and get a better chance of a hit.

But do you really need to include a quick check? What would it be used for?
Any legitimate attempt that passes the quick check will get passed on to the
list checker anyway, and if 20% of attempts are invalid a quick check only
decreases the traffic on the main list-holding server by 20%.

You also want an algorithmic means to generate the numbers, which again will
have to be kept secret. I can't see any benefit from an algorithm, beyond a
small decrease in workload, but presumably you have something in mind. Do
you need it?

It will not be easy to keep those secrets. The best (and by far the
cheapest) way to prevent a secret being revealed is not to have a secret in
the first place. Forget quick checks. Forget algorithms. You don't have to
keep anything more (or less) than the list of issued tokens secret. That is
where your security should be aimed.

Above all, what you _have_ to do is to ensure that an attacker's probability
of a hit is low enough that he won't bother, and preferably to keep it at
10^-8.

Beyond any doubt, the best way (assuming you can do it securely, and you'd
better be able to do it securely) to do that is to generate full 16-digit
candidate tokens at random, using real randomness, and check whether they
are in issue.

£1,200 please. For knowing where to hit. :) 

-- 
Peter Fairbrother

Relevant Pages

  • Re: Password alternatives
    ... their algorithm remaining secret, which in terms of cryptography is bad ... I'm not an expert on tokens. ... Unlike passwords, biometrics do have the problem of False Accept Rate ... passphrases as a string of characters, ...
    (Security-Basics)
  • Re: compression type
    ... occurance of what repeats, for there to be a token, for how tokens ... see its construction algorithm. ... It's very limited to think that's the only way to compress, ... made different, to the other shape, where the math to say one shape ...
    (comp.compression)
  • Re: compression type
    ... occurance of what repeats, for there to be a token, for how tokens ... for how a repeat occurance of a length of data can be said ... see its construction algorithm. ... can compress them even though there are no patterns, ...
    (comp.compression)
  • Re: Error reporting, was Infinite look ahead required by C++?
    ... the tool isn't the same as the algorithm the tool uses. ... valid next tokens, used to choose between shifting and reducing. ... inherent part of LALR, but rather an optimisation specific to Bison? ... be reducing when in this context we should have applied an error. ...
    (comp.compilers)
  • Re: P = NP!
    ... on a public math forum, it seems his algorithm ... We start by, once again, referring to the DNF form even though we're explicitly told we're not trying to solve the DNF form. ... Oh, by the way, the algorithm is essentially "for all tokens in the expression, if one tcis true, then it's satisfiable." ... The first paragraph of the algorithm is easy enough to understand: go through the clauses from left to right, checking to see if each clause has a valid token. ...
    (sci.math)