[Search] [pdf|bibtex] [Tracker] [Email] [Nits]

Versions: 00                                                            
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


   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

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

   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",
   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


   Client ---------> Server


   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

   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-

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
   Dublin 3

   Email: mike.scott@miracl.com

   Brian Spector
   81 Rivington Street
   London EC2A 3AY

   Email: brian.spector@miracl.com

   Go Yamamoto

   Email: yamamoto.go@ntti3.com

Scott                    Expires: June 3, 2016                  [Page 8]