Lamport's one-time password algorithm (or, don't talk to complete strangers!)

A design pattern for securing client/service interactions with OTP

The Lamport algorithm for generating and applying one-time passwords (OTPs) is a simple solution that provides great value in the right context. Not only can the Lamport OTP scheme provide effective security for distributed client/service interactions, but it's also simple to comprehend and implement. Louis Iacona introduces the Lamport algorithm, then describes an OTP reference implementation for an extensible, Java-based library.

There's a subtle beauty in simple things that present great value. To paraphrase Albert Einstein, a solution to a problem should be as simple as it can be, but no simpler. Applying a one-time password (OTP) scheme between distributed systems makes it more difficult for a would-be intruder to access and gain unauthorized control of restricted resources such as data, physical devices, or service end points. An OTP scheme is obviously a step up from completely open access, or access limited only by physical network barriers. But a solution based on an OTP challenge also has some advantages over static, infrequently changing passwords, because the window of opportunity to gain access to credentials is much smaller. There's a practical place for either type of authentication, or even both used in concert.

The Lamport OTP approach is based on a mathematical algorithm for generating a sequence of "passkey" values, each successor value based on the value of its predecessor. This article presents a simple service that is made more secure by adopting the Lamport OTP scheme. I'll demonstrate the concept and mechanics of this approach through a series of client/service interactions. I'll also present a Java-implemented framework that the existing client/service components can easily leverage.

The mechanics of Lamport OTP

The core of the Lamport OTP scheme requires that cooperating client/service components agree to use a common sequencing algorithm to generate a set of expiring one-time passwords (client side), and validate client-provided passkeys included in each client-initiated request (service side). The client generates a finite sequence of values starting with a "seed" value, and each successor value is generated by applying some transforming algorithm (or F(S) function) to the previous sequence value:

S1=Seed, S2=F(S1), S3=F(S2), S4=F(S3), ...S[n]=F(S[n-1])

The particular transforming algorithm used can be as simple or complex as you like as long as it always produces the same result for a given value. The approach has no tolerance for randomness or variability in that value S' must always be generated from a given value S.

As a simple example, suppose the client wants to create a sequence of 10 values, starting with a seed value of 0, and our transforming algorithm adds 3 to the value it's given. The sequence would look like this:

0, 3, 6, 9, 12, 15, 18, 21, 24, 27

The sequence is to be managed as a traditional last-in, first-out (LIFO) stack collection: the client consumes it in reverse order, beginning with the last value and working down toward the seed value. As you'd expect, once a sequence value is consumed, it's purged from the sequence stack, never to be used again (at least not during the same service "conversation").

For every client/service interaction, you're required to embed two extra pieces of information:

  • A relatively unique client-identifier
  • One of the generated sequence values -- the OTP. Going forward, I'll refer to this value as a passkey.

This looks straightforward enough, but it's not obvious at first blush how this extra information can contribute to the security of a service offering. With the Lamport sequence scheme in mind, here's how a series of service requests might work:

  1. The client initiates a conversation through an introduction, or a request to communicate further. Let's call this the "Hello" interaction. This Hello request is sent along with a client-identifier and the last generated passkey.
    • Upon receiving this introduction, the service reserves the right to refuse to collaborate with the requester. For now, we'll assume the service will accept all greetings.
    • The service saves the client-identifier, relating it to the passkey value provided. (You can visualize the service maintaining this information in a basic map/hashtable entity, where the client-identifier is the key and the passkey is the value.)
  2. Presumably, some number of requests, following Hello, aim to get some real work accomplished. We'll call these interactions service requests. Each service request is packaged to conform to the service interface's defined protocol, but once again, the client-identifier and current passkey values are included.
    • Upon receiving a service request, the service reserves the right to refuse to act on the request for any reason. For now, we'll assume that client authentication is limited to recognizing the client-identifier (that is, is one of the keys in its map) and validating the passkey value. That validation uses the same F(s) function that was used to generate each successive sequence value for the client. So if F(provided passkey) is equal to what has been stored in the client-identifier map, the service request proceeds. If not, the service request is ignored.
  3. At some point, the client ends the service conversation by indicating that it's done for now. We'll call this interaction "Goodbye." As before, the client-identifier and latest passkey values get included in the Goodbye request.
    • Upon receiving Goodbye from the client, the service checks the client-identifier map for a matching key. If it's found, the same authentication process that was applied to a service request is applied: comparing F(provided passkey) to the passkey value associated with this value. The client's identifier entry is purged if authentication passes. Otherwise, the Goodbye request is ignored. (Note: a service-request conversation is effectively over when Goodbye is processed, but a service can manage its client-identifier map as it chooses -- for example, by aging out entries after a period of inactivity.)

In summary, any client that uses the features of an OTP-protected service cycles through a series of Hello, service-request, and Goodbye interactions. Each conversation is prefaced by generating some number of sequence/passkey values to be used as OTPs.

1 2 3 4 5 6 Page
Join the discussion
Be the first to comment on this article. Our Commenting Policies
See more