cryptopals_set1_set2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Generic"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 904,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "import base64\n",
    "import binascii\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "def to_bytes(d, format):\n",
    "    if isinstance(d, (bytes, bytearray)):\n",
    "        return d\n",
    "    elif format == 'hex':\n",
    "        return bytearray.fromhex(d)\n",
    "    elif format == 'base64':\n",
    "        return base64.b64decode(d)\n",
    "    elif format == 'str' or format == 'bytes':\n",
    "        return d.encode()\n",
    "\n",
    "def bytes_to(b, format):\n",
    "    if not isinstance(b, (bytes, bytearray)):\n",
    "        return b\n",
    "    elif format == 'hex':\n",
    "        return binascii.hexlify(b).decode()\n",
    "    elif format == 'base64':\n",
    "        return base64.b64encode(b).decode()\n",
    "    elif format == 'str':\n",
    "        return b.decode()\n",
    "    elif format == 'bytes':\n",
    "        return b\n",
    "    \n",
    "def draw_bytestring(bs):\n",
    "    \"\"\"Represent a byte string as a matrix of color\n",
    "    \"\"\"\n",
    "    tmp = bs + bytes(math.ceil(math.sqrt(len(bs)))**2 - len(bs))\n",
    "    tmp = [int(b) for b in tmp]\n",
    "    m = [[tmp[i:i+int(math.sqrt(len(tmp)))] for i in range(0, len(tmp), int(math.sqrt(len(tmp))))]]\n",
    "    matrix = np.matrix(m[0])\n",
    "    fig = plt.figure()\n",
    "    ax = fig.add_subplot(1,1,1)\n",
    "    ax.set_aspect('equal')\n",
    "    plt.imshow(matrix, interpolation='nearest', cmap=plt.cm.binary)\n",
    "    plt.colorbar()\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Helpers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 864,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "import string\n",
    "\n",
    "def count_letter_freq(text):\n",
    "    \"\"\"Count the frequence of each letter in a string\n",
    "    Return a dict\n",
    "    \"\"\"\n",
    "    letters = {}\n",
    "    total = 0\n",
    "    for l in text:\n",
    "        letters[l.lower()] = letters.get(l.lower(), 0) + 1\n",
    "        total += 1\n",
    "    return {l:s/total for l,s in letters.items()}\n",
    "\n",
    "def hamming_distance(b1, b2):\n",
    "    distance = 0\n",
    "    for char1, char2 in zip(b1,b2):\n",
    "        distance += bin(char1 ^ char2).count('1')\n",
    "    return distance\n",
    "assert hamming_distance(b'this is a test', b'wokka wokka!!!') == 37\n",
    "\n",
    "def count_upper_lower_signs(text):\n",
    "    \"\"\"Count the amount of uppercase letters, lowercase letters and other signs\n",
    "    \"\"\"\n",
    "    counter = {'upper': 0, 'lower': 0, 'signs': 0}\n",
    "    for c in text:\n",
    "        if c in string.ascii_lowercase:\n",
    "            counter['lower'] += 1\n",
    "        elif c in string.ascii_uppercase:\n",
    "            counter['upper'] += 1\n",
    "        else:\n",
    "            counter['signs'] += 1\n",
    "    return counter\n",
    "\n",
    "NON_PRINTABLE_REGEX = \"[^\\w \" + string.printable + \"\\n]\"\n",
    "def is_encodable(bs):\n",
    "    try:\n",
    "        return bs.decode()\n",
    "    except UnicodeDecodeError:\n",
    "        return False\n",
    "def is_text(s):\n",
    "    s_test = re.sub(NON_PRINTABLE_REGEX, \"\", s.strip())\n",
    "    return s_test == s.strip()\n",
    "def is_english(text):\n",
    "    \"\"\"Simple scoring function that counts probabilities of caracters and tries\n",
    "    to match them with the probabilities of the english language\"\"\"\n",
    "    if isinstance(text, (bytes, bytearray)):\n",
    "        s = is_encodable(text)\n",
    "    else:\n",
    "        s = text\n",
    "    if not s:\n",
    "        return 0\n",
    "    freqs = ['etaoin shrdlcumwfgypbvkjxqz', [12.702,9.056,8.167,7.507,6.966,6.749,6.4,6.327,6.094,5.987,4.253,4.025,2.782,2.758,2.406,2.360,2.228,2.015,1.974,1.929,1.492,0.978,0.772,0.153,0.150,0.095,0.074]]\n",
    "    nominal_scores = {l:s for l,s in zip(freqs[0], freqs[1])}\n",
    "    text_freqs = count_letter_freq(s)\n",
    "    score = 0\n",
    "    for letter, freq in text_freqs.items():\n",
    "        if letter.lower() in nominal_scores:\n",
    "            score += nominal_scores[letter.lower()]\n",
    "        else:\n",
    "            score -= 1\n",
    "    return max(score / len(text), 0)\n",
    "\n",
    "\n",
    "def pad(text, blocksize=16):\n",
    "    padsize = blocksize - (len(text) % blocksize)\n",
    "    if padsize == 0:\n",
    "        padsize = blocksize\n",
    "    return text + bytes([padsize]*padsize)\n",
    "assert pad(b\"YELLOW SUBMARINE\", blocksize=20) == b'YELLOW SUBMARINE\\x04\\x04\\x04\\x04'\n",
    "\n",
    "def unpad(text):\n",
    "    \"\"\"Validate padding and return unpadded value\"\"\"\n",
    "    assert text[-text[-1]:] == bytes([text[-1]]*text[-1])\n",
    "    return text[:-text[-1]]\n",
    "assert unpad(pad(b\"this is random text\", blocksize=7)) == b\"this is random text\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Crypto 101"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 630,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "import itertools\n",
    "\n",
    "def xor(d1, d2, format):\n",
    "    b1,b2 = to_bytes(d1, format), to_bytes(d2, format)\n",
    "    return bytes_to(bytes(char1 ^ char2 for char1,char2 in zip(b1,b2)), format)\n",
    "\n",
    "def repeating_xor(s, key, format):\n",
    "    bs = to_bytes(s, format)\n",
    "    bkey = bytearray(itertools.islice(itertools.cycle(to_bytes(key, format)), len(bs)))\n",
    "    return xor(bs, bkey, format)\n",
    "\n",
    "def guess_repeating_xor_keysize(text, count=3, minsize=2, maxsize=40):\n",
    "    \"\"\"Try to guess the size of a repeating XOR key from a given ciphertext.\n",
    "    Return top <count> guesses.\n",
    "    \"\"\"\n",
    "    values = {}\n",
    "    for keysize in range(minsize, maxsize+1):\n",
    "        # We use 4 times the keysize in order to get a better reading\n",
    "        values[keysize] = hamming_distance(text[:keysize*4], text[keysize*4:2*keysize*4]) / (keysize*4)\n",
    "    values = [(keysize, value) for keysize, value in values.items()]\n",
    "    values.sort(key=lambda x:x[1]) # The best guess is the lowest hamming distance\n",
    "    return [keysize for keysize,_ in values[:count]]\n",
    "    \n",
    "\n",
    "def crack_single_char_xor(text):\n",
    "    \"\"\"Try to crack a cipher as a single character XOR of english text\n",
    "    \"\"\"\n",
    "    bestguess = {'key': 0, 'confidence': -len(text), 'cleartext': ''}\n",
    "    for i in range(32, 127):\n",
    "        try:\n",
    "            score = is_english(xor(text, bytes([i]*len(text)), 'bytes'))\n",
    "            if score > bestguess['confidence']:\n",
    "                bestguess['key'] = bytes([i])\n",
    "                bestguess['confidence'] = score\n",
    "                bestguess['cleartext'] = xor(text, bytes([i]*len(text)), 'str')\n",
    "        except UnicodeDecodeError:\n",
    "            pass\n",
    "    return bestguess\n",
    "\n",
    "def crack_repeating_xor(text, keysize):\n",
    "    \"\"\"Try to crack a cipher as a repeating key XOR, with a given keysize\n",
    "    \"\"\"\n",
    "    # Split into blocks of size keysize\n",
    "    blocks = [text[i:i+keysize] for i in range(0, len(text), keysize)]\n",
    "    \n",
    "    # Now, refactor blocks to be all encrypted with the same caracter\n",
    "    # (every n-th caracter of a block is encrypted with the same n-th caracter of the key)\n",
    "    transposed_blocks = [bytes(block[n] for block in blocks if len(block) > n) for n in range(keysize)]\n",
    "    \n",
    "    # Solve every transposed block for single-caracter xor\n",
    "    cleartext_transposed_blocks = [crack_single_char_xor(block) for block in transposed_blocks]\n",
    "    \n",
    "    # Rebuild and return cleartext\n",
    "    #key = bytes(block['key'][0] for block in cleartext_transposed_blocks)\n",
    "    key = b''.join(block['key'] for block in cleartext_transposed_blocks)\n",
    "    cleartext = repeating_xor(text, key, 'str')\n",
    "    confidence = sum(block['confidence'] for block in cleartext_transposed_blocks) / len(cleartext_transposed_blocks)\n",
    "    \n",
    "    return {'key': key, 'cleartext':cleartext, 'confidence':confidence}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Crypto 102"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 933,
   "metadata": {},
   "outputs": [],
   "source": [
    "from Crypto.Cipher import AES\n",
    "\n",
    "def decrypt_aes_ecb(cipher, key, IV=None, use_padding=True):\n",
    "    \"\"\"No magic here\n",
    "    (The IV is not actually used)\"\"\"\n",
    "    aes = AES.new(key, AES.MODE_ECB)\n",
    "    if use_padding:\n",
    "        return unpad(aes.decrypt(cipher))\n",
    "    else:\n",
    "        return aes.decrypt(cipher)\n",
    "def encrypt_aes_ecb(clear, key, IV=None, use_padding=True):\n",
    "    \"\"\"No magic here\n",
    "    (The IV is not actually used)\"\"\"\n",
    "    aes = AES.new(key, AES.MODE_ECB)\n",
    "    if use_padding:\n",
    "        clear = pad(clear)\n",
    "    return aes.encrypt(clear)\n",
    "assert decrypt_aes_ecb(encrypt_aes_ecb(b'test', 'YELLOW SUBMARINE'), 'YELLOW SUBMARINE') == b'test'\n",
    "\n",
    "def encrypt_aes_cbc(clear, key, IV=None):\n",
    "    \"\"\"CBC using the ECB mode of above\n",
    "    \"\"\"\n",
    "    if IV is None:\n",
    "        IV=b'\\x00'*16\n",
    "    clear = pad(clear)\n",
    "    prev_block = IV\n",
    "    cipher = b''\n",
    "    for blockstart in range(0, len(clear), 16):\n",
    "        block = clear[blockstart:blockstart+16]\n",
    "        cipher_block = encrypt_aes_ecb(xor(prev_block, block, 'bytes'), key, use_padding=False)\n",
    "        prev_block = cipher_block\n",
    "        cipher += cipher_block\n",
    "    return cipher\n",
    "def decrypt_aes_cbc(cipher, key, IV=None):\n",
    "    \"\"\"CBC using the ECB mode of above\n",
    "    \"\"\"\n",
    "    if IV is None:\n",
    "        IV=b'\\x00'*16\n",
    "    clear = b''\n",
    "    prev_block = IV\n",
    "    for blockstart in range(0, len(cipher), 16):\n",
    "        block = cipher[blockstart:blockstart+16]\n",
    "        tmp = decrypt_aes_ecb(block, key, use_padding=False)\n",
    "        clear_block = xor(prev_block, tmp, 'bytes')\n",
    "        prev_block = cipher[blockstart:blockstart+16]\n",
    "        clear += clear_block\n",
    "    return unpad(clear)\n",
    "assert decrypt_aes_cbc(encrypt_aes_cbc(b'test'*200, b'YELLOW SUBMARINE'), b'YELLOW SUBMARINE') == b'test'*200\n",
    "        \n",
    "        \n",
    "\n",
    "def detect_ecb(cipher, blocksize=16):\n",
    "    \"\"\"Return a score estimating if a given cipher has been enrypted using ECB mode.\n",
    "    This score is simply a score of redundancy of n-byte blocks\"\"\"\n",
    "    score = 0\n",
    "    for blockstart in range(0, len(cipher), blocksize):\n",
    "        # The redundancy count has to be block aligned, because a\n",
    "        # given cleartext block will only give the same cipher if it\n",
    "        # is aligned.\n",
    "        score += cipher.count(cipher[blockstart:blockstart+blocksize])\n",
    "    return score / len(cipher) * blocksize # Normalize with the number of blocks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Cryptopals notebook\n",
    "\n",
    "## Stage 1\n",
    "\n",
    "### Exercice 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 632,
   "metadata": {},
   "outputs": [],
   "source": [
    "def hex_to_base64(h):\n",
    "    return bytes_to(to_bytes(h, 'hex'), 'base64')\n",
    "\n",
    "s = '49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d'\n",
    "assert hex_to_base64(s) == 'SSdtIGtpbGxpbmcgeW91ciBicmFpbiBsaWtlIGEgcG9pc29ub3VzIG11c2hyb29t'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 633,
   "metadata": {},
   "outputs": [],
   "source": [
    "s1 = '1c0111001f010100061a024b53535009181c'\n",
    "s2 = '686974207468652062756c6c277320657965'\n",
    "r = '746865206b696420646f6e277420706c6179'\n",
    "\n",
    "assert xor(s1, s2, 'hex') == r"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 634,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'confidence': 2.3081764705882355, 'cleartext': \"Cooking MC's like a pound of bacon\", 'key': b'X'}\n"
     ]
    }
   ],
   "source": [
    "s = to_bytes('1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736', 'hex')\n",
    "print(crack_single_char_xor(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 635,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "lKu*\u001bge_H\u0014\n",
      "nXdLm on line 35 with key b'P'\n",
      "New best guess : Now that the party is jumping\n",
      " on line 170 with key b'5'\n"
     ]
    }
   ],
   "source": [
    "buest_guess = {'confidence': 0}\n",
    "with open('set1_4.txt') as f:\n",
    "    for idx, line in enumerate(f):\n",
    "        bline = to_bytes(line.strip(), 'hex')\n",
    "        guess = crack_single_char_xor(bline)\n",
    "        if guess['confidence'] > buest_guess['confidence']:\n",
    "            buest_guess = guess\n",
    "            print('New best guess : %s on line %s with key %s' % (buest_guess['cleartext'], idx, buest_guess['key']))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 636,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = to_bytes(\"Burning 'em, if you ain't quick and nimble\\nI go crazy when I hear a cymbal\", 'str')\n",
    "k = to_bytes('ICE', 'str')\n",
    "r = '0b3637272a2b2e63622c2e69692a23693a2a3c6324202d623d63343c2a26226324272765272a282b2f20430a652e2c652a3124333a653e2b2027630c692b20283165286326302e27282f'\n",
    "\n",
    "assert repeating_xor(s, k, 'hex') == r"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Exercice 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 637,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Top key sizes are :  [29, 5, 12]\n",
      "{'confidence': 0.9711152490421459, 'cleartext': \"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\", 'key': b'Terminator X: Bring the noise'}\n"
     ]
    }
   ],
   "source": [
    "%matplotlib inline\n",
    "\n",
    "with open('set1_6.txt') as f:\n",
    "    s = to_bytes(f.read().replace('\\n', '').strip(), 'base64')\n",
    "    \n",
    "values = guess_repeating_xor_keysize(s, count=10)\n",
    "print('Top key sizes are : ', values[:3])\n",
    "\n",
    "# Solve for the the 3 most probable keysizes\n",
    "for keysize in values[:1]:\n",
    "    print(crack_repeating_xor(s, keysize))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 638,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "b\"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\""
      ]
     },
     "execution_count": 638,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "with open('set1_7.txt') as f:\n",
    "    s = to_bytes(f.read().replace('\\n', '').strip(), 'base64')\n",
    "    \n",
    "decrypt_aes_ecb(s, 'YELLOW SUBMARINE')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 639,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "New best guess : {'line': 0, 'max': 1.0}\n",
      "New best guess : {'line': 131, 'max': 2.2}\n"
     ]
    }
   ],
   "source": [
    "%matplotlib inline\n",
    "\n",
    "s = []\n",
    "with open('set1_8.txt') as f:\n",
    "    for line in f:\n",
    "        s.append(to_bytes(line.strip(), 'hex'))\n",
    "\n",
    "guess = {'max': detect_ecb(s), 'line': 0}\n",
    "for idx, l in enumerate(s[1:]):\n",
    "    score = detect_ecb(l)\n",
    "    if score > guess['max']:\n",
    "        guess['max'] = score\n",
    "        guess['line'] = idx\n",
    "        print('New best guess :', guess)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stage 2\n",
    "\n",
    "### Exercice 9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 640,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert pad(b'YELLOW SUBMARINE', blocksize=20) == b'YELLOW SUBMARINE\\x04\\x04\\x04\\x04'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 641,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "b\"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\"\n"
     ]
    }
   ],
   "source": [
    "with open('set2_2.txt') as f:\n",
    "    s = to_bytes(f.read().replace('\\n', '').strip(), 'base64')\n",
    "    \n",
    "print(decrypt_aes_cbc(s, 'YELLOW SUBMARINE'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 11"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 642,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Got it correct 1000/1000 (100.0 %)\n"
     ]
    }
   ],
   "source": [
    "import os\n",
    "import random\n",
    "\n",
    "# Encrypt using a random key and a random encryption mode\n",
    "def encrypt_oracle(clear):\n",
    "    key = os.urandom(16)\n",
    "    prefix = os.urandom(random.randint(5,10))\n",
    "    suffix = os.urandom(random.randint(5,10))\n",
    "    name = ''\n",
    "    if random.random() < 0.5:\n",
    "        name = 'AES_CBC'\n",
    "        cipher = encrypt_aes_cbc\n",
    "    else:\n",
    "        name = 'AES_ECB'\n",
    "        cipher = encrypt_aes_ecb\n",
    "    return cipher(prefix + clear + suffix, key, IV=os.urandom(16)), name\n",
    "\n",
    "def detect_ecb_cbc(encrypt_oracle):\n",
    "    \"\"\"Detect if the given encryption_oracle is using CBC or ECB\n",
    "    \"\"\"\n",
    "    text = b'\\x00' * 160\n",
    "    cipher, name = encrypt_oracle(text)\n",
    "    if detect_ecb(cipher) > 1:\n",
    "        return name == 'AES_ECB'\n",
    "    else:\n",
    "        return name == 'AES_CBC'\n",
    "    \n",
    "score = 0\n",
    "n = 1000\n",
    "for i in range(n):\n",
    "    guess = detect_ecb_cbc(encrypt_oracle)\n",
    "    if guess:\n",
    "        score += 1\n",
    "print('Got it correct %s/%s (%s %%)' % (score, n, score/n*100))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 12"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 764,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Rollin' in my 5.0\n",
      "With my rag-top down so my hair can blow\n",
      "The girlies on standby waving just to say hi\n",
      "Did you stop? No, I just drove by\n"
     ]
    }
   ],
   "source": [
    "def encrypt_fixed_oracle(clear):\n",
    "    key = b'\\x82\\xd5\\xb7)\\x15r\\xd8\\xe1f\\xe7\\xf9\\xf1A8=#'\n",
    "    prefix = b''\n",
    "    suffix = to_bytes('Um9sbGluJyBpbiBteSA1LjAKV2l0aCBteSByYWctdG9wIGRvd24gc28gbXkgaGFpciBjYW4gYmxvdwpUaGUgZ2lybGllcyBvbiBzdGFuZGJ5IHdhdmluZyBqdXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUgYnkK', 'base64')\n",
    "    return encrypt_aes_ecb(prefix + clear + suffix, key)\n",
    "\n",
    "# The objective is now to crack the encrypted suffix, without using the key ofc.\n",
    "\n",
    "# Detect if it is ECB\n",
    "assert detect_ecb(encrypt_fixed_oracle(b'A'*100)) > 1\n",
    "\n",
    "# Detect blocksize\n",
    "def detect_blocksize():\n",
    "    for blocksize in range(1, 33):\n",
    "        for filler in range(blocksize):\n",
    "            # Use oracle to encrypt <blocksize>*A*2 + <filler>*A\n",
    "            # When the blocksize is correct and the padding actually completes\n",
    "            # the final block of the oracle prefix, then we have 2 identical\n",
    "            # blocks at the end\n",
    "            cipher = encrypt_fixed_oracle(b'A'*blocksize*2 + b'A'*filler)\n",
    "            if cipher[:blocksize] == cipher[blocksize:blocksize*2]:\n",
    "                print('Blocksize : %s (pad : %s)' % (blocksize, filler))\n",
    "                return blocksize\n",
    "\n",
    "# It turns out, the blocksize is 16 and the oracle appends\n",
    "# a block-aligned string to the input before encryption.\n",
    "\n",
    "# Serve a known block that is one byte short to the oracle.\n",
    "# The last byte in the block will be the first byte of the cleartext\n",
    "# that is to be attacked.\n",
    "# Then, encrypt a known block to brute-force the last byte with\n",
    "# known prefix. This uncovers the first byte of cleartext. Shift\n",
    "# and repeat after that.\n",
    "\n",
    "# Detail : \n",
    "# Encrypt A*15 to get a cipher block\n",
    "# Bruteforce A*15+i then compare with above block to recover first byte.\n",
    "# Encrypt A*14 to get a cipher block\n",
    "# Bruteforce A*14+first_recovered_cipher_byte+i then compare and get second byte\n",
    "# ...\n",
    "\n",
    "cleartext = b''\n",
    "reference_blocks = {}\n",
    "\n",
    "def bruteforce_last_block_byte(oracle, reference, prefix, blocksize=16):\n",
    "    \"\"\"Bruteforce the last byte of a given block.\n",
    "    \"\"\"\n",
    "    assert len(reference) == blocksize\n",
    "    assert len(prefix) == blocksize - 1\n",
    "    for j in range(256):\n",
    "        a = prefix + bytes([j])\n",
    "        b = oracle(bytes(a))[:blocksize]\n",
    "        if b == reference:\n",
    "            if j == 1:\n",
    "                continue\n",
    "            return bytes([j])\n",
    "    print(reference)\n",
    "    print(prefix)\n",
    "    raise ValueError('Bruteforce failed :(')\n",
    "        \n",
    "\n",
    "cleartext = b''\n",
    "cipher = encrypt_fixed_oracle(b'')\n",
    "for i in range(138): # the cipher is actually only 138 bytes long. If we solve for 144, the padding messes up the bruteforce\n",
    "    padding = b'A'*(len(cipher)-1-len(cleartext))\n",
    "    prefix = padding + cleartext\n",
    "    reference = encrypt_fixed_oracle(padding)[len(padding)-15+i:len(padding)+1+i]\n",
    "    cleartext += bruteforce_last_block_byte(encrypt_fixed_oracle, reference, prefix=prefix[-15:])\n",
    "    print(chr(cleartext[-1]), end='')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 13\n",
    "\n",
    "There is a first a little setup that will emulate a very basic web app cookie generation process"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 813,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def k_v_parsing(s):\n",
    "    values = [s2.split('=') for s2 in s.split('&')]\n",
    "    return {key:value for key,value in values}\n",
    "assert k_v_parsing('foo=bar&baz=qux&zap=zazzle') == {'foo': 'bar', 'baz':'qux', 'zap':'zazzle'}\n",
    "\n",
    "def k_v_encoding(d):\n",
    "    # Add a small sort to the items to ensure consistency\n",
    "    return 'email={email}&uid={uid}&role={role}'.format(**d)\n",
    "\n",
    "def profile_for(email, uid=10):\n",
    "    cleanmail = email.replace('&', '').replace('=', '')  # remove encoding caracters\n",
    "    return k_v_encoding({'email': cleanmail, 'uid':str(uid), 'role': 'user'})\n",
    "assert profile_for('foo@bar.com') == 'email=foo@bar.com&uid=10&role=user'\n",
    "\n",
    "# The super duper app secret\n",
    "secret = b'\\xdeaQ\\xc4\\xc4\\x85\\x8b\\xf1\\xcb\\x01dAx\\xf2\\xea\\x86'\n",
    "\n",
    "def cookie(profile):\n",
    "    \"\"\"Generate an AES encrypted cookie from the encoded profile\n",
    "    \"\"\"\n",
    "    return encrypt_aes_ecb(to_bytes(profile, 'str'), key=secret)\n",
    "\n",
    "def read_cookie(cipher):\n",
    "    \"\"\"Extract profile from cookie\n",
    "    \"\"\"\n",
    "    return k_v_parsing(bytes_to(decrypt_aes_ecb(cipher, key=secret), 'str'))\n",
    "\n",
    "assert read_cookie(cookie('email=foo@bar.com&uid=10&role=user')) == k_v_parsing(profile_for('foo@bar.com', uid=10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 814,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'email': 'AAAAAAA@a.com', 'uid': '10', 'role': 'admin'}\n"
     ]
    }
   ],
   "source": [
    "# ECB Cut & Paste\n",
    "\n",
    "# For that, we use an email that allows the block to end on '&role='\n",
    "# then cut the last block of the resulting cookie and replace ic\n",
    "# with another block. The block will be the second block of the\n",
    "# cookie generated from the email '{A*10}admin{\\x0B*11}@bar.com'\n",
    "# This email generates a padded block with only 'admin' in it.\n",
    "block1 = cookie(profile_for('A'*10 + 'admin' + '\\x0B'*11 + '@bar.com'))[16:32] # second block is the winner\n",
    "block2 = cookie(profile_for('A'*7 + '@a.com'))[:-16] # shave off last block from this one\n",
    "print(read_cookie(block2 + block1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 14\n",
    "\n",
    "v2 of the fixed oracle ECB attack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 861,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The prefix is of length 42\n",
      "Shaving 48 bytes of the start and filling with 6 bytes\n",
      "Rollin' in my 5.0\n",
      "With my rag-top down so my hair can blow\n",
      "The girlies on standby waving just to say hi\n",
      "Did you stop? No, I just drove by\n"
     ]
    }
   ],
   "source": [
    "import os\n",
    "\n",
    "def encrypt_fixed_oracle(clear):\n",
    "    key = b'\\x82\\xd5\\xb7)\\x15r\\xd8\\xe1f\\xe7\\xf9\\xf1A8=#'\n",
    "    prefix = b\"\\xa8\\xa4?\\xe3&\\x0c\\xa5\\xb7\\x1a\\x8f\\xae\\xe7\\xd9.e\\xef\\x95\\xeb8>\\xfa\\xba\\x14_\\xb4\\xad-X.Z\\xb0\\xef\\xc3\\x8d\\xf3\\xa3\\xd8\\x88'\\xc4\\xe2\\t\"\n",
    "    suffix = to_bytes('Um9sbGluJyBpbiBteSA1LjAKV2l0aCBteSByYWctdG9wIGRvd24gc28gbXkgaGFpciBjYW4gYmxvdwpUaGUgZ2lybGllcyBvbiBzdGFuZGJ5IHdhdmluZyBqdXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUgYnkK', 'base64')\n",
    "    return encrypt_aes_ecb(prefix + clear + suffix, key)\n",
    "\n",
    "\n",
    "# This is basically a twist on the Exercice 12 oracle.\n",
    "# We just have to find out how long the prefix is. Then,\n",
    "# we can complete to nearest block and just cut out the\n",
    "# first few blocks. After that, see exercice 12 for solution.\n",
    "\n",
    "# 1/ count the bytes that are in common in these two\n",
    "#    > gives us the prefix to a precision of 1 block\n",
    "def find_prefix_length():\n",
    "    pok1 = encrypt_fixed_oracle(b'A'*32)\n",
    "    pok = []\n",
    "    last_j = None\n",
    "    for i in range(16):\n",
    "        pok.append(encrypt_fixed_oracle(b'A'*i))\n",
    "        for j in range(len(pok[-1])):\n",
    "            if pok1[j] != pok[-1][j]:\n",
    "                if last_j is not None and j != last_j:\n",
    "                    # The length of identical bytes has changed. The blocked switched.\n",
    "                    # This means that the previous identical length is part of the\n",
    "                    # fixed prefix, and that the A padding just attained the block\n",
    "                    # limit. This gives us the complete length of the prefix.\n",
    "                    return last_j + (16-i)\n",
    "                else:\n",
    "                    last_j = j\n",
    "                    break\n",
    "                    \n",
    "print('The prefix is of length %s' % find_prefix_length())\n",
    "\n",
    "def wrapped_encrypt_fixed_oracle_factory(oracle, prefix_length, blocksize=16):\n",
    "    filler = b'A'*(blocksize-(prefix_length%blocksize))\n",
    "    shave_bytes = prefix_length + len(filler)\n",
    "    print('Shaving %s bytes of the start and filling with %s bytes' % (shave_bytes, len(filler)))\n",
    "    def new_oracle(clear):\n",
    "         return oracle(filler+clear)[shave_bytes:]\n",
    "    return new_oracle\n",
    "\n",
    "new_oracle = wrapped_encrypt_fixed_oracle_factory(encrypt_fixed_oracle, find_prefix_length())\n",
    "\n",
    "# Now that we have a new oracle that actually behaves like the first one !\n",
    "# Yay \\o/ !\n",
    "# See Exercice 12 for the rest\n",
    "\n",
    "cleartext = b''\n",
    "cipher = new_oracle(b'')\n",
    "for i in range(138): # the cipher is actually only 138 bytes long. If we solve for 144, the padding messes up the bruteforce\n",
    "    padding = b'A'*(len(cipher)-1-len(cleartext))\n",
    "    prefix = padding + cleartext\n",
    "    reference = new_oracle(padding)[len(padding)-15+i:len(padding)+1+i]\n",
    "    cleartext += bruteforce_last_block_byte(new_oracle, reference, prefix=prefix[-15:])\n",
    "    print(chr(cleartext[-1]), end='')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 15"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 869,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert unpad(b\"ICE ICE BABY\\x04\\x04\\x04\\x04\") == b\"ICE ICE BABY\"\n",
    "try:\n",
    "    unpad(b\"ICE ICE BABY\\x05\\x05\\x05\\x05\")\n",
    "    assert False\n",
    "except AssertionError:\n",
    "    assert True\n",
    "try:\n",
    "    unpad(b\"ICE ICE BABY\\x01\\x02\\x03\\x04\")\n",
    "    assert False\n",
    "except AssertionError:\n",
    "    assert True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 16\n",
    "\n",
    "First, define a few functions that emulate how a (web)app would handle userdata."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 908,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "b'comment1=cooking%20MCs;userdata=test;comment2=%20like%20a%20pound%20of%20bacon\\x02\\x02'\n"
     ]
    }
   ],
   "source": [
    "def build_userdata(data):\n",
    "    key = b',\\xe8~mv\\xca\\xce\\x1c \\xd4\\x83\\x9a\\x12\\xd2\\xd7\"'\n",
    "    d =  pad(b'comment1=cooking%20MCs;userdata=' + data.replace(b'=', b'').replace(b';', b'') + \\\n",
    "            b';comment2=%20like%20a%20pound%20of%20bacon')\n",
    "    return encrypt_aes_cbc(d, key=key)\n",
    "\n",
    "def is_admin(encrypted_data):\n",
    "    key = b',\\xe8~mv\\xca\\xce\\x1c \\xd4\\x83\\x9a\\x12\\xd2\\xd7\"'\n",
    "    data = decrypt_aes_cbc(encrypted_data, key=key)\n",
    "    print(data)\n",
    "    return b';admin=true;' in data\n",
    "\n",
    "assert not is_admin(build_userdata(b'test'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 945,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "b'comment1=cooking \\xd6\\x00\\xf0\\x8e5\\x8e\\x91\\xb8\\xb1\\xacf\\r?C-;admin=true;AAAA;comment2=%20like%20a%20pound%20of%20bacon\\x06\\x06\\x06\\x06\\x06\\x06'\n"
     ]
    }
   ],
   "source": [
    "import array\n",
    "\n",
    "# Build a cipher that will have at least the length to insert A;admin=true, but also be block aligned.\n",
    "# It so happens that our prefix is block aligned and user data starts on the 3rd block\n",
    "cipher = build_userdata(b'AadminAtrueAAAAA')\n",
    "\n",
    "# Now, let's flip some bits !\n",
    "# Given the XORs used by the CBC decryption function, we can simply flip the\n",
    "# ciphertext of the previous block to influence the block we have control over.\n",
    "cipher = xor(b'\\x00'*16 + xor(b'A', b';', 'bytes') + b'\\x00'*(22-17) + xor(b'A', b'=', 'bytes') + \\\n",
    "                b'\\x00'*(27-23) + xor(b'A', b';', 'bytes') + b'\\x00'*(len(cipher)-28),\n",
    "             cipher,\n",
    "             'bytes')\n",
    "assert is_admin(cipher)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}