Modern Encryption Methods in User Authentication

Lasse Huovinen
Department of Computer Science and Engineering
Helsinki University of Technology
Lasse.Huovinen@hut.fi

Tutor: Timo.Rinne@hut.fi

Abstract

This paper describes how (modern) encryption methods can be used in user authentication. Also, this paper includes case studies part which describes some systems where encryption is used for user authentication. Attacks on these systems are described if any is known.
Keywords: authentication, encryption, public-key, symmetric-key, user

Abbreviations
1. Introduction to user authentication 1.1. Weak authentication (passwords) 1.2. Zero-knowledge identification
2. Strong Authentication (Challenge-response identification) 2.1. Symmetric-key techniques 2.2. Public-key techniques 2.3. Attacks on user authentication protocols
3. Case studies 3.1. VeriSign 3.2. Kerberos 3.3. Secure Shell (SSH) 3.4. SecurID
4. Conclusions
5. References

Abbreviations

ATM: Automatic Teller Machine
DES: Data Encryption Standard
DSA: Digital Signature Algorithm
FFS: Feige-Fiat-Shamir
GQ: Guillou-Quisquat
HTTP: Hyper Text Transfer Protocol
IP: Internet Protocol
MAC: Message Authentication Code
MD5: Message Digest 5
MIT: Massachusets Institute of Technology
OS: Operating System
PIN: Personal Identification Number
SSH: Secure SHell
TCP: Transmission Control Protocol
ZK: Zero-Knowledge

1. Introduction to user authentication

The purpose of user authentication is that the claimant, A, can prove to the verifier, B, that the claimant is really A. The verifier has, or presumes beforehand, some information from the claimant so that the indentity of the claimant can be verified. The reference [1] defines user authentication in the following way.

Definition 1.1
User authentication is the process whereby one party is assured (through acquisition of corroborative evidence) of the identity of a second party involved in a protocol, and that the second has actually participated (i.e. is active at, or immediately prior to, the time the evidence is acquired).

Using user authentication the service provider can supervise service users' access to the service. The service can be, e.g., access to computer system, ATM, physical entry to restricted area, or cellular telephone network.

From point of view of the verifier, the result of an authentication process can be either completion with acceptance (i.e. acceptance of the claimant as authentic) or termination without acceptance (i.e. rejection). The reference [1] defines more specific objectives of an authentication process in the following way.

In the case of honest parties A and B, A is able to succesfully authenticate itself to B, i.e., B will complete the process having accepted A's identity.
B cannot reuse an identification exchange with A so as to successfully impersonate A to a third party C. (transferability)
The probability is negligible that any party C distinct from A, carrying out the protocol and playing the role of A, can cause B to complete and accept A's identity. Here negligible typically means "is so small that it's not of practical significance"; the precise definition depends on the application. (impresonation)
The previous remains true even if: a (polynomially) large number of previous authentications between A and B have been observed; the attacker C has participated in previous protocol executions with either or both A and B; and multiple instances of the protocol, possibly initiated by C, may be run simultaneously.

Authentication techniques are usually divided into three main categories. The division depends which security is based on. [1],[2]

There is something known. For example, passwords, PIN -codes, and the secret or private keys. Passwords and PIN -codes are told to the verifier when asked from the claimant. The knowledge of the secret or private key is demonstrated in challenge-response protocols.
There is something possessed. In this case the claimant has typically some physical accessory, e.g., magnetic-striped card, smart card or (hand-held) password generator.
There is something individual characteristics to a human. For example, handwritten signatures, fingerprints, voice or retinal patterns.

In this paper, mainly category 1 is discussed, but category 2 is also considered. Category 3 is out of the scope of this paper. The category 1 can be divided to sub-categories which are passwords (weak authentication), zero-knowledge identification, and challenge-response identification. These are discussed later in this paper.

Authetication protocols have many properties. The following lists some of the most important properties.[1] These are needed later in this paper.

reciprocity of identification. Either one or both parties may corroborate their identities to the other, providing, respectively unilateral or mutual identification. Some techniques, such as fixed-password schemes, may be susceptile to an entity posing as a verifier simply in order to capture a claimant's password.
computational efficiency. The number of operations required to execute a protocol.
communication efficiency. This includes number of passes (message exchanges) and the bandwidth required.
real-time involvement of a third party (if present). Examples of third parties include an on-line trusted third party to distribute common symmetric keys to communicating entities for authentication purposes; and an on-line (untrusted) directory service for distributing public-key certificates, supported by an off-line certification authority.
nature of trust required in a third party (if present). Examples include trusting a third party to correctly authenticate and bind an entity's name to a public key; and trusting a third party with knowledge of an entity's private key.
nature of security guarantees. Examples include provable security and zero-knowledge properties.
storage of secrets. This includes the location and method used to store critical keying material.

1.1. Weak authentication (passwords)

Usually, by weak authentication is meant using conventional passwords. As everybody knows, a password is typically a string of length 6 to 10 (sometimes more) characters and is associated to a particular user. When a user wants to become authenticated in multiuser environment, she gives her name (i.e. login name) and password. The system checks if these are correctly related to each other and then accepts or rejects her. This method is not very safe, because of password disclosure, line eavesdropping, and password guessing or dictionary attacks. If password file is in clear text, at least, superusers can read it very easily.

Better result can be achieved by crypting password file or using one-way functions. In these cases, rather than saving the password itself the encrypted password, or the result of one-way function is saved to the file. When user enters a password, the system computes a result from it and compares the result with the saved result. Usually one-way function is considered preferable than encryption.

Some additional methods to achieve better security are password salting, passphrases, and one-time passwords.

1.2. Zero-knowledge identification

The idea behind zero-knowledge (ZK) protocol is that the verifier doesn't get any useful information of the claimant's secret. If the verifier gets claimant's secret, it can use it to impersonate A later. Althought challenge-response protocols are time-variant, some partial information may be revealed to the verifier, and it can strategically collecting material find out the whole secret. ZK protocols are designed to prevent this, by allowing a claimant to demostrate knowledge of the secret without relevealing any useful information to the verifier. The point is that only a single bit of information needed ; the claimant either knows the secret or not.

Generally speaking, a ZK protocol allows a proof of the truth of an assertion, while conveying no information whatsoever about the assertion itself other than its actual truth. So, it can be said that a ZK proof is similar to an answer obtained from a (trusted) oracle[1].

Some examples on zero-knowledge protocols are Fiat-Shamir, Feige-Fiat-Shamir (FFS), and Guillou-Quisquater (GQ).

2. Strong Authentication (Challenge-response identification)

This chapter describes the idea behind cryptographic challenge-response protocols. Also some protocols are introduced here and the general idea how to attack on cryptographic challenge-response protocols is described.

The main idea behind cryptographic challenge-response protocols is that the claimant proves its identity to the verifier without revealing the secret information during the protocol. In a way, one can think claimant demonstrates to the verifier it has the knowledge of the secret information (in some mechanisms, the secret is known by the verifier, and is used to verify the response; in other mechanisms, the secret is not actually known by the verifier).

Generally, challenge-response protocols work in the following way. The verifier sends a time-variant challenge to the claimant. The claimant computes a response from the challenge using some encryption algorithm (e.g. RSA or DES) and sends the response to the verifier. So, the response depends on the challenge and the secret information. Usually the challenge is a number which is selected randomly (and secretly) by the verifier. The response shouldn't leak useful information about the secret to an enemy from any execution of the protocol.

Before studying the protocols, let's study something on time-variant parameters. Time-variant parameters may be used in the identification protocols to counteract replay and interleaving attacks, to provide uniqueness to timeliness guanrantees, and to prevent certain chosen-text attacks[1]. These time-variant parameters are called usually nonces (or unique numbers, or non-repeating values). The reference [1] defines nonce in the following way.

Definition 2.1
A nonce is a value used no more than once for the same purpose. It typically serves to prevent (undetectable) replay.

Generally, nonces can be divided to the following three main categories:

Random numbers.
In challenge-response protocols random numbers are used to provide uniqueness and timeliness assurances, and to preclude certain replay and interleaving attacks. If random numbers are "very random", they can be used to provide unpredictability to preclude chosen text attacks. The system works so that one entity includes a random number in an outgoing message. An incoming message subsequently received, whose construction required knowledge of this nonce and to which this nonce is inseparably bound, is then deemed to be fresh based on the reasoning that the random number links the two message. The non-tamperable binding is required to prevent appending a nonce to an old message.
Sequence numbers.
A sequence number (typically serial number, or value of a counter) serves as a unique number identifying a message, and is typically used to detect message replay. For stored file, sequence numbers may serve as version numbers for the file in question. Sequence numbers are specific to a particular pair of entities, and must explicitly or implicitly be associated with both the originator and recipient of a message; distinct sequences are customarily necessary for messages from A to B and from B to A.
Timestamps.
Timestamps may be used to provide timeliness and uniqueness guarantees, to detect message replay. They can be used to implement time-limited access privileges, and to detect forced delays, too. Timestamps work in authentications protocols in the following way. An entity cryptographically binds a timestamp, which is obtained from its local clock, to a message. When the second entity receives the message, it obtains the current time from its local clock and then it subtracs the timestamp from the current time. Generally, the received message is consireded to be valid if the next two conditions are provided:
1. The difference between timestamp and local time is within the acceptance window. The acceptance window depends on the system and it considers maximum message transfer time (selected e.g. by the system admistrator), maximum message processing time, and clock skew. The window size can vary from few milliseconds to tens of seconds.
2. No message from the same sender is not previously received with the same timestamp. This is considered as an optional condition, but when this condition is omitted the acceptance window have to be small enough so, that message replay is not possible. The check can be done e.g. maintaining a list of received timestamps, or storing the latest valid timestamp and accepting only increasing timestamp values. It may demand quite large storage space to save this all information.
Using timestamps for user authentication requires that host clocks are available, they are synchronized (not necessarily very strictly), and they cannot be modified by any unauthorized person (old messages can be made valid, or future messages can be know beforehand).

When using timestamps in protocols some advantages are achieved; typically, one message less is needed and no pairwise long-term state information like with sequence numbers or per-connection short-term state information like with random numbers is needed. With timestamps a drawback is to synchronize the distributed clocks. If synchronizing algorithm is not secure then the authentication will become unsecure, too. Typically, timestamp can be replaced with random or sequence number and a return message.

2.1. Symmetric-key techniques

Symmetric-key techniques require that the verifier and the claimant have the same common symmetric key. Sharing the symmetric key can be done in different ways. For small number of users in a closed system key can be shared manually. For larger systems usually trusted on-line server is used. In the latter case both entities ask their symmetric key from the server.

The Needham-Schroeder shared-key protocol is the basis for many server-based authentication protocols (e.g. Kerberos). This protocol is not important anymore except for historical reasons. This protocol has a weakness since B has no possibility to know if the key k is fresh or not. So, B has no possibility to know if the session key k should be accepted. So, any party knowing k may both resend message and compute a correct message to impersonate A to B. Instead of this protocol, e.g., Kerberos should be used. (See 3.1)

Needham-Schroeder[1],[3]
Let's A denote claimant, B verifier and T trusted server. E is a symmetric encryption algorithm (e.g., DES), N_A and N_B are nonces chosen by A and B. A and T share a symmetric key K_AT, B and T share a symmetric key K_BT. T selects a session key k for A and B to share. With these markings, Needham-Schroeder protocol sends the next messages.

(1) A -> T: A,B,N_A

(2) A <- T: E_{K_AT}(N_A,B,k,E_{K_BT}(k,A))

(3) A -> B: E_{K_BT}(k,A)

(4) A <- B: E_k(N_B)

(5) A -> B: E_k(N_B-1)

Consider the following user authentication method which is called ISO/IEC 9798-2. ISO/IEC 9798-2 includes three different kind of mechanisms.

ISO/IEC 9798-2 mechanisms[1]
Let's r_A denote random number and t_A denote a timestamp, which are generated by A. Here timestamp could be replaced by a sequence number, providing slightly different quarantees. E_K denotes a symmetric encryption algorithm, with a key K shared by A and B. Alternatively distinct keys K_AB and K_BA could be used for uni-directional communication. It is assumed that both parties are aware of the claimed identity of the other, either by context or by additional (insecured) cleartext data fields. Optional message fields are denoted by an asterisk (it is used in the same meaning later, too).

unilateral authentication, time-stamp based:

(1) A -> B: E_K(t_A,B^*)
When B has received and decrypted the message, it verifies that the timestamp is acceptable, and optionally verifies the received identifier is its own. The identifier B here prevents an attacker from re-using the message immediately on A, in the case that a single bidirectional key K is used.
unilateral authentication, using random numbers:
To avoid reliance on timestamps, the timestamp may be replaced by a random number, at the cost of an additional message:

(1) A <- B: r_B

(2) A -> B: E_K(r_B,B^*)
B decrypts the received message (2) and checks that the random number matches that sent in (1). Optionally, B checks that the identifier in (2) is its own; this prevents a reflection attack in the case of a bi-directional key K. To prevent chosen-text attacks on the encryption scheme E_K, A may embed and additional random number in (2) or the form of the challenges can be restricted, but it is very important that they are not repeating.
mutual authentication, using random numbers:

(1) A <- B: r_B

(2) A -> B: E_K(r_A,r_B,B^*)

(3) A <- B: E_K(r_B,r_A)
After B has received the message in (2), it carries out the checks as above and, in addition, recovers the decrypted r_A for inclusion in (3). After A has decrypted the message in (3), it checks that both random numbers match those used earlier. The second random number r_A in (2) serves both as a challenge and to prevent chosen-text attacks.

When challenge-response protocols are used, some kind of computing device and a secure storage for long-term keying material is needed. Quite often, to achieve additional security, a device such as a chipcard can be used for both the key storage and response computation. Of course, a card reader is necessary. Other device (sometimes cheaper) is a passcode generator. Next, let's study how a simple passcode generator works.

The picture 2-1 shows a functional diagram of a simple passcode generator. Usually passcode generators are hand-held devices with size of a pocket calculator. The device contains a device-specific secret key. When user inputs challenge to the generator, it computes a response and shows it on the small display. The user inputs the response from the display to the system. The verifier then checks this response using information stored inside the system. The response is computed from the challenge and the secret key.

This kind of authentication mechanism can be done more secure using (optional) PIN -code. The PIN can be verified locally or the response can depend on it. The main security drawback in using passcode generators is the requirement to maintain the security on the system side. Of course, it's not very convenient to carry generator always with you, too.

Picture 2-1. The idea of a passcode generator[1].

2.2. Public-key techniques

Public-key techniques are based on secret/public key pair. In user authentication public-key techniques can be used so, that claimant demonstrates knowledge of its private key. There are two ways to do that:

The claimant decrypts a challenge which verifier has encrypted using claimants public key.
The claimant digitally signs the challenge and the verifier checks the signature.

To keep this mechanism secure the key pair shouldn't be used any other purpose, because combined usage may compromise security. Also, the used public-key algorithm shouldn't be sensitive to chosen-chiphertext attacks. An attacker can attempt to extract information by stealing the role of the verifier and choosing strategic rather than random challenges.[1],[2]

Incorporating a self-generated random number (so called confounder) into the data over which the response is computed may be helpful with these problems. Such data may be made available to the verifier in cleartext to allow identification.[1]

Challenge-response based on public-key decryption.[1]
Let's study the following protocols.

Public-key decryption and witness.
Here P_A denotes the public-key encryption (e.g. RSA) algorithm of A, and h denotes a one-way hash function.

(1) A <- B: h(r),B,P_A(r,B)

(2) A -> B: r
B chooses a random number r, computes the witness x=h(r) (x demonstrates knowledge of r without disclosing it), and computes the challence e=P_A(r,B). B sends (1) to A. A decrypts e to recover r' and B', computes x'=h(r'), and quits if x' is not equal to x (implying r' is not equal to r) or if B' is not equal to its own identifier B. Otherwise, A sends r=r' to B. B succeeds with (unilateral) entity authentication of A upon verifying the received r agrees with that sent earlier. The use of the witness precludes chosen-text attacks.

Modified Needham-Schroeder public-key identification protocol.
The modified Needham-Schroeder public-key protocol provides mutual authentication and key transport of distinct keys k₁,k₂ from A to B and from B to A, respectively. If the key establishment feature is not required, k₁ and k₂ may be omitted. With P_B denoting the public-key encryption algorithm for B (e.g. RSA), the messages in the modified protocol for user authentication are then as follows (keys are omitted):

(1) A -> B: P_B(r₁,A)

(2) A <- B: P_A(r₁,r₂)

(3) A -> B: r₂

Challenge-response based on digital signatures.[1]
Let's study the following protocols.

X.509 mechanisms based on digital signatures.
The ITU-T X.509 two and three-way strong authentication protocols specify identification techniques based on digital signatures and, respectively, timestamps and random number challenges. Optionally, these protocols can be used for transporting keys. Since key transporting is out of the scope of this paper, it is not presented here.

X.509 strong two-way protocol.
Let r_A and r_B denote never re-used numbers, and cert_A and cert_B denote certificates binding parties A and B to public keys which are suitable for both encryption and signature verification. S_A(x) denotes the result of applying A's signature private key to x (respectively to B). Let's assume that both parties have their public key pairs for signatures and encryption. Also, A must have B's (authenticated) public key. With these markings and assumptions the next messages are sent during authentication:

(1) A -> B: cert_A,D_A,S_A(D_A)

(2) A <- B: cert_B,D_B,S_B(D_B),
where D_A=(t_A,r_A,B), D_B=(t_B,r_B,A,r_A)
A obtains a timestamp t_A indicating an expiry time, generates r_A and sends a message to B. After B has received the message, it verifies the authenticity of cert_A, extracts A's signature public key and verifies A's signature on the data block D_A. After that B checks that the identifier in message (1) specifies itself as intended recipient, the timestamp is valid, and checks that r_A hasn't been relayed. If these all checks succeed, B declares the authentication of A successful. Now B obtains timestamp t_B, generates r_B, and sends a message to A (2). When A has received the message, it carries out analogous actions as B did. If all checks succeed, A declares the authentication of B successful.

Because the previous protocol doesn't specify inclusion of an identifier within the scope of the encryption P_B within D_A, one can't guarantee the signing party actually knows the plaintext key.[1]

X.509 strong three-way protocol.

(1) A -> B: cert_A,D_A,S_A(D_A)

(2) A <- B: cert_B,D_B,S_B(D_B)

(3) A -> B: (r_B,B), S_A(r_B,B)
Three-way protocol differs from two-way protocol in the following way. Timestamps may be set to zero and it is not necessary to check them. When receiving (2), A checks the received r_A matches that in message (1). When receiving (3), B verifies the signature matches the received plaintext, that plaintext identifier B is correct, and that plaintext r_B received matches that in (2).

ISO/IEC 9798-3 mechanisms.
ISO/IEC 9798-3 includes three challenge-response identification mechanisms based on digital signatures. These mechanisms are analogous to the ISO/IEC 9798-2 techniques which are based on symmetric keys (see 2.1). As in 9798-2, let's r_A and t_A, respectively, denote a random number and timestamp generated by A. S_A denotes A's signature mechanism (e.g., DSA); if this mechanism provides message recovery, some of the cleartext fields listed below are redundant and can be omitted. cert_A denotes the public-key certificate containing A's signature public key. (In these mechanisms, if the verifier has the authentic public-key of the claimant a priori, certificates can be omitted; otherwise, it's assumed that the verifier has appropriate information to verify the validity of the public key contained in a received certificate).

unilateral authentication with timestamps:

(1) A -> B: cert_A,t_A,B,S_A(t_A,B)
When B has received the message, it verifies that the timestamp is acceptable, the received identifier B is its own, and (using A's public key extracted from cert_A after verifying the latter) checks that the signature over these two fields is correct.

unilateral authentication with random numbers:
In this protocol reliance on timestamps is replaced by a random number, at the cost of an additional message.

(1) A <- B: r_B

(2) A -> B: cert_A,r_A,B,S_A(r_A,r_B,B)
B verifies that the cleartext identifier is its own, and using a valid signature public-key for A (e.g., from cert_A), verifies that A's signature is valid over the cleartext random number r_A, the same number r_B as sent in (1), and this identifier. The signed r_A explicitly prevents chosen-text attacks.

mutual authentication with random numbers:

(1) A <- B: r_B

(2) A -> B: cert_A,r_A,B,S_A(r_A,r_B,B)

(3) A <- B: cert_B,A,S_B(r_B,r_A,A)
Processing of (1) and (2) goes as above, and (3) is analogous to (2).

2.3. Attacks on user authetication protocols

This chapter concerns attacks on user authentication protocols. The following lists some definitions of attacking which are given in reference [1].

Definition 2.2

impresonation: a deception whereby one entity purports to be another.
replay attack: an impersonation or other deception involving use of information from a single previous protocol execution, on the same or different verifier. For stored files, the analogue of a replay attack is a restore attack, whereby a file is replaced by an earlier version.
interleaving attack: an impersonation or other deception involving selective combination of information from one or more previous, or simultaneously ongoing protocol executions (parallel sessions), including possible origination of one or more protocol executions by an attacker itself.
reflection attack: an interleaving attack involving sending information from an ongoing protocol execution back to the originator of such information.
forced delay: a forced delay occurs when an attacker intercepts a message (typically containing a sequence number), and relays it at some later point in time. Note the delayed message is not a replay.
chosen-text attack: an attack on a challenge-response protocol wherein an attacker strategically chooses challenges in an attempt to extract information about the claimant's long-term key. Chosen-text attact can be considered so that claimant is an oracle, i.e., to obtain information not computable from knowledge of a claimant's public-key alone. The attack may involve chosen-plaintext if the claimant is required to sign, encrypt, or MAC challenge, or chosen-ciphertext if requirement is to decrypt a challenge.

When a system is wanted to be protected against attacks the following principles can be useful. At first, type of attack is described and then a way how to protect against it.

replay
use of challenge-response techniques, use of nonces, embeded target identity in response
interleaving
linking together all messages from a protocol run (e.g. chained nonces)
reflection embed identifier of target party in challenge-responses, construct protocols with each message of different form (i.e., avoiding symmetry in messages), using uni-directional keys
forced delay
combined use of random numbers with short response time-outs, timestamps with another appropriate additional techniques
chosen-text
use of zero-knowledge techniques, embed in each challenge response a confounder (e.g., self-chosen random number)

The first four types of attacks include impersonation. Impersonation is also very easy in the case, if attacker is able to discover an entity's long-term key material. This can be possible in protocols which may leak some partial information of the secret (i.e. non-ZK protocols).

During all user authentication protocols between A and B, an attacker C may come on the communication line and simply relay (without modificating) the messages between legitimates parties A and B. So, A and B see C as a communication link. Usually this is not considered as an "attack", because it doesn't alter aliveness assurance delivered by the protocol. Some special applications may suffer this problem[1]. Since identification protocols do not provide assurances about the physical location of the authenticated party, the following can be possible is some special cases. This is known as grandmaster postal-chess problem. An attacker C attemps to impersonate B, is challenged (to prove it's B) by A, and is able to relay the challenge on to the real B, get a proper response from B, and passes this response along back to A. In this case, additional measures are necessary to prevent a challenged entity from elicting aid in computing responses. Also, keys shouldn't use for many purposes, because it may allow chosen-text attacks.

Quite often authentication protocols guarantee the identity only at a given instant in time. However, sometimes the identity should be guaranteed for a long time. For example, if an attacker comes on the line just after successful authentication and communication has begun, some additional methods are needed. Actually, there exist a couple of ways to handle this problem. Firstly, the system can perform re-authentication periodically or for each different resource. Secondly, the authentication process can be tied to an ongoing integrity service. In this case, the authentication process should be integrated with a key establishment mechanism, such that a by-product of successful identification is a session key appropriate for use in a subsequent ongoing integrity mechanism[1].

Finally let's see someting about required security level for on-line versus off-line attacks. Generally the required security level for identification protocol depends on the environment and the used application. The probability of success of guessing attacks should be considered, and distinguished from the amount of computation required to mount on-line or off-line attacks (using the best known techniques). The following lists some examples from the reference [1].

Local attacks.
Selecting security parameters which limit the probability of successful impersonation of a guessing attack to a 1/2²⁰ chance may suffice if, for each attempted impersonation, a local appearance is required by the would-be impersonator and there is a penalty for failed attempts. Depending in the potential loo resulting relative to the penalty, 10 to 30 bits or more of security may be necessary.
Remote attacks.
Not surprisingly, a higher level security is necessary to keep remote attackers outside the system (e.g., hosts in a large network). If number of interactions is not limited at least 40 bits of security should be used.
Off-line attacks.
When security parameters are selected so that that attack requires 2⁴⁰ computations in real-time (during a protocol execution) may be acceptable, but at least 2⁸⁰ computations should be needed if the computations are carried out off-line and the attack is verifiable. This means attacker can confirm that probability of successful impersonation is (near) 100%.

3. Case studies

This chapter contains case studies of some well-known user authentication systems which rely on encryption.

3.1. VeriSign [4],[5],[6],[12]

VeriSign Incorporation grew out of RSA Data Security in 1995. At that time leaders of the RSA Data Security realized digital authentication was different business from RSA's. So, at the moment VeriSign Inc. is well-doing incorporation and it's products are Digital ID public- and private-label certificates. This chapter explains something about VeriSing DigitalIDs.

VeriSing can be considered as a trusted third party. When the company wants to activate new public key certificates, seven authorized people have to be present. Each person has chip-embeded plastic key.

VeriSign offers four classes of digital certificates. The following lists classes and examples of them.

Class 1:
Web site access control, secure e-mail
Class 2:
Web site access control, secure e-mail, commercial transactions
Class 3:
Access control, secure e-mail, High-value transactions, legal transactions
Class 4:
Access to enterprise sites such as banks, and corporates' confidential information.

VeriSign has a DigitalID Center which issues ID Classes 1 and 2 for Internet email and WWW users (the Center is located in DigitalID.verisign.com). For ID classes 3 and 4 registration is online and verification is offline.

VeriSign's technology for checking certificates can be integrated to application software, e.g., web browsers and mailing software. After integration the system checks transparently public key codes associated with those files. The user gets information only if something is wrong with these codes. For encrypting VeriSign uses RSA public-key algorithm.

A rumour tells that there is some kind of back door in the VeriSign system. Obviously, if that is true, authentication is not legally valid.

3.2. Kerberos

Kerberos is an authetication protocol which uses secret-key cryptography. This protocol was created in Athena project in Massachusets Institute of Technology (MIT). Because strong cryptography is used this the protocol can be used across an insecure network connection. Kerberos is freely available from MIT.[3],[7] The rest of this chapter describes the implementation of Kerberos and some security holes are introduced. The presentation of Kerberos protocol is based on references [1],[3],[7], and [9].

In the Kerberos protocol a series of encrypted messages is used to prove to the verifier that the claimant is who it claims to be. Partly, Kerberos is based on the Needham-Schroeder authentication protocol (see 2.1). It can be thought that the client is running on behalf the user. To be more presice the client has knowledge of an secret key which is known only by the user and the authentication server. The user's encryption key is derived from a password. Similarly, each application server shares an encryption key with the authentication server and it is called server key.

When a message is sent in Kerberos, it calculates a checksum for each message. If encrypted message is tried to open with wrong key or the message is changed the checksum doesn't match the data anymore and so message is ignored. Kerberos uses DES for encryption.

Initially, the server doesn't have an encryption key for a particular user. When a client (a user) wants to become authenticated on a server, the client asks authentication server to create a new encryption key and to distribute it securely to both parties. This new encryption key is called a session key and the message which is used to distribute the key to verifier is called Kerberos ticket. This ticket is a certificate issued by an authentication server, encrypted using the server key. Among other information, the ticket contains the random session key that will be used for authentication of the principal to the verifier, the name of the principal to whom the session key was issued, and an expiration time after which the session key is no longer valid. The ticket is not sent directly to the verifier, but is instead sent to the client who forwards it to the verifier as part of the application request. Because the ticket is encrypted under the server key, known only by the authentication server and intended verifier, the client cannot modify the ticket without detection.

The picture 3-1 and the following message chart explain the basic Kerberos protocol. The following lists abbreviations usually used with Kerberos.

C = client (claimant)
S = server (verifier)
K = Kerberos (authentication server)
a = client's network address
v = beginning and ending validity time for a ticket
t = timestamp
r = random number
K_x = x's secret key
K_x,y = session key for x and y
{m}K_x = m encrypted under x's secret key
T_x,y = x's ticket to use y
A_x,y = authenticator from x to y

(1) C -> K: C, S, v, r

(2) C <- K: {K_C,S,S,v,r}K_C,{T_C,S}K_S

(3) C -> S: {t,A_C,S} K_C,S,{T_C,S}K_S

(4) C <- S: {t}K_C,S (optional)

Picture 3-1. Kerberos authentication protocol (simplified situation).

When the verifier (S) has received the message (3), it decrypts the ticket, extracts the session key, and uses the session key to decrypt the authenticator. Now, if the same key was used to encrypt and decrypt the authenticator, the checksum will match and the verifier can assume the authenticator was generated by the entity named in the ticket and to whom the session key was issued. However, this is not sufficient for authentication since an attacker can intercept an authenticator and replay it later to impersonate the user. For this reason the verifier also checks the timestamp to make sure that the authenticator is fresh. If the timestamp is within a specified window (usually around 5 minutes), and if the timestamp has not been seen earlier within that window, the verifier accepts the request as authentic. Now the identity of the client has been verified by the server. Sometimes the client also wants to be sure of the server's identity. If such mutual authentication is required, the server generates an application response by extracting the client's time from the authenticator, and returns it to the client.

A separate ticket and session key are required for each client-verifier pair. When a client want to create a connection with a particular verifier, the client uses the authentication request and response ((1) and (2)) to obtain a ticket and session key from the authentication server (or Kerberos, K). In the request, the client sends the authentication server its claimed identity, the name of the verifier, a requested expiration time for the ticket, and a random number that will be used to match the authentication response with the request.

In response the session key, the assigned expiration time, the random number from the request, the name of the verifier are returned from authentication server. These all are encrypted with the user's password registered with the authentication server, together with a ticket containing similar information, and which is to be forwarded to the verifier as part of the application request. Together, the authentication request and response and the application request and response comprise the basic Kerberos authentication protocol.

When using the basic Kerberos authentication protocol, user must input the password every time she wants to become verified by a new verifier. Someone may find this quite irritating. The obvious solution is cache user's password to the workstation when she logs in. This system has a dangerous backward. Though a Kerberos ticket and the key associated with it are valid for only a short time, the user's password can be used to obtain tickets, and to impersonate the user until the password is changed. More sophisticated way to solve this problem is to cache only tickets and encryption keys which will be valid for a limited time. Tickets and encryption keys are called credentials.

The ticket granting exchange of the Kerberos protocol allows a user to obtain tickets and encryption keys using such short-lived credentials, without re-entry of the user's password. When the user first logs in, an authentication request is issued and a ticket and session key for the ticket granting service is returned by the authentication server. This ticket, called a ticket granting ticket, has a relatively short life (typically on the order of 8 hours). The response is decrypted, the ticket and session key saved, and the user's password forgotten.

In a system that crosses organizational boundaries, it is not appropriate for all users to be registered with a single authentication server. Instead, multiple authentication servers will exist, each responsible for a subset of the users or servers in the system. The subset of the users and servers registered with a particular authentication server is called a realm (if a realm is replicated, users will be registered with more than one authentication server). Cross-realm authentication allows a principal to prove its identity to a server registered in a different realm.

To prove its identity to a server in a remote realm, a Kerberos principal obtains a ticket granting ticket for the remote realm from its local authentication server. This requires the principals's local authentication server to share a cross-realm key with the verifier's authentication server. The principal next uses the ticket granting exchange to request a ticket for the verifier from the verifier's authentication server, which detects that the ticket granting ticket was issued in a foreing realm, looks up the cross-realm key, verifies the validity of ticket granting ticket, and issues a ticket and session key to the client. The name of the client, embedded in the ticket, includes the name of the realm in which the client was registered.

The Kerberos authentication protocol has many weaknesses. These are heavenly studied in the reference [8] and the rest of this chapter is based on the same reference.

The following lists some Kerberos' weaknesses:

Replay attack
This is consireded to be the most serious weakness. Authenticator cannot prevent replay attacks. The authenticator relies on use of a timestamp to guard against reuse. The claim is made that no replays are likely within the lifetime of the authenticator (about 5 minutes). This is reinforced by the precense of the IP-address in both the ticket and the authenticator. The problem is here. An intruder would not start by capturing a ticket and authenticator, and then develop the software to use them; rather, everything would be in place before the ticket-capture was attempted.
Time Services
Authenticator relies in machines' clock that they are approximately synchronized. If an attacker can mislead a host from the correct time, a stale authenticator can be replayed very easily. So, this problem is very much dependend on used synchronization protocols.
Password guessing
If an attacker records login dialogs, she has good possibilities to find several new passwords and typically users don't select good passwords.
Spoofing login
This is not barely problem of Kerberos, but it negates one of its primary advantages; password is never transmitted in cleartext format over a network. Namely, the attacker uses login -program which records users password before they are encrypted.
Inter-session chosen plaintext attacks.
Exposure of session keys.
The scope of tickets.

3.3. Secure Shell (SSH)

Secure Shell (SSH) is a product of Data Fellows. Originally, SSH has been developed by Tatu Yl�nen.

SSH offers transport -layer security -mechanism using packet mechanism and related authentication, key exchange, encryption, and integrity. An attacker is limited to only breaking the connection.[10] The rest of this chapter explains host authentication and user authentication methods used in SSH.

The SSH server sends its public RSA host key and another public RSA key, called server key, that changes every hour. Then the client compares the received host key against its own database of known host keys. Usually SSH server accepts the key of an unknown host and store it in its database for future reference (this makes use of SSH practical and flexible in most environments), but server can also be configured to refuse access to any hosts whose key is not known.

The picture 3-2 shows the message flowchart between client and server.

The client sends a message to the server. This message is formed in following way. The client generates a 256 bit random number (session key), chooses an encryption algorithm (e.g., IDEA or 3DES). Now the client encrypts the session key using RSA under both the host and the server keys. Now the message is ready.

With the host key the connection to the desired server host (only the server can decrypt the encrypted session key) is bound. The hourly changed server key is used to make decrypting recorded historic traffic impossible in the event that the host key becomes compromised. The host key is normally a 1024 bit RSA key, and the server key is 768 bits. Both keys are generated using a cryptographically strong random number generator.

When the server has received the message, it decrypts the message and recovers the session key. Now both entities start using the session key and the connection is encrypted. Finally, the server sends an encrypted confirmation to the client. When the client has received the confirmation it knows that the server was able to decrypt the key, and now it holds the proper private keys.

Now the server has been (successfully) authenticated, and encryption and integrity protection are in use on the transport-layer. Now the actual user authentication will start.

Picture 3-2. Message flowchart of SSH host identification procedure between client and server.

The actual user authentication can be done in many ways in SSH. The client starts the user authentication and it sends requests to the server. The server replies always "success" or "failure". In the latter case further authentication is needed.
The following lists current user authentication methods:[10]

Traditional password authentication. The password is transmitted over the encrypted connection. So, attackers cannot see the password in cleartext format.
A combination of traditional .rhosts or hosts.equiv authentication and RSA based host authentication. The server generates a 256 bits challenge, encrypts it with the client's public host key, and then sends it to the client. The client receives the encypted challenge. Then it decrypts it, computes MD5 of the challenge and some other information that binds the returned value to the particular session.
Pure RSA authentication. This method is based on the idea that possession of a particular private RSA key serves as authentication. The server has a list of accepted public keys. Authentication works similarly to host authentication in RhostsRSA.
SSH user authentication is quite flexible and so it's possible to add other authentication methods. For example, Data Dynamics SecurID cards (see 3.4).

In the local host runs a authetication agent. In the future this can be replaced with a smartcard. The meaning of the agent is to hold user's private RSA keys. The agent accepts authentication requests and gives back suitable answers. It never gives out the private keys. In the UNIX environments agents communicate with a SSH server using open file handles which are inherited by all children of the agent process. Other users cannot get access to the agent. Other OSs are using different mechanisms. The picture 3-3 shows this in UNIX. When the user connects to a SSH server the authentication requests are forwarded to the local machine where the authentication agent is running. This scheme offers possibility to take new connections and go through an arbitrarily long chain of hosts and still the authentication process will take place on the local machine and authentication keys need not be transmitted outside of the agent.

Picture 3-3. SSH user authentication agent in UNIX.

3.4. SecurID [11]

SecurID is a product of Metadigm Ltd. It is a credit sized device that displays a 6 digit number that changes in an unpredictable way every 60 seconds. When SecurID is used for user authentication, the user enters the number currently displayed when she logs in. The synchronized time and card codes are stored to an ACE server. The ACE server runs on a SPARC Solaris system. The ACE server can be accessed by other security systems and asked to verify a login attempt.

This system can be used to authenticate remote users on the Internet if Metadigm's FireWall-1 is used. Also, SecurID can be used to authenticate users on Post Offices, dial-up servers, and databases.

No more technical information were available on the Internet.

4. Conclusions

User authentication is becoming more and more important issue in security area. So far, most discussions of Internet have been focused on encryption, but now authentication is considered very important issue, too.

As we have seen, lot's of techniques have been developed to authenticate user's. For user authentication it is possible use passwords, encryption or zero-knowledge protocols. This paper described how symmetric key and public key techniques can be used for user authentication.

Instead of using secret passwords or passphrases, the "secret" can be obtained from a device. The device either computes the response or it knows a kind of password which is valid at the moment.

Encryption methods are preferable than passwords. However, in user authentication protocols which are based on encryption have security holes. For example, those protocols may leak some partial information and an attacker may be able to gather the secret from the partial information. So, ZK protocols are considered more secure than protocols which are based on encryption.

5. References

[1]: A.J. Menezes, P.C. van Oorschot, S.A. Vanstone. Handbook of Applied Cryptography, CRC Press Inc., 1997
[2]: G. J. Simmons Contemporary Cryptology, The Science of Information Integrity, 1992
[3]: Bruce Schneier Applied Cryptography, John Wiley & Sons Inc., 1996
[4]: Financial Service ONLINE July/August 1996, Faulkner & Gray, Inc. 1996
[5]: WebWeek January 6, 1997
[6]: The Red Herring June 1996