Crib dragging

following http://travisdazell.blogspot.com/2012/11/many-time-pad-attack-crib-drag.html



In [5]:

    
m1 = "hello world!!".encode('hex')
m2 = "other message".encode('hex')
key = "secretkey123!".encode('hex')
print 'm1: {}\nm2: {}\nkey: {}'.format(m1, m2, key)
print len(m1), len(m2), len(key)









    



m1: 68656c6c6f20776f726c642121
m2: 6f74686572206d657373616765
key: 7365637265746b657931323321
26 26 26



In [2]:

    
ct1 = hex(int(m1, 16) ^ int(key, 16))[2:-1]
ct2 = hex(int(m2, 16) ^ int(key, 16))[2:-1]
print 'ct1: {}\nct2: {}'.format(ct1, ct2)









    



ct1: 1b000f1e0a541c0a0b5d561200
ct2: 1c110b17175406000a42535444



In [3]:

    
ctx = hex(int(ct1, 16) ^ int(ct2, 16))[2:-1]
print 'ctx: {}'.format(ctx)









    



ctx: 71104091d001a0a011f054644

To demonstrate the OTP, we can decrypt the CTs by XOR'ing with the key (k): $ c_{n} \oplus k = m_{n} $



In [4]:

    
print hex(int(ct1, 16) ^ int(key, 16))[2:-1].decode('hex')
print hex(int(ct2, 16) ^ int(key, 16))[2:-1].decode('hex')









    



hello world!!
other message



In [6]:

    
import string
space = ' '.encode('hex')

def attack(crib, ctx):
    width = len(crib)
    print 'crib in hex: {}\ncrib width: {}\n------------'.format(crib, width)
    for i in range(0, len(ctx)):
        decoded = hex(int(crib, 16) ^ int(ctx[i:i+width], 16))[2:].decode('hex')
        if decoded.isalpha():
            print "{}:{}\t".format(i, i+width), '{} XOR {}'.format(crib, ctx[i:i+width]), decoded
            
attack(space, ctx)









    



crib in hex: 20
crib width: 2
------------
0:2	20 XOR 71 Q
20:22	20 XOR 54 t
21:23	20 XOR 46 f
22:24	20 XOR 64 D
23:25	20 XOR 44 d

The assignment asks us to examine what happens when we a space character ' ' with uppercase or lowercase letters:



In [6]:

    
for i in string.uppercase[:10]:
    print hex(int(' '.encode('hex'), 16) ^ int(i.encode('hex'), 16))[2:].decode('hex')









    



a
b
c
d
e
f
g
h
i
j

So, if we XOR a space with a letter we'll get it's opposite case. Thus far we have several candidates, if we didn't know anything about the PTs we'd have to expand our search with each candidate. For brevity's sake I'll expand the search with knowledge of the PT.

We know that all the letters in the PTs are lowercase so and that there are no 'q', 't', or 'f' characters so that narrows it down to 20 XOR 64 which produces 'D'



In [7]:

    
crib = ' '.encode('hex')
attack(crib, ctx)









    



crib in hex: 20
crib width: 2
------------
0:2	20 XOR 71 Q
20:22	20 XOR 54 t
21:23	20 XOR 46 f
22:24	20 XOR 64 D
23:25	20 XOR 44 d

In this demonstration I'll proceed with knowledge of the PT to expand the crib. Note that by XOR'ing with the crib we get the plaintext of the second message:



In [12]:

    
crib = 'World!!'.encode('hex')
attack(crib, ctx)









    



crib in hex: 576f726c642121
crib width: 14
------------
11:25	576f726c642121 XOR 1a0a011f054644 Message
13:27	576f726c642121 XOR 0a011f054644 Wessage
14:28	576f726c642121 XOR a011f054644 Wessage
15:29	576f726c642121 XOR 011f054644 Wossage
16:30	576f726c642121 XOR 11f054644 Wossage
17:31	576f726c642121 XOR 1f054644 Worsage
18:32	576f726c642121 XOR f054644 Worcage
19:33	576f726c642121 XOR 054644 Worlage
20:34	576f726c642121 XOR 54644 Worlage
21:35	576f726c642121 XOR 4644 Worldge



In [ ]:

    
ct1 = 0x315c4eeaa8b5f8aaf9174145bf43e1784b8fa00dc71d885a804e5ee9fa40b16349c146fb778cdf2d3aff021dfff5b403b510d0d0455468aeb98622b137dae857553ccd8883a7bc37520e06e515d22c954eba5025b8cc57ee59418ce7dc6bc41556bdb36bbca3e8774301fbcaa3b83b220809560987815f65286764703de0f3d524400a19b159610b11ef3e
ct2 = 0x234c02ecbbfbafa3ed18510abd11fa724fcda2018a1a8342cf064bbde548b12b07df44ba7191d9606ef4081ffde5ad46a5069d9f7f543bedb9c861bf29c7e205132eda9382b0bc2c5c4b45f919cf3a9f1cb74151f6d551f4480c82b2cb24cc5b028aa76eb7b4ab24171ab3cdadb8356f
ct3 = 0x32510ba9a7b2bba9b8005d43a304b5714cc0bb0c8a34884dd91304b8ad40b62b07df44ba6e9d8a2368e51d04e0e7b207b70b9b8261112bacb6c866a232dfe257527dc29398f5f3251a0d47e503c66e935de81230b59b7afb5f41afa8d661cb
ct4 = 0x32510ba9aab2a8a4fd06414fb517b5605cc0aa0dc91a8908c2064ba8ad5ea06a029056f47a8ad3306ef5021eafe1ac01a81197847a5c68a1b78769a37bc8f4575432c198ccb4ef63590256e305cd3a9544ee4160ead45aef520489e7da7d835402bca670bda8eb775200b8dabbba246b130f040d8ec6447e2c767f3d30ed81ea2e4c1404e1315a1010e7229be6636aaa
ct5 = 0x3f561ba9adb4b6ebec54424ba317b564418fac0dd35f8c08d31a1fe9e24fe56808c213f17c81d9607cee021dafe1e001b21ade877a5e68bea88d61b93ac5ee0d562e8e9582f5ef375f0a4ae20ed86e935de81230b59b73fb4302cd95d770c65b40aaa065f2a5e33a5a0bb5dcaba43722130f042f8ec85b7c2070
ct6 = 0x32510bfbacfbb9befd54415da243e1695ecabd58c519cd4bd2061bbde24eb76a19d84aba34d8de287be84d07e7e9a30ee714979c7e1123a8bd9822a33ecaf512472e8e8f8db3f9635c1949e640c621854eba0d79eccf52ff111284b4cc61d11902aebc66f2b2e436434eacc0aba938220b084800c2ca4e693522643573b2c4ce35050b0cf774201f0fe52ac9f26d71b6cf61a711cc229f77ace7aa88a2f19983122b11be87a59c355d25f8e4
ct7 = 0x32510bfbacfbb9befd54415da243e1695ecabd58c519cd4bd90f1fa6ea5ba47b01c909ba7696cf606ef40c04afe1ac0aa8148dd066592ded9f8774b529c7ea125d298e8883f5e9305f4b44f915cb2bd05af51373fd9b4af511039fa2d96f83414aaaf261bda2e97b170fb5cce2a53e675c154c0d9681596934777e2275b381ce2e40582afe67650b13e72287ff2270abcf73bb028932836fbdecfecee0a3b894473c1bbeb6b4913a536ce4f9b13f1efff71ea313c8661dd9a4ce
ct8 = 0x315c4eeaa8b5f8bffd11155ea506b56041c6a00c8a08854dd21a4bbde54ce56801d943ba708b8a3574f40c00fff9e00fa1439fd0654327a3bfc860b92f89ee04132ecb9298f5fd2d5e4b45e40ecc3b9d59e9417df7c95bba410e9aa2ca24c5474da2f276baa3ac325918b2daada43d6712150441c2e04f6565517f317da9d3
ct9 = 0x271946f9bbb2aeadec111841a81abc300ecaa01bd8069d5cc91005e9fe4aad6e04d513e96d99de2569bc5e50eeeca709b50a8a987f4264edb6896fb537d0a716132ddc938fb0f836480e06ed0fcd6e9759f40462f9cf57f4564186a2c1778f1543efa270bda5e933421cbe88a4a52222190f471e9bd15f652b653b7071aec59a2705081ffe72651d08f822c9ed6d76e48b63ab15d0208573a7eef027
ct10 = 0x466d06ece998b7a2fb1d464fed2ced7641ddaa3cc31c9941cf110abbf409ed39598005b3399ccfafb61d0315fca0a314be138a9f32503bedac8067f03adbf3575c3b8edc9ba7f537530541ab0f9f3cd04ff50d66f1d559ba520e89a2cb2a83
target = 0x32510ba9babebbbefd001547a810e67149caee11d945cd7fc81a05e9f85aac650e9052ba6a8cd8257bf14d13e6f0a803b54fde9e77472dbff89d71b57bddef121336cb85ccb8f3315f4b52e301d16e9f52f904