# Patent

## Title
Multi-server passcode verification for one-time authentication tokens with auxiliary channel compatibility

## Abstract

Multi-server passcode verification is provided for one-time authentication tokens with auxiliary channel compatibility. An exemplary method comprises receiving an authentication passcode generated by a token associated with a user; and processing the received authentication passcode using at least a first authentication server and a second authentication server, wherein the received authentication passcode is based on at least one protocode and embedded auxiliary information and wherein at least one of the first authentication server, the second authentication server and a relying party extract the embedded auxiliary information from the received authentication passcode. The disclosed method can extend an existing multi-server verification process to provide the processing of the received authentication passcode based on the embedded auxiliary information.

## Background
FIELD
The field relates generally to authentication, and more particularly to multi-server authentication.
BACKGROUND
One-time authentication tokens produce a series of unpredictable one-time passcodes (OTPs) as second authentication factors for the authentication of users to remote servers. One-time authentication tokens implement the general solution concept of second factor authentication, thus offering stronger user authentication. Passcodes are typically generated in an unpredictable manner by extracting pseudorandomness from an initial seed, that is stored at the token and shared with the server. Thus, the security of one-time authentication tokens is based on the secrecy and protection of the token's seed, in particular, against an attacker that directly compromises the server, either ephemerally to get the secret seed or permanently to tamper with the verification process.
Split-server verification employs at least two verification servers, each keeping a distinct secret state, as well as distributed cryptography to implement a joint user-authentication protocol that tolerates certain compromise of one or more servers. See, for example, U.S. Pat. No. 7,725,730. Similar split-server OTP verification protocols have been proposed to make one-time authentication tokens resilient to certain type of server-side attacks. U.S. patent application Ser. No. 13/404,737, filed Feb. 24, 2012, entitled “Method and Apparatus for Authenticating, a User Using Multi-Server One-Time Passcode Verification,” (now U.S. Pat. No. 9,118,661), employs cryptography, and U.S. patent application Ser. No. 13/795,801, filed Mar. 12, 2013, entitled “Distributed Cryptography Using Distinct Value Sets Each Comprising at Least One Obscured Secret Value,” does not support an auxiliary channel (for a discussion of auxiliary channels, see, for example, U.S. patent application Ser. No. 13/404,780, filed Feb. 24, 2012, entitled “Method and Apparatus for Embedding Auxiliary Information in One-Time Passcode Authentication Tokens” (now U.S. Pat. No. 8,984,609)).
A need therefore exists for efficient multi-server OTP verification protocols that are compatible with the existence of an auxiliary channel, while providing high levels of server-side security.
SUMMARY
Illustrative embodiments of the present invention provide multi-server passcode verification for one-time authentication tokens with auxiliary channel compatibility. In one embodiment, a method comprises receiving an authentication passcode generated by a token associated with a user; and processing the received authentication passcode using at least a first authentication server and a second authentication server, wherein the received authentication passcode is based on at least one protocode and embedded auxiliary information and wherein at least one of the first authentication server, the second authentication server and a relying party extract the embedded auxiliary information from the received authentication passcode. The disclosed method can extend an existing multi-server verification process to provide the processing of the received authentication passcode based on the embedded auxiliary information.
The embedded auxiliary information can be embedded into the authentication passcode using a codebook Ct. The codebook Ct can be at least partially transmitted to the second authentication server; or pseudorandom information RA,t can be at least partially transmitted to one or more of the first authentication server, the second authentication server and the relying party and wherein an appropriate binary codeword in a binary codebook B is selected for deriving the embedded auxiliary information and wherein the binary codeword is mapped to a digital codeword for verification.
In one exemplary embodiment, the received authentication passcode is based on at least two protocodes PR,t and PB,t generated by the token and/or pseudorandom information RA,t. The embedded auxiliary information can be embedded into the authentication passcode using a codebook Ct based on the pseudorandom information RA,t. The pseudorandom information RA,t is optionally generated by only one of the first authentication server and the second authentication server. A mapping function maps a given message in a message space to a codeword in a codebook. A given message in the message space is mapped to a binary codeword in a binary codebook and the binary codeword is mapped to a decimal codeword in a decimal codebook using a shared key.
The first authentication server can compute high order auxiliary information and the second authentication server can compute low order auxiliary information. The first authentication server then determines one or more high order matching indices between the high order auxiliary information and a high order portion of a codeword embedded in the received authentication passcode and wherein the second authentication server determines one or more low order matching indices between the low order auxiliary information and a low order portion of a codeword embedded in the received authentication passcode.
Embodiments of the invention can be implemented in a wide variety of different authentication applications, including, for example, verification of one-time passcodes (OTPs).



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 illustrates an exemplary client-side generation of passcodes that are enriched by auxiliary information by a token;
FIG. 2 illustrates an exemplary vertical split-server passcode verification scheme incorporating aspects of the present invention, where each server verifies a high-order portion or a low-order portion, respectively, and optionally extracts a portion of an embedded auxiliary information by processing a corresponding high-order codebook or low-order codebook, respectively;
FIG. 3 illustrates an exemplary split-server passcode verification process incorporating aspects of the invention with reference to the verification scheme of FIG. 2;
FIG. 4 illustrates an exemplary preprocessing portion of the disclosed split-server passcode verification scheme of FIG. 3;
FIG. 5 illustrates an exemplary first phase portion of the disclosed split-server passcode verification scheme of FIG. 3;
FIG. 6A and FIG. 6B illustrate an exemplary second phase portion and a verification phase portion of the disclosed split-server passcode verification scheme of FIG. 3, respectively;
FIG. 7 illustrates an exemplary alternate first phase portion of an alternate implementation of the disclosed split-server passcode verification scheme of FIG. 3;
FIGS. 8A and 8B, collectively, illustrate an exemplary alternate second phase portion of the disclosed split-server passcode verification scheme of FIG. 3;
FIG. 9 illustrates an exemplary alternate verification portion of the disclosed split-server passcode verification scheme of FIG. 3;
FIGS. 10, 11 and 12 illustrates alternative exemplary split-server passcode verification processes incorporating aspects of the invention related to auxiliary channel support;
FIG. 13 illustrates an exemplary processing platform that may be used to implement at least a portion of one or more embodiments of the invention comprising a cloud infrastructure; and
FIG. 14 illustrates another exemplary processing platform that may be used to implement at least a portion of one or more embodiments of the invention.



DETAILED DESCRIPTION
Illustrative embodiments of the present invention will be described herein with reference to exemplary communication systems and associated servers, clients and other processing devices. It is to be appreciated, however, that the invention is not restricted to use with the particular illustrative system and device configurations shown. Accordingly, the term “communication system” as used herein is intended to be broadly construed, so as to encompass, for example, systems in which multiple processing devices communicate with one another but not necessarily in a manner characterized by a client-server model.
As will be described, the present invention in one or more illustrative embodiments provides efficient split-server OTP verification protocols that are compatible with the existence of an auxiliary channel, while providing high levels of server-side security. According to one aspect of the invention, a “vertical-split” verification protocol is provided where different servers are responsible for verifying different portions (substrings) of the submitted passcode. According to another aspect of the invention, a method is provided for extending any general split-server OTP verification protocol without auxiliary-channel support to one that supports an auxiliary channel.
As previously indicated, passcodes are typically generated on a regular time basis, i.e., in specified time intervals often called epochs (e.g., the widely used SecurIDTM token produces a new OTP every minute). Passcodes are derived by using a secret state, called a seed, that is stored at the token and also shared with the server. Tokens can either be based on software or hardware. Software tokens produce passcodes on-demand, whenever the token's application is launched in the host device, where a series of passcodes is generated for the epochs following the launching of the application. Hardware tokens produce passcodes on a permanent basis, one passcode per epoch, for the entire lifetime of their battery (e.g., for five years from the time of manufacture). Overall, such tokens produce a time-based series of unpredictable OTPs by extracting pseudorandom bits from their seed which are converted to passcodes.
There are three main steps in the functionality of one-time authentication tokens.
1. A passcode Pt′ is produced in time epoch t′ through a one-way cryptographic function ƒ applied on the current epoch t′, and the seed σ of the token. Software tokens specify their current epoch based on the current time of the host device, whereas hardware tokens specify their epoch implicitly using a counter.
2. A passcode Pt′ may then be transmitted to an authentication server to authenticate a user to the server. The transmission of the passcode Pt′ to the server may happen either by typing performed by the user or automatically by a software token that is directly communicating to the server through a communication channel offered by the host device.
3. On receiving a candidate passcode Pt′, the server verifies this passcode by contrasting the received passcode against the passcode Pt that is locally computed by the server, accepting the passcode if and only if pt′=Pt. If the passcode is not accepted, the user is not authenticated. Otherwise, the user is authenticated if and only if a user's corresponding PIN is correct. Passcode Pt is computed by the server by applying the same function ƒ on the current epoch t′ specified by the server's current time and the seed σ of the token stored at the server. To tolerate small discrepancies between the current time of the software (or hardware) token and the current time of the server, Pt′ is also contrasted against another 2 s passcodes that are defined by epochs that are neighboring epochs to the server's epoch t, that is, to passcodes {Pt-s, . . . , Pt-1, Pt, Pt+1, . . . , Pt+s}.
Passcodes are produced by applying a one way function ƒ on the token's seed. As long as the seed remains a secret, protected against leakage to an attacker, future passcodes remain unpredictable even if an attacker has observed an arbitrarily long history of passcodes produced in the past.
Protections Against Seed Leakage
The security of any one-time authentication token collapses if an attacker gets access to the secret seed of the token. Using the seed, the attacker can clone the token and thus reconstruct the series of passcodes that the token will ever produce. In turn, the attacker can increase its chances for impersonating the corresponding user, by either performing a brute-force attack on the user's PIN or by launching a more sophisticated man-in-the-middle attack for harvesting the user's PIN. In reality, the fact that the security of the token is based on a secret seed will motivate the attacker to go after this secret seed by following one of the following three attack patterns:
1. Server Compromise: The attacker may compromise the authentication server and get the secret seed of the token of one or more users. The attacker may compromise the server ephemerally by instantly stealing the seed(s) and then terminating the attack, or permanently by remaining in control of the server for a long period of time, thus directly being able to impersonate one or more users.
2. Token Tampering or Compromise: The attacker may compromise the token and get its secret seed either by performing a direct attack against the host device of a software token (using some malware, trojan, or virus installed on the device or through some network-based attack), thus fully bypassing any protection mechanisms being in place by the token application for restricting access to the token's seed, or by physically tampering with a hardware token to directly read its seed, e.g., by opening the case of the token and reading the full internal state of the token at the time of compromise.
3. Seed-Record Capturing: The attacker may get the secret seed of the token indirectly by attacking a storage or communication unit used to store or transfer the token's seed, or through side-channel attacks performed against the token or the server.
Although conventional one-time authentication tokens are vulnerable to all such seed-leakage attacks, a general solution has been recently proposed in U.S. patent application Ser. No. 13/837,259, filed Mar. 15, 2013, entitled “Configurable One-Time Authentication Tokens with Improved Resilience to Attacks,” (now U.S. Pat. No. 9,270,655), that involves the design of a configurable one-time authentication token that is equipped with several intrusion-detection, intrusion-resilience, tamper-resistance and token-visibility technologies that protect against the above attacks. This design employs one or more of the following three protection layers:
High Layer Protection: High layer protection optionally employs one or more of the following intrusion-detection, and instruction-resilience techniques: split-server passcode verification (U.S. patent application Ser. No. 13/404,737, filed Feb. 24, 2012, entitled “Method and Apparatus for Authenticating a User Using Multi-Server One-Time Passcode Verification,” (now U.S. Pat. No. 9,118,661)), silent alarms (U.S. patent application Ser. No. 13/404,788, filed Feb. 24, 2012, entitled “Methods and Apparatus for Silent Alarm Channels Using One-Time Passcode Authentication Tokens”) and drifting keys (U.S. patent application Ser. No. 13/250,225, filed Sep. 30, 2011, entitled “Key Update With Compromise Detection”).
Low Layer Protection: Low layer protection optionally employs one or more of the following tamper-resistance techniques: forward-secure pseudorandom number generators (U.S. patent application Ser. No. 13/334,709, filed Dec. 23, 2011, entitled “Methods and Apparatus for Generating Forward Secure Pseudorandom Numbers” (now U.S. Pat. No. 9,008,303)), use of a source of randomness at the token, and randomized state transitions (U.S. patent application Ser. No. 13/828,588, filed Mar. 14, 2013, entitled “Randomizing State Transitions for One-Time Authentication Tokens”).
Intermediate Layer Protection: Intermediate layer protection optionally employs one or more of the following token-visibility techniques: data-transaction signing (U.S. patent application Ser. No. 13/826,924, filed Mar. 14, 2013, entitled “Event-Based Data-Signing Via Time-Based One-Time Authentication Passcodes,” (now U.S. Pat. No. 9,225,717) incorporated by reference herein), auxiliary channels (U.S. patent application Ser. No. 13/404,780, filed Feb. 24, 2012, entitled “Method and Apparatus for Embedding Auxiliary Information in One-Time Passcode Authentication Tokens”(now U.S. Pat. No. 8,984,609)) and time synchronization (U.S. patent application Ser. No. 13/826,993, filed Mar. 14, 2013, entitled “Time Synchronization Solutions for Forward-Secure One-Time Authentication Tokens,” U.S. patent application Ser. No. 13/728,271, filed Dec. 27, 2012, entitled “Time Synchronisation and Forward Clock Attack” (now U.S. Pat. No. 9,083,515)).
Most of the above techniques are based on the following three security mechanisms.
1. Forward-Secure Pseudorandom Number Generator (FS-PRNG): Forward security can be applied to management of the internal state of one-time authentication tokens. Instead of using a fixed global secret state, e.g., a seed, for the entire lifetime of the token, the secret state can evolve over time in a one-way cryptographic manner so that older states cannot be computed from newer states (e.g., new seeds may be computed using a one-way hash chain). More elaborate hierarchical hashing schemes are possible that improve the server-side performance with respect to management of time-evolving seeds. See, for example, U.S. patent application Ser. No. 13/334,709, filed Dec. 23, 2011, entitled “Methods and Apparatus for Generating Forward Secure Pseudorandom Numbers,” (now U.S. Pat. No. 9,083,515).
2. Split-Server Passcode Verification: Split-server passcode verification is a solution concept for tolerating server compromise(s) in systems that employ one-time authentication tokens. Split-server passcode verification involves employing distributed cryptographic techniques for dispersing the task of verifying a candidate passcode (provided by a user or token) among two or more verification servers so that each such participating server Si stores only a partial secret state σi. Generally, the token's seed σ is split or shared into two or more pieces each managed by a separate server. One security property is that verification is securely implemented in a distributed manner, yet leakage of one or more, but up to a specified threshold, partial secret states does not compromise the security of the token. See, for example, U.S. patent application Ser. No. 13/404,737, filed Feb. 24, 2012, entitled “Method and Apparatus for Authenticating a User Using Multi-Server One-Time Passcode Verification,” (now U.S. Pat. No. 9,118,661).
Typically, the seed is split into two pieces, often called the red and the blue partial seeds, produced respectively by two distinct FS-PRNGs, the red FS-PRNG FSPR and the blue FS-PRNG FSPB. Accordingly, two verification servers are employed: the red server stores the red seed that evolves through FSPR and the blue server stores the blue seed that evolves through FSPB. Upon receiving a candidate passcode Pt′, the two servers interact through a secure protocol to jointly compute the passcode Pt against which the candidate passcode is contrasted, and accordingly Pt′ is rejected if any of the two servers output “reject.” This decision is typically made by a so-called relying server that is stateless and responsible for the final decision about the acceptance of Pt′ based on the individual outputs of the red and the blue servers.
The additional feature of proactivization can be used according to which the partial states of the (e.g., two) servers evolve over time and where the servers periodically exchange secure descriptions (e.g., hashes) of their partial secret states, which are then used to create their new partial secret states.
3. Auxiliary Channel: A small (e.g., 4) number of auxiliary information bits can be embedded into the produced passcodes of a token that, in turn, can be reconstructed by the server, thus implementing a low-bandwidth auxiliary channel between the token and the server. Such channels are designed so that they are resilient to small-digit typographical errors performed by the user transcribing a passcode: An error correction code coming from a randomly selected, secret and passcode-specific codebook Ct is used to encode the auxiliary word that is to be embedded into the passcode, and this embedding corresponds to adding the resulted codeword to the initial passcode using some associative binary operation (e.g., digit-wise addition modulo 10). As specified in U.S. patent application Ser. No. 13/837,259, filed Mar. 15, 2013, entitled “Configurable One-Time Authentication Tokens with Improved Resilience to Attacks,” (now U.S. Pat. No. 9,270,655), in the split-server mode of operation, the codebook Ct evolves over time using pseudorandomness produced by only one of the two employed FS-PRNGs, by convention the blue FS-PRNG FSPB; that is, the auxiliary-channel embedded codeword is associated with the blue FS-PRNG and, thus, produced only by the blue server. See, for example, U.S. patent application Ser. No. 13/404,780, filed Feb. 24, 2012, entitled “Method and Apparatus for Embedding Auxiliary Information in One-Time Passcode Authentication Tokens,” (now U.S. Pat. No. 8,984,609).
Lightweight Split-Server Verification
Unfortunately, previous split-server passcode verification schemes tend to be less practical for wide deployment in realistic high-traffic authentication setting, where possibly hundreds of thousands of users are authenticated through one authentication server. This is because these schemes involve the repeated use of some rather involved cryptographic protocols as well as some relatively high communication costs. In particular, one scheme involves the use of a commitment scheme, namely, it involves a constant number of rounds where each round requires two commitments and two de-commitment operations. Similarly, another (more secure) scheme requires the use of secure multiparty computation, namely, it involves the digit-by-digit secure equality testing.
To increase the practicality of one-time authentication tokens, it is important to consider lightweight versions of split-server passcode verification, e.g., through schemes that are not based on the use of cryptography. Such benefits in performance, however, may come at the possible cost of reduced security.
Recently, such non-cryptographic split-server passcode verification scheme was described in U.S. patent application Ser. No. 13/795,801, filed Mar. 12, 2013, entitled “Distributed Cryptography Using Distinct Value Sets Each Comprising at Least One Obscured Secret Value.” The technique is generally based on the use of chaff sets, according to which, at time epoch t each server stores a fixed-size set of passcodes that contains the correct passcode Pt: the red server stores set Kt,R and the blue server stores set Kt,B so that Pt=Kt,R∩Kt,B, |Kt,B|=|Kt,R|=l. That is, chaff sets provide a natural trade-off between security and performance: A server compromise reveals the chaff set and the attacker has 1/l success probability towards user impersonation, but passcode verification now involves only two independent (and therefore non-interactive) easy-to-perform set-inclusion checks, namely, that P′t∈Kt,B and P′t∈Kt,R. Applying this idea to tokens is slightly more involved, as sets Kt,B and Kt,R cannot be precomputed in advance, but rather must be produced on demand, this time jointly (with interaction) between the red and blue servers. It has been shown that it is possible to have these chaff sets computed implicitly using chaff-set hints sent by each other server.
Specifically, chaff sets are constructed on the fly as follows. For a given time t, the red and blue servers, SR and SB, can compute their respective shares PR,t and PB,t, such that Pt=PR,t+PB,t. Rather than exchanging their shares directly, the red and blue servers, SR and SB, exchange share “hints”—share values that define chaff sets of optimal (maximum) size √{square root over (p)}, where p is the size of the passcode space.
Exemplary Server SR operates as follows. Let ΣR={σR,0, . . . , σR,t-1}, known to both the servers. The set ΣR is a fixed sequence of offsets that serves to construct SR's chaff set Kt,R. The general idea behind construction of Kt,R is for server SB to construct a sequence of values that includes PB,t. This sequence is centered on a random element σR,t in ΣR; other elements of ΣR serve as offsets defining chaff values. By adding PR,t to each element of this set, SR obtains a chaff set Kt,R. Within Kt,R is embedded the full, valid passcode Pt, along with chaff values. In particular:

    
    
        1. Server SB selects an index jt,B∈RZt and sends sR=PB,t−σR,jt,B to server SR.
        2. Server SR constructs chaff set

Kt,R={σR,i+sR+PR,t}i∈Zl.

Above, regular addition operator + can be alternatively replaced by digit-wise modulo 10 addition operator ⊕.

Server SB generates its chaff set by operating analogously using a fixed sequence of offsets ΣB={σB,0, . . . , σB,l-1}. The above protocol guarantees that and Pt∈Kt,R and Pt∈Kt,B. By choosing

        ΣR=Zl;
        ΣB={l,2 l, . . . ,l2},

as the two public offsets sets, for l=√{square root over (p)}, one can guarantee that Pt=Kt,R∩Kt,B and that the chaff set size is maximized. Maximizing the chaff set size is important, because an adversary compromising one of the two servers can at best guess a valid passcode from its locally computed chaff set, an event happening with probability 1/|Kt,R|=1/|Kt,B|; thus, minimizing this probability to 1/√{square root over (p)} essentially means that a breach of one server halves the effective length of the passcodes, say from 6 digits to 3 digits, as the adversary has to guess the missing 3 digits.

    
    


However, the disclosed non-cryptographic split-server passcode verification scheme is not compatible with the existence of an auxiliary channel. In other words, the disclosed scheme operates only in the case where no auxiliary channel exists. It is therefore important to design a new split-server passcode verification scheme that is both lightweight and supports an auxiliary channel in the token.
Verification Scheme
According to one aspect of the invention, a split-server passcode verification scheme is provided that is lightweight and fully compatible with the existence of an auxiliary channel between the token and the authentication servers.
Setting
While the disclosed scheme is general enough to operate with a wide range of token designs, the following exemplary embodiment employs the client-side design of U.S. patent application Ser. No. 13/837,259, filed Mar. 15, 2013, entitled “Configurable One-Time Authentication Tokens with improved Resilience to Attacks,” (now U.S. Pat. No. 9,270,655). FIG. 1 illustrates an exemplary client-side generation of passcodes by a token 100. As shown in FIG. 1, the exemplary token 100 comprises a red and a blue FS-PRNG, FSPR and FSPB, respectively, that produce protocodes PR,t and PB,t, respectively, for each epoch t. Additionally, the blue FS-PRNG FSPB produces pseudorandom information RA,t that is used for the passcode-specific pseudorandom generation of a codebook Ct which, in turn, is optionally used by the auxiliary channel to embed additional information into the two produced protocodes, finally producing the transmitted passcode Pt.
In particular, the exemplary auxiliary channel operates as follows. The embedded message m consists of a small number of k bits. A fixed (and possibly known) binary codebook B is used to map (through mapping B(·)) a k-bit message m=mk-1,tmk-2,t . . . m0,t into a binary codeword q=B(m)=ql-1,tql-2,t . . . q0,t of size l, where l equals the number of digits in the final passcode. Here, typical values are as follows: k=4 and l=6 or l=8. Thus, B can take the form of a [8, 4, 4] or [6, 4, 2] error correcting code (specifically, the [8, 4, 4] extended Hamming code or a corresponding [6, 4, 2] Hamming code). Then, using pseudorandom bits in RA,t, the auxiliary channel maps (through mapping Ct(·)) codeword q to an l-bit digital codeword ct=Ct(q)=cl-1,tcl-2,t . . . c0,t as follows: if qi,t≠0 then ci,t is randomly selected from {1,2,3,4,5,6,7,8,9} else ci,t=0. Note that with this mapping, any two digital codewords Ct(B(m)) and Ct(B(m′)) have Hamming distance that is at least the Hamming distance between their corresponding binary codewords B(m) and B(m′); thus, mapping Ct can be itself considered a Hamming code (over zero and non-zero digits).
Finally, the final exemplary passcode Pt is computed using digit-wise modulo 10 addition of PR,t, PB,t and ct, denoted here using operator ⊕ as PR,t⊕PB,t⊕ct. In this manner, the final exemplary passcode Pt optionally embeds the auxiliary information from the k-bit message m that has been mapped into the codeword ct. Thus, the final exemplary passcode Pt can be referred to as an auxiliary-information enriched passcode. That is, if Pt=pl-1,tpl-2,t . . . p0,t, PR,t=ri-1,tri-2,t . . . r0,t and PB,t=bi-1,tbi-2,t . . . b0,t (where pi,t,, ri,t, bi,t, 0≦i≦l<1 are all digits), then for 0≦i≦l−1:

pi,t=ri,t+bi,t+ci,t mod 10.

Similarly, operator Θ denotes digit-wise modulo 10 subtraction, used to appropriately solve the above equation to one of two protocodes PR,t and PB,t or the codeword ct.

To facilitate the description of the disclosed split-server passcode verification scheme, some notation is introduced related to the representations of Pt, PR,t, PB,t and ct as l-digit digital-number strings. An l-digit numeric string s=sl-1sl-2 . . . s0, where, without loss of generality, l is even, can also be viewed as the concatenation of the high-order (or most significant) and the low-order (or least significant) (l/2)-digit strings s=sl-1sl-2 . . . sl/2 and s=s(l/2)-1s(l/2)-2 . . . s0, i.e.,

s=s∥s, 

or simply

s=ss. 

It is noted that while the present invention is illustrated herein using a high-order (or most significant) half and a low-order (or least significant) half of the protocode, the invention can be applied using high-order (or most significant) portions and low -order (or least significant) portions of the protocode that have an unequal length.

Accordingly, if codebooks B and Ct are seen as 2k×l matrices then, similarly, the high-order (or most significant) portion B, Ct and the low-order (or least significant) portion B, Ct can be considered parts of them, which are 2k×l/2 matrices.
Server-Side Verification Protocol
The disclosed exemplary split-server passcode verification scheme splits the verification process across the two servers according to the high-order versus low-order partition of the passcode into two equally size parts in the exemplary embodiment. The passcode may be an auxiliary-information enriched passcode. That is, in the case of such auxiliary-information enriched passcodes, unlike some existing split verification methods that divide the passcode “horizontally,” where each server possesses a secret share of the protocode PR,t⊕PB,t and where both servers need to reconstruct and verify passcode PR,t⊕PB,t⊕ct, the disclosed split-server passcode verification scheme, shown in FIG. 2, divides the passcode “vertically,” where each server still possesses a secret share of the protocode PR,t⊕PB,t but now each server is responsible for reconstructing and verifying only the high-order portion PR,t⊕PB,t⊕ct and, respectively, the low-order portion PR,t⊕PB,t⊕ct. This idea is effective in yielding efficient split-server verification protocols. However, the existence of an auxiliary channel that is maintained by only one of the two servers introduces some additional challenges.
Moreover, the disclosed protocols consider the interaction between the two authentication servers, the blue SB server and the red SR server, with one trusted relying party, a server RP to which the final access-control/authentication decision is handed and which interacts with the high-level application that the end user of the token is interested in accessing.
FIG. 3 illustrates an exemplary split-server passcode verification process 300 incorporating aspects of the invention with reference to the verification scheme of FIG. 2. As shown in FIG. 3, the exemplary split-server passcode verification process 300 is initiated during step 310 when an auxiliary-information enriched candidate passcode Pt is presented to a relying party RP. It is noted that the exemplary relying party RP does not store the secret seed of the user.
The candidate passcode Pt is provided to each server SB and SR during step 320. As indicated above in conjunction with FIG. 1, the candidate passcode Pt supports the auxiliary channel. The candidate passcode Pt is thus as passcode that optionally embeds auxiliary information. The two servers SB and SR exchange information during step 330, as discussed further below in conjunction with FIG. 5. Finally, the servers SB and SR return a verification-related output to the relying party RP during step 340 indicating whether their respective portion has been verified. The final verification performed by the relying party RP is discussed further below in conjunction with FIG. 9. Generally, the relying party RP authenticates the user if and only if both servers SB and SR verify their respective portion of the candidate passcode Pt. These individual verifications of respective portions of the passcode may be implicit: The final verification may actually be performed at the relying party RP based on verification-related information outputted by the two servers. As discussed hereinafter, the verification protocol can comprise, for example, the vertical splitting techniques described herein.
Exemplary Verification Protocol Πt for an Epoch t
During the verification process, one server, here by exemplary convention, the blue server, is responsible for verifying the high-order portion of the passcode, and the second server, here by exemplary convention, the red server, is responsible for verifying the low-order portion of the passcode. In addition to the candidate passcode P′, at the beginning of the verification process, the two servers, blue and red, each have the following inputs for any given epoch t (within a certain search window, such as an exemplary duration of 70 epochs):

    
    
        The blue server possesses pseudorandomness RA,t, binary codebook B and the blue protocode PB,t=PB,tPB,t.
        The red server possesses the red protocode PR,t=PR,tPR,t.
    
    


The exemplary verification protocol Πt then runs as follows for a given epoch t:
FIG. 4 illustrates an exemplary preprocessing portion 400 of the disclosed split-server passcode verification scheme 300. As shown in FIG. 4, Server SB uses pseudorandomness RA,t and binary codebook B to compute the digital codebook Ct=CtCt for epoch t, using the mapping techniques discussed above in the section entitled “Setting.”
FIG. 5 illustrates an exemplary first phase portion 500 of the disclosed split-server passcode verification scheme 300. As shown in FIG. 5, during the first phase 500, the two servers exchange information as follows:

    
    
        SB sends {Ct,PB,t} to SR.
        SR sends PR,t to SB.
    
    


FIGS. 6A and 6B illustrate an exemplary second phase portion 600 and a verification phase portion 650 of the disclosed split-server passcode verification scheme 300, respectively. As shown in FIG. 6A, during the second phase 600, each server verifies the respective high-order or low-order portion of the passcode:
The blue server SB performs the following steps:
i. set index Īt to Ø;
ii. compute high order auxiliary information dt=P′tΘPR,tΘPB,t; It is noted that any references to “Θ” in the equations herein are intended to be a reference to the mathematical symbol “Θ” for digit-wise modulo 10 subtraction.
iii. for each cj∈Ct, 1≦j≦2k, check if cj=dt and if yes, then set index Īt←Īt∪j;
iv. output index Īt to Relying Party RP containing matching indices in Ct.
The red server SR performs the following steps:
i. set index It to Ø;
ii. compute low order auxiliary information dt=P′tΘPR,tΘPB,t;
iii. for each cj∈Ct, 1≦j≦2k, check if cj=dt and if yes, then set index It←It∪j;
iv. output index It to Relying Party RP containing matching indices in Ct.
For the above execution of protocol Πt:

    
    
        (Īt,It)←Πt(P′,RA,t, PB,t, PR,t).
    
    


General Verification Protocol
Given protocol Πt as a subroutine, the exemplary general verification protocol can be described as follows:
1. Relying Party RP initializes A←Ø and ans←reject;
2. For each epoch t in the search window of length 2 s+1 epochs and using a certain ordering D of the epochs:

    
    
        Run protocol Πt as (Īt,It)←Øt(P′,RA,t,PB,t,PR,t) to have servers SB and SR produce outputs Īt and It respectively, as shown in FIG. 6A;
        Server SB sends Īt to Relying Party RP and Server SR sends It to Relying Party RP, as shown in FIG. 6A;
        Relying Party RP accepts the passcode P′ with respect to epoch t and updates A←A∪{t,it} if and only if Īt∩It≠Ø, where it=Īt∩It, as shown in FIG. 6B.
    
    


3. Relying Party RP accepts the passcode P′ and set ans←accept if and only if A≠Ø.
4. Relying Party RP generates an output 660 (ans, {t*,it*}, state) to the high-level application and the two servers SB and SR where if ans=accept then {t*,it*}∈A or else {t*,it*}=⊥, and where state 670 is the authentication state of the attempted user authentication attempt.
That is, the relying party RP will search the entire search window and will accept the passcode only if the passcode has been accepted with respect to at least one epoch in the search window.
Any ordering D can be used in principle; two practical orderings are the left-to-right ordering (t′−s, . . . , t′−1, t′, 1, . . . , t′+s) or the alternating ordering (t′,t′+1,t′−1,t′+2,t′−2, . . . , t′+s,t′−s).
It can be shown, for any (t,it)∈A, it can either be the empty set or a singleton.
Output item {t*,it*} 660 corresponds to the updated information about the most recent (last) epoch t* that a successful authentication was performed for the token, along with the corresponding auxiliary information it* (a k-bit message), and it can be selected from set A in any arbitrary way; four practical exemplary selection policies may be to choose the epoch-auxiliary information pair corresponding to the minimum, maximum, median or closest epoch t* to the current Relying Party RP time t′.
Output item state 670 corresponds to secondary decision elements that may take into consideration the auxiliary information {it1,it2, . . . ,itl} that is contained in A. For instance, if silent alarms are used, then state 670 may encode the new silent alarm state of the token, and its semantic interpretation according to a given policy.
Only output item t* is necessary to be returned to servers SB and SR; ans is implied by t* and pair (it*,state) can be concealed depending on whether the state 670 related to the auxiliary information is stored and managed at servers SB or SR, or at the relying party RP.
In some cases, the information sent back to server SB can be different than the one sent back to SR, i.e., the feedback sent back by RP can be asymmetric. For instance, whenever silent alarms and drifting keys are employed using pseudorandomness provided solely by SB, then the auxiliary information it* must be an output that reaches server SB so that server SB is able to appropriately process the auxiliary channel information and possibly update its local state, which in turn can be communicated back to the relying party RP.
It is noted that the main vertical-split verification protocol discussed above (and its improvements described below) can be applied even for passcodes that are split vertically not in halves but in other unequal low-order and high-order portions, e.g., when an eight-digit passcode is vertically split into a 5-digit high-order part and a 3-digit low-order part.
Improvements and Extensions
Simplified Verification Protocol. The basic protocol Πt can be simplified as follows, under the condition that the binary codebook B is known to both server SB and server SR (a standard assumption as B is public information), but also at the minor cost of introducing an additional round of communication between SB and SR. There is no pre-processing phase at the blue server SB.
FIG. 7 illustrates an exemplary alternate first phase portion 700 of an alternate implementaiton implementation of the disclosed split-server passcode verification scheme 300. As shown in FIG. 7, during the first phase 700, the two servers exchange information as follows:

    
    
        SR sends PR,t to SB and SB sends PR,t to SR.
    
    


During the exemplary alternate first phase portion 700, no information about codebook Ct is sent to the red server Sr.
FIGS. 8A and 8B, collectively, illustrate an exemplary alternate second phase portion 800, 850 of the disclosed split-server passcode verification scheme 300. Generally, the alternate second phase 800 augments Steps iii and iv relative to the embodiment shown in FIG. 6A in each server's protocol. As discussed hereinafter, Step iii is run on the binary codewords of the binary codebook B=BB using a slightly different (acceptance) test and Step iv is augmented by a round of interaction.
As shown in FIG. 8A, each server first computes high or low order auxiliary information dt or dt, as discussed above in conjunction with FIG. 6A, and then maps the high or low order candidate digital codeword dt or dt to a corresponding high or low order binary candidate codeword q or q as follows: Every non-zero digit of dt or dt is changed to a 1 in q or q respectively.
Then, Step 3 runs as discussed above in conjunction with FIG. 6A, but now for each qj∈B or respectively for each qj∈B, 1≦j≦2k to generate output Īt and It, respectively.
Finally, as shown in FIG. 8A, servers SB and SR exchange their outputs Īt and It, and then as shown in FIG. 8B, both servers SB and SR compute the intersection I′=Īt∩It and proceed as follows:

    
    
        if the intersection I′ is not a singleton, then both servers SB and SR output Īt and It, respectively (and terminate).
        otherwise,
        Let RA,t(I′)={RA,t(I′),RA,t(I′)} be the pseudorandom bits RA,t(I′) from RA,t that are associated with mapping binary codeword qI′∈B to digital codeword cI′. Server SB sends to Server SR the pseudorandom bits RA,t(I′), and using RA,t(I′) the Server SB computes cI′. The Server SB finally outputs Īt if cI′=dt or Ø otherwise.
        Using RA,t(I′), Server SR computes cI′ and finally outputs Īt if cI′=dt or Ø otherwise.
    
    


An advantage of this first alternate protocol is the reduction of the communication cost, as the precomputed codebook Ct is no longer communicated to the server SR, at the cost of slightly increasing the interaction between the two servers.
It is noted that both the basic protocol Πt and its simplification above can be adapted to operate in a single-server setting (where the red and blue servers may collapse to one server). In any case (single- or two-server case), by performing the test directly over the digital codebook Ct with protocol Πt (rather than over the binary codebook B) and by using in the simplified version above the second round check (i.e., by mapping binary codeword qI′ back to digital codeword cI′ and checking whether candidate codeword d satisfies d=cI′), the (single- or) two-server basic and simplified protocols strictly improve the security of the (single- or) two-server one-time passcode token system of U.S. patent application Ser. No. 13/837,259, filed Mar. 15, 2013, entitled “Configurable One-Time Authentication Tokens with Improved Resilience to Attacks,” (now U.S. Pat. No. 9,270,655).
Alternate Simplified Verification Protocol. Additionally, the above protocol can be further simplified under the assumption that the trusted relying party knows the binary codebook B and possesses the pseudorandom information RAt either by storing/producing the information explicitly or by receiving the information through an on-demand request to server SB at the beginning of the split-server passcode verification protocol, as follows:
In the alternate second phase 800 above, the final step is omitted, that is, no additional information exchange is performed between SB and SR.
The high and low order dt and dt of the candidate digital codeword are included in the outputs Īt and respectively It of the basic protocol.
The general verification protocol is slightly modified to perform the additional test with respect to the digital codeword cI′ as follows:
FIG. 9 illustrates this exemplary alternate verification portion 900 of the disclosed split-server passcode verification scheme 300. As shown in FIG. 9, the servers SB and SR send the Relying Party RP their outputs Īt and dt and It and dt, respectively, during Step 1. The Relying Party RP accepts the passcode P′ with respect to epoch t during Step 2 if and only if (1) Īt∩It=it≠Ø, (2) it is a singleton and (3) Using pseudorandom bits RA,t(it) from RA,t, binary codeword bit is mapped to digital codeword cit so that cit=dtdt.
Relying Party RP generates an output 910 (ans,{t*,it*},state) to the high-level application and the two servers SB and SR where if ans=accept then {t*,it*}∈A or else {t*,it*}=⊥, and where state update 920 is the authentication state of the attempted user authentication attempt.
Thus, in this case, even though the client-side management of the information related to the auxiliary channel is asymmetric, the corresponding server-side management of this information is completely symmetric.
Extended Verification Protocol. The exemplary basic protocol Πt can be extended to allow incorporation with the recent chaff-based split-server verification protocol disclosed in U.S. patent application Ser. No. 13/795,801, filed Mar. 12, 2013, entitled “Distributed Cryptography Using Distinct Value Sets Each Comprising at Least One Obscured Secret Value,” thus extending this protocol to be compatible with the existence of an auxiliary channel, as follows.

    
    
        There is no pre-processing phase at the blue server SB.
        In the first phase, in addition to the information exchanged in U.S. patent application Ser. No. 13/795,801, filed Mar. 12, 2013, entitled “Distributed Cryptography Using Distinct Value Sets Each Comprising at Least One Obscured Secret Value,” namely values sR=PB,t−σR,jt,B and sB=PR,t−σB,jt,R as explained in the section entitled “Lightweight Split-Server Verification,” SB sends to SR codebook Ct.
        In the second phase, the protocol involves running the (joint-computation) protocol of U.S. patent application Ser. No. 13/795,801, at the end of which server SB has computed set Kt,B and SR has computed set Kt,R such that the (correct for epoch t) combined protocode PB,t+PR,t=Kt,R∩Kt,B, |Kt,B|=|Kt,R|=l. Here, regular addition operator + can be alternatively replaced by digit-wise modulo 10 addition operator ⊕. Then Step ii of the second phase is changed so that for each passcode P∈Kt,B (resp. P∈Kt,R) a corresponding candidate digital codeword d is computed as d=P′tΘP, where P′t is the candidate passcode provided by the user. Accordingly, Step iii of the second phase is changed so that each such candidate digital codeword d is checked against any possible digital codeword cj in Ct and each server outputs its local verification decision appropriately accepting the passcode P′t if and only if there exists j such that cj=d for some codeword d of the |Kt,B|=|Kt,R|=l codewords computed in Step ii. That is, conventionally we can define Īt (respectively It) to be the set of pairs (j, Pj) of matching indices j computed by Server SB (respectively by Server SR) and its corresponding protocode Pj in set Kt,B (respectively set Kt,R) that produced the corresponding digital codeword d matching the codebook in position j, or ⊥ if no such matching index was found.
    
    


Accordingly, the general verification protocol acceptance test Īt∩It≠Ø in Step 2 is augmented to further test that this non-empty intersection is a singleton set (j, Pj), and then accordingly it is set to j.
It is noted that the split-server verification protocols described above (in the section entitled “Server Side Verification Protocol,” the two alternative simplified versions thereof, and the extension above), all maintain a minimum desired level of security in the event of an ephemeral or permanent server being compromised. By successfully compromising one server, the search space of the attacker is reduced only to half; e.g., for 8-digit passcodes, the OTP system still maintains a desired 4-digit security.
Extensions for General Auxiliary-Channel Compatibility. As apparent to one skilled in art, the last protocol takes the particular split-server verification protocol of U.S. patent application Ser. No. 13/795,801, filed Mar. 12, 2013, entitled “Distributed Cryptography Using Distinct Value Sets Each Comprising at Least One Obscured Secret Value” (a protocol that is also described above and does not support the use of an auxiliary channel) and applies to it the ideas, described herein in the main protocol of the section entitled “Server Side Verification Protocol,” around the split-server verification of passwords of the form

Pt=PR,t⊕PB,t|ct,

which do support the use of an auxiliary channel, referred to herein as auxiliary-information enriched passcodes.

In general, auxiliary-information enriched passcodes require shared knowledge of the underlying codebook Ct used to map auxiliary messages into offsets of the protocode for formation of the final produced passcodes. In the exemplary embodiments of the present invention, an asymmetric auxiliary-channel model of U.S. patent application Ser. No. 13/837,259, filed Mar. 15, 2013, entitled “Configurable One-Time Authentication Tokens with Improved Resilience to Attacks” (now U.S. Pat. No. 9,270,655), is adopted, where the secret (digital) codebook Ct (that is used by the auxiliary channel) is computed only by the blue server SB by tranforming a publicly known (binary) codebook B in a non-deterministic way using pseudorandom information RA,t (produced only by the blue server SB). Accordingly, in order for any split-server verification protocol, supporting passcodes that are not enriched with auxiliary information, to operate in this asymmetric auxiliary-channel model, there is a need to make the codebook Ct also available to the red server SR and/or the relying party RP. That is any given split-server verification protocol of non-enriched passcodes that is appropriately augmented to support verification of also auxiliary-information enriched passcodes in the asymmetric auxiliary channel model discussed above will necessarily need to provide one or more of the three involved parties (the red and blue servers and the relying party) with access to underlying secret codebook Ct. This necessary task can be realized using the techniques presented above. Collectively, aspects of the present invention provide three methods to make Ct available to the involved parties during the split-server verification protocol of auxiliary-information enriched passcodes:
1. Explicit Codebook Transmission: In this case, as described in the main protocol of the section entitled “Server Side Verification Protocol,” the codebook Ct is explicitly (possibly partially) transmitted to server SR. FIG. 10 illustrates an exemplary split-server passcode verification process 1000 incorporating auxiliary channel support aspects of the invention. As shown in FIG. 10, the exemplary split-server passcode verification process 1000 is initiated during step 1010 when an auxiliary-information enriched candidate passcode Pt is presented to a relying party RP.
The candidate passcode Pt is provided to each server SB and SR during step 1020. As indicated above in conjunction with FIG. 1, the candidate passcode Pt supports the auxiliary channel. The candidate passcode Pt is thus a passcode that optionally embeds auxiliary information. The two servers SB and SR exchange information during step 1030. The codebook Ct is at least partially explicitly transmitted to server SR during step 1030. The servers SB and SR return a verification to the relying party RP during step 1040 indicating whether passcode Pt or their respective portion of passcode Pt has been verified with respect to a valid codeword of codebook Ct that consistently encodes a unique auxiliary-channel message. The final verification is performed by the relying party RP in a similar (but not necessarily the same) process with the one discussed above in conjunction with FIG. 6B. Generally, the relying party RP authenticates the user during step 1050 if and only if both servers SB and SR verify the auxiliary-information enriched candidate passcode Pt or their respective portion of Pt.
2. Implicit Codebook Computation and Codeword Checking: In this case, the non-deterministic computation of codebook Ct is enabled by transmitting the pseudorandom information RA,t as a whole or partially to some party; then, computation is performed implicitly on a codeword basis. That is, an appropriate codeword in B is first selected for deriving the auxiliary-information message, and only then this binary codeword is non-deterministically mapped to its equivalent digital codeword for verification. Depending on which party performs the above process, the following are further distinguished:
(a) Server-Side Processing: The above decoding and checking is performed at the server(s), as in the first simplified protocol of the main protocol. FIG. 11 illustrates an exemplary split-server passcode verification process 1100 incorporating server-side auxiliary channel support aspects of the invention. As shown in FIG. 11, the exemplary split-server passcode verification process 1100 is initiated during step 1110 when an auxiliary-information enriched candidate passcode Pt is presented to a relying party RP.
The auxiliary-information enriched candidate passcode Pt is provided to each server SB and SR during step 1120. The two servers SB and SR exchange information during step 1130. The pseudorandom information RA,t is transmitted to server SR during step 1030. An appropriate codeword from codebook B is selected for deriving the auxiliary-information message, and only then this binary codeword is mapped to its equivalent digital codeword for verification.
The servers SB and SR return a verification to the relying party RP during step 1140 indicating whether passcode Pt or their respective portion of passcode Pt has been verified first with respect to a valid binary codeword of codebook B that consistently encodes a unique auxiliary-channel message and second with respect to the digital codeword (in codebook Ct) corresponding to the first binary codeword in B. The final verification is performed by the relying party RP in a similar (but not necessarily the same) process with the one discussed above in conjunction with FIG. 8B. Generally, the relying party RP authenticates the user during step 1150 if and only if both servers SB and SR verify the auxiliary-information enriched candidate passcode Pt or their respective portion of Pt.
(b) Relying-Party Processing: The above decoding and checking is performed at the relying party, as in the second simplified protocol of the main protocol. FIG. 12 illustrates an exemplary split-server passcode verification process 1100 incorporating relying party processing of the auxiliary channel information. As shown in FIG. 12, the exemplary split-server passcode verification process 1200 is initiated during step 1210 when an auxiliary-information enriched candidate passcode Pt is presented to a relying party RP.
The auxiliary-information enriched candidate passcode Pt is provided to each server SB and SR during step 1220. The two servers SB and SR exchange information during step 1230. The servers SB and SR return a verification to the relying party RP during step 1240 indicating whether passcode Pt or their respective portion of passcode Pt has been verified with respect to a valid binary codeword of codebook B that consistently encodes a unique auxiliary-channel message. The final verification is performed by the relying party RP in a similar (but not necessarily the same) process with the one discussed above in conjunction with FIG. 9. Generally, the relying party RP authenticates the user during step 1150 if and only if both servers SB and SR verify the auxiliary-information enriched candidate passcode Pt or their respective portion of Pt and RP further verifies Pt with respect to a valid digital codeword in codebook Ct. The latter step is performed as follows. An appropriate codeword from codebook B is selected by the relying party RP for deriving the auxiliary-information message, and only then this binary codeword is mapped to its equivalent digital codeword for verification, using the pseudorandom information RA,t.
It is noted that the above codebook-handling processes can be applied to any generic split-server passcode verification protocol of the following form: A candidate passcode P′t is provided as input to servers SR and SB, two servers exchange information and compute a local output (possibly in multiple rounds) that is finally sent to the relying party RP which accepts or rejects P′t. Whenever access to the underlying secret codebook Ct is required during the computation, one of the three codebook accessing methods described above is employed. Therefore, aspects of the current invention introduce a design framework for constructing methods for split-server verification of auxiliary-information enriched passcodes in the asymmetric auxiliary-channel model. In particular, given any split-server verification protocol of non-enriched passcodes (e.g., like the one in U.S. patent application Ser. No. 13/795,801, Mar. 12, 2013, entitled. “Distributed Cryptography Using Distinct Value Sets Each Comprising at Least One Obscured Secret Value”) the exemplary framework proposes three ways to extend this protocol to the verification of enriched passcodes. Moreover, given any split-server verification protocol of enriched passcodes in the symmetric auxiliary-channel model, where the codebook is composed by red and blue portions locally available to SR and SB (e.g., like the ones in U.S. patent application Ser. No. 13/404,737, filed Feb. 24, 2012, entitled “Method and Apparatus for Authenticating a User Using Multi-Server One-Time Passcode Verification” (now U.S. Pat. No. 9,118,661)) the exemplary framework proposes three ways to realize this protocol also in the asymmetric auxiliary-channel model.
The foregoing applications and associated embodiments should be considered as illustrative only, and numerous other embodiments can be configured using the techniques disclosed herein, in a wide variety of different cryptography applications.
For example, both the vertical splitting and the auxiliary-channel handling methods described herein can be extended in the case of more than two servers, assuming a token-side design that supports such extensions. For instance, if a passcode comprises of three protocode parts, say red, blue and green, then vertical splitting can be considered into three corresponding parts. Splitting into more parts than the number of protocodes is also possible if the appropriate pseudorandom information is appropriately disseminated among the servers. Similarly, auxiliary-channel handling can be supported in multi-server settings,
In addition, while the present invention is illustrated herein using a high-order (or most significant) half and a low-order (or least significant) half of the protocode, the invention can be applied using high-order (or most significant) portions and low-order (or least significant) portions of the protocode that have an unequal length and/or more than two portions.
It should also be understood that split-server verification, as described herein, can be implemented at least in part in the form of one or more software programs stored in memory and executed by a processor of a processing device such as a computer. As mentioned previously, a memory or other storage device having such program code embodied therein is an example of what is more generally referred to herein as a “computer program product.”
The embodiments described herein can provide a number of significant advantages relative to conventional practice. For example, these embodiments can advantageously provide improved scalability and support of auxiliary channels. Also, a wide variety of different OTP verification protocols can be implemented using the disclosed techniques.
Authentication processes in other embodiments may make use of one or more operations commonly used in the context of conventional authentication processes. Examples of conventional authentication processes are disclosed in A. J. Menezes et al., Handbook of Applied Cryptography, CRC Press, 1997, which is incorporated by reference herein. These conventional processes, being well known to those skilled in the art, will not be described in further detail herein, although embodiments of the present invention may incorporate aspects of such processes.
The communication system may be implemented using one or more processing platforms. One or more of the processing modules or other components may therefore each run on a computer, storage device or other processing platform element. A given such element may be viewed as an example of what is more generally referred to herein as a “processing device.”
Referring now to FIG. 13, one possible processing platform that may be used to implement at least a portion of one or more embodiments of the invention comprises cloud infrastructure 1300. The cloud infrastructure 1300 in this exemplary processing platform comprises virtual machines (VMs) 1302-1, 1302-2, . . . 1302-M implemented using a hypervisor 1304. The hypervisor 1304 runs on physical infrastructure 1305. The cloud infrastructure 1300 further comprises sets of applications 1310-1, 1310-2, . . . 1310-M running on respective ones of the virtual machines 1302-1, 1302-2, . . . 1302-M under the control of the hypervisor 1304.
The cloud infrastructure 1300 may encompass the entire given system or only portions of that given system, such as one or more of client, servers, controller, authentication server or relying server in the system.
Although only a single hypervisor 1304 is shown in the embodiment of FIG. 13, the system may of course include multiple hypervisors each providing a set of virtual machines using at least one underlying physical machine.
An example of a commercially available hypervisor platform that may he used to implement hypervisor 1304 and possibly other portions of the system in one or more embodiments of the invention is the VMware® vSphereTM which may have an associated virtual infrastructure management system such as the VMware® vCenterTM. The underlying physical machines may comprise one or more distributed processing platforms that include storage products, such as VNX and Symmetrix VMAX, both commercially available from EMC Corporation of Hopkinton, Mass. A variety of other storage products may be utilized to implement at least a portion of the system.
Another example of a processing platform is processing platform 1400 shown in FIG. 14. The processing platform 1400 in this embodiment comprises at least a portion of the given system and includes a plurality of processing devices, denoted 1402-1, 1402-2, 1402-3, . . . 1402-D, which communicate with one another over a network 1404. The network 1404 may comprise any type of network, such as a WAN, a LAN, a satellite network, a telephone or cable network, a cellular network, a wireless network such as WiFi or WiMAX, or various portions or combinations of these and other types of networks.
The processing device 1402-1 in the processing platform 1400 comprises a processor 1410 coupled to a memory 1412. The processor 1410 may comprise a microprocessor, a microcontroller, an ASIC, an FPGA or other type of processing circuitry, as well as portions or combinations of such circuitry elements, and the memory 1412, which may be viewed as an example of a “computer program product” having executable computer program code embodied therein, may comprise RAM, ROM or other types of memory, in any combination.
Also included in the processing device 1402-1 is network interface circuitry 1414, which is used to interface the processing device with the network 1404 and other system components, and may comprise conventional transceivers.
The other processing devices 1402 of the processing platform 1400 are assumed to be configured in a manner similar to that shown for processing device 1402-1 in the figure.
Again, the particular processing platform 1400 shown in the figure is presented by way of example only, and the given system may include additional or alternative processing platforms, as well as numerous distinct processing platforms in any combination, with each such platform comprising one or more computers, storage devices or other processing devices.
Multiple elements of system may be collectively implemented on a common processing platform of the type shown in FIG. 13 or 14, or each such element may be implemented on a separate processing platform.
As is known in the art, the methods and apparatus discussed herein may be distributed as an article of manufacture that itself comprises a machine readable recordable storage medium containing one or more programs. The one or more programs are operable, in conjunction with a computer system, to carry out all or some of the steps to perform the methods or create the apparatuses discussed herein.
It should again be emphasized that the above-described embodiments of the invention are presented for purposes of illustration only. Many variations and other alternative embodiments may be used. For example, the techniques are applicable to a wide variety of other types of cryptographic devices and authentication systems that can benefit from distributed cryptography using distinct value sets as disclosed herein. Also, the particular configuration of communication system and processing device elements shown herein, and the associated authentication techniques, can be varied in other embodiments. Moreover, the various simplifying assumptions made above in the course of describing the illustrative embodiments should also be viewed as exemplary rather than as requirements or limitations of the invention. Numerous other alternative embodiments within the scope of the appended claims will be readily apparent to those skilled in the art.

## Claims

1. A method, comprising:
receiving an authentication passcode generated by a token associated with a user, wherein said authentication passcode is based on (i) at least one protocode generated by said token using a seed and a current time and processed by at least one of at least a first authentication server and a second authentication server to authenticate said user; and (ii) auxiliary information embedded in said authentication passcode with said at least one protocode when said authentication passcode is generated, wherein said embedded auxiliary information is distinct from (a) said at least one protocode; and (b) said seed and said current time components of said at least one protocode, wherein a mapping function maps a given message in a message space to a codeword in a codebook; and
processing the received authentication passcode using at least said first authentication server and said second authentication server, wherein at least one of said first authentication server, said second authentication server and a relying party extract said embedded auxiliary information from the received authentication passcode.

2. The method of claim 1, wherein said embedded auxiliary information is embedded into said authentication passcode using a codebook Ct that is at least partially transmitted to said second authentication server.

3. The method of claim 1, wherein said embedded auxiliary information is embedded into said authentication passcode using a codebook Ct and wherein pseudorandom information RA,t is at least partially transmitted to one or more of said first authentication server, said second authentication server and said relying party and wherein an appropriate binary codeword in a binary codebook B is selected for deriving said embedded auxiliary information and wherein said binary codeword is mapped to a digital codeword for verification using said pseudorandom information RA,t.

4. The method of claim 3, wherein said selection of said appropriate binary codeword in said binary codebook B for deriving said embedded auxiliary information and said mapping of said binary codeword to said digital codeword for verification is performed by said relying party.

5. The method of claim 3, wherein said selection of said appropriate binary codeword in said binary codebook B for deriving said embedded auxiliary information and said mapping of said binary codeword to said digital codeword for verification is performed by one or more of said first authentication server and said second authentication server.

6. The method of claim 1, wherein said method extends a multi-server verification process to provide said processing of said received authentication passcode based on said embedded auxiliary information.

7. The method of claim 1, wherein said received authentication passcode is based on one or more of at least two protocodes PR,t and PB,t generated by said token and pseudorandom information RA,t.

8. The method of claim 7, wherein said embedded auxiliary information is embedded into said authentication passcode using a codebook Ct based on said pseudorandom information RA,t.

9. The method of claim 8, wherein said pseudorandom information RA,t is generated by only one of said first authentication server and said second authentication server.

10. The method of claim 8, wherein a given message in said message space is mapped to a binary codeword in a binary codebook and said binary codeword is mapped to a decimal codeword in a decimal codebook using a shared key.

11. The method of claim 1, wherein said first authentication server computes high order auxiliary information comprising a high order candidate codeword embedded in said received authentication passcode and wherein said second authentication server computes low order auxiliary information comprising a low order candidate codeword embedded in said receive authentication passcode.

12. The method of claim 11, wherein said first authentication server determines one or more high order matching indices between said high order embedded codeword and a high order portion of a codeword of a corresponding codebook and wherein said second authentication server determines one or more low order matching indices between said low order embedded codeword and a low order portion of a codeword of a corresponding codebook.

13. The method of claim 12, wherein said relying party accepts said received authentication passcode when said high order matching indices and said low order matching indices have a non-empty intersection.

14. The method of claim 1, wherein said embedded auxiliary information comprises a message indicating whether said token has been attacked.

15. The method of claim 1, wherein said embedded auxiliary information provides an indicator of one or more of an integrity of said token, an operational parameter of said token, and a randomly evolving key of said token.

16. The method of claim 1, further comprising the step of computing a combined first and second protocode PB,t⊕PR,t based on a computed chaff set Kt,B of said first authentication server and a computed chaff set Kt,R of said second authentication server SR, and wherein for each passcode P∈Kt,B (respectively each passcode P∈Kt,R) a corresponding candidate digital codeword d is computed as d=P′tΘP, where P′t is the candidate passcode provided by the user; and wherein each candidate digital codeword d is checked against one or more possible digital codeword cj in a codebook Ct and said first and second authentication servers output a corresponding local verification decision accepting the passcode P′t when there exists a j such that cj=d.

17. An apparatus comprising:
a memory; and
at least one hardware device, coupled to the memory, operative to implement the following steps:
receiving an authentication passcode generated by a token associated with a user, wherein said authentication passcode is based on (i) at least one protocode generated by said token using a seed and a current time and processed by at least one of at least a first authentication server and a second authentication server to authenticate said user; and (ii) auxiliary information embedded in said authentication passcode with said at least one protocode when said authentication passcode is generated, wherein said embedded auxiliary information is distinct from (a) said at least one protocode; and (b) said seed and said current time components of said at least one protocode, wherein a mapping function maps a given message in a message space to a codeword in a codebook; and
processing the received authentication passcode using at least said first authentication server and said second authentication server, wherein at least one of said first authentication server, said second authentication server and a relying party extract said embedded auxiliary information from the received authentication passcode.

18. The apparatus of claim 17, wherein said embedded auxiliary information is embedded into said authentication passcode using a codebook Ct that is at least partially transmitted to said second authentication server.

19. The apparatus of claim 17, wherein said embedded auxiliary information is embedded into said authentication passcode using a codebook Ct and wherein pseudorandom information RA,t is at least partially transmitted to one or more of said first authentication server, said second authentication server and said relying party and wherein an appropriate binary codeword in a binary codebook B is selected for deriving said embedded auxiliary information and wherein said binary codeword is mapped to a digital codeword for verification using said pseudorandom information RA,t.

20. The apparatus of claim 19, wherein said selection of said appropriate binary codeword in said binary codebook B for deriving said embedded auxiliary information and said mapping of said binary codeword to said digital codeword for verification is performed by said relying party.

21. The apparatus of claim 19, wherein said selection of said appropriate binary codeword in said binary codebook B for deriving said embedded auxiliary information and said mapping of said binary codeword to said digital codeword for verification is performed by one or more of said first authentication server and said second authentication server.

22. The apparatus of claim 17, wherein said apparatus extends a multi-server verification process to provide said processing of said received authentication passcode based on said embedded auxiliary information.

23. The apparatus of claim 17, wherein said received authentication passcode is based on one or more of at least two protocodes PR,t and PB,t generated by said token and pseudorandom information RA,t.

24. The apparatus of claim 17, wherein said first authentication server computes high order auxiliary information comprising a high order candidate codeword embedded in said received authentication passcode and wherein said second authentication server computes low order auxiliary information comprising a low order candidate codeword embedded in said receive authentication passcode, wherein said first authentication server determines one or more high order matching indices between said high order embedded codeword and a high order portion of a codeword of a corresponding codebook and wherein said second authentication server determines one or more low order matching indices between said low order embedded codeword and a low order portion of a codeword of a corresponding codebook, wherein said relying party accepts said received authentication passcode when said high order matching indices and said low order matching indices have a non-empty intersection.

25. An article of manufacture, comprising a non-transitory machine readable recordable storage medium containing one or more programs which when executed implement the steps of:
receiving an authentication passcode generated by a token associated with a user, wherein said authentication passcode is based on (i) at least one protocode generated by said token using a seed and a current time and processed by at least one of at least a first authentication server and a second authentication server to authenticate said user; and (ii) auxiliary information embedded in said authentication passcode with said at least one protocode when said authentication passcode is generated, wherein said embedded auxiliary information is distinct from (a) said at least one protocode; and (b) said seed and said current time components of said at least one protocode, wherein a mapping function maps a given message in a message space to a codeword in a codebook; and
processing the received authentication passcode using at least said first authentication server and said second authentication server, wherein at least one of said first authentication server, said second authentication server and a relying party extract said embedded auxiliary information from the received authentication passcode.