Differential Cryptanalysis (AES CTR)A differential attack on a block cipher is where we analyse the change between one plaintext value and another, and the change that it makes on the output ciphers. In many cases we change one bit in the input, and observe one bit change on the input and observe the change in the output. A well designed cipher will cause an average of 50% of the bits to change. If the result is non-random, it gives an attacker an advantage in cracking the block cipher. In the following we will use AES with CTR (Counter) and where we change one bit of the plain text and then analyse the ciphertext for the number of bits that change. With CTR mode, we use a counter value for each block, and where we create a stream cipher (there is thus no need for padding). Each block then has a counter value, and where the counter value should not be used in any future block, as it is fairly trival to then crack the cipher [AES ECB][Hash][AES CBC][AES CFB][AES CTR]: |
Outline
A differential attack on a block cipher is where we analyse the change between one plaintext value and another, and the change that it makes on the output ciphers. In many cases we change one bit in the input, and observe one bit change on the input and observe the change in the output. A well designed cipher will cause an average of 50% of the bits to change. If the result is non-random, it gives an attacker an advantage in cracking the block cipher.
The differential cryptanalysis method was created in the 1990s and where it was possible to change a single bit in plaintext (P and P’) and then observe the change in the output ciphertext (C and C’):
The difference in encryption is then created with the addition of the key, and where parts of the key will be revealed through the differential method.
An S-box is often used in a crypto method, and where it is possible to follow a bit through each round and watch how it will be routed to the output, and we can then discover parts of the keys. As the differential cryptanalysis was being defined, IBM found-out that a common encryption method — DES (Data Encryption Standard) — was free of attacks for its S-boxes. It has since been shown that the NSA had actually defined an update to the original S-box specification for DES, in order to improve its resistance. It is thought that the NSA was actually trying to shore-up the DES method, in order that differential cryptanalysis would not show that it to be flawed.
While the differential cryptanalysis was published by Eli Biham and Adi Shamir in the late 1980s, it is thought that the NSA already knew about the technique before it was made public.
A sample run of AES (CTR) for a message of "hello", a counter value of "2" and a key of "qwerty123" gives 79 bit changes out of 144:
== Analysis of bits that change in a cipher with a one bit change in the plaintext== Message: hello how are you? Key: qwerty123 Counter: 2 Plain (original plain): b'hello how are you?' Plain (1 bit change): b'iello how are you?' Cipher (CFB) [0 bit change]: b'3bdfe9b0b7fa33ee93b1b1f1266f08fbc62e' Cipher (CFB) [1 bit change]: b'3adfe9b0b7fa33ee93b1b1f1266f08fbc62e' Bits changed: 143 out of 144 Cipher1: 00111011110111111110100110110000101101111111101000 Cipher2: 00111010110111111110100110110000101101111111101000 Changes: -------X------------------------------------------ Decrypt Res 1: hello how are you? Decrypt Res 2: iello how are you?
The sample code is:
# https://asecuritysite.com/cracking/diffcrypto5 from Crypto.Cipher import AES import hashlib import sys import binascii from bitstring import BitArray from Crypto.Util import Counter val='hello how are you?' password='qwerty123' counter ="2" plaintext=val def tobits(s): instr=binascii.hexlify(s).decode() c = BitArray(hex=instr) return c.bin def frombits(bits): chars = [] for b in range(len(bits) // 8): byte = bits[b*8:(b+1)*8] chars.append(chr(int(''.join([str(bit) for bit in byte]), 2))) return ''.join(chars) def encrypt(plaintext,key, mode,ctr): encobj = AES.new(key,mode,counter=ctr) return(encobj.encrypt(plaintext)) def decrypt(ciphertext,key, mode,ctr): encobj = AES.new(key,mode,counter=ctr) return(encobj.decrypt(ciphertext)) def diff(c1,c2): counter=0 str1='' str2='' str3='' for x in range(len(c1)): str1 = str1+str(c1[x]) str2 = str2+str(c2[x]) if (c1[x]==c2[x]): counter=counter+1 str3=str3+"-" else: str3=str3+"X" return str1,str2,str3,counter if (len(sys.argv)>1): plaintext=(sys.argv[1]) if (len(sys.argv)>2): password=(sys.argv[2]) if (len(sys.argv)>3): salt=(sys.argv[3]) key = hashlib.sha256(password.encode()).digest() print ("== Analysis of bits that change in a cipher with a one bit change in the plaintext==") print("\nMessage:\t",plaintext) print("Key:\t\t",password) print("Counter:\t",counter) plaintext2 = bytearray(plaintext.encode()) plaintext2[0]=plaintext2[0] ^ 1 plaintext2 = bytes(plaintext2).decode() print ("\nPlain (original plain):\t",plaintext.encode()) print ("Plain (1 bit change):\t",plaintext2.encode()) ctr=Counter.new(AES.block_size * 8,initial_value=int(counter)) ciphertext1 = encrypt(plaintext.encode(),key,AES.MODE_CTR,ctr) ciphertext2 = encrypt(plaintext2.encode(),key,AES.MODE_CTR,ctr) cipherbits1= tobits(ciphertext1) print("\nCipher (CFB) [0 bit change]: ",binascii.hexlify(bytearray(ciphertext1))) cipherbits2 = tobits(ciphertext2) print("Cipher (CFB) [1 bit change]: ",binascii.hexlify(bytearray(ciphertext2))) str1,str2,str3,counter = diff(cipherbits1,cipherbits2) print("\nBits changed:",counter," out of ",len(cipherbits1)) print("Cipher1:",str1[:50]) print("Cipher2:",str2[:50]) print("Changes:",str3[:50]) res1= decrypt(ciphertext1,key,AES.MODE_CTR,ctr) res2= decrypt(ciphertext2,key,AES.MODE_CTR,ctr) print ("\n\nDecrypt Res 1:\t",res1.decode()) print ("Decrypt Res 2:\t",res2.decode())