Problem 1. (100 points.) Define the family of functions F: {0,1}256 {0, 1)256 {0,1256 by Algorithm FK || K (1||22): Return AES-(K1,2122)||AES(K2, 12) for all K1, K2,11,12 {0,1}128 Here'l denotes string concatenation, 'e' denotes bit-wise exclusive-or, and I denotes the bit-wise complement of a string r. Let TAES denote the time for one computation of AES or AES-1 Below, running times are worst case and should be func- tions of Taes. For full credit avoid use of asymptotics. (Part A - 15 points.) Prove that F is a blockcipher according to the definition given in class. (Part B - 15 points.) What is the running-time of a 2-query exhaustive key search adversary against F? (Part C - 40 points.) Give the most efficient 2-query consistent key recovery adversary that you can with advantage 1 against F. Your answer should consist of the pseudocode for your pro- posed adversary followed by an analysis of its advantage (proving that it is 1) and resource usage (running-time and number of queries). For full credit, your adversary should be significantly faster than exhaustive key search. Exhaustive key search gets no points. (Part D - 30 points.) Would you expect your adversary in Part C to recover the target key (rather than merely a consistent key)? Why or why not? The right yeso answer with missing or completely incorrect justification gets no points. Problem 1. (100 points.) Define the family of functions F: {0,1}256 {0, 1)256 {0,1256 by Algorithm FK || K (1||22): Return AES-(K1,2122)||AES(K2, 12) for all K1, K2,11,12 {0,1}128 Here'l denotes string concatenation, 'e' denotes bit-wise exclusive-or, and I denotes the bit-wise complement of a string r. Let TAES denote the time for one computation of AES or AES-1 Below, running times are worst case and should be func- tions of Taes. For full credit avoid use of asymptotics. (Part A - 15 points.) Prove that F is a blockcipher according to the definition given in class. (Part B - 15 points.) What is the running-time of a 2-query exhaustive key search adversary against F? (Part C - 40 points.) Give the most efficient 2-query consistent key recovery adversary that you can with advantage 1 against F. Your answer should consist of the pseudocode for your pro- posed adversary followed by an analysis of its advantage (proving that it is 1) and resource usage (running-time and number of queries). For full credit, your adversary should be significantly faster than exhaustive key search. Exhaustive key search gets no points. (Part D - 30 points.) Would you expect your adversary in Part C to recover the target key (rather than merely a consistent key)? Why or why not? The right yeso answer with missing or completely incorrect justification gets no points
