Differential Cryptanalysis (AES CBC)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 CBC (Cipher Block Chaining) and where we change one bit of the plain text and then analyse the ciphertext for the number of bits that change [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 (CBC) for a message of "hello", a salt value of "1070000000000001" and a key of "qwerty123" gives 62 bit changes out of 128:
== Analysis of bits that change in a cipher with a one bit change in the plaintext== Message: hello Key: qwerty123 IV: 1070000000000001 Plain (original plain): b'hello\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b' Plain (1 bit change): b'iello\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b' Cipher (CBC) [0 bit change]: b'c96dc1fbe3fc4b2a8aa95e4a6c82ff8e' Cipher (CBC) [1 bit change]: b'0cb04671ebc74d1066b88999036a42cb' Bits changed: 62 out of 128 Cipher1: 11001001011011011100000111111011111000111111110001 Cipher2: 00001100101100000100011001110001111010111100011101 Changes: XX---X-XXX-XXX-XX----XXXX---X-X-----X-----XXX-XX-- Decrypt Res 1: hello Decrypt Res 2: iello
The sample code is:
# https://asecuritysite.com/cracking/diffcrypto from Crypto.Cipher import AES import hashlib import sys import binascii import Padding from bitstring import BitArray val='hello' password='qwerty123' iv ="1070000000000001" 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,iv): encobj = AES.new(key,mode,iv.encode()) return(encobj.encrypt(plaintext)) def decrypt(ciphertext,key, mode,iv): encobj = AES.new(key,mode,iv.encode()) 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 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("IV:\t\t\t",iv) plaintext= Padding.appendPadding(plaintext,blocksize=Padding.AES_blocksize,mode='CMS') 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()) ciphertext1 = encrypt(plaintext.encode(),key,AES.MODE_CBC,iv) ciphertext2 = encrypt(plaintext2.encode(),key,AES.MODE_CBC,iv) cipherbits1= tobits(ciphertext1) print("\nCipher (CBC) [0 bit change]: ",binascii.hexlify(bytearray(ciphertext1))) cipherbits2 = tobits(ciphertext2) print("Cipher (CBC) [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_CBC,iv) res2= decrypt(ciphertext2,key,AES.MODE_CBC,iv) print ("\n\nDecrypt Res 1:\t",Padding.removePadding(res1.decode(),blocksize=Padding.AES_blocksize,mode='CMS')) print ("Decrypt Res 2:\t",Padding.removePadding(res2.decode(),blocksize=Padding.AES_blocksize,mode='CMS'))