cryptopals solution. Part 1

Often, when studying cryptography, the emphasis is on theory, leaving the practical part aside. Exercises Matasano Crypto Challenges cryptopals This is a great option to improve your practical skills. On the one hand, you can start with a minimum of prior knowledge. On the other hand, all important topics are covered using examples of real attacks.

In this part we will look at task blocks 1 and 2.

Block 1: Basic

Themes: Basic knowledge, xor cipher
Link: https://cryptopals.com/sets/1

Task 1: Convert hex to base64

A simple preparatory task – you need to implement a coding standard Base64. It will be needed later to display binary data in a readable form.

Task 2: Fixed XOR

Also a simple preparatory task – you need to implement the function xor for byte arrays.

Task 3: Single-byte XOR cipher

The condition requires decrypting a text encrypted with a xor cipher with a key one byte long.
First, you need to come up with some kind of “closeness” metric to the English text for the decrypted data. Then, using it, determine the desired text.

We will use the function as a metric for the decrypted text:

– text
– English letters that are present in the text
— letter frequency in the decrypted text
– reference frequency of letters in English texts

The text for which the metric value is minimal will be the searched text.

Task 4: Detect single-character XOR

In the task you need to determine which text among those presented is encrypted with an xor cipher with a key one byte long.
We apply the code from the previous task to each text and, among all decrypted texts, select the one with the lowest metric value. Interestingly, a successful solution really depends on the quality of the metric and on the reference probabilities, because the list contains texts with a distribution of letters close to the usual one.

Task 5: Implement repeating-key XOR

A slight complication of Task 3: now a key of several bytes is used for encryption instead of a single-byte key.

Task 6: Break repeating-key XOR

This is the first real task. You need to decrypt text encrypted with a xor cipher with a multibyte key.

Solution:

1. Determining the key length

2. We divide the text into blocks so that one block includes characters that are encrypted on the same byte of the key

3. We decrypt each block and collect a key from the received bytes

4. Decrypt the text using the received key

The Hamming distance of two bit strings is the number of bits in which these strings differ

We will use the Hamming distance as a measure of “randomness” for bit strings, since the Hamming distance for two lines of English text will on average differ from the distance for two random lines. To compare strings of different lengths, we will use the relative Hamming distance, i.e. the distance divided by the length of the string.

To determine the key length, we go through the possible key length (according to the condition, the key length lies in the range from 2 to 40) and calculate the relative Hamming distance between text blocks. The length at which the minimum Hamming distance is obtained will be the required one.

Once the key length is found, the text is split into blocks so that each block contains all the bytes that are encrypted on the same byte of the key.
We have already cracked such a cipher in Task 3. Using the same method for each block, we obtain all the bytes of the key and decrypt the text.

Task 7: AES in ECB mode

Preparatory task, you need to decrypt a message encrypted with AES-128-ECB. It is better to implement the ECB mode yourself rather than using ready-made utilities, because it will be needed in the future.

Task 8: Detect AES in ECB mode

In the task, among the messages presented, you need to find one that is encrypted with AES-ECB.

AES in ECB mode encrypts message blocks one after another independently. If there are two identical blocks in the plaintext, then they will also be identical in the ciphertext. This drawback of the ECB mode is demonstrated by the task. We are looking for text that contains repeating blocks.

The task is not very well formulated, because in text that is not encrypted with AES-ECB, there may also be duplicate blocks. It can only be solved due to the fact that there is exactly one such text in the task.

Block 2: Block crypto

Subject: Block ciphers
Link: https://cryptopals.com/sets/2

Task 9: Implement PKCS#7 padding

Preparatory task. Need to implement an add-on PKCS#7. The padding works using a simple algorithm: n bytes with the value n are added to the end of the message. That is, the correct additions are:

0x01
0x02 0x02
0x03 0x03 0x03
...

Task 10: Implement CBC mode

You need to implement AES encryption in CBC mode using the results of Task 7. The task introduces the CBC encryption mode.

Encryption formula:

Decryption formula:

Task 11: An ECB/CBC detection oracle

This is a slightly more complicated Task 8, only now you need to distinguish between messages encrypted by AES-ECB and AES-CBC. The idea is the same: a cipher in ECB mode will have the same blocks of plaintext after encryption, but a cipher in CBC mode will have different blocks.

Task 12: Byte-at-a-time ECB decryption (Simple)

This is the first assignment dedicated to a real cryptographic vulnerability. It demonstrates the weakness of the encryption scheme:

AES-128-ECB(your_string || unknown_string, key) 

In ECB mode, each block is processed separately. The idea is as follows: let the entire block of plaintext, except the last byte, and the corresponding block of ciphertext be known. In this case, you can brute-force recover the unknown byte in the plaintext.

Solution:

1. We generate a message that consists of identical characters and whose length is one byte shorter than the full block: “AAAA…AA”

2. We send this message to the oracle and receive the ciphertext

3. Now we go through all possible bytes: add a byte to the end of the message and send the complete block “AAAA…AA”, “AAAA…AB”, “AAAA…AC”, “AAAA…AD”,…

4. If the byte matches the first byte of unknown_stringthen the same ciphertext will be obtained as in the second step

5. Continuing the actions for the remaining symbols, we completely restore unknown_string

Task 13: ECB cut-and-paste

The challenge demonstrates that ECB mode is vulnerable to block replacement/deletion attacks.

First you need to get the block ciphertext admin\0xb...\0xb — the line “admin” + PKCS7 padding to the full block. To do this, we transmit to the oracle an email consisting of 10 arbitrary characters and the string “admin\0xb…\0xb”. Then the plaintext blocks will be:

email=A...A — 1 block
admin\0xb...\0xb — 2 block
&uid=10&role=user – other blocks

The result of encrypting the second block is the encrypted block we need.

Now we provide the oracle with an arbitrary email consisting of 13 characters as input. The resulting plaintext blocks will be:
email=...&uid=10&role= — 1 and 2 blocks
user... — 3 block

In the ciphertext, we replace the last block with the previously received encrypted block admin\0xb...\0xb and we get the answer.

In a task, writing preparatory functions takes more time than solving it and distracts from the main idea. Should have made it less bulky.

Task 14: Byte-at-a-time ECB decryption (Harder)

This is a slightly more complicated version of Task 12. The difference is that now a random line is added before the text. If the length of the string is known, then you can use the attack from Task 12, which means the main difficulty is figuring out the length.

Similar to Problem 9, the length can be determined from duplicate blocks in the ciphertext:

1. We begin to transmit texts “A”, “AA”, “AAA”, …

2. At some point the plaintext will look like (P – the bytes of the starting line) PP..PAA|A...A|A....A|,

3. The ciphertext generated from this plaintext will have two identical blocks. As soon as this happens, we determine the length

4. Next we repeat the attack from Task 12

Task 15: PKCS#7 padding validation

In Task 9 you had to implement a PKCS7 padding, and in this task you need to implement a check for the correctness of the padding. It was worth combining them.

Task 16: CBC bitflipping attacks

The task demonstrates the properties of CBC mode when flipping a bit in a ciphertext block:

1. The entire block will be decrypted incorrectly

2. In the next decrypted block, the bit at the same position from the beginning of the block will be inverted

3. This will not affect other blocks

The property follows directly from the formula for decryption in CBC mode. The difficulty of the task is that we need to get the line in the decrypted text ;admin=true;, but use the symbols “;” and “=” is not possible directly, therefore:

1. Passing the string XadminYtrueXAAAA“X” in place of “;”, “Y” in place of “=”, “AAAA” – addition to a complete block

2. Let’s change the bits of the previous ciphertext block so that when decrypting in the next block, “X”->“;”, “Y”->“=” will be replaced.

This task again has an unnecessarily complex preparatory part that distracts from the main idea.

Solution code in python: https://github.com/seregablog/cryptopals

My Telegram channel