4 ms·
regvex.py -- http://gist.github.com/641688 http://gist.github.com/641688 Regvex is a proof of concept timing attack against regex engines. To make a long stor
by daeken 16y ago
regvex.py -- http://gist.github.com/641688 http://gist.github.com/641688
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.
- tectonic 16y agoFascinating, could you explain how this works?
- daeken 16y agoI'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.
- mentat 16y agoAs 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.
- Toucan 16y agohttp://emerose.com/timing-attacks-explained http://emerose.com/timing-attacks-explained For others, this helped me understand the basis of timing attacks.
- greenlblue 16y agoYou 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.
- daeken 16y agoActually, 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.
- greenlblue 16y agoYou'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.