Scripts for generating the low-order bits of an SHA1 hash.

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.