Assignment #2 - KeeLoq, MACs, and collisions

In this homework, you will be implementing the Cipher Block Chaining (CBC) mode with the KeeLoq symmetric cipher. Based on that you will implement the Message Authentication Code (MAC) algorithm, which you will subsequently find different collisions for. This homework does not have an interactive API, instead you will implement and test your solution in Python locally and then submit the code.

Apart from this assignment text, you are given the following files: keeloq.py, utils.py, macs.py, and also two files containing test vectors keeloq_cbc_test_vectors.json, mac_keeloq_test_vectors.json. You can import any function from these files into code.py, where you will implement your solutions. Treat the extra files (apart from code.py) as a library code that you can use, but do not modify it in any way. You can also use Python 3 standard library, and if you use any other sources or code, cite them accordingly. As usual, the notation A || B represents concatenation of two strings A, B.

Task 1 – KeeLoq CBC and MAC implementation (2 points)

1. (1.5 point) Implement the function keeloq_cbc_enc in the file code.py. The function keeloq_cbc_enc must encrypt a message using the KeeLoq block cipher in the Cipher Block Chaining (CBC) mode. For message padding use PKCS#7. To test the correctness of your solution you can use the test vectors in keeloq_cbc_test_vectors.json, see code.py on how to do so. We also suggest to write custom tests.


2. (0.5 point) Similarly, finish the implementation of the function mac_keeloq in the file code.py. The function mac_keeloq uses the KeeLoq cipher in the Vanilla CBC mode (slide 8 from Lecture on MACs) to create a Message Authentication Code (MAC). For the initialization vector, use the vector b"\x00\x00\x00\x00" comprising of zero bytes. For the purposes of this homework, we require that the size of the tag is variable (but always less than or equal to four bytes) and determined by the mac_size parameter of mac_keeloq. You can use the test vectors in mac_keeloq_test_vectors.json.

Task 2 – Collision finding (6 points)

1. (2 points) Thanks to your work in Task 1b you have now access to the mac_keeloq function. Your task is to implement mac_keeloq_collision function (in the file code.py) that for a given key K and tag size mac_size returns a collision on mac_keeloq, i.e., pair of distinct messages msg1 and msg2 such that:
   • mac_keeloq(msg1, K, mac_size) = mac_keeloq(msg2, K, mac_size)
   Test that for mac_size = 3 your implementation can find a collision within a couple of seconds and for mac_size = 4 within a couple of minutes.


2. (1 point) Using the existing collision for the SHA1 hash function (see https://shattered.io/), implement the function sha1_collision that takes single parameter msg (assume that the length of msg is less than 100 bytes) and finds a special collision on SHA1, i.e., returns pair of distinct messages msg1 and msg2, such that:
   • sha1(msg1) = sha1(msg2), and
   • the length of each of msg1 and msg2 is less than 600 bytes and each of the two messages contains msg as a substring.



3. (3 points) Thanks to your work in Task 2a and 2b you now know enough to be able to find collisions against the mac_combined function (from the file macs.py). mac_combined uses both mac_keeloq and SHA1 in order to create a presumably stronger MAC. For a given msg and a key K (and mac_size) the mac_combined function calculates the tag t as follows t = sha1(msg || mac_keeloq(msg, K, mac_size)). Implement the function mac_combined_collision inside the file code.py, which takes a parameter msg (assume that the length of msg is less than 100 bytes) and mac_size and returns a tuple (msg1, K1, msg2, K2) such that:

   • msg1 != msg2,
   • mac_combined(msg1, K1, mac_size) = mac_combined(msg2, K2, mac_size), and
   • the length of each of msg1 and msg2 is less than 600 bytes and each of the two messages contains msg as a substring.
   Due to the increased computation, test that for mac_size = 2 your implementation can find a collision within a couple of seconds and for mac_size = 3 within a couple of minutes. Similarly to Task 2a, you can assume the mac_size to be always less than or equal to four bytes.

Task 3 – Description (2 points)

Provide succinct and clear asnwers to the following (less than 300 words should suffice):

1. (0.5 point) What is the principle of your attack in Task 2a and its expected runtime?
2. (0.5 point) How and why is it possible to generate the special SHA1 collisions in Task 2b?
3. (0.5 point) Describe the principle of your attack in Task 2c.
4. (0.5 point) Consider a final MAC scheme, where given message msg and key K the tag t is computed as follows t = sha1(msg || K) || mac_keeloq(msg, K, mac_size). Compared to mac_combined from Task 2c, which MAC scheme is more collision resistant and why?

Submission

Submit a single .zip file containing in its root:

• a file called code.py containing your implementation of the Tasks 1 and 2. We will provide the files keeloq.py, utils.py, macs.py to make your solution executable ourselves; and
• a plain text file description.txt containing your answers for Task 3.

Not conforming to the submission structure will yield point penalty. Use only standard Python and modules already imported in the files. Do not change the signature of the functions that you are implementing, that is the number, order and names of the parameters or return values. Your solutions will be graded automagically and not conforming to those rules will lead to a point loss. As usual, a solution with no description is worth zero points.