This proposal is a work-in-progress and will likely change.

If you have comments and/or suggestions on what you see here, please submit them in the comments section below.

Introduction

There is a potential Denial of Service attack on the Perfect Paper Passwords authentication method. With a relatively small number of passcodes pre-printed, a persistent attacker could attempt multiple authentications causing your system to advance beyond your printed passcodes effectively locking you out.

One possible solution to this problem is to expire passcodes based on the current time rather than based on each authentication attempt. This would require a device (such as a cellphone) to calculate the current passcode rather than using a passcard.

Proposed Algorithm

Definitions

• "Server" is the machine you want to authenticate to.
• "Key" is a 256-bit private symmetric encryption key generated by the Server.
• "Key Calculator" is a device that shares the Key with the Server and can calculate passcodes. (e.g. Cellphone).

Description

• The Server generates a private Key.
• The Key is copied from the Server to the Key Calculator through some external secure channel such as copy/paste or typing by the user.
• The current passcode is calculated identical to PPP with the exception that passcode numbers are advanced based on the current time as follows:
1. Obtain the current time as the number of seconds since 1 Jan 1970 00:00:00 UTC (ignoring leap seconds). Store in a 128-bit number.
2. Shift the current time right by 5 bits (or perform integer division by 32).
3. The result is the passcode number. Passcode number will change every 32 seconds.
4. From the passcode number, the Time Code (N) is calculated the same as in PPP. With each value of N giving 5.33 consecutive passcodes. Time Code (N) will change roughly every 3 minutes.

Areas of Further Investigation

• Time Synchronization - The Server and Key Calculator must be synchronized in time relatively tightly for the authentication to work. Some method of tracking the time skew between the two and compensating for it can be used. N.B. Be careful of patent infringements here.

• The plot above shows a simplistic test to see how much skew we might expect between devices.
• The data represents difference between a client and server clock at various points throughout the day.
• Unfortunately, a poor server was chosen for this test. It's clock is slow by about 10 minutes! And, you can see from the slope of all the hosts that the server is continuing to lose time.
• Interestingly, host1 is an iPhone. I suspect the 20-30s swings are delays in enabling the networking to send the time to the server. I implemented a fix for this. We'll see if this improves the data.
• Host5 is a windows machine running cygwin.
• I'll continue to collect more long-term drift data.

Potential Pitfalls

• Patent Infringement - A quick search turned up these RSA SecurID Patents: 4,720,860, 4,885,778, 4,856,062. I have not reviewed them yet, however.