#!/usr/bin/env python
# coding: utf-8
# # Table of Contents
#
# # Manual implementation of some hash functions
#
# 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
#
# 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).
# Ideally, my implementation should work exactly like the reference one, only slower!
#
#
# - *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).
# - *Date*: 13 May 2017 (first part about MD5), 19 June 2017 (second part about SHA-1), 19 June 2017 (last part about SHA-2).
# - *Author*: [Lilian Besson](https://GitHub.com/Naereen/notebooks).
# - *License*: [MIT Licensed](https://LBesson.MIT-License.org/).
# ----
# ## What is a hash function?
# > 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.
# ----
# ## Common API for the different classes
#
# 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.
# In[1]:
class Hash(object):
""" Common class for all hash methods.
It copies the one of the hashlib module (https://docs.python.org/3.5/library/hashlib.html).
"""
def __init__(self, *args, **kwargs):
""" Create the Hash object."""
self.name = self.__class__.__name__ # https://docs.python.org/3.5/library/hashlib.html#hashlib.hash.name
self.byteorder = 'little'
self.digest_size = 0 # https://docs.python.org/3.5/library/hashlib.html#hashlib.hash.digest_size
self.block_size = 0 # https://docs.python.org/3.5/library/hashlib.html#hashlib.hash.block_size
def __str__(self):
return self.name
def update(self, arg):
""" Update the hash object with the object arg, which must be interpretable as a buffer of bytes."""
pass
def digest(self):
""" 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."""
return b""
def hexdigest(self):
""" 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."""
digest = self.digest()
raw = digest.to_bytes(self.digest_size, byteorder=self.byteorder)
format_str = '{:0' + str(2 * self.digest_size) + 'x}'
return format_str.format(int.from_bytes(raw, byteorder='big'))
# ----
# ## Checking the [the `hashlib` module in Python standard library](https://docs.python.org/3/library/hashlib.html)
# In[2]:
import hashlib
# 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.
# In[3]:
list(hashlib.algorithms_available)
# I will need at least these ones:
# In[4]:
assert 'MD5' in hashlib.algorithms_available
assert 'SHA1' in hashlib.algorithms_available
assert 'SHA256' in hashlib.algorithms_available
assert 'SHA224' in hashlib.algorithms_available
assert 'SHA512' in hashlib.algorithms_available
assert 'SHA384' in hashlib.algorithms_available
# Lets check that they have the block size and digest size announced:
# In[5]:
for name, s in zip(
('MD5', 'SHA1', 'SHA256', 'SHA224', 'SHA512', 'SHA384'),
(hashlib.md5(), hashlib.sha1(), hashlib.sha256(), hashlib.sha224(), hashlib.sha512(), hashlib.sha384())
):
print("For {:<8} : the block size is {:<3} and the digest size is {:<2}.".format(name, s.block_size, s.digest_size))
# ----
# ## First stupid example: a stupid hashing function
#
# 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.
#
# This is just to check the API and how to read from a bytes buffer.
# In[6]:
class HeaderHash(Hash):
""" 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.
"""
def __init__(self):
# Common part
self.digest_size = 16
self.block_size = 16
self.name = "Header"
# Specific part
self._data = b""
def update(self, arg):
""" Update the hash object with the object arg, which must be interpretable as a buffer of bytes."""
if len(self._data) == 0:
self._data = arg[:self.block_size]
def digest(self):
""" 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."""
return self._data
# Let us try it:
# In[7]:
h1 = HeaderHash()
# In[8]:
h1
print(h1)
# Let us use some toy data, to test here and after.
# In[9]:
data = b"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" * 100
# In[10]:
h1.update(data)
h1.digest()
# > Well... It seems to work, even if this first example is stupid.
# ----
# ## First real example: the MD5 hashing function
# Let start with a simple one: [the MD5 hashing function](https://en.wikipedia.org/wiki/MD5), from Rivest in 1992.
#
# Warning: it is considered broken since at least 2012, never use it for security purposes.
# ### Useful functions for the MD5 algorithm
# 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).
# In[11]:
def MD5_f1(b, c, d):
""" First ternary bitwise operation."""
return ((b & c) | ((~b) & d)) & 0xFFFFFFFF
def MD5_f2(b, c, d):
""" Second ternary bitwise operation."""
return ((b & d) | (c & (~d))) & 0xFFFFFFFF
def MD5_f3(b, c, d):
""" Third ternary bitwise operation."""
return (b ^ c ^ d) & 0xFFFFFFFF
def MD5_f4(b, c, d):
""" Forth ternary bitwise operation."""
return (c ^ (b | (~d))) & 0xFFFFFFFF
# In[12]:
def leftrotate(x, c):
""" Left rotate the number x by c bytes."""
x &= 0xFFFFFFFF
return ((x << c) | (x >> (32 - c))) & 0xFFFFFFFF
# In[13]:
def leftshift(x, c):
""" Left shift the number x by c bytes."""
return x << c
# In[14]:
from math import floor, sin
# ### The `MD5` class
# It is a direct implementation of the pseudo-code, as given for instance on the Wikipedia page, or the original research article by Rivest.
# In[15]:
class MD5(Hash):
"""MD5 hashing, see https://en.wikipedia.org/wiki/MD5#Algorithm."""
def __init__(self):
self.name = "MD5"
self.byteorder = 'little'
self.block_size = 64
self.digest_size = 16
# Internal data
s = [0] * 64
K = [0] * 64
# Initialize s, s specifies the per-round shift amounts
s[ 0:16] = [7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22]
s[16:32] = [5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20]
s[32:48] = [4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23]
s[48:64] = [6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21]
# Store it
self._s = s
# Use binary integer part of the sines of integers (Radians) as constants:
for i in range(64):
K[i] = floor(2**32 * abs(sin(i + 1))) & 0xFFFFFFFF
# Store it
self._K = K
# Initialize variables:
a0 = 0x67452301 # A
b0 = 0xefcdab89 # B
c0 = 0x98badcfe # C
d0 = 0x10325476 # D
self.hash_pieces = [a0, b0, c0, d0]
def update(self, arg):
s, K = self._s, self._K
a0, b0, c0, d0 = self.hash_pieces
# 1. Pre-processing
data = bytearray(arg)
orig_len_in_bits = (8 * len(data)) & 0xFFFFFFFFFFFFFFFF
# 1.a. Add a single '1' bit at the end of the input bits
data.append(0x80)
# 1.b. Padding with zeros as long as the input bits length ≡ 448 (mod 512)
while len(data) % 64 != 56:
data.append(0)
# 1.c. append original length in bits mod (2 pow 64) to message
data += orig_len_in_bits.to_bytes(8, byteorder='little')
assert len(data) % 64 == 0, "Error in padding"
# 2. Computations
# Process the message in successive 512-bit = 64-bytes chunks:
for offset in range(0, len(data), 64):
# 2.a. 512-bits = 64-bytes chunks
chunks = data[offset : offset + 64]
# 2.b. Break chunk into sixteen 32-bit = 4-bytes words M[j], 0 ≤ j ≤ 15
A, B, C, D = a0, b0, c0, d0
# 2.c. Main loop
for i in range(64):
if 0 <= i <= 15:
F = MD5_f1(B, C, D)
g = i
elif 16 <= i <= 31:
F = MD5_f2(B, C, D)
g = (5 * i + 1) % 16
elif 32 <= i <= 47:
F = MD5_f3(B, C, D)
g = (3 * i + 5) % 16
elif 48 <= i <= 63:
F = MD5_f4(B, C, D)
g = (7 * i) % 16
# Be wary of the below definitions of A, B, C, D
to_rotate = (A + F + K[i] + int.from_bytes(chunks[4*g : 4*g+4], byteorder='little')) & 0xFFFFFFFF
new_B = (B + leftrotate(to_rotate, s[i])) & 0xFFFFFFFF
A, B, C, D = D, new_B, B, C
# Add this chunk's hash to result so far:
a0 = (a0 + A) & 0xFFFFFFFF
b0 = (b0 + B) & 0xFFFFFFFF
c0 = (c0 + C) & 0xFFFFFFFF
d0 = (d0 + D) & 0xFFFFFFFF
# 3. Conclusion
self.hash_pieces = [a0, b0, c0, d0]
def digest(self):
return sum(leftshift(x, (32 * i)) for i, x in enumerate(self.hash_pieces))
# We can also write a function to directly compute the hex digest from some bytes data.
# In[16]:
def hash_MD5(data):
""" Shortcut function to directly receive the hex digest from MD5(data)."""
h = MD5()
if isinstance(data, str):
data = bytes(data, encoding='utf8')
h.update(data)
return h.hexdigest()
# *Note:* [This page helped for debugging](https://rosettacode.org/wiki/MD5/Implementation#Python).