derv82/average.py

## average.py
#!/usr/bin/python

"""
	Receives 2 command-line arguments:
	* Number of low-order bits to match
	* Length of time to run for (in seconds)

	Executes for a given time, generating random SHA1 hashes,
	and counting how many times the low-order bits match the "z".

	Prints out average time to generate low-order bits.
"""

import hashlib
import random
import sys
import time
import string
import binascii

random.seed(time.time())

def ascii_to_long(asc):
	"""
		converts ASCII string to long
	"""
	return long(binascii.hexlify(asc), 16)


# The given 20-digit string (pre-hashed with SHA1)
z    = '\x83\xa1K\xbe\xect\x88=\x07\x840\x89\x1f\x9ao\xae3Yw;'

# Convert x to a long
zlong = ascii_to_long(z)


def matching_bits(n, m):
	"""
		Counts number of matching bits between longs n and m, starting
		from low-order (right) side.  Only counts until it hits a
		non-matching pair of bits.
	"""
	x = n ^ m
	if x == 0: return 8 # Only way to get 0 is if n == m, so all 8 bits are the same
	# Find how many bits are similar
	place = 0
	while x % 2 == 0:
		place += 1
		x = x >> 1
	return place


def generate_low_order_bits(num, verbose=True):
	"""
		Returns the amount of time required to generate SHA1 hash that
		has at least 'num' matching low-order bits with 'z'.
	"""
	total_guesses = 0
	time_started = time.time()
	while True:
		# Generate 16 random bits
		# x = ''.join(random.choice(string.ascii_lowercase + string.digits) for x in range(32))
		x = str(random.getrandbits(64))
		total_guesses += 1

		# Get SHA-1 for x
		sha = hashlib.sha1()
		sha.update(x)
		y = sha.digest()

		# Convert y to list of ints
		ylong = ascii_to_long(y)

		# Count how many bits match
		total_matches = matching_bits(ylong, zlong)

		# If the number of matching bits between these two SHA-1 hashes is > 'num', we're done.
		if total_matches >= num: break

	# Display results (if verbose)
	if verbose:
		print 'total hashes guessed: %d' % (total_guesses)
		print '\noriginal%s' % (' ' * (len(x) - 2) + '= ' + to_hex(z))
		print 'SHA(%s) = %s' % (x, to_hex(y))

		matching_chars = total_matches / 4
		print '        %s%s%s' % (' ' * len(x), ' ' * (40 - matching_chars), '^' * matching_chars)
		print '\n %d bits matched in %.0fms' % (total_matches, 1000 * (time.time() - time_started))

	# Return the total time taken
	return time.time() - time_started


def get_average(num_bits, max_time):
	"""
		Generates hash that matches "num_bits" low order bits,
		and does this for at least 'max_time' number of seconds before stopping and taking the average.
		Returns the average amount of time required to generate the low-order bits (in milliseconds)
	"""
	# Keep track of when we started (so we know when to stop)
	time_started = time.time()
	# Keep track of how long each attempt takes
	total_time = 0.0

	runs = 0
	while time.time() - time_started < max_time:
		runs += 1
		print '\r %d' % runs,
		sys.stdout.flush()
		total_time += generate_low_order_bits(num_bits, verbose=False)

	average_time = (total_time * 1000) / float(runs)
	print "\r        \n matched %d low-order bits %d times: %.3fms average" % (num_bits, runs, average_time)
	return average_time


def to_hex(s):
	"""
		Convert an ascii string to hex string
	"""
	lst = []
	for ch in s:
		hv = hex(ord(ch)).replace('0x', '')
		if len(hv) == 1:
			hv = '0'+hv
		lst.append(hv)
	return reduce(lambda x,y:x+y, lst)


# Entry point
if __name__ == '__main__':
	try:
		# Get command line args
		args = sys.argv[1:]
		# 2 args are required, they must be digits
		if len(args) < 2 or not args[0].isdigit() or not args[1].isdigit():
			print ' script requires 2 integer arguments to calculate average time'
			print ' python isha.py <number of bits to match> <maximum time to give for generating>'
			exit(1)

		get_average(int(args[0]), int(args[1]))

	# Catch keyboard interrupts (ctrl+c)
	# Avoids printing the ugly stack dump
	except KeyboardInterrupt: pass


## best.py
#!/usr/bin/python

"""
	Calculates the most matching low-order bits for a given "z"
	Waits until user presses CTRL+C, then displays results.
"""

import hashlib
import random
import string
import time
import sys
import binascii

random.seed(time.time())

def ascii_to_long(asc):
	"""
		converts ASCII string to long
	"""
	return long(binascii.hexlify(asc), 16)


# The given 20-digit string (pre-hashed with SHA1)
z    = '\x83\xa1K\xbe\xect\x88=\x07\x840\x89\x1f\x9ao\xae3Yw;'

# Convert x to a list of ints for easy computing
zlong = ascii_to_long(z)


def matching_bits(n, m):
	"""
		Counts number of matching bits between two longs n and m,
		starting from low-order (right) side.
		Only counts until it hits a non-matching pair of bits.
	"""
	x = n ^ m
	if x == 0: return 8 # Only way to get 0 is if n == m, so all 8 bits are the same
	# Find how many bits are similar
	place = 0
	while x % 2 == 0:
		place += 1
		x = x >> 1
	return place


def generate_low_order_bits():
	"""
		Repeatedly generates SHA-1 hashes and counts # of matching bits.
		Keeps track of highest-matches until user presses CTRL+C
	"""
	total_guesses = 0
	time_started = time.time()

	most_matches = 0
	most_y = ''
	most_x = ''
	most_time = time.time()
	most_guessed = 0
	try:
		while True:
			# Generate 160 random bits
			#x = ''.join(random.choice(string.ascii_lowercase + string.digits) for d in range(32))
			x = str(random.getrandbits(160))

			total_guesses += 1

			# Get SHA-1 for x
			sha = hashlib.sha1()
			sha.update(x)
			y = sha.digest()

			# Convert y to list of ints
			ylong = ascii_to_long(y)

			# Count how many bits match
			total_matches = matching_bits(ylong, zlong)

			if total_matches > most_matches:
				most_matches = total_matches
				most_y = y
				most_x = x
				most_time = time.time()
				most_guessed = total_guesses
				print '\r Matched %d low-order bits' % (most_matches),
				sys.stdout.flush()

	except KeyboardInterrupt: pass
	print '\r                                  '
	# Display results (if verbose)
	print 'total hashes guessed: %d' % (total_guesses)
	print '\noriginal%s' % (' ' * (len(most_x) - 2) + '= ' + to_hex(z))
	print 'SHA(%s) = %s' % (most_x, to_hex(most_y))

	matching_chars = most_matches / 4
	print '        %s%s%s' % (' ' * len(most_x), ' ' * (40 - matching_chars), '^' * matching_chars)
	print '\n %d bits matched in %s after %d guesses' % (most_matches, sec_to_hms(most_time - time_started), most_guessed)


def to_hex(s):
	"""
		Convert an ascii string to hex string
	"""
	lst = []
	for ch in s:
		hv = hex(ord(ch)).replace('0x', '')
		if len(hv) == 1:
			hv = '0'+hv
		lst.append(hv)
	return reduce(lambda x,y:x+y, lst)


def sec_to_hms(sec):
	"""
		Formats seconds to HH:MM:SS format
	"""
	frac = float(sec)
	sec = int(sec)
	frac = frac - float(sec)

	s = sec % 60
	m = sec / 60
	h = m / 60
	m = m % 60
	h = h % 60
	return "%s:%s:%s.%.0f" % (h, m, s, frac * 1000)


# Entry point
if __name__ == '__main__':
	generate_low_order_bits()


## results.txt
TCSS 431 - Network Security
Hash Lab


PART 1: Calculate as many low-order bits of the 20-digit string as possible.

My ID is 24 and my given 20-digit string is '\x83\xa1K\xbe\xect\x88=\x07\x840\x89\x1f\x9ao\xae3Yw;'

I was able to generate a hash which matches the 25 low-order bits of the given string.  The hash is below:


   original                              = 83a14bbeec74883d078430891f9a6fae3359773b
   SHA(9x0afs7czay0zffrpaaq52ytdi9w1jqz) = 2fe54b3cf65dee301f90f70d513ed2009559773b
                                                                             ^^^^^^
   25 bits matched in 0:1:23.574 after 2,568,875 guesses

This calculation took 1 minute, 23 seconds and was after 2.5 million random guesses.

I used the attached script "best.py" to calculate this amount.


---------------

PART 2: Calculate how much time is needed to generate all 160 bits of an SHA-1 hash


To calculate how long it would take to generate all the bits of a 160-bit SHA1 hash, I used empirical testing by taking the average time to find lower order bits.

The script generated SHA-1 hashes which matched the low-order bits of the given Z.  The generation for each amount of bits was repeated numerously and the average time needed to generate the low-order bits was calculated.

Below are the results of the empirical testing:

BITS	AVERAGE TIME (ms)
----  -----------------
  1       0.027
  2       0.051
  3       0.096
  4       0.177
  5       0.327
  6       0.594
  7       1.178
  8       2.228
  9       4.347
 10       9.496
 11	     18.748
 12	     36.344
 13      74.938
 14     149.257
 15     290.533
 16     551.237
 17     924.674


I used the attached script "average.py" to calculate these averages.

With the data gathered, a logarhythmic pattern appeared instantly.  The function for the time needed to generate N number of bits is approximately T(N) = 2 ^ (N - 5) milliseconds.

Excel gave me the value T(N) = 1.97 ^ (N - 7) which I rounded to 2.

Plugging in the full 160 bits which SHA-1 generates, we get:
  2 ^ (160 - 7)
= 2 ^ (153)
= 1.14 * 10 ^ 46 milliseconds
= 10 ^ 32 millenia

This would take a VERY long time...

3,620,618,195,601,115,882,948,467,705,351,300 years.

According to NASA, the universe is roughly 14 billion years old.  Calculating the hash could take longer than a 25 sextillion times the age of the universe.
	#!/usr/bin/python

	"""
	Receives 2 command-line arguments:
	* Number of low-order bits to match
	* Length of time to run for (in seconds)

	Executes for a given time, generating random SHA1 hashes,
	and counting how many times the low-order bits match the "z".

	Prints out average time to generate low-order bits.
	"""

	import hashlib
	import random
	import sys
	import time
	import string
	import binascii

	random.seed(time.time())

	def ascii_to_long(asc):
	"""
	converts ASCII string to long
	"""
	return long(binascii.hexlify(asc), 16)


	# The given 20-digit string (pre-hashed with SHA1)
	z = '\x83\xa1K\xbe\xect\x88=\x07\x840\x89\x1f\x9ao\xae3Yw;'

	# Convert x to a long
	zlong = ascii_to_long(z)


	def matching_bits(n, m):
	"""
	Counts number of matching bits between longs n and m, starting
	from low-order (right) side. Only counts until it hits a
	non-matching pair of bits.
	"""
	x = n ^ m
	if x == 0: return 8 # Only way to get 0 is if n == m, so all 8 bits are the same
	# Find how many bits are similar
	place = 0
	while x % 2 == 0:
	place += 1
	x = x >> 1
	return place


	def generate_low_order_bits(num, verbose=True):
	"""
	Returns the amount of time required to generate SHA1 hash that
	has at least 'num' matching low-order bits with 'z'.
	"""
	total_guesses = 0
	time_started = time.time()
	while True:
	# Generate 16 random bits
	# x = ''.join(random.choice(string.ascii_lowercase + string.digits) for x in range(32))
	x = str(random.getrandbits(64))
	total_guesses += 1

	# Get SHA-1 for x
	sha = hashlib.sha1()
	sha.update(x)
	y = sha.digest()

	# Convert y to list of ints
	ylong = ascii_to_long(y)

	# Count how many bits match
	total_matches = matching_bits(ylong, zlong)

	# If the number of matching bits between these two SHA-1 hashes is > 'num', we're done.
	if total_matches >= num: break

	# Display results (if verbose)
	if verbose:
	print 'total hashes guessed: %d' % (total_guesses)
	print '\noriginal%s' % (' ' * (len(x) - 2) + '= ' + to_hex(z))
	print 'SHA(%s) = %s' % (x, to_hex(y))

	matching_chars = total_matches / 4
	print ' %s%s%s' % (' ' * len(x), ' ' * (40 - matching_chars), '^' * matching_chars)
	print '\n %d bits matched in %.0fms' % (total_matches, 1000 * (time.time() - time_started))

	# Return the total time taken
	return time.time() - time_started


	def get_average(num_bits, max_time):
	"""
	Generates hash that matches "num_bits" low order bits,
	and does this for at least 'max_time' number of seconds before stopping and taking the average.
	Returns the average amount of time required to generate the low-order bits (in milliseconds)
	"""
	# Keep track of when we started (so we know when to stop)
	time_started = time.time()
	# Keep track of how long each attempt takes
	total_time = 0.0

	runs = 0
	while time.time() - time_started < max_time:
	runs += 1
	print '\r %d' % runs,
	sys.stdout.flush()
	total_time += generate_low_order_bits(num_bits, verbose=False)

	average_time = (total_time * 1000) / float(runs)
	print "\r \n matched %d low-order bits %d times: %.3fms average" % (num_bits, runs, average_time)
	return average_time


	def to_hex(s):
	"""
	Convert an ascii string to hex string
	"""
	lst = []
	for ch in s:
	hv = hex(ord(ch)).replace('0x', '')
	if len(hv) == 1:
	hv = '0'+hv
	lst.append(hv)
	return reduce(lambda x,y:x+y, lst)


	# Entry point
	if __name__ == '__main__':
	try:
	# Get command line args
	args = sys.argv[1:]
	# 2 args are required, they must be digits
	if len(args) < 2 or not args[0].isdigit() or not args[1].isdigit():
	print ' script requires 2 integer arguments to calculate average time'
	print ' python isha.py <number of bits to match> <maximum time to give for generating>'
	exit(1)

	get_average(int(args[0]), int(args[1]))

	# Catch keyboard interrupts (ctrl+c)
	# Avoids printing the ugly stack dump
	except KeyboardInterrupt: pass
	#!/usr/bin/python

	"""
	Calculates the most matching low-order bits for a given "z"
	Waits until user presses CTRL+C, then displays results.
	"""

	import hashlib
	import random
	import string
	import time
	import sys
	import binascii

	random.seed(time.time())

	def ascii_to_long(asc):
	"""
	converts ASCII string to long
	"""
	return long(binascii.hexlify(asc), 16)


	# The given 20-digit string (pre-hashed with SHA1)
	z = '\x83\xa1K\xbe\xect\x88=\x07\x840\x89\x1f\x9ao\xae3Yw;'

	# Convert x to a list of ints for easy computing
	zlong = ascii_to_long(z)


	def matching_bits(n, m):
	"""
	Counts number of matching bits between two longs n and m,
	starting from low-order (right) side.
	Only counts until it hits a non-matching pair of bits.
	"""
	x = n ^ m
	if x == 0: return 8 # Only way to get 0 is if n == m, so all 8 bits are the same
	# Find how many bits are similar
	place = 0
	while x % 2 == 0:
	place += 1
	x = x >> 1
	return place


	def generate_low_order_bits():
	"""
	Repeatedly generates SHA-1 hashes and counts # of matching bits.
	Keeps track of highest-matches until user presses CTRL+C
	"""
	total_guesses = 0
	time_started = time.time()

	most_matches = 0
	most_y = ''
	most_x = ''
	most_time = time.time()
	most_guessed = 0
	try:
	while True:
	# Generate 160 random bits
	#x = ''.join(random.choice(string.ascii_lowercase + string.digits) for d in range(32))
	x = str(random.getrandbits(160))

	total_guesses += 1

	# Get SHA-1 for x
	sha = hashlib.sha1()
	sha.update(x)
	y = sha.digest()

	# Convert y to list of ints
	ylong = ascii_to_long(y)

	# Count how many bits match
	total_matches = matching_bits(ylong, zlong)

	if total_matches > most_matches:
	most_matches = total_matches
	most_y = y
	most_x = x
	most_time = time.time()
	most_guessed = total_guesses
	print '\r Matched %d low-order bits' % (most_matches),
	sys.stdout.flush()

	except KeyboardInterrupt: pass
	print '\r '
	# Display results (if verbose)
	print 'total hashes guessed: %d' % (total_guesses)
	print '\noriginal%s' % (' ' * (len(most_x) - 2) + '= ' + to_hex(z))
	print 'SHA(%s) = %s' % (most_x, to_hex(most_y))

	matching_chars = most_matches / 4
	print ' %s%s%s' % (' ' * len(most_x), ' ' * (40 - matching_chars), '^' * matching_chars)
	print '\n %d bits matched in %s after %d guesses' % (most_matches, sec_to_hms(most_time - time_started), most_guessed)


	def to_hex(s):
	"""
	Convert an ascii string to hex string
	"""
	lst = []
	for ch in s:
	hv = hex(ord(ch)).replace('0x', '')
	if len(hv) == 1:
	hv = '0'+hv
	lst.append(hv)
	return reduce(lambda x,y:x+y, lst)


	def sec_to_hms(sec):
	"""
	Formats seconds to HH:MM:SS format
	"""
	frac = float(sec)
	sec = int(sec)
	frac = frac - float(sec)

	s = sec % 60
	m = sec / 60
	h = m / 60
	m = m % 60
	h = h % 60
	return "%s:%s:%s.%.0f" % (h, m, s, frac * 1000)


	# Entry point
	if __name__ == '__main__':
	generate_low_order_bits()
	TCSS 431 - Network Security
	Hash Lab


	PART 1: Calculate as many low-order bits of the 20-digit string as possible.

	My ID is 24 and my given 20-digit string is '\x83\xa1K\xbe\xect\x88=\x07\x840\x89\x1f\x9ao\xae3Yw;'

	I was able to generate a hash which matches the 25 low-order bits of the given string. The hash is below:


	original = 83a14bbeec74883d078430891f9a6fae3359773b
	SHA(9x0afs7czay0zffrpaaq52ytdi9w1jqz) = 2fe54b3cf65dee301f90f70d513ed2009559773b
	^^^^^^
	25 bits matched in 0:1:23.574 after 2,568,875 guesses

	This calculation took 1 minute, 23 seconds and was after 2.5 million random guesses.

	I used the attached script "best.py" to calculate this amount.


	---------------

	PART 2: Calculate how much time is needed to generate all 160 bits of an SHA-1 hash


	To calculate how long it would take to generate all the bits of a 160-bit SHA1 hash, I used empirical testing by taking the average time to find lower order bits.

	The script generated SHA-1 hashes which matched the low-order bits of the given Z. The generation for each amount of bits was repeated numerously and the average time needed to generate the low-order bits was calculated.

	Below are the results of the empirical testing:

	BITS AVERAGE TIME (ms)
	---- -----------------
	1 0.027
	2 0.051
	3 0.096
	4 0.177
	5 0.327
	6 0.594
	7 1.178
	8 2.228
	9 4.347
	10 9.496
	11 18.748
	12 36.344
	13 74.938
	14 149.257
	15 290.533
	16 551.237
	17 924.674


	I used the attached script "average.py" to calculate these averages.

	With the data gathered, a logarhythmic pattern appeared instantly. The function for the time needed to generate N number of bits is approximately T(N) = 2 ^ (N - 5) milliseconds.

	Excel gave me the value T(N) = 1.97 ^ (N - 7) which I rounded to 2.

	Plugging in the full 160 bits which SHA-1 generates, we get:
	2 ^ (160 - 7)
	= 2 ^ (153)
	= 1.14 * 10 ^ 46 milliseconds
	= 10 ^ 32 millenia

	This would take a VERY long time...

	3,620,618,195,601,115,882,948,467,705,351,300 years.

	According to NASA, the universe is roughly 14 billion years old. Calculating the hash could take longer than a 25 sextillion times the age of the universe.