Featured

# 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.

Featured

# El Gamal and Diffie Hellman Similarities

In terms for public key algorithms this post is about DL problems with Diffie Hellman as a key exchange mechanism and EL Gamal as a method of encryption.

 Service Algorithm Family Integer Factor DL / Zp* DL /Elliptic curve Key Exchange RSA DH Elliptic Curve Diffie Hellman Digital Signature RSA El Gamal + DSA ECDSA Encryption RSA El Gamal Elliptic Curve El Gamal Variant

There are an additional 4 families of algorithms that were proposed in the 1970’s and 1980’s, but these are impractical to use in practice because of large keys and the slowness of them, these post-quantum cryptography algorithms are being considered now because of the increase in processing device speed.

Encryption with the DL problem.

Goal: Develop an encryption scheme from the DH key exchange scheme.

DH result is used an input for AES, but we just want to look at the handshake and DL problem and not use of AES.

For DH Key exchanges:

We have Alice and Bob with a set of domain parameters α,p that is known to both parties.

• Alice computes her key A= αa mod p
• Bob computes his Key B = αb mod p

These keys are then exchanged and both sides computing their session key KAB

• With Alice calculating Ba = αab = KAB mod p
• And Bob calculating Ab = αab = KAB mod p
 Step Alice <- α,p -> (Step 5 in EG) Bob DH Key Exchange 1 A= αa mod p (Step 7 EG) A <- (Step 9 EG) 2 ß B B = αb mod p 3 Ba = αab = KAB mod p (Step 8 EG) Both parties have KAB Ab = αab = KAB mod p (Step 11 EG) Encryption 4 Y = x.KAB mod p (Step 9 EG) Y -> 5 X = Y.KAB -1 mod p (Step 12 EG)

Now since both parties have the same key, we can use 3DES or AES to encrypt messages between them using mod 2. But more interestingly we can use multiplication to encrypt messages, by using your plaintext message and multiplying it with your secret key KAB.

When Alice wants to encrypt a message ‘x’ using multiplication, she gets the cypher text Y =  x.KAB mod p. When Bob wants retrieve the original message, he would need to find the inverse (divide) X = Y.KAB -1 mod p.

Now this scheme is essentially the same as El Gamal, you use DH to establish a session key, then encrypt using multiplication. The only difference is the terms and the sequence of events are reordered.

EG Problem

Now if we look at El Gamal (EG) the domain parameters α and p are not public but its originating from bob, as he is the receiver of the message. In public key cryptography we have the notion of the receiver of the message would need to set up public and private keys and publish the public key.

In order to come up with a DL problem, it’s always: αx = A mod p, where x is always the private key Kpr and A is always the public key Kpub.

As Bob is the receiver he chooses p and a primitive alpha, he then picks an element in p as his private key, and uses his private key and his primitive to compute his public key. He then sends or publish his public key, p and alpha to Alice. With DH we have α and p as domain parameters, but because Bob generated them he needs to inform Alice what these parameters are. This step is equivalent to the domain parameters in DH.

Alice now would also need to compute her keys, so she chooses i from the set of p where i e {2, 3, … p-2} and calculates the ephemeral key KE = αi mod p which is the same as Alice public key calculated in step 1 of DH. Now step 3 in DH is the next step where a session key is calculated, and the same is done in EG, this is just renamed as a masking key KM. Now since Alice have all the keys she can now encrypt data.

Let’s assume she computes the cypher text y = x.KM mod p, in DH Multiplication encryption KM is KAB and these are equivalent. Alice now sends her encrypted data over to bob together with her ephemeral key. This sending over of information is the merging of sending A and Y in DH by sending over the session key and the encrypted data.

When bob receives the message he needs to decrypt the message, in DH we find the inverse of KAB to decrypt the message which is equivalent to finding the inverse of KM in EG. So Bob now needs to compute the masking key KM which is equivalent to the session key in DH Step 3. He does this by using his private key and ephemeral key received from Alice. When he calculates KM he uses the inverse of KM to decrypt the message.

DH and EG are essentially the same protocol, textbooks refer to DH and EG as two completely different encryption schemes but they are in fact the same with the order in which information is sent across is altered and new terms are introduced.

 Step Alice Bob 1 Choose p and prime α 2 He computes his private key Kpr = d e {2, 3,.., p-2} 3 He computes his public key Kpub = β = αd mod p 5 ß (α, p, β) (Domain Params in DH) 6 Choose i e {2, 3, … p-2} 7 Calculates ephemeral key: KE = αi mod p (Step 1 DH) 8 Calculate masking key KM = βi mod p (Step 3 DH) 9 Encrypt Data: y = x.KM mod p (Step 4 DH) 10 y,KE  -> (Step 1 and 4 of HD combined) 11 Computes masking key (Step 3 DH) KM= KEd mod p 12 Decrypt message (Step 5 DH) X = y.KM-1 mod p

Comparison between EG and DH computations

 Area EG DH Domain Parameters Parameters α, p, β originates from the receiver Parameters α, p is public.  β is not provided Ephemeral Key KE = αi mod p A= αa mod p Session / Masking Key KM = βi mod p Ba = αab = KAB mod p Encryption y = x.KM mod p Y = x.KAB mod p Decryption X = y.KM-1 mod p X = Y.KAB -1 mod p

Proof of correctness for EG

So let’s see what bob decrypts are actually the original plaintext message that was encrypted by Alice.

Bob computes: x

y.KM-1 = y(KEd)-1   : because {KM = KEd}

= x.KM . KE-d : because {y = x.KM}

= x. βi . (αi)-d : Step 7 and 8 from EG

Now we are trying to compute x and we have allot of factors, all we have to prove is that all the factors is equal to 1, since x.1 = x.

= x(αd)i . (αi)-d since β = αd in step 3 of EG

= x. αid . α-id

= x. αid-id = x. α0 = x.1 = x

(mod p is implied)

Proof of correctness for DH

Alice computes:

Ba = (αb) a = αab mod p

Bob Computes:

Ab = (αa) b = αab mod p

Encryption and decryption is of course just inverses of each other, so there is no need to prove this.

El Gamal replacing 3DES (I work in the ATM industry so applying this to ATM is quite interesting)

El Gamal can be used in the current finance sector as a replacement 3DES with the use of ATM devices.

Currently 3DES capable ATM cash machine devices, have a Master Key (KMaster), that is inserted into the ATM manually using split knowledge. This is the first input for 3DES, the second input for 3DES is, when the ATM starts up it contacts the host and retrieves the session key(KSession). When a user does a transaction on the ATM, the Pin is encrypted using 3DES y = (x{E(KSession)D(KMaster)E(KSession)}).

The Host then decrypts or translates the pin using the inverse x = (y{D(KSession)E(KMaster)D(KSession)})

If we look at this closer, we can see the Master Key can be replaced by α, p, β when the terminal requests a session key and that the pinblock can be encrypted by y = x.KM mod p, eliminating the need for 3DES and manual encryption key entering.

By replacing 3DES with El Gamal there is no need to contact the host for new session key as the terminal would be changing the ephemeral key for every transaction. There is also no exposure to compromise the Master Keys.

 El Gamal 3DES Step 1 No Keys inserted User enter Master key manually Step 2 ATM Contract host for domain parameters α, p, β ATM Contact host for session key Step 3 Pin encrypted y = x.KM mod p Pin encrypted (E, D, E) Step 4 Host Decrypt Pin X = y.KM-1 mod p Pin decrypted (D, E, D)

Featured

# Mutual Authentication using Certificates

Mutual SSL authentication or certificate based mutual authentication refers to two parties authenticating each other through verifying the provided digital certificate so that both parties are assured of the others’ identity. In technology terms, it refers to a client (ATM) authenticating themselves to a server (Switch) and that server also authenticating itself to the client through verifying the public key certificate/digital certificate issued by the trusted Certificate Authorities (CAs).

Because authentication relies on digital certificates, certification authorities and Certificate Server are an important part of the mutual authentication process. From a high-level point of view, the process of authenticating and establishing an encrypted channel using certificate-based mutual authentication involves the following steps in TLS:

1. A client requests access to a protected resource.
2. The server presents its certificate to the client.
3. The client verifies the server’s certificate.
4. If successful, the client sends its certificate to the server.
5. The server verifies the client’s credentials.
6. If successful, the server grants access to the protected resource requested by the client.

## TLS Mutual Authentication Handshake

The TLS handshake firstly agrees the protocol to be used by both parties, then exchanges certificates and validates the signatures on each certificates. Below are more detailed steps explaining the handshake.

1. The TLS client sends a “client hello” message that lists cryptographic information such as the SSL or TLS version and, in the client’s order of preference, the CipherSuites supported by the client. The message also contains a random byte string that is used in subsequent computations. The protocol allows for the “client hello” to include the data compression methods supported by the client.
2. The TLS server responds with a “server hello” message that contains the CipherSuite chosen by the server from the list provided by the client, the session ID, and another random byte string. The server also sends its digital certificate. The server sends a “client certificate request” that includes a list of the types of certificates supported and the Distinguished Names of acceptable Certification Authorities (CAs).
3. The TLS client verifies the server’s digital certificate.
4. The TLS client sends the random byte string that enables both the client and the server to compute the secret key to be used for encrypting subsequent message data. The random byte string itself is encrypted with the server’s public key.
5. If the TLS server sent a “client certificate request”, the client sends a random byte string encrypted with the client’s private key, together with the client’s digital certificate, or a “no digital certificate alert”. This alert is only a warning, but we will not be allowing transactions without a client certificate.
6. The TLS server verifies the client’s certificate.
7. The TLS client sends the server a “finished” message, which is encrypted with the secret key, indicating that the client part of the handshake is complete.
8. The TLS server sends the client a “finished” message, which is encrypted with the secret key, indicating that the server part of the handshake is complete.
9. For the duration of the TLS session, the server and client can now exchange messages that are symmetrically encrypted with the shared secret key.

In order to have a clear understanding of public key cryptography and digital signatures, the following section provides a high level overview of the encryption scheme using mutual authentication and certificate authorities.

## Public-key certificate scheme Basics

In this section we use Alice and Bob as two parties that exchange messages, Oscar is a malicious user trying to decrypt and steal data.

The underlying problem with normal RSA is that the server has no real proof of who its communicating to. If a server is issuing public keys to all parties, how can it identify each individual user and ensue the public keys belong to valid users? Public certificates are also susceptible to Man in the Middle Attacks (MIM) where Oscar can pretend to be Alice and the server have not way of knowing.

Message authentication ensures that the sender of a message is authentic. However, in the scenario at hand Bob receives a public key which is supposedly Alice’s, but he has no way of knowing whether that is in fact the case. To make this point clear, let’s examine how a key of a user Alice would look in practice:

kA = (kpub,A,IDA)

,where IDA is identifying information, e.g., Alice’s IP address or her name together with date of birth. The actual public key kpub,A, however, is a mere binary string,  e.g., 2048 bit. If Oscar performs a MIM attack, he would change the key to:

kA = (kpub,O,IDA)

Since everything is unchanged except the anonymous actual bit string, the receiver will not be able to detect that it is in fact Oscar’s. This observation has far-reaching consequences which can be summarized as: Even though public-key schemes do not require a secure channel; they require authenticated channels for the distribution of the public keys.

The idea behind certificates and authenticated channels is quite easy: Since the authenticity of the message (kpub,A,IDA)is violated by an active Man in the middle attack, we apply a cryptographic mechanism that provides authentication. More specifically, we use digital signatures. Thus, a certificate for a user Alice in its most basic form is the following structure where IDA is identifying information like a terminal id or serial number:

CertA = [(kpub,A,IDA), sigkpr (kpub,A,IDA)]

The idea is that the receiver of a certificate verifies the signature prior to using the certificate, and both the client and the server validates the signature before using the public key. The signature protects the signed message which is the structure (kpub,A,IDA) in this case—against manipulation. If Oscar attempts to replace kpub,A by kpub,O it will be detected. Thus, it is said that certificates bind the identity of a user to their public key.

Certificates require that the receiver has the correct verification key, which is a public key. If we were to use Alice’s public key for this, we would have the same problem that we are actually trying to solve and Oscar can impersonate Alice. Instead, the signatures for certificates are provided by a mutually trusted third party. This party is called the Certification Authority commonly abbreviated as CA. It is the task of the CA to generate and issue certificates for all users in the system.

For certificate generation, we can distinguish between two main cases. In the first case, the user computes her own asymmetric key pair and merely requests the CA to sign the public key, as shown in the following simple protocol for a user named Alice:

Table 1 Certificate Generation with User-Provided Keys

 Description Alice Request / Response CA Alice generates a public private key pair generate kpr,A, kpub,A Sends this to the CA RQST(kpub,A,IDA)→ CA verifies Alice’s identity verify IDA CA signs Alice public key with its private key sA = sigkpr ,CA(kpub,A,IDA) CA creates a certificate (public private key pair) with its signature CertA = [(kpub,A,IDA), sA] Certificate is distributed to Alice for usage ←CertA

From a security point of view, the first transaction is crucial. It must be assured that Alice’s message (kpub,A, IDA) is sent via an authenticated channel. Otherwise, Oscar could request a certificate in Alice’s name.

In practice it is often advantageous that the CA not only signs the public keys but also generates the public–private key pairs for each user. In this case, a basic protocol looks like this:

Table 2 Certificate Generation with CA-Generated Keys

 Description Alice Request / Response CA Alice request certificate request certificate Sends this to the CA −RQST(,IDA)→ CA verifies Alice’s identity verify IDA CA generates new certificate generate kpr,A, kpub,A CA signs Alice public key with its private key sA = sigkpr ,CA(kpub,A,IDA) CA creates a certificate (public private key pair) with its signature CertA = [(kpub,A,IDA), sA] Certificate is distributed to Alice for usage ←CertA

For the first transmission, an authenticated channel is needed. In other words: The CA must be assured that it is really Alice who is requesting a certificate, and not Oscar who is requesting a certificate in Alice’s name. Even more sensitive is the second transmission consisting of (CertA, kpr,A). Because the private key is being sent here, not only an authenticated but a secure channel is required. In practice, this could be a certificate delivered by mail or USB stick.

Table 3 Diffie–Hellman Key Exchange with Certificates

 Description Alice Request / Response Bob Both Alice and Bob have private keys issued by a trusted CA a = kpr,A b = kpr,B A = kpub,A ≡ a a  mod p B= kpub,B ≡aB mod p Both Alice and Bob generates a public key and signs it with their private key and identity CertA = [(A,IDA), sA] CertB = [(B,IDB), sB] Certificates are exchanged CertA → ←CertB verify certificate: verify certificate: Both Alice and Bob use the public key of the CA to verify the signature of the certificate verkpub,CA (CertB) verkpub,CA (CertA) compute session key: compute session key: Session key can now be computed. kAB ≡ Ba modp kAB ≡ Ab mod p

One very crucial point here is the verification of the certificates. Obviously, without verification, the signatures within the certificates would be of no use. As can be seen in the protocol, verification requires the public key of the CA. This key must be transmitted via an authenticated channel; What’s happening here from a more abstract point of view is extremely interesting, namely a transfer of trust. With the introduction of certificates, they only have to trust the CA’s public key kpub,CA. If the CA signs other public keys, Alice and Bob know that they can also trust those. This is called a chain of trust.

## Certificate Structure

Discussing the fields defined in a X.509 certificate gives us some insight into many aspects of PKIs. We discuss the most relevant ones in the following:

• Certificate Algorithm: Here it is specified which signature algorithm is being used, e.g., RSA with SHA-1 or ECDSA with SHA-2, and with which parameters, e.g., the bit lengths.
• Issuer: There are many companies and organizations that issue certificates. This field specifies who generated the one at hand.
• Period of Validity: In most cases, a public key is not certified indefinitely but rather for a limited time, e.g., for one or two years. One reason for doing this is that private keys which belong to the certificate may become compromised. By limiting the validity period, there is only a certain time span during which an attacker can maliciously use the private key. Another reason for a restricted lifetime is that, especially for certificates for companies, it can happen that the user ceases to exist. If the certificates, and thus the public keys, are only valid for limited time, the damage can be controlled.
• Subject: This field contains what was called IDA or IDB in our earlier examples. It contains identifying information such as names of people or organizations. Note that not only actual people but also entities like companies can obtain certificates.
• Subject’s Public Key: The public key that is to be protected by the certificate is here. In addition to the binary string which is the public key, the algorithm (e.g., Diffie–Hellman) and the algorithm parameters, e.g., the modulus p and the primitive element a, are stored.
• Signature: The signature over all other fields of the certificate.

We note that for every signature two public key algorithms are involved: the one whose public key is protected by the certificate and the algorithm with which the certificate is signed. These can be entirely different algorithms and parameter sets. For instance, the certificate might be signed with an RSA 2048-bit algorithm, while the public key within the certificate could belong to a 160-bit elliptic curve scheme.

## Certificate Revocation

One major issue in practice is that it must be possible to revoke certificates. A common reason is that a certificate is stored on a smart card which is lost. Another reason could be that a person left an organization and one wants to make sure that she is not using the public key that was given to her. The solution in these situations seems easy: Just publish a list with all certificates that are currently invalid. Such a list is called a certificate revocation list, or CRL. Typically, the serial numbers of certificates are used to identify the revoked certificates. Of course, a CRL must be signed by the CA since otherwise attacks are possible.

The problem with CLRs is how to transmit them to the users. The most straightforward way is that every user contacts the issuing CA every time a certificate of another user is received. The major drawback is that now the CA is involved in every session set-up. This was one major drawback of KDC-based, i.e., symmetric key, approaches. The promise of certificate-based communication was that no online contact to a central authority was needed.

An alternative is that CRLs are sent out periodically. The problem with this approach is that there is always a period during which a certificate is invalid but users have not yet been informed. For instance, if the CRL is sent out at 3:00 am every morning (a time with relatively little network traffic otherwise), a dishonest person could have almost a whole day where a revoked certificate is still valid. To counter this, the CRL update period can be shortened, say to one hour.

However, this would be a tremendous burden on the bandwidth of the network. This is an instructive example for the trade-off between costs in the form of network traffic on one hand, and security on the other hand. In practice, a reasonable compromise must be found. In order to keep the size of CRLs moderate, often only the changes from the last CRL broadcast are sent out. These update-only CRLs are referred to as delta CRLs.

Featured

# 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.

Featured

# 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.

Featured

# The Refund vulnerability of AS2805 and EFTPOS

Transactions are normally validated, matched then processed. This is very common to ensure that requests sent to a payments switch are associated with its responses before delivering responses to a terminal. Now for all transaction types this process in true, except for refunds. Well, at least it’s not matched for most financial institutions in Australia.

Below is a few descriptions of transactions that might be processed through a typical switch in Australia:

Authorization / Cash Out

The Authorization transaction is typically used by a merchant to obtain the authorization of a transaction amount as a pre-approval for the purchase of goods or services later during the fulfillment process. Authorization transactions are typically submitted for authorization and then funds are held by the issuer until that transaction is captured or the authorization is reversed or expires. An example can be found with online retailers who initiate an Authorization transaction to guaranteed funding by the card issuer prior to the shipment/delivery (i.e. fulfillment) of the goods. An “Authorization” is also referred to as an Auth-Only transaction.

Sale / Purchase

A “Sale” transaction is used by merchants for the immediate purchase of goods or services. This transaction completes both the authorization and capture in a single transaction request. The Sale transaction is an Authorization and Capture transaction that if approved is automatically included for settlement.

Forced Sale

A “Forced Sale” is a transaction initiated by a merchant with the intent of forcing the posting of the transaction against the customer account without receiving prior authorization by the card issuer, or receiving a voice authorization code from the merchant acquiring call center. An example would be when a merchant’s terminal is offline, requiring the purchase of goods being completed without receiving online authorization by the card issuer. Or they received a Voice Approval. In these cases the merchant would enter the transaction details and forward this Forced Sale transaction to the card issuer with the expectation of receiving funding for the goods or services rendered. A forced sale does not require a matching authorization. Forced Sales are also known as Off-Line Sales.

Refund

A Refund allows a merchant to refund a previously settled transaction and submit the refund for processing. Refunds are only allowed for financial transactions (Sale and Captured) and are typically limited to the original authorization amount, or a lesser amount, in some cases, multiple partial refunds up to the original transaction amount. Some systems incorporate a feature called Matched Refunds. Matched Refunds must match back to an original transaction to help control fraud. “ Refunds” are also sometimes referred to as a “Credit” transaction.

Void

Void transactions can reverse transactions that have been previously authorized or approved by the card issuer and are pending settlement. Merchants will only be allowed to void transactions that are in an open batch (pending settlement). Sale or Refund transactions are the most commonly voided transaction types.

Capture

The Capture transaction will allow merchants to capture a previously authorized transaction that is pending settlement, and submit it for clearing and settlement. An example is when online retailers who initiate an Authorization transaction to reserve funds by the card issuer prior to the shipment/delivery (i.e. fulfillment) of the goods, and then once fulfillment has been completed the transaction will be captured and submitted for settlement. A “Capture” is also referred to as a Pre-Authorization Completion transaction.

Now According to the AS2805 Specifications,   The refund is not matched to the transaction during the refund authorization, and will approve by default, you need to match the Refund to an Authorization or Sale when doing settlement.

This appears not implemented in Australia for some reason, and some financial institutions will actually admit it.

I have tried this on a EFTPOS machine, you should try this as well. Simply do a refund on a EFTPOS terminal without doing a transaction. All you would need is a 4 digit password to access the refund function (in some cases  refunds are not password protected) , these default passwords are published by the terminal manufacturers.

In every case that I’ve tried this, the refund is processed and the funds appeared in my account. This is surely a massive risk for fraud!!!!

Strange enough, the banks are not worried about this as the funds are tied to the merchant account, and it’s not a risk for the bank but for the Merchant. These are some clause in the contracts that absolve them from the risk.

So if you have a EFTPOS terminal, ask for the refund function to be disabled or you could be out of pocket!

Featured

# Data Security – RSA

Introduction

Today in the Age Of Computer & Internet Each And Every One Has To Face The Problem Of Hacking. Here We Have Tried Our Best To Resolve This Problem Using Encryption & Decryption Technology Based On RSA Algorithm. With The Use Of This Technique We Can Build Standalone As Well As Network Application To Secure Our Data. Here We Have Present The Data Security With RSA Algorithm & Cryptography. Our mission of this Blog post is to gives you highly secured Network & Data Transmission overview.

Cryptography

Cryptography has a long & colorful history. Historically, four groups of people have used and contributed to the art of cryptography: the military, the diplomatic corps, diarists, and lovers. Of these, the military has had the most important role and has shaped the field. Within military organizations, the messages to be encrypted have traditionally been given to poorly paid code clerks for encryption and transmission. The sheer volume of messages prevented this work from being done by a few elates specialists.

One of the main constraints on cryptography had been the ability of the code clerk to perform the necessary transformation, often of a battlefield with little equipment. An additional constraint has been the difficulty in switching over quickly from one cryptographic method to another one.

Encryption

Encryption is the process of translating plain text data into something that appears to be random & meaningless (cipher text).

Simple encryption techniques may not provide adequate security, since it may be easy for an unauthorized user to break the code. There are a vast number of techniques for the encryption of data. If a really good encryption algorithm is used, there is no technique significantly better than methodically trying every possible key.

A good encryption technique has the following properties: –

• It is relatively simple for authorized users to encrypt & decrypt data.
• The encryption scheme depends not on the secrecy of the algorithm called the encryption key. It is extremely difficult for an intruder to determine the encryption key.
• The goal of every encryption algorithm is to make it as difficult as possible to decrypt the generated cipher text without using the key.

Decryption

Decryption of data is the process of converting the cipher text back to plain text. The algorithms using the same key for the encryption & decryption of data are known as symmetric algorithms. To encrypt more than a small amount of data, symmetric encryption is used.

Cipher

A block cipher is a type of symmetric-key encryption algorithm that transforms a fixed-length block of plaintext (unencrypted text) data into a block of cipher text (encrypted text) data of the same length. This transformation takes place under the action of a user-provided secret key.

Applying the reverse transformation to the cipher text block using the same secret key performs decryption. The fixed length is called the block size, and for many block ciphers, the block size is 64 bits. In the coming years the block size will increase to 128 bits as processors become more sophisticated.

Since different plain text blocks are mapped to different cipher text blocks (to allow unique decryption), a block cipher effectively provides a permutation (one to one reversible correspondence) of the set of all possible messages. The permutation effected during any particular encryption is of course secret, since it is a function of the secret key.

When we use a block cipher to encrypt a message of arbitrary length, we use techniques known as modes of operation for the block cipher. To be useful, a mode must be at least as secure and as efficient as the underlying cipher. Modes may have properties in addition to those inherent in the basic cipher.

RSA Algorithm

The RSA cryptosystem is a public-key cryptosystem that offers both encryption and digital signatures (authentication). Ronald Rivest, Adi Shamir, and Leonard Adleman developed the RSA system in 1977; RSA stands for the first letter in each of its inventors’ last names.

The RSA algorithm works as follows: take two large primes, p and q, and compute their product n = p*q; n is called the modulus. Choose a number, e, less than n and relatively prime to (p-1)*(q-1), which means e and (p-1)*(q-1) have no common factors except 1. Find another number d such that (e*d – 1) is divisible by (p-1)*(q-1). The values e and d are called the public and private exponents, respectively. The public key is the pair (n, e); the private key is (n, d). The factors p and q may be destroyed or kept with the private key.

It is currently difficult to obtain the private key d from the public key (n, e). However if one could factor n into p and q, then one could obtain the private key d. Thus the security of the RSA system is based on the assumption that factoring is difficult. The discovery of an easy method of factoring would “break” RSA.

Here is how the RSA system can be used for encryption and digital signatures. Encryption   Suppose Alice wants to send a message m to Bob. Alice creates the cipher text c by exponentiation: c = me mod n, where e and n are Bob’s public key. She sends c to Bob. To decrypt, Bob also exponentiates: m = cd mod n; the relationship between e and d ensures that Bob correctly recovers m. Since only Bob knows d, only Bob can decrypt this message.

Digital Signature :-  Suppose Alice wants to send a message m to Bob in such a way that Bob is assured the message is both authentic, has not been tampered with, and from Alice. Alice creates a digital signature s by exponentiation: s = md mod n, where d and n are Alice’s private key. She sends m and s to Bob. To verify the signature, Bob exponentiates and checks that the message m is recovered: m = se mod n, where e and n are Alice’s public key.

Thus encryption and authentication take place without any sharing of private keys; each person uses only another’s public key or their own private key. Anyone can send an encrypted message or verify a signed message, but only someone in possession of the correct private key can decrypt or sign a message.

SPEED OF RSA

An “RSA operation” whether encrypting, decrypting, signing, or verifying is essentially a modular exponentiation. This computation is performed by a series of modular multiplications.

In practical applications, it is common to choose a small public exponent for the public key. In fact, entire groups of users can use the same public exponent, each with a different modulus. (There are some restrictions on the prime factors of the modulus when the public exponent is fixed.) This makes encryption faster than decryption and verification faster than signing. With the typical modular exponentiation algorithms used to implement the RSA algorithm, public key operations take O (k2) steps, private key operations take O (k3) steps, and key generation takes O (k4) steps, where k is the number of bits in the modulus. “Fast multiplication” techniques, such as methods based on the Fast Fourier Transform (FFT), require asymptotically fewer steps. In practice, however, they are not as common due to their greater software complexity and the fact that they may actually be slower for typical key sizes.

The speed and efficiency of the many commercially available software and hardware implementations of the RSA algorithm are increasing rapidly.

By comparison, DES and other block ciphers are much faster than the RSA algorithm. DES is generally at least 100 times as fast in software and between 1,000 and 10,000 times as fast in hardware, depending on the implementation. Implementations of the RSA algorithm will probably narrow the gap a bit in coming years, due to high demand, but block ciphers will get faster as well.

BREAKING OF RSA

There are a few possible interpretations of “breaking” the RSA system. The most damaging would be for an attacker to discover the private key corresponding to a given public key; this would enable the attacker both to read all messages encrypted with the public key and to forge signatures. The obvious way to do this attack is to factor the public modulus, n, into its two prime factors, p and q. From p, q, and e, the public exponent, the attacker can easily get d, the private exponent. The hard part is factoring n; the security of RSA depends on factoring being difficult. In fact, the task of recovering the private key is equivalent to the task of factoring the modulus: you can use d to factor n, as well as use the factorization of n to find d. It should be noted that hardware improvements alone would not weaken the RSA cryptosystem, as long as appropriate key lengths are used. In fact, hardware improvements should increase the security of the cryptosystem. Another way to break the RSA cryptosystem is to find a technique to compute eth roots mod n. Since c = me mod n, the eth root of c mod n is the message m. This attack would allow someone to recover encrypted messages and forge signatures even without knowing the private key. This attack is not known to be equivalent to factoring. No general methods are currently known that attempt to break the RSA system in this way. However, in special cases where multiple related messages are encrypted with the same small exponent, it may be possible to recover the messages.

The attacks just mentioned are the only ways to break the RSA cryptosystem in such a way as to be able to recover all messages encrypted under a given key. There are other methods, however, that aim to recover single messages; success would not enable the attacker to recover other messages encrypted with the same key.

The simplest single-message attack is the guessed plaintext attack. An attacker sees a cipher text and guesses that the message might be, for example, “Attack at dawn”, and encrypts this guess with the public key of the recipient and by comparison with the actual cipher text, the attacker knows whether or not the guess was correct. Appending some random bits to the message can thwart this attack. Another single-message attack can occur if someone sends the same message m to three others, who each have public exponent e = 3. An attacker who knows this and sees the three messages will be able to recover the message m. Fortunately, padding the message before each encryption with some random bits can also defeat this attack. There are also some chosen cipher text attacks (or chosen message attacks for signature forgery), in which the attacker creates some cipher text and gets to see the corresponding plaintext, perhaps by tricking a legitimate user into decrypting a fake message.

There are also attacks that aim not at the cryptosystem itself but at a given insecure implementation of the system; these do not count as “breaking” the RSA system, because it is not any weakness in the RSA algorithm that is exploited, but rather a weakness in a specific implementation. For example, if someone stores a private key insecurely, an attacker may discover it. One cannot emphasize strongly enough that to be truly secure, the RSA cryptosystem requires a secure implementation; mathematical security measures, such as choosing a long key size, are not enough. In practice, most successful attacks will likely be aimed at insecure implementations and at the key management stages of an RSA system.

RSA IN PRIVACY

In practice, the RSA system is often used together with a secret-key cryptosystem, such as DES, to encrypt a message by means of an RSA digital envelope.

Suppose Alice wishes to send an encrypted message to Bob. She first encrypts the message with DES, using a randomly chosen DES key. Then she looks up Bob’s public key and uses it to encrypt the DES key. The DES-encrypted message and the RSA-encrypted DES key together form the RSA digital envelope and are sent to Bob. Upon receiving the digital envelope, Bob decrypts the DES key with his private key, and then uses the DES key to decrypt the message itself. This combines the high speed of DES with the key management convenience of the RSA system.

RSA for authentication and digital signatures

The RSA public-key cryptosystem can be used to authenticate or identify another person or entity. The reason it works well is because each entity has an associated private key which (theoretically) no one else has access to. This allows for positive and unique identification.

Suppose Alice wishes to send a signed message to Bob. She applies a hash function to the message to create a message digest, which serves as a “digital fingerprint” of the message. She then encrypts the message digest with her private key, creating the digital signature she sends to Bob along with the message itself. Bob, upon receiving the message and signature, decrypts the signature with Alice’s public key to recover the message digest. He then hashes the message with the same hash function Alice used and compares the result to the message digest decrypted from the signature. If they are exactly equal, the signature has been successfully verified and he can be confident the message did indeed come from Alice. If they are not equal, then the message either originated elsewhere or was altered after it was signed, and he rejects the message. Anybody who reads the message can verify the signature. This does not satisfy situations where Alice wishes to retain the secrecy of the document. In this case she may wish to sign the document, then encrypt it using Bob’s public key. Bob will then need to decrypt using his private key and verify the signature on the recovered message using Alice’s public key. Alternately, if it is necessary for intermediary third parties to validate the integrity of the message without being able to decrypt its content, a message digest may be computed on the encrypted message, rather than on its plaintext form.

In practice, the public exponent in the RSA algorithm is usually much smaller than the private exponent. This means that verification of a signature is faster than signing. This is desirable because a message will be signed by an individual only once, but the signature may be verified many times.

It must be infeasible for anyone either to find a message that hashes to a given value or to find two messages that hash to the same value. If either were feasible, an intruder could attach a false message onto Alice’s signature. Hash functions such as MD5 and SHA have been designed specifically to have the property that finding a match is infeasible, and are therefore considered suitable for use in cryptography.

One or more certificates may accompany a digital signature. A certificate is a signed document that binds the public key to the identity of a party. Its purpose is to prevent someone from impersonating someone else. If a certificate is present, the recipient (or a third party) can check that the public key belongs to a named party, assuming the certifier’s public key is itself trusted.

RSA USED CURRENTLY

The RSA system is currently used in a wide variety of products, platforms, and industries around the world. It is found in many commercial software products and is planned to be in many more. The RSA algorithm is built into current operating systems by Microsoft, Apple, Sun, and Novell. In hardware, the RSA algorithm can be found in secure telephones, on Ethernet network cards, and on smart cards. In addition, the algorithm is incorporated into all of the major protocols for secure Internet communications, including S/MIME, SSL, and S/WAN. It is also used internally in many institutions, including branches of the U.S. government, major corporations, national laboratories, and universities.

RSA AS an official standard

The RSA cryptosystem is part of many official standards worldwide. The ISO (International Standards Organization) 9796 standard lists RSA as a compatible cryptographic algorithm, as does the ITU-T X.509 security standard. The RSA system is part of the Society for Worldwide Interlake Financial Telecommunications (SWIFT) standard, the French financial industry’s ETEBAC 5 standard, the ANSI X9.31 rDSA standard and the X9.44 draft standard for the U.S. banking industry. The Australian key management standard, AS2805.6.5.3, also specifies the RSA system.

The RSA algorithm is found in Internet standards and proposed protocols including S/MIME, IPSec, and TLS (the Internet standards-track successor to SSL), as well as in the PKCS standard for the software industry. The OSI Implementers’ Workshop (OIW) has issued implementers’ agreements referring to PKCS, which includes RSA.

A number of other standards are currently being developed and will be announced over the next few years; many are expected to include the RSA algorithm as either an endorsed or a recommended system for privacy and/or authentication. For example, IEEE P1363 and WAP WTLS include the RSA system.

RSA AS a de facto standard

The RSA system is the most widely used public-key cryptosystem today and has often been called a de facto standard. Regardless of the official standards, the existence of a de facto standard is extremely important for the development of a digital economy. If one public-key system is used everywhere for authentication, then signed digital documents can be exchanged between users in different nations using different software on different platforms; this interoperability is necessary for a true digital economy to develop. Adoption of the RSA system has grown to the extent that standards are being written to accommodate it. When the leading vendors of U.S. financial industry were developing standards for digital signatures, they first developed ANSI X9.30 in 1997 to support the federal requirement of using the Digital Signature Standard. One year later they added ANSI X9.31, whose emphasis is on RSA digital signatures to support the de facto standard of financial institutions.

The lack of secure authentication has been a major obstacle in achieving the promise that computers would replace paper; paper is still necessary almost everywhere for contracts, checks, official letters, legal documents, and identification. With this core of necessary paper transaction, it has not been feasible to evolve completely into a society based on electronic transactions. A digital signature is the exact tool necessary to convert the most essential paper-based documents to digital electronic media. Digital signatures make it possible for passports, college transcripts, wills, leases, checks and voter registration forms to exist in the electronic form; any paper version would just be a “copy” of the electronic original. The accepted standard for digital signatures has enabled all of this to happen.

RSA ALGORITHM

• Choose two (in practice, large 100 digit) prime numbers p and q and let n = pq.
• Let Pi be the block of (plain) text to be encrypted. Actually Pi is the numerical equivalent of the text which may either be single letters or blocks of letters, just as long as.
Pi < (p-1)(q-1)= Ф(n)
• Choose a random value E (usually small) such that E is relatively prime to Error! Unknown switch argument.. Then the encrypted text is calculated from

Ci=PiE mod(n)

• The pair of values (n,E) act as the public key.
• To decode the ciphertext, we need to find an exponent D, which is known only to the person decoding the message, such that
DE= 1 mod((p-1)(q-1))
• Note that Ф(n)=Ф(pq)=(p-1)(q-1) Then we may calculate
C­­­iD=(PiE)D =PiDE =Pi mod(n)
• This step is based on the following result:
(ax)y = axy = az mod(n)
• where  z=xy mod(Ф(n))Show that this result is true.

By Euler’s theorem

EФ(Ф(n)) =1 mod (Ф(n))

provided E and Error! Unknown switch argument.are relatively prime, which is true by the choice of E. So we obtain

DE= 1 mod (Ф(n))
DE= EФ(Ф(n)) mod(Ф(n))
DE= EФ(Ф(n))-1 mod(Ф(n))

Example of RSA Algorithm

We have chosen p=3 and q=11, giving n=33 and z=20. A suitable value for d is d=7, since 7 and 20 have no common factors. With these choices, e can be found by solving the equation 7e=1 (mod 20), which yields e=3. The cipher text, C, for a plain text message, P, is given by C=P3 (mod 33). The cipher text is decrypted by the receiver according to the rule P=C7 (mod 33).

Because the primes chosen for this example are so small, P must be less than 33, so each plain text block can contain only a single character. The result is a monoalphabetic substitution cipher, not very impressive.

The example of the RSA algorithm:

###### Symbolic
S 19 6859 28 1342928512 19 S
U 21 9261 21 1801088541 21 U
Z 26 17576 20 1280000000 26 Z
A 01 1 1 1 1 A
N 14 2744 5 78125 14 N
N 14 2744 5 78125 14 N
E 05 125 26 8031810176 5 E

COMPARISON BETWEEN PUBLIC-KEY CRYPTOGRAPHY OVER SECRET-KEY CRYPTOGRAPHY

The primary advantage of public-key cryptography is increased security and convenience: private keys never need to be transmitted or revealed to anyone. In a secret-key system, by contrast, the secret keys must be transmitted (either manually or through a communication channel) since the same key is used for encryption and decryption. A serious concern is that there may be a chance that an enemy can discover the secret key during transmission.

Another major advantage of public-key systems is that they can provide digital signatures that cannot be repudiated. Authentication via secret-key systems requires the sharing of some secret and sometimes requires trust of a third party as well. As a result, a sender can repudiate a previously authenticated message by claiming the shared secret was somehow compromised by one of the parties sharing the secret.

For example, the Koreros secret-key authentication system involves a central database that keeps copies of the secret keys of all users; an attack on the database would allow widespread forgery. Public-key authentication, on the other hand, prevents this type of repudiation; each user has sole responsibility for protecting his or her private key. This property of public-key authentication is often called non-repudiation.

A disadvantage of using public-key cryptography for encryption is speed. There are many secret-key encryption methods that are significantly faster than any currently available public-key encryption method. Nevertheless, public-key cryptography can be used with secret-key cryptography to get the best of both worlds. For encryption, the best solution is to combine public- and secret-key systems in order to get both the security advantages of public-key systems and the speed advantages of secret-key systems. Such a protocol is called a digital envelope.

Public-key cryptography may be vulnerable to impersonation, even if users’ private keys are not available. A successful attack on a certification authority will allow an adversary to impersonate whomever he or she chooses by using a public-key certificate from the compromised authority to bind a key of the adversary’s choice to the name of another user.

In some situations, public-key cryptography is not necessary and secret-key cryptography alone is sufficient. These include environments where secure secret key distribution can take place. For example, users meet in private. It also includes environments where a single authority knows and manages all the keys, For example, a closed banking system. Since the authority knows everyone’s keys already, there is not much advantage for some to be “public” and others to be “private”. Note, however, that such a system may become impractical if the number of users becomes large; there are not necessarily any such limitations in a public-key system.

Public-key cryptography is usually not necessary in a single-user environment. For example, if you want to keep your personal files encrypted, you can do so with any secret key encryption algorithm using, say, your personal password as the secret key. In general, public-key cryptography is best suited for an open multi-user environment.

Public-key cryptography is not meant to replace secret-key cryptography, but rather to supplement it, to make it more secure. The first use of public-key techniques was for secure key establishment in a secret-key system; this is still one of its primary functions. Secret-key cryptography remains extremely important and is the subject of much ongoing study and research. Some secret-key cryptosystems are discussed in the sections on block ciphers and stream ciphers.

CONCLUSION of RSA

RSA, as a public key cryptosystem, is quite speedy and efficient. It removes the overhead of key distribution and also provides good speed. It is good technique for the data security on network or on the standalone system. Where the Encryption & Decryption is very easy to understand and make it easy for the user.

CURRENT TRENDS

ELLIPTIC CURVES

Elliptic curves are mathematical constructions from number theory and algebraic geometry, which in recent years have found numerous applications in cryptography.

An elliptic curve can be defined over any field (for example, real, rational, complex), though elliptic curves used in cryptography are mainly defined over finite fields. An elliptic curve consists of elements (x, y) satisfying the equation,

y2 = x3 + ax + b

Together with a single element denoted O called the “point at infinity”, which can be visualized as the point at the top and bottom of every vertical line. The elliptic curve formula is slightly different for some fields.

The set of points on an elliptic curve forms a group under addition, where addition of two points on an elliptic curve is defined according to a set of simple rules. For example, consider the two points p1 and p2. Point p1 plus point p2 is equal to point p4 = (x, -y), where (x, y) = p3 is the third point on the intersection of the elliptic curve and the line L through p1 and p2. The addition operation in an elliptic curve is the counterpart to modular multiplication in common public-key cryptosystems, and multiple additions are the counterpart to exponentiation.

Lattice-based cryptosystems

Lattice-based cryptosystems are based on NP-complete problems involving lattices. A lattice can be viewed as the set of all linear combinations with integral coefficients of a specified set of elements in a vector space. An example of a lattice is the infinite square grid in 2-dimensional space consisting of all points with integral coordinates. This lattice is generated by integral linear combinations of the vectors (0,1) and (1,0).

Lattice-based methods fall into two basic classes, although the solution methods for both are identical. In fact, there are efficient transformations between the two classes.

Other lattice-based methods require finding short vectors embedded in a lattice or finding points in the vector space close to vertices of the lattice or close to vectors embedded in the lattice

So far lattice-based methods have not proven effective as a foundation for public-key methods. In order for a lattice-based cryptosystem to be secure, the dimension of the underlying problem has to be large. This results in a large key size, rendering encryption and decryption quite slow. Ongoing research aims to improve the efficiency of these cryptosystems.

DSA AND DSS

The National Institute of Standards and Technology (NIST) published the Digital Signature Algorithm (DSA) in the Digital Signature Standard (DSS), which is a part of the U.S. government’s Capstone project. DSS was selected by NIST, in cooperation with the NSA, to be the digital authentication standard of the U.S. government. The standard was issued in May 1994.

DSA is based on the discrete logarithm problem and is related to signature schemes that were proposed by Schnorr and ElGamal. While the RSA system can be used for both encryption and digital signatures the DSA can only be used to provide digital signatures.

In DSA, signature generation is faster than signature verification, whereas with the RSA algorithm, signature verification is very much faster than signature generation (if the public and private exponents, respectively, are chosen for this property, which is the usual case). It might be claimed that it is advantageous for signing to be the faster operation, but since in many applications a piece of digital information is signed once, but verified often, it may well be more advantageous to have faster verification. Wiener has explored the tradeoffs and issues involved. There has been work by many authors including Naccache et al. on developing techniques to improve the efficiency of DSA, both for signing and verification.

Although several aspects of DSA have been criticized since its announcement, it is being incorporated into a number of systems and specifications. Initial criticism focused on a few main issues: it lacked the flexibility of the RSA cryptosystem; verification of signatures with DSA was too slow; the existence of a second authentication mechanism was likely to cause hardship to computer hardware and software vendors, who had already standardized on the RSA algorithm; and that the process by which NIST chose DSA was too secretive and arbitrary, with too much influence wielded by the NSA. Other criticisms more related to the security of the scheme were addressed by NIST by modifying the original proposal.

DSA SECURITY

The Digital Signature Standard was originally proposed by NIST with a fixed 512-bit key size. After much criticism that this is not secure enough, especially for long-term security, NIST revised DSS to allow key sizes up to 1024 bits. In fact, even larger key sizes are now allowed in ANSI X9.31. DSA is, at present, considered to be secure with 1024-bit keys.

DSA makes use of computation of discrete logarithms in certain subgroups in the finite field GF (p) for some prime p. Schnorr first proposed the problem for cryptographic use in 1989. No efficient attacks have yet been reported on this form of the discrete logarithm problem.

Some researchers warned about the existence of “trapdoor” primes in DSA, which could enable a key to be easily broken. These trapdoor primes are relatively rare and easily avoided if proper key-generation procedures are followed.

ECC COMPARED WITH OTHER CRYPTOSYSTEMS

The main attraction of elliptic curve cryptosystems over other public-key cryptosystems is the fact that they are based on a different, hard problem. This may lead to smaller key sizes and better performance in certain public key operations for the same level of security.

Very roughly speaking, when this FAQ was published elliptic curve cryptosystems with a 160-bit key offer the same security of the RSA system and discrete logarithm based systems with a 1024-bit key. As a result, the length of the public key and private key is much shorter in elliptic curve cryptosystems. In terms of speed, however, it is quite difficult to give a quantitative comparison, partly because of the various optimization techniques one can apply to different systems. It is perhaps fair to say the following: Elliptic curve cryptosystems are faster than the corresponding discrete logarithm based systems. Elliptic curve cryptosystems are faster than the RSA system in signing and decryption, but slower in signature verification and encryption.

GLOSSARY

CRYPTANALYSIS: -The art of breaking ciphers is called cryptanalysis.

CRYPTOLOGY: -The art of devising ciphers and breaking them is collectively known as cryptology.

ENCRYPTION: -Encryption is the process of translating plain text data into something that appears to be random & meaningless (cipher text).

DECRYPTION: -Decryption of data is the process of converting the cipher text back to plain text.

AUTHENTICATION: -Authentication is any process through which one proves and verifies certain information.

DIGITAL ENVELOPE: -The digital envelope consists of a message encrypted using secret-key cryptography and an encrypted secret key.

SECRET KEY CRYPTOGRAPHY: -It is the more traditional form of cryptography, in which a single key can be used to encrypt and decrypt a message.

BLOCK CIPHER: – A block cipher is a type of symmetric-key encryption algorithm that transforms a fixed-length block of plain text (unencrypted text) data into a block of cipher text (encrypted text) data of the same length.

MAC: -A message authentication code (MAC) is an authentication tag derived by applying an authentication scheme, together with a secret key, to a message.

RSA: -The RSA cryptosystem is a public-key cryptosystem that offers both encryption and digital signatures (authentication).

Comparison of RSA and Pohling-Hellman:-

 Operation RSA System Pohlig-Hellman Encryption Operation C = Me mod n C = Me mod p Decryption Operation M = Ce mod n M = Ce mod p Modulus p * q (prime numbers) p (prime number) Encryption exponent (e) e relatively prime to(p-1)*(q-1) e relatively prime to (p-1) Decryption exponent (d) d = e-1 mod ((p-1)*(q-1)) d = e-1 mod (p-1)
Featured

# DUKPT Explained with examples

Derived Unique Key Per Transaction (DUKPT) process that’s described in Annex A of ANS X9.24-2004.

It’s generally considered to be complex, but I’ve simplified it slightly with the help of online resources.

## Key Management

Here’s a basic outline of the technique:

1. You’re given a Base Derivation Key (BDK), which you assign to a swiper (note that the same BDK can be assigned to multiple swipers).
2. You’ll use the BDK along with the device’s own unique Key Serial Number (KSN) to generate an Initial PIN Encryption Key (IPEK) for the device.
3. You’ll assign this IPEK to a swiper, which uses it to irreversibly generate a list of future keys, which it’ll use to encrypt its messages.
4. The swiper’s KSN is used along with one of its future keys to encrypt a message, and after each swipe it’ll increment the value of its KSN.
5. Whenever a swiper takes a card it formats the card’s information into a series of tracks, each track having a particular set of information (e.g. card number, holder’s name, expiration date).
6. The swiper usually encrypts these tracks using one of its generated future keys (called the “Session Key”) along with its current KSN. It’ll then increment the value of its KSN and discard the future key it used.
7. At this point you’ll probably have an encrypted track along with the KSN the swiper used to encrypt it.
8. It’s your responsibility to determine what BDK was used to initialize this device, and from there you’ll use the BDK and KSN to rederive the IPEK, which is used to rederive the Session Key, which is finally used to decrypt the message.

There’s a lot of technical information to be said about key management, but this isn’t the place for that. In some cases your provider/manufacturer (e.g. MagTek) will supply you with swipers that need to be initialized with an IPEK, and your supplier will usually have a manual that walks you through that process. If you’re doing encryption/decryption through a third party who also supplies swipers, they may have already loaded the devices with that information; what’s more is they may not even given you the BDK that belongs to your device in order to reduce the risk of security threats.

Note: Key management is beyond the scope of this explanation. Whatever you do with your keys, just make sure it’s secure.

One methodology I’ve seen that’ll allow you to associate a particular KSN to a BDK is to take the current KSN you’ve been given, mask it to retrieve the Initial Key Serial Number (IKSN), and look up the BDK in a table that maps IKSNs to BDKs:

Example:

ksn = FFFF9876543210E00008
iksn = ksn & FFFFFFFFFFFFFFE00000 // FFFF9876543210E00000


You’d then have a table that looks like:

IKSN BDK
0xFFFF9876543210E00000 0123456789ABCDEFFEDCBA9876543210

From which you could easily grab the BDK 0123456789ABCDEFFEDCBA9876543210.

## Algorithm

Note: Assume that all numeric values are hexadecimal numbers, or the representation of a sequence of bytes as a hexadecimal number.

The following are the BDK, KSN, and encrypted track message (cryptogram) we’ve been given:

bdk = 0123456789ABCDEFFEDCBA9876543210
ksn = FFFF9876543210E00008


Here’s an example of the unencrypted track 1 data (cryptogram above), and below that is its value in hex; this is what we’ll get after successfully decrypting the cryptogram:

%B5452300551227189^HOGAN/PAUL      ^08043210000000725000000?
2542353435323330303535313232373138395E484F47414E2F5041554C2020202020205E30383034333231303030303030303732353030303030303F00000000


Note: As you’re probably already aware, this algorithm is best described using big numbers, which can’t be represented as literals in some programming languages (like Java or C#). However, many languages have classes that allow you to represent big numbers in other ways (e.g., java.math.BigInteger, System.Numerics.BigInteger). It’s your job to adapt this algorithm so that it can be represented in your language of choice. Two small problems I encountered were ensuring the correct endianness and signedness were being used (this algorithm requires the byte order to be big endian and that unsigned integers are used). I made a utility class called BigInt to do this for me.

First, let’s define a few standard functions:

• DES and Triple DES refer to their respective cryptographic algorithms. Most programming languages have access to some implementation of these ciphers either through OpenSSL or Bouncy Castle. These ciphers are initialized with a zeroed out IV of 8 bytes, they’re zero-padded, and use Cipher-Block Chaining (CBC). Let’s define the signatures for these standard functions that’ll be used throughout this algorithm:
• DesEncrypt(key, message) -> returns cryptogram
• DesDecrypt(key, cryptogram) -> returns message
• TripleDesEncrypt(key, message) -> returns cryptogram
• TripleDesDecrypt(key, cryptogram) -> returns message

First we must create the IPEK given then KSN and BDK:

CreateIpek(ksn, bdk) {
return TripleDesEncrypt(bdk, (ksn & KsnMask) >> 16) << 64
| TripleDesEncrypt(bdk ^ KeyMask, (ksn & KsnMask) >> 16)
}


Now we can get the IPEK:

ipek = CreateIpek(ksn, bdk)
= CreateIpek(FFFF9876543210E00008, 0123456789ABCDEFFEDCBA9876543210)
= 6AC292FAA1315B4D858AB3A3D7D5933A


After that we need a way to get the Session Key (this one is more complicated):

CreateSessionKey(ipek, ksn) {
return DeriveKey(ipek, ksn) ^ FF00000000000000FF
}


The DeriveKey method finds the IKSN and generates session keys until it gets to the one that corresponds to the current KSN. We define this method as:

DeriveKey(ipek, ksn) {
ksnReg = ksn & FFFFFFFFFFE00000
curKey = ipek
for (shiftReg = 0x100000; shiftReg > 0; shiftReg >>= 1)
if ((shiftReg & ksn & 1FFFFF) > 0)
curKey = GenerateKey(curKey, ksnReg |= shiftReg)
return curKey
}


Where the GenerateKey method looks like:

GenerateKey(key, ksn) {
return EncryptRegister(key ^ KeyMask, ksn) << 64
| EncryptRegister(key, ksn)
}


And EncryptRegister looks like:

EncryptRegister(key, reg) {
return (key & FFFFFFFFFFFFFFFF) ^ DesEncrypt((key & FFFFFFFFFFFFFFFF0000000000000000) >> 64,
key & FFFFFFFFFFFFFFFF ^ reg)
}


Then you can generate the Session Key given the IPEK and KSN:

key = CreateSessionKey(ipek, ksn)
= CreateSessionKey(6AC292FAA1315B4D858AB3A3D7D5933A, FFFF9876543210E00008)
= 27F66D5244FF621EAA6F6120EDEB427F


Which can be used to decrypt the cryptogram:

message = TripleDesDecrypt(key, cryptogram)
= 2542353435323330303535313232373138395E484F47414E2F5041554C2020202020205E30383034333231303030303030303732353030303030303F00000000
= %B5452300551227189^HOGAN/PAUL      ^08043210000000725000000?


That’s it, you’re done!

Featured

# EFTPOS Initialisation using RSA Cryptography

Before you start with RSA, you should generate a public and private key pair using your HSM. These can be group keys or specific to the terminal you need to connect. Your terminal manufacturer will also provide its public key and modulus. Using these keys you will be able to calculate the TMK1 and TMK2 and also your session keys. The process is in fact very simple.

Here is an example of how to create these keys using a Thales HSM

Generating an 1536 bit RSA Key

Input

001-EI2153601

Output

001-EJ00
Public Key
3081C80281C0A0FAFB1789B87F6F075B04FE60B5F20AC9D658E6C9B9B4E82AD41FD748A5A00CAF0A5691D2D01726AB073AFB7B91810430F240244E0D4737A397C747FC67C622B12E3654DCDF4F58EE29241616AE7EBA08A1E16DB79E09529FB6CA92213F2DFAB3F677793BF977D640107FBF9833842A0BFBF5F871709E78EE5A152E0BBBBBDDED80D193BAC3033FE412B3C420532A8B309942E76F7A9FB4475B8EDEFDDADC4C101FF02F74BEE0261C681E314124654C39411E2CE56FE719A45CA7592B8431D30203010001
Private key length
0488
Private Key
4E79F95F16AFF16278A893722DA94C8EBFEB013126EC0E98C9CBCBD99DB6D4E82336BD33631CB859D0506D4C2B69DAB818AEE965E73417006774DD746033A6F6EEC1AE3C823E3E20561C84B26885D9D9AE66A552864C75E2B8759B6909DA13CFE70FCB31358A56711549FB2ECC20E4EC3227309D074AE85307C98CF234AF115183716461A701E9FF877F118A5187C27D96B33BE88851ED75D71760DF671CBBA15F1EA7F54CC6205B6997669B6ED9C7448C3D0F451E229E44CC5474462D161A5A89E3D6A473080A8C734E4D5440D2E2A6530D5A848B8B2A0EE637ECF8F604D89449EA9922E115885C8024F6B765C16285C2FC5631CC8C437885170E96CD1D2CB748E4B7FE7FC40517705BC96C22C278BD15CEB51E4D49A722C09237E164D5091EBE847629488180972A1EF6626619B7A16F720D725EFB5C1164E44F915024414BEBF6CE6D258275398D35F38FDC2354F16CEECB7DA77D0E5EC3317D05B351D6938C888A88A9B588C8E88518EFD7581075CD6AA206690E865CA528D5BED5151B9BCAB892CCA49F43349F9F28C5502FC8CA5D2B6D84E57169AAD665961F28797995891B6520822134DBC92ADE13F4D154F520B5BD6EBEBF3620C3CEF941CF7A2302431FEB68C0093A0EE7CF14433F2E9E1A403E545FA96B4BF580D4C17FC26C6E93DADC23738B37E917

Generate a MAC on 1536 RSA key

Input

002-EO01<3081C80281C0A0FAFB1789B87F6F075B04FE60B5F20AC9D658E6C9B9B4E82AD41FD748A5A00CAF0A5691D2D01726AB073AFB7B91810430F240244E0D4737A397C747FC67C622B12E3654DCDF4F58EE29241616AE7EBA08A1E16DB79E09529FB6CA92213F2DFAB3F677793BF977D640107FBF9833842A0BFBF5F871709E78EE5A152E0BBBBBDDED80D193BAC3033FE412B3C420532A8B309942E76F7A9FB4475B8EDEFDDADC4C101FF02F74BEE0261C681E314124654C39411E2CE56FE719A45CA7592B8431D30203010001>

Output

002-EP00<C905141E><3081C80281C0A0FAFB1789B87F6F075B04FE60B5F20AC9D658E6C9B9B4E82AD41FD748A5A00CAF0A5691D2D01726AB073AFB7B91810430F240244E0D4737A397C747FC67C622B12E3654DCDF4F58EE29241616AE7EBA08A1E16DB79E09529FB6CA92213F2DFAB3F677793BF977D640107FBF9833842A0BFBF5F871709E78EE5A152E0BBBBBDDED80D193BAC3033FE412B3C420532A8B309942E76F7A9FB4475B8EDEFDDADC4C101FF02F74BEE0261C681E314124654C39411E2CE56FE719A45CA7592B8431D30203010101>

This is a generic version of RSA encryption using POS pinheads, there are variations in the field. Please keep that in mind when reading this.

Now when a POS terminal logs on for the first time it shall always logon using a 9820 message with a network management information code of 191, containing the TCU public key signed by the manufacturer’s secret key, and the un-enciphered PPID.

The Financial Switch shall respond with a 9830 message with the same network management information code, communicating the public key of the sponsor host (PKsp), and a random number.

The PIN Pad shall then generate the KI and send a 9820 message with a network management information code of 192 to the Financial Switch, containing the KI, PPID, date & time stamp, the random number and user data enciphered under the Financial Switch’s public key (PKsp) and signed by the TCU’s secret key (SKtcu). You will need to extract this information using your HSM H8 command, example below:

Input Data:

001-H801<FDC694A6>
<30550250AB378F98E373BBC6FA5E698F4F095A6D693A851E53C35CC9633947399C09D70932776DBEA5F2F0F0C4DAB4693CACB4D07B19242FF0435C55E3D4E28EFD563457F7EBA31BE1123DEA78CEC1573716130B020103>
;990192
<99658789F42672E7C51CB6ECAF3F061BBABCD954D4113E1CD9BD7BD4DF1BD94E6CBC10F497E9AE68265E87F77BFF293AA2D9FDE9C1A8F12A04D9B4D8DB9F5EAEE4690883838DEF670174E70C79E674F97E2457DD85EEEB346A17DD1F39CB3E8B2D69949436051994F8687F0FEE6558F28180D5A63946CD60604B1C82F6AE14454F5824CBFDCEE07478D2F0239299B64CD900DFF7559423E98F0C7AB8229933E4DD5A5E0BD736F8172668676949493577E323FC8EC592437F6DF20EDB5FBB6E92>
;0080
;1234567890123456;000

Response:

001-H900
H604A678C8C78E1B9CFD415220D418E76
U9912C5D8B113B5E9D6787D57EE9E43BA
1122334455
9876543210987654

The Financial Switch shall check the PPID and random number. If the check fails, it will respond with a 9830 with a response code of “63”.

Where the Financial Switch is satisfied with the contents of the second 9820 message, it shall respond with the KCA and the KMACH enciphered under KI and its AIIC in the clear. When the PIN Pad has deciphered KCA and KMACH, it shall erase KI.

At this time the PIN Pad shall calculate the KIA. When the KIA has been calculated, the PIN Pad shall erase KCA.

The POS terminal shall then generate a 9820 message with a network management information code of 193 to the Financial Switch containing the PPID and the Financial Switch shall respond with a 9830 response containing the two initial KEKs and the PPASN.

You can generate this using the C0/C1 HSM command.

The POS terminal shall validate the MAC on the two KEKs and the PPASN and, if the MAC is valid, shall install KEK1, KEK2 and the PPASN and shall calculate the single length DES key KMACI. These keys are the terminal initial keys, that will updated in the season key exchange.

Once this has been carried out, the PIN Pad shall erase the KIA.

When these tasks have been completed, the POS terminal shall carry out its normal logon and session key installation with the Financial Switch. As the processing (initial logon then normal logon and session key installation) completes, the POS terminal will move into the “Ready” state.

easy as pie!

Featured

# ATM Pin encryption using 3DES

## Introduction

Most modern ATM’s use a Triple Des algorithm to encrypt the pin and send it to a host server for processing. Once the host system receives the pin, it does a translation of the pin from one encryption key to another, and sends it to a bank. In this post I will attempt to explain the process and how it is done in the real world.

## Overview of the Triple Data Encryption Standard

What we all call Triple DES is EDE (encrypt, decrypt, encrypt). The way that it works is that you take three 56-bit keys, and encrypt with K1, decrypt with K2 and encrypt with K3. There are two-key and three-key versions. Think of the two-key version as merely one where K1=K3. Note that if K1=K2=K3, then Triple DES is really Single DES.

Triple DES was created back when DES was getting a bit weaker than people were comfortable with. As a result, they wanted an easy way to get more strength. In a system dependent on DES, making a composite function out of multiple DESes is likely to be easier than bolting in a new cipher and sidesteps the political issue of arguing that the new cipher is better than DES.

As it turns out, when you compose a cipher into a new one, you can’t use a double enciphering. There is a class of attacks called meet-in-the-middle attacks, in which you encrypt from one end, decrypt from the other, and start looking for collisions (things that give you the same answer). With sufficient memory, Double DES (or any other cipher) would only be twice as strong as the base cipher — or one bit more in strength.

There’s more to it. If the cipher forms a group, then encrypting twice with two keys is equivalent to encrypting once with some key. Now, it’s not trivial to know what that other key is, but it means that a brute-force attack would find that third key as it tried all possible single-keys. So if the cipher’s a group, then multiple-ciphering is merely a waste of time.

Applying this encryption in Python is trivial as there are plenty of tested libraries that can provide the functionality like pyDes and Crypto :

import os
from Crypto.Cipher import DES3

def encrypt_file(in_filename, out_filename, chunk_size, key, iv):
des3 = DES3.new(key, DES3.MODE_CFB, iv)

with open(in_filename, 'r') as in_file:
with open(out_filename, 'w') as out_file:
while True:
if len(chunk) == 0:
break
elif len(chunk) % 16 != 0:
chunk += ' ' * (16 - len(chunk) % 16)
out_file.write(des3.encrypt(chunk))

def decrypt_file(in_filename, out_filename, chunk_size, key, iv):
des3 = DES3.new(key, DES3.MODE_CFB, iv)

with open(in_filename, 'r') as in_file:
with open(out_filename, 'w') as out_file:
while True:
if len(chunk) == 0:
break
out_file.write(des3.decrypt(chunk))

## ATM Internals and how they calculate the keys

When you have an ATM, you typically need to provide it with a set of encryption keys from your host, or HSM. These keys are clear text keys and it’s not encrypted in any way. Your host will link them to your terminal number, and when the ATM encrypts the pin; the host will know what keys are used so it can decrypt / translate them to the bank. The clear keys are never stored by the host, only the LMK encrypted keys.

Lets assume your host provides the following keys to you as the ‘ATM Encryption Key’ :

Clear component A: 67C4 A719 1ADA FD08 6432 CE0D D638 4AB
Key check value: 20D40B
Clear component B: 8A89 6D4C 4625 5E2A 1A75 2002 07A7 D35E
Key check value: 4EC801
Combined Check Value: 2B547D

Now typically you would enter the clear components into the ATM, as Encryption keys, and the ATM will combine them (Basically XOR Them) and derive the check value. If the check value match, then all is good.

What happens at your host end is the following:

Your host will also combine the keys and encrypt them under the LMK (Local Master Key). It will then use this key to encrypt all other keys that are sent to the ATM.

Now the ATM have a Terminal Master Key that it can use to decrypt all keys that are sent to it from the host.

## ATM Configuration Request (Key Exchange)

Now when an ATM starts up, the first thing it does it send a configuration request to the host. This request is to get the Third key used in Triple DES.  The Host will generate a random Terminal Pin Key and encrypt it under the Terminal Master Key (TMK). Since the ATM has the Terminal Master Key, it can decrypt the encrypted TPK, and use all 3 Keys now for the Triple DES operations. (it actually uses 2)

The Host would generally execute the A0 Thales command to get this key. He would store the key in the key database to do the decryption / translation later.

## Pin Encryption / Decryption

When a ATM gets ready to transmit a transaction it does the 3DES operation on the Pin only. the cypher text is now transmitted to the host. The host never knows the pin code, and only does a translation of the pin from the terminal keys to the bank keys.

The Host will have the following:

(ZPK) Zone Pin Key – from the Bank during Host to Bank Key exchange

(TPK) Terminal Pin Key – from Terminal using Terminal Configuration Request

(PAN) Account Number –  from Transaction transmitted.

With these values, the Host can translate the pin using a HSM, below is an example of the D4 Command.

 Res = KeyGenerator.TranslatePIN_TDES(TerminalPINKey=self.Crypto["TPK_LMK"], PINEncryptionKey=self.HostKeys["ZPK_LMK"], PINBlock=self.iso.getBit(52), AccountNumber=track2["PAN"][-13:-1])

def get_commandTPKPinBlock(self, TerminalPINKey, PINEncryptionKey, PINBlock, AccountNumber):

command_code = 'D4'
KTP = TerminalPINKey
KPE = PINEncryptionKey
PinBlock = PINBlock
PAN = AccountNumber

message = command_code
message += KTP
message += KPE
message += PinBlock
message += PAN
return message
#transmit to HSM

The transaction can now be transmitted to the acquiring bank with the translated pin for processing.

Sometimes the ATM requires a Message Authentication Code, this will be covered in another post.

easy as pie