Internet-Draft M. Scott, B. Spector Intended Status: Informational MIRACL Ltd. Expires: June 3, 2016 G. Yamamoto NTT Innovation Institute Inc. December 3, 2015 M-PIN: Zero-Knowledge two-factor authentication for digital identity draft-scott-mpin-00 Abstract In this document, the M-PIN protocol for authentication of digital identity is described. This protocol identifies a Client to a Server. M-PIN requires an external Trusted Authority to issue secrets to participating Clients and Servers. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." This Internet-Draft will expire on June 3rd, 2016. Copyright Notice Copyright (c) 2015 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as Scott Expires: June 3, 2016 [Page 1] Internet-Draft M-PIN December 3, 2015 described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2 2. Requirements Notation . . . . . . . . . . . . . . . . . . . . . 3 2.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Abbreviations . . . . . . . . . . . . . . . . . . . . . . . 3 2.3 Conventions . . . . . . . . . . . . . . . . . . . . . . . . 3 3.0 The M-PIN protocol . . . . . . . . . . . . . . . . . . . . . 4 3.1 System setup and Client registration . . . . . . . . . . . . 4 3.2 Client Identification . . . . . . . . . . . . . . . . . . . 5 3.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . 5 4. Security Considerations . . . . . . . . . . . . . . . . . . . . 6 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 7 6. References . . . . . . . . . . . . . . . . . . . . . . . . . . 7 6.1 Normative References . . . . . . . . . . . . . . . . . . . . 7 6.2 Informative References . . . . . . . . . . . . . . . . . . . 7 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 8 1. Introduction Client Identification is a cryptographic protocol whereby a Client securely identifies itself to a Server. Traditionally this has been achieved using a Username/Password combination, with the passwords stored in encrypted form on the Server. Typically the Server is itself responsible for enrollment and registration of Clients. This widespread method of identification has serious shortcomings. Often in the event of a security breach at the Server, the encrypted password file might be captured and from this, using standard techniques, the majority of passwords can be recovered. Since even well supported Servers appear to be incapable of protecting such password files, the only defense seems to be the use of increasingly complex passwords by Clients, which are difficult to remember. It is generally agreed that a form of multi-factor authentication provides superior protection. One manifestation is where the Client experience becomes very similar to that of extracting money from an Automated Teller Machine (ATM). This is a familiar experience in the context of a high value transaction for many people. Here the two factors required for authentication are some form of Token, and an easily memorized PIN number, typically just 4 decimal digits in length. Scott Expires: June 3, 2016 [Page 2] Internet-Draft M-PIN December 3, 2015 It is also important in the event of a Server breach that the negative consequences for the Clients should be minimized. For this reason our solution proposes the introduction of a Trusted Authority to handle enrollment and registration of Clients, and to relieve the Server of this burden and responsibility. The Server itself is only in possession of a single small secret issued to it by the Trusted Authority. Previously there was no known protocol which allowed for this type of two-factor authentication which was not open to so-called insider attacks, or off-line dictionary attacks. This has necessitated the issuance of the Token in the potentially expensive form-factor of an autonomous hardware device. The protocol proposed here can be implemented entirely in software. The token is typically just 512 bits of data. 2. Requirements Notation The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. 2.1 Definitions Two-Factor Authentication: Two-factor Authentication is a technology which allows a Client to authenticate itself via an identity string to a Server using two independent sources of data. These MUST be such that knowledge of one factor does not reveal the other factor. Any third party who obtains by whatever means one factor for a certain identity MUST NOT be able to authenticate themselves to the Server in that identity. Digital Identity: Digital Identity is the data that uniquely describes a person or a thing, and typically contains some information about that entity's relationships. 2.2 Abbreviations AES Advanced Encryption Standard TA Trusted Authority 2.3 Conventions Scott Expires: June 3, 2016 [Page 3] Internet-Draft M-PIN December 3, 2015 o E is an ordinary pairing-friendly elliptic curve over a finite field F, defined by a fixed prime modulus p. o e: G1 X G2 -> GT is a computable bi-linear map on E. G1 is defined as a group of points on E. G2 is defined as a group of points on a twist of E. Both groups are of prime order q. GT is a finite extension field of F, also of order q. o s is a large positive integer less than q, the master secret belonging to the TA and associated with a particular Server. o H is a well known hash function that converts its input into a positive integer less than q. o H1 is a well known hash function that takes the data associated with Alice's digital identity and assigns it to a point in G1, e.g. H1("Alice@example.com") = A, a point on E in G1. o D=sA is the private key computed by the TA for Alice, and delivered only to Alice. In a similar fashion private keys are issued to all other Clients of the same Server. o S=sQ is the private key computed by the TA for this Server, where Q is a fixed public point on G2. o TOKID is the Token belonging to identity ID, and PINID is the PIN chosen by identity ID. 3.0 The M-PIN protocol 3.1 System setup and Client registration The TA chooses a suitable elliptic curve and defines the groups G1, G2 and GT. To be concrete the TA chooses a standard BN curve [BN] with parameter x=-0x4080000000000001. This generates a curve with overall security equivalent to AES at the 128-bit level [AES], and which is quite efficient for computation. The TA generates a master secret s, which is reserved for use with a particular Server. The Server is issued with the secret S=sQ. This is calculated by a point multiplication in the group G2. Note that knowledge of S and Q does not reveal s, as it is protected by a known hard problem, the discrete logarithm problem. Clients such as Alice approach the TA and are issued with a secret D=sA, where A is Alice's digital identity hashed to a point in G1. Alice then chooses a PIN number PINA and calculates her token as TOKA=D-PINA.A. In effect her PIN number is subtracted from her Scott Expires: June 3, 2016 [Page 4] Internet-Draft M-PIN December 3, 2015 secret. Alice is now ready to identify herself to the Server. 3.2 Client Identification We assume that the Server is authenticated to the Client using some existing technology such as SSL [RFC6101]. This has the added benefit of encrypting the protocol exchanges, which prevents an eavesdropper from learning even the identity of the authenticating individual. The actual identification protocol is based on the work of Kurosawa and Heng [KH]. Their protocol is a single-factor zero-knowledge proof of identity. Initially the Client hashes her digital identity "Alice@example.com" to a point A using the hash function H1, and selects a random positive integer x less than q. The Client MUST use a fresh, random value of x for each run of the protocol. The Server selects a random positive integer y less than q. The Server MUST use a fresh value of y for each run of the protocol. Client --------> Server "Alice@example.com", U=xA Server ---------> Client y Client ---------> Server V=-(x+y)(TOKA+PINA.A) The Server itself calculates A by applying the hash function H1 to the claimed digital identity. Finally the Server SHALL check that e(V,Q).e(U+yA,sQ) = 1. If it is, the Client is authenticated, otherwise she is not. As described this is a 3-pass protocol. However if the Client itself derives the challenge y as y=H(U|T) (where T is a time-stamp transmitted by the Client along her claimed identity, U and V) the protocol can be reduced in an obvious way to a secure 1-pass protocol assuming that the Server checks the accuracy of the time-stamp before completing the protocol. We point out that this 1-pass variant is probably a better choice if M-PIN is to replace an existing Username/Password implementation. 3.3 Discussion o The TA with its knowledge of the master secret s represents a Scott Expires: June 3, 2016 [Page 5] Internet-Draft M-PIN December 3, 2015 potential single-point-of-failure for the scheme. However, without going into further detail, we point out here that the TA function can be distributed in a multiplicity of ways using a standard secret sharing scheme. In its simplest manifestation there might be 2 TAs, each one of which generates a part-secret (so s=s1+s2), and both of which would have to be compromised to determine the master secret. o In a similar way the Server function and server secret can also be split across multiple Servers. o Implementation considerations: An implementation of M-PIN is particularly lightweight on the Client side. Only two point multiplications in G1 are required. Indeed there is no requirement for any support for G2 or GT arithmetic. This will be fast even if carried out within a browser. On the Server side the product of two pairings can be calculated much more efficiently than two single pairings. o An implementation of M-PIN MAY use a biometric measurement either in place of a PIN number, or in conjunction with a PIN number, in which case it supports 3-factor authentication. o It is assumed that the Server will be implementing some kind of mechanism to prevent someone who does not know the PIN from attempting to guess it by making a multiplicity of authentication attempts. Such a mechanism and its implementation are outside of the scope of this draft. 4. Security Considerations Two-Factor authentication methods can be vulnerable to off-line dictionary attacks. Here an attacker might capture one authentication factor from their victim, typically the token, and then try to use this along with other information, perhaps gleaned from previously recorded protocol runs or other stolen client secrets, to determine their PIN. One manifestation of such an attack might be an "insider" attack whereby another Client Bob with his own secret might capture the token of Alice and by some efficient computation arrive at her PIN number. Another powerful attacker might be an entity which successfully breaches the security of the Server and comes away with its secret sQ. It should not be possible for such an entity to determine a Client's secret, or to authenticate to the Server in the name of a Client. However the server secret sQ is in the group G2, and therefore cannot Scott Expires: June 3, 2016 [Page 6] Internet-Draft M-PIN December 3, 2015 be used to authenticate to the genuine server, as it expects to receive from a Client only elements of G1. So we get immunity from such attacks by the expedient of implementing the Kurosawa and Heng protocol on an ordinary pairing friendly elliptic curve, such that G1 and G2 are distinct groups, albeit of the same order. This idea was first suggested in [Scott]. The XDH assumption [Scott], [BGMM] is that in the context of a pairing, that the Decisional Diffie-Hellman problem is hard in the group G1. The basic Kurosawa and Heng protocol was proven to be secure, under standard assumptions, by Bellare et al. [BNN]. Furthermore we assert that any attacker able to determine the PIN from transmitted values, a captured token and optionally other full client secrets, breaks an instance of the XDH assumption, under the additional assumption that the function used to hash digital identities acts as a Random Oracle. 5. IANA Considerations At this time there are no IANA considerations 6. References 6.1 Normative References [RFC6101] Freier A., Karlton P., Kocher P., "The Secure Sockets Layer (SSL) Protocol Version 3.0", RFC 6101, August 2011 [RFC2119] Bradner S., "Key words for use in RFCs to Indicate Requirement Levels", RFC 2119, March 1997 6.2 Informative References [AES] National Institute of Standards and Technology, "Specification for the Advanced Encryption Standard (AES)", FIPS 197, November 2001. [BGMM] Ballard, L., Green, M., de Medeiros B., and Monrose, F., "Correlation-Resistant Storage via Keyword-Searchable Encryption", Cryptology ePrint Archive, Report 2005/417 [BN] Barreto, P., Naehrig, M., "Pairing-Friendly elliptic curves of prime order", SAC 2005, LNCS 3897, Springer-Verlag (2006), pp. 319- 331. Scott Expires: June 3, 2016 [Page 7] Internet-Draft M-PIN December 3, 2015 [BNN] Bellare, M., Namprempre, C., and Neven, G., "Security proofs for identity-based identification and signature schemes", Eurocrypt 2004, LNCS 3027, Springer-Verlag (2004), pp. 268-286. [KH] Kurosawa, K. Heng, S., "From Digital Signature to ID- based Identification/Signature", PKC 2004, LNCS 2947, Springer-Verlag (2006), pp. 125-143. [Scott] Scott, M. "Authenticated ID-based Key Exchange and remote log-in with simple token and PIN number", Cryptology ePrint Archive, Report 2002/164 Authors' Addresses Michael Scott 4 Foster Place North Ballybough Dublin 3 Ireland Email: mike.scott@miracl.com Brian Spector 81 Rivington Street London EC2A 3AY England Email: brian.spector@miracl.com Go Yamamoto NTT Email: yamamoto.go@ntti3.com Scott Expires: June 3, 2016 [Page 8]