Cryptopals - set1


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)

Author: Mohamed Aziz Knani

Date: 2019-06-17 Mon 20:45

Emacs 26.2 (Org mode 9.2.1)

Validate

hacker emblem