* 4 *

Identification and authentication

Fact of the week

Following the second world war, the now famous pair, Julius and Ethel Rosenberg were convicted and executed for spying on the U.S. bomb project for the Soviet Union in 1953. At one point they improvised a clever password system: a cardboard Jell-O box was torn in two and one half given to a contact whom they later would need to identify. The complex edge shape and colour matching made a complex key quite impossible to forge. Our bodies use a similar method of receptor identification of molecules for immune responses as well as for smell (with some subtleties). Without matching secrets it is impossible to prove someone's identity.

Chapter 2 Gollmann, chap 9 Stallings
In order to provide basic Orange Book style security mechanisms, we need to keep track of the identity of users who make requests of the system. Authentication means whether something is authentic. Usually we mean verifying somebody's identity. There are two reasons for authenticating users:

Login: username and password

When logging on to a `secure' operating system, we are asked to provide a username and a password. The username claims our identity; the password verifies that claim. If authentication succeeds, we are granted access to the system, and all of our activities then occur within the scope of an identifier which represents that user. On Unix-like systems, the username is converted into a global unique user-id number (UID). On Windows systems, the username is converted into a security-id (SID) which is only unique on a local host.

In distributed systems, identities need to be tracked between machines also. This means that one either needs

Unix and Windows handle these issues differently. Unix systems can be configured to do all of these things. Windows hosts have a trust model which is based on a single domain authentication. Once a user is admitted to a domain, he or she then has rights within any hosts which also belong to that domain. The identity is based on the username rather than the SID, since the SID of a given username is different, in general, from host to host. In the original Unix model, users had to share a common username on remote hosts if they were to avoid logging in with re-authentication. Using .rhosts files, a login would be trusted if only the user was entering from a host listed in the users's file.

There are obvious problems with password authentication.

Many users choose only weak passwords and these can then be guessed with a brute-force attack.

This type of login is called unilateral authentication, that is, it identifies the user to the computer. What is doesn't do is to verify the identity of the computer to the user (that would be bi-lateral authentication). So one problem which might occur is that an intruder could plant a fake login session on a computer, allowing them to collect passwords and account information. They could even provide a completely faked environment to fool users. Unix does not attempt to solve this problem, but NT provides a `secure attention sequence'. If the user types CTRL+ALT+DEL, they are directed to the operating system, rather than any user programs which might be trying to look like the OS.

How many times should be provide a password? Do we need several passwords for different levels of security? e.g.

In most cases a single login (single sign-on) is sufficient. Once authenticated, the user is in position of privileges which give access to everything they are allowed to see. Some systems have to be separated however, since they are completely disconnected from the system of credentials which are used for the user's login session. WWW is one such example.


There are alternatives to providing a password. For instance, biometrics is the name given to the field of identifying human physiology and psychology in order to use it for authentication: As noted in the film Gattaca, it is not impossible to spoof biometric data The point about using biometrics is to get away from the shortcomings og the password model, but there is a problem. We have, in fact, all of the problems of the password model and the added problem that we cannot change our biometric signatures if they are stolen. At least we can change passwords and digital signatures.

The biometric devices themselves have to be secure. While iris scanning is considered to be virtually infallible, there is always the chance that the scanner itself could be fed stolen biometric data unless designed with extreme care. Users would also have to be careful not to stick their irises in a machine which they did not know too much about!

Challenge/response and authentication protocols

In challenge/response systems, also called nonce or once-only methods (the word nonce is a little-used word from old English, meaning once-only from medævil "then ones"), the authenticator generates a random one-time challenge (question) and the client must then reply, using a secret key in order to encode the data. The simplest instance of this is simple the login challenge "Enter password". The challenge in the Monty Python film The search for the holy grail would not be a good challenge response system for two reasons: it was based on a `shared-secret' which anyone could have known, and also it was possible to destroy the authentication system and therefore hack in.

The OSI security architecture (ISO 7498-2) makes a distinction between origin authentication and entity authentication, i.e. who is calling and where they are calling from. The ISO/IEC 9798 is a security standard, being developed. It is published in various documents. We shall consider a few of the ideas it discusses.

We define:

Entity/origin authentication can only be satisfied for a finite period of time. Usually this is performed at the start of a session between client and server. Once we stop checking, an attacker could subsequently sneak in and change places with an authenticated user. Thus to ensure security in an on-going conversation, we have to verify identity and then use some kind of secret key to encrypt the conversation, which is only known by the authenticated parties (i.e. something which is exchanged as part of the process of authentication).

Properties of an authentication protocol

Let's be a bit more formal about an authentication protocol: We assume that there are two parties A (Alice )and B (Bob), who exchange a finite number of messages:
       |                         |
       |           M1            |
       | --------------------->  |
       |           M2            |
    A  | <--------------------   |  B
       |           M3            |
       | --------------------->  |
       |           M4            |
       | <--------------------   |
       |                         |.
A starts the protocol by sending a message to B, M1. B replies with M2, etc. We assume that message N+1 is not sent until message N has been received and understood.

During or after the exchange of the messages we need to be sure of the following:

In general, it is not possible to satisfy these beliefs until the protocol has completed its exchange. The contents of the messages can be verified for their integrity in a number of ways (how do we know that no-one has messed with the messages in transit?): We must also verify that the message is not just a replay of an older message which someone piecked up by snooping on the network. There are two methods here: Note that time stamps rely on the existence of properly and securely synchronized clocks. This introduces a dependency. Since no transfer is instantaneous, we have to allow the time to have increased by a small amount since the message was sent. This introduces a window of opportunity for those who would try to exploit the protocol. In the nonce/challenge method, a random value is sent in the first message and is echoed back in reply ensuring that both parties agree on a `one-time session key'. For instance, one could encrypt subsequent messages with a random session key, established at the start. It is up to A to ensure that the challenge is new. Predictable sequences have been exploited, for instance, in IP sequence-guessing attacks.


Consider the following exchange. A single message sent from A to B. The message contains the time t and a password key which is shared only by A and B, called Kab.

       |                         |
       |      M1(t,Kab)          |
  A    | --------------------->  |  B
       |                         |

B can verify A's identity, but A cannot verify B's identity. B knows that A is A because the message is encrypted with Kab, which is secret. B knows that the message is fresh because the time can be checked. A does not know B's identity because B never confirms its identity in any way.

       |                         |
       |      M1(t1,Kab,S)       |
  A    | --------------------->  |  B
       |      M2(t2,Kab,S)       |
       | <---------------------  |
       |                         |

The second example is similar to the first but with A sending a nonce string S for the session. Now B replies, also using the encryption key Kab. Now A can also reason that, since B received M1 (this is known since the message S is returned by B in M2), and since M2 is encrypted by Kab, that the message does come from B. This is a mutual authentication. Clearly it requires a bidirectional exchange. Both hosts know that the session is not a replay, since the time is included and also the session string should be unique. If the session string S is also unique, then time stamps are redundant.

Keys and trust

The security of keys cannot be emphasized enough here. We are trusting the encryption as though it were confirmation of identity. This means we also trust the hosts where the keys originated. Protocols which are based on a shared secret Kab, need a separate key for each pair of hosts A and B. This could be a lot of keys. One possibility is to have a single common trusted key-pair for all hosts (a zone of trust) and for hosts to identify themselves as part of the protocol.
This presupposes that the hosts all trust one another. An alternative is to use a public/private key pair like PGP. This requires only a trusted method of distributing keys. Often this is accomplished through a Trusted Third Party (TTP).

Needham-Schroeder protocol

One protocol for establishing identity was devised in 1978 by R. Needham and M. Schroeder. It uses the idea of a trusted third party and private keys, or password-based encryption to pass messages.

Suppose Alice wants to send a message to Bob. Both Alice and Bob have already registered a secret key, protected by a password, with a trusted key server (Sam). They assume that everyone else in their local domain has done the same. The trick is to establish an encryption key (K) from A to B, given only the keys they have between themselves and Sam, without an attacker being able to understand the messages. Essentially Alice asks Sam to encrypt a message to Bob for her, without giving away Bob's key.

1. A -> S : A,B,Na
2. S -> A : {Na,B,Kab,{Kab}Kbs}Kas
3. A -> B : {Kab}Kbs
4. B -> A : {Nb}Kab
5. A -> B : {Nb-1}Kab
Recall that the curly braces mean a message which is encrypted, using the key subscripted. In words, this says the following:
  1. Alice say to Sam: "I am Alice, I want to talk to Bob and I'm giving you a random nonce Na."
  2. Sam replies, quoting her nonce to show that he is a good beauracrat, confirms that the message is about a key with Bob, provides a key for encrypting messages between Alice and Bob. He also provides a message for Bob, already encrypted with the secret key that Bob and Sam share (Kbs). This message contains Alice's name and the session key (Kab) for talking to Alice privately. All of this is encrypted with the private key that Alice and Sam share (Kas).
  3. Alice simply sends the message which Sam encrypted to Bob. This is already encrypted.
  4. Bob decrypts the message and replies using the session key (Kab) with a nonce of his own to make sure that Alice is awake, i.e. that this is not a replay.
  5. Alice responds that she received the nonce.
Alice and Bob are now ready to talk, using the key (Kab).

This protocol is the basic for the Kerberos system, which is used in many Unix and Windows 2000 systems. The protocol is still controversial, after 20 years because it is not possible for Bob to tell whether the key (Kab) is fresh. It could also be twenty years old! This is not necessarily a problem, in practice, but in principle this might be exploited by an attacker.

Thought of the week

Steganography is about hiding messages within other messages, so that even the existence of a secret message is secret! Recently messages have been concealed in images...