# Crack one-block VMAC with N=17 rounds using arbitrary input data # # The input data does not conform to the SHA-256 padding requirements. # # Manipulate W[16] to determine Key[7] # # Does not work. See sections marked "BAD". # #### # # Key Schedule: # # KeyIndex = [ 0, 1, 2, 3, 4, 5, 6, 7, 3, 4, 5, 6, 7, 1, 2, 0] # # t = 0:15 # # ki = KeyIndex[t] # # W[t] = Data[t] XOR ROTR( Key[ki], 3*ki+(t>>3)) # # t > 15 # # ki = (63-t)%8 # # W[t] = (sigma1(W[t-2]) + W[t-7] + sigma0(W[t-15]) + W[t-16]) # # XOR ROTR( Key[ki], 3*ki+(t>>3)) #### # # W[16] = ( # Data Key # sigma1( Data[14] XOR ROTR( Key[2], 7) ) # [49, 51, 42] [184, 186, 177] # + Data[9] XOR ROTR( Key[4], 13) # [192] [109] # + sigma0( Data[1] XOR ROTR( Key[1], 3) ) # [455, 466, 451] [202, 213, 198] # + Data[0] XOR ROTR( Key[0], 0) # [480] [224] # ) # XOR ROTR( Key[7], 23) # [23] # # = F XOR ROTR( Key[7], 23) # # F is complicated, but VMAC-DATA.py shows that data bits [42, 49, 51] # directly affect bit 0 of W[16] (and do not affect bit 0 or bit 1 of h), # so flipping one of those bits will flip bit 0 of W[16] and bit 0 of T1. # We won't know the value of that bit of W[16], just that it changed. # # The data bits directly affecting bit 0 of W[16] are: # [49, 51, 42, 192, 455, 466, 451, 480] # sorted: [42, 49, 51, 192, 451, 455, 466, 480] # # The associated key bits directly affecting bit 0 of W[16] are: # [184, 186, 177, 109, 202, 213, 198, 224, 23] # sorted: [23, 109, 177, 184, 186, 198, 202, 213, 224] # # BAD: This analysis does not account for carry dependencies in the W[16] additions, # which throw off the value of T1 and calculation of h. import sha, random N = 17 KEY = random.getrandbits(256); Key7 = sha.ROTR( KEY & sha._mask, 3*7+(16>>3)) # Key[7] XOR with W[16] in VMAC() print( "Key7 =", format(Key7,'032b')) # arbitrary random input Data # # maybe should use all 0's here? # Data = random.getrandbits(512); # # Data = 0 # masks to set bit 0 of Data high or low # ones = (1 << 512) - 1 # 11...11 mask1 = 1 # 00...01 mask0 = ones ^ mask1 # 11...10 # from VMAC-DATA.py, N=17, # these data bits directly affect W[16][0] but not hprev[0] # A = [42, 49, 51] # for Z in A: # K7 will hold the cracked key bits # # K7 = 0 # R will hold the h bits # R = 0 print( "Z =", Z) mask1 = 1 << Z mask0 = ones ^ mask1 # find bit n of Key7 # for n in [0]: # range(31): print( "n =", n) # # W[16][n] = unknown, but we can flip it # H0 = sha.VMAC(Data & mask0,17,KEY) W0 = sha.W[N-1] if n == 0: hprev0 = sha.hprev elif hprev0 != sha.hprev: print( "error, hprev0 changed") H1 = sha.VMAC(Data | mask1,17,KEY) W1 = sha.W[N-1] if hprev0 != sha.hprev: print( "error, hprev1 changed") # for next iteration # mask1 <<= 1 mask0 = ones ^ mask1 # extract internal variables # H = H0 # h0 = (H - sha._H0[7]) & sha._mask; H >>= 32 g0 = (H - sha._H0[6]) & sha._mask; H >>= 32 f0 = (H - sha._H0[5]) & sha._mask; H >>= 32 e0 = (H - sha._H0[4]) & sha._mask; H >>= 32 d0 = (H - sha._H0[3]) & sha._mask; H >>= 32 c0 = (H - sha._H0[2]) & sha._mask; H >>= 32 b0 = (H - sha._H0[1]) & sha._mask; H >>= 32 a0 = (H - sha._H0[0]) & sha._mask; # H = H1 # h1 = (H - sha._H0[7]) & sha._mask; H >>= 32 g1 = (H - sha._H0[6]) & sha._mask; H >>= 32 f1 = (H - sha._H0[5]) & sha._mask; H >>= 32 e1 = (H - sha._H0[4]) & sha._mask; H >>= 32 d1 = (H - sha._H0[3]) & sha._mask; H >>= 32 c1 = (H - sha._H0[2]) & sha._mask; H >>= 32 b1 = (H - sha._H0[1]) & sha._mask; H >>= 32 a1 = (H - sha._H0[0]) & sha._mask; # The previous round values a,b,c,d,e,f,g,T1,T2 can be determined directly, # but not h (see notes in file REVERSE here). # # T1 ~= h + (F XOR Key7), with T1 known, but h, F, and Key7 unknown. # # A single bit flip in F will cause a corresponding bit flip in T1, # and based on the change in the carry bit related to that flip, # we can determine a bit of h. # # V = T1 - offset = h + W[N-1] # # where offset includes R, the previously calculated low-order bits of h, # to eliminate carry propagation from those bits in the addition # unwind H0 to get T1 # a = b0; b = c0; c = d0; e = f0; f = g0; g = h0 T2 = (sha.Sigma0(a) + sha.Maj(a,b,c)) & sha._mask T1 = (a0 - T2) & sha._mask V0 = (T1 - sha.Sigma1(e) - sha.Ch(e,f,g) - sha._K[N-1] - R) & sha._mask # unwind H1 to get T1 # a = b1; b = c1; c = d1; e = f1; f = g1; g = h1 T2 = (sha.Sigma0(a) + sha.Maj(a,b,c)) & sha._mask T1 = (a1 - T2) & sha._mask V1 = (T1 - sha.Sigma1(e) - sha.Ch(e,f,g) - sha._K[N-1] - R) & sha._mask print( "V0 =", format(V0,'032b')) print( "V1 =", format(V1,'032b')) print( "W0 =", format(W0,'032b')) print( "W1 =", format(W1,'032b'),"\n") v0 = (V0 >> n) & 1; w0 = (V1 >> n) & 1 # these bits must differ if v0 == w0: print( "error, v0 = w0") # consistency check # r = bit n of h # # if the carry bit changes then r = 1 else r = 0 # see truth table and notes in Crack16.py # # BAD: this does not work here because the carry can also change # due to bit n+1 of W[16] changing. # r = ((V0 >> (n+1)) & 1) ^ ((V1 >> (n+1)) & 1) # change in carry # BAD: the following, from Crack16.py, is not correct here. # There are two possibilities and we can not directly # distinguish between them without additional work. # # k = v0 ^ r # key bit # print( "k =", k) # if k != ((Key7 >> n) & 1): print( "error, k bit", n, "is wrong") if r != ((hprev0 >> n) & 1): print( "error, r bit", n, "is wrong") # insert k into K7 and r into R # # K7 |= k << n R |= r << n # print( " K7 =", format(K7,'032b')) print( "hprev =", format(hprev0,'032b')) print( " R =", format(R,'032b')) # sample run: # # Key7 = 11010111100100101100010111101100 # Z = 42 # n = 0 # V0 = 11011111001011000000011101001011 # V1 = 11100000101011000000011101010010 # W0 = 11001001011101010010001000010000 # W1 = 11001010111101010010001000010111 # # error, r bit 0 is wrong # hprev = 00010101101101101110010100111011 # R = 00000000000000000000000000000000 # Z = 49 # n = 0 # V0 = 10100000101011000000011111001011 # V1 = 11100000101011000000011101010010 # W0 = 10001010111101010010001010010000 # W1 = 11001010111101010010001000010111 # # error, r bit 0 is wrong # hprev = 00010101101101101110010100111011 # R = 00000000000000000000000000000000 # Z = 51 # n = 0 # V0 = 11100000101011000000011101010010 # V1 = 11100000101011000000010101001111 # W0 = 11001010111101010010001000010111 # W1 = 11001010111101010010000000010100 # # error, r bit 0 is wrong # hprev = 00010101101101101110010100111011 # R = 00000000000000000000000000000000