{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"toc": "true"
},
"source": [
"# Table of Contents\n",
" "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Manual implementation of some hash functions\n",
"\n",
"This small [Jupyter notebook](https://www.Jupyter.org/) is a short experiment, to see if I can implement the some basic [Hashing functions](https://en.wikipedia.org/wiki/Hash_function), more specifically [cryptographic hashing functions](https://en.wikipedia.org/wiki/Cryptographic_hash_function), like `MD5`, `SHA1`, `SHA256`, `SHA512` etc\n",
"\n",
"And then I want compare my manual implementations with the functions implemented in [the `hashlib` module in Python standard library](https://docs.python.org/3/library/hashlib.html).\n",
"Ideally, my implementation should work exactly like the reference one, only slower!\n",
"\n",
"\n",
"- *Reference*: Wikipedia pages on [Hash functions](https://en.wikipedia.org/wiki/Hash_function), [MD5](https://en.wikipedia.org/wiki/MD5), [SHA-1](https://en.wikipedia.org/wiki/SHA1) and [SHA-2](https://en.wikipedia.org/wiki/SHA-2), as well as [the `hashlib` module in Python standard library](https://docs.python.org/3/library/hashlib.html).\n",
"- *Date*: 13 May 2017 (first part about MD5), 19 June 2017 (second part about SHA-1), 19 June 2017 (last part about SHA-2).\n",
"- *Author*: [Lilian Besson](https://GitHub.com/Naereen/notebooks).\n",
"- *License*: [MIT Licensed](https://LBesson.MIT-License.org/)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"## What is a hash function?\n",
"> TL;DR : [Hash functions](https://en.wikipedia.org/wiki/Hash_function) and [cryptographic hashing functions](https://en.wikipedia.org/wiki/Cryptographic_hash_function) on Wikipedia."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"## Common API for the different classes\n",
"\n",
"I will copy the API proposed by [the `hashlib` module in Python standard library](https://docs.python.org/3/library/hashlib.html), so it will be very easy to compare my implementations with the one provided with your default [Python](https://www.Python.org/) installation."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"class Hash(object):\n",
" \"\"\" Common class for all hash methods.\n",
" \n",
" It copies the one of the hashlib module (https://docs.python.org/3.5/library/hashlib.html).\n",
" \"\"\"\n",
" \n",
" def __init__(self, *args, **kwargs):\n",
" \"\"\" Create the Hash object.\"\"\"\n",
" self.name = self.__class__.__name__ # https://docs.python.org/3.5/library/hashlib.html#hashlib.hash.name\n",
" self.byteorder = 'little'\n",
" self.digest_size = 0 # https://docs.python.org/3.5/library/hashlib.html#hashlib.hash.digest_size\n",
" self.block_size = 0 # https://docs.python.org/3.5/library/hashlib.html#hashlib.hash.block_size\n",
"\n",
" def __str__(self):\n",
" return self.name\n",
" \n",
" def update(self, arg):\n",
" \"\"\" Update the hash object with the object arg, which must be interpretable as a buffer of bytes.\"\"\"\n",
" pass\n",
"\n",
" def digest(self):\n",
" \"\"\" Return the digest of the data passed to the update() method so far. This is a bytes object of size digest_size which may contain bytes in the whole range from 0 to 255.\"\"\"\n",
" return b\"\"\n",
"\n",
" def hexdigest(self):\n",
" \"\"\" Like digest() except the digest is returned as a string object of double length, containing only hexadecimal digits. This may be used to exchange the value safely in email or other non-binary environments.\"\"\"\n",
" digest = self.digest()\n",
" raw = digest.to_bytes(self.digest_size, byteorder=self.byteorder)\n",
" format_str = '{:0' + str(2 * self.digest_size) + 'x}'\n",
" return format_str.format(int.from_bytes(raw, byteorder='big'))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"## Checking the [the `hashlib` module in Python standard library](https://docs.python.org/3/library/hashlib.html)"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"import hashlib"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can check [the available algorithms](https://docs.python.org/3.5/library/hashlib.html#hashlib.algorithms_available), some of them being [guaranteed to be on any platform](https://docs.python.org/3.5/library/hashlib.html#hashlib.algorithms_guaranteed), some are not."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['ripemd160',\n",
" 'MD4',\n",
" 'SHA224',\n",
" 'sha384',\n",
" 'md4',\n",
" 'DSA-SHA',\n",
" 'SHA256',\n",
" 'SHA384',\n",
" 'MD5',\n",
" 'whirlpool',\n",
" 'sha',\n",
" 'sha1',\n",
" 'RIPEMD160',\n",
" 'DSA',\n",
" 'dsaWithSHA',\n",
" 'dsaEncryption',\n",
" 'sha224',\n",
" 'SHA',\n",
" 'sha512',\n",
" 'md5',\n",
" 'SHA512',\n",
" 'ecdsa-with-SHA1',\n",
" 'SHA1',\n",
" 'sha256']"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"list(hashlib.algorithms_available)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"I will need at least these ones:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"assert 'MD5' in hashlib.algorithms_available\n",
"assert 'SHA1' in hashlib.algorithms_available\n",
"assert 'SHA256' in hashlib.algorithms_available\n",
"assert 'SHA224' in hashlib.algorithms_available\n",
"assert 'SHA512' in hashlib.algorithms_available\n",
"assert 'SHA384' in hashlib.algorithms_available"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Lets check that they have the block size and digest size announced:"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"For MD5 : the block size is 64 and the digest size is 16.\n",
"For SHA1 : the block size is 64 and the digest size is 20.\n",
"For SHA256 : the block size is 64 and the digest size is 32.\n",
"For SHA224 : the block size is 64 and the digest size is 28.\n",
"For SHA512 : the block size is 128 and the digest size is 64.\n",
"For SHA384 : the block size is 128 and the digest size is 48.\n"
]
}
],
"source": [
"for name, s in zip(\n",
" ('MD5', 'SHA1', 'SHA256', 'SHA224', 'SHA512', 'SHA384'),\n",
" (hashlib.md5(), hashlib.sha1(), hashlib.sha256(), hashlib.sha224(), hashlib.sha512(), hashlib.sha384())\n",
" ):\n",
" print(\"For {:<8} : the block size is {:<3} and the digest size is {:<2}.\".format(name, s.block_size, s.digest_size))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"## First stupid example: a stupid hashing function\n",
"\n",
"This \"stupid\" hashing function will use `digest_size` of 128 bytes (= 16 bits), and compute it by ... just looking at the first 128 bytes of the input data.\n",
"\n",
"This is just to check the API and how to read from a bytes buffer."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"class HeaderHash(Hash):\n",
" \"\"\" This \"stupid\" hashing function will use `digest_size` of 128 bytes, and compute it by ... just looking at the first 128 bytes of the input data.\n",
" \"\"\"\n",
" \n",
" def __init__(self):\n",
" # Common part\n",
" self.digest_size = 16\n",
" self.block_size = 16\n",
" self.name = \"Header\"\n",
" # Specific part\n",
" self._data = b\"\"\n",
"\n",
" def update(self, arg):\n",
" \"\"\" Update the hash object with the object arg, which must be interpretable as a buffer of bytes.\"\"\"\n",
" if len(self._data) == 0:\n",
" self._data = arg[:self.block_size]\n",
"\n",
" def digest(self):\n",
" \"\"\" Return the digest of the data passed to the update() method so far. This is a bytes object of size digest_size which may contain bytes in the whole range from 0 to 255.\"\"\"\n",
" return self._data"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let us try it:"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"h1 = HeaderHash()"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"<__main__.HeaderHash at 0x7fc84c200630>"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Header\n"
]
}
],
"source": [
"h1\n",
"print(h1)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let us use some toy data, to test here and after."
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"data = b\"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ\" * 100"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"b'0123456789ABCDEF'"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"h1.update(data)\n",
"h1.digest()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"> Well... It seems to work, even if this first example is stupid."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"----\n",
"## First real example: the MD5 hashing function\n",
"Let start with a simple one: [the MD5 hashing function](https://en.wikipedia.org/wiki/MD5), from Rivest in 1992.\n",
"\n",
"Warning: it is considered broken since at least 2012, never use it for security purposes."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Useful functions for the MD5 algorithm\n",
"Instead of writing the complete MD5 algorithm in the class below, I preferred to define here some useful functions, using [Bitwise operators](https://wiki.python.org/moin/BitwiseOperators)."
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def MD5_f1(b, c, d):\n",
" \"\"\" First ternary bitwise operation.\"\"\"\n",
" return ((b & c) | ((~b) & d)) & 0xFFFFFFFF\n",
"\n",
"def MD5_f2(b, c, d):\n",
" \"\"\" Second ternary bitwise operation.\"\"\"\n",
" return ((b & d) | (c & (~d))) & 0xFFFFFFFF\n",
"\n",
"def MD5_f3(b, c, d):\n",
" \"\"\" Third ternary bitwise operation.\"\"\"\n",
" return (b ^ c ^ d) & 0xFFFFFFFF\n",
"\n",
"def MD5_f4(b, c, d):\n",
" \"\"\" Forth ternary bitwise operation.\"\"\"\n",
" return (c ^ (b | (~d))) & 0xFFFFFFFF"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def leftrotate(x, c):\n",
" \"\"\" Left rotate the number x by c bytes.\"\"\"\n",
" x &= 0xFFFFFFFF\n",
" return ((x << c) | (x >> (32 - c))) & 0xFFFFFFFF"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def leftshift(x, c):\n",
" \"\"\" Left shift the number x by c bytes.\"\"\"\n",
" return x << c"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"from math import floor, sin"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### The `MD5` class"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"It is a direct implementation of the pseudo-code, as given for instance on the Wikipedia page, or the original research article by Rivest."
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"class MD5(Hash):\n",
" \"\"\"MD5 hashing, see https://en.wikipedia.org/wiki/MD5#Algorithm.\"\"\"\n",
" \n",
" def __init__(self):\n",
" self.name = \"MD5\"\n",
" self.byteorder = 'little'\n",
" self.block_size = 64\n",
" self.digest_size = 16\n",
" # Internal data\n",
" s = [0] * 64\n",
" K = [0] * 64\n",
" # Initialize s, s specifies the per-round shift amounts\n",
" s[ 0:16] = [7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22]\n",
" s[16:32] = [5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20]\n",
" s[32:48] = [4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23]\n",
" s[48:64] = [6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21]\n",
" # Store it\n",
" self._s = s\n",
" # Use binary integer part of the sines of integers (Radians) as constants:\n",
" for i in range(64):\n",
" K[i] = floor(2**32 * abs(sin(i + 1))) & 0xFFFFFFFF\n",
" # Store it\n",
" self._K = K\n",
" # Initialize variables:\n",
" a0 = 0x67452301 # A\n",
" b0 = 0xefcdab89 # B\n",
" c0 = 0x98badcfe # C\n",
" d0 = 0x10325476 # D\n",
" self.hash_pieces = [a0, b0, c0, d0]\n",
" \n",
" def update(self, arg):\n",
" s, K = self._s, self._K\n",
" a0, b0, c0, d0 = self.hash_pieces\n",
" # 1. Pre-processing\n",
" data = bytearray(arg)\n",
" orig_len_in_bits = (8 * len(data)) & 0xFFFFFFFFFFFFFFFF\n",
" # 1.a. Add a single '1' bit at the end of the input bits\n",
" data.append(0x80)\n",
" # 1.b. Padding with zeros as long as the input bits length ≡ 448 (mod 512)\n",
" while len(data) % 64 != 56:\n",
" data.append(0)\n",
" # 1.c. append original length in bits mod (2 pow 64) to message\n",
" data += orig_len_in_bits.to_bytes(8, byteorder='little')\n",
" assert len(data) % 64 == 0, \"Error in padding\"\n",
" # 2. Computations\n",
" # Process the message in successive 512-bit = 64-bytes chunks:\n",
" for offset in range(0, len(data), 64):\n",
" # 2.a. 512-bits = 64-bytes chunks\n",
" chunks = data[offset : offset + 64]\n",
" # 2.b. Break chunk into sixteen 32-bit = 4-bytes words M[j], 0 ≤ j ≤ 15\n",
" A, B, C, D = a0, b0, c0, d0\n",
" # 2.c. Main loop\n",
" for i in range(64):\n",
" if 0 <= i <= 15:\n",
" F = MD5_f1(B, C, D)\n",
" g = i\n",
" elif 16 <= i <= 31:\n",
" F = MD5_f2(B, C, D)\n",
" g = (5 * i + 1) % 16\n",
" elif 32 <= i <= 47:\n",
" F = MD5_f3(B, C, D)\n",
" g = (3 * i + 5) % 16\n",
" elif 48 <= i <= 63:\n",
" F = MD5_f4(B, C, D)\n",
" g = (7 * i) % 16\n",
" # Be wary of the below definitions of A, B, C, D\n",
" to_rotate = (A + F + K[i] + int.from_bytes(chunks[4*g : 4*g+4], byteorder='little')) & 0xFFFFFFFF\n",
" new_B = (B + leftrotate(to_rotate, s[i])) & 0xFFFFFFFF\n",
" A, B, C, D = D, new_B, B, C\n",
" # Add this chunk's hash to result so far:\n",
" a0 = (a0 + A) & 0xFFFFFFFF\n",
" b0 = (b0 + B) & 0xFFFFFFFF\n",
" c0 = (c0 + C) & 0xFFFFFFFF\n",
" d0 = (d0 + D) & 0xFFFFFFFF\n",
" # 3. Conclusion\n",
" self.hash_pieces = [a0, b0, c0, d0]\n",
"\n",
" def digest(self):\n",
" return sum(leftshift(x, (32 * i)) for i, x in enumerate(self.hash_pieces))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can also write a function to directly compute the hex digest from some bytes data."
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def hash_MD5(data):\n",
" \"\"\" Shortcut function to directly receive the hex digest from MD5(data).\"\"\"\n",
" h = MD5()\n",
" if isinstance(data, str):\n",
" data = bytes(data, encoding='utf8')\n",
" h.update(data)\n",
" return h.hexdigest()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
" *Note:* [This page helped for debugging](https://rosettacode.org/wiki/MD5/Implementation#Python).