We basically only need to change one line of the encryption function to get the decryption function, but we need to begin with converting base 64 to bytes and end with bytes to ASCII. If a zero byte is found at the end of the plaintext, it is removed before the ASCII conversion.
import bytestuff
import babyblock
def decrypt_ecb(key,ct):
ctbytes=bytestuff.b64_to_bytes(ct)
pt=[]
for j in range(0,len(ctbytes),2):
block=256*ctbytes[j]+ctbytes[j+1]
ptblock=babyblock.decrypt(key,block)
pt.extend([ptblock/256,ptblock%256])
if pt[-1]==0:
pt=pt[:-1]
return bytestuff.bytes_to_ascii(pt)
decrypt_ecb(12345,'GYoVa65MgiR8IVJSeLeDewbebld6Al/Q31sG3vSTCgjr58MihhsETOrBjxql6YIk8z4G3m5X5ypT+MJ/Pz2De2MbCgiA6KY6+5KPGm4rStxZ9ja61tYAVlatPPsG3oq5Z6uuTIIk00kXCzP/jxodrX52gxfYN/XxB7uzjZdb0dVZ9hGATMO/6z89oSWIlTz5s41KvG7HCghrenoCX9DfW0zDblehJf1cTMO/6xlXwm0cSPuSosFDX4s9IAu+4PgRf0eUDvSTxDxuV8JAblcG3vBr8579XD89g3sZV6gRYxsKCHi3CghxnmMbjXPqwdnys90/PYN7YxsKCJN4xDxuV4IkZ6s/PdpMbKNHisJAJlQ6AU58Ha1+doMXPz0XCwbebleb9b21wkCGG/w3giQM2HoCP/zDIuvnrkw/PdYgcXdOfK9sBzOCJCPrFwtMw/STCggJvNpMkVorcOvnWfaRkcMiszvTSX112WBsGUeKjxrjAcMiCbw/5noCwyKBBsJAblfCQCL27k4/PYN7Pz0XC0l0HEhWrW5XTMN4t9HVVq0UzsJtbdHDInwh21Xs6woI/VxMw7/rDNV4t27HHxgUzvM+vT/zPgbebleJtHi3g4o/PRcLBt5uVwbe0R7Cf+cqX9BKvKY6biusM4m0SXTaTFZJgOizjW73ZYZHisJArkyCJKY6gxeNcwbebldMw6jqSXRMw7/rYxuhJQe7s41uV8JAQ9W0e9tVrkyCJCL2TMNuV6ElND2vbAczqtOCWlatEbmDe2MbCgil/h8YX9B/R8JAND2gIgoIeLfOOt6N1tYAVmMbjXORWmPcwInR1QzVy56PGq5MgiRj3FatbBkz/8ZuzuHjAb21giTLnpQ57k4/PYN7TMO/61JSbvfDIq5MgiTw1mazewF+dlN0uXKoEZQOXfEZAoiVYZ3CQG5XibT8NyPrgiR8IfuSCSmuTIIk8Nao6om0wyJD1Y8al1vzPr0/CbxWrRG5YTQ/PdYgrkyCJGt6DNWzw1TNBADO6K5MgiQ0Paz2bscKCJ8N8z5jG5NaND0BBgczgiSXW9YgRA3zngm8Bt5uV0zDqOpJdD89g3vWIMMibveWW3kGEblbgcawGQKRWjQ94rWNc9YgRA0V8Q==')
The passage is from The Adventures of Huckleberry Finn, by Mark Twain.
We have to covert to bytes, extract the IV from the first two bytes, and then recover the successive plaintext bytes and convert to ASCII. The main loop is the CBC decryption algorithm itself.
import bytestuff
import babyblock
def decrypt_cbc(key,ct):
ctbytes=bytestuff.b64_to_bytes(ct)
#extract iv
iv=256*ctbytes[0]+ctbytes[1]
ctbytes=ctbytes[2:]
firstblock=babyblock.decrypt(key,256*ctbytes[0]+ctbytes[1])^iv
ptbytes=[firstblock/256,firstblock%256]
for j in range(2,len(ctbytes),2):
nextblock=(256*ctbytes[j-2]+ctbytes[j-1])^babyblock.decrypt(key,256*ctbytes[j]+ctbytes[j+1])
ptbytes.extend([nextblock/256,nextblock%256])
#remove padding
if ptbytes[-1]==0:
ptbytes=ptbytes[:-1]
return bytestuff.bytes_to_ascii(ptbytes)
decrypt_cbc(12345,'K2fT1eaQz7jISFF7RP2JfXIBiWEgh958cUfyVtvodOm9zIN5WtHqshigP6Ds+Y1LO8VPBZpH50ZZauWo8pb7rW3n9sdoTw4yUU4AhfdEL3LsOoIdall9LbobnToaoVvwANJKifQNAix5yZy+QC1Yjk0Ju9uScSDmMuPYKl92vxBXN2P/3lpGaxdw+Q6LDb8MksxMYxQiNeGVGwaYaL/n7w5lY6iTj1uVY16KYmnO69sXXZhEsUB1IcnLGFafyxwm4JMGZJLei6KfFcubKwRv5Fmrtlk5p5R8DvC6hifeFHsuZgUqawkN9VV9WCiN6TErS1C8ooNzs/Kyg7tkGtN4pt+KAYxRywvYlpinRkLLvKf3FemGTc8nSMutQWyWdViReWNMwupNVgaDTyVGW/FRfVKH/3aIjZ9im9pdg0LZJR7PMkWp1Sb06du45n783hjILKnLC4kF8f6vra0+ahA/KL4Nyh2l2JQum2hf+IKjyPaqhAAJbBmgylcK+S/CMd5JCb6ITlOm1MO/zv6oNn9ohJMAsbpKk0wDWUNPN+2DRkFZ9nXFz6uiBsymyGmXTyuTBBfkC2qhVs3WVW1rZeoF+bHyRIMnSM7n4Drug3tg6OO5YTj2p0I9xsuP7N4pRGzSzFGnY2CzUKje1egH3C81Tsy6Hg/FKEoTPnCEROywljh5Yg42RAImoU2TPvtTT95gTbUKFxp5d3wraXUv/Sw5IKbAa9LexbC5aNXXuqZ7dw7dygxRLod7c4+4ev1mIqDm')
From The Great Gatsby, by F. Scott Fitzgerald
The form of the code is the same as CBC encryption, but since encryption = decryption in CTR mode, we can replace the main loop by a single call to the encryption function.
import bytestuff
import babyblock
import modes_of_operation
def decrypt_ctr(key,ct):
ctbytes=bytestuff.b64_to_bytes(ct)
#extract iv
iv=256*ctbytes[0]+ctbytes[1]
ctbytes=ctbytes[2:]
ptbytes=modes_of_operation.encrypt_ctr(key,ctbytes,iv)
#remove padding
if ptbytes[-1]==0:
ptbytes=ptbytes[:-1]
#remove the counter bytes that were placed there by the encrypt function
#and convert to ASCII
return bytestuff.bytes_to_ascii(ptbytes[2:])
decrypt_ctr(12345,'BNJADVJq9I9vIOmFHvVjuLcDhusgLf1QJXlwTzp6tVzrYvaAWAD3GaUc1iVrDyEHmv7wx9piIXuFZccxPgfW+/0O5LCaH43yBTfczPJQ/B3CueLT7p/7NQdtRxgoQyL+g+tpV/7RD4oioxQGQnGe/5pSocb+RpWz26dt94TxNQ1Tju4fcG1isU8sYhZnUxLrUhtbvg/hW0D0BBVpTqCXG883vrCCQmK0XhkD/MnP13tR01Atm2Jx2YgzteyIhwxMpMa88kvhfs7aMFyWXgX1e+Evlcm4Ym4Ne0v+65PYeQpqknwqrrXyXBEFuojamv2ETGMb7K6toBrVRvMkohqkD1RwHrvPuTUO6tKR9fHlUpaxZc/3mahrIxBGtMk8EWwOHAnmChb8aW4e/yMleSoaTg==')
The passage is from Ulysses, by James Joyce.
For each key, decrypt the first twenty bytes, and check if they are all in the range 0..127. If this holds, there is a high probability (million to one) that the correct key has been found, so return the decryption.
import babyblock
import bytestuff
import modes_of_operation
def decrypt_brute(ciphertext):
ctbytes=bytestuff.b64_to_bytes(ciphertext)
found=False
key = -1
while not found and key<65536:
key+=1
v=[babyblock.decrypt(key,256*ctbytes[2*j]+ctbytes[2*j+1]) for j in range(10)]
found=True
for u in v:
if u/256>127 or u%256>127:
found = False
print 'key :',key
print 'done'
return decrypt_ecb(key,ciphertext)
decrypt_brute('yqtaDj/hWklqWL6KAqsapUWhvKC36ls7BFxtR/MDfWTx3BZ2AqsapUWhQYq4YGS/4Zpex4C7apcFg2wGoKizTjjlFnYwqIju411CRc93xpvStyZaCCtA/dYo4phaDuY3TDOmSwgq27GAisyUGfcJ560qfRowXwRcP+GRp6ZLdqRtdcCHb9DHqjhppeXP14xIQkXNh21Hqf0db7ygg+XSt4C7TiOTgseqYWW+inCoOGm/OM93qf0l5RjpFypaSbfqx6oxELygT0LHqj29Wg7mN6aklFQ4KicivKBDvDEQEO7tV4Pl1jdMM60qfRqmpDgq1jcP+whW+RmArAxrRaECqxqlRaFtdbyglKG6yVoOJeU/4Rn3iO4WdnnyfRo9vYC7apcFg8CHVk2T3s93YD1tdaCovzjPd4wUiaEFg5OLXZXg0h1vv6MDz8qrWg5ql6Cos06MSIwUb9AWdjhpg+XWN0wz4NKk5MCHymQjhQMPwIdex7ygAw+Ti5RUvKCzTtK3Aqsl/uZaKm8DD4mhd/ZR4K0qoKhA/byg3ptbOw/wPb0Cq21Hapcjhc2HaeevHsEU8C44aan9Cn28oPkZvorJVrygP+HPdxZ2MKgCqw/7rx7BFFpJZL+TiwRcMF8P8ARcCFad/1pJZL8wX3f2iaHwC6akOCpFoVoOapdR4MCH5jeAu04jwIcl5Rn3h08wX9ohWpeUoThpRaEIKgKrRaEEXKCoujnXbgkqoKjNh4CKRaFkv94vRaFBisCHZL/TsbygjBTJL+1HjBRaSQMPk4uUVLyg3puMFODSOCq8oEWhvzgr4JrqdqTjXYwUWkkDD60qx6paDuY35lo8GAP+kqAxEEJFTwhkvwm/gLtqlwWDk4u8oIwU6zj9ws93oXlex/rZCCpvHARKA884G17HWg7mN6akOCrSt4CsQ7xaDuY3lKE4aeY3GDwEXHakPb2tKm1HpQdMM55mYD28oLo5JloWdjhppeUQNclWz3ezTj02b9DWN2/QFnY4aaXlEDXMlM93yVY3qCZaUzV9GmS/pMitKn0arSoxEIwUNUbcC4wUWknmNzwYCFYQf1oO5jemSwgqefKAmJOLvKBJAKCoN6ioLspkz3cDD1oO5jdsBoHKBFwnIr84yagCqxqlFna8oEO8Wg7mN6ZLPBjP11s7K+BbOwgqbXVsBm1HRaG8oLNOyVZT2L7D')
The passage is from Tom Jones, by Henry Fielding
The code below creates a dictionary containing each ciphertext block that occurs, together with the number of occurrences. This is then used to create a list (essentially a histogram) that gives the number of ciphertexts that occur 0,1,2,... times.
import babyblock
def collision_statistics(M):
tabulation={}
for key in range(65536):
C=babyblock.encrypt(key,M)
if C in tabulation:
tabulation[C]+=1
else:
tabulation[C]=1
#cell 0 of the return value is the
#number of blocks that don't occur
#as ciphertexts
histogram=[65536-len(tabulation)]
maxval=max(tabulation.values())
for j in range(1,maxval+1):
histogram.append(len([v for v in tabulation if tabulation[v]==j]))
return histogram
Let's run this for a few different starting plaintext blocks
collision_statistics(0)
collision_statistics(12345)
collision_statistics(9999)
Here are the values predicted by the Poisson distribution. Since the number of blocks is the same as the number of keys, we have λ=1, which simplifies the expression for the probabilities.
import math
[2**16*math.exp(-1)/math.factorial(j) for j in range(9)]
The agreement is very close. In this respect, at least, our invented cipher is behaving the way we would like it to. Here for purposes of comparison is the problem reworked with only two rounds of the block cipher.
import babyblock
def collision_statistics_reduced(M):
tabulation={}
for key in range(65536):
C=babyblock.encrypt(key,M,numrounds=2)
if C in tabulation:
tabulation[C]+=1
else:
tabulation[C]=1
#cell 0 of the return value is the
#number of blocks that don't occur
#as ciphertexts
histogram=[65536-len(tabulation)]
maxval=max(tabulation.values())
for j in range(1,maxval+1):
histogram.append(len([v for v in tabulation if tabulation[v]==j]))
return histogram
collision_statistics_reduced(22222)
The results are very different.
The posted base 64-encoded ciphertext was obtained by encrypting each block twice, under two different 16-bit baby block keys, using CBC mode. The first four characters of plaintext are 'We h'. Let's first extract the 2 known plaintext-ciphertext pairs from this information. We need to convert the base-64 encoding back to a list of byte values. Then we extract the input blocks to encryption for the first and second blocks; these are the data to which we will apply the attack.
import bytestuff
ct64='ywQeWpy8MhTTHOY59fxO1aJ1x4h8049CAuoUx8S9unrpj+iXkh8FLgTU3ITqFoXscLpTcI7jgGxXnSHBmseCyqsGvZZbefvZNB/sFlLw6y/g1+rlBAnMHLFxMZEIJPGgaBzViL6xUU1h640OtBal8YhGtcGqUygjFP4CFMXADnZH03kksiDas5nPU8ykh8Kw54p6ehdYwxLyiWKSvyndkOAffrmsWZSmr08zPdidaH8f4o5FxnH+EZCVq487KVUzRSTNtA3vCngd8eNBPCnz34q18xvaBSgDHuelyZQ/DEwevH3Ii/ICMnSFloRw2JP0ngWdHUlfrnLQCtq6oJ1lVX+I//ubrK1n/1cE9EHo4ZlBFMrZLc3R6anGvgvfvjWX7UPoJX3Sd9tDdARheLA6Edh98gL78fOhghg23d7MBX6OfTycd811Z9ferNimbS5GZhnTzkmot/iJ89en+1zLPOypl6L6h/TDHykfhuY/A7/iEoESGsE39OO6SNcuQFAnUZse42X5Zz3ngyfTuwELSvWOw7okrFIi0/d1yNzF9yaOmIaXhvlc2hNG6zyuRT7y5oKBXktJvqAYfX9+bZjCOkPcDSe71rxDooY3BWHffHO37lf1rWX23HFJY8QoyMFSBTGPD5YSQVfe02+X916WJDzTeTLJvZlKm0XzHr4tS3dNUUAJRhH5ogcg1VZApLlXkKCNuywAWUYlgBExumJ+1s98EHKj9wsR2qOYfmfX/rLUqU0IlQ3z8wGIKmg7kFDAGSgt78AAJlX5ni79x8Kq0OnR/yrFg8psmuyRleBC7tHg4HnHaLIdibvMpy2O/zS3L6800KXnrPkOS3FWUOlv/m/q7F3R9bATITnH2RhR'
ct=bytestuff.b64_to_bytes(ct64)
ptblock_1=bytestuff.ascii_to_bytes('We')
ptblock_2=bytestuff.ascii_to_bytes(' h')
first_input=bytestuff.xor(ct[:2],ptblock_1)
second_input=bytestuff.xor(ct[2:4],ptblock_2)
firstinval=256*first_input[0]+first_input[1]
secondinval=256*second_input[0]+second_input[1]
firstoutval=256*ct[2]+ct[3]
secondoutval=256*ct[4]+ct[5]
print firstinval,firstoutval
print secondinval,secondoutval
We'll decrypt the pair of output blocks under all possible keys, and create a dictionary entry whose key is the pair of blocks we found and whose value is the key we used.
import babyblock
big_dictionary={}
for k in range(65536):
blockpair=(babyblock.decrypt(k,7770),babyblock.decrypt(k,40124))
if not blockpair in big_dictionary:
big_dictionary[blockpair]=k
else:
print 'collision with key ', k, 'and key ',big_dictionary[blockpair]
print len(big_dictionary)
We'll just make a note of the fact that a block pair in our table was obtained withe two different keys. We now proceed to encrypt the input values under all different keys, and see if the blockpair matches something that's already in the dictionary.
for k in range(65536):
blockpair=(babyblock.encrypt(k,40033),babyblock.encrypt(k,15922))
if blockpair in big_dictionary:
print 'collsion with encryption key ', k, 'and decryption key ',big_dictionary[blockpair]
The entry that gave us a collision in the original construction of the table will not be an issue. But we have found two possible solutions for the pair of keys. What we will try to do is decrypt the third block of ciphertext under both these keys and see if what we get is ASCII text.
thirdoutval=256*ct[6]+ct[7]
thirdinval=babyblock.decrypt(8460,babyblock.decrypt(28546,thirdoutval))
thirdplain=(secondoutval^thirdinval)
thirdplain_hi=thirdplain/256
thirdplain_lo=thirdplain%256
bytestuff.bytes_to_ascii([thirdplain_hi,thirdplain_lo])
thirdinval=babyblock.decrypt(11296,babyblock.decrypt(4186,thirdoutval))
thirdplain=(secondoutval^thirdinval)
thirdplain_hi=thirdplain/256
thirdplain_lo=thirdplain%256
bytestuff.bytes_to_ascii([thirdplain_hi,thirdplain_lo])
Great! The key pair 11296, 4186 works. The first six characters of the plaintext are 'We hol'. Now we can proceed to decrypt the entire ciphertext. Remeber that cells ct[0:2] hold the IV.
pt=[]
for j in range(2,len(ct)-2,2):
prevblock=256*ct[j-2]+ct[j-1]
thisblock=256*ct[j]+ct[j+1]
decrypted_block=babyblock.decrypt(11296,babyblock.decrypt(4186,thisblock))
plainblock=decrypted_block^prevblock
pt+=[plainblock/256,plainblock%256]
bytestuff.bytes_to_ascii(pt)
From The Declaration of Independence.