Forward secure one-time authentication tokens with embedded time hints

A non-transitory machine-readable recordable storage medium for generating a user authentication passcode for presentation to an authentication server, wherein one or more software programs when executed by one or more processing devices implement the following steps:

• determining a current state of said token;
• generating, using said token, a user authentication passcode based on said current state, wherein said generated user authentication passcode comprises an embedded time hint not previously known to said authentication server, wherein said embedded time hint is embedded in said generated user authentication passcode when said generated user authentication passcode is generated;
• and
• communicating said generated user authentication passcode to said authentication server, wherein said authentication server obtains said embedded time hint from said generated user authentication passcode and determines a time interval to search for another user authentication passcode based on said embedded time hint, wherein said communicating step employs one or more of (i) a verification-independent auxiliary channel that employs a plurality of auxiliary bits comprising at least one auxiliary bit indicating that said embedded time hint is activated, and (ii) a verification-dependent auxiliary channel that employs a plurality of auxiliary bits comprising at least one auxiliary bit indicating that said embedded time hint is activated and at least two independent forward-secure pseudorandom generators.

A token apparatus for generating a user authentication passcode for presentation to an authentication server, the apparatus comprising:

• a memory;
• and
• at least one hardware device, coupled to the memory, operative to implement the following steps:
• determine a current state of said token;
• generate, using said token apparatus, a user authentication passcode based on said current state, wherein said generated user authentication passcode comprises an embedded time hint not previously known to said authentication server, wherein said embedded time hint is embedded in said generated user authentication passcode when said generated user authentication passcode is generated;
• and
• communicate said generated user authentication passcode to said authentication server, wherein said authentication server obtains said embedded time hint from said generated user authentication passcode and determines a time interval to search for another user authentication passcode based on said embedded time hint, wherein said communication employs one or more of (i) a verification-independent auxiliary channel that employs a plurality of auxiliary bits comprising at least one auxiliary bit indicating that said embedded time hint is activated, and (ii) a verification-dependent auxiliary channel that employs a plurality of auxiliary bits comprising at least one auxiliary bit indicating that said embedded time hint is activated and at least two independent forward-secure pseudorandom generators.

A server-side method for processing a user authentication passcode, comprising:

• receiving a user authentication passcode, generated using a token, wherein said received user authentication passcode comprises an embedded time hint not previously known to said authentication server, wherein said embedded time hint is embedded in said generated user authentication passcode when said generated user authentication passcode is generated, wherein said receiving step employs one or more of (i) a verification-independent auxiliary channel that employs a plurality of auxiliary bits comprising at least one auxiliary bit indicating that said embedded time hint is activated, and (ii) a verification-dependent auxiliary channel that employs a plurality of auxiliary bits comprising at least one auxiliary bit indicating that said embedded time hint is activated and at least two independent forward-secure pseudorandom generators;
• obtaining, by at least one processing device of said server, said embedded time hint from said received user authentication passcode;
• and
• determining, by said at least one processing device of said server, a time interval to search for another user authentication passcode based on said embedded time hint.

A non-transitory machine-readable recordable storage medium for processing a user authentication passcode, wherein one or more software programs when executed by one or more processing devices implement the following steps:

• receiving a user authentication passcode, generated using a token, wherein said received user authentication passcode comprises an embedded time hint not previously known to an authentication server, wherein said embedded time hint is embedded in said generated user authentication passcode when said generated user authentication passcode is generated, wherein said receiving step employs one or more of (i) a verification-independent auxiliary channel that employs a plurality of auxiliary bits comprising at least one auxiliary bit indicating that said embedded time hint is activated, and (ii) a verification-dependent auxiliary channel that employs a plurality of auxiliary bits comprising at least one auxiliary bit indicating that said embedded time hint is activated and at least two independent forward-secure pseudorandom generators;
• obtaining, by at least one processing device of said authentication server, said embedded time hint from said received user authentication passcode;
• and
• determining, by said at least one processing device of said authentication server, a time interval to search for another user authentication passcode based on said embedded time hint.

A server apparatus for processing a user authentication passcode, the apparatus comprising:

• a memory;
• and
• at least one processing device, coupled to the memory, operative to implement the following steps:
• receive a user authentication passcode, generated using a token, wherein said received user authentication passcode comprises an embedded time hint not previously known to said authentication server, wherein said embedded time hint is embedded in said generated user authentication passcode when said generated user authentication passcode is generated, wherein said receiving employs one or more of (i) a verification-independent auxiliary channel that employs a plurality of auxiliary bits comprising at least one auxiliary bit indicating that said embedded time hint is activated, and (ii) a verification-dependent auxiliary channel that employs a plurality of auxiliary bits comprising at least one auxiliary bit indicating that said embedded time hint is activated and at least two independent forward-secure pseudorandom generators;
• obtain, by said at least one processing device of said server apparatus, said embedded time hint from said received user authentication passcode;
• and
• determine, by said at least one processing device of said server apparatus, a time interval to search for another user authentication passcode based on said embedded time hint.