Pairing Crypto Protocols

M-Pin Protocol - Introduction

The genesis of the M-Pin Protocol was first put forward in a research paper by Dr. Michael Scott in 2002 2.

The M-Pin Protocol has been iterated on several times over the years since, to develop three distinct modes, which will be explored in the following sections.

The M-Pin Protocol is intended to replace the well-known Username/Password authentication mechanism which is widely considered to be effectively broken.

The main problem is the existence of a password file on the server, which is commonly stolen and hacked, revealing most user passwords.

The idea behind M-Pin is that each registered client is issued with a secret cryptographic key derived from their identity. They then prove to a server that they are in possession of this key using a zero-knowledge proof protocol, which can be extended to include authenticated key agreement.

This protocol design eliminates the need for any information related to clients, or their keys, to be kept on the authentication server.

Common to both Chow-Choo and M-Pin is that the keys are issued in shares, not as whole keys, by the Distributed Trust Authorities. Only the clients, who receive all of the shares from the D-TA's, will ever know the completed whole keys.

Industry commentators have long advocated a multi-factor solution. The novel feature of M-Pin and Chow-Choo is that the cryptographic secrets issued to clients or peers may be safely split up into any number of independent factors.

Each of these factors has the same form; they are points on an elliptic curve. To recreate the original secret, they are simply added together again -- it's as simple as that.

One factor might be derived from a short 4-digit PIN. Another might be a token conveniently stored in an authenticator app on a smartphone.

Classic two-factor solutions are in fact often hierarchical and two-level. A key generated from one factor is used to unlock the other.

Disjointed technologies are used by each factor. Typically a password (or a biometric) might be used to unlock an authentication key stored in a file.

Strictly speaking, this solution is only one factor, as it is only this authentication key that is required, and an attacker would be satisfied if they could obtain this without knowing the password.

However since this is probably not possible, we accept that the overall effect is two-factor authentication.

Software encryption might be used as the locking mechanism, but since a brute force attack will discover the authentication key, the password must become a large hard-to-remember pass-phrase.

The alternative (which achieves the same functionality as two-factor M-Pin) is to lock the authentication key into a secure hardware vault. Now a short PIN can be used to unlock it.

However, secure hardware is expensive and may not be supported on all devices. Another downside of this classic approach is that the extension to multi-factor authentication is not at all obvious.

As noted in Milagro Crypto Concepts, the M-Pin Protocol exploits:

  • Elliptic Curve Cryptography
  • Pairing Based Cryptography
  • Identity Based Encryption
  • Zero Knowledge Proof

Because of the characteristics that M-Pin inherits from the four techniques above, the M-Pin Protocol and its variants are able to deliver:

  • Multi-factor authentication (MFA) using Zero Knowledge Proof
  • Authenticated Key Agreement
  • Distribution, or splitting, of Trust Authorities
  • Subliminal Channel Communication3

The three modes of operation of the M-Pin Protocol are as below. All are fully protected against  MITM (man in the middle) attacks and KCI (Key Compromise Impersonation)  attacks:

  • M-Pin 1-pass: Client to server authentication via digital signatureof a time-stamp.
  • M-Pin 2-pass: Client to server authentication via an interactive zero knowledge proof.
  • M-Pin FULL: Mutual client to server authentication via an interactive zero knowledge proof, and able to drive an Authenticated Key Agreement between client and server, resulting in 128 bit shared secret key.

Note that the M-Pin Full Authenticated Key Agreement possesses the quality of perfect forward secrecy (PFS), meaning, even if the client and server long term keys are compromised, the past session keys (used to encrypt TLS traffic, for example) are not compromised.

Chow-Choo Protocol - Introduction

The Chow-Choo Protocol was developed by Sherman S.M. Chow and Kim-Kwang Raymond Choo and published in 2007 via a research paper titled Strongly-Secure Identity-based Key Agreement 4. The Chow-Choo Protocol can be technically described as an identity-based key agreement protocol.

The Chow-Choo Protocol is of these classifications and exploits the features of:

  • Elliptic Curve Cryptography
  • Pairing Based Cryptography
  • Identity Based Encryption

Because of the characteristics that Chow-Choo inherits from the three techniques above, the Chow-Choo Protocol can deliver:

  • Multi-factor authentication (MFA) using Zero Knowledge Proof
  • Authenticated Key Agreement
  • Distribution, or splitting, of Trust Authorities

Note that the Chow-Choo Protocol is not a Zero Knowledge Proof protocol, and is not able to deliver a Subliminal Channel capability.


Table 1. PROTOCOL RECOMMENDATIONS
Protocols | Use Cases -------|------- M-Pin 1-Pass | Digital signature authentication in battery or bandwidth constrained environments such as IoT devices, embedded applications and mobile apps.
This should be considered the default implementation for client to server authentication suitable for almost all use cases. M-Pin 1-Pass +
M-Pin 2-Pass | Digital signature and client to server authentication in smartphones apps, desktop browsers and software applications. M-Pin 2-Pass | Client to server authentication in smartphone apps, desktop browsers and software applications. M-Pin FULL | Mutual client and server authentication with authenticated key agreement for use in smartphone apps, hardware and software applications.
Authenticated Key Agreement with PFS can be used as the basis for TLS sessions between clients and servers. Chow-Choo | Mutual peer to peer authentication with authenticated key agreement for use in smartphone apps, hardware and software applications.
Authenticated Key Agreement with PFS can be used as the basis for TLS sessions between clients and servers and peer to peer.

Protocols In Depth

The Milagro framework protocols rely on Distributed Trust Authorities to issue shares, or fractions, of Type-3 Pairing keys to Milagro Crypto Apps, such as the Milagro MFA server and clients, or to software or hardware applications that have embedded Milagro code in order derive the functional capabilities.

These clients or peers become the only entities that know the completed whole keys assembled from shares (fractions) issued by different Distributed Trust Authorities.

As outlined in the previous section, Type-3 pairings were selected as they are the most efficient pairing and will work with non-supersingular pairing-friendly curves.

These operate as $G_1$ x $G_2 \rightarrow G_T$, where $G_2$ is a particular group of points, again of the order $q$, but on a twisted elliptic curve defined over an extension which is a divisor of $k$.

These curves can be constructed to be a near perfect fit at any required level of security 1. The pairing protocols within the Milagro framework all work on a Type-3 pairing.

One of the novel aspects of pairing-based cryptography is that deployed secrets are commonly represented as points on an elliptic curve, which are the result of multiplying a known point by a master secret $s$.

So for example a secret might be of the form $sP$, where $P$ is known.

There are a number of interesting things we can do with secrets that have this form, that are not possible with the secrets that arise when using other cryptographic technologies.

For example they can be split into two, into $s_1P$ and $s_2P$ where $s=s_1+s_2$ and $sP = s_1P +s_2P$.

In fact they can be just as easily split into multiple parts, just like chopping up a cucumber.

We can also add extra components to create a secret of the form $s(P_1+P_2) = sP_1+sP_2$.

It is the flexibility that arises from this form of the secret that allows us to introduce the idea of chopping off a tiny sliver of the secret to support a PIN number.

It also facilitates the concept of Time Permits as discussed in a later section.

Lastly, it enables Distributed Trust.

Distributed Trust Authorities

A Trusted Authority will be in possession of a master secret $s$, a random element of $F_q$.

A client secret is of the form $s.H(ID)$, where ID is the client identity and $H(.)$ a hash function which maps to a point on $G_1$.

From prior art, we assume that $H$ is modelled as a random oracle where $H(ID) = r_{ID}.P$

where $r_{ID} \in F_q$ is random and $P$ is a fixed generator of $G_1$.6

The server will be issued with $sQ$, where $Q$ is a fixed generator of $G_2$.

Note that this will be the only multiple of $s$ in $G_2$ ever provided by the TA. Servers will always be associated with their own unique master secrets.

Note that the TA functionality can be trivially distributed using a secret sharing scheme, to remove from the overall system a single point of compromise or coercion.

In the simplest possible case there may be two Distributed Trusted Authorities (D-TAs), each of which independently maintains their own share of the master key.

So $s=s_1+s_2$, and each D-TA issues a part-client key to the client $s_1 H(ID)$ and $s_2 H(ID)$, which the client, after receiving the shares, adds together to form their full key.

Now even if one D-TA is compromised, the client key is still safe.

NOTE: As discussed in the 'Distributed Trust Ecosystem Proposal', the Milagro Project has put forward a proposal to create an ecosystem whereby any participant can run independent Distributed Trust Authority services.

M-Pin 1-Pass

As opposed to Chow-Choo, which can be used in a client to server as well as a peer to peer setting, M-Pin is strictly a client-server protocol.

To embellish the security of the client-server protocol, it is important that client and server secrets should be kept distinct.

A simple way to do this is to exploit the structure of a Type-3 pairing and put client secrets in $G_1$ and the server secret in $G_2$ as noted in the preceding section.

For a Type-3 pairing there is assumed to be no computable isomorphism between these groups, even though both are of the same order.

In the original implementation, the client was supplied with a challenge by the server as part of the second step within the protocol, after the first step whereby the client announced her identity to the server.

In a later proposal, it was realised that an M-Pin 1-Pass Protocol could be obtained if the client itself derived the challenge as $y$ as $y=H(U|T)$ where $T$ is a time-stamp transmitted by the Client along her claimed identity, $U$ and $V$.5.

The protocol could then be reduced in an obvious way to a secure 1-pass protocol. However, this assumes that the Server checks the accuracy of the time-stamp before completing the protocol.

This all works thanks to the pairing function $e(.,.)$ and its remarkable bilinearity property $e(aP,Q) = e(P,aQ) = e(P,Q)^{a}$.


Figure 1. M-Pin 1-Pass
Alice - identity $ID_a$ Server
Generates random $x<q$
$A=H(ID_a)$
$U=x{A}$
$ID_a$, $U~~ $
$y=H(U|T)$
$V=-(x+y){((s-\alpha)A+\alpha A)} \rightarrow$
$A=H(ID_a)$
$g=e(V,Q).e(U+yA,sQ)$
if $g \ne 1$, reject the connection

M-Pin 2-Pass

As you can see below in Fig 2., M-Pin in two pass mode operates in a challenge (from the Server) to client, who responds to the challenge. This implementation obviates the need for synchronised clocks, at the cost of of a full roundtrip.


Figure 2. M-Pin 2-Pass
Alice - identity $ID_a$ Server
Generates random $x<q$ Generates random $y<q$
$A=H(ID_a)$
$U=x{A}$
$ID_a$, $U~~ \rightarrow $
$\leftarrow y$
$V=-(x+y){((s-\alpha)A+\alpha A)} \rightarrow$
$A=H(ID_a)$
$g=e(V,Q).e(U+yA,sQ)$
if $g \ne 1$, reject the connection

M-Pin Full

This more elaborate protocol not only replaces Username/Password, but replaces the functionality of digital certificates being utilised to drive key agreement for TLS or VPN protocols.

Our starting point is the M-Pin protocol as described above.

The idea is to run it first (to authenticate the client to the server), and then proceed to authenticate the server to the client via an authenticated key exchange, which also establishes the agreed key of 128 bits.

This protocol requires another general hash function $H_g(.)$ which serializes, and hashes its input to a 256-bit value. Both sides can then extract a key from this value $K$.

It is left as a simple exercise for the reader to confirm that both client and server end up with the same key.

Note that since the first part of the protocol is just the original M-Pin protocol, all of its features and extensions still apply.

This protocol was deliberately designed to reduce client-side computation to a minimum.


Figure 3. M-Pin FULL
Alice - identity $ID_a$ Server
Generates random $x<q$ Generates random $y<q$
$A=H(ID_a)$
$U=x{A}$
$ID_a$, $U~~ \rightarrow $
$\leftarrow y$
$V=-(x+y){((s-\alpha)A+\alpha A)} \rightarrow$
$A=H(ID_a)$
$g=e(V,Q).e(U+yA,sQ)$
if $g \ne 1$, reject the connection
$R=r{A} \rightarrow $ $\leftarrow W=w{A}$
$h=H(A,U,y,V,R,W)$ $h=H(A,U,y,V,R,W)$
$K=H_g((g_1.{g_2}^\alpha)^{r+h} | x{W})$ $K=H_g(e(R+hA,sQ) | w{U})$

Chow-Choo Protocol

As initially proposed, the Chow-Choo Protocol was based on a type-1 pairing. A type-1 pairing operates as $G_1 \times G_1 \rightarrow G_T$, where $G_1$ is a group of points of prime order $q$ on the curve, and $G_T$ is a finite extension field of the same order, whose extension is the so-called embedding degree $k$ associated with the curve.

In the Milagro framework, the Chow-Choo Protocol is made to work in a Type-3 setting.

Pairings are usually written as functions of the form $g=e(A,B)$, where $A \in G_1$, $g \in G_T$, and for a Type-1 pairing $B \in G_1$ and for Type-3 $B \in G_2$.

Consider now an application of this protocol to an imagined Internet of Things (IoT) setting.

Each Thing is issued with a serial number and its own Chow-Choo key (which can double as an M-Pin Key) based on that serial number as an identity.

These keys may be embedded at the time of manufacture, by the manufacturer acting as a naturally trusted authority.

When a Thing needs to communicate with another Thing, an action which requires knowing only the identity of the other, both parties can activate the Chow-Choo Protocol to calculate the same key to encrypt their communication.

For both sending and receiving, Alice is issued with $sA_1$ and $sA_2$, where $A_1=H_1$ and $A_2=H_2$ both in the $ID = Alice$.

Similarly Bob is issued with $sB_1$ and $sB_2$. Now if Alice initiates and Bob responds, Alice calculates the key as $e(sA_1,B_2)$ and Bob can calculate the same key as $e(A_1,sB_2)$, where by convention the initiator uses their sender key and the responder uses their receiver key.

One thing we can exploit -- in any communication context there is an initiator and a responder, or a sender and receiver, if you will.

In the above example, Alice and Bob both were issued sender and receiver keys respectively, as this describes where they can appear in the pairing.

An obvious advantage is to issue each Thing with two keys, one in $G_1$ and the other in $G_2$, if the Thing is approved to send and receive.

However, the capability exists to cryptographically bound Things to only receive information, or only send information, based upon whether or not a Thing has been issued a sender and / or a receiver key.

This capability is exploited in the Milagro framework to enable peer to peer authenticated key agreement.


Figure 4. Chow-Choo Protocol
SENDERRECEIVERxq*AG1:=H1(IA)PaG1:=xAG1IA,PaG1y,wq*AG1:=H1(IA)BG2:=H2(IB)PbG2:=yBG2PgG1:=wAG1pia:=Hq(PaG1PbG2PgG1IB)pib:=Hq(PbG2PaG1PgG1IA)k:=e(piaAG1+PaG1,(y+pib)BG2)K:=H(k,wPaG1)IB,PgG1,PbG2BG2:=H2(IB)pia:=Hq(PaG1PbG2PgG1IB)pib:=Hq(PbG2PaG1PgG1IA)k:=e((x+pia)AG1,pibBG2+PbG2)K:=H(k,xPgG1)

Notes on Chow-Choo Protocol:

* $G_1$: a $r$-order cyclic subgroup of $E(F_p)$. * $G_2$: a subgroup of$E(F_{p^k})$, where $k$ is the embedding degree of the Curve. * $H1$: Maps string value to a point on the curve in $G_1$. * $H2$: Maps string value to a point on the curve in $G_2$. * $Hq$: Hashes inputs to an integer modulo the curve order $q$. * H(): Hash function. * $||$: denotes the concatenation of messages.

For additional information, the reader is encouraged to download the following research papers from MIRACL LABS (LINK TO PAPERS).

## REFERENCES

D. Freeman and M. Scott and E. Teske. A taxonomy of pairing-friendly elliptic curves. Journal of Cryptography. 2010. Pages 224 -- 280. Volume 23. M. Scott. Authenticated ID-based Key Exchange and remote log-in with simple token and PIN number. Cryptology ePrint Archive, Report 2002/164. http://eprint.iacr.org. C. Boyd and A. Mathuria, Protocols for Authentication and Key Establishment, Springer-Verlag, 2003. Chow, S.S.M., Choo, K.-K.R.: Strongly-Secure Identity-based Key Agreement and Anonymous Extension. Cryptology ePrint Archive, Report 2007/018. Chow, S.S.M., Choo, K.-K.R.: Strongly-Secure Identity-based Key Agreement and Anonymous Extension. Cryptology ePrint Archive, Report 2007/018. N. Smart and F. Vercauteren. On Computable Isomorphisms in Efficient Pairing-based Systems. Discrete Applied Mathematics. Volume 155. Pages 538--547. 2007.