University of Sheffield
MSc Cybersecurity and Artificial Intelligence
COM6014 Fundamental Security Properties and Mechanisms
Assignment 1. Cryptographic Analysis Task Report (100 Marks) Issued: Tuesday 17 November 2020
Online submission deadline: 1500 on Tuesday 8 December 2020.
Q1 Implementing Linear Cryptanalysis of Four Rounds of the Heys Cipher (80 Marks)
The file FourRounds.txt (issued as part of this assignment) contains 10000 plaintext-ciphertext pairs, with plaintexts and ciphertexts expressed as non-negative integers.
Each integer should be interpreted as a 16-bit block in the standard binary representation. Thus, an integer value of 5 should be interpreted as the 16-bit block 0000 0000 0000 0101, an integer value of 131 should be interpreted as the 16-bit block 0000 0000 1000 0011, and so on.
The data in the FourRounds.txt file is in two columns: the first column contains the plaintext values and the second contains the corresponding ciphertext values.
The encryption has been carried out using the block cipher from the document titled ¡°Tutorial on Linear and Differential Cryptanalysis¡± by Howard Heys. This tutorial document is also provided with this assignment. On page 12 onwards of the tutorial document Heys develops an example of a linear approximation over three rounds and describes how it can be used to discover 8 bits of the final round key (k5). The 8 bits targeted are k5,5- k5,8 and k5,13 – k5,16.
I. Using the 3-round linear approximation given by Heys and the data provided in FourRounds.txt recover the targeted 8 bits of the final round key. You should:
a. Write a program to implement the procedure to recover the targeted final round key bits. This will include all helper code, e.g. to read in data and write results to file.
[25 Marks]
b. Provide comments in your code to enable the reader to understand it. [5 Marks]
c. Run your code and tabulate your results. Indicate the most likely value of the targeted 8 bits (and why). [10 Marks]
II. Derive a further linear approximation (or possibly two) that allows you to recover the remaining 8 bits of the final round key. You should indicate clearly which S-boxes are ¡®active¡¯ in your approximation, what the approximations for individual active S-boxes are, what the biases of those approximations are, and how your approximations link up to form a 3-round linear approximation. You should state clearly the 3-round approximation and the probability it holds (i.e., the probability it is true). A structure diagram for the Heys block cipher is provided with this assignment. You should annotate this diagram (or a similar diagram of your own) to convey as much of this information as possible, e.g. by highlighting active S-boxes and their linkages in some way and providing suitable annotations. [10 Marks]
(You can develop an approximation that targets 8 bits, or two separate approximations that target 4 bits each. Your resulting approximations must exhibit suitable biases, whatever approach is adopted.)
III. Using the linear approximation(s) in (II) above and the data provided in FourRounds.txt, recover the remaining 8 bits of the final round key. Run your code and tabulate your results. Indicate the most likely value of the remaining 8 bits (and why). [5 Marks]
Note: you will have to change your code a little (or perhaps supply different parameters, depending on implementation). Provide any amended code you have developed for this part of the task (suitably commented).
IV. Explain briefly how you would now recover the remaining four keys. [3 Marks]
[You are required to explain how. You are not required to actually recover any further keys.]
V. Suppose now that you have recovered all 5 round keys using your method described above. Using those recovered key values, you now encrypt the original 10000 plaintext blocks but find that the resulting ciphertexts are not the same as those in the FourRounds.txt file. Why might this be the case? How can you modify your procedure to find (or give better chances of finding) the actual keys used?
[7 Marks]
VI. What changes could you make to the block cipher to make it more resilient against linear cryptanalysis? Explain why your suggestions would make the system more difficult to break.
[10 Marks]
VII. For the same targeted ¡®remaining bits¡¯ above, i.e., k5,1- k5,4 and k5,9 – k5,12, develop a suitable three-round differential approximation. Provide the analogous information to that in (II) above in the same way, i.e., using the structure diagram, S-box highlighting, annotations etc.
[5 Marks]
2
Note: you are not required to implement (code) any aspect of differential cryptanalysis.
Your script for this question should separate out main text and code. The code should be placed in an appendix together with any further contextual information needed to run it.
Q2 Attacking a Stream Cipher (20 Marks)
Here you are required to carry various preliminary analyses and indicate how
you could attack a stream cipher and how you can strengthen the cipher.
The truth table for a Boolean function f(x1, x2, x3) on three variables x1, x2, and x3 is given below. It forms the basis of a classical combining cipher, where the input streams for x1, x2, and x3 are supplied by three Linear Feedback Shift Registers (LFSRs) that are clocked synchronously. LFSR1 produces the stream for x1, LFSR2 produces the stream for x2, and LFSR3 produces the stream for x3. The corresponding keystream bit produced is given by f(x1, x2, x3). The ¡®key¡¯ for the given cryptosystem comprises the initial state of LFSR1, the initial state of LFSR2 and the initial state of LFSR3.
(i) Analyse the truth table to determine the degree of agreement between each of the inputs x1, x2, and x3 and the keystream f(x1, x2, x3).
[4 Marks]
(ii) Explain how you would attack this system to recover the initial states of all three registers.
[6 Marks]
(iii)Using Walsh Hadamard Transform values F(w) of the function f(x1,x2,x3) specify constraints that prevent a direct correlation attack on any single register. Explain why.
[4 Marks]
(iv) Briefly describe two further changes to the cipher that would increase its resilience to attack. (These should be reasonable changes to the current cipher. Replacing the cipher with a radically different one, for example, is
x1x2x3
f(x1,x2,x3)
x1x2x3
f(x1,x2,x3)
000
1
100
0
001
0
101
1
010
0
110
0
011
1
111
1
not an appropriate change.]
[6 Marks]
3
4