Internet DRAFT - draft-scott-mpin
draft-scott-mpin
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]