# Homework 6 (FCS)

## Exercise 1

# hw6 SHA

import os
import sys
import hashlib

import random
import timeit

import random
import binascii

import numpy as np

def ex1():
	btxt1 = b'51.505-Foundations-of-Cybersecurity-MSSD'
	btxt2 = b'51.505-Foundations-of-Cybersecurity-MSSd'

	sha_btxt1 = hashlib.sha1(btxt1)
	sha_btxt2 = hashlib.sha1(btxt2)

	return sha_btxt1.hexdigest(), sha_btxt2.hexdigest()

<sha1 HASH object @ 0x000002653F669FB0>
<sha1 HASH object @ 0x000002653F79B210>

sha_btxt1.hexdigest() => `d2d2b25b4ee22957a08c41bfcb12e3b16e810699`

sha_btxt2.hexdigest() => `da7e687280aca8cd68a50ca5c1445f82da9783f7`

## Exercise 2

import os
import sys
import hashlib

import random
import timeit

import random
import binascii

import numpy as np

def ex2():
	

	n = [8, 16]

	mean_time = {n[0] : [], n[1] : []}

	# n = 8  => hashed.append(...).hexdigest()[0:2]
	# n = 16 => hashed.append(...).hexdigest()[0:4]


	for x in range(30):

		for k in n:
			rd512 = [hex(random.getrandbits(512))]
			collision_found = False
			start = timeit.default_timer()

			bites = int(k/4)

			hashed = [hashlib.sha512(binascii.unhexlify(rd512[0][2:].zfill(128))).hexdigest()[0:bites]]

			while not collision_found:
				# generate a new random message
				temp = hex(random.getrandbits(512))
				rd512.append(temp)

				hashed.append(hashlib.sha512(binascii.unhexlify(temp[2:].zfill(128))).hexdigest()[0:bites])

				for i in range(0, len(rd512)):	# sequentially pick each message/hash from the list
					for j in range(i+1, len(rd512)):	# and compare it with every other one
						if hashed[i] == hashed[j]:
							collision_found = True
							end = timeit.default_timer()
							
							print("\nMessage 1: ", rd512[i])
							print("Corresponding Hash: ", hashed[i])

							print("\nMessage 2: ", rd512[j])
							print("Corresponding Hash: ", hashed[j])

							time_taken = end - start
							break
					if collision_found:
						break

			print(f'For n = {k} A total of {len(rd512)} messages generated.')
			print(f'For n = {k} A total of {len(hashed)} hashes computed.')

			mean_time[k].append(time_taken)

	for key, val in mean_time.items():
		print(f'\nn = {key} on average takes {np.mean(val)} s')

Results:

Message 1:  0x59ac8f8e3fe67e93974f276fd88f97149d3f6fe3483b0246306bdf32571de9261731e150d365ab36a3929a05e5820d344468c24349ab09b490f8e304453d23c5
Corresponding Hash:  81

Message 2:  0x29f373b96e481c2707d91d15527e8dde55054009a4d207f2ab1f028cbf66beabcd5a9256f9058e8fc8138649fd2bfbc4c31118ea8216c083f16bdc8827fae0ae
Colliding Hash:  81
For n = 8 A total of 17 messages generated.
For n = 8 A total of 17 hashes computed.

Message 1:  0xd37693ac2c2c9cca567cf8f744be1f551d42359b5581e6b1cf52ddcde6fa51cc7456649dc5edb344cfd2c9991e0b1b78b2e0daaf980e78356f50c6d1db2a2410
Corresponding Hash:  0ca7

Message 2:  0x176aad7b3001d39e7e75ffa846a938f624186f28515c5c5f63055d0e9f667b5b3ce8fc22cbfb607d9a40263e3602c2cda8ea6a8d1f455d7f26704a504e16490d
Colliding Hash:  0ca7
For n = 16 A total of 250 messages generated.
For n = 16 A total of 250 hashes computed.

Message 1:  0x16c912771ba9acbd9552903eda53abf635584472191521b2ab85dcc5662dd2afc146d6cb16b696e2c1a0799ed0b6e7c2a68daeb9555432558f8afa9ea20d6d42
Corresponding Hash:  2a

Message 2:  0x73526f1bbd730438c7b8a07889a6d26f45a9a466e18c7469d48ca51fb87abe6bd5925e0b8fa0512741ae30f87c76aeb390444ea7831a1d6d4f83f4a6bd1c344b
Colliding Hash:  2a
For n = 8 A total of 16 messages generated.
For n = 8 A total of 16 hashes computed.

Message 1:  0x2defbf9a4297728d03efceedfbe6ca986fdfe042bbb2edba31557d47e1e9f6052b55425cb52b62509ddd9615b3ea4b49fb7261cbac5ea3235171353b9e54c1e7
Corresponding Hash:  116d

Message 2:  0x4e7622a81b772b58c2e1d075ec9b7437be672cde784ccd710e3d09c239d98fa1f4c4222f838e31902c433ec9fb62139821db156c6d6dff708ea1462fd67fb31
Colliding Hash:  116d
For n = 16 A total of 346 messages generated.
For n = 16 A total of 346 hashes computed.

Message 1:  0x9abec72a7de5363f76761c1a9c38ea703737d62ebe8e6512dcbb73e3b1c9258692611ccd9017e33e8131c6c845da2abe869a601cc3b001910a4fff52b646af3f
Corresponding Hash:  dc

Message 2:  0xc29bc570014bb95f22fb03799f59cccf66a8e0d29d053a436b270fa22ca5bbec5588471538225fa93da50416172a521161fb14d41862c84d6dfdec8e63a1e71a
Colliding Hash:  dc
For n = 8 A total of 17 messages generated.
For n = 8 A total of 17 hashes computed.

Message 1:  0x14b951d006bd2d3838839b68ebe675c131dd59c3f67a0552f769e33ea2c6fb31c098114778b16ec1a2ef5c0c496a63cf0a1bd76dcbc5c7301c63c7287c9321fa
Corresponding Hash:  9bc3

Message 2:  0x5fec090b49f34d6c945e4cf053b47df7d187b818c814586b26bf76841d662613db92b6542afe2f128e00edf165fdf1a885806189f37cd2b98760a68218312a4e
Colliding Hash:  9bc3
For n = 16 A total of 236 messages generated.
For n = 16 A total of 236 hashes computed.

Message 1:  0xf04fce383d0fe008fcf0d2c008bf992c890e4c1f013a3de9baa461031251b5c1c841d27766363f9af3d4667e9a405fb0e5e6ecee09af76d3b9cfb16d3090d434
Corresponding Hash:  1b

Message 2:  0x37d531773032d6a5f9c517d22cb7524a6254ac38392cc4ec8b3c74ba71020d5a10d4423107793bf44fc299cad348f2268cf79beb086141adfc7bbb888a0f8dc5
Colliding Hash:  1b
For n = 8 A total of 14 messages generated.
For n = 8 A total of 14 hashes computed.

Message 1:  0x13c02723ac2c882aa9933d70321a079be86074bcbe1d415ff2037f7fed2e0aa22382867e9a851e2dfaf18bf00365481785513e792e0cad71bc963514379e968b
Corresponding Hash:  7ccc

Message 2:  0xf313470f43b411ac68bba09d67717a95faa39a64215f2b1582f3d311fa4374c7d3d4178fca747e2b0307d3772a707711f3536d25911bebc3c4f990ac4cde3111
Colliding Hash:  7ccc
For n = 16 A total of 435 messages generated.
For n = 16 A total of 435 hashes computed.

Message 1:  0x6319d8ce028486d648bfc09fcf7f44a94174f4d74bf2a938d0223af30e60fad95554ec14f58bbb942d947359f04635ceead5dfccb0a5fa7b3b60ab5dde4be340
Corresponding Hash:  10

Message 2:  0xbaa9ed932e48973db7acb5314ecee2522689cd5ada2c5437102eda3c6efb9699b4854499a84535098260ce2c812a5e4290bbf8ce3d172f433d077ba83d7ff5c7
Colliding Hash:  10
For n = 8 A total of 14 messages generated.
For n = 8 A total of 14 hashes computed.

Message 1:  0xafa9dc40788ecb96114a230281a83fd8aa68c92268be832934f655159e47bf110f9d741d6f2f8383e2c9c60b8140b1a400e0f5f9789611c9573db7ecbd53108e
Corresponding Hash:  c74f

Message 2:  0xdf72f9a87de1be4ee53de28145f95f78fc9703315d463fa354cc1f331679357e940744438eb4e92715368390c2bad30b342df9a0e510ead9b741309c01d3a463
Colliding Hash:  c74f
For n = 16 A total of 41 messages generated.
For n = 16 A total of 41 hashes computed.

n = 8 on average takes 0.00015161999999998565 s

n = 16 on average takes 0.32491243999999997 s

n = 8 on average the number of messages are 15.6

n = 16 on average the number of messages are 261.6

The colliding hashes can be seen in the snippets of the results.

On average (for 30 iterations) H8 takes 0.00015161999999998565 s
On average (for 30 iterations) H16 takes 0.32491243999999997 s

## Exercise 3

def ex3():
	ns = [8,16]

	for n in ns:
		counter = 0
		preimage_found = False
		start = timeit.default_timer()

		bites = int(n/4)

		while not preimage_found:
			counter += 1
			# generate a random message
			rd512 = hex(random.getrandbits(512))

			hashed = hashlib.sha512(binascii.unhexlify(rd512[2:].zfill(128))).hexdigest()[0:bites]



			if hashed == "0"*bites:
				preimage_found = True
				end = timeit.default_timer()
				break

		print("Took", end - start, "seconds to find preimage.")
		print("The preimage found is ", rd512, " after generating ", counter, "messages.")
		print("The full SHA512 hash is ", hashlib.sha512(binascii.unhexlify(rd512[2:].zfill(128))).hexdigest())

Results

For H8 It took 0.00039320000000042654 seconds to find preimage.
The preimage found is  0x491b73a0d246dd6ab9336c26715fc36230a4aae62155f1d520fe2f917ff05b8535c2a1ce2c8c7dcd1b04a01c9ba80a9e53ac91e63ad1dbafc3b61c198995fce3  after generating  140 messages.
The full SHA512 hash is  000b14f3f660a7414ccf27befac3de7fc6b81d77cef09b89affc62a1621a778dd99dce163766e205be2b028ed01b0f4a301c228843b0ecd7f54a72adf4ea73b7
For H16 It took 0.15512569999999926 seconds to find preimage.
The preimage found is  0xe92a0859fcb5de01ff3c4327f1002be5503e689cad0d75a22d0ee763a11e1fda4a955b87be4d1875521be5091e01218724b2831f82aa218ae1140fd50d6a717f  after generating  69533 messages.
The full SHA512 hash is  00006126ec80341585798d7c415d9520fd3e2990af3b6069355bc654da5641174234d5d8cc6a485133adc80637080ba6ae87ab676867a36a56834dde77b8e37a

## Exercise 4

def ex4():
	# Generate Key
	key = "1".zfill(32)
	print("Key: ", key)
	key = binascii.unhexlify(key)


	# Generate Random Tag
	_tag = hex(random.getrandbits(128))[2:].zfill(32)
	print("Tag: ", _tag)
	tag = binascii.unhexlify(_tag)

	# Decrypt single blk to find tag.
	cipher = AES.new(key, AES.MODE_CBC, IV = binascii.unhexlify('0'.zfill(32)))	# use AES CBC
	singleblk = int.from_bytes(cipher.decrypt(tag), byteorder='big')


	# consider two-block message "blk1 || blk2", where we have a choice of blk2
	blk2 = 1


	'''
	Assume as if tag was MAC(blk1 || blk2) = MAC((MAC(blk1) xor blk2)
	i.e. MAC(blk1) = blk2 xor singleblk
	'''
	_tagprev = hex(singleblk ^ blk2)[2:].zfill(32)
	print("Previous tag: ", _tagprev)
	tagprev = binascii.unhexlify(_tagprev)


	cipher = AES.new(key, AES.MODE_CBC, IV = binascii.unhexlify('0'.zfill(32)))	# use AES CBC
	blk1 = (cipher.decrypt(tagprev)).hex().zfill(32)


	print("Single Block Message: ", hex(singleblk)[2:].zfill(32))
	print("Block 1 of two-block Message: ", blk1)
	print("Block 2 of two-block Message: ", hex(blk2)[2:].zfill(32))

	ex4_verify(blk1, hex(blk2)[2:].zfill(32), _tag, _tagprev, hex(singleblk)[2:].zfill(32))





def ex4_verify(check_blk1, check_blk2, check_tag, check_tagprev, check_singleblk):
	key = key = "00000000000000000000000000000001".zfill(32)
	tag = check_tag.zfill(32)
	tagprev = check_tagprev.zfill(32)
	singleblk = check_singleblk.zfill(32)
	blk1 = check_blk1.zfill(32)
	blk2 = check_blk2

	key = binascii.unhexlify(key)
	tag = binascii.unhexlify(tag)
	tagprev = binascii.unhexlify(tagprev)
	singleblk = binascii.unhexlify(singleblk)
	blk1_blk2 = binascii.unhexlify(blk1 + blk2)

	cipher = AES.new(key, AES.MODE_CBC, IV = binascii.unhexlify('0'.zfill(32)))	# use AES CBC
	check1 = cipher.encrypt(singleblk).hex()
	cipher = AES.new(key, AES.MODE_CBC, IV = binascii.unhexlify('0'.zfill(32)))	# use AES CBC
	check2 = cipher.encrypt(blk1_blk2).hex()

	if check1 == check2[32:]:
		print("Tag is the same for ", singleblk.hex(), " and ", blk1_blk2.hex(), ".")
		print("Tag: ", tag.hex())

Results

Key:  00000000000000000000000000000001
Tag:  11fa92774478f2d8fc78756eaa0a1fb5
Previous tag:  0f87e3b053400b58a55239384065d87a
Single Block Message:  0f87e3b053400b58a55239384065d87b
Block 1 of two-block Message:  5f3e639ffb8736012b19a1a525246609
Block 2 of two-block Message:  00000000000000000000000000000001
Tag is the same for  0f87e3b053400b58a55239384065d87b  and  5f3e639ffb8736012b19a1a52524660900000000000000000000000000000001 .
Tag:  11fa92774478f2d8fc78756eaa0a1fb5

## Exercise 5

Let MAC(.) be the function using CBC=MAC that generates the tag for a message, such that $MAC(a) = t$

The two-block message would be $a || (a ⨁ MAC(a))$.

$MAC(a || (a ⨁ MAC(a)))$ =

= $MAC(MAC(a) ⨁ (a ⨁ MAC(a)))$
= $MAC(MAC(a) ⨁ MAC(a) ⨁ a)$
= $MAC(a)$
= $t$

In other words, by concatenating a with a ⨁ MAC(a), the corresponding tag is still t. The attacker can therefore choose the two-block message as a || (a ⨁ MAC(a)) and forge the tag as t.
In fact, we could continue concatenating more of a ⨁ MAC(a) and apply CBC-MAC and still arrive a tag t. In each XOR operation, the MAC(a) component of the newly concatenated block cancels out t from the previous MAC(.) output. This leaves the final MAC(.) with input a effectively, creating an output equal to t (that the attacked had earlier received).