Download nicolosi:2schnorr.pdf

Contents : Proactive Two-Party Signatures for User Authentication Antonio Nicolosi Maxwell Krohn Yevgeniy Dodis and David Mazi eres NYU Department of Computer Science nicolosi max dodis dm @cs.nyu.edu Abstract We study proactive two-party signature schemes in the context of user authentication. A proactive two-party signature scheme (P2SS) allows two parties--the client and the server--jointly to produce signatures and periodically to refresh their sharing of the secret key. The signature generation remains secure as long as both parties are not compromised between successive refreshes. We construct the first such proactive scheme based on the discrete log assumption by efficiently transforming Schnorr's popular signature scheme into a P2SS. We also extend our technique to the signature scheme of Guillou and Quisquater (GQ) providing two practical and efficient P2SSs that can be proven secure in the random oracle model under standard discrete log or RSA assumptions. We demonstrate the usefulness of P2SSs (as well as our specific constructions) with a new user authentication mechanism for the Self-certifying File System (SFS) 28 . Based on a new P2SS we call 2Schnorr the new SFS authentication mechanism lets users register the same public key in many different administrative realms yet still recover easily if their passwords are compromised. Moreover an audit trail kept by a secure authentication server tells users exactly what file servers an attacker may have accessed-- including even accounts the user may have forgotten about. may have the right to initiate signatures of arbitrary messages while a server's role is simply to approve and log what has been signed. In such settings an attacker may gain fruitful advantage from the use of even a single key share unless some separate mechanism is used for mutual authentication of the two parties. Finally ordinary two-party signatures offer no way to transfer ownership of a key share from one party to another--as the old owner could neglect to erase the share it should no longer be storing. Proactive digital signatures allow private key shares to be updated or "refreshed" in such a way that old key shares cannot be combined with new shares to sign messages or recover the private key. While a number of proactive signature protocols have been constructed most existing protocols are threshold schemes designed for a variable number of parties. Because these threshold schemes require a majority of participants to be honest they do not scale down to only two parties. This paper describes 2Schnorr a proactive signature protocol specifically designed for two parties. 2Schnorr is an efficient protocol that is easy to implement and produces digital signatures compatible with the Schnorr 32 signature scheme. In the random-oracle model a three-message version of 2Schnorr is provably secure against existential forgeries assuming only that discrete logs are hard. For applications with bounded concurrency such as user authentication a two-message version can also be proven secure under the stronger one-more-discrete-log assumption. The technique we describe is equally applicable to the GuillouQuisquater (GQ) 20 signature scheme producing twoand three-message 2GQ protocols based on the RSA and one-more-RSA inversion problems respectively. We will concentrate on 2Schnorr however as 2GQ is completely analogous. P2SS signatures have a natural application to the problem of user authentication particularly for settings with many administrative realms. Within a large university for example it is not uncommon for a user to have five or six different shell accounts on machines in separate research groups. On the web users typically establish accounts at dozens of different sites over time. Under such circumstances a user whose private key or other credentials get 1. Introduction Until now little attention has been given to proactive twoparty signature schemes (P2SSs). In an ordinary two-party signature scheme a private key is split between two parties both of whom must approve and participate in the signing of messages. An attacker must compromise both parties to forge signatures on its own. However the attacker has the entire lifetime of the public key to compromise each of the two parties. Moreover particularly in the two-party case the parties' roles may be asymmetric--for instance a client This research was sponsored by the Defense Advanced Research Projects Agency (DARPA) and the Space and Naval Warfare Systems Center San Diego under contract N66001-00-1-8927. compromised is unlikely to remember every place at which he needs to update his login information. Some of the sites may even be unavailable at the time the user tries to update them at which point the user may just give up on the problem until the next time he needs one of the accounts. Using 2Schnorr we built a user-authentication mechanism that addresses these challenges for SFS 28 . SFS is a secure global file system in which users gain transparent access to files from many different administrative realms after logging in with a single password. With the new authentication mechanism every user has an ordinary Schnorr public signature key on file wherever the user has an account. The corresponding private key is split between the user and an authentication server of the user's choice. If the user's password is ever compromised he can immediately block further unauthorized access to all of his accounts by updating his password and private key halves on this single authentication server. Moreover from the server's logs the user can determine exactly what servers an attacker has accessed where on the network those accesses came from and whether the attacker has changed the user's login information at any sites. Thus even accounts the user may have forgotten about will be brought back to his attention if there is any risk of an attacker having accessed them. The next section describes SFS and related work in user authentication and proactive signature schemes. Section 3 describes the 2Schnorr protocol and gives a proof of security. Section 4 describes the implementation of our userauthentication mechanism in SFS. Section 5 reports on the performance of 2Schnorr and our user-authentication scheme. Section 6 concludes. simultaneously access servers in multiple realms. The SFS client itself has no notion of belonging to a particular realm. (In fact SFS has no client-side configuration options that would differentiate one client from another.) Users simply access files based on whatever realms they belong to. If a user accesses a file on a server the client has never heard of an "automounting" mechanism causes the file to spring into existence before the access completes. SFS users have public signature keys which they register with any realms in which they have accounts. User authentication consists of digitally signing an authentication request with the corresponding private key. Each user runs a program sfsagent that attempts to authenticate her to every file server she accesses. In this way by registering the same public key in every administrative realm a user can transparently access files from multiple realms without worrying about administrative boundaries. Unfortunately if a user's private key is ever compromised the user may have to update her public key in a large number of realms. The mechanism described in this paper makes it considerably more difficult to compromise a user's key. SFS comes bundled with a remote execution utility rex with similar functionality to the popular ssh 37 . Between the file system and rex any SFS user authentication mechanism can cover a large fraction of the day-to-day network accesses people make to their servers. 2.2. User Authentication Of widely used network file systems SFS's goals are probably most similar to those of AFS 22 . AFS is a file system designed to work over the wide-area network. AFS has been particularly successful in large organizations--for instance permitting the user community of an entire university to share access to the same file systems. Unfortunately AFS does not adapt as well to settings with many different administrative realms. AFS's security is based on the centralized Kerberos 33 authentication system in which a central authority manages all of the accounts and servers in a given administrative realm. Cross-realm authentication is possible but requires cooperation from realm administrators. Thus users must typically type a separate password for each realm in which they wish to access servers. Since the central Kerberos server stores a secret that is effectively equivalent to the user's password it is inadvisable for users to have the same password in different Kerberos realms. The SSH remote login tool supports a mode of authentication based on public keys. The user registers his private key with an agent process on the local machine and stores the corresponding public key in a file .ssh/authorized keys in his home directory on the server. SSH public key authentication is very convenient. Users therefore typically end up copying their authorized keys file to all of their different accounts. Unfor- 2. Related Work A vast number of systems have dealt with the problem of user authentication. This section describes SFS and the motivation for a new SFS user authentication mechanism. We then highlight a few other systems that have tackled user authentication on a large scale. Finally we discuss related work in cryptography. 2.1. SFS Overview SFS is a secure network file system designed for decentralized control and easy sharing of files across organizational boundaries. In SFS's administrative model servers are grouped into administrative realms that recognize the same set of authorized users. Realms can be as large as an entire campus or as small as a single server behind a DSL line. While a simple mechanism allows one realm to "import" or recognize users from another realms in general need not trust each other coordinate with each other or even know of each other's existence. Each SFS user may have accounts in many different administrative realms. From a single client machine users can tunately changing public keys requires many accounts to be updated and users are likely to forget to update accounts on infrequently used machines. Perhaps most relevant to P2SS are the various hardwarebased user-authentication systems. As smart cards and other physical security devices gain more computational power it will become increasingly practical for them to compute digital signatures. Such configurations will be even more desirable if they can keep an audit trail of all signed messages in case the device is stolen or otherwise compromised. P2SS schemes enable such scenarios while additionally allowing users to recover from compromised devices without changing their public keys. To compromise a user's public key permanently an attacker would need to break the user's hardware device (or steal a backup of the user's share) and compromise the centralized signature server before the user had an opportunity to recover from the first event. 2.3. Related Cryptography Related work in cryptography includes proactive cryptosystems two-party signature schemes and in particular several specialized two-party signature schemes designed to remain secure under various models of device compromise. Proactive signatures. Basic multi-party signature schemes remain secure only as long as a sufficient number of parties remain uncompromised. Unfortunately the longer the lifetime of a public key the more realistic the threat that enough parties will be compromised to render the public key completely insecure. Proactive cryptosystems 29 21 address the problem by allowing a potentially unbounded number of compromises so long as not too many of them happen simultaneously. Specifically there is an efficient share update protocol which allows parties to refresh the way in which they share the secret key. As long as a bounded number of servers are compromised between any two successive refreshes the system remains secure. Most proactive signatures are threshold schemes which assume an honest majority of players. Such schemes only function in the case of n 3 players. In fact most threshold techniques and even definitions (e.g. robustness) are inapplicable to the two-party setting. Two-party signature schemes. Building an ordinary two-party signature scheme is trivial. Given a secure one-party signature algorithm let the client and server -1 each generate its own key pair--call them Kc Kc and -1 Ks Ks respectively. The two-party public key then consists of the two public keys Kc Ks . A two-party signature of a message m just consists of two independent sig-1 -1 natures of m using Kc and Ks . The first signature can only be produced by the client and the second only by the server. Most previous work on two-party signatures has therefore focused on the problem of generating signatures that are compatible with existing one-party algorithms. Such twoparty schemes allow systems to interoperate with verifiers that cannot be updated to understand new signature types. While 2Schnorr and 2GQ are the first two-party schemes compatible with Schnorr and GQ they are hardly the first schemes to interoperate with standard one-party algorithms. Bellare and Sanhdu 6 and MacKenzie and Reiter 26 consider several flavors of two-party generation of the RSA (full domain hash) signatures (building on some previous less formal work e.g. 10 18 ). The schemes are simple elegant and in most cases reducible to the basic RSA assumption. MacKenzie and Reiter 27 also give a protocol for two-party generation of DSA signatures 16 . Two-party signatures can also be viewed as a special case of general secure two-party computation 36 . Resisting compromise. Two-party signatures are also related to the notion of key-insulated signature schemes 13 . In this model a server helps the client update its secret key from period to period. Though public keys remain the same across updates signatures reflect the period in which they were created. Thus a verifier can reject signatures produced in periods during which the client was known to be compromised. Within a given period the client performs all signatures on its own. This has the advantage of not requiring the server's cooperation on each signature but for our application we specifically want all signatures to go through the server for approval and logging. Involving the server on each signature also allows for immediate recovery from a compromised password without the need to notify all verifiers of compromised periods. Recent work of Itkis and Reyzin 24 on intrusionresilient signatures combines the properties of key-insulated and proactive signatures. However as in the key insulated model the server only helps the client update its secret key from one time-period to the next all the signing is done by the client alone. In the P2SS model the actual secret does not change from one time period to the next only the sharing of the secret changes. The most closely related work was proposed in 25 where MacKenzie and Reiter extend their schemes from 26 to allow for delegation of password-checking services. Their paper describes a protocol for a novel hardware-based user-authentication mechanism. In their model the server is almost stateless the device contains a password protected private key yet an attacker who captures the device cannot mount an off-line password guessing attack. By contrast the authentication system described in this paper assumes a stateful server and is designed to work with stateless clients--as in the case of a user with only a password who wants to sit down at a new workstation and access all of her files. Embedded in the MacKenzie and Reiter protocol is actually a fully general-purpose P2SS version of RSA. We believe that their RSA algorithm could be used to build a user-authentication system similar to the one described in this paper. Similarly our 2Schnorr and 2GQ schemes could replace RSA within their protocols. We note however that in the case of RSA proactivization costs some efficiency because of the need to employ techniques from 17 to share the secret exponent over a much larger modulus than (n). In both 2Schnorr and 2GQ the share update protocol is very simple: a client simply sends a random element of an appropriate group to the server over a secure channel. Of course this does not mean that proactivization is generally simple in the two-party case. Indeed there seems to be no way to "proactivize" the trivial double signature two-party scheme. The question of generic proactive two-party signatures is not as trivial as in the non-proactive case. Other than the two-party RSA scheme in 25 previous two-party signatures do not appear to "proactivize" in as simple a manner as 2Schnorr and 2GQ. 3. The 2Schnorr Signing Protocol This section specifies the 2Schnorr signing protocol and analyzes its security. Like the standard Schnorr signature scheme 2Schnorr relies on a cryptographic hash function H which for the proofs we will assume behaves like a random oracle (a common assumption in cryptographic research first formalized in 4 . Before going into the details of 2Schnorr we briefly describe the standard Schnorr scheme. The Schnorr signature scheme 31 was first proposed as an application of the Fiat-Shamir transformation 14 . It can be instantiated on any group G of prime order in which the discrete log problem is believed to be hard. Schnorr has been proven secure under the standard notion of existential unforgeability against an adaptive chosen-message attack 19 in the Random Oracle Model. The security has been analyzed among other places in 32 30 . For concreteness we will consider cyclic subgroups of Z p (for large primes p) of prime order q . The key generation algorithm produces two large primes p and q such that q (p - 1) and an element g in Z p of or and sets der q . Then it picks a random element x in Z q y g x mod p. The public key is p q g y while the corresponding private key is x. The group parameters p q g can be safely shared between a community of users so that y by itself can be thought of as the public key corresponding to private key x. Schnorr additionally relies on a cryptographic hash function H mapping arbitrary strings to elements of Z q . We will assume H has been specified as a parameter of the scheme. To sign a message m the holder of the private key x picks k a random k Z q and sets r g mod p. It then computes e H (m r) s k + xe mod q and outputs the signature r s . Note that k must be kept secret and chosen anew each time disclosing or reusing the value of k would allow recovery of the secret key x. To check whether a given r s is indeed a signature for some message m it suffices to know the corresponding public key p q g y and verify that g s ry e mod p where e H (m r). 2Schnorr is a simple two-party proactive variation of the above scheme. We call the two parties the client and the server. We assume the client is the party that wants the digital signature--it starts with the message and ends with the signature. The server simply wants to log or approve all signed messages. The main issue in generalizing Schnorr to two parties is that if one party say the server could control the choice of one of the secret quantities x or k or their public counterparts y and r then the server would gain an advantage over the client and the resulting scheme might not be secure. Fortunately the parties need only agree on random values a task usually referred to as coin flipping 8 . This can be implemented by first having each party choose a random share then exchanging and combining the shares to produce the agreed upon value. Of course the two parties might not reveal their shares simultaneously. To prevent the second party say the server from choosing its share after learning the client's the server can first "commit" to its share then "open" the commitment upon receiving the client's share. The simplest commitment scheme for a random share r is to reveal G(r) for some hash function G that behaves like a random oracle. The client cannot learn anything from G(r) but will be able to check r's consistency at the end of the exchange. G need not be a random oracle however. Any "extractable" commitment scheme will do (for instance "committing" encryption 12 which can be implemented without random oracles). However since Schnorr relies on random oracle H anyway G might as well be a random oracle too. Note further that G and H take inputs of different lengths and thus will never be evaluated on the same input. An implementation can therefore use the same cryptographic hash function--e.g. SHA-1 15 --for both H and G. We remark that the use of extractable commitment to chose randomness in Schnorr and GQ generalizes to other probabilistic signature schemes in which the security result depends on honestly chosen public randomness (e.g. PSS 5 PFDH 11 ). Key generation. A 2Schnorr public key is just an ordinary Schnorr public key p q g y . However the corresponding Schnorr private key x is split between two key halves xc and xs such that x xc + xs (mod q ). A public 2Schnorr key can be centrally generated along with two halves for the corresponding private key as follows: q a large prime p a larger prime such that q (p - 1) g an element of Z p of order q xc xs random elements of Zq y g (xc +xs ) mod p The two private key halves are xc and xs . For distributed key generation between the client and server the client chooses p q g and xc computes yc g xc mod p and sends the server p q g G(yc ) . The server then picks xs and sends the client ys g xs mod p. Finally the client reveals yc both parties compute y yc ys mod p and the public key is p q g y . To prevent the client from (maliciously) choosing "bad" group parameters 7 the server may require the client to prove it has generated the values p q g according to some specific algorithm. In the implementation described in Section 4 we use the method proposed by the NIST in 16 for which such a proof can be easily provided. Signature generation. To sign a message m the client and the server each select a random element of Zq --kc for the client ks for the server. The two parties then exchange the three messages shown in Figure 1. First the server picks at random an ephemeral private key ks from Z q computes the corresponding ephemeral public key rs g ks mod p and sends G(rs ) (message 1). Similarly the client computes its ephemeral key pair kc rc and sends the second flow of the protocol consisting of the value G(rs ) it got in message 1 its ephemeral public key rc and the message m it wishes to sign. Upon receiving message 2 the server checks that rc belongs to the group specified by p q and q mod p 1 then computes g by verifying the equality rc r rc rs mod p e H (m r) ss ks + xs e mod q and replies with message 3 which reveals the value of rs . The client computes G(rs ) and verifies that it matches the value received in message 1 if so it verifies rs and computes sc in a way analogous to that described above for ss . Finally the client sets s sc + ss mod q and obtains the pair r s --an ordinary Schnorr signature. The protocol in Figure 1 requires three messages. The first message can be precomputed and sent to the client in advance reducing network latency to a single round trip from the time the client receives the message to be signed. As discussed later however a system with a constant bound on the number of concurrent signatures requested by the client can simply eliminate the first message of the protocol (and remove G(rs ) from the second message). The resulting two-message protocol may be more convenient to implement. Signature verification. Signature verification is identical to Schnorr. Given a public key p q g y a message m and a signature r s the signature is valid if and only if g s ry e (mod p) where e H (m r). It can be easily checked that signatures obtained from an honest execution kc Z q rc g kc mod p r rc rs mod p sc kc + xc e mod q s sc + ss mod q 1 2 3 R ks Z q rs g ks mod p e H (m r) ss ks + xs e mod q R G( r s ) G(rs ) rc m rc r s s s Client Server Figure 1. message client. ks nature is 2Schnorr signature protocol. m is the being signed. kc is chosen by the is chosen by the server. The final sigr s . of the signing protocol do indeed verify correctly. Key update. The aim of key updates is to tolerate multiple compromises of each party. Clearly any adversary that compromises both parties between two successive key updates will learn the entire state of the system and completely break the security of the public key. However the system should be able to withstand multiple break-ins as long as one honest key update happens in between. Key updates are considerably simpler in the two-party case than in general proactive signatures. Since either party can already destroy the private key by erasing its own share there is no need to preserve the private key when the client or server misbehaves. Further simplifying the problem our update protocol assumes a secure channel between the client and server because our system already requires such a channel for other purposes. (Otherwise the client and server could use a 2Schnorr signature as part of negotiating a secure channel.) To update the key halves xc and xs the client picks a random Zq and sends it to the server over a secure channel. The new key halves xc and xs are simply computed as: xc xc - mod q xs xs + mod q This update algorithm is not only simple but also quite effective in completely re-randomizing the state of the system thus simplifying the arguments for the security proofs in the following subsections. GQ signatures. The Schnorr signature scheme is often studied together with the GQ scheme its "twin" based on the RSA assumption. The two can be thought of as variations of the same basic theme. Semantically the difference between the two is that in Schnorr all secrets are drawn from the additive group Zq and their public counterparts are obtained by exponentiation on a fixed base with GQ

INFO HASH : 40a0beb202420470df378ce915a624d6a5e5a211

Download now

File Size: 199 kb