5 ms·

Fascinating, could you explain how this works?

• daeken 16y ago
  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.
  • mentat 16y ago
    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.