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
-
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
-
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.
-
Format-Preserving Encryption
Mihir Bellare, Thomas Ristenpart, Phillip Rogaway, and Till Stegers
Selected Areas in Cryptography, pages
295-312. Springer-Verlag, 2009