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

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(<i>provided passkey</i>) 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(<i>provided passkey</i>) 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.

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.

Reference implementation

The reference implementation offers a simple example of how an OTP framework can be applied to an existing client/service collaboration with minimal coding, and extended to use alternate sequence algorithms and stricter client-identifier validation. You can download the RI source code anytime.

Life without OTP

Before securing a client/service pair with an OTP scheme, interactions might flow fairly simply: the client obtains a handle to a known service and issues requests. Our sample service here provides four end points (which are of limited use but adequate for demonstration purposes):

• echo returns the set of parameters provided by the client back to the client.
• replace writes data into a specified file resource. It creates the file if it doesn’t already exist and replaces the file if it does.
• append appends data into a specified file resource. It creates the file if it doesn’t already exist and appends to the file if it does.
• get obtains the contents of a specified file resource.

The client sends a sequence of clearly defined requests to a service. The requests pass or fail on the merits of completing the related work, and a response is returned, as illustrated in Figure 1.

The class model shown in Figure 2 implements the service flow shown in Figure 1.

In Figure 2’s class model:

• TestDriver simulates the action of the service client. It creates usable instances of SampleClient and SampleService and triggers a workflow on the SampleClient.
• SampleClient is an example service-client component that issues a series of requests to an instance of SampleService (which is not secured through an OTP scheme).
• SampleService is a simply modeled notional service that provides trivial echo, file-manipulation, and file-retrieval service end points.
• ServiceException extends the base Java Exception, providing a single wrapper for all lower-level exceptions and meaningful exception codes and messages.

The core of the SampleClient is implemented in Listing 1.

Listing 1. SampleClient’s core implementation

public void doSomeWork(SampleService someService) {
  try {
   setup(someService);
   sendRequests(someService);
   cleanup(someService);
  }
  catch(ServiceException ex) {
   SimpleLogger.error(getClass().getName() + ": " + ex);
  }
 }

 protected void sendRequests(SampleService someService) throws ServiceException {
  String scratch = "";

  scratch = someService.processRequest( "echo", "Hello,", "JavaWorld" );
  SimpleLogger.info("echo: " + scratch);
  someService.processRequest( "replace", "/tmp/JavaWorld", "Added this note on .... " + new Date());
  someService.processRequest( "append", "/tmp/JavaWorld", "Added another note on .... " + new Date());
  scratch = someService.processRequest( "get", "/tmp/JavaWorld");
  SimpleLogger.info(" "get" retrieved the following:n" + scratch);

 }

Launching the TestDriver class produces the output in Listing 2, which includes some process logging and service-resident file content.

Listing 2. Testing sample client/service

SampleService echoing: Hello,...
echo: Hello, JavaWorld

 SampleService replacing: /tmp/JavaWorld
 SampleService appending: /tmp/JavaWorld
 SampleService getting: /tmp/JavaWorld
 "get" retrieved the following:

 Added this note on .... Sun Feb 22 11:05:07 EST 2009
 Added another note on .... Sun Feb 22 11:05:07 EST 2009

Listing 3 shows the main SampleService code.

Listing 3. SampleService

package com.opensolutionspace.appl;

import java.io.*;
import com.opensolutionspace.common.*;
import com.opensolutionspace.otp.lib.OtpService;

/**
* 02/01/2009 - Simply modeled notional service ...
* provides trivial "echo", and file creation and retrieval service points
* @author lji
*
*/
public class SampleService {

 protected String serviceName;

 public SampleService() {
  init();
 }

 protected void init() {
  serviceName = Utility.shortClassName(this);
 }


 public String processRequest(String request, String... args )
     throws ServiceException {

  String rs = "";
  try {
   if("get".equalsIgnoreCase(request) ) {
    rs = get(args);
   }
   else if("append".equalsIgnoreCase(request) ) {
    append(args);
   }
   else if("replace".equalsIgnoreCase(request) ) {
    replace(args);
   }
   else if("echo".equalsIgnoreCase(request) ) {
    rs = echo(args);
   }
   else {
    throw new ServiceException(ServiceException.Code.INVALID_SERVICE);
   }
  }
  catch(Exception ex) {
   throw new ServiceException(ServiceException.Code.PLATFORM_EXCEPTION, ex);
  }

  return rs;
 }

 /////////////////////////////////////////////////
 // Specific service point Implementation methods
 // echo(), get(), put(), replace()
 /**
 * echo back the provided args ...
 * @param args
 * @return
 */
 protected String echo(String...args) {
  SimpleLogger.info(" " + serviceName + " echoing: " + args[0].toString() + "..." );
  StringBuffer buffer = new StringBuffer(args.length * 25);

  for(String arg : args) {
   if(buffer.length() > 0 )
    buffer.append(" ");
   buffer.append(arg);
  }
  buffer.append("n");
  return buffer.toString();
 }

 /**
 * return the contents of a given file
 * @param args
 * @return
 */
 protected String get(String...args)throws Exception {
  SimpleLogger.info(" " + serviceName + " getting: " + args[0].toString() );
  String file = args[0];
  return Utility.fileContents(file);
 }

 /**
 * create, or append to the file if it already exists.
 * @param args
 * @throws Exception
 */
 protected void append(String...args) throws Exception {
  put(true, args);
 }

 /**
 * create, or append to the file if it already exists.
 * @param args
 * @throws Exception
 */
 protected void replace(String...args) throws Exception {
  put(false, args);
 }

 /**
 * Write content to a file
 * @param fileFlag
 * @param args
 * @throws Exception
 */
 private void put(boolean fileFlag, String...args) throws Exception {
  String operation = "appending";
  if(fileFlag == false )
   operation = "replacing";
  SimpleLogger.info(" " + serviceName + " " + operation + ": " + args[0].toString() );
  String file = args[0];
  String log = args[1];
  Utility.writeToFile(file, log, fileFlag);

 }

 public String getServiceName() {
  return serviceName;
 }

}

Applying OTP

Applying a OTP scheme to the SampleClient/SampleService pair makes the process diagram in Figure 3 more interesting but not much more complicated.

The five class-level entities in Figure 3 are:

• SecureSampleClient: A client component that extends the implementation of SampleClient. Its activities include:
  • Obtaining a PassKeySequencer instance
  • Asking the sequencer instance for a set or specific number of passkey values
  • Negotiating with an OTP protected service:
    • Introduction, invoking the hello() service method
    • Some series of service requests, invoking the requestService() service method
    • Indicating the end of the conversation, invoking the goodbye() service method

• OtpService: An interface that defines a set of operations to be implemented by OTP secured services.
• PassKeySequencerFactory: A class that encapsulates the details of constructing an implementation of PassKeySequencer. Clients of PassKeySequencer need not concern themselves with selecting a specific sequence algorithm and the details of creation/initialization.
• PassKeySequencer: An interface that defines functionality of all implementing OTP Sequencer classes. Implementors of PassKeySequencer encapsulate a specific sequence algorithm. Operations include:
  • Providing “next” sequence value. (Recall that the sequence of values is used as a classic stack collection from last to first values.)
  • Encoding a given value with the same algorithm that was used to create each sequence value’s successor
  • Generating or regenerating a new sequence of values
• OtpAuthority: An interface that defines a client request’s authentication behavior. Implementations of OtpAuthority are expected to be used directly by implementations of OtpService. Their responsibility can include passkey and client-identifier validation as well as service-request context checking, but a minimum level of validation beyond the described OTP check is not defined.

These class-level entities perform the following sequence of actions:

1. The SecureSampleClient class asks the PassKeySequencerFactory for a PassKeySequencer instance.
2. The PassKeySequencerFactory has a notion of which PassKeySequencer implementation to create and return.
3. The SecureSampleClient asks the PassKeySequencer to generate N number of sequence values (or a default number of values), which are consumed with each service interaction.
4. The OtpService receives a request from a client. Before agreeing to process a client request, the OtpService asks the OtpAuthority to validate.
5. The OtpAuthority receives the requesting client-identifier, a passkey value, and the service name/type. It can fail the authentication request for any reason, but it is expected to validate the passkey value according to Lamport OTP rules.
6. If a PassKeySequencer instance is not already created, the OtpAuthority asks the PassKeySequencerFactory for one.
7. The PassKeySequencer instance is asked to validate the passkey value.

As with the original client/service, request responses and potentially thrown exceptions flow their way back to the initiating client.

Static structures

The supporting classes and interfaces shown in Figure 4 meet our general design goals.

The classes and interfaces in Figure 4 reuse our original client/service implementations through inheritance. Sequence-value generation and validation is not only decoupled from the client and OtpService implementations, but we also made it trivial to leverage multiple sequence algorithms. The authentication of the client-identifier and passkey value is also decoupled into a separate OtpAuthority component. Finally, a “factory” component — PassKeySequenceFactory — ensures that cooperating client/service components use the same OTP sequence algorithm.

The classes and interfaces in Figure 4 that I haven’t already described are:

• SecureSampleService: A class that extends the SampleService. It uses an instance of SimpleOtpAuthority to meet its OtpService interface obligations (following the common Adapter pattern).
• SecureServiceException: A class extending ServiceException. It defines error codes and conditions specific to an OTP-protected service interaction.
• BaseOtpAuthority: An abstract class that is a convenient start for extending classes that implement the OtpAuthority interface. It provides data structures and default key-management and authentication methods. Concrete classes that implement the OtpAuthority would be well served by extending BaseOtpAuthority and modifying or extending behavior as needed.
• SimpleOtpAuthority : A class representing the only concrete implementation of OtpAuthority, fulfilling most of its obligations by extending the BaseOtpAuthority class.
• BaseSequencer: An abstract class that is a convenient start for extending classes that implement the PassKeySequencer interface. It provides data structures and sequence-value-generation and maintenance logic that would apply to most PassKeySequencer implementations. Concrete classes that implement PassKeySequencer would be well served by extending this base class and modifying or extending behavior as needed.
• HashSequencer: This is the only concrete implementation of PassKeySequencerin the base library (*.otp.lib) package. Others can be found in the *.otp.poc package. The sequence algorithm here is based on starting with a reasonably unique seed value and making each successor value the MD5-hash value of its predecessor.
• SimpleSequencer: This implementation of PassKeySequencer produces a sequence of numbers that starts with 18 and follows this logic: add 3; if the resulting numbers contain a 3, replace it with a 4. (Recall that this was the algorithm used by Tom and Jerry’s notional conversation.)
• FiboSequencer: This sequencer produces a sequence of numbers that starts with 1 and generates a series of values that follows the well-known Fibonacci sequence (1, 1, 2, 3, 5, 8, 13 ...).

Listing 4 shows the significant coding details of the SecureSampleService class, which implements OtpService and extends the original service class, SampleService.

Listing 4. SecureSampleService

package com.opensolutionspace.otp.appl;

import com.opensolutionspace.appl.SampleService;
import com.opensolutionspace.common.*;
import com.opensolutionspace.otp.lib.*;
import com.opensolutionspace.otp.poc.*;

/**
 * 02/03/2009 - extends the SampleService as is.
 * Uses an instance of SimpleOtpAuthority to meet its OtpService
 * obligations ...
 * @author lji
 */
public class SecureSampleService extends SampleService implements OtpService {

    public SecureSampleService() {

    }

    SimpleOtpAuthority otpAuthority = new SimpleOtpAuthority();


    public void hello(String id, String first ) throws SecureServiceException {
      otpAuthority.hello(id, first);
    }


    public String requestService(
      String id, String password, String request, String... args )
      throws SecureServiceException {

      if(otpAuthority.authorizeRequest(id, password, request, args) != OtpService.OK) {
        throw new SecureServiceException(
          SecureServiceException.Code.AUTHORIZATION_EXCEPTION);
      }

      String rs = "";
      try {
        rs = processRequest(request, args);
      }
      catch(ServiceException se) {
        SimpleLogger.error("CATCH CLAUSE failed");
        throw new SecureServiceException(
            SecureServiceException.Code.SERVICE_EXCEPTION, se);
      }

      return rs;
    }


    public void goodbye(String id, String password ) throws SecureServiceException {
      otpAuthority.goodbye(id, password);
    }


}

Notice that SecureSampleService, as I stated previously, does little on its own beyond marshaling the service-request attributes submitted by the requesting client. An instance of OtpAuthority is used to fulfill the behavior defined by OtpService. The basic service operations are supported by the SampleService superclass.

The implementation of HashSequencer and its base class — BaseSequencer — is worth reviewing, because it’s where the core of the Lamport algorithm is implemented. Listing 5 shows the code for these classes.

Listing 5. HashSequencer and BaseSequencer

package com.opensolutionspace.otp.lib;

import java.util.*;
import java.security.*;
import java.io.UnsupportedEncodingException;
import java.math.*;


/**
* The is the only concrete implementor of PassKeySequencer
* in the com.opensolutionspace.otp.lib package.
* Others can be found in the com.opensolutionspace.otp.poc package.
* Sequence is based on starting with a reasonably unique seed
* value and making each successor value the MD5-hash value of its
* predecessor ...
*
* @author lji
* 02/07/2009
*/
public class HashSequencer extends BaseSequencer implements PassKeySequencer {


 protected String genSeed() {
  return this.getClass().getName() + new Date().getTime();
 }

 public String encode(String value) {
   String rval = "";
   try {
     rval = genMD5(value);
   }
   catch (NoSuchAlgorithmException ex) {
     System.err.println("encode():" + ex);
     return rval;
   }
   catch (UnsupportedEncodingException ex) {
     System.err.println("encode():" + ex);
     return rval;
   }
   return rval;
 }


 protected String genMD5(String value)
    throws NoSuchAlgorithmException, UnsupportedEncodingException {

    MessageDigest md = MessageDigest.getInstance("MD5");
    md.update(value.getBytes(), 0, value.length());
    return "" + new BigInteger(1, md.digest()).toString(16);
 }

 /*
 NOTE: BaseSequence provides
 implementation of nextValue() & genValues(...) methods
 */


}


/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

package com.opensolutionspace.otp.lib;

import java.util.*;


/**
* 02/02/2009
* Convenience base Sequencer Class - carries data structures and
* sequence value generation and maintenance logic that apply to all/most PassKeySequencer implementors.
* Concrete classes that implement PassKeySequencer would be well served
* by extending this base class and modifying/extending behavior as needed.
*
* @author lji
*/
public abstract class BaseSequencer {

 protected int maxValues = PassKeySequencer.DEFUALT_MAX_VALUES;
 protected Stack<String> passwordLifo;


 protected abstract String genSeed();
 public abstract String encode (String value);


 protected String nextValue(String value) {
   return encode(value);
 }


 public BaseSequencer() {
   passwordLifo = new Stack<String>();
 }

 public BaseSequencer(int n) {
   maxValues = n;
   passwordLifo = new Stack<String>();
 }


 public String nextValue() {
   return passwordLifo.pop();
 }

 public void genValues(int n) {
   passwordLifo.removeAllElements();
   String value = genSeed();
   for (int i=0; i < n ; i++) {
     value = nextValue(value);
     passwordLifo.add(value);
   }
 }

 public void genValues() {
   genValues(maxValues);
 }


}

The SimpleSequencer class, shown in Listing 6, represents an alternative sequence algorithm.

Listing 6. SimpleSequencer

package com.opensolutionspace.otp.poc;

import java.util.*;

import com.opensolutionspace.otp.lib.BaseSequencer;
import com.opensolutionspace.otp.lib.PassKeySequencer;

/**
 * 02/10/2009
 *
 * This sequencer produces a sequence of numbers that starts with
 * "18" and goes onto generate a series of numbers that follows
 * this logic - add 3 - if the resulting numbers contain a 3,
 * replace it with a 4.
 * @author lji
 */
public class SimpleSequencer
    extends BaseSequencer implements PassKeySequencer {


    public String encode(String value) {

        /**
        * Change to add 3, if result contains "3"
        * change that digit to "4" ...
        */
        int ival = this.seqToInt(value);
        ival = ival += 3;
        String sval = "" + ival;

        return sval.replaceAll("3", "4");
    }


    protected String genSeed() {
        return "18";
    }


    private int seqToInt(String seq) {
        int ival;

        try {
            ival = Integer.parseInt(seq);
        }
        catch(NumberFormatException ex) {
            ival = 90890707;
        }

        return ival;
    }

}

Notice that the required coding here is limited to two methods: genSeed(), which is an abstract method defined in its superclass, and encode(), a method defined in the PassKeySequencer interface that implements the sequence algorithm.

The initial implementation of the PassKeySequencerFactory has a notion of what the default PassKeySequencer implementation (that is, the shared sequence algorithm) is, but it can also be directed to create a specific implementation based on a fully qualified class name.

Leveraging a common factory pattern design leaves all other components oblivious to the details of determining the why, what, and how of the sequence-algorithm selection. Listing 7 shows a PassKeySequencerFactory class that provides a PassKeySequencer based on the following precedence order:

1. The implementation requested by the client
2. The implementation set in the environment (property bundle)
3. The default implementation in the code (HashSequencer)

Listing 7. Constructing a PassKeySequencer implementor

package com.opensolutionspace.otp.lib;

import java.lang.*;
import java.util.*;
import com.opensolutionspace.common.*;

/**
 * Provides ease of constructing an implementor of PassKeySequencer ...
 * Clients of PassKeySequencer's need not concern themselves with
 *  selecting a specific sequence algorithm (i.e., implementation),
 *  the details of creation/initialization and the finite set of implementors.
 *
 * @author lji
 *  02/02/2009
 */
public class PassKeySequencerFactory {

    /**
     * Create and return a Sequence instance based on the "classpath" value ...
     */
    static public PassKeySequencer createSequence(String classPath) {

        // Use Hash if what user asks for is NA
        PassKeySequencer passKeySequence = new HashSequencer();

        //
        try{
            Class theClass = Class.forName( classPath );
            passKeySequence = (PassKeySequencer)theClass.newInstance();
            //SimpleLogger.info( "PassKeySequenceFactory: successfully created: " + passKeySequence.getClass().getName() );
        }
        catch( InstantiationException e ){
                SimpleLogger.error( "PassKeySequenceFactory:" + e );
        }
        catch( IllegalAccessException e ){
                SimpleLogger.error( "PassKeySequenceFactory:" + e );
        }
        catch( ClassCastException e ){
                SimpleLogger.error( "PassKeySequenceFactory:" + e );
        }
        catch( ClassNotFoundException e ){
                SimpleLogger.error( "PassKeySequenceFactory:" + e );
        }


        if( passKeySequence == null ) {
            passKeySequence = new HashSequencer();
            SimpleLogger.error(  "PassKeySequenceFactory: Seq Class Was Not Instantiated - Still null" );
        }


        return passKeySequence;
    }

    /**
     * Returns the "default/current" Sequence Type
     */
    static public PassKeySequencer createSequence() {

        String seqType;
        ObjectAttributes attributes;
        attributes = ObjectAttributes.createObjectAttributes("PassKeySequencerFactory");
        attributes.loadAttributes();
        seqType = attributes.getString("sequenceType");
        //System.out.println("client attributes: " + attributes.toString());
        if(seqType == null) {
            seqType = PassKeySequencer.DEFAULT_SEQUENCE_TYPE;
        }

        return createSequence(seqType);
    }


}

The implementation of SimpleOtpAuthority and its base class — BaseOtpAuthority — is also worth reviewing. This is where all client requests are validated, providing OtpService instances with a single point for all validation, including passkey validation. Instances of PassKeySequencer are not directly used by OtpService implementations. Listing 8 shows the implementation of the two classes.

Listing 8. SimpleOtpAuthority and BaseOtpAuthority

package com.opensolutionspace.otp.poc;

import java.util.*;
import com.opensolutionspace.otp.lib.*;



/**
 *
 * 02/01/2009
 * Used by the SecureService class
 * It's only validation check on the clientId: it cannot be empty
 * @author lji
 */
public class SimpleOtpAuthority extends BaseOtpAuthority implements OtpAuthority {

    public SimpleOtpAuthority() { }

    /**
    * Defined as abstract in BaseOtpAuthority
    */
    protected boolean validRequester(String id) {
      if(id == null || id.length() == 0)
          return false;
        return true;
    }

}


///////////////////////////////////////////////////////////////////////////////////////////////////

package com.opensolutionspace.otp.lib;

import java.util.Hashtable;
import java.util.Map;

import com.opensolutionspace.common.SimpleLogger;

/**
 * 02/03/2009
 *
 * Convenience base OTP Service Class - carries data structures and
 * default key management and authentication methods.
 * Concrete classes that implement the OtpService would be well served
 * by extending this and modifying/extending behavior as needed.
 * @author lji
 *
 */
public abstract class BaseOtpAuthority {

    private Map<String,String> requesterMap;
    private PassKeySequencer passKeySequence;


    public BaseOtpAuthority() {
      init();
    }


    protected void init() {
      requesterMap = new Hashtable<String,String>(83);
      passKeySequence = PassKeySequencerFactory.createSequence();
      return;
    }


    // required to be implemented by derived classes
    protected abstract boolean validRequester(String id) ;


    protected void update(String id, String password) {
      requesterMap.put(id, password);
    }


    protected void purgeId(String id) {
      requesterMap.remove(id);
    }


    protected boolean knownClient(String id) {
      if( requesterMap.containsKey(id) == false) {
        return false;
      }
      return true;
    }

    protected boolean authenticate(String id, String password) {
      /**
      * Reject empty s!
      */
      if( password == null || password.length() == 0 )
        return false;

      // perform operation on to obtain what should be stored
      // on behalf of this client ...
      String real = passKeySequence.encode(password);
      // stored value ...
      String found = requesterMap.get(id);

      if(real.equals(found) == true ) {
        update(id, password) ;
        return true;
      }

      return false;
    }


    ////////////////////////////////////////////////////
    ///// Public methods
    /**
    * 1st interaction between client and server "conversation"
    */
    public void hello(String id, String info ) throws SecureServiceException {

      if(this.validRequester(id) == true)
        update(id, info);
      else
        throw new SecureServiceException(
            SecureServiceException.Code.AUTHORIZATION_EXCEPTION);

    }


    /**
    * 2 opportunities for failure - 'unknown/untrusted client', or bad password ...
    */
    public int authorizeRequest(
       String id, String info, String request, String... args ) {

       // Are we satisfied with the way the client is identifying himself?
       if( knownClient(id) == false) {
         SimpleLogger.error("Unknown Client - NOT Allowing " + request + " on behalf of " + id + "n");
         return OtpService.UNKNOWN_CLIENT;
       }

      // Is the passkey valid?
      if( authenticate(id, info ) == false) {
         SimpleLogger.error(" PassKey Rejected - NOT Allowing " + request + " on behalf of " + id + "n");
         return OtpService.INVALID_PASSWORD;
      }

      // Ok, go ahead and allow service
      SimpleLogger.info("Allowing " + request + " on behalf of " + id );
      return OtpService.OK;
    }


    public void goodbye(String id, String info ) throws SecureServiceException {

      // validate the request to end this client conversation
      // Is the password valid
      if( authenticate(id, info ) == false) {
        SimpleLogger.error("PassKey Rejected - NOT terminating conversation on behalf of " + id + "n");

        throw new SecureServiceException(
        SecureServiceException.Code.AUTHORIZATION_EXCEPTION);

      }

      // Don't even bother checking if 'id' already exists - just purge
      purgeId(id);
      SimpleLogger.info("Terminating conversation on behalf of " + id + "n");

    }


}

A note about packaging

The interfaces and classes in the reference implementation are partitioned across five packages. Here’s a brief synopsis of what each package contains, with the packages listed in roughly least-to-most dependent order:

• *.otp.test contains The test driver class: TestDriver
• *.appl contains the original client/service classes: SecureSampleClient and SecureSampleService
• *.common contains several generally useful “utility classes” that are not specific to any particular application: ObjectAttributes, SimpleLogger, ServiceException,, and Utility.
• *.otp.lib contains core interfaces and base-class implementations specific to OTP generation, maintenance, and validation: BaseOtpAuthority, PassKeySequencer, BaseSequencer, PassKeySequencerFactory, HashSequencer, SecureServiceException, OtpAuthority, and OtpService
• *.otp.poc contains proof-of-concept implementations or class stubs that extend base classes in *.otp.lib: FiboSequencer, SimpleOtpAuthority, StringSequencer, FicaOtpAuthority, and SimpleSequencer. Note: If a developer wanted to utilize this reference implementation, the contents of common, otp.lib, and otp.poc would be provided in one or more JARs.
• *.otp.appl contains the client/service classes that rely on OTP — extensions of the*.appl components SecureSampleClient and SecureSampleService.

Figure 5 shows the package interdependencies.

In conclusion

Leveraging tried and tested algorithms often proves to be the main ingredient in a software solution recipe. Incorporating single-usage, or one-time, passwords into requests passed between cooperating entities is not a novel idea, but it is a practical one. Lamport’s approach focuses on synchronizing client/service entities through a common sequencing algorithm used both to generate and to validate passkey values sent along with every interaction. It might not be the only security precaution you take, but it’s worth considering between distributed applications if you would like to:

• Tighten up casual, clear-text, unauthenticated interactions.
• Simplify needlessly complicated interactions that use certificate-authority and encryption overhead, without completely disregarding security concerns.
• Authenticate client requests without necessarily implementing user-registration and password-assignment use cases. That is, it lets you allow anonymous interactions but ensure that a service conversation is being initiated by a trusted or recognized client.

Next steps

As published, the Lamport algorithm focuses on sequence-value generation and management, within an OTP context. The solution details I’ve offered in this article (relating to client/service interactions) are beyond its scope. The reference implementation shows how you can apply an OTP framework to an existing client/service collaboration with minimal coding, and it can be extended to generate alternate sequence algorithms and stricter client-identifier validation. However, this is a proof-of-concept-level code — a baseline. Here are some suggestions for taking this implementation to the next level:

• Use a more realistic scenario that OTP would generally be applied to, such as a client/service pair that’s distributed across machine or JVM boundaries. A service deployed as an HTTP servlet, or an remote method invocation (RMI) service would be a much more practical example, but wouldn’t be much more of a challenge than extending our original SampleClient and SampleService implementations.
• Demonstrate additional, less trivial PassKeySequencer implementations.
• Demonstrate additional, less trivial OtpAuthority implementations.
• Provide more-detailed error checking and exception handling around the OTP authentication and core service usage.
• Since the client is not obligated to say “goodbye” (not really enforceable in this model) the OtpAuthority implementations should probably “age out” the client-identifier records after a period of idleness and/or fixed period.
• Demonstrate that core library classes can be used in a thread-safe manner.

Acknowledgments

Leslie Lamport is credited with first suggesting that using a one-way function to generate a sequence of values could be useful for securing distributed systems through one-time (expiring) passwords. Most of Lamport’s career has revolved around solution algorithms for distributed computing.

Special acknowledgments are owed to two trusted peers and friends: Jeff Kroll of HP Software and Tim Ihde of DoubleCheck, Inc. — Jeff for noticing the practical usefulness of Lamport’s algorithm and sharing his quick study with me, and Tim for long ago introducing me to the multifaceted world of application security.