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

A design pattern for securing client/service interactions with OTP

1 2 3 4 5 6 Page 2
Page 2 of 6

Example conversation

Taking this explanation to the next level, let's create a notional conversation between two people, Tom and Jerry, representing a client and a service, respectively. Jerry is a generous guy who grants a lot of favors, but he wants to make sure that he's interacting with one of the few people that he has shared his "secret" sequence algorithm with. Here's how this might work.

Assume Tom and Jerry are sharing an algorithm that was used to generate the following sequence:

18, 21, 24, 27, 40, 44, 47, 50

For the sake of simplicity, we use whole numbers here. Our seed value happens to be 18 (but that's hardly significant). The F(s) sequence function applies the following operations: add 3, and if the result contains the digit 3, then change that digit to a 4.

Here's how that conversation might flow:

Tom: Hello, Jerry - I want to talk to you. "Identifier=Tom", "Passkey=50"

Jerry has no reason to turn Tom away, so he saves a record of Tom's introduction along with the provided passkey value: "Tom"->"50".

Tom: Jerry, will you loan me your car?: "Identifier=Tom", "Passkey=47"

Jerry wants to make sure this is really Tom. He applies the function to "47": F(47) = 50. The sequence function returns "50":F(47) = 50, which matches the passkey value saved in Tom's record. He responds with Yes and replaces Tom's record with "Tom"->"47".

Tom receives the reply and is pleased but realizes that he doesn't know where Jerry's car is. He now requests Where is your car?: "Identifier=Tom", "Passkey=44"

Jerry once again wants to make sure this is really Tom. As before, he applies the function to the provided passkey: F(44) = 47, which matches the sequence value saved in Tom's record. Jerry responds with the information Tom has requested -- The corner of Metro and Goldwyn -- and replaces the Tom record with "Tom"->"44".

Tom receives the information he needs, and then says, Thanks, Jerry! Goodbye: "Identifier=Tom", "Passkey=40"

Jerry realizes that Tom is done with this conversation. One last time he applies the shared sequence function to the provided passkey F(40) = 44. The record maintained for Tom is now purged.

I've limited the sequence examples so far to whole-number values generated by fairly simple algorithms that yield patterns that might well be recognized for what they are. The most secure sequence algorithm is one whose predecessor values (a predecessor value is a value generated just prior to a given sequence value S) can't be calculated easily even if an intruder client knows what the sequence function is. For example, suppose we use a one-way hash function to calculate the sequence set. If an intruder observes a sequence value S and suspects that a hash function is being used to generate each sequence value, it's still virtually impossible for the intruder to masquerade as an active client by calculating the predecessor value. (That said, even when a more detectable algorithm is used, the window of opportunity for an intruder is only as long as the client/service conversation between the Hello and Goodbye requests.)

Proof of concept: Design

The Lamport OTP approach is fairly easy to implement, especially in a language such as Java.

The earlier conversation between Tom and Jerry had a major flaw from a good-class-level-design perspective -- mainly, that the Tom and Jerry entities knew too much. Collectively, they were responsible for all the work related to generating, maintaining, and using sequence/passkey values, and authenticating requests against client-identifier records.

In the interest in building a more maintainable and extensible solution, areas of responsibility need to be clearly defined and distributed across components, leaving Tom (the client) and Jerry (the service) to deal with little more than submitting service requests and servicing them. So it would probably be a good idea to have dedicated components dealing with the particulars of OTP sequences in a way that allows new sequence algorithms to be easily incorporated and selected at runtime. Also, when Tom introduced himself to Jerry, Jerry accepted his identity at face value. Maybe that's good enough for most collaborating peers, but the ability to easily incorporate a more rigorous identity validation would also be useful.

With these ideas driving a design, the optimal OTP reference implementation might allow us to:

  • Minimize impact on existing client/service components -- that is, not require us to modify the implementation of existing services and their clients.
  • Build an OTP framework with a healthy separation between the main areas of responsibility:
    • Sequence passkey generation and maintenance
    • Sequence passkey consumption
    • Client-identifier validation
    • Sequence passkey validation
  • Allow the following extensions:
    • Integrate new sequence-algorithm implementations.
    • Vary the algorithm used dynamically at runtime based on service type, or on demand, or based on any other criteria.
    • Adopt stricter and varying rules of client-request validation beyond OTP validation.

The next section present the major details of a reference OTP implementation that achieves these design goals.

1 2 3 4 5 6 Page 2
Page 2 of 6