COMP3491 Codes and Cryptography - Coursework 2: Feistel cipher
COMP3491 Codes and Cryptography 2022-23 Summative
In this coursework you will explore what makes a good (or bad) Feistel function in a Feistel cipher. Alice and Bob wish to communicate secretly. They decide to use a Feistel cipher in which the function f is bitwise AND (for example, f (10110, 00111) = 00110). So, given a 2t-bit plaintext (L0 , R0 ) and an rt-bit key (K0 , . . . , Kr ), their cipher performs r rounds as follows: Li = Ri−1 , Ri = Li−1 ⊕ f (Ri−1 , Ki ), The output cipertext is then (Lr , Rr ).
1 Implementing the Cipher
Implement the encryption and decryption functions for the Feistel cipher described above. Specifically, you should provide:
- A function feistel(plaintext, key, rounds) which, given a plaintext of any even length 2t ≥ 2, a key of the correct corresponding length, and an integer rounds ≥ 3, returns the correct ciphertext. [5 marks]
- A function defeistel(ciphertext, key, rounds) which, given a ciphertext of any even length 2t ≥ 2, a key of the correct corresponding length, and an integer rounds ≥ 3, returns the correct plaintext. [5 marks]
Your input and output (for these functions and all others in the coursework) should be in Python’s bytes datatype, but within your functions you may use a package to facilitate easier operations on bit-strings. One such package is bitarray (https://pypi.org/project/bitarray/), but you may use others if you wish.
2 Cracking a 3-Round Cipher
Alice and Bob first use 3 rounds for their Feistel cipher. You aim to attack their cipher.
- Design a function crack3round(plaintext, ciphertext) which, given a plaintext-ciphertext pair (of any even length 2t), returns a key such that encoding the plaintext using key would give the ciphertext (i.e. feistel(plaintext,key,3) = ciphertext). [20 marks]
You should aim to make your function (and also those for parts 3 and 4) efficient enough to run on large inputs (e.g. with t = 10, 000).
3 Cracking a 4-Round Cipher
To improve security, Alice and Bob switch to a 4-round cipher.
- Again, design a function crack4round(plaintext, ciphertext) which, given a plaintext-ciphertext pair, returns a key such that encoding the plaintext using key gives the ciphertext (i.e. feistel(plaintext,key,4) = ciphertext). [15 marks]
4 Cracking an r-Round Cipher
Finally, Alice and Bob extend their scheme so that they can use an r-round Feistel cipher for any r ≥ 3.
- Design a function crackrround(plaintext, ciphertext, rounds) which, given a plaintext-ciphertext pair and a number of rounds, returns a key such that encoding the plaintext under an r-round Feistel cipher using key gives the ciphertext, (i.e. feistel(plaintext,key,rounds) = ciphertext). [10 marks]
5 Cryptographic Hash Function
Alice and Bob now attempt to use their cipher to construct a hash function using the Davies-Meyer construction and Merkle-Damg˚ ard transform. Specifically, they use their 4-round Feistel cipher (still with bitwise AND as the Feistel function) on 64-bit plaintexts to construct the hash function H : {0, 1}∗ → {0, 1}64 . As an initialisation vector (IV) they use the all-1s vector.
- Implement this hash function as a function cipherhash(hashinput). [15 marks] (You may notice potentially unexpected behavior from this hash function, even if implemented correctly.)
6 Report
- Write a short report (no longer than 3 pages, 11pt font, margin at least 2cm) describing the design choices made in your functions from parts 2-4 and justifying their correctness. Marks will be awarded for originality, clarity, and soundness. [20 marks]
- Your report should also answer the following question: Is the bitwise AND function a good choice of Feistel function? Discuss, and give at least one positive property and one negative property. [10 marks]
Submission Checklist
Code file (.py) containing
- feistel(plaintext, key, rounds) function
- defeistel(ciphertext, key, rounds) function
- crack3round(plaintext, ciphertext) function
- crack4round(plaintext, ciphertext) function
- crackrround(plaintext, ciphertext, rounds) function
- cipherhash(hashinput) function Report file (.pdf) containing
- Justification of design choices and correctness for your functions for parts 2-4
- Answer to the question “Is the bitwise AND function a good choice of Feistel function?”
Submission
Submission will be to Gradescope. You will be able to use automatic tests to check your code’s correctness before final submission.
