Crypotpals challenges are a fun way of learning practical cryptography instead of dry mathematical textbooks, I will be doing the challenges for the next couple of weeks.
Challenge 1:
def convert_hex_to_base64(hex): import base64 return base64.b64encode(hex.decode("hex"))
Challenge 2
def xor_two_strings(s1, s2): import binascii s1, s2 = s1.decode("hex"), s2.decode("hex") res = "" for i in range(len(s1)): res += chr(ord(s1[i]) ^ ord(s2[i])) return binascii.hexlify(res)
Challenge 3
from ch02 import xor_two_strings from collections import Counter from string import printable import binascii def bruteforce(ch): for i in range(256): yield xor_two_strings(ch, binascii.hexlify(chr(i)*len(ch))).decode("hex"), i
Doing this the ad-hoc way
def not_so_good_freq(ch, limit=3): FREQ = {'\x00': 0.0, '\x83': 0.0, '\x04': 0.0, '\x87': 0.0, '\x08': 0.0, '\x8b': 0.0, '\x0c': 0.0, '\x8f': 0.0, '\x10': 0.0, '\x93': 0.0, '\x14': 0.0, '\x97': 0.0, '\x18': 0.0, '\x9b': 0.0, '\x1c': 0.0, '\x9f': 0.0, ' ': 0.1601132522827019, '\xa3': 0.0, '$': 2.5223225546082834e-06, '\xa7': 0.0, '(': 0.00019043535287292538, '\xab': 0.0, ',': 0.016740654794935177, '\xaf': 0.0, '0': 2.5223225546082833e-05, '\xb3': 0.0, '4': 1.2611612773041417e-05, '\xb7': 0.0, '8': 2.0178580436866267e-05, '\xbb': 1.2611612773041417e-06, '<': 0.0, '\xbf': 1.2611612773041417e-06, '@': 2.5223225546082834e-06, '\xc3': 2.5223225546082834e-06, 'D': 0.0012485496645311003, '\xc7': 0.0, 'H': 0.0011186500529687736, '\xcb': 0.0, 'L': 0.0010530696665489582, '\xcf': 0.0, 'P': 0.0006255359935428543, '\xd3': 0.0, 'T': 0.002136407203753216, '\xd7': 0.0, 'X': 7.56696766382485e-05, '\xdb': 0.0, '\\': 0.0, '\xdf': 0.0, '`': 0.0, '\xe3': 0.0, 'd': 0.03412197951874086, '\xe7': 0.0, 'h': 0.04803384956868284, '\xeb': 0.0, 'l': 0.02675301417545276, '\xef': 1.2611612773041417e-06, 'p': 0.011935630328406397, '\xf3': 0.0, 't': 0.06602935983453564, '\xf7': 0.0, 'x': 0.000836149926852646, '\xfb': 0.0, '|': 0.0, '\xff': 0.0, '\x80': 0.0, '\x03': 0.0, '\x84': 0.0, '\x07': 0.0, '\x88': 0.0, '\x0b': 0.0, '\x8c': 0.0, '\x0f': 0.0, '\x90': 0.0, '\x13': 0.0, '\x94': 0.0, '\x17': 0.0, '\x98': 0.0, '\x1b': 0.0, '\x9c': 0.0, '\x1f': 0.0, '\xa0': 0.0, '#': 1.2611612773041417e-06, '\xa4': 0.0, "'": 0.0016004136608989558, '\xa8': 0.0, '+': 0.0, '\xac': 0.0, '/': 3.02678706552994e-05, '\xb0': 0.0, '3': 1.6395096604953842e-05, '\xb4': 0.0, '7': 1.7656257882257983e-05, '\xb8': 0.0, ';': 0.001397366695252989, '\xbc': 0.0, '?': 0.0011514402461786813, '\xc0': 0.0, 'C': 0.0009496544418100187, '\xc4': 0.0, 'G': 0.0004855470917620945, '\xc8': 0.0, 'K': 6.93638702517278e-05, '\xcc': 0.0, 'O': 0.00041366089895575846, '\xd0': 0.0, 'S': 0.0011300005044645109, '\xd4': 0.0, 'W': 0.0007630025727690057, '\xd8': 0.0, '[': 2.5223225546082834e-06, '\xdc': 0.0, '_': 0.00022953135246935377, '\xe0': 0.0, 'c': 0.016579226151440245, '\xe4': 0.0, 'g': 0.015338243454572971, '\xe8': 0.0, 'k': 0.005967815164203198, '\xec': 0.0, 'o': 0.05827700146294708, '\xf0': 0.0, 's': 0.04627326842556626, '\xf4': 0.0, 'w': 0.017045855824042777, '\xf8': 0.0, '{': 0.0, '\xfc': 0.0, '\x7f': 0.0, '\x81': 0.0, '\x02': 0.0, '\x85': 0.0, '\x06': 0.0, '\x89': 0.0, '\n': 0.02052035514301569, '\x8d': 0.0, '\x0e': 0.0, '\x91': 0.0, '\x12': 0.0, '\x95': 0.0, '\x16': 0.0, '\x99': 0.0, '\x1a': 0.0, '\x9d': 0.0, '\x1e': 0.0, '\xa1': 0.0, '"': 0.0071646572163648285, '\xa5': 0.0, '&': 0.0, '\xa9': 2.5223225546082834e-06, '*': 0.00011350451495737275, '\xad': 0.0, '.': 0.008594814104827726, '\xb1': 0.0, '2': 1.7656257882257983e-05, '\xb5': 0.0, '6': 1.1350451495737274e-05, '\xb9': 0.0, ':': 0.0003392523835948141, '\xbd': 0.0, '>': 0.0, '\xc1': 0.0, 'B': 0.0006747212833577157, '\xc5': 0.0, 'F': 0.0005511274781819099, '\xc9': 0.0, 'J': 0.0003543863189224638, '\xcd': 0.0, 'N': 0.0005208596075266105, '\xd1': 0.0, 'R': 0.0002774554810069112, '\xd5': 0.0, 'V': 0.0001450335468899763, '\xd9': 0.0, 'Z': 0.0, '\xdd': 0.0, '^': 0.0, '\xe1': 0.0, 'b': 0.009946778994097766, '\xe5': 0.0, 'f': 0.01655400292589416, '\xe9': 0.0, 'j': 0.0005460828330726933, '\xed': 0.0, 'n': 0.052933461131009434, '\xf1': 0.0, 'r': 0.046652877970034805, '\xf5': 0.0, 'v': 0.006418049740200777, '\xf9': 0.0, 'z': 0.00027114967462039046, '\xfd': 0.0, '~': 0.0, '\x01': 0.0, '\x82': 0.0, '\x05': 0.0, '\x86': 0.0, '\t': 0.0, '\x8a': 0.0, '\r': 0.02052035514301569, '\x8e': 0.0, '\x11': 0.0, '\x92': 0.0, '\x15': 0.0, '\x96': 0.0, '\x19': 0.0, '\x9a': 0.0, '\x1d': 0.0, '\x9e': 0.0, '!': 0.0012044090198254553, '\xa2': 0.0, '%': 1.2611612773041417e-06, '\xa6': 0.0, ')': 0.00019043535287292538, '\xaa': 0.0, '-': 0.0030658830651263684, '\xae': 0.0, '1': 7.945316047016092e-05, '\xb2': 0.0, '5': 1.6395096604953842e-05, '\xb6': 0.0, '9': 2.270090299147455e-05, '\xba': 0.0, '=': 0.0, '\xbe': 0.0, 'A': 0.0011312616657418151, '\xc2': 0.0, 'E': 0.0005208596075266105, '\xc6': 0.0, 'I': 0.003624577510972103, '\xca': 0.0, 'M': 0.0020493870756192302, '\xce': 0.0, 'Q': 3.6573677041820106e-05, '\xd2': 0.0, 'U': 0.00010215406346163547, '\xd6': 0.0, 'Y': 0.000552388639459214, '\xda': 0.0, ']': 2.5223225546082834e-06, '\xde': 0.0, 'a': 0.05961509357816678, '\xe2': 0.0, 'e': 0.09386318922463804, '\xe6': 0.0, 'i': 0.04810321343893457, '\xea': 0.0, 'm': 0.01724133582202492, '\xee': 0.0, 'q': 0.0008033597336427383, '\xf2': 0.0, 'u': 0.021007163396055087, '\xf6': 0.0, 'y': 0.014814861524491752, '\xfa': 0.0, '}': 0.0, '\xfe': 0.0} l = [] for br, i in bruteforce(ch): score = 0 for c in br: score += FREQ.get(c, 0) l.append((i, score, br)) return sorted(l, key=lambda x: x[1])[::-1][:limit]
Doing it the scientific way, if the two probability distributions are identical the output will converge to zero, so we need to minimize the output:
def chi_squared(ch, limit=3): # using a statistical method returns best "limit" candidates FREQ = { "e": 12.02, "t": 9.10, "a": 8.12, "o": 7.68, "i": 7.31, "n": 6.95, "s": 6.28, "r": 6.02, "h": 5.92, "d": 4.32, "l": 3.98, "u": 2.88, "c": 2.71, "m": 2.61, "f": 2.30, "y": 2.11, "w": 2.09, "g": 2.03, "p": 1.82, "b": 1.49, "v": 1.11, "k": 0.69, "x": 0.17, "q": 0.11, "j": 0.10, "z": 0.07} ls = [] for br, i in bruteforce(ch): cnt = Counter(br.lower()) s = 0 for key, val in cnt.iteritems(): try: e = (len(br) * FREQ[key] / 100) s += (val - e)**2 / e except KeyError: s += val**2 ls.append((i, s, br)) return sorted(ls, key=lambda x: x[1])[:limit]
Challenge 5
from itertools import cycle from binascii import hexlify def repeating_xor(text, key): l = "" k = 0 for i in cycle(key): try: l += chr(ord(i) ^ ord(text[k])) except IndexError: return l k += 1
Challenge 6
import sys from random import randint def popcount(x): setBits = 0 while (x > 0): setBits += x & 1 x /= 2 return setBits def hamming_distance(s1, s2): assert len(s1) == len(s2) f = 0 for i in range(len(s1)): f += popcount(ord(s1[i]) ^ ord(s2[i])) return f def find_keysize(cipher, keysize): blocknum = randint(1, 40) blocknum2 = randint(1, 40) if blocknum2 == blocknum: blocknum2 = randint(1, 40) block1, block2 = cipher[keysize*(blocknum-1):keysize*blocknum], cipher[keysize*(blocknum2-1):keysize*(blocknum2)] return float(hamming_distance(block1, block2)) / keysize def transpose(cipher, keysize): cipher = cipher + (keysize - (len(cipher) % keysize)) * "\x00" blocks = [cipher[i:i+keysize] for i in range(0, len(cipher), keysize)] return "".join(["".join(c) for c in zip(*blocks)])
With enough number of simulations the keysize will converge to the correct value, because the blocks are randomized each time
def simulation(cipher): smallestScore = sys.maxint keysize = 0 for KEYSIZE in range(10, 41): distance = find_keysize(cipher, KEYSIZE) if distance < smallestScore: smallestScore = distance keysize = KEYSIZE return keysize
Challenge 7
from Crypto.Cipher import AES def paddpkcs7(s, n): s = str(s) return s + ((n - len(s)) % n) * chr(n - len(s) % n) def unpadpkcs7(s): i = ord(s[-1]) return s[0:-i] def aes_ecb_decrypt(cipher, key): aes = AES.new(key, AES.MODE_ECB, "\x00" * 16) return aes.decrypt(cipher)
Challenge 8
def probably_ecb(cipher): blocks = [cipher[i:i+16] for i in range(0, len(cipher), 16)] for i, block1 in enumerate(blocks): for j, block2 in enumerate(blocks): if block1 == block2 and i != j: return True return False
Testing
To test it all up, here is the code:
#!/usr/bin/env python import binascii from base64 import b64decode from test import support import unittest from ch01 import convert_hex_to_base64 from ch02 import xor_two_strings from ch03 import chi_squared, bruteforce, not_so_good_freq from ch05 import repeating_xor from ch06 import simulation, hamming_distance, transpose from ch07 import aes_ecb_decrypt, unpadpkcs7 from ch08 import probably_ecb from collections import Counter class Set1(unittest.TestCase): poem = "I'm back and I'm ringin' the bell \nA rockin' on the mike while the fly girls yell \nIn ecstasy in the back of me \nWell that's my DJ Deshay cuttin' all them Z's \nHittin' hard and the girlies goin' crazy \nVanilla's on the mike, man I'm not lazy. \n\nI'm lettin' my drug kick in \nIt controls my mouth and I begin \nTo just let it flow, let my concepts go \nMy posse's to the side yellin', Go Vanilla Go! \n\nSmooth 'cause that's the way I will be \nAnd if you don't give a damn, then \nWhy you starin' at me \nSo get off 'cause I control the stage \nThere's no dissin' allowed \nI'm in my own phase \nThe girlies sa y they love me and that is ok \nAnd I can dance better than any kid n' play \n\nStage 2 -- Yea the one ya' wanna listen to \nIt's off my head so let the beat play through \nSo I can funk it up and make it sound good \n1-2-3 Yo -- Knock on some wood \nFor good luck, I like my rhymes atrocious \nSupercalafragilisticexpialidocious \nI'm an effect and that you can bet \nI can take a fly girl and make her wet. \n\nI'm like Samson -- Samson to Delilah \nThere's no denyin', You can try to hang \nBut you'll keep tryin' to get my style \nOver and over, practice makes perfect \nBut not if you're a loafer. \n\nYou'll get nowhere, no place, no time, no girls \nSoon -- Oh my God, homebody, you probably eat \nSpaghetti with a spoon! Come on and say it! \n\nVIP. Vanilla Ice yep, yep, I'm comin' hard like a rhino \nIntoxicating so you stagger like a wino \nSo punks stop trying and girl stop cryin' \nVanilla Ice is sellin' and you people are buyin' \n'Cause why the freaks are jockin' like Crazy Glue \nMovin' and groovin' trying to sing along \nAll through the ghetto groovin' this here song \nNow you're amazed by the VIP posse. \n\nSteppin' so hard like a German Nazi \nStartled by the bases hittin' ground \nThere's no trippin' on mine, I'm just gettin' down \nSparkamatic, I'm hangin' tight like a fanatic \nYou trapped me once and I thought that \nYou might have it \nSo step down and lend me your ear \n'89 in my time! You, '90 is my year. \n\nYou're weakenin' fast, YO! and I can tell it \nYour body's gettin' hot, so, so I can smell it \nSo don't be mad and don't be sad \n'Cause the lyrics belong to ICE, You can call me Dad \nYou're pitchin' a fit, so step back and endure \nLet the witch doctor, Ice, do the dance to cure \nSo come up close and don't be square \nYou wanna battle me -- Anytime, anywhere \n\nYou thought that I was weak, Boy, you're dead wrong \nSo come on, everybody and sing this song \n\nSay -- Play that funky music Say, go white boy, go white boy go \nplay that funky music Go white boy, go white boy, go \nLay down and boogie and play that funky music till you die. \n\nPlay that funky music Come on, Come on, let me hear \nPlay that funky music white boy you say it, say it \nPlay that funky music A little louder now \nPlay that funky music, white boy Come on, Come on, Come on \nPlay that funky music \n" def test_ch1(self): self.assertEqual(convert_hex_to_base64("49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d"), "SSdtIGtpbGxpbmcgeW91ciBicmFpbiBsaWtlIGEgcG9pc29ub3VzIG11c2hyb29t") def test_ch2(self): self.assertEqual( xor_two_strings("1c0111001f010100061a024b53535009181c", "686974207468652062756c6c277320657965"), "746865206b696420646f6e277420706c6179") def test_ch3(self): ch = "1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736" res = chi_squared(ch) results = [] for key in res: results.append(xor_two_strings(ch, binascii.hexlify(chr(key[0])*len(ch))).decode("hex")) self.assertIn("Cooking MC's like a pound of bacon", results) def test_ch4(self): l = [] with open("4.txt") as myfile: f = myfile.read() for line in f.splitlines(): for result, i in bruteforce(line): l.append(result) self.assertIn("Now that the party is jumping\n", l) def test_ch5(self): f = """Burning 'em, if you ain't quick and nimble\nI go crazy when I hear a cymbal""" r = """0b3637272a2b2e63622c2e69692a23693a2a3c6324202d623d63343c2a26226324272765272a282b2f20430a652e2c652a3124333a653e2b2027630c692b20283165286326302e27282f""" self.assertEqual(binascii.hexlify(repeating_xor(f, "ICE")), r) def test_ch6(self): with open("6.txt", "r") as myfile: cipher = b64decode(myfile.read()) self.assertEqual(hamming_distance("this is a test", "wokka wokka!!!"), 37) l = [] for _ in range(50): l.append(simulation(cipher)) keysize = Counter(l).most_common()[0][0] self.assertEqual(keysize, 29) self.assertEqual(transpose("abcdefg", 2), "acegbdf\x00") transposed = transpose(cipher, keysize) recovered_key = "" for block in [transposed[i:i+(len(transposed)/keysize)] for i in range(0, len(transposed), len(transposed)/keysize)]: recovered_key += chr(not_so_good_freq(binascii.hexlify(block))[0][0]) self.assertEqual(recovered_key, "Terminator X: Bring the noise") self.assertEqual(repeating_xor(cipher, recovered_key), self.poem) def test_ch7(self): with open("7.txt", "r") as myfile: cipher = b64decode(myfile.read()) out = unpadpkcs7(aes_ecb_decrypt(cipher, "YELLOW SUBMARINE")) self.assertEqual(out, self.poem) def test_ch8(self): with open("8.txt", "r") as myfile: lines = myfile.read().splitlines() for line in lines: if probably_ecb(binascii.unhexlify(line)): self.assertEqual(line, "d880619740a8a19b7840a8a31c810a3d08649af70dc06f4fd5d2d69c744cd283e2dd052f6b641dbf9d11b0348542bb5708649af70dc06f4fd5d2d69c744cd2839475c9dfdbc1d46597949d9c7e82bf5a08649af70dc06f4fd5d2d69c744cd28397a93eab8d6aecd566489154789a6b0308649af70dc06f4fd5d2d69c744cd283d403180c98c8f6db1f2a3f9c4040deb0ab51b29933f2c123c58386b06fba186a") break if __name__ == "__main__": support.run_unittest(Set1)
No comments:
Post a Comment