cryptopals_set5.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Generic\n",
    "\n",
    "Helpers. All copied from previous notebooks"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import os\n",
    "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": [
    "# Crypto\n",
    "\n",
    "Simple crypto functions that are only accessory. Copied from previous notebooks."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import itertools\n",
    "from Crypto.Cipher import AES\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",
    "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\"\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 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",
    "\n",
    "def encrypt_aes_cbc(clear, key, IV=None, debug=False):\n",
    "    \"\"\"CBC using the ECB mode of above\n",
    "    \"\"\"\n",
    "    if IV is None:\n",
    "        IV=b'\\x00'*16\n",
    "    clear = pad(clear, blocksize=16)\n",
    "    prev_block = IV\n",
    "    cipher = b''\n",
    "    for blockstart in range(0, len(clear), 16):\n",
    "        block = clear[blockstart:blockstart+16]\n",
    "        if debug:\n",
    "            print(\"encrypting...\", block)\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",
    "    if debug:\n",
    "        print(\"resulting cipher :\", cipher)\n",
    "    return cipher\n",
    "def decrypt_aes_cbc(cipher, key, IV=None, debug=False):\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",
    "        if debug:\n",
    "            print(\"decrypting...\", block)\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",
    "    if debug:\n",
    "        print(\"resulting clear :\", clear)\n",
    "    return unpad(clear)\n",
    "\n",
    "test_iv = os.urandom(16)\n",
    "assert decrypt_aes_cbc(encrypt_aes_cbc(b\"cookingMCslikeapoundofbacon\", b'YELLOW SUBMARINE', IV=test_iv), b'YELLOW SUBMARINE', IV=test_iv) == b\"cookingMCslikeapoundofbacon\"\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "b'cookingMCslikeapoundofbacon\\x05\\x05\\x05\\x05\\x05'"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pad(b\"cookingMCslikeapoundofbacon\", blocksize=16)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Cryptopals Notebook\n",
    "\n",
    "## Set 5\n",
    "\n",
    "### Exercice 33\n",
    "\n",
    "Diffie-Hellman."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import random\n",
    "import hashlib\n",
    "\n",
    "class DH:\n",
    "    \n",
    "    def __init__(self, p=37, g=5, a=None):\n",
    "        self._p, self._g = p, g\n",
    "        self._A, self._B, self._s = None, None, None\n",
    "        self.generate_private_key(a)\n",
    "        \n",
    "    def generate_private_key(self, a=None):\n",
    "        self._a = random.randint(0, self._p-1)\n",
    "        if a is not None:\n",
    "            self._a = a\n",
    "        # goooo, python! power-mod is included\n",
    "        # otherwise - not that hard to implement :\n",
    "        # use a classic power algorithm but mod\n",
    "        # the result everytime you multiply by the base\n",
    "        self._A = pow(self._g, self._a, self._p)\n",
    "        \n",
    "    @property\n",
    "    def public_key(self):\n",
    "        if self._A is None:\n",
    "            self.generate_private_key()\n",
    "        return self._A\n",
    "\n",
    "    def generate_session_key(self, B):\n",
    "        # Generate the session key from the distant public key\n",
    "        # and the local private key\n",
    "        self._B = B\n",
    "        self._s = pow(B, self._a, self._p)\n",
    "        return self._s\n",
    "        \n",
    "    @property\n",
    "    def session_key(self):\n",
    "        return self._s\n",
    "    \n",
    "    @property\n",
    "    def key(self):\n",
    "        sha1 = hashlib.sha1()\n",
    "        sha1.update(hex(self._s)[2:].encode())\n",
    "        return sha1.digest()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Alice session key : 36\n",
      "Bob session key : 36\n"
     ]
    }
   ],
   "source": [
    "alice = DH()\n",
    "bob = DH()\n",
    "alice.generate_session_key(bob.public_key)\n",
    "bob.generate_session_key(alice.public_key)\n",
    "print('Alice session key :', alice.session_key)\n",
    "print('Bob session key :', bob.session_key)\n",
    "assert alice.session_key == bob.session_key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class NISTDH(DH):\n",
    "    def __init__(self, a=None):\n",
    "        self._p = 0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff\n",
    "        self._g = 2\n",
    "        super().__init__(self._p, self._g, a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Alice session key : b'K\\xc4n\\xbdGX>8\\x1b\\xac\\xb4\\xb4\\xe72\\xd4x\\xa5`\\x8e\\xe5'\n",
      "Bob session key : b'K\\xc4n\\xbdGX>8\\x1b\\xac\\xb4\\xb4\\xe72\\xd4x\\xa5`\\x8e\\xe5'\n"
     ]
    }
   ],
   "source": [
    "alice = NISTDH()\n",
    "bob = NISTDH()\n",
    "alice.generate_session_key(bob.public_key)\n",
    "bob.generate_session_key(alice.public_key)\n",
    "print('Alice session key :', alice.key)\n",
    "print('Bob session key :', bob.key)\n",
    "assert alice.session_key == bob.session_key"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 34\n",
    "\n",
    "MITM on DH. Let the fun begin ! We will emulate network actors with a simple message passing class. Back and forth is handled using callbacks and predefined functions. Messages are arbitrary python objects/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class NetworkActor:\n",
    "    \n",
    "    def __init__(self, name, actions):\n",
    "        self._log = []\n",
    "        self._name = name\n",
    "        self._actions = actions\n",
    "        self._dh = NISTDH()\n",
    "        self._action_idx = 0\n",
    "        \n",
    "    @property\n",
    "    def name(self):\n",
    "        return self._name\n",
    "    \n",
    "    def initiate(self, receiver):\n",
    "        # Trigger first action\n",
    "        action = self._actions[self._action_idx]\n",
    "        self._action_idx = (self._action_idx + 1) % len(self._actions)\n",
    "        action(self, receiver)\n",
    "    \n",
    "    def send(self, receiver, msg):\n",
    "        receiver.receive(self, msg)\n",
    "        \n",
    "    def receive(self, sender, msg):\n",
    "        print('[.]', sender.name, '->', self.name, '\\n', msg, '\\n\\n')\n",
    "        if self._actions:\n",
    "            action = self._actions[self._action_idx]\n",
    "            self._action_idx = (self._action_idx + 1) % len(self._actions)\n",
    "            action(self, sender, msg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[.] Alice -> Bob \n",
      " {'p': 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919, 'g': 2, 'A': 388712358194302795818422031719832238594049407398319062885254342311945502195044750945184834394649615937633754440978528453518137165115881724920167032850623966116635833295822452294389546620408370282213867342900933773052631051863236898541496510939515210326452331618952173448196502251924613045991916948801099560601081866748733072210092528528461349543677391147605391209900959096967088700833962576835556329098841968585577355312438016896290942604047810078803971878356146} \n",
      "\n",
      "\n",
      "[.] Bob -> Alice \n",
      " {'B': 209612737763834694395513180305369748542649109184363008088876620239122390928684926387074917518973117185560825903896569813326923622802500428774807754316150826800261172190167717276942991792607280236138389645316931221983239463871873715465644344162791262202725316531408718176952088547419261954761831676673147224355677905495224624227756170259328000816312375811374297021326220097248019622200261654839104519938891119221131352341073875628584917678210458996053691960142265} \n",
      "\n",
      "\n",
      "[.] Alice -> Bob \n",
      " b'r\\xb3=(u\\x87\\x9f\\x8f\\xb3\\xaa\\xb2\\x9bU,\\xa6\\xad\\x11\\xca7\\xa3\\xc7\\xda\\x03\\x8f\\xa7\\x16T\\xac\\x9a\\x88\\x03\\x94\\x08{\\xd8\\xbc\\x89]\\xa9o\\xa8`\\xcfa\\xa9\\x05\\x0b\\x08' \n",
      "\n",
      "\n",
      "[.] Bob -> Alice \n",
      " b'\\xecs\\x15O#\\xaaU\\x03\\xc7\\x02\\x07\\xc1\\xc2\\xfdT\\xc5\\xcc)*\\xef\\x0cs\\xbe:\\xd6\\xf0g\\x1fh`\\x88\\x07\\xab\\x10=\\xeb\\x1f\\n2`\\x02\\x03E\\xa2\\x0f\\xfe\\xf0\\x1d' \n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# First, the sequence without the MITM actor\n",
    "import os\n",
    "\n",
    "def ex34_initiate(alice, bob):\n",
    "    # First, Alice sends its parameters to Bob\n",
    "    alice._dh = NISTDH()\n",
    "    bob.receive(alice, {\"p\": alice._dh._p, \"g\": alice._dh._g, \"A\": alice._dh.public_key})\n",
    "\n",
    "def ex34_m1(bob, alice, msg):\n",
    "    # Then bob replies with its public key\n",
    "    p, g, A = msg[\"p\"], msg[\"g\"], msg[\"A\"]\n",
    "    bob._dh = DH(p, g)\n",
    "    bob._dh.generate_session_key(A)\n",
    "    bob.send(alice, {\"B\": bob._dh.public_key})\n",
    "\n",
    "def ex34_m2(alice, bob, msg):\n",
    "    # Alice replies with encrypted random message\n",
    "    B = msg[\"B\"]\n",
    "    alice._dh.generate_session_key(B)\n",
    "    payload = b\"cookingMCslikeapoundofbacon\"\n",
    "    iv = os.urandom(16)\n",
    "    key = alice._dh.key[:16]\n",
    "    \n",
    "    # Alice expects the same message in reply, but encrypted with\n",
    "    # a different IV\n",
    "    alice.expected_reply = payload\n",
    "    alice.iv_to_avoid = iv\n",
    "    \n",
    "    encrypted_msg = encrypt_aes_cbc(payload, key, IV=iv)\n",
    "    alice.send(bob, encrypted_msg + iv)\n",
    "    \n",
    "def ex34_m3(bob, alice, msg):\n",
    "    # Bob decrypts Alice's message and re-encrypts it with another IV\n",
    "    payload = msg[:-16]\n",
    "    iv = msg[-16:]\n",
    "    key = bob._dh.key[:16]\n",
    "    cleartext = decrypt_aes_cbc(payload, key, IV=iv)\n",
    "    \n",
    "    new_iv = os.urandom(16) # don't check if it's the same. YOLO !\n",
    "    encrypted_msg = encrypt_aes_cbc(cleartext, key, IV=new_iv)\n",
    "    bob.send(alice, encrypted_msg + new_iv)\n",
    "    \n",
    "def ex34_final(alice, _, msg):\n",
    "    # Alice decrypts incoming message and checks that it is the same\n",
    "    payload = msg[:-16]\n",
    "    iv = msg[-16:]\n",
    "    key = alice._dh.key[:16]\n",
    "    cleartext = decrypt_aes_cbc(payload, key, IV=iv)\n",
    "    \n",
    "    assert iv != alice.iv_to_avoid\n",
    "    assert cleartext == alice.expected_reply\n",
    "    \n",
    "\n",
    "Alice = NetworkActor(\"Alice\", actions=[ex34_initiate, ex34_m2, ex34_final])\n",
    "Bob = NetworkActor(\"Bob\", actions=[ex34_m1, ex34_m3])\n",
    "\n",
    "Alice.initiate(Bob)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$For\\ B:\\\\\\begin{eqnarray}\n",
    "s &=& (A ^ b)\\mod p\\\\\n",
    "&=& (p ^ b)\\mod p\\\\\n",
    "&=& 0\\\\\\end{eqnarray}$$\n",
    "\n",
    "$$For \\ A:\\\\\\begin{eqnarray}\n",
    "s &=& (B ^ a)\\mod p\\\\\n",
    "&=& (p ^ a)\\mod p\\\\\n",
    "&=& 0\\end{eqnarray}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[.] Alice -> Eve \n",
      " {'p': 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919, 'g': 2, 'A': 1329431685833625354369860065784686073965688617510080613112570227428883292768243821791969074774511404632627311404921715803091588370174584077370629645943689855392206344207534741356889114780022431234497003466903405672350843803636740453906242964325222247968752638766976744916122197395140664099270304807661421953852513165863491773245427840445191693158262002642699059982047521075151710540658887488492526742378643409150867642221417551975343503506261965661753573500902247} \n",
      "\n",
      "\n",
      "[.] Eve -> Bob \n",
      " {'p': 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919, 'g': 2, 'A': 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919} \n",
      "\n",
      "\n",
      "[.] Bob -> Eve \n",
      " {'B': 493610133197382539282284057950190501992448924039579343273271126405921875673823692898994179966546522579543517611754530979511689957113349455299042667664575244108467425780077934169241496971715420246879936766501806760776840640515194770514233574201922521622631256028252974441335700847245606537880108108246033988535181265441291310282953073232269434154673389592320644442391962435048405904052227530411878925944881024733036828403100217666292311365449806848793165071925675} \n",
      "\n",
      "\n",
      "[.] Eve -> Alice \n",
      " {'B': 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919} \n",
      "\n",
      "\n",
      "[.] Alice -> Eve \n",
      " b'\\xf9U\\xa4@\\xcf\\xd8\\xdd\\xb7`W\\xa2\\x90-\\xfa6\\x92\\xc2\\xc0\\xb0\\xae\\x9a!\\x01\\x11\\xd3\\x7f\\x86\\x0f\\x804\\xf9e\\xf6\\x0c\\xd0\\xc8\\xa4R*A\\xcd\\x9e]\\xb9\\x9a\\xdc\\xc0\\xde' \n",
      "\n",
      "\n",
      "[.] Eve -> Bob \n",
      " b'\\xf9U\\xa4@\\xcf\\xd8\\xdd\\xb7`W\\xa2\\x90-\\xfa6\\x92\\xc2\\xc0\\xb0\\xae\\x9a!\\x01\\x11\\xd3\\x7f\\x86\\x0f\\x804\\xf9e\\xf6\\x0c\\xd0\\xc8\\xa4R*A\\xcd\\x9e]\\xb9\\x9a\\xdc\\xc0\\xde' \n",
      "\n",
      "\n",
      "[.] Bob -> Eve \n",
      " b'\\xa0\\xb2\\xf2Z\\xa5\\x85$Q\\xfa\\xf8\\xbf\\x1d\\x82\\x12\\xfb\\xfbUp0<\\x9d\\xb4\\xfeR\\x05\\x07\\x0f\\xc8\\xb6\\xaag\\xc6\\xb7T||\\xdeb\\x90h5\\tY9\\xc9zP:' \n",
      "\n",
      "\n",
      "Intercepted message b'cookingMCslikeapoundofbacon' \n",
      "\n",
      "\n",
      "[.] Eve -> Alice \n",
      " b'\\xa0\\xb2\\xf2Z\\xa5\\x85$Q\\xfa\\xf8\\xbf\\x1d\\x82\\x12\\xfb\\xfbUp0<\\x9d\\xb4\\xfeR\\x05\\x07\\x0f\\xc8\\xb6\\xaag\\xc6\\xb7T||\\xdeb\\x90h5\\tY9\\xc9zP:' \n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Now, the sequence with the attacker (Eve)\n",
    "\n",
    "class MITM(NetworkActor):\n",
    "    def __init__(self, alice, bob, name, actions):\n",
    "        self.alice = alice\n",
    "        self.bob = bob\n",
    "        super().__init__(name, actions)\n",
    "\n",
    "def ex34_initiate_i(eve, _, msg):\n",
    "    # Eve alters the message !\n",
    "    # Bob still should think the message came from Alice in a real world attack\n",
    "    eve.intercepted_p, eve.intercepted_g, eve.intercepted_A = msg[\"p\"], msg[\"g\"], msg[\"A\"]\n",
    "    eve.bob.receive(eve, {\"p\": msg[\"p\"], \"g\": msg[\"g\"], \"A\": msg[\"p\"]})\n",
    "    \n",
    "    \n",
    "def ex34_m1_i(eve, _, msg):\n",
    "    # Eve also modifies this one\n",
    "    eve.intercepted_B = msg[\"B\"]\n",
    "    eve.alice.receive(eve, {\"B\": eve.intercepted_p})\n",
    "    \n",
    "def ex34_m2_i(eve, _, msg):\n",
    "    # Eve intercepts the message and decrypts it easily\n",
    "    sha1 = hashlib.sha1()\n",
    "    sha1.update(hex(0)[2:].encode())\n",
    "    key = sha1.digest()[:16]\n",
    "    payload = msg[:-16]\n",
    "    iv = msg[-16:]\n",
    "    cleartext = decrypt_aes_cbc(payload, key, IV=iv)\n",
    "    eve.intercepted_encrypted_message_1 = msg\n",
    "    eve.cleartext_1 = cleartext\n",
    "    eve.bob.receive(eve, msg)\n",
    "    \n",
    "def ex34_m3_i(eve, _, msg):\n",
    "    # confirm with the return message\n",
    "    sha1 = hashlib.sha1()\n",
    "    sha1.update(hex(0)[2:].encode())\n",
    "    key = sha1.digest()[:16]\n",
    "    payload = msg[:-16]\n",
    "    iv = msg[-16:]\n",
    "    cleartext = decrypt_aes_cbc(payload, key, IV=iv)\n",
    "    eve.intercepted_encrypted_message_2 = msg\n",
    "    eve.cleartext_2 = cleartext\n",
    "    assert eve.cleartext_1 == eve.cleartext_2\n",
    "    print('Intercepted message', cleartext, \"\\n\\n\")\n",
    "    \n",
    "    eve.alice.receive(eve, msg)\n",
    "    \n",
    "\n",
    "Eve = MITM(Alice, Bob, \"Eve\", actions=[ex34_initiate_i, ex34_m1_i, ex34_m2_i, ex34_m3_i])\n",
    "\n",
    "Alice.initiate(Eve)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 35\n",
    "\n",
    "Same idea but with manipulating g instead of the public keys."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[.] Alice -> Bob \n",
      " {'p': 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919, 'g': 2} \n",
      "\n",
      "\n",
      "[.] Bob -> Alice \n",
      " {'g': 2, 'ACK': 'ACK'} \n",
      "\n",
      "\n",
      "[.] Alice -> Bob \n",
      " 882665450804064424646685508158717852644913876155024618774923198413315030318799501392300124829973480213692044148262688802232547730839980925399387985420951877605418323334856951605356657876919021038296078438267962224503885036535336925212196930164764238118714950145970595896267231648355458274042288318944559434780001474185118426370772446084987000464796734991166378004167655868633550445677823012986422804539226681548599502665286921175825032029431163382282347148400220 \n",
      "\n",
      "\n",
      "[.] Bob -> Alice \n",
      " 1415881728309401506115721529201263141956915270447019566085318649676999136548159079932096369455925489762230400733419973002278756276933995370755657435554932503015693585046115253195356555104177994517246709099546794766086622321191104787509141997041788117515966010142380823493749877372952830996694597554938536649136026448060370721893215189884764148488180583436743916951184070433700679682979601732421948273681163203509293693386678822826989726068108397219971145953573539 \n",
      "\n",
      "\n",
      "[.] Alice -> Bob \n",
      " b':\\xab\\xb90\\xd5Qch\\xb4\\xc6\\xa1MC(\\xd1\\x16\\xa8p\\xffT\\xc5\\r\\xf42\\xd6\\x9f\\x81\\nn\\x98l\\x91<\\xd7\\xf32N\\tb\\xc2\\x04>\\xd4c\\xc2\\x97\\xda\\xcf' \n",
      "\n",
      "\n",
      "[.] Bob -> Alice \n",
      " b'\\xf1\\xd5\\x00\\x93}\\'\\xf3e* GZ$\\x0f\\x8c\\x926\\xca\\'\\xcc\\x87:\\x98\\x9d\\xfbc\\'>\\x03\\x99\\x965ya\"\\x9f\\xa6\\x0e\\x94\\xa1\\x86\\xb3x\\xe5Y\\x15\\xbf0' \n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# The base-case without the MITM\n",
    "\n",
    "def ex35_initiate(alice, bob):\n",
    "    # All messages now go through Eve\n",
    "    alice._dh = NISTDH()\n",
    "    alice._sent_p, alice._sent_g = alice._dh._p, alice._dh._g\n",
    "    bob.receive(alice, {\"p\": alice._dh._p, \"g\": alice._dh._g})\n",
    "    \n",
    "def ex35_m1(bob, alice, msg):\n",
    "    # Respond with ACK\n",
    "    p, g = msg[\"p\"], msg[\"g\"]\n",
    "    bob._dh = DH(p, g)\n",
    "    alice.receive(bob, {\"g\": g, \"ACK\": \"ACK\"})\n",
    "    \n",
    "def ex35_m2(alice, bob, msg):\n",
    "    assert msg[\"ACK\"] == \"ACK\"\n",
    "    \n",
    "    # The exercice is worded pretty loosely for this one.\n",
    "    # We just assume that we can change the g value of both parties\n",
    "    # else there is a key mismatch in the end. If we don't assume\n",
    "    # this, we could always renegotiate public keys with Alice for\n",
    "    # the MITM attack, but that kinda defeats the purpose of giving\n",
    "    # Bob a manipulated g value.\n",
    "    alice._dh = DH(alice._sent_p, msg[\"g\"])\n",
    "    alice._dh.generate_private_key()\n",
    "    bob.receive(alice, alice._dh.public_key)\n",
    "    \n",
    "def ex35_m3(bob, alice, msg):\n",
    "    bob._dh.generate_session_key(msg)\n",
    "    alice.receive(bob, bob._dh.public_key)\n",
    "\n",
    "def ex35_m4(alice, bob, msg):\n",
    "    # Alice replies with encrypted random message\n",
    "    B = msg\n",
    "    alice._dh.generate_session_key(B)\n",
    "    payload = b\"cookingMCslikeapoundofbacon\"\n",
    "    iv = os.urandom(16)\n",
    "    key = alice._dh.key[:16]\n",
    "    \n",
    "    # Alice expects the same message in reply, but encrypted with\n",
    "    # a different IV\n",
    "    alice.expected_reply = payload\n",
    "    alice.iv_to_avoid = iv\n",
    "    \n",
    "    encrypted_msg = encrypt_aes_cbc(payload, key, IV=iv)\n",
    "    alice.send(bob, encrypted_msg + iv)\n",
    "    \n",
    "def ex35_m5(bob, alice, msg):\n",
    "    # Bob decrypts Alice's message and re-encrypts it with another IV\n",
    "    payload = msg[:-16]\n",
    "    iv = msg[-16:]\n",
    "    key = bob._dh.key[:16]\n",
    "    cleartext = decrypt_aes_cbc(payload, key, IV=iv)\n",
    "    \n",
    "    new_iv = os.urandom(16) # don't check if it's the same. YOLO !\n",
    "    encrypted_msg = encrypt_aes_cbc(cleartext, key, IV=new_iv)\n",
    "    bob.send(alice, encrypted_msg + new_iv)\n",
    "    \n",
    "def ex35_final(alice, _, msg):\n",
    "    # Alice decrypts incoming message and checks that it is the same\n",
    "    payload = msg[:-16]\n",
    "    iv = msg[-16:]\n",
    "    key = alice._dh.key[:16]\n",
    "    cleartext = decrypt_aes_cbc(payload, key, IV=iv)\n",
    "    \n",
    "    assert iv != alice.iv_to_avoid\n",
    "    assert cleartext == alice.expected_reply\n",
    "\n",
    "Alice = NetworkActor(\"Alice\", actions=[ex35_initiate, ex35_m2, ex35_m4, ex35_final])\n",
    "Bob = NetworkActor(\"Bob\", actions=[ex35_m1, ex35_m3, ex35_m5])\n",
    "\n",
    "Alice.initiate(Bob)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "All the different scenarios :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$With\\ g=1:\\\\\\begin{eqnarray}\n",
    "A &=& (1 ^ a)\\mod p\\\\\n",
    "&=& 1\\\\\n",
    "\\implies s &=& (1 ^ a)\\mod p\\\\\n",
    "&=& 1\\\\\\end{eqnarray}$$\n",
    "\n",
    "$$With\\ g=p:\\\\\\begin{eqnarray}\n",
    "A &=& (p ^ a)\\mod p\\\\\n",
    "&=& 0\\\\\n",
    "\\implies s &=& (0 ^ a)\\mod p\\\\\n",
    "&=& 0\\\\\\end{eqnarray}$$\n",
    "\n",
    "$$With\\ g=p-1:\\\\\\begin{eqnarray}\n",
    "A &=& ((p-1) ^ a)\\mod p\\\\\n",
    "&=& 1\\\\\n",
    "\\implies s &=& (1 ^ a)\\mod p\\\\\n",
    "&=& 1\\\\\\end{eqnarray}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Aaaand with the MITM\n",
    "    \n",
    "def ex35_initiate_i(eve, _, msg):\n",
    "    # Eve intercepts this message and changes the g value\n",
    "    eve.intercepted_p, eve.intercepted_g = msg[\"p\"], msg[\"g\"]\n",
    "    fake_msg = {\"p\": msg[\"p\"], \"g\": eve.fake_g}\n",
    "    eve.bob.receive(eve, fake_msg)\n",
    "    \n",
    "def passthrough_bob_to_alice(eve, _, msg):\n",
    "    # Generic passthrough method\n",
    "    print(\"generic b>a\")\n",
    "    eve.alice.receive(eve, msg)\n",
    "    \n",
    "def passthrough_alice_to_bob(eve, _, msg):\n",
    "    # Generic passthrough method\n",
    "    print(\"generic a>b\")\n",
    "    eve.bob.receive(eve, msg)\n",
    "    \n",
    "def ex35_m4_i(eve, _, msg):\n",
    "    # Eve gets the encrypted message, but already knows the key\n",
    "    sha1 = hashlib.sha1()\n",
    "    sha1.update(hex(eve.forced_key)[2:].encode())\n",
    "    key = sha1.digest()[:16]\n",
    "    payload = msg[:-16]\n",
    "    iv = msg[-16:]\n",
    "    print(\"key\", key)\n",
    "    cleartext = decrypt_aes_cbc(payload, key, IV=iv)\n",
    "    eve.intercepted_encrypted_message_1 = msg\n",
    "    eve.cleartext_1 = cleartext\n",
    "    eve.bob.receive(eve, msg)\n",
    "    \n",
    "def ex35_m5_i(eve, _, msg):\n",
    "    # confirm with the return message\n",
    "    sha1 = hashlib.sha1()\n",
    "    sha1.update(hex(eve.forced_key)[2:].encode())\n",
    "    key = sha1.digest()[:16]\n",
    "    payload = msg[:-16]\n",
    "    iv = msg[-16:]\n",
    "    cleartext = decrypt_aes_cbc(payload, key, IV=iv)\n",
    "    eve.intercepted_encrypted_message_2 = msg\n",
    "    eve.cleartext_2 = cleartext\n",
    "    assert eve.cleartext_1 == eve.cleartext_2\n",
    "    print('Intercepted message', cleartext)\n",
    "    \n",
    "    eve.alice.receive(eve, msg)\n",
    "    \n",
    "Eve = MITM(Alice, Bob, \"Eve\", actions=[ex35_initiate_i, passthrough_bob_to_alice,\n",
    "                                       passthrough_alice_to_bob,\n",
    "                                       passthrough_bob_to_alice,\n",
    "                                       ex35_m4_i, ex35_m5_i])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[.] Alice -> Eve \n",
      " {'p': 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919, 'g': 2} \n",
      "\n",
      "\n",
      "[.] Eve -> Bob \n",
      " {'p': 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919, 'g': 1} \n",
      "\n",
      "\n",
      "[.] Bob -> Eve \n",
      " {'g': 1, 'ACK': 'ACK'} \n",
      "\n",
      "\n",
      "generic b>a\n",
      "[.] Eve -> Alice \n",
      " {'g': 1, 'ACK': 'ACK'} \n",
      "\n",
      "\n",
      "[.] Alice -> Eve \n",
      " 1 \n",
      "\n",
      "\n",
      "generic a>b\n",
      "[.] Eve -> Bob \n",
      " 1 \n",
      "\n",
      "\n",
      "[.] Bob -> Eve \n",
      " 1 \n",
      "\n",
      "\n",
      "generic b>a\n",
      "[.] Eve -> Alice \n",
      " 1 \n",
      "\n",
      "\n",
      "[.] Alice -> Eve \n",
      " b'W\\x1f6\\x9d\\xa4|G\\xf5\\x9a\\xe1\\x0cZ\\xa3U\\xa94\\xa8\\x11\\xb0\\\\oCu~\\xf9S\\xfe\\xcb\\x0f\\x17@\\xcc\\xff\\xed\\x04?\\x95\\xfet+\\xa4\\xefT\\xa8\\xf3(\\x9c\\x16' \n",
      "\n",
      "\n",
      "key b'5j\\x19+y\\x13\\xb0LTWM\\x18\\xc2\\x8dF\\xe6'\n",
      "[.] Eve -> Bob \n",
      " b'W\\x1f6\\x9d\\xa4|G\\xf5\\x9a\\xe1\\x0cZ\\xa3U\\xa94\\xa8\\x11\\xb0\\\\oCu~\\xf9S\\xfe\\xcb\\x0f\\x17@\\xcc\\xff\\xed\\x04?\\x95\\xfet+\\xa4\\xefT\\xa8\\xf3(\\x9c\\x16' \n",
      "\n",
      "\n",
      "[.] Bob -> Eve \n",
      " b'0bL\\t\\xb5<\\xfb\\xcflM\\xf4\\xc1.#\\x11\\x0e%\\xd7\\xa6\\xba\\xae\\x98_A\\xb3\\xb8\\xd6\\xf9\\x1e\\x85M\\xd8v\\x1f\\xda\\x07/\\xf8\\xe9\\xe4\\x1a\\x9b\\xa7m\\x03\\x0f)\\x8d' \n",
      "\n",
      "\n",
      "Intercepted message b'cookingMCslikeapoundofbacon'\n",
      "[.] Eve -> Alice \n",
      " b'0bL\\t\\xb5<\\xfb\\xcflM\\xf4\\xc1.#\\x11\\x0e%\\xd7\\xa6\\xba\\xae\\x98_A\\xb3\\xb8\\xd6\\xf9\\x1e\\x85M\\xd8v\\x1f\\xda\\x07/\\xf8\\xe9\\xe4\\x1a\\x9b\\xa7m\\x03\\x0f)\\x8d' \n",
      "\n",
      "\n",
      "[.] Alice -> Eve \n",
      " {'p': 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919, 'g': 2} \n",
      "\n",
      "\n",
      "[.] Eve -> Bob \n",
      " {'p': 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919, 'g': 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633918} \n",
      "\n",
      "\n",
      "[.] Bob -> Eve \n",
      " {'g': 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633918, 'ACK': 'ACK'} \n",
      "\n",
      "\n",
      "generic b>a\n",
      "[.] Eve -> Alice \n",
      " {'g': 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633918, 'ACK': 'ACK'} \n",
      "\n",
      "\n",
      "[.] Alice -> Eve \n",
      " 1 \n",
      "\n",
      "\n",
      "generic a>b\n",
      "[.] Eve -> Bob \n",
      " 1 \n",
      "\n",
      "\n",
      "[.] Bob -> Eve \n",
      " 1 \n",
      "\n",
      "\n",
      "generic b>a\n",
      "[.] Eve -> Alice \n",
      " 1 \n",
      "\n",
      "\n",
      "[.] Alice -> Eve \n",
      " b'\\xc9V\\xc8K\\xf8\\x19x\\xc0\\x82\\x80Huf\\xf2\\x93B~\\x1d\\xd7\\xf9\\xad\\xd2f\\x17\\xda\\xce\\x96\\xdf\\xda\\xa7\\x10\\x18v\\xd07\\xed\\xb0wr\\xb0\\xd4\\xe2\\xa5k\\xd1\\x9a\\x9fr' \n",
      "\n",
      "\n",
      "key b'5j\\x19+y\\x13\\xb0LTWM\\x18\\xc2\\x8dF\\xe6'\n",
      "[.] Eve -> Bob \n",
      " b'\\xc9V\\xc8K\\xf8\\x19x\\xc0\\x82\\x80Huf\\xf2\\x93B~\\x1d\\xd7\\xf9\\xad\\xd2f\\x17\\xda\\xce\\x96\\xdf\\xda\\xa7\\x10\\x18v\\xd07\\xed\\xb0wr\\xb0\\xd4\\xe2\\xa5k\\xd1\\x9a\\x9fr' \n",
      "\n",
      "\n",
      "[.] Bob -> Eve \n",
      " b'\\xa1@8D.\\xd2;\\x11\\x1e\\xb8i\\xd1\\x1f*z\\xa0i\\xa2\\xbc\\x90\\xd7\\xe6\\x84\\xeb,\\x01@v\\x95\\x15\\xedD\\xcaO\\xd4\\x80\\xb1\\xf8=M\\xf6F\\xdc?\\xf1a[r' \n",
      "\n",
      "\n",
      "Intercepted message b'cookingMCslikeapoundofbacon'\n",
      "[.] Eve -> Alice \n",
      " b'\\xa1@8D.\\xd2;\\x11\\x1e\\xb8i\\xd1\\x1f*z\\xa0i\\xa2\\xbc\\x90\\xd7\\xe6\\x84\\xeb,\\x01@v\\x95\\x15\\xedD\\xcaO\\xd4\\x80\\xb1\\xf8=M\\xf6F\\xdc?\\xf1a[r' \n",
      "\n",
      "\n",
      "[.] Alice -> Eve \n",
      " {'p': 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919, 'g': 2} \n",
      "\n",
      "\n",
      "[.] Eve -> Bob \n",
      " {'p': 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919, 'g': 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919} \n",
      "\n",
      "\n",
      "[.] Bob -> Eve \n",
      " {'g': 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919, 'ACK': 'ACK'} \n",
      "\n",
      "\n",
      "generic b>a\n",
      "[.] Eve -> Alice \n",
      " {'g': 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919, 'ACK': 'ACK'} \n",
      "\n",
      "\n",
      "[.] Alice -> Eve \n",
      " 0 \n",
      "\n",
      "\n",
      "generic a>b\n",
      "[.] Eve -> Bob \n",
      " 0 \n",
      "\n",
      "\n",
      "[.] Bob -> Eve \n",
      " 0 \n",
      "\n",
      "\n",
      "generic b>a\n",
      "[.] Eve -> Alice \n",
      " 0 \n",
      "\n",
      "\n",
      "[.] Alice -> Eve \n",
      " b'\\xfa)T\\r<\\xcd\\xb6y\\x7f`k\\x830 \\xcb\\x86ZR\\xc4k\\xcf\\xe3~\\xb8:z\\xc34)\\x0c\\xa9\\x11UA\\xc9\\x14%\\xdbT\\x13}\\xfb\\xf4\\xc65\\xb1RY' \n",
      "\n",
      "\n",
      "key b'\\xb6X\\x9f\\xc6\\xab\\r\\xc8,\\xf1 \\x99\\xd1\\xc2\\xd4\\n\\xb9'\n",
      "[.] Eve -> Bob \n",
      " b'\\xfa)T\\r<\\xcd\\xb6y\\x7f`k\\x830 \\xcb\\x86ZR\\xc4k\\xcf\\xe3~\\xb8:z\\xc34)\\x0c\\xa9\\x11UA\\xc9\\x14%\\xdbT\\x13}\\xfb\\xf4\\xc65\\xb1RY' \n",
      "\n",
      "\n",
      "[.] Bob -> Eve \n",
      " b')\\xb8\\x88:\\xec\\xe3\\xd81\\xcaL\\xefW/E\\x83\\x1a3H\\xa7`\\xfd[6\\xe8\\xa1\\xa5BK\\r\\xe9\\x9a\\x9aF\\x92V\\xa4\\x95\\x14{3\\xa1V[\\x0b\\x87\\x03\\x1b\\xcf' \n",
      "\n",
      "\n",
      "Intercepted message b'cookingMCslikeapoundofbacon'\n",
      "[.] Eve -> Alice \n",
      " b')\\xb8\\x88:\\xec\\xe3\\xd81\\xcaL\\xefW/E\\x83\\x1a3H\\xa7`\\xfd[6\\xe8\\xa1\\xa5BK\\r\\xe9\\x9a\\x9aF\\x92V\\xa4\\x95\\x14{3\\xa1V[\\x0b\\x87\\x03\\x1b\\xcf' \n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "p = 0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff\n",
    "\n",
    "# g = 1\n",
    "Eve.fake_g, Eve.forced_key = 1, 1\n",
    "Alice.initiate(Eve)\n",
    "\n",
    "# g = p - 1\n",
    "Eve.fake_g, Eve.forced_key = p-1, 1\n",
    "Alice.initiate(Eve)\n",
    "\n",
    "# g = p\n",
    "Eve.fake_g, Eve.forced_key = p, 0\n",
    "Alice.initiate(Eve)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Exercice 36\n",
    "\n",
    "Implement SRP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import os\n",
    "import random\n",
    "\n",
    "BIGP = 0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff\n",
    "MEDIANP = 107\n",
    "SMALLP = 7\n",
    "\n",
    "def sha256(msg):\n",
    "    hasher = hashlib.sha256()\n",
    "    hasher.update(msg.encode())\n",
    "    return hasher.digest()\n",
    "\n",
    "def sha256mac(key, message):\n",
    "    return sha256(key + message) # Meh. Good enough :p."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Both client and server are aware of these at one point at least\n",
    "N, g, k = BIGP, 2, 3\n",
    "P = \"password\"\n",
    "\n",
    "# Server (\"account creation\" - before the actual auth)\n",
    "salt = random.randint(0, 2**64)\n",
    "xH = sha256(hex(salt) + P)\n",
    "x = bytes_to(xH, \"int\")\n",
    "v = pow(g, x, N)\n",
    "# Save to server what needs to be saved (consider the rest discarded)\n",
    "server = {'v': v, 'salt': salt}\n",
    "\n",
    "# Client (start of authentication)\n",
    "I = \"email@test.com\"\n",
    "a = random.randint(0, 2**64)\n",
    "A = pow(g, a, N)\n",
    "client = {'a': a, 'A': A}\n",
    "server['A'] = A # I and A are transmitted \n",
    "server['I'] = I\n",
    "\n",
    "# Server\n",
    "b = random.randint(0, 2**64)\n",
    "B = (k*v + pow(g, b, N)) % N\n",
    "server['b'] = b\n",
    "server['B'] = B\n",
    "client['B'] = B # salt and B are transmitted\n",
    "client['salt'] = salt\n",
    "\n",
    "# Both\n",
    "uH = sha256(str(A) + str(B))\n",
    "u = bytes_to(uH, 'int')\n",
    "client['u'] = u\n",
    "server['u'] = u\n",
    "\n",
    "# Client (knows his password and his session random key a)\n",
    "xH = sha256(hex(salt) + P)\n",
    "x = bytes_to(xH, 'int')\n",
    "client['x'] = x\n",
    "client['S'] = pow(B - k*pow(g, x, N), a + u*x, N)\n",
    "\n",
    "# Server\n",
    "server['S'] = pow(A * pow(v, u, N), b, N)\n",
    "\n",
    "# Ensure it has worked :\n",
    "assert server['S'] == client['S']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Why it works :\n",
    "\n",
    "$$\\begin{align*}\n",
    "S_{client}\n",
    "&= (B-k.g^x)^{a+u.x} \\ \\ (\\mathrm{mod}\\ N) \\\\\n",
    "&= (k.v+g^b-k.g^x)^{a+u.x} \\ \\ (\\mathrm{mod}\\ N) \\\\\n",
    "&= (g^b)^{a+u.x} \\ \\ (\\mathrm{mod}\\ N) \\\\\n",
    "&= (g^{a+u.x})^b \\ \\ (\\mathrm{mod}\\ N) \\\\\n",
    "&= (g^a.(g^x)^u)^b \\ \\ (\\mathrm{mod}\\ N) \\\\\n",
    "&= (A.v^u)^b \\ \\ (\\mathrm{mod}\\ N) \\\\\n",
    "&= S_{server}\n",
    "\\end{align*}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 37\n",
    "\n",
    "Break SRP with a 0-key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Bob is creating an account for username bob\n",
      "Creating account for bob\n",
      "Bob is trying to authenticate as bob\n",
      "Starting authentication flow for identity bob\n",
      "Client bob is authenticated !\n",
      "Bob is authenticated as bob\n"
     ]
    }
   ],
   "source": [
    "# First, let's make SRP into real server and clients\n",
    "\n",
    "# Global constants\n",
    "N, g, k = BIGP, 2, 3\n",
    "\n",
    "class Server:\n",
    "    def __init__(self):\n",
    "        self.accounts = {}\n",
    "        self.sessions = []\n",
    "        \n",
    "    \n",
    "    def create_account(self, I, P):\n",
    "        print(\"Creating account for\", I)\n",
    "        salt = random.randint(0, 2**64)\n",
    "        xH = sha256(hex(salt) + P)\n",
    "        x = bytes_to(xH, \"int\")\n",
    "        v = pow(g, x, N)\n",
    "        self.accounts[I] = {'v': v, 'salt': salt}\n",
    "    \n",
    "    def authenticate(self, I, A, cb):\n",
    "        print(\"Starting authentication flow for identity\", I)\n",
    "        salt = self.accounts[I]['salt']\n",
    "        v = self.accounts[I]['v']\n",
    "        b = random.randint(0, 2**64)\n",
    "        B = (k*v + pow(g, b, N)) % N\n",
    "        uH = sha256(str(A) + str(B))\n",
    "        u = bytes_to(uH, 'int')\n",
    "        S = pow(A * pow(self.accounts[I]['v'], u, N), b, N)\n",
    "        K = bytes_to(sha256(str(S)),'base64')\n",
    "        HMAC = sha256mac(K, str(salt))\n",
    "        self.sessions.append({'I': I, 'A': A, 'b': b, 'K': K, 'HMAC': HMAC})\n",
    "        cb(salt, B, len(self.sessions)-1, self.validate_authentication)\n",
    "    64\n",
    "    def validate_authentication(self, session_id, HMAC):\n",
    "        if self.sessions[session_id]['HMAC'] == HMAC:\n",
    "            print('Client', self.sessions[session_id]['I'], 'is authenticated !')\n",
    "            return True\n",
    "        else:\n",
    "            print('Client', self.sessions[session_id]['I'], 'failed authentication...')\n",
    "            return False\n",
    "\n",
    "    \n",
    "class Client:\n",
    "    def __init__(self, identity, username, password):\n",
    "        self.identity = identity\n",
    "        self.username = username\n",
    "        self.password = password\n",
    "        self.session = {}\n",
    "        \n",
    "    def register_account(self, s):\n",
    "        print(self.identity, \"is creating an account for username\", self.username)\n",
    "        s.create_account(self.username, self.password)\n",
    "    \n",
    "    def authenticate(self, s):\n",
    "        print(self.identity, \"is trying to authenticate as\", self.username)\n",
    "        a = random.randint(0, 2**64)\n",
    "        A = pow(g, a, N)\n",
    "        self.session = {'a': a, 'A':A}\n",
    "        s.authenticate(self.username, A, self.exchange1)\n",
    "        \n",
    "    def exchange1(self, salt, B, session_id, cb):\n",
    "        self.session['salt'] = salt\n",
    "        self.session['B'] = B\n",
    "        uH = sha256(str(self.session['A']) + str(B))\n",
    "        u = bytes_to(uH, 'int')\n",
    "        xH = sha256(hex(salt) + self.password)\n",
    "        x = bytes_to(xH, 'int')\n",
    "        a = self.session['a']\n",
    "        S = pow(B - k*pow(g, x, N), a + u*x, N)\n",
    "        K = bytes_to(sha256(str(S)),'base64')\n",
    "        HMAC = sha256mac(K, str(self.session['salt']))\n",
    "        self.session['K'] = K\n",
    "        self.session['HMAC'] = HMAC\n",
    "        self.session['session_id'] = session_id\n",
    "        if cb(session_id, HMAC):\n",
    "            print(self.identity, \"is authenticated as\", self.username)\n",
    "        \n",
    "\n",
    "Alice = Server()\n",
    "Bob = Client('Bob', 'bob', 'bob@passw0rd')\n",
    "\n",
    "Bob.register_account(Alice)\n",
    "Bob.authenticate(Alice)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Eve is trying to break in as bob\n",
      "Eve : A is N * 34\n",
      "Starting authentication flow for identity bob\n",
      "Client bob is authenticated !\n",
      "Eve is authenticated as bob !\n"
     ]
    }
   ],
   "source": [
    "# Now create a malicious client, that does not know the password !\n",
    "# Eve will use A = 0, which gives S = (0 x v^u)^b = 0\n",
    "# Given that everything is mod N, A = N, 2*N etc... also works.\n",
    "\n",
    "class MaliciousClient(Client):\n",
    "    \n",
    "    def authenticate(self, s):\n",
    "        print(self.identity, \"is trying to break in as\", self.username)\n",
    "        a = 0\n",
    "        i = random.randint(0, 100)\n",
    "        A = N * i\n",
    "        print(\"Eve : A is N *\", i)\n",
    "        self.session = {'a': a, 'A':A}\n",
    "        s.authenticate(self.username, A, self.exchange1)\n",
    "        \n",
    "    def exchange1(self, salt, B, session_id, cb):\n",
    "        self.session['salt'] = salt\n",
    "        S = 0\n",
    "        K = bytes_to(sha256(str(S)),'base64')\n",
    "        HMAC = sha256mac(K, str(self.session['salt']))\n",
    "        self.session['K'] = K\n",
    "        self.session['HMAC'] = HMAC\n",
    "        self.session['session_id'] = session_id\n",
    "        if cb(session_id, HMAC):\n",
    "            print(self.identity, \"is authenticated as\", self.username, \"!\")\n",
    "            \n",
    "Eve = MaliciousClient(\"Eve\", \"bob\", \"\")\n",
    "Eve.authenticate(Alice)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Exercice 38\n",
    "\n",
    "Implement and break a simplified version of SRP, that uses a less secure B value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Server:\n",
    "    def __init__(self):\n",
    "        self.accounts = {}\n",
    "        self.sessions = []\n",
    "        \n",
    "    \n",
    "    def create_account(self, I, P):\n",
    "        print(\"Creating account for\", I)\n",
    "        salt = random.randint(0, 2**128)\n",
    "        xH = sha256(hex(salt) + P)\n",
    "        x = bytes_to(xH, \"int\")\n",
    "        v = pow(g, x, N)\n",
    "        self.accounts[I] = {'v': v, 'salt': salt}\n",
    "    \n",
    "    def authenticate(self, I, A, cb):\n",
    "        print(\"Starting authentication flow for identity\", I)\n",
    "        salt = self.accounts[I]['salt']\n",
    "        v = self.accounts[I]['v']\n",
    "        b = random.randint(0, 2**128)\n",
    "        B = pow(g, b, N)\n",
    "        uH = sha256(str(A) + str(B))\n",
    "        u = bytes_to(uH, 'int')\n",
    "        S = pow(A * pow(self.accounts[I]['v'], u, N), b, N)\n",
    "        K = bytes_to(sha256(str(S)),'base64')\n",
    "        HMAC = sha256mac(K, str(salt))\n",
    "        self.sessions.append({'I': I, 'A': A, 'b': b, 'K': K, 'HMAC': HMAC})\n",
    "        cb(salt, B, len(self.sessions)-1, self.validate_authentication)\n",
    "\n",
    "    def validate_authentication(self, session_id, HMAC):\n",
    "        if self.sessions[session_id]['HMAC'] == HMAC:\n",
    "            print('Client', self.sessions[session_id]['I'], 'is authenticated !')\n",
    "            return True\n",
    "        else:\n",
    "            print('Client', self.sessions[session_id]['I'], 'failed authentication...')\n",
    "            return False\n",
    "\n",
    "    \n",
    "class Client:\n",
    "    def __init__(self, identity, username, password):\n",
    "        self.identity = identity\n",
    "        self.username = username\n",
    "        self.password = password\n",
    "        self.session = {}\n",
    "        \n",
    "    def register_account(self, s):\n",
    "        print(self.identity, \"is creating an account for username\", self.username)\n",
    "        s.create_account(self.username, self.password)\n",
    "    \n",
    "    def authenticate(self, s):\n",
    "        print(self.identity, \"is trying to authenticate as\", self.username)\n",
    "        a = random.randint(0, 2**128)\n",
    "        A = pow(g, a, N)\n",
    "        self.session = {'a': a, 'A':A}\n",
    "        s.authenticate(self.username, A, self.exchange1)\n",
    "        \n",
    "    def exchange1(self, salt, B, session_id, cb):\n",
    "        self.session['salt'] = salt\n",
    "        self.session['B'] = B\n",
    "        uH = sha256(str(self.session['A']) + str(B))\n",
    "        u = bytes_to(uH, 'int')\n",
    "        xH = sha256(hex(salt) + self.password)\n",
    "        x = bytes_to(xH, 'int')\n",
    "        a = self.session['a']\n",
    "        S = pow(B, a + u*x, N)\n",
    "        K = bytes_to(sha256(str(S)),'base64')\n",
    "        HMAC = sha256mac(K, str(self.session['salt']))\n",
    "        self.session['K'] = K\n",
    "        self.session['HMAC'] = HMAC\n",
    "        self.session['session_id'] = session_id\n",
    "        if cb(session_id, HMAC):\n",
    "            print(self.identity, \"is authenticated as\", self.username)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Bob is creating an account for username bob\n",
      "Creating account for bob\n",
      "Bob is trying to authenticate as bob\n",
      "Starting authentication flow for identity bob\n",
      "Client bob is authenticated !\n",
      "Bob is authenticated as bob\n"
     ]
    }
   ],
   "source": [
    "Alice = Server()\n",
    "Bob = Client('Bob', 'bob', 'bob@passw0rd')\n",
    "\n",
    "Bob.register_account(Alice)\n",
    "Bob.authenticate(Alice)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "with open('/usr/share/dict/british-english') as _in:\n",
    "    words = _in.read().split('\\n')[:1000]\n",
    "\n",
    "class MITMServer:\n",
    "    \n",
    "    def __init__(self, server, manipulate=False):\n",
    "        self.accounts = {}\n",
    "        self.sessions = []\n",
    "        self.server = server\n",
    "        self.manipulate = manipulate\n",
    "    \n",
    "    def create_account(self, I, P):\n",
    "        self.server.create_account(I, P) # Let's pretend I didn't see that.\n",
    "    \n",
    "    def authenticate(self, I, A, cb):\n",
    "        print(\"Starting MITMing auth flow for\", I)\n",
    "        self.client = {'I': I, 'A': A, 'cb': cb}\n",
    "        self.server.authenticate(I, A, self.authenticate_cb)\n",
    "    \n",
    "    def authenticate_cb(self, salt, B, session_id, cb):\n",
    "        print(\"MITM server got server data back\")\n",
    "        self.server = {'salt': salt, 'B': B, 'session_id': session_id, 'cb': cb}\n",
    "        if self.manipulate:\n",
    "            print(\"Forcing b = 2, B = g^2\")\n",
    "            self.client['cb'](salt, pow(g, 2, N), session_id, self.validate_authentication)\n",
    "        else:\n",
    "            self.client['cb'](salt, B, session_id, self.validate_authentication)\n",
    "    \n",
    "    def validate_authentication(self, session_id, HMAC):\n",
    "        print(\"MITM authentication validation intercepted.\")\n",
    "        if self.manipulate:\n",
    "            uH = sha256(str(self.client['A']) + str(pow(g, 2, N)))\n",
    "            u = bytes_to(uH, 'int')\n",
    "            offline_dictionnary_attack(HMAC, self.server['salt'], self.client['A'],\n",
    "                                       pow(g, 2, N), 2, u)\n",
    "            print('Authentication not completed (because tampering). But we have the password !')\n",
    "        self.server['cb'](session_id, HMAC)\n",
    "        \n",
    "import tqdm\n",
    "def offline_dictionnary_attack(HMAC, salt, A, B, b, u):\n",
    "    for word in tqdm.tqdm(words):\n",
    "        xH = sha256(hex(salt) + word)\n",
    "        x = bytes_to(xH, 'int')\n",
    "        S_try = (pow(B, u*x, N)*pow(A, b, N)) % N\n",
    "        K_try = bytes_to(sha256(str(S_try)),'base64')\n",
    "        HMAC_try = sha256mac(K_try, str(salt))\n",
    "        if HMAC_try == HMAC:\n",
    "            print('Password found :', word)\n",
    "            return word\n",
    "    print('Password not found :(...')\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "  2%|▏         | 20/1000 [00:00<00:04, 197.43it/s]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Bob is creating an account for username bob\n",
      "Creating account for bob\n",
      "Bob is trying to authenticate as bob\n",
      "Starting MITMing auth flow for bob\n",
      "Starting authentication flow for identity bob\n",
      "MITM server got server data back\n",
      "MITM authentication validation intercepted.\n",
      "Client bob is authenticated !\n",
      "\n",
      "Bob is creating an account for username bob\n",
      "Creating account for bob\n",
      "Bob is trying to authenticate as bob\n",
      "Starting MITMing auth flow for bob\n",
      "Starting authentication flow for identity bob\n",
      "MITM server got server data back\n",
      "Forcing b = 2, B = g^2\n",
      "MITM authentication validation intercepted.\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      " 68%|██████▊   | 677/1000 [00:02<00:01, 275.79it/s]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Password found : Andre's\n",
      "Authentication not completed (because tampering). But we have the password !\n",
      "Client bob failed authentication...\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "Alice = Server()\n",
    "Bob = Client('Bob', 'bob', 'bob@passw0rd')\n",
    "Eve = MITMServer(Alice)\n",
    "\n",
    "Bob.register_account(Eve)\n",
    "Bob.authenticate(Eve)\n",
    "print(\"\")\n",
    "\n",
    "# With password cracking\n",
    "import random\n",
    "Alice = Server()\n",
    "Bob = Client('Bob', 'bob', random.choice(words))\n",
    "Eve = MITMServer(Alice, manipulate=True)\n",
    "\n",
    "Bob.register_account(Eve)\n",
    "Bob.authenticate(Eve)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given that Eve has intercepted the salt, Eve can deduce K from S. This means she has to crack S with the offline dictionnary attack. This works because :\n",
    "\n",
    "$$\\begin{align*}\n",
    "S_{client}\n",
    "&= B^{a+u.x} \\ \\ (\\mathrm{mod}\\ N) \\\\\n",
    "&= B^{u.x}.B^{a} \\ \\ (\\mathrm{mod}\\ N) \\\\\n",
    "&= B^{u.x}.A^{b} \\ \\ (\\mathrm{mod}\\ N) \\\\\n",
    "\\end{align*}$$\n",
    "\n",
    "Eve has intercepted u and A, and has forced B and b, so it can simply bruteforce the value of K _offline_ !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Exercice 39\n",
    "\n",
    "Implement RSA\n",
    "\n",
    "*Warning : uses an external lib for the primegen part, that wraps OpenSSL, as suggested*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# First, get some primitives down :\n",
    "\n",
    "import gensafeprime\n",
    "\n",
    "def primegen(small=True):\n",
    "    \"\"\"Generate a random prime.\"\"\"\n",
    "    if small:\n",
    "        return gensafeprime.generate(32)\n",
    "    return gensafeprime.generate(128)\n",
    "\n",
    "def egcd(r, u, v, rp, up, vp):\n",
    "    \"\"\"Extended Euclid algorithm for GCD\n",
    "    Given a, b, find GCD(a,b) and x,y such that :\n",
    "        a.x + b.y = GCD(a,b)     (Bézout coefficients)\n",
    "    \"\"\"\n",
    "    if r == 0:\n",
    "        return up, vp\n",
    "    else:\n",
    "        return egcd(rp - (rp // r)*r, up - (rp // r)*u, vp - (rp // r)*v, r, u, v)\n",
    "    \n",
    "    \n",
    "def invmod(a, N):\n",
    "    \"\"\"Calculate the inverse modulo\"\"\"\n",
    "    x, _ = egcd(a, 1, 0, N, 0, 1)\n",
    "    return x % N\n",
    "\n",
    "assert (invmod(15, 37) * 15) % 37 == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 126,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import base64\n",
    "\n",
    "def str_to_int(s):\n",
    "    return int(base64.b16encode(s), 16)\n",
    "def int_to_str(i):\n",
    "    s = hex(i)[2:].upper()\n",
    "    if len(s) % 2 == 1:\n",
    "        s = '0' + s # base16 wants even length strings, adding a 0 in front does not change the value. Perfect.\n",
    "    return base64.b16decode(s)\n",
    "assert int_to_str(str_to_int((b\"Hello, world !\"))) == b'Hello, world !'\n",
    "\n",
    "class RSA:\n",
    "    def __init__(self, small=True):\n",
    "        self.p = primegen(small=small)\n",
    "        self.q = primegen(small=small)\n",
    "        self.n = self.p * self.q\n",
    "        self.et = (self.p - 1) * (self.q - 1)\n",
    "        self.e = 3\n",
    "        self.d = invmod(self.e, self.et)\n",
    "        self.block_length = 3 + (not small)*9\n",
    "    \n",
    "    @property\n",
    "    def public(self):\n",
    "        return self.e, self.n\n",
    "    \n",
    "    @property\n",
    "    def private(self):\n",
    "        return self.d, self.n\n",
    "    \n",
    "    def encrypt_block(self, s, i2s = True):\n",
    "        # Encrypt one block\n",
    "        if isinstance(s, bytes):\n",
    "            m = str_to_int(s)\n",
    "            if m > self.n:\n",
    "                print(m, self.n)\n",
    "                raise Exception(\"Message not encryptable. Please use blocks.\")\n",
    "            if i2s:\n",
    "                return int_to_str(pow(m, self.e, self.n))\n",
    "            else:\n",
    "                return pow(m, self.e, self.n)\n",
    "        else:\n",
    "            m = s\n",
    "            return pow(m, self.e, self.n)\n",
    "    \n",
    "    def decrypt_block(self, s, i2s = True):\n",
    "        if isinstance(s, bytes):\n",
    "            c = str_to_int(s)\n",
    "            if c > self.n:\n",
    "                print(c, self.n)\n",
    "                raise Exception(\"Message not encryptable. Please use blocks.\")\n",
    "            if i2s:\n",
    "                return int_to_str(pow(c, self.d, self.n))\n",
    "            else:\n",
    "                return pow(c, self.d, self.n)\n",
    "        else:\n",
    "            c = s\n",
    "            return pow(c, self.d, self.n)\n",
    "    \n",
    "    def encrypt(self, s):\n",
    "        acc = []\n",
    "        for i in range(0, len(s), self.block_length):\n",
    "            acc.append(self.encrypt_block(s[i:i+self.block_length]))\n",
    "        return acc\n",
    "        \n",
    "    \n",
    "    def decrypt(self, s):\n",
    "        return b\"\".join(self.decrypt_block(b) for b in s)\n",
    "        \n",
    "    \n",
    "r = RSA(small=False)\n",
    "assert r.decrypt(r.encrypt(b\"Vanilla Ice Baby\")) == b'Vanilla Ice Baby'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Exercice 40\n",
    "\n",
    "Break RSA with E = 3, broadcast attack."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "r1, r2, r3 = RSA(small=False), RSA(small=False), RSA(small=False)\n",
    "text = b'Cooking MC\\'s like a pound of bacon'\n",
    "c1, c2, c3 = r1.encrypt(text), r2.encrypt(text), r3.encrypt(text)\n",
    "(_, n1),(_, n2),(_, n3) = r1.public, r2.public, r3.public"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "b'Cooking MC&\\xe8 like a pou.d of bacon'\n"
     ]
    }
   ],
   "source": [
    "import decimal\n",
    "def decrypt(c1, n1, c2, n2, c3, n3):\n",
    "    c1, c2, c3 = str_to_int(c1), str_to_int(c2), str_to_int(c3)\n",
    "    e1 = invmod(n2*n3, n1) * n2 * n3\n",
    "    e2 = invmod(n1*n3, n2) * n1 * n3\n",
    "    e3 = invmod(n1*n2, n3) * n1 * n2\n",
    "    cleartext = (c1 * e1 + c2 * e2 + c3 * e3) % (n1 * n2 * n3)\n",
    "    return round(pow(cleartext, decimal.Decimal(1)/3)) # Decimal allows to have for higher precision\n",
    "\n",
    "\n",
    "c = b\"\".join([int_to_str(decrypt(c1i, n1, c2i, n2, c3i, n3)) for c1i, c2i, c3i in zip(c1, c2, c3)])\n",
    "print(c) # It's not exaaaactly the original, so no assert here.\n",
    "         # But very close and could be improved with a better cube root algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}