DIT250/TDA352-Homework 4 Translation-based Block Cipher Solved

 

A code implementation
A report in which the block cipher design is explained in detail so that other people can re-implement the cipher. The report has to contain:All the design choices made by the group, e. functions, permutations, implementations, etc.
Answers to some specific questions contained in this document
Test vectors that allows anyone to verify the correct implementation of the block cipher.
The learning objective of the assignment is to let the group understand how complex is the process required in the standardization process for a cryptographic primitive.

0. Introduction
Cryptography seems to be a very interesting and “cool world” since it provides cryptographic primitives that can be used to guarantee secure communication. It might seem that everyone can create his own cryptographic primitives and, for example, home-brew its own blockcipher!

This should not be the case.

In fact, there are different standardization processes, like AES[1], NESSIE[2] or the current CAESAR[3], in order to define which block cipher is more secure, efficient and should be used.

The standardization process is in fact a competition, like a crypto-Hunger Game! Different research teams design their own primitives, register them in the contest and then the goal is to break the ciphers submitted by each research team.

Only one design will remain and will be recommended by the standardisation process to be used.

Designing cryptographic primitives is hard. But why?

In this assignment we will go through the process of designing a toy block cipher.

1. Translation Based Block Ciphers
A block cipher is defined by an encryption algorithm E and a decryption algorithm D acting on a fixed length bit-string {0,1}n of length n.

E takes as input a message msg and a key k and encrypts it into a ciphertext ct.

D takes a ciphertext ct and a key k and outputs a message msg.

The main property we require is that, whenever we fix a key k, the decryption algorithm D is the inverse of the encryption E with the same key. Formally D(k,E(k,msg)) = msg.

Notation: Let k denote the concatenation operator. If a and b are bit-strings, akb is the concatenation of the two strings. Let ⊕ be the xor operation.

In this assignment, we consider the translation based (TB) block-ciphers (or known as substitution-permutation) as depicted in Figure 1.

Figure 1: Encryption algorithm of a TB block cipher.

A TB block-cipher is an iterated block-cipher design. This means that the blockcipher is defined with a round function R that is iterated for a specific number of round r. In this way, it is just necessary to define the round function R and the number of rounds r in order to completely describe an iterated block-cipher. We define the i-th partial ciphertext cti the output of the i-th round function.

A mandatory algorithm used in block-ciphers is the key-scheduler H. This algorithm takes a key k and returns a finite list of keys {k0,k1,...,kr} called round-keys. It is important to notice that the number of keys is r+1 where r refers to the number of rounds and the “+1” key, the k0 key, is xored with the original message.

Therefore, the message msg is xored with the round-key k0, then the i-th round will use the i-th round-key ki.

What defines an iterated block-cipher into a translation-based is the specific composition of the round. A TB round is defined using a permutation map S on short bit-substrings and then a linear map P over the whole message space.

This means that the TB block-cipher is defined over the message space of bit-string {0,1}n of length n. In the beginning of the round, the partial ciphertext cti−1 is subdivided into m sub-strings of dimension l, namely cti−1[1]k...kcti[l]. In parallel, every sub-string is mapped via the permutation S which is a permutation over {0,1}l (“short bit-substring” since l < n) obtaining what we call S(cti−1) = S(cti−1[1])kS(cti−1[2])k...kS(cti−1[m]). Finally, we concatenate the whole message and apply the linear map P defined over {0,1}n and xor the round key ki obtaining P(S(cti−1)) ⊕ ki which is the new partial ciphertext cti.

Therefore, by having the key scheduler H, a specific number of rounds r, a design for the round function R using a permutation map S and a linear map P, it is possible to completely define a TB block-cipher.

Note: it is still necessary to fix the message and key length, n long bit-string, and the dimension l of the permutation map S. Observe, and/or convince yourself, that it is implicit that the length of the messages is equal to the dimension of the permutation map multiplied by the number of them, i.e. n = l · m.

By combining all these notions, it is possible to formally define a TB-block cipher:

Definition 1. Let the message space M, the ciphertext space C and the key space K be the set of bit-strings of length {0,1}n. Let l and m be positive integers such that n = l · m. Consider a permutation S : {0,1}l → {0,1}l a bit-string of length l and a linear transformation P : {0,1}n → {0,1}n. Let r be a positive integer indicating the number of rounds. Consider the key scheduler H : K → Kr+1 that takes as input a key k and return a set of round-keys {k0,k1,...,kr} with index i. A translation-based block-cipher (E,D) is defined by the length of the bit-string used l,m,n, the number of rounds r, the specific permutation/linear map S,P and a key scheduler H. A sketch representation of the cipher construction can be seen in Figure 1.

Before the rounds:
The message msg is xor-ed with the key k0. The result is the partial ciphertext ct0.

For any round i ∈ {1,...,r}:
The round function R(i,cti−1,ki) is the i-th round function that takes as input the i− 1-th partial ciphertext and the i-th round key ki. The partial ciphertext cti is splitted into m substrings of length l, cti−1 = cti−1[1]kcti−1[2]k...kcti−1[m] and on every substring, the permutation S is computed obtaining S(cti−1[1])kS(cti−1[2])k...kS(cti−1[m]) that we can denote with S(cti−1). Afterwards, the result is mapped via the linear map P and then the round key ki is xor-ed with the result obtaining P(S(cti−1)) ⊕ ki. The result is the partial ciphertext cti.

After the rounds:
The final ciphertext ct is the final partial ciphertext ctr.

In the “wild” there are a lot of attacks and design principles for block ciphers. We hardly recommend to just give a look to Avanzi’s book “A Salad of Block Ciphers”[4] that contains a state-of-the-art discussion and explanation on how to design a block-cipher, how to prove the security, which are the faulty design choice and a lot of different implementation of real block ciphers.

1. Project Specification
In order to easily represent the boxes S and P, we will consider the octal5 numerical system and represent numbers with a subscript 8. For example, 1238 is in fact the number 83 = 1 · 82 + 2 · 81 + 3 · 80 or, in binary, (001 010 011)2.

Notice that the binary representation has the most-significant bit on the left!

                                                 (100)2 = 8          (010)2 = 2          (001)2 = 1

Question 1: Is there a way to quickly change from octal to binary representation and viceversa?

For the sake of simplicity, your goal is to design a 18-bit translation-based block cipher with a substitution box S of 6-bits. The message, ciphertext and key space is {0,1}18. The key-scheduler H : K → Kr+1 is given and it is recursively defined using the octal permutation φ as defined in the Table 1.

x
08
18
28
38
48
58
68
78
φ(x)
38
58
78
18
28
08
68
48
Table 1: φ permutation used in the key-scheduler H.

The first round-key k0 is equal to the input key k. Then, given i-th round-key ki, the (i+1)th round-key ki+1 is obtained by converting the bit-string into the octal representation, applying octal-wise the permutation φ and reverse the string before re-joining the pieces.

Formally,

                                   k                       (1)

For example, if the round-key is ki = (012345)8, then the next round-key ki+1 is

Question 2: What is the 12-th round-key k12 obtained by the key-scheduler H from the input key k  ? Do you think that the key-scheduler H is good? Why?

As stated in Definition 1, we have defined l,m,n and H.

It is now your choice to define/design the substitution box S : {0,1}6 → {0,1}6 the linear map P : {0,1}18 → {0,1}18 and the number of rounds r.

We highly suggest you to define the S in octal notation, similarly to the permutation φ.

Question 3: How can you verify that your S is in fact a correct substitution box?

(Hint: What does it mean “substituting”?)

To simplify the notation in our case, permutations can be written as a octal string by just writing the ordered outputs of the permutation.

For example, let us consider the general description for S in Table 2 where every octal input x will be sent to two octal numbers NNx. By just considering the S line, we can

x
00
01
...
07
10
11
·
77
S(x)
NN00
NN01
...
NN07
NN10
NN11
·
NN77
S = NN00kNN01k...kNN07kNN10kNN11k · kNN77

Table 2: S permutation notation trick.

just represent the S map with the octal string obtained by concatenating the outputs, which is NN00kNN01k...kNN07kNN10kNN11k · kNN77. As a concrete example, the permutation used for the key scheduler φ can be denoted as φ = 35712064.

In order to design the linear map P, let us start with an example and consider a small map λ : {0,1}3 → {0,1}3 defined as the multiplication of x with a specific bit-matrix. x is an octal number, therefore it is represented with 3 bits x = (x1 x2 x3)2.

If we compute the row-column multiplication, we obtain

Now, if we consider the input x = (101)2, we have that λ(x) = (001)2.

In order to compress the notation, we can represent the matrix in octal-notation too! We can take the bit-string and read them as “up-to-down” columns and change them to octal notation. In our example, we obtain that λ can be represented as

A longer bit string will have a longer octal representation. We highly suggest for your project to use the octal-notation. You final matrix will therefore will therefore be represented as a 6·18 = 108 octal-numbers written in a 6 rows and 18 column table that can be compressed into a single octal-string that is the concatenation of the rows. As an example, let us consider the matrix η and the procedure to obtain a compressed representation.

The only requirement for the matrix λ is to be invertible6. In our example, the inverse map λ−1 is λ−1 = 375.

Question 4: Why does the linear map have to be invertible?

(Hint: We are now describing the “encryption” algorithm. What about the “decryption”?)

5https://en.wikipedia.org/wiki/Octal

6https://en.wikipedia.org/wiki/Invertible matrix

If everything went well, you should now have a substitution box S and an invertible linear matrix to be used into the linear map P.

Question 5: How confident are you about the security of your S and P? Are they secure? Can you prove it?

The last missing piece is a number of rounds r. Pick whatever number you prefer!

Question 6: Which is a good number of round? Do you think that it is more secure to have r 50 or r 5 is enough?

Congratulations! You now have designed a TB block cipher!

The next step is to explain what you have chosen, why these specific functions and how you might allow other to re-implement your cipher.

2. General Specification Report
In order to better understand the requirement, please take a look at the structure of the specification for the PRESENT-Toy[5] or LED8 block ciphers. Other examples can be easily be found on-line.

The design-report is the blueprint of your cipher. It has to be easy to read and understand, it has to contain all the information needed to re-implement it. For this reason, the report should be well-structured and should contains:

Notation used: the designers notation used in their report;
S and P: it is mandatory to clearly state and define S and P. It is mandatory to explain how designers have chosen these functions;
Security/Efficiency discussion: in this section, designers explain and motivate their choices, either using mathematical proofs or empirical tests. In the next section;
Test Vectors: in order to check if the implementation is correct.
Regarding the last point, test vectors are really important to verify the correctness of an implementation. There is no standard way to provide test-vectors. you could provide either test vector for a complete encryption:

input message msg + input key k −→ output ciphertext ct

or the partial output of every round:

input message msg + input key k −→ round outputs

By providing a good list of vectors (msg,k,ct), or (msg,k,(ct0,ct1,...,ctr)), anyone can test the correct implementation.

To better explain the test-vector importance, let us consider the following example, the key-scheduler H you have to use in your project and some test-vector to verify the correct implementation of H.

Let us consider the key k = 012345.

By the definition of H, we have that k0 = k = 012345. Afterwards, k1 = 534602 and it is obtained by applying Equation 1 and related instruction in the same section.

A list of test-vector that you can use to check the correct implementation of the key scheduler H is, in octal notation, contained in Table 3.

000000
000000
333333
111111
555555
000000
333333
111111
555555
000000
111111
111111
555555
000000
333333
111111
555555
000000
333333
111111
012345
012345
021753
104573
140235
017325
071453
102543
120735
014375
120735
120735
014375
041253
107523
170435
012345
021753
104573
140235
104573
104573
140235
017325
071453
102543
120735
014375
041253
107523
041253
041253
107523
170435
012345
021753
104573
140235
017325
071453
017325
017325
071453
102543
120735
014375
041253
107523
170435
012345
Table 3: Key-scheduler H test-vectors.

As you might expect, in order to provide the test vectors, it is necessary to have a code implementation of your cipher. Therefore, you will have to include it. It is mandatory that the code is commented, clean and easy to use.

 Your Specification Report!
Of course it is quite hard to write the third section about “Security”. That is why your report must contain, as separate sections:

Notation used: you will need a section where you have to explain the octal notation, how your block cipher is designed, e. translation-based;
S and P: state and describe your functions
Answer to the assignment questions
Test Vectors Table: 3-4 vectors in the format (msg,k,ct) and the partial evaluations, for all the r rounds, of the message msg = (00 00 00)8 with key k = (00 00 00)8.
The test-vector table will therefore have the format represented in Table 4.

mmmmmm
kkkkkk
cccccc
mmmmmm
kkkkkk
cccccc
mmmmmm
kkkkkk
cccccc
mmmmmm
kkkkkk
cccccc
                              msg           k               ct0                ct1                ct2             ...          ctr                 ct

000000
000000
cccccc
cccccc
cccccc
...
cccccc
cccccc
Table 4: Format for the final report test-vector.

[1] https://en.wikipedia.org/wiki/Advanced Encryption Standard process

[2] https://en.wikipedia.org/wiki/NESSIE

[3] https://competitions.cr.yp.to/caesar.html

[4] https://eprint.iacr.org/2016/1171.pdf

[5] https://pdfs.semanticscholar.org/7082/7ac50fa184893fe68314d741b8b85baba36e.pdf 8https://eprint.iacr.org/2012/600.pdf