Lightweight network authentication for resource constrained devices via mergeable stateful signatures

Abstract

Signature-based authentication is a core cryptographic primitive essential for most secure networking protocols. A new signature scheme, MSS, allows a client to efficiently authenticate herself to a server. The new scheme is modeled in an offline/online model where client online time is premium. The offline component derives basis signatures that are then composed based on the data being signed to provide signatures efficiently and securely during run-time. MSS requires the server to maintain state and is suitable for applications where a device has long-term associations with the server. MSS allows direct comparison to hash chains-based authentication schemes used in similar settings, and is relevant to resource-constrained devices, e.g., IoT. MSS instantiations are derived for two cryptographic families, assuming the hardness of RSA and decisional Diffie-Hellman (DDH) respectively. Then used is the new scheme to design an efficient time-based one-time password (TOTP) protocol.

Claims

1. A system of or operatively interfaced with an IoT environment inclusive of internet of things (IoT) devices, the system comprising: a hardware-implemented computational platform configured to generate authenticated messages utilizing mergeable stateful signatures to generate authenticated; wherein two or more message/signature pairs are merged by the computational platform to obtain a new message/signature pair, said system being invertible and also a public operation, so it does not require knowledge of a secret key, which allows a client to authenticate itself to a single server multiple times spread over different transactions and times.

2. The system of claim 1, wherein each of the authenticated messages are unique for a lifespan of the system.

3. The system of claim 1, wherein the authenticated messages are client-initiated.

4. The system of claim 1, wherein the authenticated messages are IoT device-initiated.

5. The system of claim 1, wherein the system is stateful in that state, or verifier identity, is maintained across multiple messages/signatures.

6. The system of claim 1, wherein a construction of the computational platform configured to generate authenticated messages utilizing mergeable stateful signatures is defined or characterized such that it builds upon a general intermediate primitive.

7. The system of claim 1, wherein the IoT devices include one or more of: a smart watch, a smart refrigerator, a thermostat, and a heart rate monitor.

8. The system of claim 1, wherein the IoT devices are configured/controlled to periodically send readings to a gateway.

9. The system of claim 1, wherein the computational platform is part of: a two-factor authentication system, a system of a cloud provider for the IoT devices, a security app, or an authenticator app.

10. A time-based one-time password(TOTP) system comprising: a computer hardware-implemented architecture, platform or interface configured/programmed to periodically generate unique time-limited passwords for-two factor authentication that allows an internet of things (IoT) device to authenticate itself to a server; wherein two or more message/signature pairs are merged by the computer-implemented architecture to obtain a new message/signature pair which is a process that is invertible and also a public, so it does not require knowledge of a secret key, which allows a client to authenticate itself to a single server multiple times spread over different transactions and times.

11. The TOTP system of claim 10, wherein the computer-implemented architecture, platform or interface is configured/programmed to take into consideration the computational power and energy limitations of IoT devices and to provide the IoT devices with the ability to perform two factor authentication.

12. The TOTP system of claim 10, wherein the computer-implemented architecture, platform or interface is configured/programmed to facilitate and/or utilize offline second factor authentication.

13. The TOTP system of claim 10, wherein the computer-implemented architecture, platform or interface is configured/programmed utilizing one or more cryptographic primitives.

14. A method of reducing authentication latency and energy consumption for a time-based one-time password(TOTP) system implementation on IoT devices, the method comprising: providing an internet of things (IoT) communication protocol with a digital signature step that allows the IoT devices to precompute and store data prior to communication which in turn allows the device to produce and communicate unique authenticated messages; wherein two or more message/signature pairs are merged by the IoT communication protocol to obtain a new message/signature pair, said digital signature method being invertible and also a public operation, so it does not require knowledge of a secret key, which allows a client to authenticate itself to a single server multiple times spread over different transactions and times.

15. The method of claim 14, further comprising: receiving via a gateway the unique authenticated messages generated by one or more of the IoT devices.

16. The method of claim 14, wherein the gateway is a local/cloud gateway or smartphone.

17. The method of claim 14, wherein the unique authenticated messages are periodically generated by one or more of the IoT devices.

18. The method of claim 14, wherein the IoT devices include one or more of: a smart watch, a smart refrigerator, a thermostat, and a heart rate monitor.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1A depicts MSS overview_Setup: user signs pairs of random strings (i.e., signs 2 random strings) where each pair is mapped to a bit location and each pair string is a random value representing either 0 or 1;

(2) FIG. 1B depicts MSS overview_Offline signing: user apriori signs a fresh nonce and keeps it in storage, which will exclusively be used for next message;

(3) FIG. 1C depicts MSS overview_Online signing: user signs a message by merging/multiplying already stored signatures (in setup and offline signing) corresponding to the message bits and nonce;

(4) FIG. 2 depicts a TOTP system overview;

(5) FIG. 3 depicts offline second factor authentication;

(6) FIG. 4 is a graph showing Authentication latency of TOTP systems;

(7) FIG. 5 is a graph showing Authentication energy consumption of TOTP systems;

(8) FIG. 6 depicts a one-dimensional hash chain; and

(9) FIG. 7 is a flow chart showing an example TOTP authentication method.

DETAILED DESCRIPTION

(10) For the purpose of illustrating the invention, there is shown in the accompanying drawings several embodiments of the invention. However, it should be understood by those of ordinary skill in the art that the invention is not limited to the precise arrangements and instrumentalities shown therein and described below.

I. Overview

(11) The signature scheme, Mergeable Stateful Signatures (MSS), is described herein, which yields an authentication protocol with low overhead. As previously noted, MSS operates in a model where the verifier is assumed to always be the same party (e.g., an MQTT broker). This allows state to be maintained across multiple signatures, which in turn allows for efficiency improvements over standard signatures. The system analyzes the security of MSS in the offline/online model of Even, Goldreich and Micali, where the signing algorithm is split into two parts. The first part is costlier and can be performed offline, but importantly, before the message to sign is known. The second part is online, and can make use of the result of the offline computation to provide low cost signature. The efficiency of the online phase is tied to the length of the message being signed. The system is most efficient for short messages, and efficiency degrades as the message length grows. For messages which are 256 bits or longer (in which case, the system would sign a 256-bit hash of the message), the online phase is no faster than a standard public-key signature. Thus, in one embodiment, the IoT device may frequently send small amounts of data to a single server. It is likely that this pattern will be pervasive in IoT and other cyberphysical systems; for example, Table II (see below) shows some recent applications that have an IoT client or a sensor communicating with a single server, and the efficiency improvements introduced by MSS. Furthermore, MSS can also be utilized to reduce the signature verification cost when the client-server roles are switched and the IoT device becomes the server/verifier, which makes the system versatile and useful in other applications (e.g., last two applications in Table II).

(12) TABLE-US-00002 TABLE II Example IoT applications for MSS and efficiency gains. Number MSS-RSA vs. MSS-ECEL Gamal of Message base RSA vs. base ECELGamal Messages Size Extra Battery Extra Battery Application (per Day) (bits) Speedup Lifetime Speedup Lifetime Heart rate monitor 144-1,440 8 32 2 Continous glucose monitor 288 9 28 2 Temperature sensor 1,440 12 21 2 Soil moisture sensor 1,234 14 18 2 Vehicle tracker 2,880 57 4 1.8 Humidity sensor 1,440 14 18 2 Smart electricity meter 24-1,440 40 6 1.8 People counting sensor 96 17 15 1.9 Water level sensor 96 7 36 2 Smart lock 368 21 2 1.54 Drone command 36,000 4 2.1 1.56 and control (1 hr. use)

(13) MSS is described in Section II and implement it twice, within two digital signature standards: RSA signatures and elliptic curve ElGamal signatures. In Section III, demonstrated is a concrete application; specifically, described is use MSS to implement a time-based one-time password (TOTP) authentication protocol. TOTP systems allow a user to authenticate herself to a server using a one-time password that is valid for a short, fixed time. After the time expires, the user will have to authenticate herself again using another password.

(14) The experiments (implemented on Raspberry Pis) show that the new MSS-based TOTP systems provide appealing efficiency gains (in Section IV). The RSA-based system cuts down authentication latency and energy consumption by 12 and 20 times, respectively, compared to a traditional RSA-based system. Additionally, the elliptic curve ElGamal (ECElGamal) based system reduces authentication latency and energy consumption by 2 and 3 times, respectively, compared to traditional ECElGamal/ECDSA/EC-Schnorr-based system. The ECElGamal-based system also reduces authentication latency and energy consumption by 82 and 792 times, respectively, compared to a recent TOTP system based on hash chains (with client storage of first hash of each week) but requires double the password size.

(15) Also presented is an asymptotic analysis of MSS's efficiency in Section V. MSS can be used in place of hash chains and reduces their online timespace complexity from O (N) to O (polylog(N)) where N is the number of signatures. Further shown is that the ECElGamal implementation allows us to reduce the offline time to O (polylog(N)) using specifics of the ECElGamal signature scheme. Section VI presents a formal proof of the security of MSS, by defining an incremental forgery game and showing that the attacker cannot win the game (break the system) provided the underlying scheme (RSA or Elliptic Curve) is secure. Section VII presents some concluding remarks.

II. MSS Via Mergeable Signatures

(16) In this section, described is a new signature scheme, MSS (Mergeable Stateful Signatures). MSS allows a client to authenticate herself to a single server efficiently multiple times typically spread over different transactions/times. As mentioned above, the assumption that the receiver is always the same party allows maintaining state across multiple signatures which allows improving efficiency.

(17) A. Signature Preliminaries

(18) Digital signatures are fundamental objects from cryptography. Formally, a signature scheme consists of three algorithms (KeyGen, Sign, Verify) satisfying the syntax: KeyGen takes a security parameter as a unitary input and generates a key pair (vk, sk); Sign takes sk and a message as input and outputs a signature ; Verify takes a message/signature pair and vk as input and outputs a bit indicating whether the signature is valid.

(19) Additionally, the two properties correctness and security must hold. Correctness says that for all messages msg, if (vk, sk)KeyGen(1.sup.n) and Sign(msg, sk), then Verify(vk, msg, )=1. Intuitively, security demands that without possession of the secret key, nobody can produce a valid signature for a new message. Formally proved is the security of MSS in Section VI.

(20) In the main construction, MSS, builds on top of signature schemes which support a special malleability property which is called mergeability. MSS has mergeable signatures for modularity. By abstracting (e.g., defining or characterizing) the main part of the construction so it builds on top of a general intermediate primitive, by which the system is able to concretize MSS based on several different cryptographic assumptions (e.g., RSA, BLS, or even Lattice assumptions). This property mergeability is the same as that of homomorphism. Roughly speaking, a signature scheme is mergeable if two message/signature pairs (msg.sub.1, .sub.1) and (msg.sub.2, .sub.2) can be merged to obtain a new message/signature pair (msg*, *). This operation must also be invertible in the sense that given (msg*, *) and (msg.sub.1, .sub.1) one can recover (msg.sub.2, .sub.2). In example embodiments, it is important that this must be a public operation, so it does not require knowledge of the secret key. Security demands that without the secret key, nobody can produce a valid signature on a new message even one that can be created by merging together two (or more) message/signature pairs which they have already seen signed.

(21) Formally, a signature scheme (KeyGen, Sign, Verify) is mergeable if there exist two additional algorithms Merge and Reconstruct (Merge, Rec) which both take two message/signature pairs (msg.sub.1, .sub.1), (msg.sub.2, .sub.2) as input and output a message/signature pair (msg*, *). Moreover, in example embodiments, two additional properties may hold: 1) Merge and Rec are inverses of each other; and 2) if the input signatures are valid then so is the merged signature. Formally, (1) requires that (msg.sub.2, .sub.2) equals
Rec((msg.sub.1,.sub.1),Merge((msg.sub.1,.sub.1),(msg.sub.2,.sub.2))).
Property (2) requires that if Verify(vk, msg.sub.i, .sub.i)=1 for i=1, 2, then
Verify(vk,msg*,*)=1 where (msg*,*) is one of {Merge,Rec}((msg.sub.1,.sub.1),(msg.sub.2,.sub.2)).
The reader may wish to keep in mind the example
Merge((msg.sub.1,.sub.1),(msg.sub.2,.sub.2))=(msg.sub.1.Math.msg.sub.2,.sub.1.Math..sub.2).

(22) This will essentially be the case in both of the constructions (MSS on RSA and on elliptic curve Bonch-Lynn-Shacham, BLS) with the precise meaning of multiplication (.Math.) customized for each cryptographic assumption.

(23) B. MSS Overview

(24) FIGS. 1A-1C provided an overview of how MSS operates. Instead of signing a message string all at once, the MSS scheme/protocol uses pre-computed signatures of representative random strings for each bit of (a hash of) the message. So as a starting (flawed) example, suppose the message hash h is -bits long, and the scheme had chosen pairs of random strings, {r.sub.i,0, r.sub.i,1}.sub.i=1, . . . , , (which are made public) and individually signed each string obtaining signatures {.sub.i,0, .sub.i,1}.sub.i=1 . . . , .sub. (which are kept private). Now each pair of signatures is mapped to a bit location to represent signatures on its bit values (i.e., 0 or 1). Then one could sign a message by sending the signatures which correspond to the bits of h. So, for example, if h=101, the signature would be (.sub.1,1, .sub.2,0, .sub.3,1) such that .sub.3,1 represents the signature on the value of the third digit in h, which is 1. Note that in this naive implementation, signing a single message requires signing multiple random strings and sending multiple signatures, thus sign time, signature size and verification time are drastically increased. On the other hand, the signer can precompute the .sub.i,b's, b{0, 1}, once during a setup phase and reuse them every time she signs a message, thus obtaining a scheme with very fast online sign-time. The main problem is that this naive scheme will not be secure since if an adversary sees many messages signed, she will eventually learn all of the .sub.i,b's and be able to sign new messages by herself.

(25) To fix this problem with security, mergeable signatures are used rather than sending all of the representative signatures in the clear (which is inefficient and insecure), the system merges them into a single signature. For security reasons, the system also merges in a signature on a fresh random nonce (which can be generated offline). So to summarize, the random representative strings and their signatures (two for each bit) are computed one time during setup, then several nonces and nonce signatures are computed offline and stored. Then once this data is in place, all the client has to do to compute the signature is merge together several of the signatures she has already computed. In the instantiation of mergeable signatures, the merge algorithm is much faster than the signing algorithm. Thus, the online cost of signing a message in MSS is greatly reduced.

(26) MSS makes online time/offline time/space tradeoffs available to the signer; while the signer needs to have one nonce signature ahead of time to achieve fast online signing for the next message, she typically would store a number of nonce signatures at a time (e.g., computed when idle/charging, or replenished periodically from a trusted proxy that is assigned the offline computation) as shown in FIGS. 1A-1C.

(27) C. MSS Via Mergeable Signaturesthe Main Contribution

(28) In this section, the main contribution MSS is built assuming a general mergeable signature scheme. In order to make authentication efficient for devices with small computational power as previously mentioned, analyzed is MSS in the online/offline model of Even, Goldreich and Micali. In this model, the Sign algorithm is split into two algorithms (Sign.sub.off, Sign.sub.on) representing the offline and online procedures. The syntax is that Sign.sub.off takes sk (but not the message to sign) as input and produces output ; Sign.sub.on takes (sk, msg, ) and outputs the signature . Ideally, Sign.sub.on should be significantly more efficient than Sign.sub.off. The intended use case is that Sign.sub.off is run offline before the message to sign is known to allow considerable speed and energy advantages for the online signing procedure.

(29) Assume (KeyGen, Sign, Verify, Merge, Rec) to be a mergeable signature scheme, let H be a hash function modeled as a random oracle and let N be a length parameter. In example embodiments, MSS consists of, or includes, four algorithms (KeyGen, Sign.sub.off, Sign.sub.on, Verify) and supports signatures on -bit messages. In the following, it is assumed that verification keys are included as part of the signing keys (this saves some syntax since it prevents us from having to explicitly pass the verification keys to the signing algorithms). Allowed is Merge and Rec to take many inputs rather than just two, without loss of generality: it can repeatedly apply the two-input version.

(30) TABLE-US-00003 Algorithm 1: KeyGen{acute over ()}(1.sup.n) 1: (vk; sk) KeyGen(1.sup.n); 2: Initialize two 2 arrays B, initialized with random strings, and , empty; also initialize U = [ ] an empty list; 3: Set = B.map (r .fwdarw. Sign(sk; r)); 4: Output (vk{acute over ()}; sk{acute over ()} = (vk; B; U); (sk; ));

(31) TABLE-US-00004 Algorithm 2: Sign{acute over ()}.sub.off (sk{acute over ()}) 1: Choose a random nonce r.sub.$ and set .sub.$ Sign(sk, r.sub.$); where vk, sk are part of sk{acute over ()} 2: Output {acute over ()} = (r.sub.$, .sub.$);

(32) TABLE-US-00005 Algorithm 3: Sign{acute over ()}.sub.on(sk{acute over ()}, msg, {acute over ()}) 1: Parse msg = b.sub.1 . . . as bits, and parse {acute over ()} = (r.sub.$, .sub.$); 2: Set (r, ) = Merge({(r.sub.j,b.sub.j , .sub.j,b.sub.j )}.sub.j, (r.sub.$, .sub.$)); r.sub.j,.sub.b.sub.j B and .sub.j,b.sub.j 3: Output {acute over ()} = (r, );

(33) TABLE-US-00006 Algorithm 4: Verify{acute over ()} (vk{acute over ()} , msg, {acute over ()}) 1: Parse msg = b.sub.1 . . . and {acute over ()} = (r, ); 2: Compute (r.sub.$, .sub.$) = Rec ({(r.sub.j,bj , .sub.j,b.sub.j)}.sub.j, (r, ); if r.sub.$ U ,reject and exit; This means the nonce r.sub.$ was used previously 3: U.push(r.sub.$) 4: Output Verify(vk, r, ) = 1

(34) Some remarks on Algorithm 1-4 are as follows: 1. Notice that the offline signing algorithm, Sign.sub.off, signs a random string, while the online algorithm, Sign.sub.on, calls Merge. For all of the mergeable schemes, built in are subsequent sections, Merge will be significantly more efficient than Sign. 2. The list U represents some persistent state maintained by the verifier over time. The purpose is to keep track of all nonces (the r.sub.$ values) used so far to force the signing algorithm to choose a fresh nonce for each new signature. This is important for security. 3. Note that the runtime of Sign.sub.on grows with since it requires merging +1 signatures together. Thus the system is most efficient when is small.

(35) Mergeable signatures are, in fact, not hard to find. Two very common signature schemes can be used, RSA signatures and BLS (or, a discrete log/elliptic curve based scheme with a formal security proof) signatures, and both support Merge and Rec operations (see sections below). The security of the construction is analyzed in Section VI.

(36) Mergeable Signatures via RSA

(37) The arithmetic for the RSA signature scheme takes place modulo a composite integer N=pq which is the product of two primes. The scheme works as follows. KeyGen(1.sup.n): draws N=pq and e according to the RSA distribution, computes d=e.sup.1 (mod (N)) (using its knowledge of p and q, and here (N) is Euler's totient function: (N)=(p1)(q1)) and outputs (vk, sk) where vk=(N, e) and sk=(N, e, d); Sign msg, (N, e, d): let r=msg (mod N) and output =r.sup.d(mod N); Verify (N, e), msg, : computer r=msg (mod N), if .sup.e=r (mod N) output 1, otherwise output 0.

(38) The Merge and Rec algorithms for RSA are modular multiplication as follows:
Merge((r.sub.1,.sub.1),(r.sub.2,.sub.2))=(r.sub.1r.sub.2,.sub.1.sub.2)
Rec((r.sub.1,.sub.1),(r.sub.2,.sub.2))=(r.sub.1r.sub.2.sup.1,.sub.1.sub.2.sup.1) Note that if vk=(N, e) and (.sub.1, .sub.2) are valid signatures on messages (r.sub.1, r.sub.2), then .sub.i.sup.e=r.sub.i (mod N) holds for i=1, 2. Therefore, if
(r,)=Merge((r.sub.1,.sub.1),(r.sub.2,.sub.2))=(r.sub.1.Math.r.sub.2,.sub.1.Math..sub.2)
Then
.sup.e=(.sub.1.Math..sub.2).sup.e=.sub.1.sup.e.sub.2.sup.e=(r.sub.1.Math.r.sub.2)=r and so is a valid signature of r.
Mergeable Signatures Via BLS

(39) The arithmetic in BLS scheme takes place in a cyclic group G with generator g that is equipped with a pairing map e: GG.fwdarw.G.sub.T for another group G.sub.T (called the target group) such that e(g, g)1 and e(g.sup.a,g.sup.b)=e(g,g).sup.ab for all integer exponents a, b. The syntax of the scheme is as follows: KeyGen(1.sup.n): draws G and g, and draws a random exponent x, and outputs (vk, sk) where vk=(G, g, g.sup.x) and sk=(G, g, x); Sign msg, (G, g, x): put r=msg and output (r, r); Verify (G, g, g.sup.x), msg, : parse =(r, r); check that (g, g.sup.x, r, r) is a DDH tuple, if so output 1, otherwise output 0.

(40) The Merge and Rec operations here are also based on multiplication:
Merge((r.sub.1,.sub.1),(r.sub.2,.sub.2))=(r.sub.1r.sub.2,.sub.1.sub.2).
Rec((r.sub.1,.sub.1),(r.sub.2,.sub.2))=(r.sub.1r.sub.2.sup.1,.sub.1.sub.2.sup.1)

(41) Similar to RSA, the mergeability can be verified as follows. If vk=(G, g, gr) and (, ) are valid signatures on messages then .sub.i=(r.sub.i, r.sub.i.sup.x) holds for i=1, 2. Therefore, if
(r,)=Merge(r.sub.1,.sub.1),(r.sub.2,.sub.2)=(r.sub.1.Math.r.sub.2,.sub.1.Math..sub.2)
Then
=.sub.1.Math..sub.2=(r.sub.1.Math.r.sub.2,r.sub.1.sup.x.Math.r.sub.2.sup.x)=(r.sub.1.Math.r.sub.2),(r.sub.1.Math.r.sub.2).sup.x) therefore, when the verification algorithm parses as (r, r) and checks whether e(g.sup.x, r)=e(g, r), it passes. This is because, e(g.sup.x, r)=e(g.sup.x,r.sub.1.Math.r.sub.2)=e(g,(r.sub.1.Math.r.sub.2).sup.x).

III. MSS Application: Time Based One Time Password (TOTP) Systems

(42) Two factor authentication and similar techniques have been introduced to combat user password weaknesses. Several hardware tokens (e.g., YubiKey) are used today as second factor authenticators, which rely on standard bidirectional communication based challenge-response authentication. As it is becoming more popular to use devices such as IoT devices as second factor authenticators, it might be the case that such devices are offline or have only one-way communication (e.g., from second factor device to authenticating device); in such case, systems such as Duo fall back to one-time password implementations (e.g., D. M'Raihi et al. Hotp: An hmac-based one-time password algorithm. Tech. rep. 2005, which is hereby incorporated by reference). In these implementations, however, the next password stays valid until the next authentication (which could be a long time); this makes it subject to various attacks such as phishing. Time-based OTP (TOTP) systems mitigate this issue by assigning each authentication time period tp a different password, and thus limiting the password window-of-use and protecting users from such attacks.

(43) Hash chains have been proposed to implement TOTP systems that do not share secrets with the server while providing time/space tradeoffs for user efficiency (refer to Section V for hash chain authentication). Assuming N represents the hash chain-TOTP system lifespan, a standard choice of parameters indicates N2.sup.21 (lifespan of roughly 2 years), with each hash in the chain representing half a minute; nonetheless, their timespace complexity is O(N), which is expensive for constrained users and servers. MSS can provide attractive properties (in terms of time and space) compared to hash chains (see Section V for details).

(44) In this section, implemented is a MSS based TOTP protocol, which goes through setup and authentication phases (FIG. 2). It allows the device's online authentication algorithm to rely on only lightweight (i.e., non-cryptographic) operations in order to produce/verify a TOTP for a tp. The RSA-based implementation of the protocol significantly speeds up signing at the online time, compared with traditional RSA while the ElGamal-based implementation improves the efficiency of verification by taking advantage of the merging construction for BLS. Optimizing verification is important for situations where the constrained devices are verifiers (e.g., smart locks). Although ElGamal-based signatures are similar to BLS-based ones in that they are both implemented in discrete-log groups, they lack security proof. Nearly all of the arithmetic used in BLS carries over to the ElGamal setting, so the implementation here is thought of as morally as an implementation of the scheme MSS. The discrepancy here is in some sense unavoidable: had the applicants worked with ElGamal signatures in Section II and VI, the applicants may not have been able to prove rigorous security since even the basic ElGamal scheme has no security proof. Likewise, to implement the exact BLS-based protocol may cause the results have given an unfair advantage because base BLS signatures are so much slower than base ElGamal.

(45) A. RSA-based TOTP System

(46) a) Setup: Whenever a client wishes to use a TOTP system as a means for authentication, it has to first go through a one-time setup so that both nodes are configured with proper keys using the steps of KeyGen described in Algorithm 1. The client defines B: ={r.sub.i,bZ.sub.N|i[1, d], b{0, 1}} that represents all the bit values, where every rib is randomly chosen. The client computes the set of bit signatures , which contains Sign(sk, r) for each rB, where Sign works as Sign described below. Next, it shares the tuple (B, vk, st) with the server, where st denotes the initial time to use the system. b) Authentication: Whenever the client wants to authenticate itself, it uses st to infer the current authentication time period tp represented in binary (i.e., tp{0, 1}.sup.d with some pre-agreed on encoding of the time). The authentication procedure is described in Algorithm 5, for which details are as follows: Defines {circumflex over (B)}={r.sub.i,bB[1,d], b{tp.sub.i}} and *={.sub.i,b|i[1,d],b{tp.sub.i}}; Draws a nonce r.sub.$ and computes H(vk, r.sub.$), GCD(H(vk,r.sub.$),r)=1 for all r{circumflex over (B)} to avoid signature overlap; Computes nonce signatures as .sub.$Sign.sub.off(sk,r.sub.$)=H(vk, r.sub.$).sup.sk,d mod N and sets :={.sub.$} Runs {circumflex over ()}Sign.sub.on(sk,tp,.sub.$,r.sub.$)=.sub..sub.i.sub.**.sub.i*mod N It then sends the TOTP tuple (r.sub.$, {circumflex over ()}) to authenticate itself.

(47) TABLE-US-00007 Algorithm 5: Authentication 1: Sign.sub.off (arg.sub.1, arg.sub.2); 2: {circumflex over ()} Sign.sub.on(sk, tp, .sub.$, arg.sub.3); Server runs Verify( ) 3: if Verify(vk, tp, {circumflex over ()}, arg.sub.3) = 1 then 4: ACCEPT; 5: else 6: REJECT; 7: end if

(48) Upon receipt of the TOTP, the server infers the same tp from its own clock and the shared st to avoid accepting void TOTPs that might have been stolen/replayed. In order to verify whether the received TOTP is legitimate, it does the following: Creates a verification subset {circumflex over (V)}:={circumflex over (B)}{H(vk,r.sub.$)}; Runs Verify(vk,tp,{circumflex over ()},r.sub.$), which checks if the following equation holds .sub.v{circumflex over (V)}(v)=.sup.?{circumflex over ()}.sup.vk.Math.e mod N;

(49) If successful, the client is authenticated. c) Efficiency and Overhead: In order to avoid communicating nonces r.sub.$ during authentication, both nodes can be configured to derive unique and coprime nonces using a pseudorandom function (e.g., r.sub.$.sup.i=H (counter)). Since, in TOTP systems, tp increases over time and that the client uses its TOTP generation algorithm only once in each time-interval, tp can be used by both nodes to also derive the nonces {r.sub.$}.sub.i (e.g., r.sub.$.sup.i=H(tp)) without loss of security; this releases the server from keeping state in memory as well as allows both nodes to avoid communicating such nonces over the network during authentication. The enhancement in Jurjen N. Bos and David Chaum. Provably Unforgeable Signatures. In: CRYPTO. Springer, 1992, which is hereby incorporated by reference, can also be used in the present case to reduce the size of signature set and bit value set B to halfparticularly important for edge devices with limited storage; instead of explicitly dealing with values representing 0 for each different digit, assumed is the presence of 1 implies absence of 0 and vice versa. This allows clients to store signatures corresponding to values representing 1 for all digits only, namely ={.sub.i,1}.sub.i[1,d]. Similarly, the server only keeps values representing 1 for all digits, namely B={r.sub.i,1Z}.sub.i[1,d]. It can also use one set of coprime values representing different bits (i.e., the set B) for all clients in the system. Clients can also store only one key of the key pair, preferably vk since the recommended size of the public verification exponent vk.Math.e{0, 1}.sup.17 is smaller than the private signing exponent sk.Math.d{0, 1}.sup.0.292-|N|, and derive one key from the other as needed.
B. ECElGamal-Based TOTP System

(50) In several DDH-based signatures (e.g., ECDSA), the most expensive part of the signing operation can by design be done offline; however, signature verification still has to incur at least 2 exponentiations in the critical online time, which can be expensive for a limited-resource verifier (e.g., a smart lock). The MSS-based ECElGamal construction allows us to replace one of the exponentiations with only a few multiplications (e.g., 21 multiplications for a 2-year TOTP system), thus reducing online verification time significantly. a) Setup: When the instantiation of Algorithm 1 is done using ECElGamal signatures, the output key pair is (sk=(G, g, x), vk=(G, g, xg)); where g is the public base point for the elliptic curve, sk.Math.x[2, N1] is a secret random scalar and vk.Math.xg is a point on the elliptic curve G. In the second step, B is chosen in such a way which guarantees that the overlap amongst signatures of different authentication times is avoided. Hence, the following constraint: .sub.r*B.Math.(r*).sub.rB(r), B.Math.BB must be satisfied. Therefore, selected is B={r.sub.i,b=.sup.e mod N|iI=[1, d], bJ={0, 1}, Z.sub.N, e[1, |I|.Math.|J|]}, where N is a large prime determining the order of an elliptic curve group. KeyGen in this case is the same as the one in Algorithm 1 except that the client sends (B, vk, st) to the server and the server computes the last step of KeyGen as =B.Math.map (r.fwdarw.gr). b) Authentication: This procedure follows the same protocol described in Algorithm 5 and the three procedures (Sign.sub.off, Sign.sub.on and Verify) are computed as follows. The signature of tp (current time to authenticate) consists of the tuple (.sub.$, {circumflex over ()}). Similar to normal ECElGamal signatures, .sub.$=(x.sub.1, y.sub.1) is a point on the curve calculated by .sub.$=Sign.sub.off (r.sub.$, g)=r.sub.$g, where r.sub.$[2, N1] is an integer nonce that is coprime with the modulus N (i.e., GCD(r.sub.$, N)=1) so that it has a multiplicative inverse r.sub.$.sup.1 that will be needed to calculate the second part of the signature; r.sub.$ must be unique and random for each signature to prevent A from recovering sk. In order to compute any .sub.$, only needed is the set P={ag:a{2.sup.0, . . . , 2.sup.log(N)-1}} pre-computed and stored in memory.

(51) In order to calculate {circumflex over ()}, the client creates the subset {circumflex over (B)}={r.sub.i,bB}.sub.ie[1,d].Math.be{tpi} that contains the digit values corresponding to its current authentication time period tp. It then runs {circumflex over ()}Sign.sub.on(sk, tp, .sub.$, r.sub.$) which outputs the second part of the signature, {circumflex over ()}=r.sub.$.sup.1(.sub.r{circumflex over (B)}(r)sk.Math.x.Math..sub.$.Math.x.sub.1)mod N. It communicates the TOTP tuple (.sub.$, {circumflex over ()}) to authenticate itself. The server now creates a signature verification subset {circumflex over ()}={circumflex over (B)}.Math.map(r.fwdarw.gr), which contains already computed values (at setup) corresponding to tp; it then runs the procedure Verify(vk, tp, .sub.$, {circumflex over ()}) to check the validity of .sub.$.Math.x.sub.1vk.Math.xg+{circumflex over ()}.sub.$=?.sub.v{circumflex over ()}v. c) Efficiency and Overhead: The technique mentioned earlier that suggests keeping values corresponding to 1 only for all digits is also applicable here (i.e., and B). Since .sub.$ is independent of tp, it can be calculated and sent ahead of time, allowing the server to calculate part of the left side of the verification equation apriori, namely .sub.$.Math.x.sub.1vk.Math.xg; thus, the only expensive operation left for signature verification becomes {circumflex over ()}.sub.$. This approach enables the TOTP system to be faster in the online authentication time. It also allows clients to send only half the signature at the critical time of authentication, namely {circumflex over ()}{0, 1}.sup.|N|. NIST suggests that elliptic curves with |N|=256 can provide 128-bit security; if this recommendation is followed, the system can have clients send only 256-bit TOTP tokens at the online authentication time. The server can also use one set of values representing the different digits (i.e., ) for all clients to avoid per user storage.
C. Other Considerations a) Offline Second Factor Authentication: The systems require one-way communication, which makes them a good fit for offline second factor authenticators. Mechanisms facilitating communication of TOTPs generated by offline devices (e.g., a refrigerator with a screen) can be used in the systems (e.g., QR encoding). FIG. 3 illustrates an example system model for edge devices using the new TOTP systems for offline second factor authentication. b) Clock Synchronization: Similar to standard TOTP systems, the systems require synchronized clocks at the client and server. Natural delay between the time of generating a TOTP at the client and the TOTP verification at the server can cause authentication failure. The server can allow a small window of time skew (e.g., 30 seconds before the current time) and thus can verify the received TOTP accordingly, as used in standard TOTP systems.

IV. Implementation and Evaluation

(52) Implemented was a prototype of the RSA and ECElGamal-based TOTP systems. For comparisons with counterparts, implemented are TOTP systems that rely on SHA-256-based 1-dimensional hash chains (referred to as 1D/1DHC), RSA-based multi-dimensional hash chain (MDHC), traditional ECElGamal, ECDSA, EC-Schnorr and traditional RSA with full domain hash (RSA-FDH). RSA is used with 3072-bit modulus, and all elliptic curve cryptography (ECC)-based signatures use the NIST P-256 curve.

(53) A. Experimental Setups

(54) The experiments were taken for TOTP systems that had a lifespan of 2 years (i.e., 2.sup.21 TOTPs). They were done on a constrained Raspberry Pi Zero W (RPi), with a single-core 1.0 GHz CPU and 512 MB RAM, and a laptop, with a dual-core 3.0 GHz CPU and 16 GB RAM. The client and server play the role of the TOTP generator and the TOTP verifier, respectively. The setups include: a laptop and a RPi (e.g., a smart lock scenario); a RPi and a laptop (e.g., a smart watch scenario); and two RPis (e.g., a car gate scenario). Referred to is the first and last hash in a chain as head and tail, respectively. Hash chain based authentication is described in Section V. RSA public exponents (used for verification or hashing) were set to size 17 bits. In case of 1DHC, the server constantly replaces its tail with the hash used at last successful authentication. Also considered is a case where the client already has in storage hashes across the chain that correspond to the beginning of each month/week, which helps expedite calculating any target hash in the chain. Also noted is that in this implementation, a simpler SHA hash is also used as in the scheme of D. Kogan, N. Manohar, and D. Bonch. T/Key: Second-Factor Authentication From Secure Hash Chains. In: CCS. ACM, 2017, which is hereby incorporated by reference. Also proposed and evaluated is a MDHC-TOTP system with 21 dimensions (referred to as 21D), with each dimension being 2 hashes long so as to offer 2.sup.21 possible TOTPs and decrease the chain diameter (i.e., make the number of hashes smaller, although the system may have to use a commutative hash such as RSA). All ECC-based systems calculate the first part of the signature before knowledge of next tp.

(55) B. Performance and Overhead Analysis

(56) Discussed is the performance and overhead of the TOTP systems and the other alternatives, with focus on the online authentication phase. The authentication phase is broken down into two sub-tasks: (1) Generation of a TOTP at the client side, which is generating a target hash in the chain for hash chains, and a signature for the rest of the schemes; and (2) Verify of the TOTP at the server side, which is checking if the received TOTP can hash forward to the tail for hash chain-based schemes, or verifying a signature for the other schemes.

(57) FIG. 4 demonstrates that the MSS-based ECElGamal-TOTP system reduces latency to complete authentication compared to the following alternatives as follows: RSA-FDH (158 reduction), 1DHC (best case with client storing hashes of every week beginnings, 82), MDHC (41) and traditional ECElGamal/ECDSA/EC-Schnorr systems (2), respectively for the IoT to IoT scenario. The other proposed RSA-TOTP system also cuts down authentication latency by 12, 6 and 3 times compared to alternatives based on RSA-FDH, 1DHC (with client hash storage as in the previous case), and MDHC, respectively. Even though computations required at the client can be reduced in TOTP systems based on 1DHC by keeping some hashes along the chain as shown in the results, the server cannot use this technique and keep such hashes since this reveals future passwords and makes them susceptible to theft in case of server compromise attacks, necessitating the full chain traversal.

(58) FIG. 5 shows the energy consumption for each scheme (measured using a power meter). The MSS-based ECElGamal-TOTP system provides energy savings of a factor of 1572, 792, 243 and 3 compared to its alternatives: RSA-FDH, 1DHC (with client hash storage as in the previous case), MDHC and traditional ECElGamal/ECDSA/EC-Schnorr systems, respectively. The MSS-based RSA-TOTP system also reduces energy consumption by 20, 10 and 3 times compared to RSA-FDH, 1DHC (with client hash storage as in the previous case) and MDHC TOTP systems, respectively.

(59) Table III (below) shows the parameters kept at each node and amount of storage needed for them across all systems. Since online-offline signature schemes keep parameters that are pre-processed offline, they require more storage than traditional signature schemes. As an optimization to traditional ECEl-Gamal, ECDSA, EC-Schnorr and the ECElGamal, during setup pre-compute the system may store different bases P that allow such schemes to generate 2 nonce signatures using only O(log N) storage where N is the total number of signatures in the life of system. For all elliptic curve schemes (including the new ECElGamal), the client side requires more storage than other systems based on hash chains and RSA; however, this storage is still less than 16 KBytes which is reasonable for modern IoT devices given the saving in power and computational delay. The server storage requirement is reduced by 4 and 2 compared to MDHC and RSA-FDH, respectively. The ECElGamal outperforms traditional ECElGamal, without requiring extra storage at the server side while requiring only a few extra bytes at the client. The new RSA system improves on traditional RSA, but underperforms the simpler hash and EC based systems. However, since it offers formal security proof (not available in ECDSA, EC-Schnorr or ECElGamal), it may be of interest to high assurance applications.

(60) TABLE-US-00008 TABLE III Storage for TOTP systems. Storage (bytes) TOTP Client Server System Size Param. Size Param. RSA-FDH 391 st, vk.N, vk.e 388 st, vk.N 1D, 31, st, salt, 31 st, salt, tail 1D mo. sto., 409, head, hashes 1D wk. sto. 1705 MDHC (21D) 817 st, vk.N, {vk.e.sub.i}.sub.i, head 772 st, vk.N, head New RSA 8839 st, vk.N, vk.e 388 st, vk.N, ', .sub.$ New 16513 st, sk.x, r.sub.$.sup.1, 196 st, vk.xg, ECElGamal .sub.$.x.sub.1, B, P vk.xg .Math. .sub.$.x.sub.1, .sub.$ ECElGamal 16484 st, sk.x, r.sub.$.sup.1, 196 st, vk.xg, .sub.$.x.sub.1, P vk.xg .Math. .sub.$.x.sub.1, .sub.$ ECDSA 16484 st, sk.x, r.sub.$.sup.1, 100 st, vk.xg, .sub.$ .sub.$.x.sub.1, P EC-Schnorr 16516 st, sk.x, r.sub.$, .sub.$, P 68 si, vk.xg

V. Asymptotic Efficiency of MSS

(61) In this section, analyzed is MSS's time and space complexity in comparison to hash chains. MSS provides similar functional properties to hash chains and can be used in any context where hash chains are applied. First provided is an analysis of hash chains to be able to provide a baseline. Show is that MSS reduces the timespace complexity from O(N) to O(polylog(N)).

(62) Given a hash function H, a hash chain (FIG. 6) is a list of vertices {v.sub.0, . . . , v.sub.N} where each v.sub.i is obtained by hashing the value before it (i.e., v.sub.i is labeled by a string x.sub.i such that x.sub.i+1=H(x.sub.i) holds for all i). The first vertex v.sub.0 is called the head of the chain, v.sub.N is the tail. The labels in a hash chain can be computed in the forwards direction (i.e., given x.sub.i one can compute x.sub.i+1