Snippets

Set 1

Challenge 1 - Convert hex to base64

import base64 
base64.b64encode("49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d".decode("hex"))

Challenge 2 - Fixed XOR

from itertools import cycle

def xor_mb(message, key):
    return''.join(chr(ord(m_byte)^ord(k_byte)) for m_byte,k_byte in zip(message, cycle(key)))

xor_mb("1c0111001f010100061a024b53535009181c".decode('hex'), "686974207468652062756c6c277320657965".decode('hex')).encode('hex')

Challenge 3 - Single-byte XOR cipher

from collections import Counter
message = "1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736".decode('hex')
cnt = Counter(message)
cnt.most_common(3)
for vv in cnt.most_common(7):
    for char in "ETAOIN SHRDLU".lower():
        key = chr(ord(vv[0]) ^ ord(char))
        print key, xor_mb(message, key)

Challenge 4 - Detect single-character XOR

Solution using limited frequency analysis approach

import string
from collections import Counter
from itertools import cycle

def xor_mb(message, key):
        return''.join(chr(ord(m_byte)^ord(k_byte)) for m_byte,k_byte in zip(message, cycle(key)))

printset = set(string.printable)
messages = open("4.txt", 'r').readlines()

for line in messages:
    message = line.rstrip().decode('hex')
    cnt = Counter(message)
    for vv in cnt.most_common(3):
            for char in "ETAOINSHRDLU".lower():
                key = chr(ord(vv[0]) ^ ord(char))
                temp = xor_mb(message, key)
                if set(temp).issubset(printset) and temp[-1] == "\n":
                    print key, temp

https://dbjergaard.github.io/posts/matasano_set_1.html Recommends chi-squared. Cool concept but super slow in Python. Would not recommend it.
Pearson's chi-squared test
Chi-square distribution introduction | Probability and Statistics | Khan Academy
Pearson's chi square test (goodness of fit) | Probability and Statistics | Khan Academy

chi-squared approach

import math
import string

from collections import Counter
from itertools import cycle


# Source http://jsbin.com/kaxoxajige/1/edit?js,output
expected = [0.08167,0.01492,0.02782,0.04253,0.12702,0.02228,0.02015,0.06094,0.06966,0.00153,0.00772,
0.04025,0.02406,0.06749,0.07507,0.01929,0.00095,0.05987,0.06327,0.09056,0.02758,0.00978,
0.02360,0.00150,0.01974,0.00074]


# Source -h https://hflog.wordpress.com/2014/04/01/how-to-perform-a-chi-squared-goodness-of-fit-test-in-python

def gf(x):
    #Play with these values to adjust the error of the approximation.
    upper_bound=100.0
    resolution=1000000.0    
    step=upper_bound/resolution
    val=0
    rolling_sum=0
    while val<=upper_bound:
        rolling_sum+=step*(val**(x-1)*2.7182818284590452353602874713526624977**(-val))
        val+=step
    return rolling_sum


def ilgf(s,z):
    val=0
    for k in range(0,100):
        val+=(((-1)**k)*z**(s+k))/(math.factorial(k)*(s+k))
    return val


def chisquarecdf(x,k):
    return 1-ilgf(k/2,x/2)/gf(k/2)


def chisquare(observed_values,expected_values):
    test_statistic=0
    for observed, expected in zip(observed_values, expected_values):
        test_statistic+=(float(observed)-float(expected))**2/float(expected)
    df=len(observed_values)-1
    return test_statistic, chisquarecdf(test_statistic,df)


def frequency(message):
    message = message.lower().strip(" ")
    freq = []
    length = len(message)
    for char in "abcdefghijklmnopqrstuvwxyz":
        freq.append(float(message.count(char)) / length)
    return freq


def xor_mb(message, key):
        return''.join(chr(ord(m_byte)^ord(k_byte)) for m_byte,k_byte in zip(message, cycle(key)))


printset = set(string.printable)
messages = open("4.txt", 'r').readlines()


for line in messages:
    message = line.rstrip().decode('hex')
    for key in range(0 ,256):
        temp = xor_mb(message, chr(key))
        temp_freq = frequency(temp)
        chi, tt = chisquare(temp_freq, expected)
        print chi, tt, temp

Classic approach - https://inventwithpython.com/hacking/chapter20.html

Challenge 5 - Implement repeating-key XOR

 def xor_mb(message, key):
        return''.join(chr(ord(m_byte)^ord(k_byte)) for m_byte,k_byte in zip(message, cycle(key)))

plain = """Burning 'em, if you ain't quick and nimble
I go crazy when I hear a cymbal"""
xor_mb(plain, "ICE").encode('hex')

Challenge 6 - Break repeating-key XOR

First part uses Hamming distance to calcualte the XOR key size.
I think this is pretty slick. The code below can be used to crack locky encoded executables.

import base64
import string
import sys
import collections

from cStringIO import StringIO
from collections import Counter
from itertools import cycle 
from itertools import product


def xor_mb(message, key):
    return''.join(chr(ord(m_byte)^ord(k_byte)) for m_byte,k_byte in zip(message, cycle(key)))


def hamming_distance(bytes_a, bytes_b):
    return sum(bin(i ^ j).count("1") for i, j in zip(bytearray(bytes_a), bytearray(bytes_b)))


def key_len(message, key_size):
    """"returns [(dist, key_size),(dist, key_size)]"""
    avg = []
    for k in xrange(2,key_size): 
        hd = []
        for n in xrange(len(message)/k-1):
            hd.append(hamming_distance(message[k*n:k*(n+1)],message[k*(n+1):k*(n*2)])/k)
        if hd:
            avg.append((sum(hd) / float(len(hd)), k))
    return sorted(avg)[:10]

data = open("6.txt",'rb').read()
d_data = base64.b64decode(data)
print key_len(d_data, 64)

Challenge 7 - AES in ECB mode

import base64
from Crypto.Cipher import AES

key = "YELLOW SUBMARINE"
IV = 24 * "\x00"
mode = AES.MODE_ECB
message =  base64.b64decode(open("7.txt", "rb").read())
encryptor = AES.new(key, mode, IV=IV)
plain = encryptor.decrypt(message)
print plain

Challenge 8 - Detect AES in ECB mode

from collections import Counter

KEY_SIZE = 16
data = open("8.txt", "r").readlines()
for line in data:
    data = line.rstrip().decode('hex')
    substr_counter = Counter(data[i: i+ KEY_SIZE] for i in range(len(data) - KEY_SIZE))
    sub_count = substr_counter.most_common(5)
    for temp in sub_count:
        key, count = temp
        if count > 3:
            print key, data

Challenge 9 - Implement PKCS#7 padding

BLOCK_SIZE = 20 # not correct standard size

def pad_pkcs_7(plain_text):
    rem = BLOCK_SIZE % len(plain_text)
    pad = (('%02x' % rem)* rem).decode('hex')
    return plain_text + pad

print pad_pkcs_7("YELLOW SUBMARINE")

Snippets

Alexander Hanel CryptoPals

Set 1

Challenge 1 - Convert hex to base64

Challenge 2 - Fixed XOR

Challenge 3 - Single-byte XOR cipher

Challenge 4 - Detect single-character XOR

Challenge 5 - Implement repeating-key XOR

Challenge 6 - Break repeating-key XOR

Challenge 7 - AES in ECB mode

Challenge 8 - Detect AES in ECB mode

Challenge 9 - Implement PKCS#7 padding

Challenge 10 - Implement CBC mode

Comments (2)