One Time Identification, a request for comments/testing. g.w at
Wed Jan 31 01:03:09 EST 2007

Good evening, I hope this note finds everyone's day going well.

Its becoming increasingly obvious that the utility of passwords are
becoming problematic.  If users are forced into passwords with
sufficient entropy they write them down.  Products such as PRTK are
making it increasingly difficult to select passwords which can be
easily remembered and yet are secure.

Common solutions to this problem include One Time Password systems and
pre-authentication strategies such as PKINIT.  While effective these
systems each have their own issues ranging from diminished entropy to

For the last several months we have been working on an alternative
strategy for a system which combines two-factor authentication with
strong single use passwords.  The primary focus of this work was to
develop a system which integrated naturally with desktop based
Kerberos authentication and was freely implementable.

The purpose of this note is to introduce the work and get
comments/feedback from the community.

The proposal is referred to as OTI or One Time Identification.  The
system is based on an identity token which can be carried on a
standard USB flash disk.  The identity token is included in an
identification payload which is symmetrically encrypted and included
in the AS_REQ authorization field.  The KDC decrypts and verifies the
identity upon receipt of the AS_REQ.  If the OTI identity matches that
of the principal requesting the service the AS_REP proceeds.

The identity token consists of a DER encoded structure of the
following information:

          1.) 32-bit identity epoch time.
          2.) RSA encrypted 160-bit user identity.

The epoch time is randomly chosen when the user's identity token is
generated.  RSA encryption is done against a private key held by the

When the AS_REQ is composed a DER encoded data structure of the
following elements is created:

          1.) Authentication request time.
          2.) IP address of target KDC server.
          3.) RSA encrypted identity.

A time interval dependent key scheduler is used to derive a symmetric
encryption key using the following information:

           1.) Epoch time of identity.
           2.) Offset of authentication time from identity epoch time.
           3.) SHA256 hash of the RSA encrypted identity.
           4.) User password key.

The key scheduler uses the authentication epoch time differential to
perturb the generation of two separate vectors.  These vectors are
combined and then fed into an N-round iteration of feedback hashing to
generate the final encryption key.

Vector 1 is generated as follows:

       ||    = Concantenation.
       Ukey  = User's authentication key (des3-hmac-sha1 in reference imp).
       Etime = 32-bit identity epoch time.
       Eoffs = Authentication/epoch time offset (network byte order).
       Ihash = SHA256 hash of RSA encrypted identity.
       Nrnd  = Iteration round count.

       V1 = Hmac256(K, Etime)
                    | K = (Ukey || Eoffs)

       The Etime is decomposed into a UNIX time structure with a
       gmtime call.  The day of the month represented by the Etime is
       used as an offset into the V1 vector to obtain an 8-bit round
       count value (Nrnd).

Vector 2 is generated as follows:

       V2 = Hmac256(K, Ukey)
                    | K = (Ihash || Eoffs)

       The first 16 bytes of the V2 vector are retained to serve as
       the IV (Initialization Vector) for AES-256-CBC symmetric
       encryption of the OTI payload.

Iteration rounds:

        A seed vector for the iteration rounds is formed as follows:

                Seed = (V1 || V2)

        The Seed vector (512 bits) is reduced to a 256 bit vector by
        the first SHA256 hashing round.  The 256 bit output vectors
        are then iteratively fed back for Nrnd-1 iterations.

The output of the final round is used as an AES-256-CBC encryption key
with the IV abstracted from the V2 vector.

Upon receipt of the AS_REQ payload the KDC re-creates the key and IV
by running the same key scheduler using the authentication start time
from the AS_REQ.  In the prototype implementation the identity epoch
time and the SHA256 hash of the RSA encrypted identity token are
stored in an LDAP directory object indexed by the user's Kerberos
principal.  Appropriate access controls are assumed on the directory

If decryption is successful the payload is ASN decoded.  The
authentication time from the OTI payload is matched to the
authentication start time of the AS_REQ.  The encoded IP address is
verified to match one of the IP addresses the KDC is listening on.

The KDC then uses its private RSA key to decrypt the identity
payload.  The 160-bit intrinsic identity is verified to match the
identity assigned to the principal.  The AS_REP is then issued to the
user if all validation checks pass.

The take away from all this is that the authentication request is
processed if and only if the user can supply an identity token which
is unique in time and valid to the KDC.  The time dependent key
scheduler generates a unique password at one second granularity
intervals given a specific user password and identity token.

>From the user's perspective the interface is identical to a standard
login attempt with the exception that a USB dongle with the identity
token needs to be available to generate the AS_REQ.  No additional
prompts, button pushes, pin numbers, certificate slot selection, PKI
infra-structure etc. are needed.

Since timing is based on a quantity agreed to by both the client and
KDC (authn start time) there are no issues with clock cadence and or
re-synchronization windows.  Standard KDC clock skew issues are still
present but that is a well understood issue.

As I noted earlier this system was designed specifically to meet the
needs of Kerberos based authentication.  Beyond user convenience a
primary concern was avoidance of replay attacks.

Adding the authentication time and the IP address of the target KDC
server in the encryped OTI payload locks the request to a specific KDC
for a specific instant in time.  No coordination is required between
master and slave KDC's.

At the level of an individual KDC a potential reply attack is now
slaved to the clock skew window of the KDC.  A natural benefit of OTI
is that each authentication attempt now has a unique footprint, the
checksum of the encrypted payload.

In order to avoid reply attacks within the clock skew window the KDC
caches the hash of the encrypted payload along with the authentication
request time indexed by principal name upon issuance of an AS_REP.
The cache entries only need to be maintained until the authentication
time associated with the payload expires from the clock skew window.

Finally it goes without saying that failure throttling needs to be
integrated into the KDC for full security.

So, in a nutshell... :-), thats the strategy.

As I noted at the start we have a working implementation of all this.
A primary concern, of course, is on the strength and randomness of the
time unique OTI encryption keys.

I put together a tarball which will generate two utilities which
people can use to play around with this a bit.  The following URL will
pull the tarball:

Typing make should suffice to build it on most Linux systems.  The
only thing which may need some tweaking are the locations for Kerberos
and OpenSSL which are configurable at the top of the Makefile.

Compiling will produce the following two binaries:



The tarball also contains a sample identity token.  Running genOTI
will cause several questions to be asked.  These are basically to
supply information which the AS_REQ would normally have.  The utility
will then read the token and begin printing encryption keys and their
corresponding times.

The genOTI utility also supports a -o switch.  This will cause
encrypted payloads to be generated and written to files tagged by
authentication time.  The decryptOTI utility will ask for several
pieces of information and then attempt to decrypt the designated
payload file.

The OTI-test tarball contains two pre-compiled .a files of all the
library code for simplicity purposes.  If anyone wants to validate
that the test utilities are not going to do anything evil full sources
can be pulled from:

Please feel free to forward any comments or questions you may have on
all this.  Everything is GPL/OpenSSL exception.

Apologies for the length of the introduction.  I would be happy to
entertain more in depth discussion in private e-mail if anyone is
interested in all this.

Best wishes for a pleasand and productive remainder of the week.

As always,
Greg Wettstein

                         The Hurderos Project
         Open Identity, Service and Authorization Management

"My thoughts on trusting Open-Source?  A quote I once saw said it
 best: 'Remember, Amateurs built the ark.  Professionals built the
 Titanic.'  Perhaps most significantly the ark was one guy, there were
 no doubt committees involved with the Titanic project."
                                -- Dr. G.W. Wettstein

More information about the krbdev mailing list