Security Protocols with Conventional Cryptography - A Classical Introduction to Cryptography: Applications for Communications Security - page 140

The password generation . The client is given a seed password w , and the server
is given a pair ( f n ( w ) , n ) associated with this client. Here, f is a one-way

function.
The access control scheme . When the client wants to access the server for the i -th
time, he sends w i =

f n − i ( w ) to the server. The server then checks that f ( w i )
is the first entry of the pair of the clients, retrieves the second entry which is
necessarily n − i + 1, and replaces this pair by ( w i , n − i ) in the database.

With this scheme, the number of accesses is limited to n . The server only has to make
one f computation. The client can implement a time-memory tradeoff: either he keeps
all f i ( w ) in memory and does not have to compute anything (if the client is a human
being, he can keep a sheet of passwords), or he only keeps w and makes on average

n
2

n
2 m

f -computations per access, or stores m different passwords and makes on average

f -computations per access.

5.3.2 S/Key and OTP

The Bellcore company developed a popular one-time software based on the Lamport
scheme: S/Key, which has also been published as an Internet document RFC 1760
(Ref. [85]). This was later transformed into an Internet standard: the one-time password
(OTP) system RFC 2289 (Ref. [86]).

In this standard, the one-way f function is MD5 by default. It can also be SHA-1
or MD4.

In addition to the format of transmission, this standard provides an interesting way
to represent passwords in a humanly readable way: the 64-bit password is first expanded
into 66 bits with a checksum. Then it is split into six 11-bit packets. Each packet is
encoded into a word given by a 2048-word dictionary of at most four alphabetical
characters. Thus, a 64-bit password is represented by six humanly readable short words.

In OTP, the user gives his password w (more precisely a secret pass-phrase of at least
10 characters) to the OTP generator. The generator generates a random seed s which
consists of 1-16 lowercase alphanumerical characters. It then hashes w concatenated
with s and reduces it to 64 bits using a standard function (see Ref. [86]). This produces
a string S

= ,

s ). (The purpose of the seed is to diversify the pass-phrase, since it
may very well be the case that the same pass-phrase is used in different applications by
a particular individual.) The generator then computes p i =

H ( w

H N − i ( S ) for i

N
with a given integer N and gives them to the user together with s . The OTP generator
also sends p 0 =

= 0 ,...,

H N ( S ) and s to the server and discards everything from its memory.
The server keeps the last 64-bit one-time password p , a sequence integer i which is
first set to 1, and s in memory with integrity protection.

When the user wants to access the server, the server sends a challenge

otp-

algorithm sequence integer seed