01 hash functions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Cryptographic hash functions\n",
    "\n",
    "A cryptographic hash function satisfies the following properties (see [Rogaway and Shrimpton](https://eprint.iacr.org/2004/035)):\n",
    "\n",
    "> **preimage-resistance / one-way function**: for essentially all pre-specified outputs, it is computationally infeasible to find any input which hashes to that output, i.e., to find any preimage $x'$ such that $h(x') = y$ when given any $y$ for which a corresponding input is not known\n",
    "\n",
    "> **2nd-preimage / weak collision resistance**: it is computationally infeasible to find any second input which has the same output as any specified input, i.e., given $x$, to find a 2nd-preimage $x' \\neq x$ such that $h(x) = h(x')$.\n",
    "\n",
    "> **strong collision resistance**: it is computationally infeasible to find any two distinct inputs $x, x'$ which\n",
    "hash to the same output, i.e., such that $h(x) = h(x')$.\n",
    "\n",
    "Let's take a look at a practical example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'97e6c5c06e30d8e6de51d5b923fb6b1efab0061732eb23634e1f856694c075ca'"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from cryptography.hazmat.backends import default_backend\n",
    "from cryptography.hazmat.primitives import hashes\n",
    "\n",
    "# initialize the digest object with the required hash algorithm\n",
    "digest = hashes.Hash(hashes.SHA256(), backend=default_backend())\n",
    "\n",
    "# the message to be encoded should be a bytes object (byte array);\n",
    "# if you specify a string without encoding, each character might be read as more than one byte\n",
    "message = 'to hash'.encode('utf-8')\n",
    "\n",
    "# the digest object is updated with message contents\n",
    "digest.update(message)\n",
    "\n",
    "# any further string updates are appended to the message to be hashed\n",
    "digest.update('append to message'.encode('utf-8'))\n",
    "\n",
    "# finalizing the digest object disables any further updates and returns the hash\n",
    "# output as hexadecimal to be a little more legible\n",
    "digest.finalize().hex()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise**: try changing a single letter of the message, and verify that the digest changes completely.\n",
    "\n",
    "**Exercise**: Verify that the message digest if the length you expect from a [SHA-256](https://en.wikipedia.org/wiki/SHA-2) hash. Try changing the hash algorithm to one with a different digest length, e.g. [MD5](https://en.wikipedia.org/wiki/MD5)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Integrity, non-repudiation, and collision attacks\n",
    "\n",
    "Hash functions are commonly used to guarantee **integrity** of a message, or a file.\n",
    "1. The smallest change in input leads to a large change in output.\n",
    "2. Hash digests are very small, usually much smaller than the message.\n",
    "3. Digests are very quick to compute in software.\n",
    "\n",
    "In order to rely on hash functions for this use in general, they need to be resistant against not only preimage but also collision attacks. If a collision can be found with a practical algorithm, it becomes possible to generate two files with different content but the same hash - see below for links to examples (advanced topic).\n",
    "\n",
    "The so-called *birthday attack* works on any hash function and is therefore considered the point of reference for collision attacks. You can read up on the [birthday problem](https://en.wikipedia.org/wiki/Birthday_problem) for your information. For the purpose of this exercise, assume that the following is true.\n",
    "\n",
    "> **Birthday problem**: Suppose a sequence of integers $I=\\{i\\}_{j=1}^n$ are drawn uniformly at random with replacement in the range $[1,d]$. Let the probability that any two of these integers are equal be\n",
    ">\n",
    "> $\n",
    "\\begin{align*}\n",
    "    p(n,d) & = \\mathbb{P}(i_j=i_k) \\qquad \\mbox{for any} \\; i_j, i_k \\in I \\\\\n",
    "           & = 1 -  \\binom{d}{n} \\frac{ n! }{ d^n} \\\\\n",
    "           & \\approx 1-e^{-n(n-1)/(2d)}\n",
    "\\end{align*}    \n",
    "$.\n",
    ">\n",
    "> The number of random integers required to obtain a given $p$ is\n",
    ">\n",
    "> $n(p,d) \\approx \\left[2d\\ln\\left(\\frac{1}{1-p}\\right)\\right]^{1/2}$\n",
    "\n",
    "This result applies to *ideal* hash functions to the extent that digests are indistinguishable from random numbers.\n",
    "\n",
    "**Exercise**: suppose there are $n$ students in your classroom. Each person has a birthday that can be mapped to the range $[1,366]$. Calculate the probability that any two out of $n$ students have the same birthday. Calculate the number of students required for probablities in the range $[0.1, 0.9]$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYQAAAEGCAYAAABlxeIAAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjAsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+17YcXAAAgAElEQVR4nO3deXhU5d3G8e8vO/u+hxCQIPuWACouVbFSEXHBumEVtFYr1rrUautrFbXi0lpfiwuKgLhQdylSd6yCC4SdhMUYQkhYAoGEJWSd5/1jBt6IgAjJnJnJ/bmuXMycOUluDmTunHOe8xxzziEiIhLldQAREQkNKgQREQFUCCIiEqBCEBERQIUgIiIBMV4HOFotW7Z0ycnJXscQEQkrixYt2uaca3Ww18K2EJKTk0lPT/c6hohIWDGz9Yd6TYeMREQEUCGIiEiACkFERIAwPodwMBUVFeTl5VFaWup1lLCVkJBAYmIisbGxXkcRkSCLqELIy8ujUaNGJCcnY2Zexwk7zjkKCwvJy8ujc+fOXscRkSCLqENGpaWltGjRQmVwlMyMFi1aaA9LpI6KqEIAVAbHSNtPJPT5fLUzS3XEFYKISCQqrajizUV5XPDUfKZ9mVMr30OFEESjR48mOzv7qD53wYIF9O/fn/79+9OvXz/efvvt/a8VFRUxevRounfvTo8ePfjqq6/2v/bkk0/SvXt3evXqxR133AHAihUruPrqq4/p7yIiwZGzbQ8PvpfJCQ99wm2vL2NJbhGzlm2sle8VUSeVQ1lGRgZVVVV06dLlqD6/d+/epKenExMTw6ZNm+jXrx8jR44kJiaGm2++meHDh/PGG29QXl5OSUkJAHPnzuXdd99l2bJlxMfHU1BQAECfPn3Iy8sjNzeXpKSkGvs7ikjNqKzy8cnqAl76ej1ffLtt//LeHRpz5QmdGNmvfa18XxVCDcrJyWH48OGkpqayePFievXqxYsvvkj9+vV5+eWXGTVq1P51GzZsyM0338zs2bOpV68e7777Lm3atDnk165fv/7+x6WlpfuP9RcXF/P5558zbdo0AOLi4oiLiwPg6aef5s477yQ+Ph6A1q1b7/8aI0eOZObMmfv3GkTEe1t3lfHqglxeXZDLpmL/4I74mChG9mvPmBM60S+xSa2e54vYQki+871a+bo5E0cc9vU1a9YwZcoUhg4dyrhx43jqqae4/fbbmT9/Ppdddtn+9fbs2cMJJ5zAgw8+yB133MFzzz3H3Xfffdiv/c033zBu3DjWr1/PjBkziImJYd26dbRq1YqxY8eybNkyUlNTeeKJJ2jQoAFr167liy++4M9//jMJCQk89thjDBo0CIC0tDQmTpyoQhAJAWs272LKvGzeWbqR8kofAF1aNuDyIUmMTk2kaf24oOTQOYQa1rFjR4YOHQrAmDFjmDdvHgCbNm2iVav/n2AwLi6Oc889F4DU1FRycnJ+9GsPGTKEjIwMFi5cyEMPPURpaSmVlZUsXryYG264gSVLltCgQQMmTpwIQGVlJdu3b+frr7/m0Ucf5Ze//CX77qHdunVrNm6sneOQIvLjfD7H3DUFXDnlG87+x+e8lp5HRZWPYT3a8NI1Q/jkttO49pQuQSsDiOA9hB/7Tb62HLg7t+95vXr1vje+PzY2dv9r0dHRVFZWHvH36NGjBw0bNmTlypUkJiaSmJjIkCFDAP+J632FkJiYyIUXXoiZMXjwYKKioti2bRutWrWitLSUevXqHdPfVUR+utKKKt5eks+UeevIKtgNQL3YaC5OS2Ts0M50btnAs2zaQ6hhubm5+0f5vPLKK5x88smA/008KyvrRz//7bff5q677vrB8nXr1u0vjfXr17N69WqSk5Np27YtHTt2ZM2aNQB88skn9OzZE4Dzzz+fuXPnArB27VrKy8tp2bLl/ue9e/c+xr+tiByp4pIKnvzkW06a+Cl3vbWCrILdtG2cwB+Hd+fru85kwqjenpYBRPAegleOP/54Jk2axLhx4+jZsyc33HADACNGjOCzzz5j2LBhh/387777jsaNG/9g+bx585g4cSKxsbFERUXx1FNP7X9zf/LJJ7niiisoLy+nS5cuTJ06FYBx48Yxbtw4evfuTVxcHNOnT9+/VzJ37lxGjPBmL0qkLtm6q4wp89bx0tfr2V3m/6WuT4cmXHtKZ87p047Y6ND5vdz2HVMON2lpae7AG+SsWrWKHj16eJTIP8ro3HPPZeXKlT94be/evZx++unMnz+f6OjoQ36NMWPG8Pjjj3/vfENNKysr47TTTmPevHnExPzwdwKvt6NIJNiwvYTJn2fzWvoGygInik/u2pLfnn4cJ3bxboodM1vknEs72GvaQwiSevXqcd9995Gfn3/Ysf8vvfRSrWfJzc1l4sSJBy0DETk2WQW7eOqz73h36UaqAlNM/LxnG357elf6d2zqcbrD0ztCDUpOTj7o3sE+Z599dhDTHFpKSgopKSlexxCJKFkFu3nik2+ZvXwjzkF0lHHBgA7c8LPj6NamkdfxjkjEFYJzThO0HYNwPYQo4pWcbXv430++5Z2l+fgcxEVHMTotketPPY6kFvV//AuEkIgqhISEBAoLCzUF9lHadz+EhIQEr6OIhLwN20t48tNveXNxPlU+R0yUccmgjow/oysdmobnkO6gFIKZDQeeAKKB551zEw94PQmYDjQNrHOnc27OT/0+iYmJ5OXlsXXr1hpIXTftu2OaiBzcxqK9TJqbxWvpG6iockRHGRenJvK7M1Po2Dy89ggOVOuFYGbRwCTgLCAPWGhms5xzmdVWuxt4zTn3tJn1BOYAyT/1e8XGxupOXyJSK4pKypk0N4vpX62nvNKHGVwwoAO/OzPF8+sHakow9hAGA1nOuWwAM5sJjAKqF4ID9g2+bwJoTgURCQmlFVVM/zKHSXOz2Fnqv45gRN923DIsha6tw+Nk8ZEKRiF0ADZUe54HDDlgnXuBD83sJqABcNCrt8zsOuA6QNM2i0itqvI53lmSz98+XMPGwMyjQ7u24K5f9KB3hyYep6sdoXJS+TJgmnPub2Z2IjDDzHo753zVV3LOTQYmg//CNA9yikiEc87x37Vbmfif1azevAuAHu0ac+cvunNqSsuIHrASjELIBzpWe54YWFbdNcBwAOfcV2aWALQECoKQT0QEgMyNO3lwTibzswoBaN8kgdvPPp7z+3cgKipyi2CfYBTCQiDFzDrjL4JLgcsPWCcXOBOYZmY9gARAQ4VEJCi27ynnbx+u4dUFufgcNE6IYfwZXfnVickkxB56qplIU+uF4JyrNLPxwAf4h5S+4JzLMLMJQLpzbhZwG/Ccmd2C/wTz1U5XSIlILauo8jHjq/X84+O17CytJDrKGHtSJ24+MyWo9yEIFUE5hxC4pmDOAcvuqfY4ExgajCwiIgCfr93KhNmZ++9JcEpKS+45tycpYTLNRG0IlZPKIiJBsW7bHh58L5OPV/lPUXZqUZ//GdGTM3u0jugTxkdChSAidUJpRRX//DSLyZ9nU17lo0FcNDedmcLYocnEx9Sd8wSHo0IQkYg3d3UB98xayYbtewG4aGAifxx+PK0ba96u6lQIIhKxNhXv5b5ZmbyfsRmA7m0b8cD5vUlLbu5xstCkQhCRiFNZ5WPalzn8/aO1lJRXUT8umluGdePqockhdcvKUKNCEJGIsmj9dv789sr9Vxmf3asNfxnZi/ZhOiV1MKkQRCQi7Cqt4OH3V/PS17kAJDarx4RRvTijexuPk4UPFYKIhL25qwv409sr2FRcSkyU8ZvTujD+9BTqxWn00E+hQhCRsLV9TzkT/p3BO0v9M+b3TWzCwxf1pUe7xj/ymXIwKgQRCTvOOWYv38S9szIo3FNOQmwUt511PGOHJhOjk8ZHTYUgImFlc3Epd7+zko9XbQHghC7NmXhhX5Ij5K5lXlIhiEhYcM7x+qI87v93JrvKKmkUH8OfRvTg0kEd6/yUEzVFhSAiIa9gVyl/emvF/vmHhvVozQPn96FtE11pXJNUCCIS0mYv38jd76ykqKSCRgkxTBjVi/P7d9BeQS1QIYhISCoqKed/3s3g38v8I4hOSWnJI6P70q6JLjCrLSoEEQk5c1cXcMeby9m6q4z6cdH86ZweXDEkSXsFtUyFICIhY3dZJQ/MzmTmwg0ADEpuxmMX96NTC40gCgYVgoiEhCW5O/j9v5ayvrCEuOgobj+7G9ec3IXoOnBz+1ChQhART1X5HE9/lsXjH39Llc/Ro11jnri0P93q8K0svaJCEBHP5Bft5ZZ/LWXBuu0AXHtyZ/4w/HjdwcwjKgQR8cTs5Rv501sr2FlaSatG8fzt4n6c2q2V17HqNBWCiATV7rJK/vJuBm8uzgNgWI82PHxRH1o0jPc4magQRCRolucVcdOrS1hfWEJCbBR3j+ip4aQhRIUgIrXOOcfU+Tk89J9VVFT5Txw/eVl/urbWieNQokIQkVpVVFLOH95YzkeZ/tlJrz4pmbvO6a4TxyFIhSAitWZx7g5uemUJ+UV7aZQQw6Oj+zK8dzuvY8khqBBEpMb5fI7nvsjm0Q/WUOlz9Etswj8vH0jH5vW9jiaHoUIQkRq1fU85t7++jE9X+6eqvvbkztwxvDtxMbqTWahTIYhIjVm0fjs3vryEzTtLaVIvlr9d3I9hPdt4HUuOkApBRI6Zc45pX+bw4HurqPQ5BiY15cnLB9KhqaaqDicqBBE5JnvKKvnjm8uZvXwTANec3Jk7f9GdWN3sPuyoEETkqGUV7Ob6lxaRVbCbBnHRPDK6HyP6ahRRuFIhiMhReW/5Ju54Yxl7yqvo2rohz4xJpWvrhl7HkmOgQhCRn6SiysfE/6xmyrx1AIzs156JF/ahQbzeTsKd/gVF5IgV7CzlxlcWszBnBzFRxt0jenDVScmaiyhCqBBE5Igszt3B9TMWUbCrjDaN43nqioGkdmrudSypQUEZBmBmw81sjZllmdmdh1jnl2aWaWYZZvZKMHKJyJGZuSCXS5/9moJdZQzu3JzZN52iMohAtb6HYGbRwCTgLCAPWGhms5xzmdXWSQHuAoY653aYWevaziUiP6680seE2Rm89HUuAFed2Im7z+2pIaURKhiHjAYDWc65bAAzmwmMAjKrrfNrYJJzbgeAc64gCLlE5DAKdpVy48v+8wVx0VE8cEFvfpnW0etYUouCUQgdgA3VnucBQw5YpxuAmc0HooF7nXPvH/iFzOw64DqApKSkWgkrIrB0QxHXz1jE5p2ltG2cwDNXptK/Y1OvY0ktC5WTyjFACvAzIBH43Mz6OOeKqq/knJsMTAZIS0tzwQ4pUhe8lr6Bu99ZSXmlj0HJzZh0xUBaN0rwOpYEQTAKIR+ovp+ZGFhWXR7wjXOuAlhnZmvxF8TCIOQTEaCyyseDc1YxdX4OAGNOSOKec3tpltI6JBiFsBBIMbPO+IvgUuDyA9Z5B7gMmGpmLfEfQsoOQjYRAYr3VjD+lcV88e02YqON+0f15tLBOixb19R6ITjnKs1sPPAB/vMDLzjnMsxsApDunJsVeO3nZpYJVAF/cM4V1nY2EYHsrbu5dno62dv20KJBHM9cmcqgZA0prYvMufA8FJ+WlubS09O9jiES1r74dis3vryYnaWVdG/biOevSiOxme5qFsnMbJFzLu1gr4XKSWURCaJ99y944L1VVPkcP+/Zhscv6a/5iOo4/euL1DHllT7+Mmslry7wjwYff3pXbj2rG1FRmo+orlMhiNQh2/eUc/1Li1iwbjvxMVE8Mrovo/p38DqWhAgVgkgdkVWwm3HTFpK7vYTWjeJ57ldp9NPFZlKNCkGkDpiftY3rX1rErtJKendozPO/GkTbJrrYTL5PhSAS4V5dkMv/vLOSysDJ439c2p/6cfrRlx/S/wqRCFXlczz8/momf+6/xvM3p3Xhj2d318ljOSQVgkgEKimv5OaZS/kocwsxUcYD5+vKY/lxKgSRCLO5uJRrX1zIyvydNE6I4ZkxqZzUtaXXsSQMqBBEIkjGxmKumZbO5p2ldGpRnylXDaJr64Zex5IwoUIQiRBz1xQw/uXF7CmvYnByc565MpXmDeK8jiVhRIUgEgFe/mY997ybQZXPMap/ex4Z3Zf4mGivY0mYUSGIhDGfz/HwB6t59r/+kUQ3neGfhsJMI4nkp1MhiISp0ooqbnttGe+t2ERMlPHXC/rwy0G657EcPRWCSBjavqecX7+YzqL1O2gUH8NTYwZySkorr2NJmFMhiISZddv2MHbqAnIKS2jfJIEXxg6ie9vGXseSCKBCEAkji9Zv59rp6ewoqaBX+8a8cPUg2jTWnERSM1QIImHi/ZWbuHnmUsoqfZx+fCv+eflA3dBGapT+N4mEgWnz13Hf7Eycg8sGJ3H/qF7EREd5HUsijApBJIT5fI6H/rOK575YB8Afzj6e3/7sOA0rlVqhQhAJUaUVVdz2+jLeW+4fVvrI6L5cODDR61gSwVQIIiGouKSCX89IZ8G67TSM909Qd3KKJqiT2qVCEAkxeTtKuHrqQrIKdtOmcTxTrx5Mz/YaViq1T4UgEkIyN+7k6qkLKNhVRrc2DZk2djDtm9bzOpbUESoEkRAxP2sbv5mxiN1llZzQpTnPXplGk3qxXseSOkSFIBIC3l2az+2vL6OiyjGyX3seu1izlUrwqRBEPPbc59k8OGcVANee3Jk/ndND9z0WT6gQRDzi8zkenLOKKfP81xjcPaIH157SxeNUUpepEEQ8UFbpn7p69vJNxEYbj13cj1H9O3gdS+o4FYJIkO0sreC6F9P5Ott/jcHkK1M5qauuMRDvqRBEgmhzcSlXT13A6s27aN0onmljdY2BhI4fnR3LzH5hZt+Y2Roze83MTgxGMJFIk1Wwi4ue/pLVm3fRpVUD3rzhJJWBhJQj2UN4ChgDZAKpwKNmNsk592qtJhOJIIvW7+Ca6QspKqlgYFJTplw1iGYN4ryOJfI9R1IIBc65+YHHH5vZV8A3gApB5Ah8smoLN76ymNIKH2d2b80/Lx9IvThdYyCh50gmVF9nZg+Y2b5fZyqAylrMJBIx/rUwl+tmLKK0wsclaR159spUlYGErCMpBB9wAbDBzOYBWcBnZpZSq8lEwphzjic/+ZY/vrmCKp/jpjO6MvGiPrqpjYS0Hz1k5Jy7HMDM4oHeQL/Ax3Nm1sU5l1S7EUXCS5XPce+sDGZ8vR4zmHBeL648MdnrWCI/6oiHnTrnyoBFgY+fxMyGA08A0cDzzrmJh1jvIuANYJBzLv2nfh8Rr5VWVHHLv5byn5WbiYuJ4n8v7c/w3u28jiVyRGr9OgQziwYmAWcBecBCM5vlnMs8YL1GwM34T1iLhJ3ivRX8+kX/TW0aJcTw/K/SGNKlhdexRI5YMA5oDgaynHPZzrlyYCYw6iDr3Q88DJQGIZNIjdpcXMolz37FgnXbadM4ntevP1FlIGEnGIXQAdhQ7XleYNl+ZjYQ6Oice+9wX8jMrjOzdDNL37p1a80nFTkKWQW7919wdlzggrPubXXBmYQfz4c8mFkU8Hfgth9b1zk32TmX5pxLa9WqVe2HE/kRi3N3MPqZL8kv2suApKa8cf1JJDar73UskaMSjLmM8oGO1Z4nBpbt0wj/6KXPzAygLTDLzM7TiWUJZZ+u3sJvX9YFZxI5glEIC4EUM+uMvwguBS7f96JzrhjYP9WjmX0G3K4ykFD2WvoG7nrLf43BL9MS+esFusZAwl+tF4JzrtLMxgMf4B92+oJzLsPMJgDpzrlZtZ1BpKY453jqs+949IM1AIw/vSu3/bwbgb1bkbAWlOmvnXNzgDkHLLvnEOv+LBiZRH6qKp9jwr8zmP6V/4Kze0f24qqTkr2OJVJjdD8EkSNQWlHFra8tZc6KzcRFR/H4Jf0Z0VcXnElkUSGI/IidpRX8eno636zbTqP4GCb/Ko0Tj9M1BhJ5VAgih7FlZylXvfD/dzibPm4wPdrpGgOJTCoEkUPIKtjNVS8sIL9oL11aNeDFcYN1jYFENBWCyEFUv8PZgKSmvKA7nEkdoEIQOYDucCZ1lQpBpJqZC3L58zsrqfI5LknryIMX9NYFZ1JnqBBE8F9w9sQn3/KPj78F4KYzunLrWbrgTOoWFYLUeZVVPu5+ZyUzF24gyuD+83tzxZBOXscSCToVgtRpJeWVjH9lCZ+uLiA+JoonLxvAz3u19TqWiCdUCFJnFe4uY9z0dJZtKKJZ/Viev2oQqZ2aeR1LxDMqBKmT1hfu4aoXFpBTWEJis3pMHzeY41o19DqWiKdUCFLnLM8rYuzUhRTuKadX+8ZMHTuI1o0SvI4l4jkVgtQpc9cUcOPLiykpr+KUlJY8PSaVhvH6MRABFYLUIa8uyOXuwDUGFw7owMSL+hIXo2sMRPZRIUjEc87x2IdrmDT3O0A3tRE5FBWCRLTySh93vLGMd5ZuJDrKeOD83lw2OMnrWCIhSYUgEat4bwXXz1jEV9mF1I+LZtIVAzn9+NZexxIJWSoEiUj5RXsZO3UBa7fsplWjeKZePYjeHZp4HUskpKkQJOKszC9m3LSFFOwqI6V1Q6aOHaT7GIgcARWCRJTPAsNK95RXcUKX5jw7Jo0m9WO9jiUSFlQIEjFmfL2ev7y7Ep+DUf3b88jovsTH6D4GIkdKhSBhr8rn+OucVUyZtw7wT119y7BuREVpWKnIT6FCkLBWUl7JzTOX8lHmFmKjjYcu7Mvo1ESvY4mEJRWChK0tO0u5dno6K/KLaZwQw7NXpnHicS28jiUStlQIEpZWbdrJuGkL2VRcSlLz+kwdO0izlYocIxWChJ3qI4lSOzVj8pWptGgY73UskbCnQpCw8uJXOdz370yqfI6R/drz6Oi+JMRqJJFITVAhSFioqPJx378zeOnrXMA/Qd2tZ2kkkUhNUiFIyCsqKefGVxYzP6uQuJgoHr6oDxcM0EgikZqmQpCQllWwm2unLySnsISWDeOZ/KtUBibpvscitUGFICHr87VbufGVxewqraRnu8Y8d1UaHZrW8zqWSMRSIUjIcc4x/csc7n9vFVU+x9m92vD4Jf2pH6f/riK1ST9hElIqqnz8ZVYGr3yjk8ciwaZCkJCxbXcZN768mG/WbScuJopHR/dlVP8OXscSqTNUCBISVuQV85sZ6WwsLqV1o3ievTKVATp5LBJUUcH4JmY23MzWmFmWmd15kNdvNbNMM1tuZp+YWadg5JLQ8NbiPEY/8yUbi0sZmNSU2TedrDIQ8UCt7yGYWTQwCTgLyAMWmtks51xmtdWWAGnOuRIzuwF4BLiktrOJtyqqfPx1ziqmzs8B4LLBSdx7Xk/dw0DEI8E4ZDQYyHLOZQOY2UxgFLC/EJxzc6ut/zUwJgi5xEOFu8sY/8oSvsouJDbauPe8XlwxRDuGIl4KRiF0ADZUe54HDDnM+tcA/znYC2Z2HXAdQFJSUk3lkyBbmV/Mb2YsIr9oL60axfP0FQNJS27udSyROi+kTiqb2RggDTjtYK875yYDkwHS0tJcEKNJDXlrcR5/ensFpRU++ndsyrNXptKmcYLXsUSE4BRCPtCx2vPEwLLvMbNhwJ+B05xzZUHIJUFUWlHFff/O5NUF/usLLknryITze+l8gUgICUYhLARSzKwz/iK4FLi8+gpmNgB4FhjunCsIQiYJotzCEm54eREZG3cSFxPFhPN6ccmgjpjpYjORUFLrheCcqzSz8cAHQDTwgnMuw8wmAOnOuVnAo0BD4PXAm0Suc+682s4mte+jzC3c+tpSdpVWktS8Pk9dMZDeHZp4HUtEDiIo5xCcc3OAOQcsu6fa42HByCHBU1nl49EP1/Dsf7MBOKtnGx67uB9N6sV6nExEDiWkTipLZCjYWcr4V5ewYN12oqOMPw4/nl+f0kWHiERCnApBatT8rG3cPHMp23aX0bpRPP+8fCCDO2tIqUg4UCFIjaio8vH3j9byzH+/wzk4sUsLnrisP60baUipSLhQIcgxyy0s4aaZS1i2oYgog9+dmcJNZ3QlJjooU2WJSA1RIcgxeWdJPne/s5LdZZW0b5LAPy4doENEImFKhSBHZXdZJfe8u5K3FvuvMTynT1seuqAvTeprFJFIuFIhyE+2PK+I3726hJzCEhJio7h3pC40E4kEKgQ5YpVVPiZ/kc3jH62losrRo11jnrysP11bN/I6mojUABWCHJHvtu7mtteWsXRDEQBXn5TMnb/oTkKs5iISiRQqBDksn88x9cscHnl/NWWVPto1SeDhi/pyardWXkcTkRqmQpBDyi0s4fY3lrFg3XYALhqYyD0je2r6CZEIpUKQH3DO8fI3ufx1zipKyqto2TCehy7sw1k923gdTURqkQpBvie/aC93vrmcL77dBsC5fdsxYVRvmjeI8ziZiNQ2FYIA/hFE077M4e8fraWkvIqm9WO5f1RvRvZr73U0EQkSFYKwIq+Yu95ezsr8nQAM79WWCef30jxEInWMCqEO211Wyd8+XMP0L3PwOejQtB73ndeLYTpXIFInqRDqqA8zNvOXWRlsKi4lyuDXp3Tm98O60SBe/yVE6ir99Ncx+UV7uW9WBh9mbgGgb2IT/npBH93WUkRUCHXFnrJKnv3vdzz7eTZllT4axEXzh7OP58oTk4mO0hxEIqJCiHg+n+OtJfk88v5qCnaVATCibzvuHtGDdk3qeZxOREKJCiGCLczZzv2zM1meVwz4Dw/dc25P0pJ1vwIR+SEVQgTasL2Eie+v5r3lmwBo0zieO87uzgUDOhClw0MicggqhAhSuLuMZz/PZtqXOZRX+oiPieI3px3H9ad1oX6c/qlF5PD0LhEBduwpZ/IX2Uz/MoeS8ioARvVvzx3Du9Ohqc4TiMiRUSGEseKSCp6fl83U+TnsLqsE4Mzurfn9sG70SdQwUhH5aVQIYWhnaQVT5+Xw/LxsdpX6i+DUbq24ZVgKA5KaeZxORMKVCiGMbN1Vxoyv1zP9yxyK91YAMLRrC24Z1k0jh0TkmKkQwsDqzTuZ8sU63l26kfIqHwCDOzfn1rO6cUKXFh6nE5FIoUIIUT6f47/fbmXKF+uYl+W/N4EZnNWzDdec3JkhnZtjpiGkIlJzVAghpqS8kksraCcAAAgtSURBVHeWbGTKvGy+27oHgPpx0VycmsjYoZ1JbtnA44QiEqlUCCHAOUf6+h28kZ7Heys27R8x1K5JAledlMxlg5JoUl/3MRaR2qVC8FB+0V7eWpTHm4vzyCks2b98QFJTrj4pmXP6tCM2OsrDhCJSl6gQgmxPWSUfZW7hjUV5zP9uG875l7dpHM+FAxO5aGAiXVs39DakiNRJKoQg2FS8l09WFfDxqi18mVW4f6RQXEwUZ/dqy+jURE7u2lLTUIuIp1QItcA5R8bGnXy8agsfr9qy/17F4B8plNqpGRcM6MDIvu11bkBEQoYKoQb4fI6srbtJz9lB+vrtfPVdIZuKS/e/Xi82mlNSWjKsZxvO6N6alg3jPUwrInJwKoSjsLe8imV5RSxav4P0nO0szi3af+XwPm0ax3Nmjzac1aMNJx7XgoTYaI/SiogcmaAUgpkNB54AooHnnXMTD3g9HngRSAUKgUuccznByHY4xXsryN66m+yte/iu2p/rtu2h0ue+t267JgmkdmpGWqdmpCU3p2e7xrr3gIiElVovBDOLBiYBZwF5wEIzm+Wcy6y22jXADudcVzO7FHgYuKQ28pRWVFFUUsH2PeXsKCln+55yikrK2b6nYv/zzTtLyd66h227yw76NaIMerZrTFpyM38JJDfXNNMiEvaCsYcwGMhyzmUDmNlMYBRQvRBGAfcGHr8B/NPMzDn3/V/Da8DYqQv5KrvwiNZNiI2ic8uGHNeqAce1akiXan/qhjMiEmmC8a7WAdhQ7XkeMORQ6zjnKs2sGGgBbKu+kpldB1wHkJSUdFRhWjeOp1WjeJrXj6NZg1iaN4ijaf24wPM4mjeIpWXDeDq3bED7JvV02EdE6oyw+jXXOTcZmAyQlpZ2VHsPT1w6oEYziYhEimDMi5APdKz2PDGw7KDrmFkM0AT/yWUREQmSYBTCQiDFzDqbWRxwKTDrgHVmAVcFHo8GPq2N8wciInJotX7IKHBOYDzwAf5hpy845zLMbAKQ7pybBUwBZphZFrAdf2mIiEgQBeUcgnNuDjDngGX3VHtcClwcjCwiInJwmltZREQAFYKIiASoEEREBFAhiIhIgIXr6E4z2wqsP8TLLTngKucQo3zHRvmOXahnVL5jc7h8nZxzrQ72QtgWwuGYWbpzLs3rHIeifMdG+Y5dqGdUvmNztPl0yEhERAAVgoiIBERqIUz2OsCPUL5jo3zHLtQzKt+xOap8EXkOQUREfrpI3UMQEZGfSIUgIiJABBaCmQ03szVmlmVmd3qd50BmlmNmK8xsqZmlh0CeF8yswMxWVlvW3Mw+MrNvA382C7F895pZfmAbLjWzczzM19HM5ppZppllmNnNgeUhsQ0Pky8ktqGZJZjZAjNbFsh3X2B5ZzP7JvBz/K/A1PmhlG+ama2rtv36e5GvWs5oM1tiZrMDz49u+znnIuYD//Ta3wFdgDhgGdDT61wHZMwBWnqdo1qeU4GBwMpqyx4B7gw8vhN4OMTy3Qvc7vW2C2RpBwwMPG4ErAV6hso2PEy+kNiGgAENA49jgW+AE4DXgEsDy58BbgixfNOA0V5vv2o5bwVeAWYHnh/V9ou0PYTBQJZzLts5Vw7MBEZ5nCmkOec+x38PiupGAdMDj6cD5wc1VDWHyBcynHObnHOLA493Aavw3yM8JLbhYfKFBOe3O/A0NvDhgDOANwLLvdx+h8oXMswsERgBPB94bhzl9ou0QugAbKj2PI8Q+s8f4IAPzWyRmV3ndZhDaOOc2xR4vBlo42WYQxhvZssDh5Q8O6RVnZklAwPw/xYZctvwgHwQItswcLhjKVAAfIR/L7/IOVcZWMXTn+MD8znn9m2/BwPb73Ezi/cqH/AP4A7AF3jegqPcfpFWCOHgZOfcQOAXwI1mdqrXgQ7H+fc5Q+o3IuBp4DigP7AJ+Ju3ccDMGgJvAr93zu2s/loobMOD5AuZbeicq3LO9cd/v/XBQHevshzMgfnMrDdwF/6cg4DmwB+9yGZm5wIFzrlFNfH1Iq0Q8oGO1Z4nBpaFDOdcfuDPAuBt/D8AoWaLmbUDCPxZ4HGe73HObQn8kPqA5/B4G5pZLP4325edc28FFofMNjxYvlDbhoFMRcBc4ESgqZntu6NjSPwcV8s3PHAozjnnyoCpeLf9hgLnmVkO/kPkZwBPcJTbL9IKYSGQEjjDHof/3syzPM60n5k1MLNG+x4DPwdWHv6zPDELuCrw+CrgXQ+z/MC+N9qAC/BwGwaO104BVjnn/l7tpZDYhofKFyrb0MxamVnTwON6wFn4z3PMBUYHVvNy+x0s3+pqZW/4j897sv2cc3c55xKdc8n43+8+dc5dwdFuP6/PjtfC2fZz8I+k+A74s9d5DsjWBf/Ip2VARijkA17Ff8igAv+xxmvwH4P8BPgW+BhoHmL5ZgArgOX433jbeZjvZPyHg5YDSwMf54TKNjxMvpDYhkBfYEkgx0rgnsDyLsACIAt4HYgPsXyfBrbfSuAlAiORvPwAfsb/jzI6qu2nqStERASIvENGIiJylFQIIiICqBBERCRAhSAiIoAKQUREAlQIIiICqBBERCRAhSBSg8zsLTN7wMw+N7NcMxvmdSaRI6VCEKlZffDPNHkqcDNwhcd5RI6YCkGkhphZfaAJ8HhgUSxQ5F0ikZ9GhSBSc3oCi5xzVYHnfQnNyQtFDkqFIFJz+uCfPG6fvvgnRRMJCyoEkZpzYCH0RnsIEkY026mIiADaQxARkQAVgoiIACoEEREJUCGIiAigQhARkQAVgoiIACoEEREJ+D8v+/bOK26ldAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYAAAAEGCAYAAABsLkJ6AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjAsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+17YcXAAAgAElEQVR4nO3dd3yV5f3/8dcnkzCDEBAJEBCQkUCQCFrbSu2vlqpYtXytVls37kq1omjdWlGraK1ocWK14qpfrbXDWqzjKyPsvYdRhLBnyLp+f1wHjAxJSM59n/F+Ph55cK4798n9zgHuz7nH+VzmnENERJJPStgBREQkHCoAIiJJSgVARCRJqQCIiCQpFQARkSSVFnaAumjdurXLy8sLO4aISFyZOnXqOudczt7L46oA5OXlUVxcHHYMEZG4YmYr97dcp4BERJKUCoCISJJSARARSVJxdQ1gfyoqKigpKaGsrCzsKHGrUaNG5Obmkp6eHnYUEQlQ3BeAkpISmjVrRl5eHmYWdpy445xj/fr1lJSU0Llz57DjiEiA4v4UUFlZGa1atdLO/xCZGa1atdIRlEgSivsCAGjnX096/URiXFV03qAlRAEQEUlYG6bC211hzYQG/9EqAFE2fPhwPvzww0N67uTJkyksLKSwsJC+ffvy5ptv7vnepk2bGDp0KD169KBnz558+umne7732GOP0aNHD3r37s2IESMAmD17NhdccEG9fhcRCdiWhTBhMOz8HJaNa/AfH/cXgWPZ+vXrmThxIo888sghPT8/P5/i4mLS0tJYvXo1ffv2ZciQIaSlpXHttdcyePBgXn/9dcrLy9mxYwcAEyZM4K233mLmzJlkZmaydu1aAAoKCigpKWHVqlV07NixwX5HEYmS7Z/Bf34Au9ZBu8EwYGyDb0JHAPW0YsUKevbsyaWXXkrv3r056aST2LlzJwBvvPEGgwcP3rNuXl4eI0aMoKCggAEDBrBkyZJv/NmNGzcmLc3X6LKysj3n6jdv3syHH37IxRdfDEBGRgbZ2dkAPPHEE9x0001kZmYC0KZNmz0/b8iQIYwfP76BfnMRiZqydTDhJNjxGbT+FnznDUjNaPDNJFYB+LNF5+sgFi9ezFVXXcXcuXPJzs7mjTfeAOCTTz6hf//+X1u3RYsWzJ49m6uvvprhw4cf9GdPmjSJ3r17U1BQwJNPPklaWhrLly8nJyeHCy+8kH79+nHJJZewfft2ABYtWsRHH33EwIEDOeGEE5gyZcqen1VUVMRHH31Ul1dURIJWsRU+OBm2LIAW+TDoHUhrHJVNBVYAzCzVzKab2TuRcWczm2RmS8zsFTNr+PIWkM6dO1NYWAhA//79WbFiBQCrV68mJ+frDfjOOeecPX/WPG9/IAMHDmTu3LlMmTKF++67j7KyMiorK5k2bRpXXHEF06dPp0mTJowaNQqAyspKNmzYwMSJE3nwwQc566yz2D3vc5s2bfjiiy8a6tcWkYZWtQs+PAM2TIEmneF7/4SMllHbXJDXAK4F5gPNI+P7gdHOufFm9iRwMfBEvbbws3AmuN99ugUgNTV1zymgrKysfe6vr3nLZV1uv+zZsydNmzZlzpw55Obmkpuby8CBAwEYOnTongKQm5vLmWeeiZkxYMAAUlJSWLduHTk5OZSVlZGVlXXIv6eIRFF1FfzfubDmfWjUFk78FzQ+IqqbDOQIwMxygVOApyNjA04EXo+sMg44PYgsQerZs+c+5/lfeeWVPX8ed9xxALz55puMHDlyn+cvX76cyspKAFauXMmCBQvIy8vj8MMPp0OHDixcuBCA999/n169egFw+umnM2GCv11s0aJFlJeX07p16z3j/Pz8KPymIlIvzsGUK+CzNyC9hX/n36xr1Dcb1BHAI8AIoFlk3ArY5JyrjIxLgPb7e6KZDQOGAXF398opp5zCH//4Ry655JI9yzZu3EifPn3IzMzk5ZdfBmDp0qU0b958n+d//PHHjBo1ivT0dFJSUhgzZsyenfljjz3GueeeS3l5OV26dOG5554D4KKLLuKiiy4iPz+fjIwMxo0bt+dIY8KECZxyyinR/rVFpK5m3gxLn4LURnDCO9CybzDbdc5F9Qs4FRgTeTwIeAdoDSypsU4HYM7Bflb//v3d3ubNm7fPslhy/PHHu40bNzrnnOvUqZMrLS3dZ51zzz3XrV27Nqo5ysrK3MCBA11FRcV+vx/rr6NIwpr3oHMv4dyfU50reScqmwCK3X72qUEcARwPnGZmJwON8NcAHgWyzSzN+aOAXODzALIE7qGHHmLVqlV7btPcnxdffDHqOVatWsWoUaP23FYqIjFg6XMw/Qb/+NjnoX2wR+hR3xs450YCIwHMbBDwa+fcuWb2GjAUGA+cD7wV7Sxh2H2hFthzd1AYunXrRrdu3ULbvojs5bP/hcmR08P9H4XO5wUeIczPAdwIXGdmS/DXBJ451B/kXDh3/yQKvX4iAVvzAXxyNrhqyL8NjvplKDECPR/gnPsA+CDyeBkwoL4/s1GjRqxfv14toQ+Ri8wH0KhRo7CjiCSHDVPhv6dB9S7odiUU3BFalLg/IZybm0tJSQmlpaVhR4lbu2cEE5Eo293crXIrdDobih6DEN+4xn0BSE9P10xWIhL7dpTAf076qrnbsePAwu3Gk1i9gEREYlHZOr/z37EKWh8H33k9Ks3d6koFQEQkmvY0d5vvm7ud8A6kNQk7FaACICISPVW74KMzI83d8nyLh8zDwk61hwqAiEg0VFfB/50HX/4bGrWBE9+LenO3ulIBEBFpaHuau70O6c0Da+5WVyoAIiINbeYtezV3Kww70X6pAIiINKT5D8G8+8BS4duvQZvvhJ3ogFQAREQayrLnYfqv/eNjn4P2p4Ya52BUAEREGkLJWzAp0tzt6Eeg88/DzVMLKgAiIvW15gP4+KfgqiD/VuhxbdiJakUFQESkPjZMq9Hc7QoouDPsRLWmAiAicqi2LPqquVvHn0L/cJu71ZUKgIjIodhRAv/5AewqhcNPguNegJTUsFPViQqAiEhd7Vr/VXO3VsfCd/8SE83d6koFQESkLiq21Wju1hsG/S1mmrvVlQqAiEhtVe2Cj86A9ZNjsrlbXakAiIjUxt7N3b73L2jcPuxU9aICICJyMM5B8ZVfNXcb9A9o3i3sVPWmAiAicjCzfgNLxkaau/0VDusXdqIGEfUCYGaNzGyymc00s7lmdmdk+fNmttzMZkS+YrNdnogkt/kPw9zf+uZux78Kbb4bdqIGE8Sk8LuAE51z28wsHfjYzP4e+d4NzrnXA8ggIlJ3y56H6df7xwOfhdwhocZpaFEvAM45B2yLDNMjXy7a2xURqZevNXcbDV1+EW6eKAjkGoCZpZrZDGAt8J5zblLkW/ea2SwzG21mmQd47jAzKzaz4tLS0iDiikiyW/Pfr5q79b4FegwPO1FUBFIAnHNVzrlCIBcYYGb5wEigB3AMcBhw4wGeO9Y5V+ScK8rJyQkirogksw3T4L9DfHO3rpdDn7vDThQ1gd4F5JzbBEwABjvnVjtvF/AcMCDILCIi+/hac7ezoOgPcdXcra6CuAsox8yyI4+zgB8AC8ysXWSZAacDc6KdRUTkgLav3Ku525/irrlbXQVxF1A7YJyZpeILzqvOuXfM7D9mlgMYMAO4PIAsIiL7KvkrTDwfyjf65m7feSMum7vVVRB3Ac0C9vnUhHPuxGhvW0TkG1WVw8yRsOBhPz7iZPjWi5DeNNxcAQniCEBEJPZsWwGf/NQ3drM0KLwPelwHljwNElQARCT5fPa/MPFCqNgEjTvC8eMh57iwUwVOBUBEkkfVLpg+Ahb93o/bD4Fjn4/rls71oQIgIslh2zL4+CzYMNWf8un3ABw1PKFv8zwYFQARSXyrXodJF0PFFmjSCY5/BVoPDDtV6FQARCRxVZXBtOth8Rg/zj0djn0WMlqGmytGqACISGLastjf5bNxOqSkQ7/fQfdrkvqUz95UAEQk8awYD5OH+ZYOTbv4Uz6tisJOFXNUAEQkcVTuhGm/giV/9OMOQ2Hg05DRItxcMUoFQEQSw5aF/i6fTbMgJcP38O92hU75fAMVABGJf8tfgimXQeV2aNoVvv1qwszbG00qACISvyp3wNRfwtJn/LjT2TDgj5DePNxccUIFQETi0+b5/pTP5jmQkglFv4cjL9UpnzpQARCR+LPsBZhyBVTtgGbd4duvQcs+YaeKOyoAIhI/KrdD8dWw7Hk/zjsPjnkiado3NzQVABGJD5vmwidnweZ5kJrlp2vscqFO+dSDCoCIxDbnYNlz/p1/1U5o3sOf8snODztZ3FMBEJHYVbHNn+tf8aIfdz4fjnkc0pqEmytBqACISGzaOMuf8tmyEFIb+x1/lwvCTpVQVABEJLY4B0ufgqnX+m6eLXr7D3a16BV2soSjAiAisaNiC0y+DFaO9+MuF0HRY5DWONxcCUoFQERiw4bp/oNd25b4c/zHPAmdzws7VUJLifYGzKyRmU02s5lmNtfM7ows72xmk8xsiZm9YmYZ0c4iIjHIOVj8BPzrOL/zzy6AHxZr5x+AqBcAYBdwonOuL1AIDDazY4H7gdHOua7ARuDiALKISCwp3+wnbZlyJVTvgq7D4KRJ0KJH2MmSQtQLgPO2RYbpkS8HnAi8Hlk+Djg92llEJIZsmAr/OBpWvQZpTeFbL/tGbmlZYSdLGkEcAWBmqWY2A1gLvAcsBTY55yojq5QA7Q/w3GFmVmxmxaWlpUHEFZFocg4WPgb/+hZsWwYtC2HwNMg7O+xkSSeQAuCcq3LOFQK5wACg1sd3zrmxzrki51xRTk5O1DKKSAC2LIIJP/QtnKvLoduVcNKn0Lxb2MmSUqB3ATnnNpnZBOA4INvM0iJHAbnA50FmEZEAVe6EeffBvPv9jj+jpT/d0/F/wk6W1IK4CyjHzLIjj7OAHwDzgQnA0Mhq5wNvRTuLiITg83fhb71hzt1+59/lIjh1oXb+MSCII4B2wDgzS8UXnFedc++Y2TxgvJndA0wHngkgi4gEZfsqmDocSt704+wC37o55/hwc8keUS8AzrlZwD6TczrnluGvB4hIIqmugAWjYfadfsKWtKZQcCccdQ2kpIedTmrQJ4FFpOGs/dB379w8z487/g8c/TA0zg03l+yXCoCI1F/ZWph+Ayx/wY+bdvUTthzxw3BzyTdSARCRQ1ddBUvHwoyboWKTn5y990jodSOkNgo7nRyECoCIHJr1xf50z4ZiP273Q/+uv1nXcHNJrakAiEjdlG+Cmbf4Bm44yGoP/R+FDmdqft44owIgIrXjHKx4CaZf78/5Wyr0+BXk3wbpzcJOJ4dABUBEDm7zPN+xc+1//Tjn23DMGH9vv8QtFQARObDK7f4TvPMfAlcJma2h34PQ+RdggbQSkyhSARCRfTkHJW/5eXl3rAIMul4GfX8LmYeFnU4aiAqAiHzdtuVQfA188Tc/btnPt3BoPTDcXNLgVABExKvaBfN/B3PvgaoySG8Ofe6BbldAinYViUh/qyICX/4bplwFWxf5caefwdG/g6x24eaSqFIBEElmO1fDtOtg5Xg/bn4UFI2Bw08MN5cEQgVAJBlVV8LiMTDzN1C5FVKzIP9W6HE9pGaEnU4CogIgkmzWTfQtHDbO8OP2Q6D/76FpXqixJHgqACLJYtd6mDESlj7lx006+R1/7mnh5pLQqACIJDpXDcuehxkjfBFISYcev4b8WyCtSdjpJEQqACKJbOMsKL4SSj/x47bfg6LHoUXPcHNJTFABEElEZWth9l2w5ElwVdCorZ+Zq9M56tgpe6gAiCSSim2w4GGY/yBUbvP9erpfDX3uhozssNNJjFEBEEkE1RWw9BmYfQeUrfHLjjgVCu+D7PxQo0nsino7PzPrYGYTzGyemc01s2sjy+8ws8/NbEbk6+RoZxFJOM7BZ3+Bv+X7WzvL1kCrAfD9D2DQX7Xzl28UxBFAJXC9c26amTUDpprZe5HvjXbO/S6ADCKJZ+3H/s6edZ/6cdOuUPhb6DBU5/mlVqJeAJxzq4HVkcdbzWw+0D7a2xVJWJvnw4yb4PO3/TgzBwrugK6X+ls8RWrpoKeAzOxHZjbJzBaa2atmdtyhbszM8oB+wKTIoqvNbJaZPWtmLQ/154okhR1fwKRL4d18v/NPawL5t8NpS6H7ldr5S53V5hrAGOA64FhgLPCgmZ1T1w2ZWVPgDWC4c24L8ARwJFCIP0J46ADPG2ZmxWZWXFpaWtfNisS/8s1+Eva/doWlTwPmWzQPWQJ97tB8vHLIzDn3zSuYTXLODawxbgJMcs7V+uqSmaUD7wD/dM49vJ/v5wHvHOxnFhUVueLi4tpuViS+VZXD4idg7t3+E7wAHX4Cfe/1XTtFasnMpjrnivZeXptrAMvN7B7gLudcOVCBv7Bb2w0b8Awwv+bO38zaRa4PAJwBzKntzxRJaK4aVr7i3/VvX+6X5XwbCh+AnEM+Ayuyj9oUgGr8DvpSM1sMdAT+YmbdnHOLa/H844GfA7PNLNJ+kJuBc8ysEHDACuCyuoYXSThfvg8zboQNU/24RS/oOwran6o7e6TBHbQAOOd+BmBmmUA+0Dfy9ZSZdXHOdTzI8z8G9vcv9926xxVJUBtn+h3/6n/6cdYR0Ocu6Hy+pmOUqKn1vyzn3C5gauRLRBrC9pUw6zZY/ifA+Xl4e90IRw2HtMZhp5MEp7cWImHYtQHm/hYW/QGqd/lbOLtdCb1/A41ah51OkoQKgEiQqspg4WN+51+xyS/rdA70vQeadgk3myQdFQCRIFRXwYoXYdatsOMzv6zt96Hf/XBY/3CzSdJSARCJJudg9T/8Bd5Ns/2y7L5QeD+0O0l39kioVABEomV9sW/WtmaCHzfu6E/15J3r+/SLhEwFQKShbV3qP8S16hU/zmgJvW+B7ldBaqNws4nUoAIg0lDKSmHO3X4axuoKSMmEo66F3jf5IiASY1QAROqrcjssGA3zHoDKrYBBlwug4C5o0iHsdCIHpAIgcqiqymDxkzDvPj8JO8ARJ0PhKMguCDebSC2oAIjUVVU5LHsG5twDO7/wy1oN9Dv+toNCjSZSFyoAIrVVXQHLX/Dn+bev9Mta9vM9e444Rbd0StxRARA5mOoqWPkyzL4Tti3xy1r09jv+3NN1S6fELRUAkQNx1fDZGzDrdtgy3y9r1t3Pv9vxLEhJDTWeSH2pAIjszTk/5+6s22DTLL+sSR4U3A5556k9syQM/UsW2c05349/1q2wITL1aONc36Gzy4WQmhFuPpEGpgIgAr5dw6xbofQTP27UFnrfDF2H6dO7krBUACS5lX7id/y7+/VktoJeN/ne/JqQRRKcCoAkp/XFfse/+h9+nJ4NPX8NR/0S0puFm00kICoAklw2zoLZt0HJW36c1hR6/Ap6XAcZ2eFmEwmYCoAkh83zYfbtsOo1P07Ngu7XQM8bNAWjJC0VAElsW5f4D3Ct/LO/rz8lE7pd7s/zZx0edjqRUEW9AJhZB+AFoC3ggLHOuUfN7DDgFSAPWAGc5ZzbGO08kiS2r/QtG5Y9D67KT7p+5DDIv8Xf2ikigRwBVALXO+emmVkzYKqZvQdcALzvnBtlZjcBNwE3BpBHEtmOz/2E60uf8r17LNXfw59/KzTtHHY6kZgS9QLgnFsNrI483mpm84H2wI+BQZHVxgEfoAIgh6psLcwdBYvHQPUuwKDTz/ynd5t3DzudSEwK9BqAmeUB/YBJQNtIcQD4En+KaH/PGQYMA+jYsWP0Q0p82bUe5j8ICx+Dqh1+WYehvl9Pdu9Qo4nEusAKgJk1Bd4AhjvntliN1rnOOWdmbn/Pc86NBcYCFBUV7XcdSULlm/wsXAtGR2bhAtoP8R06WxaGm00kTgRSAMwsHb/zf8k595fI4jVm1s45t9rM2gFrg8gica5iGyz6Pcx7ECo2+WWHnwR97obWA8LNJhJngrgLyIBngPnOuYdrfOtt4HxgVOTPt6KdReJY5Q5Y/ATMGwW71vllbU7wO/423wk3m0icCuII4Hjg58BsM5sRWXYzfsf/qpldDKwEzgogi8SbqjJYMhbm3gdlX/plrY/zO/62J2oWLpF6COIuoI+BA/0v/X60ty9xqqoclj0Lc++FHSV+2WH9oeAuOOJH2vGLNAB9ElhiS3VljXl3V/hl2QV+x5/7Y+34RRqQCoDEhv3Nu9u8BxTcCR2Hat5dkShQAZBw7W/e3aZd/Qe4Op2jeXdFokgFQMKx33l3O0H+bdD5F5p3VyQA+l8mwXLOT8Iy67av5t3Nag/5v4EuF2neXZEAqQBIMJyDNf/xs3Ct+9Qv07y7IqFSAZDoW/uR3/Gv/a8fZ7aGXjdq3l2RkKkASPSsm+R3/F++58fp2dDrBj8Tl+bdFQmdCoA0vA3T/Dn+L/7mx+nN4ahf+bl3M1qEm01E9lABkIazaba/nbPkTT9OawLdfwk9fw2Zh4WbTUT2oQIg9bd5Acy+A1a9Cjh/QbfbVdBrBDRqE3Y6ETkAFQA5dFuXwOy7YOVLkQnXM6DrZdB7JGS1CzudiByECoDU3d4TrlsadL0Uet8CTTqEnU5EakkFQGpvx+e+O+fSpzXhukgCUAGQg9v5pZ+IZfGTX024nncu5N8OzbuFnU5EDpEKgBxY2TqY/wAs+gNU7fTLOv6Pn3C9Ra9Qo4lI/akAyL7KN8H838HCR6Fym1+W+2Pfmrll33CziUiDUQGQr1SVwaLH/Xn+8o1+WbsfQZ+7oFVRuNlEpMGpAIi/hXPFSzDzN7BjlV/WZhD0vRdyvhVqNBGJHhWAZLf6XzB9BGya6cfZBVB4P7QbrOkXRRKcCkCy2jAdZoyAL//tx41zoc/dkPdzzcIlkiRUAJLNtuX+VM/KP/txegvfk7/7NZCWFW42EQlU1AuAmT0LnAqsdc7lR5bdAVwKlEZWu9k59260syS1Xethzr2w+HGoLvdtG7pf7Xf+ma3CTiciIQjiCOB54A/AC3stH+2c+10A209ulTv97ZzzRkHFZvyHuM7zp3ua5oWdTkRCFPUC4Jz70Mzyor0d2Ut1FSx/AWbfBjtK/LLDT4J+90PLwnCziUhMCPMawNVm9gugGLjeObdxfyuZ2TBgGEDHjh0DjBennIMv3oUZN8HmOX5Zy36RO3t+EG42EYkpKSFt9wngSKAQWA08dKAVnXNjnXNFzrminJycoPLFp3WT4f3vwX9P9Tv/Jp3guBdhcLF2/iKyj1COAJxza3Y/NrOngHfCyJEwti6FmTdHJmQBMg7zrZm7XwWpmeFmE5GYFUoBMLN2zrnVkeEZwJwwcsS9srW+L//iJ8FV+pm4jroWet0EGdlhpxORGBfEbaAvA4OA1mZWAtwODDKzQsABK4DLop0joVRuhwWjYd4DULkVMN+Xv+BOTcgiIrUWxF1A5+xn8TPR3m5Cqq6EZc/6+Xd3Rg6gjjgFCkdBdn6o0UQk/uiTwPHAOfj8bX9nz5YFftlhx0C/B6DtoFCjiUj8UgGIdaWfwowboPQTP256JPT9rZ+YRc3aRKQeVABi1ZaFMGMklLzpx5mtIf826HoZpGaEm01EEoIKQKzZ+SXMvhOWPgWuClIbQ4/roNcNkN487HQikkBUAGJFxVY/DeOCh/xdPpYKXYf5+Xez2oWdTkQSkApA2KorYMlTMOdOf18/QO7p0Pc+aNEj3GwiktBUAMJU8leYfj1sXezHrY+Dfg9CzvHh5hKRpKACEIada2DqNbDqNT9u1t3fy597uu7sEZHAqAAEyTlYPg6mXQflGyGtCfS5F7pfCSnpYacTkSSjAhCUbctg8mVfzcHbbjAMeNJ37BQRCYEKQLRVV/kZuWbdClU7/PSLRz8CeefqdI+IhEoFIJo2zoJJl8CGKX7c6WfQ/xFopHkNRCR8KgDRUFUGc+6Beff7Ns2NO8AxT0D7U8JOJiKyhwpAQ1v7MUy+NNK0zaDbVVB4H6Q3CzuZiMjXqAA0lIotvnfP4jF+3LwHDHxa9/SLSMxSAWgIn78DU66AHSVgadB7pJ+SUdMxikgMUwGoj7K1MPVaWDnej1sN8O/6swvCzSUiUgsqAIfCOVjxIkwdDuUbfMfOvvdC92sgJTXsdCIitaICUFfbVsCUy2H1P/348B/AgD9C086hxhIRqSsVgNqqroJFf4BZt/h2zRkt4ejR0PkX+kCXiMQlFYDa2DQXJl0M6yf5ccefQv9HIattuLlEROohJdobMLNnzWytmc2psewwM3vPzBZH/mwZ7RyHpGoXzLod/tHP7/yz2sN334Jvj9fOX0TiXtQLAPA8MHivZTcB7zvnugHvR8axpfRT+Hs/mHOXn7Sl6+VwylzIPS3sZCIiDSLqp4Cccx+aWd5ei38MDIo8Hgd8ANwY7Sy1UrEVZt7iz/fjfK/+gU9Bm++GnUxEpEGFdQ2grXNudeTxl8ABz6eY2TBgGEDHjh2jm+qLv8Pky2HHKv+Brl4jIP9WSG0U3e2KiIQg9IvAzjlnZu4bvj8WGAtQVFR0wPXqpWwdTBsOK17y48P6w8BnoGXfqGxORCQWhFUA1phZO+fcajNrB6wNJYVzsPJl/2neXesgNQv63A1HXQspoddGEZGoCmsv9zZwPjAq8udbgSfYvsr37/niXT9ueyIMGAvNjgw8iohIGKJeAMzsZfwF39ZmVgLcjt/xv2pmFwMrgbOinWMPVw2LxsDMkVC5DdKz4eiHoMuF+kCXiCSVIO4COucA3/p+tLe9j83z/Axd6z714w5DoegxyDo88CgiImFLjhPdVeUwbxTMvReqyyGrHRQ9Dh3OCDuZiEhoEr8AVGyFf30LNkc+iHzkpdDvAcjIDjeXiEjIEr8ApDfz/fmryvwHutoOCjuRiEhMSPwCAHDMGEjJhLSssJOIiMSM5CgAOt0jIrKPIJrBiYhIDFIBEBFJUioAIiJJSgVARCRJqQCIiCQpFQARkSSlAiAikqTMuejMsRINZlaK7x56KFoD6xowTkNRrrpRrrpRrrqJ1VxQv2ydnHM5ey+MqwJQH2ZW7JwrCjvH3pSrbpSrbpSrbmI1F0Qnm04BiYgkKRUAEZEklUwFYGzYAQ5AuepGuepGueomVlpJ6dgAAASVSURBVHNBFLIlzTUAERH5umQ6AhARkRpUAEREklTCFQAzG2xmC81siZndtJ/vf9fMpplZpZkNjaFc15nZPDObZWbvm1mnGMl1uZnNNrMZZvaxmfWKhVw11vuJmTkzC+TWvVq8XheYWWnk9ZphZpfEQq7IOmdF/o3NNbM/x0IuMxtd47VaZGabYiRXRzObYGbTI/8nT46RXJ0i+4dZZvaBmeXWa4POuYT5AlKBpUAXIAOYCfTaa508oA/wAjA0hnJ9D2gceXwF8EqM5Gpe4/FpwD9iIVdkvWbAh8BEoCgWcgEXAH8I4t9VHXN1A6YDLSPjNrGQa6/1rwGejYVc+AuuV0Qe9wJWxEiu14DzI49PBP5Un20m2hHAAGCJc26Zc64cGA/8uOYKzrkVzrlZQHWM5ZrgnNsRGU4E6lfZGy7XlhrDJkAQdw0cNFfE3cD9QFkAmeqSK2i1yXUp8LhzbiOAc25tjOSq6Rzg5RjJ5YDmkcctgC9iJFcv4D+RxxP28/06SbQC0B74rMa4JLIsbHXNdTHw96gm8mqVy8yuMrOlwAPAL2Mhl5kdDXRwzv0tgDy1zhXxk8gh+utm1iFGcnUHupvZJ2Y20cwGx0guwJ/aADrz1c4t7Fx3AOeZWQnwLv7oJBZyzQTOjDw+A2hmZq0OdYOJVgDinpmdBxQBD4adZTfn3OPOuSOBG4HfhJ3HzFKAh4Hrw86yH38F8pxzfYD3gHEh59ktDX8aaBD+nfZTZhZLk2WfDbzunKsKO0jEOcDzzrlc4GTgT5F/d2H7NXCCmU0HTgA+Bw75NYuFX6ghfQ7UfMeVG1kWtlrlMrP/B9wCnOac2xUruWoYD5we1UTewXI1A/KBD8xsBXAs8HYAF4IP+no559bX+Lt7Gugf5Uy1yoV/N/m2c67CObccWIQvCGHn2u1sgjn9A7XLdTHwKoBz7lOgEb4ZW6i5nHNfOOfOdM71w+8rcM4d+oXzaF/YCPIL/y5nGf5QcvdFlN4HWPd5grsIfNBcQD/8BaBusfR61cwDDAGKYyHXXut/QDAXgWvzerWr8fgMYGKM5BoMjIs8bo0/1dAq7FyR9XoAK4h8MDVGXq+/AxdEHvfEXwOIar5a5moNpEQe3wvcVa9tBvGCB/mFP1xbFNmZ3hJZdhf+XTXAMfh3Q9uB9cDcGMn1b2ANMCPy9XaM5HoUmBvJNOGbdsRB5tpr3UAKQC1fr/sir9fMyOvVI0ZyGf602TxgNnB2LOSKjO8ARgWRpw6vVy/gk8jf4wzgpBjJNRRYHFnnaSCzPttTKwgRkSSVaNcARESkllQARESSlAqAiEiSUgEQEUlSKgAiIklKBUBEJEmpAIiIJCkVAJF6MrO/mNk9Zvahma2KtPQQiXkqACL1VwBscs59F7gWODfkPCK1ogIgUg9m1hjfL350ZFE6EMisViL1pQIgUj+9gKnuqzbGfYA5IeYRqTUVAJH6KcA3C9utDzArpCwidaICIFI/exeAfHQEIHFC3UBFRJKUjgBERJKUCoCISJJSARARSVIqACIiSUoFQEQkSakAiIgkKRUAEZEk9f8BRQTr5dAFQAgAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "from numpy import arange, exp, log, sqrt\n",
    "%matplotlib inline\n",
    "import matplotlib.pyplot as pplt\n",
    "\n",
    "d = 366\n",
    "n = arange(1,40)\n",
    "p = 1 - exp(-n*(n-1)/(2*d))\n",
    "\n",
    "pplt.plot(n, p, linewidth=2, label='p(n, {0})'.format(d))\n",
    "pplt.xlabel('$n$')\n",
    "pplt.ylabel('$p$')\n",
    "pplt.legend()\n",
    "pplt.show()\n",
    "\n",
    "p = arange(.1,1,.1)\n",
    "n = sqrt(2*d*log(1/(1-p)))\n",
    "pplt.plot(p, n, linewidth=2, label='n(p, {0})'.format(d), color='orange')\n",
    "pplt.xlabel('$n$')\n",
    "pplt.ylabel('$p$')\n",
    "pplt.legend()\n",
    "pplt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise**: verify these equations hold in probability by repeated experiments.\n",
    "\n",
    "**Exercise**: How many random digests would you need to compute to find a collision in MD5 with a probability of $1/2$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Passwords\n",
    "Hash functions are routinely used to store passwords, for several reasons - one of them being that if a company's database is stolen, user passwords should not be instantly compromised. For this use case, preimage resistance is a crucial property.\n",
    "\n",
    "**Example**: suppose a company's user database has been stolen and published, with each entry containing username, IP address, email address, and hashed password. Suppose one specific password $x$ hashes to the following string, under SHA-256:\n",
    "> $H(x)=$'7902699be42c8a8e46fbbb4501726517e86b22c56a189f7625a6da49081b2451'\n",
    "\n",
    "It should be infeasible for you to guess what $x$ is, assuming:\n",
    "1. SHA-256 is a cryptographic hash function, as per the definitions above; and\n",
    "2. there is a high uncertainty in the possible choice of password $x$.\n",
    "\n",
    "The second requirement is due to hash functions being deterministic: there is no uncertainty in the result of the computation $h=H(x)$.\n",
    "\n",
    "## Dictionary attack\n",
    "\n",
    "In some cases, it is possible to do better than a brute force attack because the space of all *plausible* input is much smaller than the space of all *possible* input. This is known as a *dictionary attack*.\n",
    "\n",
    "Suppose I also told you that the string $x$ is composed of a single digit number. There would be 10 possible different values of $x$ - in other words, the size of the message space would be $\\#\\mathcal{M}=10$ - and even without knowing $x$ it would take very little time and effort to recover $x$ by brute force, like so:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "SHA-256('0') = 5feceb66ffc86f38d952786c6d696c79c2dbc239dd4e91b46729d73a27fb57e9\n",
      "SHA-256('1') = 6b86b273ff34fce19d6b804eff5a3f5747ada4eaa22f1d49c01e52ddb7875b4b\n",
      "SHA-256('2') = d4735e3a265e16eee03f59718b9b5d03019c07d8b6c51f90da3a666eec13ab35\n",
      "SHA-256('3') = 4e07408562bedb8b60ce05c1decfe3ad16b72230967de01f640b7e4729b49fce\n",
      "SHA-256('4') = 4b227777d4dd1fc61c6f884f48641d02b4d121d3fd328cb08b5531fcacdabf8a\n",
      "SHA-256('5') = ef2d127de37b942baad06145e54b0c619a1f22327b2ebbcfbec78f5564afe39d\n",
      "SHA-256('6') = e7f6c011776e8db7cd330b54174fd76f7d0216b612387a5ffcfb81e6f0919683\n",
      "SHA-256('7') = 7902699be42c8a8e46fbbb4501726517e86b22c56a189f7625a6da49081b2451\n",
      "SHA-256('8') = 2c624232cdd221771294dfbb310aca000a0df6ac8b66b696d90ef06fdefb64a3\n",
      "SHA-256('9') = 19581e27de7ced00ff1ce50b2047e7a567c76b1cbaebabe5ef03f7c3017bb5b7\n"
     ]
    }
   ],
   "source": [
    "for x in range(10):\n",
    "    digest = hashes.Hash(hashes.SHA256(), backend=default_backend())\n",
    "    digest.update(str(x).encode())\n",
    "    h = digest.finalize().hex()\n",
    "    print('''SHA-256('{0}') = {1}'''.format(x, h))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This can lead to what is known as a *brute force* attack: it is possible, in principle, to exhaustively enumerate $H(x)$ for every $x$, store these values in a table, and then given a hash value $h$ to search the table for some message $m$ whose digest will be $H(m)=x$. The constraints are:\n",
    "1. Time and cost required to compute all possible hashes\n",
    "2. Space and cost required to store all possible digests\n",
    "\n",
    "**Example**: the space of all possible English letters (upper-and lower-case) is of size $\\#L=2\\cdot26$. Suppose it takes 1ms to compute a single SHA-256 hash. A message drawn uniformly at random from the space of 8-letter passwords forces a brute-force adversary to expend the following resources:\n",
    "\n",
    "Total number of possibilities | Storage memory required (terabytes) | Time to compute (years)\n",
    "--- | --- | ---\n",
    "$n=(2\\cdot26)^8$ | $n\\cdot(256 + 8\\cdot 8)/(8\\cdot10^{12}) $  | $n/(1000\\cdot60\\cdot60\\cdot24\\cdot356)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "possibilities: 53459728531456\n",
      "memory: 2138.38914125824 Tb\n",
      "time to compute: 1695.1968712409944 years\n"
     ]
    }
   ],
   "source": [
    "n = (2*26)**8\n",
    "memory = n*(256+64)/(8*10**12)\n",
    "time = n/(1000*60*60*24*365)\n",
    "print('possibilities: {0}'.format(n))\n",
    "print('memory: {0} Tb'.format(memory))\n",
    "print('time to compute: {0} years'.format(time))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise**: Can you see where the storage requirement computation comes from?\n",
    "\n",
    "The possibilities also need to be stored so that we can look up the password from the hash. For each possibility we need to store both the 64-bit password and the 256-bit hash.\n",
    "\n",
    "**Exercise**: compute the SHA-256 hash of the top 10 [most common passwords](https://en.wikipedia.org/wiki/List_of_the_most_common_passwords) of 2019. Is '8bb0cf6eb9b17d0f7d22b456f121257dc1254e1f01665370476383ea776df414' one of them?\n",
    "\n",
    "**Exercise**: the number of all existing English words, of any length, is somewhere near $6\\cdot 10^5$ - see e.g. [wolfram|alpha](https://www.wolframalpha.com/input/?i=number+of+words+in+english). Assume that the most frequent word is as likely to be used as a password as the most infrequent one, and compute the following values:\n",
    "\n",
    "Total number of possibilities | Total storage memory required (megabytes) | Time to compute (seconds)\n",
    "--- | --- | ---\n",
    "$6\\cdot10^5$ | ? | ?\n",
    "\n",
    "It is possible in theory to pre-compute every single $h=H(x)$ for all $x$, if the message space or the digest space is small enough, to build a lookup table: each entry in the table associates the key-value pair $h,x$ so anyone with the table can look up a value of $x$, given a key $h$. It can be an expensive process, but only needs to be done once.\n",
    "\n",
    "**Exercise**: compute the MD5 and/or SHA1 hash of a password and see if it has already been pre-computed and uploaded to an online database, for instance [isc.sans.edu/tools/reversehash](https://isc.sans.edu/tools/reversehash.html)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Rainbow tables\n",
    "\n",
    "Computing brute force possibilities at runtime and looking up all pre-computed values are two extreme cases: in the former there is no storage but a random computational effort has to be expended every time; in the latter, a fixed computational effort is expended only once, and a maximal storage effort must be maintained. A *[rainbow table](https://en.wikipedia.org/wiki/Rainbow_table)* trades off storage of pre-computed values against runtime computational effort.\n",
    "\n",
    "Suppose we define some function $G$ mapping hash values back into passwords, and we construct a table by computing the chain of values\n",
    "\n",
    "$\n",
    "\\begin{align*}\n",
    "    p & \\in P_1 \\\\\n",
    "    h & = H(p) \\in H_1 \\\\\n",
    "    p' & = G(h) \\in P_2 \\\\\n",
    "    h' & = H(p')\\in H_2\n",
    "\\end{align*}\n",
    "$\n",
    "\n",
    "Suppose we make the rather unrealistic assumption that we can find a $G$ and the sets $P_1,P_2$ and $H_1, H_2$ are disjoint. *If* we could find such a $G$, and if we had the capacity to compute all of $P_2$ and to store a table mapping $P_1$ into $H_2$, then we could examine any new hash value $\\tilde{h}$ and conclude that one of the following is true:\n",
    "\n",
    "* $\\tilde{h}\\in H_2$, therefore we can compute the corresponding $p'$\n",
    "* $G(\\tilde{h}) \\in P_1$, therefore we have just computed the corresponding $p$\n",
    "* $\\tilde{h}$ is not the hash of a password in the space we initially considered.\n",
    "\n",
    "The storage requirement for this algorithm, $P_1,H_2,G$ is half that of the full pre-computed table $H,P$, and it only requires a single hash computation at runtime for every look-up."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Salted hash\n",
    "\n",
    "A common mitigation strategy against pre-computation is to add a random *salt* $s$ to every hash: password hashes are computed as $h=H(x,s)$, and stored in a database as pairs $(h,s)$.\n",
    "\n",
    "**Exercise**: Suppose passwords are chosen as a single random word in the English language and computed with MD5. What are the number of possibilities, storage requirements, and time to compute every possible $h$ in the two following scenarios:\n",
    "1. no salt\n",
    "2. a random 32-bit salt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linux user passwords\n",
    "\n",
    "The linux function used to hash passwords is `crypt(3)`. You can check the man page on your distribution, or see [here](http://manpages.ubuntu.com/manpages/disco/en/man3/crypt.3.html). As you can see, salting algorithms are specified by an `$id` variable, and salts are encoded as strings of *up to* 16 characters, taken from a set of 64 possible values each, namely `[a-zA-Z0-9./]`. To quote:\n",
    "\n",
    "> ID  | Method\n",
    "> --- | ---\n",
    "> 1   | MD5\n",
    "> 2a  | Blowfish (not in mainline glibc; added in some Linux distributions)\n",
    "> 5   | SHA-256 (since glibc 2.7)\n",
    "> 6   | SHA-512 (since glibc 2.7)\n",
    "\n",
    "However, note well: if no `id` is specified, the function defaults to a DES-based algorithm with a two-character salt. Note that [DES](https://en.wikipedia.org/wiki/Data_Encryption_Standard) is a block cipher with a 64-bit block size. If you have not seen block ciphers before, simply treat this as if it were a hash function with a 4-bit digest for the purposes of this exercise.\n",
    "\n",
    "Lastly, note that [OWASP recommend](https://github.com/OWASP/CheatSheetSeries/blob/master/cheatsheets/Password_Storage_Cheat_Sheet.md) that every password be salted with a 32- or 64-bit random number.\n",
    "\n",
    "**Exercise**: Compute the number of possibilities, memory, and time requirements in each of the following scenarios:\n",
    "0. DES with a 2-character salt\n",
    "1. MD5 with a 128-bit salt\n",
    "2. SHA-256 with a 256-bit salt\n",
    "\n",
    "**Exercise**: if you have access to a linux machine, one way to check how your account passwords are being created is by\n",
    "> `xed /etc/shadow`\n",
    "\n",
    "Note that you *should* need administrator privileges to access this file, for good reason. You can check the permissions on this file by\n",
    "> `ls -l /etc/shadow`\n",
    "\n",
    "and you should probably see something beginning with\n",
    "> `-rw-r----- 1 root shadow`\n",
    "\n",
    "meaning the file belongs to the `root` user with read and write access, and that anyone in the `shadow` group has read access.\n",
    "\n",
    "Once you do manage to open it, please *don't make any changes to this file* while looking!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Standards\n",
    "A list of approved hash functions is maintained by [NIST](https://csrc.nist.gov/Projects/Hash-Functions).\n",
    "\n",
    "We have discussed the principle and motivation for password hashing and salting. As you should have seen in the linux password case, it is not enough to simply generate a hash; we also need to specify which algorithm and parameters were used so that a verification function can be correctly executed. Each protocol will likely have its own requirements. For instance, the WPA wifi protocol uses the [PBKDF2](https://en.wikipedia.org/wiki/PBKDF2) (Password-Based Key Derivation Function; see NIST [SP 800-132](https://csrc.nist.gov/publications/detail/sp/800-132/final)) standard.\n",
    "\n",
    "Rather than implementing your own version of each password hash creation and verification algorithm, you will most likely want to make use of existing libraries such as [passlib](https://passlib.readthedocs.io/en/stable/)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Attack budget\n",
    "\n",
    "Note that an exhaustive search can always be parallelized across several machines, if you have enough money to spend on hardware and electricity. For instance, a [GeForce GTX 1080 Ti](https://www.nvidia.com/en-us/geforce/products/10series/geforce-gtx-1080-ti/) has a [reported](https://www.techspot.com/article/1438-ethereum-mining-gpu-benchmark/) hashrate of 31.3 MH/s. Since these are measured as double SHA-256 for mining purposes, let's count it as $62.6 \\cdot  10^6$ SHA-256 operations per second.\n",
    "\n",
    "**Exercise**: Suppose an adversary wants to crack a single password, knowing the 256-bit salt and the SHA-256 hash. Calculate how much time and money it costs to recover that one password using a single GTX card, in the worst case - i.e. ignore the probability that the computation will find a match long before every possible password has been tried. Make the following assumptions:\n",
    "* the cost of one card is about 600€\n",
    "* the card consumes a constant 180 W of power\n",
    "* the average electricity retail price of electricity is 0.10€ per kW$\\cdot$h\n",
    "* ignore any other equipment and cooling costs\n",
    "* the password to be recovered is a truly random string of 256 bits.\n",
    "\n",
    "**Exercise**: calculate the cost to parallelize the operation in the previous exercise such that the time taken in the worst case is less than 1 week.\n",
    "\n",
    "**Exercise**: repeat the calculation by changing the last assumption:\n",
    "* the password to be recovered is one of the $6\\cdot 10^5$ words in the English language.\n",
    "\n",
    "**Exercise**: How much would it cost to pre-compute all posible SHA-256 digests of every word in the English language with the every possible 32-bit salt appended to each one?\n",
    "\n",
    "Now, go to [haveibeenpwned.com](https://haveibeenpwned.com) and check when and how many times your hashed and salted passwords have been stolen from databases. Make a note of how long ago that happened, and see if you can find out what the hashing algorithm and the salt length were."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Advanced collision attacks\n",
    "\n",
    "You can find online a demo of a practical [MD5 collision attack](https://www.mscs.dal.ca/~selinger/md5collision/) to generate two different executables - one with malware, one without - and of a practical [SHA1 collision attack](http://shattered.io/) to generate two different pdfs with the same hash, which could be applied to create two versions of a signed contract.\n",
    "\n",
    "The examples above are specific to the hash function algorithm they were designed for."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Theme\n",
    "You can run the following cell to change the appearance of this notebook to suit your taste. Check for available themes on [github.com/dunovank/jupyter-themes](https://github.com/dunovank/jupyter-themes)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "ename": "IndexError",
     "evalue": "list index out of range",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mIndexError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-2-d348088c1268>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;32mfrom\u001b[0m \u001b[0mjupyterthemes\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mstylefx\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mset_nb_theme\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0mset_nb_theme\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'solarized'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m~/Documents/courses/Introduction to Computer and Network security/2019-20/github/i2cns-19/env/lib/python3.6/site-packages/jupyterthemes/stylefx.py\u001b[0m in \u001b[0;36mset_nb_theme\u001b[0;34m(name)\u001b[0m\n\u001b[1;32m    476\u001b[0m     \u001b[0;32mfrom\u001b[0m \u001b[0mIPython\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcore\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdisplay\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mHTML\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    477\u001b[0m     \u001b[0mstyles_dir\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mos\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpath\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mjoin\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mpackage_dir\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m'styles/compiled/'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 478\u001b[0;31m     \u001b[0mcss_path\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mglob\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'{0}/{1}.css'\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mstyles_dir\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mname\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    479\u001b[0m     \u001b[0mcustomcss\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mopen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcss_path\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m\"r\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mread\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    480\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mIndexError\u001b[0m: list index out of range"
     ]
    }
   ],
   "source": [
    "from jupyterthemes.stylefx import set_nb_theme\n",
    "set_nb_theme('solarized')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "l"
   ]
  }
 ],
 "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.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}