3 ms·

I love this idea, though I'm not sure I want my password manager executing arbitrary regexes it finds on the Internet.

by linsomniac 7y ago

saagarjha 7y ago
If you restrict it to “formal” regular expressions you’ll stay out of “arbitrary code executing on a Turing machine”.
- wahern 7y ago
  Regular expression engines are notoriously buggy. You definitely wouldn't want to pass random expressions to libpcre. Web browsers are already running random expressions from the internet, but their regex implementations have proven the rule by being fodder from exploit writers. In any event, requiring a password manager to pull the engine from Firefox or Chrome wouldn't be cool. They're more likely to use libpcre or re2, but see above. The NAPTR DNS record type uses regular expressions for domain rewriting: https://en.wikipedia.org/wiki/NAPTR_record https://en.wikipedia.org/wiki/NAPTR_record Not many DNS libraries support that record type as it adds alot of problematic bloat.
  - saagarjha 7y ago
    libpcre is exactly the implementation I’m not talking about, because it supports too much. I think re2 doesn’t do backtracking, so it’s probably a better choice.
    - wahern 7y ago
      You can still easily blow up memory with unions, which makes it easy to lock up Linux, which notoriously performs poorly under memory pressure.
      - saagarjha 7y ago
        Just set a memory limit on the process.
      - lilyball 7y ago
        A non-backtracking regex engine like re2 should be linear with respect to the regex size and can be configured with a memory budget.
        wahern 7y ago
        The number of DFA states can explode exponentially. It's a real problem, especially if you're compiling untrusted expressions off the internet. Evaluation is linear, but you're just evaluating your own password. In this scenario, it may make sense to just use a simple backtracking implementation, though as you alluded to early there aren't many simple ones around.
        pjscott 7y ago
        RE2, at least, will fall back to an NFA-based matcher if things get too pathological.
daxelrod 7y ago
Counterpoint: if you allow your browser to run JavaScript, it’s already executing arbitrary regexes it finds on the Internet.
- closeparen 7y ago
  The browser is, the passwords manager is on the other end of an IPC mechanism with a hopefully small and well-defined interface.
  - daxelrod 7y ago
    My point is that it is possible for your password manager to sandbox regex execution at least as well as your browser does. I totally agree with your concerns about scope creep increasing the attack surface.
ben509 7y ago
But it's not executing a match, it's creating a random password picker. That's exactly equivalent to parsing the pattern where the actions on terminals are to generate random characters.

I love this idea, though I'm not sure I want my password manager executing arbitrary regexes it finds on the Internet.

saagarjha 7y ago

If you restrict it to “formal” regular expressions you’ll stay out of “arbitrary code executing on a Turing machine”.

wahern 7y ago
Regular expression engines are notoriously buggy. You definitely wouldn't want to pass random expressions to libpcre. Web browsers are already running random expressions from the internet, but their regex implementations have proven the rule by being fodder from exploit writers. In any event, requiring a password manager to pull the engine from Firefox or Chrome wouldn't be cool. They're more likely to use libpcre or re2, but see above. The NAPTR DNS record type uses regular expressions for domain rewriting: https://en.wikipedia.org/wiki/NAPTR_record https://en.wikipedia.org/wiki/NAPTR_record Not many DNS libraries support that record type as it adds alot of problematic bloat.
- saagarjha 7y ago
  libpcre is exactly the implementation I’m not talking about, because it supports too much. I think re2 doesn’t do backtracking, so it’s probably a better choice.
  - wahern 7y ago
    You can still easily blow up memory with unions, which makes it easy to lock up Linux, which notoriously performs poorly under memory pressure.
    - saagarjha 7y ago
      Just set a memory limit on the process.
    - lilyball 7y ago
      A non-backtracking regex engine like re2 should be linear with respect to the regex size and can be configured with a memory budget.
      - wahern 7y ago
        The number of DFA states can explode exponentially. It's a real problem, especially if you're compiling untrusted expressions off the internet. Evaluation is linear, but you're just evaluating your own password. In this scenario, it may make sense to just use a simple backtracking implementation, though as you alluded to early there aren't many simple ones around.
        pjscott 7y ago
        RE2, at least, will fall back to an NFA-based matcher if things get too pathological.

daxelrod 7y ago

Counterpoint: if you allow your browser to run JavaScript, it’s already executing arbitrary regexes it finds on the Internet.

closeparen 7y ago
The browser is, the passwords manager is on the other end of an IPC mechanism with a hopefully small and well-defined interface.
- daxelrod 7y ago
  My point is that it is possible for your password manager to sandbox regex execution at least as well as your browser does. I totally agree with your concerns about scope creep increasing the attack surface.

ben509 7y ago

But it's not executing a match, it's creating a random password picker. That's exactly equivalent to parsing the pattern where the actions on terminals are to generate random characters.