Tom Ristenpart

From Credit Cards to Censorship Circumvention:
Building Encryption Schemes with Specialized Ciphertext Formats


Traditional symmetric encryption schemes map plaintexts to ciphertexts
that are unformatted bit strings. In this talk we will explore
encryption that takes into account formatting requirements for
ciphertexts. We start with format-preserving encryption (FPE), for which
we gave the first cryptographic definitions in 2009 and which is now
used widely in industry. FPE ensures that ciphertexts preserve the
format of the underlying plaintext, for example enabling the encryption
of credit card numbers to yield ciphertexts that are themselves valid
credit cards. We will present definitions of FPE and a generic
construction in the form of Rank-Encipher-Unrank, which combines classic
results regarding the ranking of languages in the sense of
Goldberg-Sipser with small-domain ciphers to produce FPE schemes that
work for formats described by arbitrary regular languages. We will then
overview our recent results on building fully secure small-domain
block-ciphers, giving a new paradigm for building PRPs from pseudorandom
separators, a primitive we introduce. We will finish with a recent
generalization of FPE called format-transforming encryption (FTE). Here
we use a variant of an Encrypt-Unrank approach to implement encryption
tunnels whose ciphertexts on the wire are guaranteed to match against
arbitrary regular expressions.  This enables, for example, confuse
Internet censors that use regular-expression based deep-packet
inspection to identify and block circumvention tools such as Tor.

This talk will cover joint work with Mihir Bellare, Scott Coull, Kevin
Dyer, Phil Rogaway, Thomas Shrimpton, Till Stegers, and Scott Yilek