Re: Method of authentication

From: Andrew Swallow (am.swallow_at_btopenworld.com)
Date: 10/19/05 

Date: Wed, 19 Oct 2005 19:41:23 +0000 (UTC)

The proposed protocol contained mistakes so the newsgroup did not
applauded the original poster. We are willing to say what the mistakes
are so they can be cured resulting in a very good product.

Tamir wrote:

[snip]

>
> Ok. You want the whole system, then?
> This system is meant to be used as an electronic lock & key.
> There are two different versions, I'll give you both.
>
> 1) Both the lock and the key have infra-red transmitters and recievers.
> They both have the same base numbers and array in them, and the lock
> has an extra set of base information. The key sends some signal or
> other to the lock, saying it wants to identify itself. The lock gets
> the signal, and sends a random number created by the generator with the
> extra set of starting data. The key gets the number, and uses it as one
> of the base numbers in the random number generator. The key creates a
> number, and sends it by infra-red to the lock. The lock does the same
> calculations to get that number, and makes sure the two numbers are the
> same. The lock and the key then both shift the starting numbers.
> Please, don't mention the fact that one could be shifted, and then the
> two would have different numbers. I have a way of dealing with that,
> but that's the main reason for version 2.
>
> 2) The key has an infra-red transmitter and the lock has an infra-red
> reciever. Both the lock and the key shift their numbers every few
> seconds, so they always have the same numbers. When the key wants to
> open the lock, it creates a random number using the generator and sends
> it by infra-red to the lock. The lock does the same calculation and
> makes sure the numbers are the same.
>
> If either of these methods were being used online, they would be
> breakable by means of replay attacks, but since they're not meant for
> that, it's ok.

This is a variation on the car door lock problem this newsgroup has
discussed in the past. You may wish to read those postings.

Threat model.
============

1. The value of beating the lock is about equal to the value of the
items being protected. Safes, warehouses and the cargo compartments of
trucks frequently carry goods worth millions of dollars. Corrupt code
breakers can be hired for less than that. So very strong systems are
needed.

2. Anything using radio or infra-red communications is an online system
to the thief.
a. The original infra-red messages for cars were recorded and the
playbacks used for theft. So a rolling key variable system is needed
and duplicate messages must be discarded.
b. Hacking attempts - possibly using a computer hidden near the lock -
can continue 24 hours a day, 365 days a year for many years. The system
must be able to withstand this.

3. The locks are to be opened by humans. Even with retries people can
not use a key more than 2 or 3 times a second. So make automated
hacking such as 2b difficult by limiting the number of infra-red
messages to say 10 a second per door.

4. Doors are frequently opened by more than one person. The owners of
"one person" safes normally have a backup key in case the main key is
lost or damaged. So the system must support multiple keys to the same
lock and the keys needs to identify themselves to the lock. The
identification needs to be unique.

5. Where an area, such as a building, is being protected the area may
have more than one door. The protocol needs to be able to handle this
even if some implementations only support one door. So the protocol
must allow the same key to open more than one door.

6. The security system will probably be sold to multiple buyers. These
buyers may be opponents. The mechanism in locks and keys can be reverse
engineered. So keys for one lock must not work in other locks unless
authorised and only the specified unique information can be kept secret.

7. The current world population is about 6 billion people and is
expected to rise to 10 billion. People have lived over 100 years.
There are many locks in peoples homes and places of work, a safe figure
should be say 100 locks. (Source try the UN website.) These are all
potential customers, getting the protocol right first time means that
the protocol can be used for the rest of the manufactures existence.
10,000,000,000 * 100 * 100 = 100,000,000,000,000 = 10**14
A binary number this big can be stored in 47 bits. So use an
identification field containing at least 47 bits in the messages. Each
key should have a unique identification number. Adding one to the
previous number is sufficient to produce uniqueness providing the ranges
allocated to different manufactures do not overlap.

8. The protocol uses an exchange of pseudo random numbers to
authenticate the lock and key to each other, preventing attack 2a. The
easiest way to generate a number that an outsider cannot predict is to
use a high grade encryption algorithm in counter mode. So use DES3 or
AES encryption and add one to the counter in the key each time it is
used. Each user needs their own unique random key variable of 128 bits
which is stored in both the key and the lock. (Warning keys and key
variables are different.)

9. Infra-red communications are subject to noise. So protection
against noise and tampering are needed. So calculate and appending a
HMAC to the end of messages.

10. Keys are used by humans which limits the number of times they can
be used, both per day and in a lifetime. It may be possible to
increment the count from requirement 8 at one end of the link without
incrementing its counterpart. So make the count field too big to be
used up in the life of a person. Only open or close the lock when the
count for that key is bigger than the previous count. When the count is
used up disable the key.

11. People leave and join organisations. So many locks will need a way
of introducing new uses and their keys plus a way of disabling keys.

12. Batteries run down and mains power can fail causing information in
ram to be lost. So information like counts, identifiers and key
variables has to be held in memory that survives power failure.

13. The manufacture needs a method of generating random key variables.

Notes
=====

A practical system will have other requirements.

Door - a physical object that opens.

Lock - a mechanism that prevents unauthorised people from opening doors.
  A centralised lock computer may control more than one door.

Key - physical object that activates a lock.

Key variable - a big binary number used by encryption algorithms. A
random patten is used to make them unpredictable and unique to each user.

Andrew Swallow

Relevant Pages

  • Re: Monitoring the contents of a dynamic file
    ... Yes, on my SuSE 8.2 system, too. ... The protocol would seem to be flakey, if "tail -f" or standard/normal *nix ... either a lock file, ... However, that should function like a semaphore: ...
    (comp.os.linux.misc)
  • Re: smp race fix between invalidate_inode_pages* and do_no_page
    ... Such a workload ... >> fast path for the tree lock too. ... > protocol will need to be changed to "must return with the page locked". ... True" before unlocking (then the other side will have to block the pte ...
    (Linux-Kernel)
  • Re: Proposal: add pru_close protosw method, refactor abort/detach
    ... it refactors pru_detach and pru_abort into three protocol switch functions: ... pru_abort: socket is being aborted, generally due to insufficient queue space in a listen socket, or close of a listen socket while connections are waiting to be accepted: close abruptly and potentially with data loss. ... I realized, of course, that I omitted to specifically describe the specific chicken-and-egg problem that kicked this off: if the protocol lends a lock to the socket layer for use over the reference count, then the protocol detach must occur after any last possible use of that lock, and in the current world order, the lock was used several times after the call to detach -- possibly before a second call to detach, for example. ...
    (freebsd-arch)
  • Re: Keyless entry problem - 1999 New Beetle
    ... lock, but the drivers door does not. ... The driver and passenger doors failing didn't ... motor lines to see if it would operate. ...
    (rec.autos.makers.vw.watercooled)
  • Re: Glass Channel Removal =?windows-1252?Q?=96_2000_Concorde?=
    ... safety lock on the end of the door - instructions for that on same page ... followed by depression of lock button). ... I'm surprised Chrysler didn't lean on GECOM and get some form ... IOW what you would consider normally tight is not quite tight enough, and what you would normally consider a little too tight is about right. ...
    (rec.autos.makers.chrysler)
Quantcast