Cryptography: Theory and Practice

[#1]

"In theory, there is no difference between theory and practice. But, in practice, there is."  Yogi Berra

This week was a busy one for those involved in the field of cryptography.  Around this time every year "Crypto", the annual conference for the International Association for Cryptologic Research is held on campus at the University of California, Santa Barbara but this year it was co-located with a couple of other related events. Overlapping with Crypto was "CHES", the workshop on Cryptographic Hardware and Embedded Systems, which is also an IACR event, and following on from these two NIST (the National Institute for Standards and Technology) are holding the second SHA-3 Candidate Conference as part of the process of selecting the next standard for a cryptographic hash function.  I attended the Crypto conference and also took advantage of the “reciprocal hospitality” arrangements with CHES to attend a number of their sessions.  Sadly, I didn't get to go to the SHA-3 conference but there was a great deal of discussion of the candidate algorithms at the other two events.

Unlike my previous company, Juniper is not a "cryptography company".  Juniper is one of the world’s largest vendors of network security products but security and cryptography are different fields. Cryptography is to security as structural engineering is to architecture.  Just as the architects who wants to build the tallest towers or the greenest homes or the most grand halls need to understand the latest in structural engineering techniques, we at Juniper need to understand the state of the art in the field of cryptography to build the world’s most advanced security products.  Crypto and CHES are fora in which ideas at the leading edge of cryptography are being presented; Crypto approaches the field from a fairly theoretical point of view while CHES is much more targeted at the practice.

The program for Crypto was a grueling schedule including 38 refereed papers, a panel session and an invited talk. I'm not going to talk about the often arcane details of the papers. Instead I will focus on some of the areas covered and discuss why this theory is (or will in the future be) relevant to us.

First up was a session on "Leakage". This was not referring to oil in the Gulf of Mexico or to WikiLeaks but instead it was about how can we build ciphers and protocols that are secure even when the attacker can acquire some limited knowledge of what is going on inside the system.  Many security devices have been attacked over the years because subtleties of the implementation "leaked" information about what was going on inside what was otherwise considered to be a "black box". Examples include timing attacks against crypto-enabled servers, power analysis on smart cards and Bleichenbacher's attack on SSL. The three papers in this session looked at various ways we can build ciphers that are still secure even when some amount of information does get leaked.  This can be very useful when building real system, but as I'll discuss later, the people at CHES take a different approach to this.

Next up we had a session on Lattices. These are mathematical constructs that are the basis of some very hard mathematical problems, and hard problems often make strong crypto systems. Lattice-based crypto systems are especially interesting because it is generally thought that these problems are not just hard for classical computers to solve but also hard for quantum computers. This means that the resulting ciphers should, at least in theory, still be secure when we have quantum computers. Since QC is still a long way off we don't need these yet, but technology often advances much faster than expected so thinking about these problems now is probably a worthwhile insurance plan.  They also turn out to have some useful properties when it comes to homomorphic encryption, about which I'll talk some more in a moment.

The invited talk was entitled "Zero Knowledge - 25 Years". Rather than being a lament on our lack of understanding, it was actually about a field of cryptography known as "zero knowledge proofs". These are protocols that allow, say, Alice to prove to Bob that she knows the solution to a puzzle without telling Bob anything about what the solution is. It might sound a bit abstract then think about this way: Alice might want to prove to Bob's server that she has the password to her account, without ever divulging anything about the password. By using zero-knowledge proofs we can build authentication protocols that are immune to a whole stack of different types of attack from both eavesdroppers and insiders. Could be sort of handy, don't you think?

The three sessions that I found most interesting, and perhaps the ones with the most profound possibilities for the future of networked computing, were on homomorphic encryption, multi-party computation and computation delegation. Homomorphic encryption systems are ones that allow you to give someone the encryption of some values (say A and B) and they can compute for you the encryption of the result of some function of those values (e.g.. A+B or A*B) without being able to decrypt the individual values. Why? Because then you can leave your business's encrypted Personally Identifying Information on some untrusted cloud computing service and still use those untrusted computers to do the processing, even though you won't let them decrypt the data itself. Such systems are still far too slow and complex for real-word applications but huge progress is being made.  Multi-party computation and computation delegation, as you might expect, involve processing data that are distributed among a number of people (or servers). Unlike regular distributed computing though, this is about encrypting and distributing the data in such a way that no single part is sufficient to work out what the raw data are, but still allowing the data to be processed.  Again, this has direct applications in outsourcing your processing to third party servers while maintaining the security of the data. Sadly, again the existing state of the art is still too slow to be much use but it is also improving rapidly. As the availability of cheap compute cycles in the cloud continues to grow these techniques will start to become viable and could well change the way we go about processing our data.

Other sessions in Crypto included "Pseudorandomness", "Quantum Cryptography" and a number more.  If you need to know more about "Equivalence of Uniform key Agreement and Composition Insecurity", or any of the other papers, you can get the proceedings from online book sellers or well-stocked university libraries: ISBN 3642146228

Over in the other lecture hall the CHES workshop was busy presenting 30 papers on the practicalities of building and breaking implementations of cryptographic systems. Three sessions (nine papers) looked at aspects of efficient implementations of cryptographic algorithms. Efficiency in implementation is a perennial problem for both very small and very large systems.  If you are building a contactless smart card you can't expend much energy encrypting a bit of data because the inductive coupling from the reader to the card cannot convey much power.  If you are building a full duplex 100 gigabit per second line interface for a router you can't expend much energy encrypting a bit because every single nanojoule used on each bit amounts to 200 watts of heat to dissipate out of the interface card!  Understanding how to build the most efficient implementations is very important to both.

Another common theme in CHES, with more than half a dozen papers, was looking at side-channel attacks. I mentioned the idea of side-channel attacks above when talking about "Leakage"; side-channel attacks are ones in which we take measurements of some cryptographic implementation, such as, the amount of power being consumed by a circuit or the time taken be a chunk of executable code, and we use this to deduce something about the state of the system, ideally something about the key. These papers were fairly evenly split between "attack" and "defense" paper, which shows how this type of research is a cat-and-mouse game that is going to keep on running for quite a while. Side channel attacks can be combated by a number of measures ranging from trying to minimize the signal that escapes (filtering), through adding random delays to the processing of data to subtle techniques where random values are algorithmically combined with the data being processed and then reversed out afterwards.

The remainder of the talks at CHES covered topics including fault induction attacks (getting keys out of systems by glitching the processor), pseudorandom functions and random number generators, and a bunch of evaluations of various SHA-3 candidate algorithms from a hardware perspective.  Lots of good stuff; I only wish I'd had the time attend the last day and a half of CHES but sadly the office beckoned.  I shall be getting a copy of the conference proceedings for this conference: ISBN 3642150306

Trying to condense a week of intense presentations on the leading edge of cryptographic study into a single blog post is pretty much impossible but I hope that this has given you a taste of the sorts of things cryptographers get up to.  In case you are interested in finding out more, I include below a bunch of links to some readable introductions to some of the topics I have discussed.  Happy reading!