Assignment 3--Solutions to the Computer Problems

4. ECB Decryption

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.

In [9]: 
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)
In [10]: 
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==')
Out[10]:
"Tom and me found the money that the robbers hid in the cave, and it made us rich. We got six thousand dollars apiece -- all gold. It was an awful sight of money when it was piled up. Well, Judge Thatcher he took it and put it out at interest, and it fetched us a dollar a day apiece all the year round -- more than a body could tell what to do with. The Widow Douglas she took me for her son, and allowed she would sivilize me; but it was rough living in the house all the time, considering how dismal regular and decent the widow was in all her ways; and so when I couldn't stand it no longer I lit out. I got into my old rags and my sugar-hogshead again, and was free and satisfied. But Tom Sawyer he hunted me up and said he was going to start a band of robbers, and I might join if I would go back to the widow and be respectable. So I went back."

The passage is from The Adventures of Huckleberry Finn, by Mark Twain.

5. CBC Decryption

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.

In [12]: 
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)
In [13]: 
decrypt_cbc(12345,'K2fT1eaQz7jISFF7RP2JfXIBiWEgh958cUfyVtvodOm9zIN5WtHqshigP6Ds+Y1LO8VPBZpH50ZZauWo8pb7rW3n9sdoTw4yUU4AhfdEL3LsOoIdall9LbobnToaoVvwANJKifQNAix5yZy+QC1Yjk0Ju9uScSDmMuPYKl92vxBXN2P/3lpGaxdw+Q6LDb8MksxMYxQiNeGVGwaYaL/n7w5lY6iTj1uVY16KYmnO69sXXZhEsUB1IcnLGFafyxwm4JMGZJLei6KfFcubKwRv5Fmrtlk5p5R8DvC6hifeFHsuZgUqawkN9VV9WCiN6TErS1C8ooNzs/Kyg7tkGtN4pt+KAYxRywvYlpinRkLLvKf3FemGTc8nSMutQWyWdViReWNMwupNVgaDTyVGW/FRfVKH/3aIjZ9im9pdg0LZJR7PMkWp1Sb06du45n783hjILKnLC4kF8f6vra0+ahA/KL4Nyh2l2JQum2hf+IKjyPaqhAAJbBmgylcK+S/CMd5JCb6ITlOm1MO/zv6oNn9ohJMAsbpKk0wDWUNPN+2DRkFZ9nXFz6uiBsymyGmXTyuTBBfkC2qhVs3WVW1rZeoF+bHyRIMnSM7n4Drug3tg6OO5YTj2p0I9xsuP7N4pRGzSzFGnY2CzUKje1egH3C81Tsy6Hg/FKEoTPnCEROywljh5Yg42RAImoU2TPvtTT95gTbUKFxp5d3wraXUv/Sw5IKbAa9LexbC5aNXXuqZ7dw7dygxRLod7c4+4ev1mIqDm')
Out[13]:
"In my younger and more vulnerable years my father gave me some advice that I've been turning over in my mind ever since.  'Whenever you feel like criticizing any one,' he told me, 'just remember that all the people in this world haven't had the advantages that you've had.'  He didn't say any more, but we've always been unusually communicative in a reserved way, and I understood that he meant a great deal more than that.  I'm inclined to reserve all judgments, a habit that has opened up many curious natures to me and also made me the victim of not a few veteran bores."

From The Great Gatsby, by F. Scott Fitzgerald

6. CTR Decryption

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.

In [16]: 
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:])
In [17]: 
decrypt_ctr(12345,'BNJADVJq9I9vIOmFHvVjuLcDhusgLf1QJXlwTzp6tVzrYvaAWAD3GaUc1iVrDyEHmv7wx9piIXuFZccxPgfW+/0O5LCaH43yBTfczPJQ/B3CueLT7p/7NQdtRxgoQyL+g+tpV/7RD4oioxQGQnGe/5pSocb+RpWz26dt94TxNQ1Tju4fcG1isU8sYhZnUxLrUhtbvg/hW0D0BBVpTqCXG883vrCCQmK0XhkD/MnP13tR01Atm2Jx2YgzteyIhwxMpMa88kvhfs7aMFyWXgX1e+Evlcm4Ym4Ne0v+65PYeQpqknwqrrXyXBEFuojamv2ETGMb7K6toBrVRvMkohqkD1RwHrvPuTUO6tKR9fHlUpaxZc/3mahrIxBGtMk8EWwOHAnmChb8aW4e/yMleSoaTg==')
Out[17]:
"Mr Leopold Bloom ate with relish the inner organs of beasts and fowls. He liked thick giblet soup, nutty gizzards, a stuffed roast heart, liverslices fried with crustcrumbs, fried hencods' roes. Most of all he liked grilled mutton kidneys which gave to his palate a fine tang of faintly scented urine."

The passage is from Ulysses, by James Joyce.

7. Brute-force Attack on Baby Block Cipher

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.

In [7]: 
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)
In [10]: 
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')

key : 22752
done
Out[10]:
'In that part of the western division of this kingdom which is commonly called Somersetshire, there lately lived, and perhaps lives still, a gentleman whose name was Allworthy, and who might well be called the favorite of both nature and fortune; for both of these seem to have contended which should bless and enrich him most.  In this contention, nature may seem to some to have come off victorious, as she bestowed on him many gifts, while fortune had only one gift in her power; but in pouring forth this, she was so very profuse, that others perhaps may think this single endowment to have been more than equivalent to all the various blessings which he enjoyed from nature.  From the former of these, he derived an agreeable person, a sound constitution, a solid understanding, and a benevolent hear; by the latter, he was decreed to the inheritance of one of the largest estates in the county.'

The passage is from Tom Jones, by Henry Fielding

8. Collision Statistics

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.

In [3]: 
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

In [13]: 
collision_statistics(0)
Out[13]:
[24134, 24055, 12078, 4026, 1006, 203, 30, 4]
In [5]: 
collision_statistics(12345)
Out[5]:
[24044, 24105, 12195, 3995, 966, 199, 27, 5]
In [6]: 
collision_statistics(9999)
Out[6]:
[24007, 24257, 12063, 3968, 1002, 199, 35, 4, 1]

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.

In [12]: 
import math
[2**16*math.exp(-1)/math.factorial(j) for j in range(9)]
Out[12]:
[24109.347056611645,
 24109.347056611645,
 12054.673528305822,
 4018.2245094352743,
 1004.5561273588186,
 200.91122547176371,
 33.48520424529395,
 4.783600606470564,
 0.5979500758088205]

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.

In [14]: 
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
In [15]: 
collision_statistics_reduced(22222)
Out[15]:
[31690, 16230, 9511, 4490, 2177, 852, 363, 145, 59, 10, 8, 1]

The results are very different.

9. Meet-in-the-Middle Attack on Double Encryption

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.

In [1]: 
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

40033 7770
15922 40124

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.

In [1]: 
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)

collision with key  58152 and key  21786
65535

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.

In [4]: 
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]

collsion with encryption key  8460 and decryption key  28546
collsion with encryption key  11296 and decryption key  4186

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.

In [7]: 
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])
Out[7]:
'z\xe4'
In [8]: 
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])
Out[8]:
'ol'

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.

In [12]: 
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)
Out[12]:
'We hold these truths to be self-evident, that all men are created equal, that they are endowed by their Creator with certain unalienable Rights, that among these are Life, Liberty and the pursuit of Happiness. That to secure these rights, Governments are instituted among Men, deriving their just powers from the consent of the governed, That whenever any Form of Government becomes destructive of these ends, it is the Right of the People to alter or to abolish it, and to institute new Government, laying its foundation on such principles and organizing its powers in such form, as to them shall seem most likely to effect their Safety and Happines'

From The Declaration of Independence.