Cryptography

# From Bi-Linear Maps to Searchable Encryption

## Pairings-Based Cryptography

### Introduction

Theoretical research into pairings-based cryptography has been a well-researched area over the last few years, this cryptography scheme is based on the mapping of two cryptographical groups which allows for a new cryptographical scheme based on a trapdoor permutation between the groups with some interesting complexity properties.

These two groups are called a Gap Groups in many instances, where the Decisional Diffie-Helman problem is easy, but the Computational Diffie-Helman still is hard to solve. Weil and Tate pairings are used in implementations but requires complex mathematics, this is why in this section we will use a slightly more abstract means to explain bilinear maps..

### Bilinear Maps

Mostly all constructions of pairings-based cryptosystems use bilinear maps, for this we consider two groups $G_1$ and $G_2$ or a prime order $q$. We can denote $G_1$ using additive notation and $G_2$ using multiplicative notation, even as the group operations of $G_1$ and $G_2$ are very different, $G_1$ can also be written as a multiplicative group operation in some literature.

If we consider two generators of group $G_1$ as $\ P$ and $Q$, we can write:

$aP\ =\ P+P+\ ..P\ \}\ a$ times

Using this we can also consider a map $e$ as follows: ${e:\ G}_1\ \times G_1\ \to \ \ G_2$

This type of bilinear map has a main group $G_1$ and a shadow group $G_2$ where we map two group elements in the first group to the second group would need have properties between them in order for it to be useful,  Bilinearity, non-degenerate and computable.

Bilinearity:

For Group $G_1$ using generators $P$ and $\ Q$ we can define a map to $G_2$, where the additive operation in group $G_1$ equals the multiplicative operation in $G_2$:

$\forall P,\ Q\in G_1, \forall a,\ b\ \in {\mathbb{Z}}^*_q,$
$Map:e\left(aP,\ bQ\right)=e(P,\ Q)^{ab}$

If G1 and G2 where both multiplicative groups then the Bilinearity property would be the following:

• $\forall P,\ Q\in G_1,\ \forall a,\ b\ \in {\mathbb{Z}}^*_q,$
• $Map:e\left(P^a,\ Q^b\right)=e(P,\ Q)^{ab}$

This has an interesting property whereby it beaks the decisional Diffie-Helman problem, but this will be discussed in more details later.

Non-Degeneracy:

If all the elements map to the identity of the group then if would not have any additional computational aspects to explore. It is therefore important not to create a map with the identity of either of the groups.
$\forall P\ \in G_1,\ P\ \neq 0\ \ \left\langle e\left(P,\ P\right)\right\rangle =G_2\ (e\left(P,\ P\right)\ generates\ G_2)$
Such that: $P\ \neq 0\ \Rightarrow e\left(P,\ P\right)\neq 1$

Computability: $e$ should be efficiently computable, there are some constructions of maps that are hard to compute.

The construction of these bilinear pairs has been proven by Wei and Tate pairings, where $G_1$ is a typical elliptic curve group, and $G_2$ is a finite field. These have proven to provide complex problems across these groups to construct cryptographical schemes.

### Complex Problems

For the usage of bilinear maps in cryptographical schemes, we define a one-way function using two problems, the Decisional Diffie-Helman problem and the discrete log problem.

Theorem 1: The Discrete Log Problem in $G_1$ is no harder than the Discrete Log Problem in $G_2$.

Proof 1: If we use our additive notation and consider that $Q\ =\ aP$, we then need to solve $a$, which is random, for a given $P$ and a random $Q$
$e\left(P,\ Q\right)=e\left(P,\ aP\right)=e(P,\ P)^a$

With this we can effectively reduce the Discrete Log Problem in $G_1$ to the Discrete Log Problem in $G_2$, if we are given $P\in G_1$ and a random $Q\in G_1$ then the mapping of $e$ is easily computable by calculating ${{log}_P (Q)}$ as:

$P^=e(P,\ P)$
$Q^=e(P,\ Q)$
$a=\ {{log}_{P^} \left(Q^\right)\ in\ \ G_2\ }$
$a={{log}_P (Q)\ }\ in\ G_1$

With this we can see that the difficulty of solving the discrete log problem in both groups are the same, since the computation of ${{log}_P (Q)\ }$ have the same complexity in both groups.

Theorem 2: The Decisional Diffie-Helman is easy in $G_1$.

Proof 2: Solving the Decisional Diffie-Helman problem in $G_1$ requires distinguishing between:

$\langle P,\ aP,\ bP,\ cP \rangle \ with\ a,\ b,\ c\ \in {\mathbb{Z}}^*_q$ and
$\langle P,\ aP,\ bP,\ abP \rangle \in {\mathbb{Z}}^*_q$
If we can define $P,A,B$ and $C$ as the distinguishers four values, then the distinguisher function is as follows:

$v_1=Map:e(A,\ B)\ and\ v_2=Map:e(P,\ C)$

If we have that $v_1=v_2$, then the tuple is of type $\langle P,\ aP,\ bP,\ abP\rangle$

From this we can take $C=\ abP$ from (Theorem 1)

$e(A,\ B)=e(aP,\ bP)$
$=e(P,\ P)^{ab}$
$=e(P,\ abP)$
$=e(P,\ C)$

Since the map $e$ is non-degenerate we can set $e\left(A,\ B\right)=e(P,\ C)$ equivalent to $c\ =ab$. The distinguisher has thus a significant advantage given the mapping $e$ to decide the Decisional Diffie-Helman problem.

Theorem 3 The Bilinear Diffie-Helman Problem is easy in $G_1$ but difficult in $G_2$

Fact: If we are given two groups $G_1$ and $G_2$ with a map between them as $e$, there are no polynomial time algorithm that can compute $\left(P,\ aP,\ bP,\ cP\right)for\ \ some\ a,\ b,\ c\ \in \ {\mathbb{Z}}^*_q$ in $G_1$ given $e(P,\ P)^{abc}$ in $G_2$. With this we can construct the following properties between the groups as the following hard problems:

$e(aP,\ bP)^c\ in\ G_1=e(P,\ P)^{abc}\ in\ G_2$
$e(aP,\ cP)^b\ in\ G_1=e(P,\ P)^{abc}\ in\ G_2$
$e(bP,\ cP)^a\ in\ G_1=e(P,\ P)^{abc}\ in\ G_2$

Using these theories, we can now construct cryptosystems based on these hard problems found in these groups.

### Cryptography Schemes

Using these complexity problems, there has been an abundance of cryptosystems developed over the years, where the two most notable are the 3-party key agreement scheme, identity based encryption and searchable encryption.

#### The 3-party Diffie-Helman key agreement scheme

Joux  introduced in 2000 a three-party key agreement scheme using bilinear maps utilizing the Bilinear Diffie-Helman problem for the construction.

If we have two groups $G_1$ and $G_2$ with $P$ as a generator of $G_1$, and three parties $A,\ B,\ C$ that have respective secrets $a,\ b,\ c\ \in \ {\mathbb{Z}}^*_q$ we can construct a key agreement scheme where each party shares a secret key as follows:
$A\ \longrightarrow B,\ C:aP$
$B\ \longrightarrow A,\ C:bP$
$C\ \longrightarrow A,\ B:cP$

Using the Bilinear Diffie-Helman Problem we can define the following:

$A$ computes $e(bP,\ cP)^a=e(P,\ P)^{abc}$
$B$ computes $e(aP,\ cP)^b=e(P,\ P)^{abc}$
$C$ computes $e(aP,\ bP)^c=e(P,\ P)^{abc}$

All parties now have the same shared key $K=e(P,\ P)^{abc}\ \in G_2$ that can be used as an input to a symmetric encryption scheme.

#### Identity Based Encryption

The idea of using private information, like an email address, as a public key has been long debated and researched, whereby the corresponding private key can be delivered to the rightful owner. The role of the key generator must be to verify the private information before distributing the private key to the owner, although a public key infrastructure would solve this problem, there were substantial research into this area to move away from a trusted third party, and having the identity as part of the encryption.

In Dan Boneh’s and Franklin’s paper an Identity based encryption scheme was created to remove the public key infrastructure with the use of bilinear maps and the bilinear Diffie-Helman problem, incorporating a random oracle model. This protocol consists out of five phases:

Setup

• Defining two groups $G_1$ and $G_2$ with a bilinear map $e:G_{1\ }\times G_1\ \to \ G_2$ and $P$ as a generator
• A System wide secret key $s\in \ {\mathbb{Z}}^*_q$
• A corresponding system wide public key $P_{pub}=sP$, which are not distributed
• Public hash function $H_1:\{0,\ 1{\}}^*\ \to G^*_1$, a random oracle
• Public hash function $H_2:G_2\ \to \{0,\ 1{\}}^n$ for some fixed $n$, the second random oracle.
• The message space $\mathcal{M}=\{0,\ 1{\}}^n$
• The cypher space $C=G^*_1\ \times \{0,\ 1{\}}^n$

To create a private key for a corresponding participant for $ID\in \{0,1{\}}^*$ the system computes:

$Q_{ID}=H_1(ID)$ and
$d_{ID}=\ {sQ}_{ID}$ which is the private key that can be distributes to the user.

Encryption:
If we are now given a message $m\ \in \mathcal{M}$ we can compute the cyphertext as follows:

• $Q_{ID}=H_1\left(ID\right)\in G^*_1$
• We then choose a random $r\in \ {\mathbb{Z}}^*_q$
• We can now compute $g_{ID}=e\left(Q_{ID},\ P_{pub}\right)\in G_2$
• And create the cyphertext: $c=(rP,\ m\oplus H_2(g^r_{ID}))$

Decryption:

When the user receives the cyphertext, he has $c=(u,\ v)\in C$ and can decrypt it using his corresponding private key $d_{ID}$ and $H_2$

$m=v\oplus H_2(e(d_{ID},\ u))$

The main reason that both encryption and decryption works are because of the properties of pairings and the mask generated by $H_2$ that is xor’ed with the plaintext. We can prove the correctness by using simple substitution from the parameters above:

$m=v\oplus H_2(e(d_{ID},\ u))$
$m=v\oplus H_2(e(sH_1(ID)\ ,\ rP))$
$m=v\oplus H_2(e(H_1(ID)\ ,\ P))^{rs}$
$m=v\oplus H_2(e(Q_{ID}\ ,\ sP))^r$
$m=v\oplus H_2(e(Q_{ID}\ ,\ P_{pub}))^r$
$m=v\oplus H_2(g^r_{ID}$)
$m=(m\oplus H_2 (g^r_{ID}))\oplus H_2(g^r_{ID}))$

$=m$

This scheme provides us a way to use the identity as a parameter within the encryption and decryption without the use of a third party. The usage of identity is important, as this can bind the encryption and decryption to a owner of the keys.

## Searchable Encryption

Searchable encryption schemes are a well-studied topic, and there have been several constructions using order revealing and order preserving schemes. For the a simplified construction a protocol I have chosen to use an order revealing encryption schemes based on bilinear maps, this construction  is proven to be secure against adaptively chosen keyword attacks assuming the bilinear Diffie-Helman problem is intractable using the random oracle model.

To use this construction , we will look at the following scenario:

For this scenario, we need to define four entities that will be involved in the scheme:

• Users (1..n): responsible for the creation of messages that are sent to a trusted party for routing. These messages are sent and received via a secure channel to the messaging server.
• Third Party / Message Server: The messaging platform, that routes messages to users, and that can test weather a certain list of keywords are present in the message.
• Legal Authority (1..n): The party interested in searching the message data.
• Trusted Third Party: a Party responsible for securing the private key

Suppose a Legal authority needs to be alerted when certain keywords are transmitted to a messaging server. For example, a user sends a message to another user that he is planning a bombing, the “bombing” needs to create an alert on the messaging server, and the legal authority needs to be sent a encryption of the message thread.

If the messages between the users are encrypted using semantic means, then the messaging server cannot make any alerting decisions as it cannot decrypt the messages. Our goal here is to ensure that the messaging server provide a way to test whether a keyword has been transmitted between the users, without revealing the content of the messages. This can only be achievable by the legal authority providing a list of keywords to the message server that can be used, as well messaging server needs to have access to both the encryption and decryption key of the user’s messages.

To do so, a user encrypts messages between users and messaging server using a standard public key cryptosystem and saves it in his database. The messages are appended with a Public-Key Encryption with keyword Search (PKS) of each keyword. For example, User Steve sends Peter a message $M$ with words $W_1$, $W_2..W_m$, then the trusted messaging server create:
$E_{A_{pub}}(Message)\ \parallel PKS(A_{pub},\ W_1)\parallel \dots \parallel PKS(A_{pub},\ W_m)$
Where $\parallel$ denotes concatenation and $E_{A_{pub}}$ is the public key of the legal authority (Alice). The reason for this form of encryption is so that the legal authority can provide a trapdoor $T_w$ to the messaging server to test whether a certain keyword has been used. Given a searchable encryption for a keyword $PKS(A_{pub},\ \ W^)$ and a trapdoor $T_w$ the messaging server can determine is $W=W^$ , if it’s the case that $W\neq W^$ then the messaging server does not learn any information about the word. It’s also quite interesting to note that this is not a very communitive scheme, as the searchable encryption (PKS) is constructed only using the public key of the legal authority.

### Definitions

Throughout this section we will refer to a negligible function as $f\mathrm{:}\mathrm{\ }\mathbb{R}\to \mathrm{[}0,\ 1]$ where $f\left(s\right)<1/g(s)$ for any polynomial $g$ and sufficiently large $s$. I will start by defining a searchable public key encryption scheme (PKS) where the public key refers to the cyphertext created by the messaging server  using the public key of the legal authority , and the searchable encryption scheme (PKS) does not reveal any information about the message.

Our goal is to enable the legal authority to send a short secret key ($T_w$) for a specific word to the messaging server, so that the messaging server can locate all messages that have this keyword without revealing the word $W$. The secret key ($T_w$) produced by the legal authority is based on the private key, and the messaging server send the message containing the words back to the legal authority, encrypted using the corresponding public key.

Definition 1.1: The following polynomial time randomized algorithms are part of a non-interactive searchable encryption scheme (PKS).

• $KeyGen(s)$: For a security parameter $s$ a corresponding public/private key pair is generated ($A_{priv},\ A_{pub})$ by the legal authority and the public key is sent to the messaging server.
• $PKS(A_{pub},\ W)$: For a word $W$ in the message, a searchable encryption (PKS) is generated using the public key $A_{pub}$ of the legal authority. We will denote the $PKS$ function as $S$
• $Trapdoor(A_{priv},\ W)$: Given the private key of the legal authority, a certain word $W$ produces a trapdoor $T_w$.
• $Test(A_{pub},\ S,\ T_W)$: Given the public key of the legal authority $A_{pub},\ \$and a searchable encryption $S$ on the messaging server, a trapdoor $T_w$ outputs yes’ if $W=W'$

The legal authority will run the $KeyGen$ algorithm and generate its public/ private key pairs, and then use the $Trapdoor$ function to generate a series of trapdoors for words $W_1..\ W_i$ that it wants to search for. The messaging server will then use the $Test$ function to determine whether a given message has a keyword $W_i$.

### Construction

For the definition above I will provide an efficient construction using bilinear maps based on a variant of the Decision Diffie-Hellman assumption with identity based encryption

We will use two groups $G_1,\ G_2$ of prime order $p$ and a bilinear map $e:G_1\times G_1\to G_2$ between the two groups. This map satisfies the following three properties where the size of $G_1$ and $G_2$ is determined by a security parameter:

• Computable: If you are given two elements in $G_1$ as $g,\ h$ then there exists a polynomial time algorithm to compute the map $e(g,\ h)$ in $G_2$
• Bilinear: for all integers in the prime order, we have a map $e(g^x,\ g^y)$ = $e(g,\ g)^{xy}$
• Non-degenerate: if $g$ is a generator of $G_1$ then the map $e(g,\ g)$ is a generator of $G_2$

From this we can build a non-interactive searchable encryption scheme based on bilinear maps. For this we will need two hash function, or random oracles in each group as:

$H_1:\{0,\ 1{\}}^*\to G_1$ and $H_2:G_2\to \{0,\ 1{\}}^{{log p\ }}$

Based on definition 1.1 we will construct the scheme using the same model based on the Dan Boneh Searchable Encryption Scheme:

• $KeyGen(s)$: The security parameter $s$ determines the size of the prime order $p$ of the groups $G_1$and $G_2$. The legal authority then also selects a random $\alpha \in {\mathbb{Z}}^*_p$ and a generator $g$ of $G_1$. The Output is a public key $A_{pub}=[g,\ h=g^{\alpha }]$ and a private key $\alpha$. The public key is then distributed to the messaging server.
• $PKS(A_{pub},\ W)$: Using the public key and a word $W$, the messaging server computes a bilinear map $t\ =e(H_1(W),\ h^r)\in G_2$ using the random oracle and a random $r\in {\mathbb{Z}}^*_p$. Then outputs a searchable encryption $PKS(A_{pub},\ W)=[g^r,\ H_2(t)]$.
• $Trapdoor(A_{priv},\ W)$: The legal authority uses the random oracle and its private key to generate a trapdoor $T_w=H_1(W)^{\alpha }\in G_1$
• $Test(A_{pub},\ S,\ T_W)$: When the messaging server receives a Test function from the legal authority as $S=[A,\ B]$ it can test if $H_2(e(T_w,\ A))=B$

The construction of the scheme can be viewed as a derivative of Identity Based Encryption with a limited number of identities. Using this scheme, the messaging server needs to have the ability to create an index of the words that’s exchanged between the users of the system that can be tested. Unfortunately, this construction has several issues relating to the sharing of the creation of the trapdoor function. None the less, the use of bi-linear maps and hash functions allows us to identify encrypted words without revealing what they actually are.

Standard

# Importing ZPK and ZMK into Thales Payshield 9000 HSM

ZMK

Zone Master Key (ZMK) also known as an Interchange key (IK), is a key-encrypting key which is distributed manually between two communicating sites, within a shared network, in order that further keys can be exchanged automatically. The ZMK is used to encrypt keys of a lower level (e.g. ZPK) for transmission.

The ZMK is exchanged using secured methods and Split knowledge policy. The IK is split into two components that are sent by two separate physical couriers to two nominated Security Officers of the other party. This is one of the most secure way to do it since no single person gains knowledge of the clear ZMK.

Here is the detailed Process. please note values indicated here are for testing only, in live environment the values will be exchanged securely.

Build ZMK Key manually:

This key is generated by two components, lets call them K1 and K2. To obtain the ZMK Key,

ZMK = K1 XOR K2


Test values provided,

K1 (clear) = 6D6B E51F 04F7 6167 4915 54FE 25F7 ABEF
K2 (clear) = 6749 9B2C F137 DFCB 9EA2 8FF7 57CD 10A7

ZMK (clear) key = K1 XOR K2 = 0A227E33F5C0BEACD7B7DB09723ABB48;
KCV = 05EE1D


Import ZMK into HSM

FK
Key length [1,2,3]: 2
Key Type: 000
Key Scheme: U
Component type [X,H,E,S]: X
Enter number of components (2-9): 2
Enter component #1: 6D6BE51F04F76167491554FE25F7ABEF
Enter component #2: 67499B2CF137DFCB9EA28FF757CD10A7

Encrypted key: U E685 8676 0A16 3026 C297 1007 3AB2 D7BE
Key check value: 05EE1D


ZPK

Zone PIN Key (ZPK) also known as a A PIN Protection Key (PPK), is a data encrypting key which is distributed automatically and is used to encrypt PINs. For security and protocol reasons the HSM where this key generated, never exposes the ZPK in clear. But it can be exported using another key called ZMK (Interchange Key). In this context exports actually means use the ZMK Key to encrypt the ZPK and give back to the user.

Import ZPK

The following ZPK shared by communicating party, is encrypted under ZMK

ZPK encrypted under ZMK: AC4D3C5F603C1B502E5F45668A155C25
KCV: AFDA4F


From the host application, send the A6 commands with required arguments as following,

HSM Command:

0000A6001UE68586760A163026C29710073AB2D7BEXAC4D3C5F603C1B502E5F45668A155C25U00


Where,

Atalla Variant = 00
Encrypted PPK Key = AC4D…….5C25
Key Scheme= X
Key Scheme LMK= U
Key Type = 001
ZMK = E68586760……..D7BE
ZMK Scheme = U

Response:
0000A700U5F2DC42E10C92B16BA54802314CE95F5AFDA4F

ZPK under LMK: U5F2DC42E10C92B16BA54802314CE95F5
KCV: AFDA4F


Here we can compare KCV (AFDA4F) to check if key is imported successfully.

Standard

# Overview

Remote key loading infrastructures generally implement Diebold’s and Triton’s Certificate Based Protocols (CBP), and NCR, Wincor and Hyosung Signature based Protocols.

The Diebold and Triton approaches use X.509 certificates and PKCS message formats to transport key data. NCR, Wincor and Hyosung methods rely on digital signatures to ensure data integrity. Both processes require the loading of the ATM EPP with a public key or certificate at the factory. Both these methods are supported in and XFS compliant manner and this document describes the process of doing so as well as the pitfalls and benefits of using both methods.

## The General Process

### Initialization

A prerequisite for using Remote Keys is for a customer to generate a set of keys or certificates that will be “signed” by a Certificate Authority or Trust Authority. Once signed, the public key or certificate signatures are returned and imported into the Host system. The EPPs obtain their signed public keys or certificates during the manufacturing process before being installed in ATMs.

### Mutual Authentication

With public and private key pairs now present in the Host and in the ATM’s EPP, mutual authentication can be initiated with message exchanges from the Host to the EPP.  The ATM sends the EPP serial number to Host encrypted by its public key or certificate. The Host verifies the message and sends a message back to the EPP encrypted by its public key or certificate.

### Key Delivery

With mutual authentication successfully completed, the Host receives a request to deliver a new terminal master key to the EPP. The Host receives the key request and generates a random terminal master key and encrypts it with the public key of the EPP and “signs” the new TMK message. This message is sent to the EPP. The EPP verifies the signature, decrypts the new terminal master key, and stores the key.

If the dialogue has been successfully completed, the EPP sends a notification back to the Host that it has loaded the new terminal master key including a Key Check Value (KCV) of the new key. If the terminal key load is unsuccessful, an appropriate error message will be returned to the Host. Upon receiving a “successful” terminal master key load message from the EPP with the correct KCV, the Host will establish the new TMK in the key database.

### RSA Data Authentication and Digital Signatures

Digital signatures rely on a public key infrastructure (PKI). The PKI model involves an entity, such as a Host, having a pair of encryption keys – one private, one public. These keys work in consort to encrypt, decrypt and authenticate data.

One-way authentication occurs is through the application of a digital signature. For example:

1. The Host creates some data that it would like to digitally sign;
2. Host runs the data through a hashing algorithm to produce a hash or digest of the data. The digest is unique to every block of data – a digital fingerprint of the data, much smaller and therefore more economical to encrypt than the data itself.
3. Digest is encrypted with the Host’s private key. This is the digital signature – a data block digest encrypted with the private key.

The Host then sends the following to the ATM:

1. Data block.
2. Digital signature.
3. Host’s public key.

To validate the signature, the ATM performs the following:

ATM runs data through the standard hashing algorithm – the same one used by the Host – to produce a digest of the data received. Consider this digest2;

ATM uses the Host’s public key to decrypt the digital signature. The digital signature was produced using the Host’s private key to encrypt the data digest; therefore, when decrypted with the Host’s public key it produces the same digest. Consider this digest1. Incidentally, no other public key in the world would work to decrypt digest1 – only the public key corresponding to the signing private key.

ATM compares digest1 with digest2. If digest1 matches digest2 exactly, the ATM has confirmed that the data was not tampered with in transit. Changing a single bit in the data sent from the Host to the ATM would cause digest2 to be different than digest1. Every data block has a unique digest; therefore, an altered data block is detected by the ATM.

Public key used to decrypt the digital signature corresponds to the private key used to create it. No other public key could possibly work to decrypt the digital signature, so the ATM was not handed someone else’s public key.

This gives an overview of how Digital Signatures can be used in Data Authentication. In particular, Signatures can be used to validate and securely install Encryption Keys.

The following section describes Key Exchange and the use of Digital signatures.

### RSA Secure Key Exchange using Digital Signatures

In summary, both end points, the ATM and the Host, inform each other of their Public Keys. This information is then used to securely send the PIN device Master Key to the ATM.

A trusted third party, the Signature Issuer, is used to generate the signatures for the Public keys of each end point, ensuring their validity.

The detail of this is as follows:

#### Purpose:

The Host wishes to install a new master key (KM) on the ATM securely.

#### Assumptions:

• The Host has obtained the Public Key (PKSI) from the Signature Issuer.
• The Host has provided the Signature Issuer with its Public Key (PKHOST), and receives the corresponding signature Sign(SKSI)[ PKHOST]. The Signature Issuer uses its own Private Key (SKSI) to create this signature.
• In the case where Enhanced Remote Key Loading is used, the Host has provided the Signature Issuer with its Public Key (PKROOT), and receives the corresponding signature Sign(SKSI)[PKROOT]. The Host has generated another key pair PKHOST and SKHOST and signs the PKHOST with the SKROOT.
• (Optional) The Host obtains a list of the valid PIN device’s Unique Identifiers. The Signature Issuer installs a Signature Sign(SKSI)[ UIATM] for the Unique Id (UIATM) on the ATM PIN. The Signature Issuer uses SKSI to do this.
• The Signature Issuer installs its Public Key (PKSI) on the ATM PIN. It also derives and installs the Signature Sign(SKSI )[PKATM] of the ATM PIN’s Public Key (PKATM) on the ATM PIN. The Signature Issuer uses SKSI to do this.
• The ATM PIN device additionally contains its own Public (PKATM) and Private Key (SKATM).

#### Steps for the Process

Step 1: The ATM PIN sends its Public Key to the Host in a secure structure: The ATM PIN sends its ATM Public Key with its associated Signature. When the Host receives this information it will use the Signature Issuer’s Public Key to validate the signature and obtain the ATM Public Key.

Step 2 (Optional):  The Host verifies that the key it has just received is from a valid sender. It does this by obtaining the PIN device unique identifier. The ATM PIN sends its Unique Identifier with its associated Signature. When the Host receives this information it will use the Signature Issuer’s Public Key to validate the signature and retrieve the PIN Unique Identifier. It can then check this against the list it received from the Signature Issuer.

Step 3 (Enhanced Remote Key Loading only) : The Host sends its root public key to the ATM PIN: The Host sends its Root Public Key (PKROOT) and associated Signature. The ATM PIN verifies the signature using PKSI and stores the key.

Step 4:  The Host sends its public key to the ATM PIN: The Host sends its Public Key (PKHOST) and associated Signature. The ATM PIN verifies the signature using PKSI (or PKROOT in the Enhanced Remote Key Loading Scheme) and stores the key

Step 5:  The ATM PIN receives its Master Key from the Host: The Host encrypts the Master Key (KM) with PKATM. A signature for this is then created. The ATM PIN will then validate the signature using PKHOST and then obtain the master key by decrypting using SKATM.

Step 6 – Alternative including random number:  The Host requests the ATM PIN to begin the DES key transfer process and generate a random number. The Host encrypts the Master Key (KM) with PKATM. A signature for the random number and encrypted key is then created using SKHOST. The ATM PIN will then validate the signature using PKHOST, verify the random number and then obtain the master key by decrypting using SKATM.

### Certificate Exchange and Authentication

Both end points, the ATM and the Host, inform each other of their Public Keys. This information is then used to securely send the PIN device Master Key to the ATM. A trusted third party, Certificate Authority (or a HOST if it becomes the new CA), is used to generate the certificates for the Public Keys of each end point, ensuring their validity. In this message contains the Host certificate, which has been signed by the trusted CA. The Pinpad Cryptography Unit (CTU) uses the Public Key of the CA (loaded at the time of production) to verify the validity of the certificate. If the certificate is valid, the CTU stores the HOST’s Public Verification Key. The CTU then sends a message that contains a certificate, which is signed by the CA and is sent to the HOST. The HOST uses the Public Key from the CA to verify the certificate. If valid then the HOST stores the CTU’s verification or encryption key (primary or secondary this depends on the state of the CTU).

### Remote Key Exchange

After the above has been completed, the HOST is ready to load the key into the CTU.

The following is done to complete this and the application must complete the Remote Key Exchange in this order:

1. Return RATM from the CTU to be used in authenticating the message.
2. Next, the ATM sends down the KTK to the CTU. The following items below show how this is accomplished.
3. a) HOST has obtained a Key Transport Key and wants to transfer it to the CTU. HOST constructs a key block containing an identifier of the HOST, IHOST, and the key, KKTK, and enciphers the block, using the CTU’s Public Encryption Key.
4. b) After completing the above, the HOST generates random data and builds the outer message containing the random number of the Host, RHOST, and the random number of the ATM, RATM. The identifier of the CTU, IENC, and the enciphered key block. The HOST signs the whole block using its private signature key and sends the message down to the CTU. The CTU then verifies the HOST’s signature on the message by using the HOST’s Public Verification Key. Then the CTU checks the identifier and the random number of the CTU passed in the message to make sure that the CTU is talking to the right HOST. The CTU then deciphers the enciphered block using its private verification key. After the message has been deciphered, the CTU checks the Identifier of the HOST. Finally, if everything checks out to this point the CTU will load the Key Transport Key
5. c) After the Key Transport Key has been accepted, the CTU constructs a message that contains the random number of the Host, the random number of the CTU and the HOST identifier all signed by the private signature key of the CTU. This message is sent to the Host.
6. d) The HOST verifies the message sent from the CTU by using the ATM’s public verification key. The HOST then checks the identifier of the Host and then compares the identifier in the message with the one stored in the HOST. Then checks the random number sent in the message and to the one stored in the HOST. The HOST finally checks the CTU’s random number with the one received.

### Replace Certificate

After the key is been loaded into the CTU, the following could be completed: The new CA requests a Certificate from the previous Certificate Authority. The HOST must over-sign the message to take over the role of the CA to ensure that the CTU accepts the new Certificate Authority. The HOST sends the message to the CTU. The CTU uses the HOST’s Public Verification Key to verify the HOST’s signature. The CTU uses the previous CA’s Public Verification Key to verify the signature on the new Certificate sent down in the message. If valid, the EPP stores the new CA’s certificate and uses the new CA’s Public Verification Key as its new CA verification key.

Standard