# Crack one-block VMAC with N=17 rounds # # The input data does not conform to the SHA-256 padding requirements. # # Does not work. # # 3 bits of V are examined, varying just the lsb of the W[16] input, # but those bits are a function of 3 bits of each term in the additions. # #### # # 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) # # 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] # # Note data bits which directly affect W[16][0] # but do not affect hprev[0,1,2] or W[16][1,2]: # # sorted(WS[16][0] - hprev[0]) = [42, 49, 51] # sorted(WS[16][0] - hprev[1]) = [42, 49, 51] # sorted(WS[16][0] - hprev[2]) = [42, 49, 51, 192] # sorted(WS[16][0] - WS[16][1]) = [42, 49, 51, 192, 451, 455, 466, 480] # sorted(WS[16][0] - WS[16][2]) = [42, 49, 192, 451, 455, 466, 480] # import sha, random N = 17 KEY = random.getrandbits(256); #-- KEY = 0 # # sigma1 term with D[49,51]=0 reduces to one effective key bit: D[42] XOR Keff # Keff = ((KEY >> 184) & 1) ^ ((KEY >> 186) & 1) ^ ((KEY >> 177) & 1) # # second term: D[192] XOR K109 # K109 = (KEY >> 109) & 1 # # bits of ROTR( Key[7], 23) = [ ... 25, 24, 23] # K25 = (KEY >> 25) & 1 print( "Keff =", Keff); print( "K109 =", K109); print( " K25 =", K25) # masks to set bit 0 of Data high or low # ones = (1 << 512) - 1 # 11...11 mask1 = 1 # 00...01 mask0 = mask1 ^ ones # 11...10 # masks to set or reset bits 42 and 192 # mask_42_1 = 1 << 42 mask_42_0 = mask_42_1 ^ ones mask_192_1 = 1 << 192 mask_192_0 = mask_192_1 ^ ones # key bits affecting W[16][0] # # Bd = 0 # for i in [ 49, 51, 42, 192, 455, 466, 451, 480 ]: # Bd = (Bd << 1) | (Data >> i) & 1 # print( "Data = ", format(Bd,'08b')) # Bk = 0 # for i in [ 184, 186, 177, 109, 202, 213, 198, 224, 23 ]: # Bk = (Bk << 1) | (KEY >> i) & 1 # print( "Key =", format(Bk,'09b')) # Bx = Bd ^ (Bk >> 1) # print( " XOR = ", format(Bx,'08b')) # print( ((Bx>>7)&1)^((Bx>>6)&1)^((Bx>>5)&1), # "+", ((Bx>>4)&1), # "+", ((Bx>>3)&1)^((Bx>>2)&1)^((Bx>>1)&1), # "+", ((Bx>>0)&1) ) #-- Key7 = sha.ROTR( KEY & sha._mask, 3*7+(16>>3)) # Key[7] XOR with W[16] in VMAC() #-- print( "Key7 =", format(Key7,'032b')) # extract internal SHA-256 variables # def extract(H): h = (H - sha._H0[7]) & sha._mask; H >>= 32 g = (H - sha._H0[6]) & sha._mask; H >>= 32 f = (H - sha._H0[5]) & sha._mask; H >>= 32 e = (H - sha._H0[4]) & sha._mask; H >>= 32 d = (H - sha._H0[3]) & sha._mask; H >>= 32 c = (H - sha._H0[2]) & sha._mask; H >>= 32 b = (H - sha._H0[1]) & sha._mask; H >>= 32 a = (H - sha._H0[0]) & sha._mask; return (a,b,c,d,e,f,g,h) # extract V = T1 - offset = h + W[N-1] # # 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. # def reverse( D, N, K): H = sha.VMAC( D, N, K) W = sha.W[N-1] hprev = sha.hprev (an,b,c,d,e,f,g,h) = extract(H) # a = b; b = c; c = d; e = f; f = g; g = h T2 = (sha.Sigma0(a) + sha.Maj(a,b,c)) & sha._mask T1 = (an - T2) & sha._mask V = (T1 - sha.Sigma1(e) - sha.Ch(e,f,g) - sha._K[N-1]) & sha._mask # if V != (hprev + W) & sha._mask: print( "error in reverse, V is wrong") return (V, W, hprev) # each of these data bits affects one bit in the W[16][0] sum # #-- Dlist = [42, 192, 451, 480] #-- Vlist = [ V0 & 7 ] # lsb 3 bits #-- change one bit at a time #-- #-- for D in Dlist: #-- print( "D =", D) #-- mask1 = 1 << D #-- mask0 = ones ^ mask1 ne = eq = 0 # focus on last three bits of V: # # V = h + (D42 XOR Keff + D192 XOR K109 + u) XOR [K25, K24, K23] #--------------^^^^^^^^^^^^^^^^^^^^^^^^^^^^ # want this to be 1, i.e. 0+1 or 1+0, for a pair of (D42,D192) values # # u = 0 or 1 or 2 for i in range(1000): # input Data # Data = random.getrandbits(512); #-- Data = 0 # # reset bits which affect W[16][0,1,2] # for i in [49, 51, 42, 192, 455, 466, 451, 480]: # W[16][0] Data &= (1 << i) ^ ones for i in [50, 52, 43, 193, 456, 467, 452, 481]: # W[16][1] Data &= (1 << i) ^ ones for i in [51, 53, 44, 194, 457, 468, 453, 482]: # W[16[2] Data &= (1 << i) ^ ones # with bits (42,192) = (0,0), (1,0), (0,1), (1,1) # (V00, W00, hprev00) = reverse( Data, 17, KEY) (V11, W11, hprev11) = reverse( Data | mask_42_1 | mask_192_1, 17, KEY) (V01, W01, hprev01) = reverse( Data | mask_192_1, 17, KEY) (V10, W10, hprev10) = reverse( Data | mask_42_1, 17, KEY) # it turns out that hprev00 always equals hprev10, and hprev11 always equals hprev01 # because D42 does not affect hprev, and D192 does # # if( hprev00 != hprev10 or hprev11 != hprev01): print( "H error, h00!=h10 or h11!=h01") # continue # If the last three bits of V00 and V11 (or V01 and V10) are equal, # then in some cases the same is true for W and hprev - and if so then # changes in bits 42 and/or 192 should change W and V, but not hprev. # # TODO: take advantage of constant but unknown hprev somehow, # e.g. subtract two V values to cancel it? ZZ # # In this case we know that (D42 XOR Keff) + (D192 XOR K109) == 1 # so one term is 1 and the other is 0, but we can't tell which. # However if D42 == D192 (i.e. V00 == V11) then we know Keff != K109, # and if D42 != D192 (i.e. V01 == V10) then we know Keff == K109 # # if (V00 & 7) == (V11 & 7): ne += 1 # if (V01 & 7) == (V10 & 7): eq += 1 # continue # # ZZ: ne and eq counts come out about equal and inconsistent # need some other consistency check ZZ # # checking the concept # if True: # if (((V00 & 7) == (V11 & 7)) or ((V01 & 7) == (V10 & 7))) and \ # (hprev01 & 7) == (hprev10 & 7): # # in practice, with unknown key, can't check hprev value, # have to find multiple cases and check for result consistency? ZZ # SW00 = SV00 = Sh00 = SW01 = SV01 = Sh01 = "" if (W00 & 7) == (W11 & 7): SW00 = "*" if (V00 & 7) == (V11 & 7): SV00 = "*" if (hprev00 & 7) == (hprev11 & 7): Sh00 = "*" if (W01 & 7) == (W10 & 7): SW01 = "*" if (V01 & 7) == (V10 & 7): SV01 = "*" if (hprev01 & 7) == (hprev10 & 7): Sh01 = "*" print() print( "W00 =", format(W00,'032b'), SW00) print( "W11 =", format(W11,'032b')) print( "W01 =", format(W01,'032b'), SW01) print( "W10 =", format(W10,'032b')) print() print( "V00 =", format(V00,'032b'), SV00) print( "V11 =", format(V11,'032b')) print( "V01 =", format(V01,'032b'), SV01) print( "V10 =", format(V10,'032b')) print() print( "h00 =", format(hprev00,'032b'), Sh00) print( "h11 =", format(hprev11,'032b')) print( "h01 =", format(hprev01,'032b'), Sh01) print( "h10 =", format(hprev10,'032b')) if True: # if SV00: print( "V00-V01 =", format((V00-V01)&7,'03b'), \ " V00-V10 =", format((V00-V10)&7,'03b'), \ " V01-V10 =", format((V01-V10)&7,'03b'), SV00 ) # if Keff == K109: print( "error, Keff,109 wrong") # else: print("OK") # if SV01: print( "V01-V00 =", format((V01-V00)&7,'03b'), \ " V01-V11 =", format((V01-V11)&7,'03b'), \ " V00-V11 =", format((V00-V11)&7,'03b'), SV01 ) # if Keff != K109: print( "error, Keff,109 wrong") # else: print("OK") # break # print( "ne =", ne, "eq =", eq)