Posted by: jonkatz | January 14, 2014

Real-World Crypto, Day 2, Session 2

The second session was on encryption. Jonathan Trostle kicked things off with a talk about authenticated encryption. Besides the “standard” security goals, he mentioned the idea of misuse resistance which requires, roughly that nonce reuse by the sender only leaks whether the same message is encrypted twice (using the same nonce) but otherwise does not breach privacy or authenticity. Jonathan’s talk focused on “lightweight” authenticated encryption schemes, that aim to minimize network overhead (i.e., ciphertext length) as well as the amount of energy expended per encrypted byte.

One point he made, which is obvious but nevertheless bears repeating (especially in light of the CAESAR competition), is that there is unlikely to be a single “best” authenticated-encryption scheme. The best scheme to use depends on the application (e.g., how many messages will be encrypted using a given key) or the deployment environment (e.g., hardware/software, or the relative cost of computation vs. transmission). It would be useful, therefore, to have a set of algorithms standardized, suited for different uses.

Tom Shrimpton spoke next about format-transforming encryption. (I had heard a previous talk on this topic by his student, Kevin Dyer.) The basic goal here is to make encrypted data “look like” other data so as to prevent it from being filtered using deep-packet inspection (DPI), as several countries do. DPI looks at payload-level information, including the data itself as well as information about what applications are being used. “Regular” encryption does not help here, since the very fact that encryption is being used may cause the packet to be filtered out; more specifically, the DPI may be using a whitelist of allowed applications and/or words. Previous work in this space was slow, inflexible, and lacked empirical validation.

So, the goal is to develop a (private-key) cryptographic transformation that makes arbitrary traffic look like “benign” traffic from some other application. The transformation will take as input a [specification of a] set of strings that the DPI will classify in the desired way, and output ciphertexts that will match the desired classification. This is very flexible, since the desired format can be changed, as needed.

Almost all the DPIs evaluated use regular expressions (or something close to that) to perform filtering. So the specification of strings that will be allowed to pass the DPI corresponds to a regular language, that furthermore can be learned from the traffic that is allowed to pass.

To map ciphertexts to words of the regular language, the key insight is to using ranking, that is, an efficiently computable/reversible map from integers to words in the regular language. (This was shown to be possible by Goldberg and Sipser in 1985. It turns out that this gives exactly the rank of a word in the lexicographic ordering of the words in the language) Given this, the solution is relatively straightforward: encrypt the plaintext as usual to get some ciphertext; view the ciphertext as a series of integers; then map these integers to words of the language. There are, as is to be expected, several practical difficulties that emerge in trying to get this to work in practice, but Tom and his co-authors show that this can be done.

One question I was left with was whether the approach can be applied to DPI based on blacklists. While it is true that the complement of a regular language is still regular, the complexity of ranking depends on the size of the regular language [sic — see below] and so may get too large. (In the Q&A, Tom claimed that everything still works, so I guess I’ll have to look in the paper for details. Update: after reading my original post, Tom clarified that the complexity depends on the size of the DFA for the language, not the size of the language. Since a regular language and its complement have DFAs of the same size, everything works out fine.)

In the final talk of the session, Mike Bond spoke about “Crypto as a service,” i.e., providing crypto for other organizations. (This is something his company, Cryptomathic, is working on.) This raises a number of practical questions, such as backing up keys, updating keys, and achieving key separation. There is also the question of making the crypto API useable (and understandable) to the client.  He gave a walkthrough of a banking application that might use the service. Admittedly, this was a bit outside my expertise.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: