cryptopals_set4.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Generic\n",
    "\n",
    "This is mostly copied from the previous notebook"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "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 bytes(bytearray.fromhex(d))\n",
    "    elif format == 'base64':\n",
    "        return base64.b64decode(d)\n",
    "    elif format == 'str' or format == 'bytes':\n",
    "        return d.encode()\n",
    "    elif format == 'int':\n",
    "        return to_bytes(hex(d)[2:], 'hex')\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",
    "    elif format == 'int':\n",
    "        return int(bytes_to(b, 'hex')[2:], 16)\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\n",
    "\n",
    "This is mostly copied from the previous notebook"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "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 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\n",
    "\n",
    "Generic crypto stuff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "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",
    "\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",
    "def aes_ctr_generator(key, nonce=0):\n",
    "    \"\"\"Generate a keystream using AES-CTR.\n",
    "    \"\"\"\n",
    "    if isinstance(nonce, bytes):\n",
    "        nonce = int.from_bytes(nonce, 'big')\n",
    "    while True:\n",
    "        counter = nonce.to_bytes(9, 'big') + b'\\x00'*7\n",
    "        yield encrypt_aes_ecb(counter, key, use_padding=False)\n",
    "        nonce += 1\n",
    "        \n",
    "def encrypt_aes_ctr(key, cleartext, nonce=0):\n",
    "    \"\"\"Encrypt some text with AES-CTR.\n",
    "    \"\"\"\n",
    "    cipher = b''\n",
    "    keystream = aes_ctr_generator(key, nonce=nonce)\n",
    "    for i in range(0, len(cleartext), 16):\n",
    "        block = cleartext[i:i+16]\n",
    "        cipher += xor(block, next(keystream), 'bytes')\n",
    "    return cipher\n",
    "\n",
    "decrypt_aes_ctr = encrypt_aes_ctr # Such elegance !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Cryptopals notebook - part 3\n",
    "\n",
    "## Set 4\n",
    "\n",
    "### Exercice 25\n",
    "\n",
    "First, let's get the cleartext from the ECB exercice (exercice 7 - AES ub ECB mode)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "with open('set1_7.txt') as f:\n",
    "    s = to_bytes(f.read().replace('\\n', '').strip(), 'base64')\n",
    "    \n",
    "cleartext = decrypt_aes_ecb(s, 'YELLOW SUBMARINE')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Then we reencrypt it with CTR and a random key."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import os\n",
    "key = os.urandom(32)\n",
    "cipher = encrypt_aes_ctr(key, cleartext)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Implement the targeted change function\n",
    "import math\n",
    "def edit(ciphertext, key, offset, newtext):\n",
    "    # Re-build the generator\n",
    "    keystream = aes_ctr_generator(key)\n",
    "    \n",
    "    # Now, lets splice the cipher text with the new one\n",
    "    splice_over = False\n",
    "    new_cipher = b''\n",
    "    i = 0\n",
    "    while i < len(ciphertext):\n",
    "        block = ciphertext[i:i+16]\n",
    "        if i + 16 < offset or splice_over:\n",
    "            # Unchanged block\n",
    "            new_cipher += block\n",
    "            next(keystream)\n",
    "            i += 16\n",
    "        else:\n",
    "            # In splice territory !\n",
    "            # First, get all the blocks in cleartext that we need\n",
    "            new_offset = offset % 16\n",
    "            blockcount = math.ceil((len(newtext)+new_offset) / 16)\n",
    "            cleartext = b''\n",
    "            keyblocks = []\n",
    "            for bc in range(blockcount):\n",
    "                block = ciphertext[i+bc*16:i+bc*16+16]\n",
    "                keyblocks.append(next(keystream))\n",
    "                cleartext += xor(block, keyblocks[-1], 'bytes')\n",
    "            \n",
    "            # New splice the new text into the cleartext\n",
    "            new_cleartext = cleartext[:new_offset] + newtext + cleartext[new_offset+len(newtext):]\n",
    "            \n",
    "            # And reencrypt\n",
    "            new_ciphertext = b''\n",
    "            for bc in range(blockcount):\n",
    "                block = new_cleartext[bc*16:bc*16+16]\n",
    "                new_ciphertext += xor(block, keyblocks[bc], 'bytes')\n",
    "                \n",
    "            # And wrap up\n",
    "            new_cipher += new_ciphertext\n",
    "            i += blockcount*16\n",
    "            splice_over = True\n",
    "    return new_cipher"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Test the edit function\n",
    "import os\n",
    "test_key = os.urandom(32)\n",
    "test_cipher = encrypt_aes_ctr(test_key, b\"This is a test text ! Wow ! It is marvelous. Truly.\")\n",
    "test_edited = edit(test_cipher, test_key, 3, b\"INSERT ME\")\n",
    "test_clear = decrypt_aes_ctr(key=test_key, cleartext=test_edited)\n",
    "assert test_clear == b'ThiINSERT MEst text ! Wow ! It is marvelous. Truly.'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "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": [
    "# Actual deciphering\n",
    "controlled_cipher = edit(cipher, key, 0, b'\\x00'*len(cipher))\n",
    "deciphered_cleartext = xor(controlled_cipher, cipher, 'bytes')\n",
    "print(deciphered_cleartext)\n",
    "assert deciphered_cleartext == cleartext"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 26\n",
    "\n",
    "First, copy the helpers from the CBC bit-flipping exercice (set 2 - Exercice 16) but change the CBC method to CTR."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "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_ctr(key, d)\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_ctr(key, encrypted_data)\n",
    "    print(data)\n",
    "    return b';admin=true;' in data\n",
    "\n",
    "assert not is_admin(build_userdata(b'test'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The inject it trivially"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "b'comment1=cooking%20MCs;userdata=;admin=true;\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00;comment2=%20like%20a%20pound%20of%20bacon\\x04\\x04\\x04\\x04'\n"
     ]
    }
   ],
   "source": [
    "# Get a few bytes of keystream\n",
    "lenprefix = len(b'comment1=cooking%20MCs;userdata=')\n",
    "encrypted_userdata = build_userdata(b'\\x00'*50)\n",
    "keystream_data = encrypted_userdata[lenprefix:lenprefix+100]\n",
    "\n",
    "# Now inject the desired data\n",
    "injected_data = xor(b';admin=true;', keystream_data[:len(b';admin=true;')], 'bytes')\n",
    "injected_userdata = encrypted_userdata[:lenprefix] + injected_data + encrypted_userdata[lenprefix+len(injected_data):]\n",
    "assert is_admin(injected_userdata)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 27\n",
    "\n",
    "First copy the code from the CBC exercice (set 2 - Exercice 16) and adapt them to use IV=Key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def encrypt_aes_cbc_mod(clear, key):\n",
    "    \"\"\"CBC using the ECB mode of above\n",
    "    \"\"\"\n",
    "    IV=key\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",
    "\n",
    "def decrypt_aes_cbc_mod(cipher, key):\n",
    "    \"\"\"CBC using the ECB mode of above\n",
    "    \"\"\"\n",
    "    IV=key\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",
    "    try:\n",
    "        clear = unpad(clear)\n",
    "    except:\n",
    "        pass # Meh.\n",
    "    def find_high_ascii(x):\n",
    "        return x > 127\n",
    "    is_high_ascii_list = list(map(find_high_ascii, clear))\n",
    "    return clear, any(is_high_ascii_list)\n",
    "assertion_clear, assertion_high_ascii = decrypt_aes_cbc_mod(encrypt_aes_cbc_mod(b'test'*200, b'YELLOW SUBMARINE'), b'YELLOW SUBMARINE')\n",
    "assert assertion_clear == b'test'*200\n",
    "assert not assertion_high_ascii"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Oh noes, the cipher was incorrect ! A high ASCII caracter was found !\n",
      "The decrypted cipher was : b'YELLOW SUBMARINE\\xf0\\x0e\\ng\\xd9%\\xa5I6\\xcef+\\x9a\\xc9\\xa0\\xaa\\x80\\xcc\\x07\\x89\\xc1[5\\xe0\\xb9,\\x83/`\\x8bQ7'\n",
      "Extracted key : b'\\xd9\\x89K\\xc5\\x8e\\x0c\\x15\\xb3\\xecn\\xcen2\\xc2\\x1fr'\n"
     ]
    }
   ],
   "source": [
    "# Sender has this :\n",
    "key = b'\\xd9\\x89K\\xc5\\x8e\\x0c\\x15\\xb3\\xecn\\xcen2\\xc2\\x1fr'\n",
    "cleartext = b'YELLOW SUBMARINE1234567890123456YELLOW SUBMARINE'\n",
    "ciphertext = encrypt_aes_cbc_mod(cleartext, key)\n",
    "\n",
    "# Attacker intercepts message and modifies it\n",
    "new_ciphertext = ciphertext[:16] + b'\\x00'*16 + ciphertext[:16]\n",
    "\n",
    "# Receiver tries to decode new ciphertext and fails\n",
    "new_cleartext, is_high_ascii = decrypt_aes_cbc_mod(new_ciphertext, key)\n",
    "if is_high_ascii:\n",
    "    print('Oh noes, the cipher was incorrect ! A high ASCII caracter was found !')\n",
    "    print('The decrypted cipher was :', new_cleartext)\n",
    "    \n",
    "# Attacker gets the error message and tries to get the key from it\n",
    "new_key = xor(new_cleartext[:16], new_cleartext[32:], 'bytes')\n",
    "assert new_key == key\n",
    "print('Extracted key :', new_key)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Exercice 28\n",
    "\n",
    "SHA 1 implementation taken from [here](https://github.com/pcaro90/Python-SHA1/blob/master/SHA1.py), validated quickly agaisnt the value given by DDG. The modifications for the next exercice are directly contained in this implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 211,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class SHA1:\n",
    "    def __init__(self, _H=None, _len_state=None):\n",
    "        self._len_state = _len_state\n",
    "        if _H is None:\n",
    "            self.__H = [\n",
    "                0x67452301,\n",
    "                0xEFCDAB89,\n",
    "                0x98BADCFE,\n",
    "                0x10325476,\n",
    "                0xC3D2E1F0\n",
    "                ]\n",
    "        else:\n",
    "            self.__H = _H\n",
    "\n",
    "    def __str__(self):\n",
    "        return ''.join((hex(h)[2:]).rjust(8, '0') for h in self.__H)\n",
    "\n",
    "    # Private static methods used for internal operations.\n",
    "    @staticmethod\n",
    "    def __ROTL(n, x, w=32):\n",
    "        return ((x << n) | (x >> w - n))\n",
    "\n",
    "    @staticmethod\n",
    "    def __padding(stream, _len_state=None):\n",
    "        l = len(stream)  # Bytes\n",
    "        if _len_state:\n",
    "            l += _len_state\n",
    "        hl = [int((hex(l*8)[2:]).rjust(16, '0')[i:i+2], 16)\n",
    "              for i in range(0, 16, 2)]\n",
    "\n",
    "        l0 = (56 - l) % 64\n",
    "        if not l0:\n",
    "            l0 = 64\n",
    "\n",
    "        if isinstance(stream, str):\n",
    "            stream += chr(0b10000000)\n",
    "            stream += chr(0)*(l0-1)\n",
    "            for a in hl:\n",
    "                stream += chr(a)\n",
    "        elif isinstance(stream, bytes):\n",
    "            stream += bytes([0b10000000])\n",
    "            stream += bytes(l0-1)\n",
    "            stream += bytes(hl)\n",
    "\n",
    "        return stream\n",
    "\n",
    "    @staticmethod\n",
    "    def __prepare(stream):\n",
    "        M = []\n",
    "        n_blocks = len(stream) // 64\n",
    "\n",
    "        stream = bytearray(stream)\n",
    "\n",
    "        for i in range(n_blocks):  # 64 Bytes per Block\n",
    "            m = []\n",
    "\n",
    "            for j in range(16):  # 16 Words per Block\n",
    "                n = 0\n",
    "                for k in range(4):  # 4 Bytes per Word\n",
    "                    n <<= 8\n",
    "                    n += stream[i*64 + j*4 + k]\n",
    "\n",
    "                m.append(n)\n",
    "\n",
    "            M.append(m[:])\n",
    "\n",
    "        return M\n",
    "\n",
    "    @staticmethod\n",
    "    def __debug_print(t, a, b, c, d, e):\n",
    "        print('t = {0} : \\t'.format(t),\n",
    "              (hex(a)[2:]).rjust(8, '0'),\n",
    "              (hex(b)[2:]).rjust(8, '0'),\n",
    "              (hex(c)[2:]).rjust(8, '0'),\n",
    "              (hex(d)[2:]).rjust(8, '0'),\n",
    "              (hex(e)[2:]).rjust(8, '0')\n",
    "              )\n",
    "\n",
    "    # Private instance methods used for internal operations.\n",
    "    def __process_block(self, block):\n",
    "        \n",
    "        MASK = 2**32-1\n",
    "\n",
    "        W = block[:]\n",
    "        for t in range(16, 80):\n",
    "            W.append(SHA1.__ROTL(1, (W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16]))\n",
    "                     & MASK)\n",
    "\n",
    "        a, b, c, d, e = self.__H[:]\n",
    "\n",
    "        for t in range(80):\n",
    "            if t <= 19:\n",
    "                K = 0x5a827999\n",
    "                f = (b & c) ^ (~b & d)\n",
    "            elif t <= 39:\n",
    "                K = 0x6ed9eba1\n",
    "                f = b ^ c ^ d\n",
    "            elif t <= 59:\n",
    "                K = 0x8f1bbcdc\n",
    "                f = (b & c) ^ (b & d) ^ (c & d)\n",
    "            else:\n",
    "                K = 0xca62c1d6\n",
    "                f = b ^ c ^ d\n",
    "\n",
    "            T = ((SHA1.__ROTL(5, a) + f + e + K + W[t]) & MASK)\n",
    "            e = d\n",
    "            d = c\n",
    "            c = SHA1.__ROTL(30, b) & MASK\n",
    "            b = a\n",
    "            a = T\n",
    "\n",
    "            #SHA1.debug_print(t, a,b,c,d,e)\n",
    "\n",
    "        self.__H[0] = (a + self.__H[0]) & MASK\n",
    "        self.__H[1] = (b + self.__H[1]) & MASK\n",
    "        self.__H[2] = (c + self.__H[2]) & MASK\n",
    "        self.__H[3] = (d + self.__H[3]) & MASK\n",
    "        self.__H[4] = (e + self.__H[4]) & MASK\n",
    "\n",
    "    # Public methods for class use.\n",
    "    def update(self, stream):\n",
    "        stream = SHA1.__padding(stream, self._len_state)\n",
    "        stream = SHA1.__prepare(stream)\n",
    "        for block in stream:\n",
    "            self.__process_block(block)\n",
    "\n",
    "    def digest(self):\n",
    "        return to_bytes(self.hexdigest(), 'hex')\n",
    "    \n",
    "    def digest_with_state(self):\n",
    "        return self.digest(), self.__H\n",
    "\n",
    "    def hexdigest(self):\n",
    "        s = ''\n",
    "        for h in self.__H:\n",
    "            s += (hex(h)[2:]).rjust(8, '0')\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 212,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "sha1 = SHA1()\n",
    "sha1.update(b'test')\n",
    "assert sha1.hexdigest() == 'a94a8fe5ccb19ba61c4c0873d391e987982fbbd3'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 213,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def sha1mac(key, message):\n",
    "    sha1 = SHA1()\n",
    "    sha1.update(key + message)\n",
    "    return sha1.digest_with_state()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 214,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# A few trivial verifications\n",
    "message = b'Hello, world !'\n",
    "key = b'foo'\n",
    "mac = sha1mac(key, message)\n",
    "assert sha1mac(key, b'Hello, warld !') != mac\n",
    "assert sha1mac(b'bar', message) != mac"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Exercice 29\n",
    "\n",
    "The modified SHA1 algorithm is defined in the previous exercice.\n",
    "This is a completely valid SHA1 algorithm, with one twist : the internal state can be set to any value at initalisation. This includes the 5-integer array \\_\\_H and the length of the complete message.\n",
    "\n",
    "We use this and the valid MAC that was given for the inconspicuous message the make a MAC length-extension attack, in order to generate a MAC that is valid for a message containing `admin=true`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 219,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original MAC b'b\\xf8s\\\\\\x14\"\\t\\xee\\xe4\\xa5E\\x91M\\xec\\x8e\\xe3n\\x12.['\n",
      "SHA1 State [1660449628, 337775086, 3836036497, 1307348707, 1846685275]\n"
     ]
    }
   ],
   "source": [
    "# We will try to forge a MAC for the following prefix\n",
    "key = b'\\xe6\\xfa05\\xf6\\xd2\\x05\\x0fL,\\x13,'\n",
    "original_message = b\"comment1=cooking%20MCs;userdata=foo;comment2=%20like%20a%20pound%20of%20bacon\"\n",
    "original_mac, sha1_state = sha1mac(key, original_message)\n",
    "print(\"Original MAC\", original_mac)\n",
    "print(\"SHA1 State\", sha1_state)\n",
    "\n",
    "\n",
    "# In this example, we want to forge a MAC that has the same prefix as the original one.\n",
    "# The attacker know the original message and the original MAC, but has no information about the key,\n",
    "# except a vague idea about its length (let's say between 0 and 256 bytes).\n",
    "\n",
    "# Validation function\n",
    "def is_valid_mac(mac, message):\n",
    "    tmp = sha1mac(key, message)[0]\n",
    "    return tmp == mac\n",
    "assert is_valid_mac(original_mac, original_message)\n",
    "\n",
    "# The message we want to append\n",
    "new_message_suffix = b\";admin=true\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 220,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found a valid MAC b'\\r\\xea\\xcb\\xef\\xca\\x92\\xd8\\x91a:N\\xf1\\xfe4M\\xe7\\x11z\\xab\\xa8' for keylength ! 12\n"
     ]
    }
   ],
   "source": [
    "# Bruteforce over keylength to get the desired result\n",
    "for i in range(0, 255):\n",
    "\n",
    "    # Apparently the sha1_state variable gets corrupted somewhere\n",
    "    sha1_state = [1660449628, 337775086, 3836036497, 1307348707, 1846685275]\n",
    "\n",
    "    glue_padding = sha1_padding(b'A'*i + original_message)[len(original_message)+i:]\n",
    "    new_message = original_message + glue_padding + new_message_suffix\n",
    "\n",
    "    # Let's generate the MAC, then find the message that corresponds to the MAC\n",
    "    fake_sha1_generator = SHA1(_H=sha1_state, _len_state=i + len(original_message)+len(glue_padding))\n",
    "    fake_sha1_generator.update(new_message_suffix)\n",
    "    fake_mac = fake_sha1_generator.digest()\n",
    "\n",
    "    if is_valid_mac(fake_mac, new_message):\n",
    "        print(\"Found a valid MAC\", fake_mac, \"for keylength !\", i)\n",
    "        break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Exercice 30\n",
    "\n",
    "MD4 length extension attack. Same idea as previously, other algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Shamelessly copied from https://github.com/ricpacca/Cryptopals/blob/master/S4C30.py\n",
    "\n",
    "from struct import pack, unpack\n",
    "\n",
    "def left_rotate(value, shift):\n",
    "    \"\"\"Returns value left-rotated by shift bits. In other words, performs a circular shift to the left.\"\"\"\n",
    "    return ((value << shift) & 0xffffffff) | (value >> (32 - shift))\n",
    "\n",
    "class MD4:\n",
    "    \"\"\"Adapted from: https://github.com/FiloSottile/crypto.py/blob/master/3/md4.py\"\"\"\n",
    "    buf = [0x00] * 64\n",
    "\n",
    "    _F = lambda self, x, y, z: ((x & y) | (~x & z))\n",
    "    _G = lambda self, x, y, z: ((x & y) | (x & z) | (y & z))\n",
    "    _H = lambda self, x, y, z: (x ^ y ^ z)\n",
    "\n",
    "    def __init__(self, message, ml=None, A=0x67452301, B=0xefcdab89, C=0x98badcfe, D=0x10325476):\n",
    "        self.A, self.B, self.C, self.D = A, B, C, D\n",
    "\n",
    "        if ml is None:\n",
    "            ml = len(message) * 8\n",
    "\n",
    "        length = pack('<Q', ml)\n",
    "\n",
    "        while len(message) > 64:\n",
    "            self._handle(message[:64])\n",
    "            message = message[64:]\n",
    "\n",
    "        message += b'\\x80'\n",
    "        message += bytes((56 - len(message) % 64) % 64)\n",
    "        message += length\n",
    "\n",
    "        while len(message):\n",
    "            self._handle(message[:64])\n",
    "            message = message[64:]\n",
    "\n",
    "    def _handle(self, chunk):\n",
    "        X = list(unpack('<' + 'I' * 16, chunk))\n",
    "        A, B, C, D = self.A, self.B, self.C, self.D\n",
    "\n",
    "        for i in range(16):\n",
    "            k = i\n",
    "            if i % 4 == 0:\n",
    "                A = left_rotate((A + self._F(B, C, D) + X[k]) & 0xffffffff, 3)\n",
    "            elif i % 4 == 1:\n",
    "                D = left_rotate((D + self._F(A, B, C) + X[k]) & 0xffffffff, 7)\n",
    "            elif i % 4 == 2:\n",
    "                C = left_rotate((C + self._F(D, A, B) + X[k]) & 0xffffffff, 11)\n",
    "            elif i % 4 == 3:\n",
    "                B = left_rotate((B + self._F(C, D, A) + X[k]) & 0xffffffff, 19)\n",
    "\n",
    "        for i in range(16):\n",
    "            k = (i // 4) + (i % 4) * 4\n",
    "            if i % 4 == 0:\n",
    "                A = left_rotate((A + self._G(B, C, D) + X[k] + 0x5a827999) & 0xffffffff, 3)\n",
    "            elif i % 4 == 1:\n",
    "                D = left_rotate((D + self._G(A, B, C) + X[k] + 0x5a827999) & 0xffffffff, 5)\n",
    "            elif i % 4 == 2:\n",
    "                C = left_rotate((C + self._G(D, A, B) + X[k] + 0x5a827999) & 0xffffffff, 9)\n",
    "            elif i % 4 == 3:\n",
    "                B = left_rotate((B + self._G(C, D, A) + X[k] + 0x5a827999) & 0xffffffff, 13)\n",
    "\n",
    "        order = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]\n",
    "        for i in range(16):\n",
    "            k = order[i]\n",
    "            if i % 4 == 0:\n",
    "                A = left_rotate((A + self._H(B, C, D) + X[k] + 0x6ed9eba1) & 0xffffffff, 3)\n",
    "            elif i % 4 == 1:\n",
    "                D = left_rotate((D + self._H(A, B, C) + X[k] + 0x6ed9eba1) & 0xffffffff, 9)\n",
    "            elif i % 4 == 2:\n",
    "                C = left_rotate((C + self._H(D, A, B) + X[k] + 0x6ed9eba1) & 0xffffffff, 11)\n",
    "            elif i % 4 == 3:\n",
    "                B = left_rotate((B + self._H(C, D, A) + X[k] + 0x6ed9eba1) & 0xffffffff, 15)\n",
    "\n",
    "        self.A = (self.A + A) & 0xffffffff\n",
    "        self.B = (self.B + B) & 0xffffffff\n",
    "        self.C = (self.C + C) & 0xffffffff\n",
    "        self.D = (self.D + D) & 0xffffffff\n",
    "\n",
    "    def digest(self):\n",
    "        return pack('<4I', self.A, self.B, self.C, self.D)\n",
    "\n",
    "    def hex_digest(self):\n",
    "        return hexlify(self.digest()).decode()\n",
    "    \n",
    "    \n",
    "def md_pad(message):\n",
    "    \"\"\"Pads the given message the same way the pre-processing of the MD4 algorithm does.\"\"\"\n",
    "    ml = len(message) * 8\n",
    "\n",
    "    message += b'\\x80'\n",
    "    message += bytes((56 - len(message) % 64) % 64)\n",
    "    message += pack('<Q', ml)\n",
    "\n",
    "    return message\n",
    "\n",
    "def state_from_digest(md4hash):\n",
    "    # Unpack a md4 hash into the 4 state variables\n",
    "    return unpack(\"<4I\", b'\\xdb4mi\\x1dz\\xccM\\xc2b]\\xb1\\x9f\\x9e?R')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import os\n",
    "class MD4Oracle:\n",
    "    \n",
    "    def __init__(self):\n",
    "        # Generate key\n",
    "        self._key = os.urandom(12)\n",
    "        \n",
    "    def generate(self, message):\n",
    "        # Generate a valid MAC\n",
    "        return MD4(self._key + message).digest()\n",
    "    \n",
    "    def check(self, mac, message):\n",
    "        # Check if a MAC is valid\n",
    "        real_mac = self.generate(message)\n",
    "        return real_mac == mac"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original MAC b'\\x8939\\x0e7\\xcd\\x93j\\xcdD(\\x8aV\\xab\\x99\\xb8'\n",
      "MD4 State (238629769, 1788071223, 2317894861, 3097078614)\n"
     ]
    }
   ],
   "source": [
    "# We will try to forge a MAC for the following prefix\n",
    "oracle = MD4Oracle()\n",
    "original_message = b\"comment1=cooking%20MCs;userdata=foo;comment2=%20like%20a%20pound%20of%20bacon\"\n",
    "original_mac = oracle.generate(original_message)\n",
    "md4_state = unpack('<4I', original_mac)\n",
    "print(\"Original MAC\", original_mac)\n",
    "print(\"MD4 State\", md4_state)\n",
    "assert oracle.check(original_mac, original_message)\n",
    "\n",
    "# In this example, we want to forge a MAC that has the same prefix as the original one.\n",
    "# The attacker know the original message and the original MAC, but has no information about the key,\n",
    "# except a vague idea about its length (let's say between 0 and 256 bytes).\n",
    "\n",
    "# The message we want to append\n",
    "new_message_suffix = b\";admin=true\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found a valid MAC b'\\xe3\\xcb\\r\\xdc\\tL\\x17\\xff\\x04\\x81`OP\\xe0\\x0c\\x9f' for keylength ! 12\n"
     ]
    }
   ],
   "source": [
    "# Bruteforce over keylength to get the desired result\n",
    "for i in range(0, 15):\n",
    "\n",
    "    glue_padding = md_pad(b'A'*i + original_message)[len(original_message)+i:]\n",
    "    new_message = md_pad(b'A'*i + original_message)[i:] + new_message_suffix\n",
    "\n",
    "    # Let's generate the MAC, then find the message that corresponds to the MAC\n",
    "    fake_md4_generator = MD4(new_message_suffix, ml=(i + len(new_message))*8,\n",
    "                             A=md4_state[0], B=md4_state[1], C=md4_state[2], D=md4_state[3])\n",
    "    fake_mac = fake_md4_generator.digest()\n",
    "\n",
    "    if oracle.check(fake_mac, new_message):\n",
    "        print(\"Found a valid MAC\", fake_mac, \"for keylength !\", i)\n",
    "        break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 31\n",
    "\n",
    "\n",
    "Breaking HMAC-SHA1 timing leak. Shouldn't be too hard. Webserver and HMAC function are copied over here but should be called from another file to be able to run independently."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# see exercice31.py file"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Attacker payload\n",
    "import os\n",
    "content = bytes_to(os.urandom(50), 'hex')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Current key is b'\\xd3\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00'\n",
      "Current key is b'\\xd3\\x16\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00'\n",
      "Current key is b'\\xd3\\x16h\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00'\n",
      "Current key is b'\\xd3\\x16hw\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00'\n",
      "Current key is b'\\xd3\\x16hw\\x04\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00'\n",
      "Current key is b'\\xd3\\x16hw\\x04,\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00'\n",
      "Current key is b'\\xd3\\x16hw\\x04,\\xbb\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00'\n",
      "Current key is b'\\xd3\\x16hw\\x04,\\xbb+\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00'\n",
      "Current key is b'\\xd3\\x16hw\\x04,\\xbb+\\xcc\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00'\n",
      "Current key is b'\\xd3\\x16hw\\x04,\\xbb+\\xcc\\x93\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00'\n",
      "Current key is b'\\xd3\\x16hw\\x04,\\xbb+\\xcc\\x93H\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00'\n",
      "Current key is b'\\xd3\\x16hw\\x04,\\xbb+\\xcc\\x93H\\xd1\\x00\\x00\\x00\\x00\\x00\\x00\\x00\\x00'\n",
      "Current key is b'\\xd3\\x16hw\\x04,\\xbb+\\xcc\\x93H\\xd1\\x9d\\x00\\x00\\x00\\x00\\x00\\x00\\x00'\n",
      "Current key is b'\\xd3\\x16hw\\x04,\\xbb+\\xcc\\x93H\\xd1\\x9d\\x9e\\x00\\x00\\x00\\x00\\x00\\x00'\n",
      "Current key is b'\\xd3\\x16hw\\x04,\\xbb+\\xcc\\x93H\\xd1\\x9d\\x9ev\\x00\\x00\\x00\\x00\\x00'\n",
      "Current key is b'\\xd3\\x16hw\\x04,\\xbb+\\xcc\\x93H\\xd1\\x9d\\x9ev\\xaf\\x00\\x00\\x00\\x00'\n",
      "Current key is b'\\xd3\\x16hw\\x04,\\xbb+\\xcc\\x93H\\xd1\\x9d\\x9ev\\xaf\\xfb\\x00\\x00\\x00'\n",
      "Current key is b'\\xd3\\x16hw\\x04,\\xbb+\\xcc\\x93H\\xd1\\x9d\\x9ev\\xaf\\xfb\\xfe\\x00\\x00'\n",
      "Current key is b'\\xd3\\x16hw\\x04,\\xbb+\\xcc\\x93H\\xd1\\x9d\\x9ev\\xaf\\xfb\\xfe}\\x00'\n",
      "Current key is b'\\xd3\\x16hw\\x04,\\xbb+\\xcc\\x93H\\xd1\\x9d\\x9ev\\xaf\\xfb\\xfe}\\x82'\n",
      "\n",
      "\n",
      "Key should be b'\\xd3\\x16hw\\x04,\\xbb+\\xcc\\x93H\\xd1\\x9d\\x9ev\\xaf\\xfb\\xfe}\\x82'\n"
     ]
    },
    {
     "ename": "AttributeError",
     "evalue": "'Response' object has no attribute 'body'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAttributeError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-33-408e9bb81c81>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m     36\u001b[0m req =  requests.get(\"http://localhost:9999\", params={\"signature\": bytes_to(current_hmac, 'hex'),\n\u001b[1;32m     37\u001b[0m                                               \"content\": content})\n\u001b[0;32m---> 38\u001b[0;31m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'Q'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mreq\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbody\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mAttributeError\u001b[0m: 'Response' object has no attribute 'body'"
     ]
    }
   ],
   "source": [
    "# Now, bruteforce the HMAC byte per byte. Simple.\n",
    "import time, requests\n",
    "\n",
    "\n",
    "current_hmac = b'\\x00' * 20\n",
    "\n",
    "def index_of_max(a):\n",
    "    # Find the index of the highest value in an array as well as its index\n",
    "    assert  len(a) > 0\n",
    "    mx, idx = a[0], 0\n",
    "    for i in range(1, len(a)):\n",
    "        if mx < a[i]:\n",
    "            mx, idx =  a[i], i\n",
    "    return mx, idx\n",
    "\n",
    "# A HMAC is 20 bytes long\n",
    "for i in range(20):\n",
    "    \n",
    "    # And each byte may be between 0 and 255\n",
    "    timers = []\n",
    "    for b in range(255):\n",
    "\n",
    "        current_hmac = current_hmac[:i] + bytes([b]) + current_hmac[i+1:]\n",
    "        start = time.monotonic()\n",
    "        requests.get(\"http://localhost:9999\", params={\"signature\": bytes_to(current_hmac, 'hex'),\n",
    "                                               \"content\": content})\n",
    "        timers.append(time.monotonic() - start)\n",
    "    \n",
    "    # Find the byte that had the slowest answer. This one should be it.\n",
    "    mx, idx = index_of_max(timers)\n",
    "    current_hmac = current_hmac[:i] + bytes([idx]) + current_hmac[i+1:]\n",
    "    print('Current key is', current_hmac)\n",
    "\n",
    "    \n",
    "print('\\n\\nKey should be', current_hmac)\n",
    "req =  requests.get(\"http://localhost:9999\", params={\"signature\": bytes_to(current_hmac, 'hex'),\n",
    "                                              \"content\": content})\n",
    "print('Is this the right key ?', req.json())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "Key should be b'\\xd3\\x16hw\\x04,\\xbb+\\xcc\\x93H\\xd1\\x9d\\x9ev\\xaf\\xfb\\xfe}\\x82'\n",
      "Q True\n"
     ]
    }
   ],
   "source": [
    "print('\\n\\nKey should be', current_hmac)\n",
    "req =  requests.get(\"http://localhost:9999\", params={\"signature\": bytes_to(current_hmac, 'hex'),\n",
    "                                              \"content\": content})\n",
    "print('Q', req.json())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 32\n",
    "\n",
    "Basically the same but with lower artificial sleep.\n",
    "Use following techniques :\n",
    "- guess bytes in groups to amplify the early abort\n",
    "- use statistical methods and a lot of retries to find slowest guess"
   ]
  }
 ],
 "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": 2
}