COM6014 Assignment 1
Cryptographic Analysis Task
Issued: 13 November 2021
Deadline for submission via MOLE: 1500 on the 9 December 2021.
Total Marks Available 100.
The marks for this assessment make up 50% of
the total marks available for the module.
Answer both questions.
Any queries on this assignment should be raised via the “Assessment discussion forum”.
Question 1. Classical Stream Cipher Design (40 Marks)
You are required to design a classical combining cipher with four Linear Feedback Shift Registers (LFSRs) providing inputs to a combining function. You should assume that the lengths of LFSR1, LFSR2, LFSR3 and LFSR4 are 7, 11, 17, and 19, respectively.
You should:
a) identify suitable feedback functions for the four LFSRs. You should argue why they are suitable, i.e. show what desirable property/properties they have. You should:
i. specify a criterion for suitability [2 Marks]
ii. present 4 suitable feedback functions [8 Marks]
You will have to consult the literature to complete this.
b) identify a suitable 4-input Boolean function f(x1,x2, x3, x4) for the combining function. In particular, this function should not be susceptible to any single register correlation attack and you must check whether this is the case. Marks are awarded as follows:
i. specify the criteria for suitability.
You should express these both informally but also as constraints over specific Walsh Hadamard values for the function. [3 Marks]
ii. present the truth table for f(x1,x2, x3, x4). [2 Marks]
iii. check whether f(x1,x2, x3, x4) satisfies or does not satisfy the specified criteria.
You should present your working for showing that a correlation attack on LFSR1 is not possible. You should use the jacsjar program made available with this assessment to produce a full analysis of your function (which you should include with your answer). For each specified criterion draw attention to the relevant element in the printout and indicate whether the criterion is met or not. [5 Marks]
c) Explain how a correlation-based attack of some form can nevertheless be launched to recover the key (i.e. the initial states of the LFSRs) and what the computational complexity of the attack is. You can refer to the printout generated earlier using jacsjar to help you. [15 Marks]
d) The non-linearity of a Boolean function f on four inputs is given by the formula:
where ranges over 0000..1111.
High non-linearity is also a desirable property of Boolean combining functions. How might you find a function with the highest possible nonlinearity for a Boolean function satisfying the above requirements? [5 Marks]
You are free to reference/use any public source, including lecture notes, web-pages, conference or journal papers etc. Provide web-links or other appropriate references to any sources you use.
Question 2. Substitution Permutation Network Cipher and Linear Cryptanalysis (60 Marks)
A simple 3-round substitution permutation network (SPN) cipher inspired by the Heys cipher is shown in Figure 1.
The cipher operates on 8-bit blocks. Key mixing is simple bitwise XOR. The 8-bit plaintext block P is XOR-ed bitwise with the 8-bit key K1 before the resulting 8-bit block enters the two first round S-boxes. The remaining key mixing operations are handled similarly.
A substitution box (S-box) is shown in Figure 2. This S-box is used throughout the cipher shown in Figure 1, i.e. all 6 S-boxes are identical.
The permutation part of the first two rounds is as shown in Figure 1. The final (third) round does not implement any permutation; the outputs from the final round S-boxes are simply XOR-ed bitwise with the key K4 to produce ciphertext C.
256 plaintext-ciphertext (P-C) pairs have been generated using the 3-round cipher and four secret keys (K1, K2, K3, K4). The 256 P-C pairs are given in the file TwoFiveSixPCs.txt that accompanies this assessment. Plaintexts and ciphertexts are given as integers with the natural binary interpretation, e.g. the integer 5 represents the 8-bit block 00000101, 129 represents the 8-bit block 10000001, and so on.
You are required to carry out Linear Cryptanalysis on the P-C pairs provided.
You should:
a) Use Linear Cryptanalysis to recover the final round key K4. You should:
i. give one or more suitable 2-round linear approximations involving bits of the plaintexts P and intermediate ciphertexts U3 (as shown in Figure 1). [10 Marks]
ii. indicate any active S-boxes in your approximations and their biases. [5 Marks]
iii. give the absolute value of the bias of any 2-round approximation derived above and show how all such biases were calculated. [5 Marks]
iv. Explain your specific choice of approximation(s). [5 Marks]
The above allows for using two approximations: one that targets the first four bits of K4 and one that targets the second four bits of K4. It also allows for the use of a single approximation that targets all 8 bits of the key K4. You should justify your choice.
b) Use the results above to recover the key K4. Show the results of your work. You will need to implement code to:
i. read-in the P-C pairs [5 Marks]
ii. carry out the (partial) decryption of the ciphertexts for a given (possibly partial) key guess, i.e., to obtain the appropriate U3 bits. [10 Marks]
iii. carry out the approximation checking between the appropriate P bits and U3 bits. [5 Marks]
iv. identify promising candidates for K4. You should state in your answer why identified candidate(s) are particularly promising. [5 Marks]
v. explain how confident you are you have identified the correct K4. [5 Marks]
c) Outline how you would recover all remaining keys, i.e. K1 , K2 , and K3. [5 Marks]
Figure 1. Simple Very Small SPN Cipher
Figure 2. Specification of the Common S-Box