Assignment 2: COMP6453 2024 T2

This set consists of 3 questions with a total marks of 60. Change log

• Question 2, Part 3, Compute t := Fk(r) Fk(h1i||m1) Fk(hli||ml)

1. Block Ciphers modes of operation

   Consider CBC and CTR modes of operation for block ciphers.

   Marks

   • Part 1: 2 + 2 marks

   • Part 2: 2 + 2 marks

   • Total marks is 8.

2. Security of Message Authentication Codes

   Let F be a pseudorandom function. Show that each of the following MACs is insecure even if used to authenticate fixed-length messages. In each case you should present a forgery that can be done efficiently. In each case, assume there exists a function KeyGen that outputs a uniform k 2 {0, 1}n. Let hii denote an n/2-bit encoding of the integer i.

   1. To authenticate a message m = m1, , ml, where mi 2 {0, 1}n, compute

      tag t := Fk(m1) Fk(ml).

   2. To authenticate a message m = m1, ·· · , ml, where mi 2 {0, 1}n/2, com- pute tag t := Fk(h1i||m1) Fk(hli||ml).

   3. To authenticate a message m = m1, , ml, where mi 2 {0, 1}n/2 choose

      uniform r ← {0, 1}n, compute t := Fk(r) Fk(h1i||m1) Fk(hli||ml)

      and let the tag be hr, ti.

      Marks

      • Part 1: 5 marks

      • Part 2: 7 marks

      • Part 3: 8 marks

      • Total: 20 marks

3. Finding collisions on a 40-bit Hash

Write a program to find hash collisions on a 40-bit hash. The program should

1. Can you reduce the number of calls to the SHA-1 function? (Hint: Use a result from your class)

2. Write a pseudo code for hashCollision().

3. Implement the above in any programming language of your choice. You do not have to implement SHA-1 but use an appropriate library to generate SHA-1 digests. The output of the program should be two hash collisions obtained by generating two tuples (m1, m2, n) and (m0 , m0 , n0). While

   1 2

   submitting the code, please add compilation instructions and execution

   instructions.

   Marks

   • Part 1: 2 marks

   • Part 2: 2 marks

   • Part 3: 10 marks. If your idea is correct but the pseudo-code is incorrectly written – 4 marks.

   • Part 4: 18 marks. Inefficient code using brute force search – 8 marks.

   • Total: 32 marks

Full Submission

1. Q1: Write answer in a file q1. You can use pdf or txt format.

2. Q2: Write answer in a file q2. You can use pdf or txt format.

3. Q3: Put the answers of the part (1), (2), (3) in a pdf or txt file, code and headers for part (4) all in a folder.

4. Upload a zip file with all three answers. hzidihass2i.zip