Hash Functions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Some Tests with Hash Functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from binascii import hexlify\n",
    "from os import urandom\n",
    "from hashlib import sha256, shake_128\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Example 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's hash an ASCII string with SHA256. Print the output will as a hexadecimal string"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = b\"test message\"\n",
    "y = sha256(x).hexdigest()\n",
    "y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Example 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider the hash SHAKE128 with output 16 bits. Generate a random digest and find a preimage. Print the number of attempts."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "DIGESTSIZE = 2\n",
    "\n",
    "# Define a hash function h with output size DIGESTSIZE bytes \n",
    "h = lambda x: shake_128(x).digest(DIGESTSIZE)\n",
    "\n",
    "# y is the target\n",
    "y = urandom(DIGESTSIZE)\n",
    "\n",
    "i = 0\n",
    "yp = None\n",
    "while (yp != y):\n",
    "    # Generate a random 64 bit input\n",
    "    xp = urandom(8)\n",
    "    yp = h(xp)\n",
    "    i = i + 1\n",
    "\n",
    "print(\"Attempt #{}\".format(i) )\n",
    "print(\"Preimage is {}\".format(hexlify(xp)) )    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Example 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Find, empirically, the average number of attempts to find a preimage to SHAKE128 with output 8 bits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "DIGESTSIZE = 1\n",
    "num_simulations = 1000\n",
    "h = lambda x: shake_128(x).digest(DIGESTSIZE)\n",
    "\n",
    "def simulate(y):\n",
    "    i = 0\n",
    "    yp = None\n",
    "    while (y != yp):\n",
    "        # Generate a random 64 bit input\n",
    "        xp = urandom(8)\n",
    "        yp = h(xp)\n",
    "        i = i + 1\n",
    "    return(i)        \n",
    "\n",
    "messages = [ urandom(DIGESTSIZE) for _ in range(num_simulations) ]\n",
    "simulations = [simulate(m) for m in messages]\n",
    "\n",
    "np.mean(simulations)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.hist(simulations,32);\n",
    "plt.xlabel('Number of attempts')\n",
    "plt.ylabel('Occurrences')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Example 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Find the empirical probability of finding a second preimage with $q=100$ attempts  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "DIGESTSIZE = 2\n",
    "# attempts\n",
    "q = 100\n",
    "# number of simulations\n",
    "num_simulations = 10000\n",
    "\n",
    "h = lambda x: shake_128(x).digest(DIGESTSIZE)\n",
    "\n",
    "def simulate(message,attempts):\n",
    "    y = h(message)\n",
    "    xp = [ urandom(8) for _ in range(attempts) ]\n",
    "    yp = [ h(x) for x in xp]\n",
    "    return ( y in yp )\n",
    "\n",
    "# generate many random messages\n",
    "messages = [urandom(8) for _ in range(num_simulations)]\n",
    "\n",
    "# simulate finding a second preimage\n",
    "simulations = [ simulate(m,q) for m in messages]\n",
    "\n",
    "# result\n",
    "p_succ = (sum(simulations)) / num_simulations\n",
    "p_theory = q / pow(2,DIGESTSIZE * 8)\n",
    "\n",
    "print(\"Simulations: p={}\".format(p_succ))\n",
    "print(\"Theory: p={}\".format(p_theory))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Example 5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Find the empirical probability of finding a collision with  q=30  attempts.\n",
    "Use a 16-bit hash function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "DIGESTSIZE = 2\n",
    "# attempts\n",
    "q = 30\n",
    "# number of simulations\n",
    "num_simulations = 10000\n",
    "\n",
    "h = lambda x: shake_128(x).digest(DIGESTSIZE)\n",
    "\n",
    "def simulate(attempts):\n",
    "    xp = [ urandom(8) for _ in range(attempts) ]\n",
    "    yp = [ h(x) for x in xp]\n",
    "    # remove unique items\n",
    "    ys = set(yp)\n",
    "    # if they are the same, there were no duplicates    \n",
    "    return (len(ys) != len(yp))\n",
    "\n",
    "# simulate finding a collision\n",
    "simulations = [ simulate(q) for _ in range(num_simulations)]\n",
    "# result\n",
    "p_succ = (sum(simulations)) / num_simulations\n",
    "p_theory = 1-np.exp(-q**2 / pow(2,DIGESTSIZE*8+1))\n",
    "\n",
    "print(\"Simulations: p={}\".format(p_succ))\n",
    "print(\"Theory: p={}\".format(p_theory))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lab Work\n",
    "\n",
    "Work in pairs. One is Alice, one is Bob.\n",
    "\n",
    "Use SHAKE128 with 8 bits output.\n",
    "\n",
    "Alice generates a random input and sends it to Bob. Bob finds a second preimage and sends it to Alice.\n",
    "Alice verifies that the second preimage is correct.\n",
    "\n",
    "How many attempts did Bob make?\n",
    "\n",
    "Now swap your roles and use SHAKE128 with 16 bits of output."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Challenge"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For this challenge use the hash function SHAKE128 with 1 byte of output. Your goal it to find a second preimage for the following input. Measure the time it takes, then increase the output size by one byte and repeat. Plot your measurements in a graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "input_string = b'The frog jumped into the pond'"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}