Problem 2: Meet in the middle attack This problem involves cryptanalysis of a simple cipher I'll call TOY. It is adapted from the simple cipher in Chapters 6 and 7 of The Block Cipher Companion. TOY operates on a 4-bit input v and produces a 4-bit output w. The cipher involves 2 steps: xor with a 4-bit key ko and the application of a non-linear S-box whose truth table is given below TOY is really weak for a variety of reasons, most of which I'll ask you to ignore for this problenm (such as the fact that its final operation is key-independent, so it may easily be unraveled without making any key guesses). Let's strengthen it slightly by iterating it twice to produce a cipher I call 2TOY As before, 2TOY receives a 4-bit input and returns a 4-bit output x. Unlike TOY though, this cipher has an 8-bit key (ko, k1). You should probably implement both TOY and TOY-1 as a warmup, 0 Figure 1: The ciphers TOY (left) and 2TOY (right, uses 2 iterations of TOY with independent keys) x 0 12 345678 9a bcdef S[x6 4 c 5 07 2 e 1 f 3 d 8 a 9 b Figure 2: Truth table for the 4-bit to 4-bit substitution box S and you're welcome implement 2TOY in the straightforward manner as well. But your ultimate goal for this problem is to find a quicker way to implement 2TOY Your task: Implement a function mitm 2TOY (v, x) that executes a "meet-in-the-middle" attack to find the set of keys consistent with the given (message, ciphertext) pair quicker than an 8- bit brute-force search would. This function should take advantage of the structure of 2TOY as two applications of TOY. That is: for 2T0Y on some message u to yield ciphertext under key (ko,k1), it must be the case that there exists some intermediate value w such that simultaneously TOY(v, ko) and wTOY (x, ki) Your code should leverage this fact to compute the set of keys consistent with a given (v, x) pair using two independent loops on ko and ki. That is, your code should run in 2- 2" time rather than 22 time, where n is the length of the key of TOY (n4, in our case). The downside is that your code will also require 2- 2" intermediate state, whereas a naive brute-force attack would not. This problem is an example of a time-memory tradeoff in cryptanalysis, and it's the reason why DES was strengthened by moving to 3DES rather than 2DES (which would only add 1 bit of security to Your output Use your function to find all keys (ko, k1) consistent with input0xA and output Z'-0 rB. Output the keys as hex-formatted lowercase strings, and concatenate them together in increasing order SHA-256 hash of the answer: f)783f558e348978cf298fbb271a9227ac644a542d7d6d173f24f54bf4f709d3 Problem 2: Meet in the middle attack This problem involves cryptanalysis of a simple cipher I'll call TOY. It is adapted from the simple cipher in Chapters 6 and 7 of The Block Cipher Companion. TOY operates on a 4-bit input v and produces a 4-bit output w. The cipher involves 2 steps: xor with a 4-bit key ko and the application of a non-linear S-box whose truth table is given below TOY is really weak for a variety of reasons, most of which I'll ask you to ignore for this problenm (such as the fact that its final operation is key-independent, so it may easily be unraveled without making any key guesses). Let's strengthen it slightly by iterating it twice to produce a cipher I call 2TOY As before, 2TOY receives a 4-bit input and returns a 4-bit output x. Unlike TOY though, this cipher has an 8-bit key (ko, k1). You should probably implement both TOY and TOY-1 as a warmup, 0 Figure 1: The ciphers TOY (left) and 2TOY (right, uses 2 iterations of TOY with independent keys) x 0 12 345678 9a bcdef S[x6 4 c 5 07 2 e 1 f 3 d 8 a 9 b Figure 2: Truth table for the 4-bit to 4-bit substitution box S and you're welcome implement 2TOY in the straightforward manner as well. But your ultimate goal for this problem is to find a quicker way to implement 2TOY Your task: Implement a function mitm 2TOY (v, x) that executes a "meet-in-the-middle" attack to find the set of keys consistent with the given (message, ciphertext) pair quicker than an 8- bit brute-force search would. This function should take advantage of the structure of 2TOY as two applications of TOY. That is: for 2T0Y on some message u to yield ciphertext under key (ko,k1), it must be the case that there exists some intermediate value w such that simultaneously TOY(v, ko) and wTOY (x, ki) Your code should leverage this fact to compute the set of keys consistent with a given (v, x) pair using two independent loops on ko and ki. That is, your code should run in 2- 2" time rather than 22 time, where n is the length of the key of TOY (n4, in our case). The downside is that your code will also require 2- 2" intermediate state, whereas a naive brute-force attack would not. This problem is an example of a time-memory tradeoff in cryptanalysis, and it's the reason why DES was strengthened by moving to 3DES rather than 2DES (which would only add 1 bit of security to Your output Use your function to find all keys (ko, k1) consistent with input0xA and output Z'-0 rB. Output the keys as hex-formatted lowercase strings, and concatenate them together in increasing order SHA-256 hash of the answer: f)783f558e348978cf298fbb271a9227ac644a542d7d6d173f24f54bf4f709d3