Month: February 2017

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)

 

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