""" PlayCrypt 3 : Block ciphers, key recovery, and hash functions """ # from email.utils import encode_rfc2231 from itertools import count # from operator import xor # from numpy import int_ from playcrypt.primitives import * from playcrypt.tools import * from playcrypt.ideal.function_family import * from playcrypt.games.game_cr import GameCR from playcrypt.simulator.cr_sim import CRSim from playcrypt.ideal.block_cipher import BlockCipher """ Problem 1 [10 points] Let E: {0,1}^k x {0,1}^n -> {0,1}^n be a block cipher (with inverse E_I). Define Enc: {0, 1}^k x {0, 1}^(mn) --> {0, 1}^((m+1)*n) as shown below. The message space of Enc is the set of all strings M whose length is an integer multiple of n. Notes: Sizes in comments are bits, sizes in code are in bytes (bits / 8). In the code K\in{0,1}^k. """ def Enc(K, M): """ Encryption algorithm Enc constructed from function family F. :param K: blockcipher key :param M: plaintext message :return: ciphertext """ assert len(M) % n_bytes == 0 M = split(M,n_bytes) # Caveat: M is now a list of strings, indexed from 0 to len(M)-1. The # code below does exactly the same thing as in hw3.pdf, the "+ 1" # offsets in hw3.pdf are removed here, precisely to take this # numbering difference into account C0 = random_string(n_bytes) C = [C0] count = string_to_int(E(K,C0)) for i in range(len(M)): Pi = int_to_string((count + i) % 2**n, n_bytes) Ai = xor_strings(M[i], Pi) Bi = E(K, Ai) C.append(xor_strings(Bi, Pi)) return join(C) """ (1) [3 points] Give a decryption algorithm Dec such that SE = (K,Enc,Dec) is a symmetric encryption scheme satisfying the correct decrypiton condition of Slide 3,4. """ """ n - bit size of each block E - is the encryption block cipher """ def Dec(K,C): """ You must fill in this method. This is the decryption algorithm that the problem is asking for. :param K: This is the secret key for the decryption algorithm. It is an n-bit string :param C: This is the ciphertext to decrypt. You may assume that C is a bitstring whose length is a multiple of n. :return: return a plaintext string. """ C = split(C, n_bytes) M = [] count = string_to_int(E(K, C[0])) for i in range(len(C) - 1): Pi = int_to_string((count + i) % 2**n, n_bytes) Ai = xor_strings(Pi, C[i+1]) Bi = E_I(K, Ai) M.append(xor_strings(Bi, Pi)) return join(M) pass """ (2) [7 points] Give a 1-query adversary A that has advantage Adv^ind-cpa_SE(A) >= 0.9 and running time O(T_E + n), where T_E is the time to compute E or E_I. """ def A(fn): """ You must fill in this method. This is the adversary that the problem is asking for. :param fn: This is the LR oracle supplied by GameIND-CPA, you can call this oracle with two messages to get an "encryption" of either the left or right message. :return: return a bit that represents a guess of the secret bit b. """ ## secret bit represents left(0) or right(1) # adversary should not know message or key ## //////// NOTES # 1 query ci = e(k, pi) xor pi msg = 000 # set boundaries from range of i # not wrap around mod 2^n is useless # force encryption to get 2 identiical input # get pattern from ciphertext C = fn(e1, e2) # bit level ## //////// NOTES M0 = [] M1 = random_string(n) for i in range(n_bytes): M0.append(int_to_string(i, n//n_bytes)) M0_join = join(M0) # print("M0 length: ", len(M0_join)) # print("M1 length: ", len(M1)) C = fn(M1, M0_join) C_split = split(C, n_bytes) if(C_split[1] == C_split[2] or C_split[1] == C_split[3]): # print("please work") return 1 return 0 """ Problem 2 [10 points] Let E: {0,1}^k x {0,1}^l -> {0,1}^l be a block cipher (with inverse E_I) and let T_E denote the time to compute E or E_I. Let D be the set of all strings whose length is a positive multiple of l. 1. [4 points] Define the hash function H1: {0,1}^k x D -> {0,1}^l via the CBC construction, as follows: """ def H1(K, M): """ Hash function. :param K: Key used by the hash function, must be of size k_bytes :param M: Message hashed by the function, must be of length n * l_bytes """ M = split(M, l_bytes) C = ["\x00" * l_bytes] for B in M: C += [E(K, xor_strings(C[-1], B))] return C[-1] """ Show that H1 is not collision resistant by presenting an O(T_E + l) time adversary A1 with Adv^cr_H(A)=1. """ def A1(K): """ You must fill in this method. We will define variables k, l, k_bytes, l_bytes, E, and E_I for you. :param K: This is the key used as the seed to the provided hash function :return: Return 2 messages, M1 and M2, that your adversary believes collide """ # Approach 1: MAke M1 an encryption ahead of M0 # appraoch 2: Make M0 = 000..E(K, M0[0])...E(K, M0[0]), # M1 = E(K, M0[0])... E(E(K, M0[0])) res1 = "" res2 = "" M0 = ["\x00" * l_bytes] E_M0 = E(K, M0[0]) E_M1 = E(K, E_M0) M1 = [E_M0] M1.append(E_M1) for i in range(l_bytes - 1): M0.append(E_M0) for i in range(l_bytes - 2): M1.append(E_M0) res1 = join(M0) res2 = join(M1) return res1, res2 """ 2. [6 points] Define the hash function H2: {0,1}^k x D -> {0,1}^l as follows: """ def H2(K, M): """ Hash function. :param K: Key used by the hash function, must be of size k_bytes :param M: Message hashed by the function, must be of length n * l_bytes """ M = split(M, l_bytes) W = [] C = ["\x00" * l_bytes] for B in M: W += [E(K, xor_strings(C[-1], B))] C += [E(K, xor_strings(W[-1], B))] return C[-1] """ Show that H2 is not collision resistant by presenting an O(T_E + l) time adversary A2 with Adv^cr_H(A)=1. """ def A2(K): """ You must fill in this method. We will define variables k, l, k_bytes, l_bytes, E, and E_I for you. :param K: This is the key used as the seed to the provided hash function :return: Return 2 messages, M1 and M2, that your adversary believes collide """ res1 = "" res2 = "" M0 = ["\x00" * l_bytes] EM0 = E(K, M0[0]) M1 = [EM0] EEM0 = E(K, EM0) EEM0_xor_EM0 = xor_strings(EEM0, EM0) E_EEM0_xor_EM0 = E(K, EEM0_xor_EM0) E_EEM0_xor_EM0_xor_EEM0_xor_EM0 = xor_strings(E_EEM0_xor_EM0, EEM0_xor_EM0) M0.append(EEM0) for i in range((l//l_bytes) - 2): M0.append(E_EEM0_xor_EM0_xor_EEM0_xor_EM0) for j in range((l//l_bytes) - 1): M1.append(E_EEM0_xor_EM0_xor_EEM0_xor_EM0) res1 = join(M0) res2 = join(M1) return res1, res2 """ ======================================================================================== Code below this line is used to test your solution and should not be changed. ======================================================================================== """ from playcrypt.games.game_lr import GameLR from playcrypt.simulator.lr_sim import LRSim if __name__ == '__main__': print("--- Problem 1 ---") # Arbitrary choices of k, n. k = 128 n = 128 # 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 g = GameLR(1, Enc, k_bytes) s = LRSim(g, A) # test decryption worked = True for j in range(100): K = random_string(k_bytes) num_blocks = random.randrange(n_bytes*8) M = random_string(num_blocks*n_bytes) C = Enc(K, M) if M != Dec(K, C): print ("Your decryption function is incorrect.") worked = False break if worked: print ("Your decryption function appears correct.") try: print ("The advantage of your adversary A1 is approximately " + str(s.compute_advantage(2000))) except ValueError as e: print("Error computing advantage:", e) print() print("--- Problem 2 ---") # Case 1: k = l = 128 k = 128 l = 128 k_bytes = k//8 l_bytes = l//8 EE = BlockCipher(k_bytes, l_bytes) E = EE.encrypt E_I = EE.decrypt g1 = GameCR(H1, k_bytes) s1 = CRSim(g1, A1) g2 = GameCR(H2, k_bytes) s2 = CRSim(g2, A2) print("When k=128, l=128:") print("The advantage of your adversary A1 is ~" + str(s1.compute_advantage())) print("The advantage of your adversary A2 is ~" + str(s2.compute_advantage())) # Case 2: k = 64 ; l = 16 k = 64 l = 16 k_bytes = k//8 l_bytes = l//8 EE = BlockCipher(k_bytes, l_bytes) E = EE.encrypt E_I = EE.decrypt g1 = GameCR(H1, k_bytes) s1 = CRSim(g1, A1) g2 = GameCR(H2, k_bytes) s2 = CRSim(g2, A2) print("\nWhen k=64, l=16:") print("The advantage of your adversary A1 is ~" + str(s1.compute_advantage())) print("The advantage of your adversary A2 is ~" + str(s2.compute_advantage()))