""" PlayCrypt 2 : Block Ciphers and Key Recovery Security Module General comment on all the problems below: - You must complete the code of the functions A50, A1, A3 (and only these functions). If you wish, you can also add auxiliary functions (but that should not be necessary for this assignment) - You do not know the key (which is concealed in the playcrypt objects such as GamePRF and GameKR). However you do know the block cipher that is being used, so you are allowed to call the functions E and E_I inside the functions that you code. - Likewise, variables such as k, n, as well as k_bytes and n_bytes, which are defined for each problem at the end of this file, can be accessed from your code. - Other functions might be useful, in particular the functions that are listed under Tools (https://ucsdcse107.github.io/playcrypt/playcrypt.tools.html) and Primitives (https://ucsdcse107.github.io/playcrypt/playcrypt.primitives.html) in the Playcrypt documentation. - For each of the questions, it is possible to successfully answer with well under 20 lines of code. ------------- please write text here (if relevant) ------------- List your references and/or the people you discussed with here: Is there any feedback you would like to give us? Are there particular topics you would like to see in discussion sections? ----------------------------------------------------------------- """ import json from operator import xor import sys, os, itertools from playcrypt.primitives import * from playcrypt.tools import * from playcrypt.ideal.block_cipher import * """ Problem 1 [10 points] Let E be a blockcipher E:{0, 1}^k x {0, 1}^n --> {0, 1}^n and E_I be its inverse. Define F1: {0, 1}^k x {0, 1}^n --> {0, 1}^n as shown below. Notes: Sizes in comments are bits, sizes in code are in bytes (bits / 8). In the code K\in{0,1}^k and M\in{0,1}^n Adversary is for the pseudo-random function game. """ def F1(K, M): """ Blockcipher F constructed from blockcipher E. This is for problem 1, and in order to distinguish it from the other Fs in this assignment, this one is named F1. You must not change this method. :param K: blockcipher key :param M: plaintext message :return: ciphertext """ C = E(K, M) return C """ k=128 (key length) n=8 (block length) E(K, M) - encryption Func E_I - inverse encryption func Show that F is not a secure PRF by presenting in pseudocode an adversary A50 such that - adv_F^prf(A50) = Pr[Real --> 1] - Pr[Rand --> 1]= 1 """ def A50(fn): """ You must fill in this method. This is the adversary that the problem is asking for. :param fn: This is the oracle supplied by GamePRF, you can call this oracle to get either an encryption of the data you pass into it or a random result. :return: return 1 for guessing the real world (you got the encrypted ciphertext) or 0 for guessing it is a random world. """ arr = [] for i in range(50): mes = int_to_string(i+1) arr.append(fn(mes)) for i in range(len(arr)): comp = arr[i] j = i+1 while(j < len(arr)-1): if(comp == arr[j]): return 0 j += 1 return 1 """ Problem 2 [10 points] Let E be a blockcipher E:{0, 1}^k x {0, 1}^n --> {0, 1}^n and E_I be its inverse. Define F2: {0, 1}^k+n x {0, 1}^n --> {0, 1}^n as shown below. Notes: Sizes in comments are bits, sizes in code are in bytes (bits / 8). In the code K1\in{0,1}^k and K2,M\in{0,1}^n Adversaries are for the consistent key recovery game. """ def F2(K, M): """ Blockcipher F constructed from blockcipher E. This is for problem 2, and in order to distinguish it from the other Fs in this assignment, this one is named F2. You must not change this method. :param K: blockcipher key :param M: plaintext message :return: ciphertext """ K1 = K[:k_bytes] K2 = K[k_bytes:] C = E(K1, xor_strings(M, K2)) return C """ (a) [5 points] Give a 1-query adversary A1 that has advantage Adv^kr_F(A1) = 1 and running time O(T_E + k + n). """ """ k, n >= 4 """ def A1(fn): """ You must fill in this method. This is the adversary that problem 2, question (a) is asking for. :param fn: This is the oracle supplied by GameKR, you can call this oracle to get an "encryption" of the data you pass into it. :return: return the a string that represents a key guess. """ mes = int_to_string(0, n_bytes) C = fn(mes) # = k2 k1 = int_to_string(0, k_bytes) for i in range(k): g1 = int_to_string(i, k_bytes) if(E(g1, mes) == C): k1 = g1 k2 = E_I(k1, C) return k1 + k2 """ (b) [5 points] Give a 3-query adversary A3 that has advantage Adv^kr_F(A3) = 1 and running time O(2^k * (T_E + k + n)). """ # k_bytes = 1 # n_bytes = 8 def A3(fn): """ You must fill in this method. This is the adversary that problem 2, question (b) is asking for. :param fn: This is the oracle supplied by GameKR, you can call this oracle to get an "encryption" of the data you pass into it. :return: return the a string that represents a key guess. """ C = [] k1 = int_to_string(0, k_bytes) # initialize k2 = int_to_string(0, k_bytes) # Initialize mes0 = int_to_string(0, n_bytes) # 0's*n_bytes message mes1 = int_to_string(1, n_bytes) # random message1 mes2 = int_to_string(2, n_bytes) # random message2 C.append(fn(mes0)) # index 0: E(K1, K2) # K2 = E_I(K1, C[0]) Real K2 if K1 is guessed correctly C.append(fn(mes1)) # index 1: E(K1, mes1 XOR k2) # random encryption, Use to test guessed K1 C.append(fn(mes2)) # index 2: E(K1, mes2 XOR k2) # random encryption, Use to test guessed K1 # b = 0 for a in range(2**k): g1 = int_to_string(a, k_bytes) g2 = E_I(g1, C[0]) if(C[0] == E(g1, g2)): if(C[1] == E(g1, xor_strings(mes1, g2))): # C[1] = first random encryption # if(C[2] == E(g1, xor_strings(mes2, g2))): # Not necessary? k1 = g1 k2 = E_I(k1, C[0]) return k1+k2 pass """ ========================================================================= The following lines are used to test your code, and must not be modified. ========================================================================= """ from playcrypt.games.game_kr import GameKR from playcrypt.games.game_prf import GamePRF from playcrypt.simulator.kr_sim import KRSim from playcrypt.simulator.world_sim import WorldSim if __name__ == '__main__': # hw2 p1 k = 128 n = 8 # Block & key size in bytes. k_bytes = k//8 n_bytes = n//8 EE = BlockCipher(k_bytes, n_bytes) E = EE.encrypt E_I = EE.decrypt g1 = GamePRF(50, F1, k_bytes, n_bytes) s1 = WorldSim(g1, A50) print("Problem 1: the advantage of your adversary A50 is approximately " + str(s1.compute_advantage(20))) # hw2 p2 (a) # Arbitrary choices of k, n. k = 128 n = 64 # Block & key size in bytes. k_bytes = k//8 n_bytes = n//8 EE = BlockCipher(k_bytes, n_bytes) E = EE.encrypt E_I = EE.decrypt g1 = GameKR(1, F2, k_bytes+n_bytes, n_bytes) s1 = KRSim(g1, A1) print("Problem 2, question (a): the advantage of your adversary A1 is approximately " + str(s1.compute_advantage(20))) # hw2 p2 (b) # Smaller choices of k, n. k = 8 n = 64 k_bytes = k//8 n_bytes = n//8 EE = BlockCipher(k_bytes, n_bytes) E = EE.encrypt E_I = EE.decrypt g3 = GameKR(3, F2, k_bytes+n_bytes, n_bytes) s3 = KRSim(g3, A3) print("Problem 2, question (b): the advantage of your adversary A3 is approximately " + str(s3.compute_advantage(20)))