FINDING · EVALUATION
DFA state-space explosion makes DFA-based FTE impractical for many realistic network-monitor regexes: the minimum DFA for `(a|b)*a(a|b){16}` has 131,073 states requiring 266 MB of precomputed tables, while the equivalent NFA has only 36 states requiring 73 KB — a reduction of roughly four orders of magnitude. Some formats in the Snort corpus required up to 383 MB under DFA-based ranking, rendering them prohibitive for deployment.
From 2014-luchaup-libfte — LibFTE: A Toolkit for Constructing Practical, Format-Abiding Encryption Schemes · §4, Table 6 · 2014 · USENIX Security Symposium
Implications
- When selecting target protocol formats for FTE, evaluate the NFA state count rather than the DFA state count — regex patterns with bounded repetition (e.g., `.*a.{N}`) can produce exponentially larger DFAs that make the scheme undeployable.
- Audit all regex-based FTE format specifications against DFA explosion before shipping a transport; fall back to NFA-based ranking whenever DFA construction exceeds available memory.
Tags
Extracted by claude-sonnet-4-6 — review before relying.