hashing_notebook.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## PV080 Seminar 07 - hash functions\n",
    "\n",
    "This notebook contains code for two tasks treated in this seminar:\n",
    "1. Brewing custom hash functions\n",
    "2. Use preimage attack to crack leaked database of passwords\n",
    "\n",
    "All necessary code resides here. The cell below contains some auxillary functions and is to be called only once. Scroll below for the relevant tasks.\n",
    "\n",
    "## Part 1: Custom hash functions\n",
    "\n",
    "Run the cell below once. \n",
    "In the cell below, some helper functions can be found regarding the first task. You don't have to modify them. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import statistics\n",
    "import hashlib\n",
    "import secrets\n",
    "\n",
    "def floyd(f: callable, x0: str, limit_iterations: int = 100000) -> int:\n",
    "    \"\"\"\n",
    "    You don't have to modify or call this function.\n",
    "    Floyd's cycle detection algorithm: https://en.wikipedia.org/wiki/Cycle_detection\n",
    "    Used to test the quality of the hash function.\n",
    "    \"\"\"\n",
    "    tortoise = f(x0) \n",
    "    hare = f(f(x0))\n",
    "\n",
    "    steps_taken = 0\n",
    "    while tortoise != hare:\n",
    "        steps_taken += 1\n",
    "        tortoise = f(tortoise)\n",
    "        hare = f(f(hare))\n",
    "\n",
    "        if steps_taken > limit_iterations:\n",
    "            return -1\n",
    "   \n",
    "    mu = 0\n",
    "    tortoise = x0\n",
    "    while tortoise != hare:\n",
    "        tortoise = f(tortoise)\n",
    "        hare = f(hare) \n",
    "        mu += 1\n",
    " \n",
    "    lam = 1\n",
    "    hare = f(tortoise)\n",
    "    while tortoise != hare:\n",
    "        hare = f(hare)\n",
    "        lam += 1\n",
    "\n",
    "    return lam\n",
    "\n",
    "def test_hash_function(function_to_test: callable):\n",
    "    \"\"\"\n",
    "    You don't have to modify this function.\n",
    "    Different toy functions that test the quality of a hash function.\n",
    "    \"\"\"\n",
    "    def test_determinism(inputs, outputs, n_iters=100):\n",
    "        print(f'Testing if your function is deterministic.')\n",
    "        for i, o in zip(inputs, outputs):\n",
    "            for _ in range(n_iters):\n",
    "                if function_to_test(i) != o:\n",
    "                    print(f'\\t- Result: Not deterministic.')\n",
    "                    return\n",
    "        print(f'\\t- Result: Deterministic')\n",
    "\n",
    "    def generate_test_data(n_samples=100000, max_int=2**128):\n",
    "        inputs = [secrets.token_hex(16) for _ in range(n_samples)]\n",
    "        outputs = [function_to_test(x) for x in inputs]\n",
    "        return inputs, outputs\n",
    "\n",
    "    def test_n_collisions(inputs, outputs):\n",
    "        print(f'Testing number of inputs with collision. [0%;100%], lower is better, <1% is good.')\n",
    "        collision_fraction = len(set(outputs)) / len(inputs)\n",
    "        print(f'\\t- Result: {(1 - collision_fraction) * 100:.5f}%')\n",
    "    \n",
    "    def test_average_cycle_length(inputs, limit_iterations=50000):\n",
    "        print(f'Testing number of short cycles. [0; {len(inputs)}] less is better, <20 is good.')\n",
    "        lengths = [floyd(function_to_test, x, limit_iterations) for x in inputs]\n",
    "        lengths = [x for x in lengths if x != -1]\n",
    "        n_cycled = len(lengths)\n",
    "        print(f'\\t- Result: {n_cycled}')\n",
    "        print(f'Average cycle length. [0; {limit_iterations}], higher is better, >10000 is good')\n",
    "        avg_cycle_len = int(statistics.mean(lengths)) if lengths else -1\n",
    "        suffix = ''\n",
    "        if avg_cycle_len == 1:\n",
    "            suffix = ', which means that on average H(x) = H(H(x)) = x'\n",
    "        elif avg_cycle_len == -1:\n",
    "            suffix = ', which is good, no short cycle was found.'\n",
    "        print(f'\\t- Result: {avg_cycle_len}{suffix}')\n",
    "\n",
    "    def test_hamming_weight(outputs):\n",
    "        def count_hamming_weight(num: str):\n",
    "            return sum([num & (1<<i)>0 for i in range(32)])\n",
    "        print(f'Computing average hamming weight: [0;32] closer to 16 is better, 14-18 is good.')\n",
    "        weights = [count_hamming_weight(int(x, 16)) for x in outputs]\n",
    "        print(f'\\t- Result: {int(statistics.mean(weights))}')\n",
    "    \n",
    "    inputs, outputs = generate_test_data()\n",
    "    test_determinism(inputs[:1000], outputs[:1000])\n",
    "    test_n_collisions(inputs, outputs)\n",
    "    test_average_cycle_length(inputs[:20])\n",
    "    test_hamming_weight(outputs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 1: Brewing custom hash function\n",
    "\n",
    "- Your only task is to invent your own cryptographic hash function by modifying the method `custom_hash_function()` in the cell below.\n",
    "- You can use the following operators:\n",
    "    - Modular exponentiation: `pow(base, exponent, modulo)`\n",
    "    - Multiplication with constant integer `inpt * constant_integer`\n",
    "    - Integer divison with constant integer: `inpt // constant_integer`\n",
    "    - Bitwise xor with constant integer: `inpt ^ constant_integer`\n",
    "    - Bitwise and with constant integer: `inpt & constant_integer`\n",
    "    - Bit complement: `~inpt`\n",
    "    - Anything else you like\n",
    "- There is also a wrapper `custom_hash_function_wrapper()`. You don't have to modify it. The wrapper will:\n",
    "    - Automagically encode string as integer\n",
    "    - Apply your hash function on the integer\n",
    "    - **Truncate the result into 4 bytes**\n",
    "    - Automagically decode the integer into hex string\n",
    "- Running `test_hash_function(custom_hash_function_wrapper)` will test your function. Below, you can also see the same tests for truncated SHA-256 function. As SHA-256 is a strong cryptographic hash function, your function should strive for similar results in the tests.\n",
    "- Don't forget that apart from tested properties, the hash function should also be hard to invert.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Testing if your function is deterministic.\n",
      "\t- Result: Deterministic\n",
      "Testing number of inputs with collision. [0%;100%], lower is better, <1% is good.\n",
      "\t- Result: 98.76600%\n",
      "Testing number of short cycles. [0; 20] less is better, <20 is good.\n",
      "\t- Result: 20\n",
      "Average cycle length. [0; 50000], higher is better, >10000 is good\n",
      "\t- Result: 1 , which means that on average H(x) = H(H(x)) = x\n",
      "Computing average hamming weight: [0;32] closer to 16 is better, 14-18 is good.\n",
      "\t- Result: 4\n"
     ]
    }
   ],
   "source": [
    "# TODO: Modify the function below to compute a hash of an integer.\n",
    "def custom_hash_function(inpt: int) -> int:\n",
    "    return inpt % 1234 # TODO: Replace this example with some real computation\n",
    "\n",
    "\n",
    "def custom_hash_function_wrapper(inpt: str) -> str:\n",
    "    \"\"\"\n",
    "    You don't have to modify this function.\n",
    "    Just a wrapper for your function. Accepts string on input, returns hex() representation of the hash.\n",
    "    \"\"\"\n",
    "    try:\n",
    "        inpt = int(inpt, 16)  # We work with hexa in task 1\n",
    "    except ValueError:\n",
    "        inpt = int.from_bytes(inpt.encode(), byteorder='big', signed=False)  # We work with ascii in task 2\n",
    "    output = custom_hash_function(inpt)\n",
    "    output = output % 4294967296\n",
    "    return output.to_bytes(length=4, byteorder='big', signed=False).hex()\n",
    "\n",
    "test_hash_function(custom_hash_function_wrapper)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Below, the truncated version of SHA-256 is tested, your hash function should get as close to these values as possible"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Testing number of inputs with collision. [0%;100%], lower is better, <1% is good.\n",
      "\t- Result: 0.00000%\n",
      "Testing number of short cycles. [0; 20] less is better, <20 is good.\n",
      "\t- Result: 8\n",
      "Average cycle length. [0; 50000], higher is better, >10000 is good.\n",
      "\t- Result: 29114\n",
      "Computing average hamming weight: [0;32] closer to 16 is better, 14-18 is good.\n",
      "\t- Result: 15\n"
     ]
    }
   ],
   "source": [
    "def sha256_32_bits(message: str) -> str:\n",
    "    \"\"\"\n",
    "    You don't have to modify this function.\n",
    "    Given a string, will compute sha256 of the string and return first 32 bits of the digest\n",
    "    \"\"\"\n",
    "    h = hashlib.sha256()\n",
    "    h.update(message.encode())\n",
    "    return h.digest()[:4].hex()\n",
    "\n",
    "test_hash_function(sha256_32_bits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 2: Password cracking\n",
    "\n",
    "Again, starting with some helper functions that you don't have to modify"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "from datetime import datetime\n",
    "\n",
    "PASSWORD_DATABASE = {'WalterJohns@teleworm.eu': '0c6794',  \n",
    "                     'AlvinJones@armyspy.com':  '0f0545',  \n",
    "                     'GenevaClay@armyspy.com':  '094144',  \n",
    "                     'JuanaJensen@gmail.com':   '0b04b6',  \n",
    "                     'ClydeTejeda@seznam.cz':   '0fe3f9'}\n",
    "\n",
    "\n",
    "def authenticate(mail: str, password: str) -> str:\n",
    "    \"\"\"\n",
    "    You don't have to modify this function.\n",
    "    Given login pair (mail, password), this function will attempt to authenticate the given user\n",
    "    \"\"\"\n",
    "    if mail not in PASSWORD_DATABASE:\n",
    "        return '[NOK] Incorrect mail'\n",
    "    elif PASSWORD_DATABASE[mail] == sha256_20_bits(password):\n",
    "        return f'[OK] Successfully authenticated as {mail}'\n",
    "    else:\n",
    "        return f'[NOK] Wrong password.'\n",
    "\n",
    "\n",
    "def increment_string(arr: str) -> str:\n",
    "    \"\"\"\n",
    "    You don't have to modify this function.\n",
    "    will increment a string array (taking into account only the a-z, A-Z, 0-9 characters)\n",
    "    will automatically extend the integer when needed. \n",
    "    Examples: 'z' -> 'z0', 'abc' -> 'abd'\n",
    "    \"\"\"\n",
    "    LOWEST_NUMBER = 48\n",
    "    HIGHEST_NUMER = 57\n",
    "    LOWEST_UPPECASE_CHAR = 65\n",
    "    HIGHEST_UPPERCASE_CHAR = 90\n",
    "    LOWEST_LOWERCASE_CHAR = 98\n",
    "    HIGHEST_LOWERCASE_CHAR = 122\n",
    "    \n",
    "    def increment_alphabet(b: int) -> int:\n",
    "        \"\"\"\n",
    "        You don't have to modify or directly call this function.\n",
    "        Will increment ascii integer.\n",
    "        \"\"\"\n",
    "        if b == HIGHEST_NUMER:\n",
    "            return LOWEST_UPPECASE_CHAR\n",
    "        elif b == HIGHEST_UPPERCASE_CHAR:\n",
    "            return LOWEST_LOWERCASE_CHAR\n",
    "        elif b == HIGHEST_LOWERCASE_CHAR:\n",
    "            return LOWEST_NUMBER\n",
    "        elif b == 0:\n",
    "            return LOWEST_NUMBER\n",
    "        else:\n",
    "            return b + 1\n",
    "    \n",
    "    incremented_arr = bytearray(arr.encode())\n",
    "    for i in range(len(incremented_arr) - 1, -1, -1):\n",
    "        incremented_arr[i] = increment_alphabet(incremented_arr[i])\n",
    "        if incremented_arr[i] != LOWEST_NUMBER:\n",
    "            break\n",
    "        elif incremented_arr[i] == LOWEST_NUMBER and i == 0:\n",
    "            return arr + '0'\n",
    "\n",
    "    return bytes(incremented_arr).decode()\n",
    "\n",
    "def sha256_20_bits(message: str) -> str:\n",
    "    \"\"\"\n",
    "    You don't have to modify this function.\n",
    "    Given a string, computes sha256 on it and returns hex representation of first 20 bits of the digest\n",
    "    \"\"\"\n",
    "    h = hashlib.sha256()\n",
    "    h.update(message.encode())\n",
    "    dgst = int.from_bytes(h.digest()[:3], byteorder = 'big', signed=False) & int('0FFFFF', 16)\n",
    "    return dgst.to_bytes(3, byteorder='big', signed=False).hex()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 2a: Password cracking, 20 bits of SHA-256\n",
    "\n",
    "- Your task is to implement two functions below: `find_preimage()` and `attack_database()` to authenticate to the database.\n",
    "- The `PASSWORD_DATABASE` is in the cell above and passwords were hashed using `sha256_20_bits()` function above.\n",
    "- `find_preimage(h_x)` should, given a hash `h_x` return some `y` for which `sha256_20_bits(y) = h_x`.\n",
    "    - It may be useful to use function `increment_string()` to generate different preimage candidates. E.g. calling `increment_string(\"abc\")` will return `\"abd\"`.\n",
    "    - Finding the preimage may take up to 20 seconds.\n",
    "- `attack_database()` should then only call the `find_preimage()` on all database hashes and get a viable password for each mail.\n",
    "- Using obtained passwords, you can try to call `authenticate(mail, your_found_preimage)` to login to the database.\n",
    "- Do you think you found the same password as was used to create the database? Or could it be different?."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_preimage(template_hash: str) -> str:\n",
    "    \"\"\"\n",
    "    Given a template_hash (hex encoded string), the function should return y such that\n",
    "    sha256_20_bits(y) == template_hash.\n",
    "    \"\"\"\n",
    "    pass  # TODO: Implement me.\n",
    "\n",
    "\n",
    "def attack_database():\n",
    "    \"\"\"\n",
    "    For each entry (mail, password_hash) in PASSWORD_DATABASE, this function should find\n",
    "    a suitable preimage and perform authentication into the database.\n",
    "    \"\"\"\n",
    "    for mail, password_hash in PASSWORD_DATABASE.items():\n",
    "        pass  # TODO: Implement me.\n",
    "\n",
    "attack_database()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Task 2b: Password cracking, 32 bits of custom hash function\n",
    "\n",
    "Below is a snippet that creates a password database using your custom hash function from the first part. Try to attack your custom database again and answer the following questions:\n",
    "1. Was cracking your 32-bit function easier than cracking 20 bits of SHA-256? \n",
    "2. Did you find the shorter or longer password then the one used to construct the database? \n",
    "3. When using weak hash function, does strong password actually help?\n",
    "4. If we use one-bit longer hash function, how does it affect the computation time needed to find the preimage (consider random function as the hash function)?\n",
    "5. Estimate time to find a preimage of full SHA-256, given the time it took you to find preimage on 20 bits. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "CUSTOM_FUNCTION_PASSWORD_DATABASE = {'WalterJohns@teleworm.eu': custom_hash_function_wrapper('tackling plausible snort guzzler'),  \n",
    "                                     'AlvinJones@armyspy.com':  custom_hash_function_wrapper('shifting rush stew rework'),  \n",
    "                                     'GenevaClay@armyspy.com':  custom_hash_function_wrapper('hastiness percolate suds hurray'),  \n",
    "                                     'JuanaJensen@gmail.com':   custom_hash_function_wrapper('boundless washstand mud macaroni'),  \n",
    "                                     'ClydeTejeda@seznam.cz':   custom_hash_function_wrapper('twerp passable music subscript')}\n",
    "\n",
    "def custom_function_authenticate(mail: str, password: str) -> str:\n",
    "    \"\"\"\n",
    "    You don't have to modify this function.\n",
    "    Will authenticate using your custom database.\n",
    "    \"\"\"\n",
    "    if mail not in CUSTOM_FUNCTION_PASSWORD_DATABASE:\n",
    "        return '[NOK] Incorrect mail'\n",
    "    elif CUSTOM_FUNCTION_PASSWORD_DATABASE[mail] == custom_hash_function_wrapper(password):\n",
    "        return f'[OK] Successfully authenticated as {mail}'\n",
    "    else:\n",
    "        return f'[NOK] Wrong password.'\n",
    "\n",
    "def custom_function_find_preimage(template_hash: str) -> str:\n",
    "    \"\"\"\n",
    "    Given a template_hash (hex encoded string), the function should return y such that\n",
    "    custom_hash_function_wrapper(y) == template_hash.\n",
    "    \"\"\"\n",
    "    pass  # TODO: Implement me.\n",
    "\n",
    "\n",
    "def custom_function_attack_database():\n",
    "    \"\"\"\n",
    "    For each entry (mail, password_hash) in CUSTOM_FUNCTION_PASSWORD_DATABASE, this function should find\n",
    "    a suitable preimage and perform authentication into the database.\n",
    "    \"\"\"\n",
    "    for mail, password_hash in CUSTOM_FUNCTION_PASSWORD_DATABASE.items():\n",
    "        pass  # TODO: Implement me.\n",
    "\n",
    "custom_function_attack_database()"
   ]
  }
 ],
 "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.8.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}