A Modular Framework for Building Variable-Input-Length Tweakable Ciphers

For this weeks study group I presented a paper by Shrimpton and Terashima from AsiaCrypt 2013[1]: A Modular Framework for Building Variable-Input-Length Tweakable Ciphers. Starting from the bottom, the authors take a modular approach to build an Authenticated Encryption (AE) scheme, starting with some relatively simple primitives and extending their functionality until full AE is supported. So, the paper can be broken up into 4 sections:

1. Introduce our primitives: Tweakable Block Ciphers (both Beyond Birthday fixed-input-length and Variable-input-length)
2. Combine these with their new Protected IV (PIV) to form an Arbitrary Input Length Tweakable Block cipher (AIL TBC)
3. Provide two explicit examples of such constructions
4. Build a secure AE scheme out of a VIL TBC

From a practical point of view, Part 3 is arguably the most interesting, because it provides explicit examples of secure constructions and (when combined with 4) yields an AE scheme that may be secure beyond the birthday bound (which is the point at which most symmetric security proofs break down).
This blog will mainly focus on Part 2, and readers are encouraged to read the full paper for more details on .

Background

Very briefly, let us sketch a few key notions:

• A TBC (Tweakable Blockcipher) acts like a family of block ciphers, one for each tweak. If it is secure, then any change in the tweak should make the TBC act completely differently, which we call an STPRP (for strong tweakable pseudo-random permutation).
• A primitive is VIL (Variable Input Length) secure if it is secure when queried on messages of different lengths
• A primitive is AIL (Arbitrary Input Length) secure if it is secure when queried with message of any (single) length
• Authenticated Encryption was discussed in a blog post last year[2] and (roughly) corresponds to secure communication between two people sharing a key.
• The Birthday Bound on n bits is roughly $q^2/2^n$, and is the point many symmetric security results break down. A scheme that is still secure for $q>2^{n/2}$ is known as Beyond Birthday Bound (BBB) secure.

The Protected IV (PIV) construction

The key aim of the paper was to build a secure VIL TBC (ie an STPRP) from a fixed-width TBC with variable length tweak (F) and a VIL TBC (V). To do so, the authors describe the PIV (for Protected-IV) scheme. A diagram of the construction is given to the right, and we thank the authors for permission to reproduce their graphic. It can be seen as an extension of the SIV scheme[3], except that by re-encrypting the keeping the IV secret ("protecting" it) and letting it carry some information about the plaintext, the authors have managed to remove the ciphertext expansion required for SIV security.
The most interesting thing about the scheme is that V does not have to be secure as a VIL TBC: V only has to be secure if the tweak is never repeated (similar to the idea of a nonce-based authenticated encryption scheme). This makes V much easier to construct with (for example) a slight variant of counter mode sufficing.
The idea behind the proof is relatively intuitive, built around the fact that (because F is secure) the IV is random and doesn't repeat (up to a birthday bound term on |IV|). So, V is always called with a unique tweak, securely encrypting the X_r (or decrypting the Y_r) content, and so the output is nicely random, making the whole scheme a secure STPRP. Thus security of the scheme reduces to the security of F, V and of a birthday attack on the IV.

Instantiations and Building Authenticated Encryption

To close, the paper provided some instantiations, and explains how to extend the Encode-then-Encipher[4] concept and proof to achieve strong Authenticated Encryption from a STPRP. We didn't have time to discuss these elements in detail, but observed that to achieve Beyond Birthday security, the IV had to be twice as wide as the birthday bound we seek to pass.

References

1. A Modular Framework for Building Variable-Input-Length Tweakable Ciphers, Shrimpton & Terashima
2. 52 Things #27: What is AEAD?, from this blog
3. Deterministic Authenticated-Encryption: A Provable-Security Treatment of the Key-Wrap Problem Rogaway & Shrimpton
4. Encode-then-encipher encryption: How to exploit nonces or redundancy in plaintexts for efficient cryptography BEllare & Rogaway

Sixth Bar-Ilan University Winter School on Cryptography

This is the first of a two-part blog post has been collaboratively written for the ECRYPT-EU blog by Eduardo (University of Bristol), Marie-Sarah, Matthias and Ralph. Part 2 can be found here.

Earlier this month, from 4-7 January, a few ECRYPT-NET fellows and about a hundred others attended the Bar-Ilan University winter school on cryptography. It took place in Ramat Gan, a suburb of Tel Aviv, at the Kfar Maccabiah hotel and conference centre (named after the Maccabiah, or Jewish Olympics, that take place there every four years). The school was intense, but well organized. It was split into two parts, verifiable computation and special encryption, and so will be our coverage of it.

Part 1: Verifiable Computation

Michael Walfish, Yael Tauman Kalai, and Eran Tromer guided us through methods for verifying the outsourced computation of functions. We particularly appreciated the crystal-clear overview of all sessions, given by Michael Walfish, that emphasized how the content of the talks fit together.

Let's set the scene for verifiable computation: a client (the verifier) wants to outsource the computation of a function f to a server (the prover) who has more computing resources. But how does the verifier know that the value returned by the prover is actually the result of applying the function f to the purported inputs? A malicious or a lazy server could indeed modify the process to gain some advantages as, for instance, reducing the cost of operating a system.

Verifiable computation of f(x) comprises the following two phases:

1. Program representation (or arithmetization): The verifier (or a party he trusts) expresses the function f as a set of arithmetic constraints over a field, in terms of the input x, output y, and intermediate variables z. Each of these x, y, and z may be vectors, e.g., x=(x₁,x₂,x₃). Typically, the format these constraints needs to have is that of degree-2 polynomials that equal 0 when they (and the function f) are satisfied.
2. Solving and proving: The server must prove to the client that the solution it returns, y, is correct. The landscape of proof protocols shows a trade-off between efficiency, expressiveness and additional properties like zero-knowledge or non-interactivity. The speaker himself recently wrote a survey which is a very nice introduction to the state of the art and these trade-offs.

Yael Kalai's talks took a more theoretical approach, guiding us through the evolution of Probabillistically Checkable Proofs (PCPs). She emphasized the importance of "good" security assumptions, where "good" requires at least, and according to her point of view, that the underlying assumptions can be efficiently falsified. These theoretical worries were well founded, as most of today's verifiable computation protocols rely on SNARKs (standing for Succint Non-interactive ARguments of Knowledge) which cannot be proved secure via black-box reductions from (efficiently) falsifiable assumptions. 

Yael's talks provided also very interesting and intuitive examples. To give one, suppose that Peggy and Victor are playing chess. After a number of moves, Peggy (the prover) wants to prove to Victor (the verifier) that she has a checkmate. If Victor fails to see it, it is for Peggy easier to convince him by continuing the game (an interactive proof) until he does, rather than to explain all the possible combinations of moves without moving any piece (a non-interactive proof). This intuition of the power of interaction extends to the rest of the proof systems. Finally, she even showed us how the subject fits in the quantum framework, introducing us to the notion of non-signalling adversaries.

Eran Tromer recovered the line of Michael Walfish and focused on the details of SNARKs and how they are actually constructed. Among others, he has been writing libsnark, a C++ library that is used a lot for verifiable computation systems relying on SNARKs. He also showed us a potential application for them, called Zerocash. Zerocash is a protocol that provides a privacy-preserving version of Bitcoin. In contrast to Bitcoin, where all the transactions are public in the block chain, Zerocash does not contain information about the payment’s origin, destination or amount. The correctness of the transaction is guaranteed via a zero-knowledge proof. More details can be found here.

Part 1.5: Excursion to Caesarea and Binyamina Winery

Sun starting to go down in Caesarea.

Tuesday afternoon, we made an excursion to the remains of Caesarea, a Roman city on the Mediterranean coast that was built by Herod over 2000 years ago. To say that it had a tumultuous history would be an understatement. Our tour included a walk through a "graveyard" of columns and capitals, the amphitheatre (whose first row is still intact), and the hippodrome.

Next, we took an informative tour of the Binyamina winery. We learned that grapes are crushed with a flexible rubber material to simulate the skin of feet. For red wine, the grapes are fermented (skin, seeds, and all) before being crushed. For white wine, seeds and skin are removed (by sedimentation) after pressing, then fermented. The tannin (bitter-tasting substances) in wine comes from the seeds, skin, and maybe the material of the barrel in which it is matured. Whether wine is aged or matured in an American oak (sweeter) or French oak (more tannins, adds more complex flavours) barrel affects the final product. Tannins prevent oxidation, so red wine (with more tannins) can be matured longer. Stopping fermentation early makes wine more sweet.

After learning how wine is made, we concluded the day by learning how it tastes (using our five senses!) and enjoying a generous dinner.

The second and last part of the post can be found in the ECRYPT-EU blog.

Max Levchin Prize @ RealWorldCrypto 2016

This week saw Real World Crypto 2016 in Stanford California. The highlight was the first awarding of the Levchin prize for work in the field of practical cryptography. The prize award is donated by Max Levchin, a founder of PayPal, and two such prizes of $10,000 will be awarded annually. 

The first recipients of the award are 

• Phil Rogaway for his long standing work on developing practical cryptographic algorithms, the development of practice oriented provable security, format preserving encryption and numerous other algorithms which are used every day to secure our online world.
• The miTLS team for their work on producing a formal analysis of the TLS protocol specification, and in the process finding a number of  real world attacks on this protocol such as the triple-handshake attack.

The real purpose of the award though is to highlight work to the wider community that one can have deep and lasting impact on society by working in an area as mathematically opaque as cryptography. Awards such as this, and events such as Real World Crypto, are designed to raise the profile of applied work in this space and encourage people to apply their skills to solving the pressing security problems affecting our online world.

In the rest of the conference there was an amazing program of interesting talks (although I would say so, since I was on the panel for selecting the talks). The highlight of day one for me was the talk by Adrienne Porter Felt on usability issues related to TLS failures in Google Chrome. By collecting numerous bug reports from Chrome users the team at Google found that most errors are not due to poor server configurations (indeed most errors occur when users connect to sites such as Google or Facebook), but are due to poor client configurations. For example a significant proportion of errors are caused by device times being incorrect. So lesson: Make sure you set your clocks correctly. 

One highlight of the second day was Hovav Shacham's talk on the recent discovery of a backdoor Juniper's ScreenOS. The initial backdoor was rather uninteresting in that if a certain key combination was presented a user would be given enhanced privileges. However, on discovery of this backdoor Hovav and his colleagues discovered a more interesting potential backdoor based on the Dual-EC PRNG that could compromise the VPN traffic that Juniper is used to protect. The interesting part was that previous cryptographic focus on Dual-EC has been on products which had explicitly listed Dual-EC usage as part of their FIPS certification. The Juniper product had not explicitly listed that it used Dual-EC, so the discovery of a Dual-EC based potential backdoor could imply that many more products, by many more vendors, could be using the Dual-EC PRNG.

The talks generating the most interest on the third day were the ones explaining the new Intel SGX technology. This is a technology which allows applications to run in an "encrypted enclave" on an Intel chip; where data is held encrypted in memory and is only decrypted as it enters the chip and is processed. When it returns to memory it is automatically encrypted. At its heart this idea goes back to the original paper on homomorphic encryption by Rivest et al from the mid 1970s. However, the new Intel technology has a number of additional features which make it suitable for a modern environment. The first talk by Rebekeh Leslie Hurd introduced the overall technology and some of the attestation and communication issues needed to authenticate the enclaves, and allow enclaves to talk to each other. The second talk by Shay Gueron discussed the details of how the memory is encrypted in a way which respects the cache architecture on modern microprocessors.