Study group: Virtualisation

Today's study group was led by Dan and Marcin on the topic of virtualisation: the creation of virtual environments to emulate the physical environments on which software is designed to run. In a traditional computer system, application multi-tasking is enabled by the OS, a software layer in between hardware and applications which manages shared resources and protects applications from one another. Modern virtualisation is the natural next step: allowing multiple OS's to share the same hardware (whilst remaining isolated from one another). This is particularly desirable in the context of cloud computing, facilitating dynamic resource provision which is highly flexible to current demand and permits sales in small units as multiple customers can share the same hardware resources.

However, it isn't trivial because each OS has the same 'ring zero' privilege level, so how does the server now decide which applications get what, and when? The solution to this is to insert another layer in between the hardware and the multiple operating systems, called a virtual machine manager (VMM), which is endowed with 'ring -1' privileges and tasked with the responsibility of allocating resources between OS's and of isolating them from one another. In particular, no VM should be able to access the data or software of another VM (either directly or via a side-channel) or to affect VM availability.

Economic motives have driven the increasing trend towards virtualisation, but whilst it makes 'good business sense' it introduces novel security problems which need to be understood and dealt with. The VMM is designed in such a way as to protect a VM from other potentially malicious VMs on the same server, but how can we be sure if this objective has been achieved?

The first paper we looked at, "Hey, You, Get Off of My Cloud: Exploring Information Leakage in Third-Party Compute Clouds" (Ristenpart et al., 2009) [pdf], explores the possible vulnerabilities of virtualised cloud services by way of a case study. Amazon EC2 has three levels of infrastructure: a region (e.g. US, Asia, etc), an availability zone (i.e. a data centre), and an instance type (e.g. Linux 32-bit). The user creates a VM image and asks Amazon to 'run' it, at which point it is placed onto a physical server (and acquires an internal and external IP address and domain).

The authors describe the three-part challenge facing a would-be attacker:

1. To 'map' the address space of the cloud and instantiate a VM on the desired machine (i.e. the one hosting the target VM).
2. To check for co-residency (i.e. confirm desired placement).
3. To attack the target VM (for example, extract information).

Their subsequent investigation uncovers possible strategies for acheiving each of these goals, and leads naturally to straightforward recommendations for improved security:

1. The address space can be 'mapped' simply by launching VMs with different parameters and seeing what IPs they are assigned. It turns out that 'similar' requests are placed in 'similar' areas of the map, so that carefully chosen parameters can increase the probability of being placed on the same server as the target VM - even more so if the launch can be timed to coincide. (Non-static IPs would remove the possibility to do this).
2. The most conclusive check for co-residency is by observing the 'Dom 0' address of a packet sent to or from the target (each VMM has an IP address associated which will be attached to any packet passing through it). Alternatively, round-trip times for packets sent to the target can be measured: if these are small (or, if they are similar to those of packets sent from the adversary to itself), co-residency is likely. Lastly, numerically close IP addresses can also be an indicator. The authors suggest security policy mitigations to increase the challenge to the attacker.
3. Having achieved and confirmed co-residency, the attacks they suggest relate to previously-discovered micro-architectural strategies, such as side-channel leakage from shared cache memory (see, e.g., "Cache-timing attacks on AES" (Bernstein, 2005) [pdf].

The second paper we looked at, "NoHype: Virtualized Cloud Infrastructure Without the Virtualization" (Keller et al, 2010) [pdf], proposed to mitigate the vulnerabilities of cloud infrastructure by getting rid of the virtualisation layer. They justified this by observing that the increasing trend in the number of cores-to-a-processor means the benefits of fine-grained provision will no longer rely on the ability to put multiple VMs on a single core. They thereby set out to demonstrate that some of the tasks performed in software by the VMM could be equally well performed in hardware, highlighting ways in which existing technology could be tweaked to achieve this as well as identifying gaps which would require new technologies to fill.

Theory and practice for hash functions

This week many members of the group have been in Cambridge for the Newton Institute workshop titled 'Is Cryptographic Theory Practically Relevant?' The workshop was my first encounter with the wider cryptographic community and I thoroughly enjoyed the talks and the atmosphere during my time at the Newton Institute. I particularly enjoyed Bart Preneel's discussion of hash functions [video], with particular focus on the SHA-3 competition. Hash functions are crucial to many cryptographic applications, so naturally the competition is being closely followed by many in the cryptographic community, but it was noted that the amount of active researchers in the field is surprisingly low, particularly when compared to the AES competition.

There are many requirements of a good hash function, but there is still a discussion on exactly what properties the winning entry should satisfy. It is vital that the security definitions are formulated correctly and that they accurately reflect practical needs, particularly when the hash function is iterated. In 2004 Maurer et al. [pdf] introduced indifferentiability as a way of using random oracles as a proof method, however in 2011 Ristenpart et al. [pdf] showed that this is not always enough when composition is concerned, and in keeping with the theme of the workshop the the gap between the theory and the practical applications was in fact considerable.

In 2008 60 submissions were made to the SHA-3 competition, and the winner from the final 5 entrants will be picked at some point in 2012. There are many attacks on Merkle-Damgard constructions [pdf] [pdf], so designing a new construction method has been a major feature of the competition so far. Bart Preneel noted that his student Bart Mennink has made some considerable progress in understanding the various constructions including the sponge [details], and more work in this area will help the community provide more precise and effective security definitions and create tight security reductions from which meaningful conclusions can be drawn. The point was made that industry was advised to stop using MD5 in the mid-1990s but this advice was largely ignored until 2009. Many papers attacking SHA-1 have been withdrawn, and in the community it is not an acceptable suggestion that this surprising lack of progress is due to the strength of the hash function and in fact more work needs to be done. These points were very effectively portrayed with images of the Golden Gate bridge shrouded in varying levels of fog.

Work analysing the SHA-3 candidates was highlighted ([pdf] , [pdf] , [pdf] ) and the concluding remarks of the talk noted the open questions such as:

• Are standard model security proofs possible, and if so how will the new proof approaches help the rest of the cryptographic literature?
• Are improvements to the current indifferentiability bounds possible?

Mathematical and practical security problems not directly related to cryptography

The third talk of the first day of the workshop "Is Cryptographic Theory Practically Relevant?" was given by David Naccache (a video of the talk is available online). In his abstract, he noted that the talk was intended for people bored by 'random oracles, lattices, security reductions and games'. As described by the title, the problems he discussed were not directly related to cryptography, but rather nice mathematical problems that arose from a number of practical security problems.

The first problem had to do with the depiction of data on radar charts. The point was to rearrange the axes of the chart to maximize the area depicting the attributes of ones employer, while minimizing the area depicting the attributes of their competitors. This problem was probably the least related to security, but a general theme throughout his talk was that many mathematical problems are interesting; you just need to convince people to give you funding for looking at them.

The second problem was related to physically protecting electronic devices or chips from tampering by embedding them in a 3D mesh of metal. This lead to the study of random Hamiltonian cycles in 3-dimensional planar graphs of a cube-like structure. The goal was to end up with a 'cage' with has the device embedded in the center, such that it is hard to drill towards the device. However, due to the particular structure of the graph, a single cage would always leave regularly spaced holes in between the edges. Fortunately, it is possible to interleave a smaller cage inside the bigger cage, thus neatly filling up the holes. These cages were constructed taking a regular Hamiltonian cycle in the graph and then transforming them randomly to get rid of the regular structure.

David went on to talk about the third problem, which arose from the probing of chips. It is possible to probe chips with special machines, in order to analyze what exactly happens on these chips. To somehow defend against this, David and his students looked at the problem of physically 'scattering' a secret on the chip, thus maximizing the physical distance between parts (such as shares from secret sharing). The chip was modeled as an n by n chessboard and the shares of different secrets were modeled as colored pawns. You have pawns of n colors and must place them on the board such that pawns of the same color are as far from each other as possible. This problem turned out to be related to the mathematical theory of tiling. David noted that the solutions obtained would always be periodic, which might be undesirable from a security point of view. Thus, some care must be taken to make periodic solutions non-periodic, which possible reduces the distances between pawns of the same color slightly. As someone in the audience pointed out, it is possible to extend this model by adding colorless pawns to model unimportant information that does not need to be scattered.

At this point, David was running out of time and offered to take questions. However, his next subject was titled "How to identify quickly" and the audience encouraged him to use the remaining two minutes to show how quickly one could identify. He used these last few minutes to describe how to speed up comparisons of a biometric scan to a database of biometric data for identification purposes. The trick was to add additional data such as the person's height and then sort the database entries by the distance from the measured height to the recorded heights. This could be extended to several types of data (he gave height and IQ as examples because they were independent) but this might require some extra statistics to remove dependence between these attributes. Unfortunately, he really was out of time at this point and did not get to talk about other problems that he had prepared. More information can be found once his slides become available, but he said that if people were interested in these problems they should send him an email as well.

The practical application of cryptography to international card payments

The following is a summary of the talk "The practical application of cryptography to international card payment" given by John Beric and Mike Ward from Mastercard International on day 2 of the workshop. The core topic of the talk was EMV, a global system for debit and credit card transactions based on smart cards.

After arguing for the necessity of card payments, the first speaker made it clear that the real world does not always implement what cryptographers like to see because of the long life cycles of the system. Then, he outlined the history of distance payments, in the form of cheques, magnetic stripe card transactions, and offline EMV transactions. Cheques provide physical evidence and are hard to forge, but they are slow to process and the signature check cannot be made at the time of the transaction. The only advantage of magnetic stripe cards over cheques is the faster processing, at the cost of no physical evidence and little protection against copying of the card. To make these acceptable to customers nevertheless, the banks operate a policy of zero liability on the side of customers, which in turn the facilites fraud.

Finally, offline EMV transactions offer evidence by a digital signature, and it is believed that the cost of breaking the scheme exceeds the possible profits. This contrasts the case of magnetic stripe cards, where the investments required to copy a card are rather low. Nonetheless, the world of EMV transactions is not perfect as there might be corrupted terminals intercepting the PIN or not displaying the correct amount of a transaction on the display. There are plans to mitigate this by employing the users' smartphones as part of the trusted computing base. But of course, cards and PIN can be stolen as well as smartphones.

The second speaker highlighted some technical details. The central theme in the implementation of EMV seems to be that the specification recommends a high level of security; however, the recommendations are not always followed in favour of the flexibility of a globally employed system. In some regions for example, the majority of cards do not support digital signatures but use a so-called static signature, which only provides authentication of the card instead of authorisation of a specific transaction. In the same spirit, the failure of a cryptographic check may not lead to the abortion of a transaction because a part of the system might simply not support the necessary cryptographic schemes. While the specification recommends the use of AES, implementations mostly use 3DES and even proprietary ciphers and signature schemes.

The talk was concluded by an outlook to a future specification, where elliptic curve cryptography (ECC) will be adopted. An open question related to this is whether Schnorr signatures will be used. In the question session, a member of the audience suggested that the emphasis should be on the simplification of the historically grown specification instead of the introduction of ECC, which he accounts more to the economic interests of the patent holders involved.

Cryptography with Work-based Corruptions and the Combinatorics of Anonymity

The third talk on Wednesday was given by Aggelos Kiayias (University of Connecticut). Protocols in the MPC setting  are designed to allow a group of n players compute a function on n arbitrary inputs. The protocol must at least ensure input privacy and output delivery to the clients. An adversary willing to make the protocol fail, can simply  break the assumption which relies on. But most likely it will try to corrupt more than t players (for some security threshold t). How is this corruption actually performed? Theoreticians just assume this is done instantly and comes at no cost. The reality is rather different: each player may have different resources or security parameters. 


The question Aggelos threw was whether it is possible to come up with an appropiate model. He proposed to use resource-based corruptions, where a symbolic amount of coins (or resources) is assigned to each player, e.g. an adversary will spend less time breaking weak passwords in dictionary attacks. The adversary can corrupt the player if it spends at least s coins in such operation. Things are more complex when all the players look identical for external observers (hidden diversity). It can be achieved by e.g. randomly permuting the position of the players in the cloud. 

He explained a game to measure the amount of coins that the adversary will need in order to corrupt (more than t) players. This is what he called 'Combinatoric Game of Anonymity': we have a system conformed with buckets and balls. Buckets are players, and their size is the number of balls required to fill them up (corrup them). Assuming the only feedback we get from the system is whether or not a bucket is filled, how do we know the amount of balls required to collapse the entire system? Clearly if we do know the exactly amount of balls, then we are back in the classical situation, and the players can be considered to be instantly corrupted by a sufficient enough resource-powered adversary. There are intermediate states of ignorance, though. For example the adversary may only know  n and that some (unknown) bucket has size s (size-only), or n and the maximal size ( max-only).

Another interesting question was whether we can discretize the amount of work needed to break a cryptosystem. He explained the concept of exact hardness for some threshold value epsilon. It is used to compare functions according to their inversion ( gives the number of steps needed to succesfully carry out the compilation with probability greater than epsilon). How easily can the exact hardness be computed? Bounds can be provided in the random oracle model, and ranges in the standard model.
 There are several interesting properties. For example, given a family of functions, find a value T such that it is not posible to amortize the exact hardness of any function in the family beyond T ( that is, the exact hardness of any function in the family for (any given arbitrary) epsilon, is greater than T times a finite linear combination of the exact hardness of arbitrary functions in the family). Another property is the indistinguishability, when an adversary can not infer which function is better to attack first.

Is Cryptographic Theory Practically Relevant? (Day 1)

Yesterday the workshop wondering about the practical relevance of cryptographic theory started at the reknowned Newton Institute in Cambridge. There was a staggering number of participants including people from both industry and from academia, covering a vast range of cryptographic theory and practice.

The workshop started with Serge Vaudenay's talk ominously titled "Privacy in Deniable Anonymous Concurrent Authentication with Setup is Impossible: Do we Care?". His choice of title had already received some critical comments in the comments section of Jon Katz's blog, so I was looking forward what the title referred to. Before Serge came to the main topic so to speak, he discussed another issue that fits very well with the Dagstuhl seminar from two weeks ago.

Last Eurocrypt he and his coauthors looked at statistical attacks on RC4.There they estimated certain complexities using assumptions about certain variables being independently distributed in some way. Since then, they have tried to validate these assumptions in practice by running experiments. It turned out that the variables behaved quite differently then assumed and expected, so a different model (related to modelling tornados) was needed. Turning the workshop's theme on his head, Serge concluded that practice can be relevant for theory.

He continued to talk about deniability in certain protocols. His main point was that a notion like deniability is extremely brittle. It is known how to achieve deniable authentication in the standard model, but as soon as a random oracle is added into the mix, the deniability no longer holds. Similarly, once the right kind of trusted hardware token is available, deniability can no longer hold. The point is that these extra powers are more useful to the adversary than to the protocol designer and from the literature on for instance receipt-free elections they don't come as an entire surprise, but it is still somewhat strange to see in action.

Serge's talk contained a third part on achieving different kinds of privacy in authentication protocols relevant for RFID tags, where he adapted a security definitions to bypass impossibility notions and realign with practice. The combination of the three parts of his talk was a clear reminder of the limitations and potential dangers of conducting cryptographic theory in complete isolation from practice, as one might well end up with unrealistic models or assumptions. In other words, a great start to the workshop.

Cryptomathic HSM Portal

Mike Bond from Cryptomathic gave a talk on their HSM Portal. A Hardware Security Module (HSM) is a certified physically tamperproof device that is used and often mandated in areas such as banking.
HSMs are ancient technology by today's standards, both in respect to the algorithms, parameters and modes in use and the APIs.

Yet an HSM is not "security" in and of itself but a module in a larger system: building such a system securely on top of a HSM is by no means easy.
HSM portal is a solution that offers an higher-level environment to build a HSM-based system. Customers can get the technical details (key length, key refresh time period, algorithms, modes of operation sorted by Cryptomathic and delivered in a configuration file). An API call might now look like "ENCRYPT file FROM alice TO bob", in other words something that non-cryptographers have a chance of getting right.

Three types of crypto-users were mentioned: home-growers, that know little of cryptographic theory and devide their own ad-hoc "cipher" when needed; passable theorists (among whom Mr Bond counts himself) who know the theory and core theorists who are "most likely to have written the theory and founded their own start-up company based on it".

Mr Bond made the point that industry does not care about security as much as compliance. This reduces the incentive to apply theoretical advances in cryptography. An algorithm, mode of operation or API is good if it is standardised and ticks certain boxes rather than if it has a formal proof of security.
In the case of API attacks, compliance boils down to specifying what an honest user should do with the API, not what a possibly dishonest or careless user CAN do.