2016 07 04 2

Page 1

Cryptography and Architectures for Computer Security Exam Code: 095947 (old 090959), A.Y. 2015–2016, Semester: 2 Prof. G. Pelosi July 4th, 2016 – Exam Session Name: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Surname: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Student ID: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Signature: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Time: 2h:30’. Use of textbooks, notes, phones or Internet connected devices is not allowed. Prior to turn in your paper, write your name on any additional sheet and sign it. Question 1 [4 pts] A5/1 is a stream cipher with a 64-bit key employed to secure GSM communications, which is still in use whenever the link between the mobile phone and the cell is downgraded to GSM. Performing an exhaustive key search to find a key is thus within practical feasibility, although taking quite some computation. To this end, Time-to-Memory Tradeoffs (TMTO) are an appealing approach, and have effectively been used to crack A5/1 encrypted messages in practice. (a) Assuming to employ a nVidia Geforce GTX 1070, able to compute around 29 ×230 A5/1 keystreams per second, each one 64-bit long, calculate how much memory is required to break A5/1 in less than 0.1s in the following two cases: i) GDDR5 DRAM, access time 0.5µs, ii) SATA-SSD 10µs. Assume, for the sake of simplicity, that the data structure in memory allows you to check for the presence of a given value with a single access, and that you are given an A5/1 plaintext- ciphertext pair, where both are 64-bit long to the end of finding the key. Argue on which one of the two strategies may be practically viable. (b) Which one(s) of the following…