A toolkit for constructing practical, format-abiding encryption schemes.

What is Format-Abiding Encryption?

A format-abiding encryption scheme is an encryption scheme where the plaintext and ciphertext must have a specified format. Format-abiding encryption schemes are used in a range of applications: in-place encryption in databases, in-browser encryption for web forms or per-message encryption of network traffic for censorship circumvention. In the most general case a format is a language, and in current practice it is usually expressed as a regular expression.

In Format-Preserving Encryption (FPE) the plaintext and ciphertext have the same format. FPE was introduced by Bellare et al. [3]. For instance, in the case of credit-card numbers, FPE transforms plaintext, which is a string of 16 decimal digits, into ciphertext, which is also a string of 16 decimal digits.

In Format-Transforming Encryption (FTE) the plaintext and ciphertext have different formats. FTE was introduced by Dyer et al. [2] as a way to circumvent network censors that perform deep-packet-inspection to block target protocols, such as those used by Tor.

Format-abiding encryption relies on a method called rank-and-encipher: ranking transforms the plaintext into an integer, which is then encrypted, and then unranking transforms the encoded integer to the ciphertext.

LibFTE

LibFTE is the first general-purpose library that introduces a unifying framework for general-purpose development and deployment of FPE or FTE schemes using formats specified by regular expressions. LibFTE also overcomes some technical limitations of the prior FTE software. Previously, ranking was performed using the Deterministic Finite Automata (DFA) representation of regular expressions, which means that format-abiding encryption was feasible only for regular expressions for which the DFA representation could be built. Luchaup et al. [1] give new algorithms that allow format-abiding encryption to work starting with the Nondeterministic Finite Automata (NFA) representations of regular expressions. When both representations are possible, there is a trade-off between choosing a DFA or a NFA representation: DFAs are usually larger than the NFAs, sometimes prohibitively large, and the library initialization time is large too when using DFAs. However DFAs lead to faster ranking algorithms. As [1] explains, the difficulty of configuration decisions goes beyond selecting a DFA or NFA representations. For this reason LibFTE also includes a configuration assistant to help the users with such design decisions.

Software

You are encouraged to download it and try it by following the README directions.

Publications

  1. LibFTE: A Toolkit for Constructing Practical, Format-Abiding Encryption Schemes
    Daniel Luchaup, Kevin P. Dyer, Somesh Jha, Thomas Ristenpart and Thomas Shrimpton
    To appear in the proceedings of USENIX Security 2014
  2. Protocol Misidentification Made Easy with Format-Transforming Encryption
    Kevin P. Dyer, Scott E. Coull, Thomas Ristenpart and Thomas Shrimpton
    In proceedings of the ACM Conference on Computer and Communications Security (CCS), 2013.
  3. Format-Preserving Encryption
    Mihir Bellare, Thomas Ristenpart, Phillip Rogaway, and Till Stegers
    Selected Areas in Cryptography, pages 295-312. Springer-Verlag, 2009