Regvex is a proof of concept timing attack against regex engines. To make a long story short, the timing characteristics of regex engines make it perfectly suited to timing attacks, allowing you to (locally or remotely) create data that matches a given regex, and potentially even reconstruct the actual regex you're matching against.
The current version works locally against Python's sre, but I plan to take it further when I have time.
You will not be able to reconstruct the regex by a timing attack unless you make some assumptions on the input like maximum length and even then reconstructing the regex will be tough. If you don't make a maximum length assumption then the best you can do is create a string that will pass it because you will never be able to tell the difference between /a+/ and /a{1,10^99999999999999}/. Practically this might not make a difference but theoretically it does.
Actually, while that was my first thought as well, it depends on the underlying implementation. I'm not positive here, but I think that the characteristics of the regex engine could allow you to recognize the difference between /a+/ and /a{1,1000}/. That said, I haven't done anything to this end yet -- we'll see if my idea remotely pans out. It'll certainly require knowing what regex engine you're attacking, unlike just generating data.
You're probably right. I think the idea is really cool and I'm surprised some CS grad student hasn't jumped on this stuff yet. There is a lot of theory lurking in the background for this kind of stuff and it would definitely make a nice master's thesis.
I'm planning on writing up a blog post exploring the attack and possibilities, but from a high level:
When you pass data into a regex engine for matching, it works character-by-character. When it reaches a character that doesn't match, the matching is terminated. That means that if you have the regex /^foo$/, "f" will take slightly longer to parse than "b", since it'll move on to the next character for "f", but not "b".
Due to this, you can produce matching data for a regex in a fairly small number of samples. Interestingly, it takes fewer samples to reliably get characters further down the string -- however, this may be a result of my horrid statistics code. Not sure yet.
As far as I'm aware, no one has ever done this before.
As someone who has made regular expression acceleration products, we were aware of this possibility but we didn't ever implement a proof of concept. The range of applications is pretty staggering just in network and host security. I'm interested to see what you come up with.
Regvex is a proof of concept timing attack against regex engines. To make a long story short, the timing characteristics of regex engines make it perfectly suited to timing attacks, allowing you to (locally or remotely) create data that matches a given regex, and potentially even reconstruct the actual regex you're matching against.
The current version works locally against Python's sre, but I plan to take it further when I have time.