Laboratory Exercises II: Symmetric and Asymmetric Cryptography

Introduction

In this set of exercises we will study the basics of symmetric (secret key) and asymmetric (public key) cryptography. For this purpose, we will use CrypTool, an excellent program by means of which cryptographic functions and mechanisms can be easily demonstrated and analyzed. We will learn about both classical and modern cryptography. We will begin our study with a couple of exercises related to classical ciphers such as Caesar's and Vernam. Using CrypTool, we will demonstrate their weaknesses and limitations. Then, we will focus on modern ciphers, primarily Data Encryption Standard (DES), and on basic operation modes of block ciphers such as Electronic Codebook (EBC) and Cipher Block Chaining (CBC). The "cut-and-paste" attack against EBC and CBC will be demonstrated. Finally, in the last set of exercises we will study basic public key cryptosystems RSA and Di?e-Hellman.

Exercise 1 -

In this exercise we will demonstrate and study two representatives of classical ciphers, namelly, Caesar's cipher and Vernam (one-time pad) cipher. We will also perform cryptanalysis of a simple permutation cipher.

Recall, Caesar's cipher falls in the category of monoalphabetic substitution ciphers (i.e., each element from the plaintext will be replaced with a unique element from the space of ciphertexts). For this reason, a cipehertext preserves the relative frequency at which plaintext elements appear in the corresponding plaintext. In Vernam cipher encryption is performed by means of eXclusive-OR (XOR) logical operation (plaintext is XORed with an encryption key). If an encryption key is chosen randomly and is at least as long as the plaintext to be encrypted, XOR encryption (one-time pad) is provably (perfectly) secure.

Task 1.1. Caesar's Cipher

1. Given that the Caesar's cipher is used, recover the plaintext that corresponds to the following ciphertext: Sodlqwhaw wr eh hqfubswhg. Describe your approach to cryptanalysis of the ciphertext. (Try to recover the plaintext without assistance of CrypTool.)

2. Use CrypTool to check your answer to the ?rst challenge (task). In order to do this, you should ?rst create a new document in CrypTool by clicking on the icon "New" (or choose "File . New"). Write the challenge ciphertext in a newly open document. In the main menu, under "Analysis" tab, select "Symmetric Encryption (classic) . Ciphertext only . Caesar" and follow the instructions.

3. Assume that we choose M (that is, K=13) as an encryption key in Caesar's cipher. What is the result (Ci) of the following (double) encryption

C_i = E (K,E(K, M_i)),

where M_i is an arbitrary plaintext element? Explain your answer.

How many encryptions with key K=2 is needed before observing the same effect as in the previous example (with K=13)?

Task 1.2. Vernam and One-Time Pad Cipher

1. Consider the following letter encodings:

A message M = MARIO is Vernam encrypted into ciphertext C = AOAMV. Find the corresponding encryption key (please note that the key is 4 letters long). Provide details of your cryptanalysis.

2. Consider the following two ciphertexts C₁= MAOEE and C₂=RTITR that are obtained by Vernam encrypting messages M₁ and M₂, respectively, under the same encryption key. The letter encodings is the same as in the ?rst task. Encrypted messages are two names. Let us denote with m_i,k the kth  letter in message M_i. The following is known about messages (names): m_1,1=R and m_2,4=T. Using this information, try to recover messages M₁ and M₂, as well as the encryption key. Provide details of your cryptanalysis.

Task 1.3. Monoalphabetic Substitution Cipher

This type of a cipher is similar to the Caesar's cipher, i.e. every letter of the plaintext is replaced by a different letter of the alphabet, with the di?erence that the encryption key can be any permutation of the plaintext elements. In this way the key space increases from 26 (in the case of Caesar's cipher) to 26!. This cipher, however, is still vulnerable to the"relative frequency"-based attack.

Your task is to decrypt the following message that was encrypted using a monoalphabetic substitution cipher.

Exercise 2 -

In this exercise we will focus on modern ciphers, primarily on the most prominent block cipher DES. We will study a relationship between DES and its extension 3-DES (triple DES). Recall, 3-DES was introduced in order to compensate for a short encryption key (only 56 bits) in the original DES cipher. 3-DES is still widely used for protection of data con?dentiality. In October 2000, Rijndael encryption algorithm (AES) was chosen as a more robust and more flexible replacement of the DES encryption algorithm. Similar to DES, AES is also a block cipher but it supports a variable block length and a variable key length (i.e., 128, 192 and 256 bits).

We will further study two basic operation modes of block ciphers, namely, ECB and CBC. More speci?cally, we will show that it is possible to rearrange the ECB and CBC ciphertext blocks in such a way that all (or some) of the blocks decrypt correctly. This is a well-known cut-and-paste attack.

Task 2.1. Histogram Analysis of the Data Encryption Standard

In this task we compare a frequency histogram of a document before and after encryption with the DES cipher. We use CrypTool to accomplish this. Quoting CrypTool help: "The histogram of a document expresses the frequency distribution of the characters of a document in graphical form in a corresponding window."

Create a new document in CrtypTool and fill it with a longer English text. Alternatively, open an existing English text. Save this document for later reference.

1. In the main menu, click on the "View" submenu and select "As HexDump". This is to convert ASCII representation of the plaintext document into the corresponding hexadecimal representation.

2. In the main menu, open the "Analysis" submenu and select "Tools for Analysis. Histogram" to obtain the histogram of the plaintext (un-encrypted) document (Figure 4). Save the result.

3. Encrypt the plaintext document (English text) using the DES cipher. In CrypTool click on the window with the plaintext document in order to make it active. In the main menu, under the "Crypt/Decrypt" submenu select "Symmetric (modern). DES CBC...". Enter the encryption key and encrypt the plaintext document.

4. Repeat step 2 above to obtain the histogram of the encrypted text (ciphertext). Compare the result with the histogram obtained in step 2. Describe/explain your observations.

Task 2.2. Histogram Analysis of the Caesar's Cihper

Repeat all the steps from the previous task, while using Caesar's cihper with an arbitrary key instead of the DES cipher. Compare the obtained results with the results from the previous task. Describe/explain your observations.

Task 2.3. Triple DES (3-DES)

1. Assume that a message m is encrypted using 3-DES (in the ECB mode) with the following key (hex value):

K = 11 22 33 44 55 66 77 88 AA BB CC DD EE FF FF FF

The encrypted message is to be decrypted using only regular 1-DES (not 3-DES). Explain how is this done.

2. Use CrypTool and encrypt your name with 3-DES in the ECB mode under the following two encryption keys:

K₁ = 11 22 33 44 55 66 77 88 AA BB CC DD EE FF FF FF

K₂ = 11 22 33 44 55 66 77 88 11 22 33 44 55 66 77 88

Decrypt resulting ciphertexts using 1-DES cipher. Provide any intermediate results that you obtain. One among the keys K1 and K2 enables "fast" decryption with the 1-DES cipher (a single application of 1-DES).Which one? Please explain your answer.

Task 2.4. "Cut-and-Paste" Attack on ECB and CBC Modes

Let us denote with M1 M2... Mk a message M broken up into k 64 bit segments. Also, let us denote with K the corresponding encryption key. Then, the ECB encryption mode can be mathematically described as follows:

C_i = E(K, M_i), i = {1, 2, . . . , k}

M_i = D(K, C_i), i = {1, 2, . . . , k} .

Similarly, for the CBC mode we have:

C₁ = E(K, M1 ⊕ IV)

C_i = E(K, M_i ⊕ C_i-1), i = {2, 3, . . . , k}

M₁ = D(K, C₁) ⊕ IV

Mi = D(K, C_i) ⊕ C_i-1, i = {2, 3, . . . , k} .

1. Consider the following message M:

M=Bob's salary is $25000--Tom's salary is $15000.

Break the message (plaintext) up into 64 bit long plaintext segments (M₁ M₂...M_k). Note that each letter in the message is an 8 bit ASCII character; each "space" (blank) counts as a single ASCII character. Use t sign to denote blank characters. For example, the ?rst 64 bit plaintext segment is M1=Bob'stsa.

2. Using CrypTool, encrypt the above message with DES in the ECB mode using key K = 11 22 33 44 55 66 77 88. Write down resulting 64 bit ciphertext blocks C₁ C₂... C_k.

3. Exchange ciphertext blocks C₁ and C₄ in the above sequence of ciphertext blocks to obtain the following sequence of ciphertext blocks:

C₄ C₂ C₃ C₁ C₅... C_k

Decrypt the resulting ciphertext using the key from step 2. What message do you obtain? Please explain.

4. Repeat steps 1-3 but now use DES in the CBC mode. Contrast the decrypted text with the one obtained when the ECB mode is used. Explain your observations.

Task 2.5. Controlled Plaintext Changes in the CBC Mode

Your task is to cause a controlled change in the decrypted message by modifying an appropriate CBC ciphertext block.

1. Use CrypTool and encrypt message

M=Bob's salary is $25000--Tom's salary is $15000.

with DES in the CBC mode. Choose the encryption key at will.

2. In the resulting ciphertext sequence modify an appropriate ciphertext block so that it causes the following change in the decrypted message: $15000 → $.5000.

Provide details of your actions. (Hint: Use CrypTool to accomplish this task.)

3. Do all ciphertext blocks decrypt correctly after this modi?cation? Explain your answer.

4. Does the CBC (and/or ECB) mode of encryption ensure data integrity? Please explain using experience gained from the present and the previous task.

Exercise 3 -

In this exercise we will focus on asymmetric or public key cryptography. We will study some important properties of a (textbook) RSA public key cryptosystem. We will demonstrate certain attacks against RSA - "factoring-based" and "chosen-ciphertext" attack. Finally, we will touch upon the Diffie-Hellman key exchange protocol and its security in face of passive and active attacks.

Task 3.1. RSA Encryption

The RSA encryption algorithm works with numbers. As your task is to encrypt some textual messages, we obviously need a method for coding of a message into numbers. We next describe one such a method that is used in CrypTool. The method is called b-adic (where b is the number of plaintext elements) and works as follows. Suppose that the plaintext alphabet consists the following elements:

ABCDEFGHIJKLMNOPQRSTUVWXYZ,

1. You are asked to encrypt your name using RSA with a small modulus N (that is, N < 100000). Choose N such that the length of the resulting RSA modulus N allows you to work with blocks of length 2.

2. Show that CrypTool RSA encryption works by encrypting the first block of the message "manually". You are allowed to use only multiplication and squaring operations (and of course your calculator). In order to make this process manageable, use "reduction by modulo" property, that is,

(a × b) mod N ≡ ((a mod N) × (b mod N)) mod N.

Provide the steps of your calculation.

3. After decryption of a given ciphertext, we have to decode the result back to its initial plaintext representation. How would you do this? Decode 354 into a plaintext alphabet ABCDEFGHIJKLMNOPQRSTUVWXYZ, assuming the block length of 2 and 27-adic coding.

Task 3.2. Chosen Ciphertext Attack on RSA

This is an attack against the textbook version of the RSA algorithm. In this attack, an attacker first chooses a message and encrypts it the victim's public key. Then, the attacker asks the victim to sign (decrypt) for him a specially crafted related message. Due to the following property of RSA

E(PU, M₁) × E(PU, M₂) = E(PU, M₁ × M₂) ,

the attacker can easily recover any message encrypted with the victim's private key, without ever learning this private key.

For example, the attacker wants to decrypt the following ciphertext C = M^e mod N, without knowing the private key d. The attacker proceeds as follows. Knowing the victim's public key e, he prepares the following message

X = (C × 2^e) mod N,

gives it to the victim and asks her to sign it. The victim signs message X with its private key and sends the result Y back to the attacker.

Y = X^d mod N

Using Y and equation (1), the attacker can retrieve the encrypted message M as follows:

X^d = ((C mod N) × (2^e mod N))^d

     = ((M^e mod N) × (2^e mod N))^d

        = ((2 ×M)^e mod N)^d

     = (2 ×M)^ed mod N

     = 2 × M.

1. Show by example that equation (1) holds for the RSA encryption algorithm. Please provide details of your solution. Use CrypTool to accomplish this task.

2. Demonstrate by example the chosen ciphertext attack against RSA. Please provide details of your solution. Use CrypTool to accomplish this task.

Task 3.3. Attack on RSA by Factoring Modulus N

By factoring the RSA modulus N, the attacker learn prime numbers p and q. From this, the attack can calculate Euler's Φ(N) function as follows

Φ(N) = (p - 1)(q - 1) .

Furthermore, the public key e is also known by the attacker. Therefore, he can calculate the corresponding private key d, which is the inverse modulo Φ(N) of e, that is,

d = e^-1(mod Φ(N)).

1. Decrypt the ciphertext given below knowing that the public key e is 11 and the RSA modulus N is 40741. The plaintext alphabet is encrypted using the block length of 2 and 27-adic coding (for details on encoding please check Task 3.1).

Task 3.4. Diffie-Hellman Key Exchange Protocol

1. The Diffie-Hellman protocol is secure against passive (eavesdropping) attacks. Explain why.

2. Describe a possible man-in-the-middle (MITM) attack on the Diffie-Hellman protocol and explain its consequences.

Attachment:- Symmetric and Asymmetric Cryptography Assignment.rar