Cryptography and Security in Clouds II (Zurich March 15-16 2011)

One of the highlights of the last week in Zurich was undoubtedly Rado Sion's (http://www.cs.sunysb.edu/~sion/) talk on the economics of cloud computing in relation to security. Measuring the cost of outsourcing in the cloud as cost of a single CPU cycle in "picocents", that is 10^-14$ allows one to weigh up the real economic cost of outsourcing. In particular, one can ask how many additional cloud cycles can we spend on cryptography, before its outsourcing becomes too expensive? Most talks after this, had members of the audience asking this very question. In particular, novel encryption schemes such as functional encryption may be very cool but aren't going to come cheap!

In 2009 Craig Gentry's construction of the first fully homomorphic scheme (i.e a scheme which supports unlimited computation on encrypted data) was hailed as a major theoretical breakthrough due to its obvious implications for secure computation in untrusted clouds, but could such a scheme ever be economical for anyone to deploy? Much of Sion's research has focused on answering questions like these in a far more concrete fasion than many cryptographers and cloud advocates would normally dare. The conclusions make fascinating reading. For example, http://www.cs.sunysb.edu/~sion/research/sion2010wpes-pcost.pdf analyses the cost (again, in picocents) of a variety of cryptographic schemes for home users up to large size data centres such as those provided by the Amazon cloud. Figures are calculated using the ECRYPT benchmarking (http://bench.cr.yp.to/) for AES, RSA encryption and DSA, ECDSA signatures. The authors also give figures for transferring data into the cloud and storage costs. Armed with these results they analyse various scenarios of outsourcing, namely simple storage such as that offered by Amazon S3, searching on encrypted data and secure SQL queries in the cloud. Suppose a user wants to store (but not compute on) data held in the cloud. Based on their figures they predict outsourced storage can be upwards of 2 orders of magnitude higher than local storage, even in the absence of security assurances. Searching on encrypted data turns out to only be economical in the cloud if the returned result is less than 36 bytes per query (and this doesn't take into account the cost of TCP overheads) and similarly damning conclusions are drawn for SQL queries based on current schemes.

Perhaps ironically, this doesn't imply a highly computationally expensive crypto-scheme such as FHE is economically unviable. We can envisage a scenario where a home user simply didnt have the necessary computational power on her desktop, but required computation (say a simple private information retrieval) from the database. For example, doctors requiring information on patients from a health database held remotely. It may be cheaper for the corresponding health service to provide PIR to their doctors and paying for the extra overhead that comes with outsourcing than maintaining their own IT infrastructure and still have the security guarentees provided by cryptographic schemes.

We conclude that whilst looking at the cost of outsourcing purely in terms of CPU cycles renders it useless for the most part, there are scenario-specific cases where it is economical. Businesses and home users alike will have to take a serious look at whether this is the case for them and not simply be taken in by the frenzied marketing surrounding "the cloud".

Cryptography and Security in Clouds (Zurich March 15-16 2011)

"The Cloud" is supposed to let you run a virtual machine and abstract away all details like what physical processors or disks lie beneath. But we can't hope our adversaries will be nice and stick to this ...

In the first talk we saw some examples of what can go wrong from a security perspective when you ignore what lies beneath. If two virtual machines are executed on the same physical machine, we call them co-resident and if our adversary can get his VM co-resident to ours we may be in trouble. If he can take over the physical machine for example by exploiting a bug in the hypervisor (software layer that runs the VMs), he gains complete control of our VM. Even if he's confined to his VM, he can measure the latency of operations and possibly gain a side-channel from the fact that his code uses the same physical caches as ours. Using Amazon's cloud as an example, the speakers showed that it's surprisingly easy to get co-resident with a target of your choice and to detect if this was successful.

Another nice feature of VMs is they can be suspended to a disk image and restarted. A less nice feature is that the same image can be restarted several times, given a different query each time but may use the same randomness/PRG - practical examples were presented as our favourite browsers seed the PRG for TLS and co. when they start up. In other words, we can actually apply the "forking lemma" in practice! For a server VM, we saw practical examples of stealing the TLS master key this way.

Another security issue arises in cloud-based backup systems like dropbox. They use a trick called deduplication - if two users backup the same file, it only stores the file once and the second user doesn't even have to upload it again (the service can compare file hashes). It's pretty much the equivlent of UNIX hard links. It's estimated that deduplication saves 95%-99% of space for online backup systems, but we're still talking about petabytes.

Deduplication gives anyone an oracle to test whether a file has been backed up before and to brute-force test which version of a file has been backed up if only a small portion is unknown. Another problem is that knowing the hash of someone's file allows you to retrieve it - just pretend you have a file with that hash, deduplication means you get access to it without any further questions. As an aside, dropbox claims to encrypt all files with "military-grade encryption" (AES is mentioned too) but for deduplication to work at all, it seems like they encrypt everyone's files with the same key.

With problems like these out there, what can we do? Two main approaches were presented, both dealing with the fact that the client cannot fully trust the could provider. The first is based on secure hardware (mostly TPMs) and several talks gave scenarios for using hardware-based trust. The second approach is to use software-based cryptography - mostly some variation of MPC, although we heard some good arguments why general MPC won't make it into the real world. However, special cases (Voting and Linear Programming were mentioned) offer good opportunities for efficient MPC-like constructions. The principle of using two (or more) clouds also appeared in several talks.

More on PKC 2011

(Written by Georg)

Since Matthew Green from John Hopkins University was unable to come to PKC, I was asked to give the talk for him and I agreed. His paper is on Secure Blind Decryption, a cryptographic primitive which extends a public-key encryption scheme by the following functionality: a User, holding a ciphertext and a Decryptor holding the decryption key run a protocol upon which the User learns the encrypted message. Security demands on the one hand that the User does not learn anything more than the message and on the other that the Decryptor cannot distinguish which ciphertext the User asked to be decrypted.

This primitive has many applications from Oblivious Transfer (with additional properties) to Private Information Retrieval. A practical motivation is that when outsourcing data to an (untrusted) "cloud", not only must the data be protected, but it should also remain hidden which data is accessed. Examples include medical records or patents, where merely the information of which record is accessed can reveal much about a patient's status or a company's intentions.

The author constructs the first CCA-secure scheme with a blind decryption protocol by applying the CHK transform to a variant of a tag-based Cramer-Shoup-type cryptosystem based on DLIN and a new F-unforgeable one-time signature.

Another highlight of the day was Vinod Vaikuntanathan's invited talk on leakage-resilient cryptography. Whereas traditional cryptographic models assume that certain information (such as decryption keys) are completely secret, this is not true in practice: realisations of cryptographic schemes might succumb to side-channel attacks, which reveal parts of the secrets. Leakage-resilient cryptography tries to model these attacks formally and provide (provable) security against them.

Ciphertext Policy Attribute Based Encryption

Today at PKC 2011 a talk was given by Hakan Seyalioglu on the paper by Brent Waters, entitled "Ciphertext-Policy Attribute-Based Encryption: An Expressive, Efficient, and Provably Secure Realization".

First, let us consider what attribute based encryption is and why this may be useful. In standard public key cryptography, a file is encrypted under a user's public key. The corresponding secret key (and that key alone) can then be used to decrypt the ciphertext. Now, assume users each have various attributes associated to them. For example, Alice may be in a group called "internal affairs", she is female, and based in the USA office of her organisation. Thus we assign her the attributes "internal affairs", "female" and "USA". If Bob wants to encrypt a document so it can be decrypted by everyone who is a member of the "internal affairs" group, he could create an encryption of the document for every user in this group using their public key. However, what if Bob does not know who is in the group? What if users are added to this group at a later time? In this situation, we can not use standard public key cryptography, therefore we turn to attribute based encryption (ABE).

In ABE, a key authority is considered to be a trusted party who generates keys for users within a system. The key authority has a master secret key (MSK) and public key (PK). For each user in the system the key authority generates keys based on the users attributes, using the MSK. Each user is then given their corresponding secret key, SK. Now, when a user wants to encrypt a document they construct a policy for this document. The policy specifies which attributes are required to decrypt this document, for example ("internal affairs" OR ("female" AND "Canada")). Given the constructed policy and the PK (of the key authority for a system), documents can then be encrypted and distributed to everyone - but only decrypted by users which match the policy assigned to the ciphertext.

Note that if we have the policy ("internal affairs" AND "female" AND "Canada") neither Bob (given the attributes "male" and "Canada") nor Alice should be able to decrypt documents with this policy. We can see that together they meet the criteria - so crucially, we do not want collusion between users to allow them to decrypt documents - only a user who meets the criteria alone should be able to decrypt the document.

Waters introduces a new ciphertext-policy based (as opposed to key-policy based) ABE. When one constructs a new scheme, the security must be considered - formally one produces a proof reducing to some hard cryptographic problem. One consideration when constructing new schemes is what hard problem we wish the scheme to be reduced to. However, ultimately security may depend on whether the hard problem to which you reduce is truly hard. Therefore, Waters gives several different constructions, each reducing to a different problem. One scheme has a ciphertext size of O(n), private key size of O(A) and an encryption time of O(n), where n is the size of an access formula (i.e. the size of the policy), and A is the number of attributes in a user's key. The other schemes have worse complexities, but reduce to different (harder) assumptions. This paper demonstrates well the trade off between assumptions required and the efficiency of the resulting scheme.

Privacy economics and risk perception workshop

Some of us spent Thursday discussing about privacy and what makes us give our precious personal information away, drawing on prospect and utility theories, econometric models, theories of cognitive bias in decision making as well as the impact of social class and political beliefs. The facilitator, Spyros Kokolakis from the University of Aegean, presented the case of the brand new Greek national ID scheme. This is based on smartcard technology and intended to be used to monitor every single financial transaction for reasons of tackling tax evasion - ambitious as much as controversial!

It was interesting to explore how perceptions of risk vary, depending on contextual anchors, personal experience etc. and consider how their understanding may have a fundamental role in the success of any technological platform, especially in our area of security and privacy. A key observation was that the planning of any intervention based on schemes such as the IDs above, not only does it require a robust technological platform, but also an appreciation for the factors that may facilitate or inhibit its use (or abuse!): perception of value, comfort, fear, perception of risk to name but a few. These are not always easily captured in quantitative or qualitative models and even then, it may be difficult to integrate those into the security design.

And as for the case of the new Greek IDs, if I had any reservations for their effectiveness against tax evasion before, well, those certainly didn't go away after our discussions. But I'll be certainly looking out for the results of Spyros' evaluative research of the scheme.

INTRUST 2010

I attended INTRUST 2010 in Beijing, China. The conference focused on all aspects of trusted systems like trusted modules, platforms, services and applications. In this year, program was split on two parts. In first two days was technical session where the audience was able to select talks from main topics like Hardware Security, Security Analysis, Software Protection or Mobile Trusted Systems. Third day was reserved for Workshop with Invited Talks with keynote speakers like Andrew Yao, Moti Yung, Ahmed-Reza Sadeghi or Liqun Chen.

The bast paper award was sponsored by Singapore Management University (US$1000) and was given to "Seamless Integration of Trusted Computing into Standard Cryptographic Frameworks" by Andreas Reiter, Georg Neubauer, Michael Kapfenberger, Johannes Winter and Kurt Dietrich from IAIK, Graz. This was the first presentation of the conference and in this talk author presented a novel design for Trusted Software Stack (TSS) - interface between applications and Trusted Platform Module (TPMs). Proposed TSS can be easily integrated into existing security frameworks and reuse application programming interface (APIs) from well known frameworks. Presented stack has nice features like dynamically loading components via the network, add, update or replaced functionality even after deployment and support multiple TPMs. The last features is especially nice for mobile devices and systems with many virtual TPMs. The prof of concept was done with the BoncyCastle security framework, but according to authors further enhancement might include integration into Java Cryptographic Extension and CryptoAPI.

Just after first session I gave a talk on "Hardware Trojans for Inducing or Amplifying Side-Channel Leakage of Cryptographic Software", where I presented a novel concept of micro-architectural Trojan Side Channels.

Definitively the last day of the conference was the best one. Many keynote speakers was invited to give a talk: Andrew Yao - "Some Perspectives on Complexity-Based Cryptography"; Moti Yung - "Embedding Cryptography to General IT Engineering System/Project"; Liquen Chen - "Security and Privacy in Vehicular Systems - Case Study: Trusted Anonymous Announcement"; Ahmad-Reza Sadeghi - "Trusted and Secure Computing in Practice: Where are We Now!" and many others.

During this session very interesting talk was given by DongHoon Lee from Korea University on Security Issues in Smart Grid. He highlights security problems in smart grids like privacy of smart meters users and smart meter attacks. According to wikipedia smart meter is an advanced meter that records consumption in intervals of an hour or less and communicates that information at least daily via some communications network back to the utility for monitoring and billing purposes. This information of consumption might reveal (if is not protected) e.g. user's lifestyle pattern which might be considered as a privacy violation. Author presented also the list of possible attacks on smart meters. The last part of the talk was dedicated to security requirements of smart meters and a need of security standards in this field.

The last talk of the conference was given by Claire Vishik from Intel. She briefly introduced "Direction in Hardwire Security R&D in Government, Academic and Industrial Research". The audience was able to listen some state-of-the-art security issues from industry, academia and government perspective, advantages and disadvantages of all of them and point of interests in terms of security research. The last part of the talk was focused on Intel's work and vision - goals and future.

Highlights of ACSAC 2010

I just returned from this year's Annual Computer Security Applications Conference (ACSAC) in Austin, Texas. Unfortunately, due to the adverse weather conditions and resulting flight delays, I missed out on the first day of the technical program.

ACSAC is dedicated to work on practical security applications and this year its program encompassed such diverse topics as detection of misbehaving network entities (e.g. spammers, malware-infected machines/botnets), malware analysis/mitigation, practical authentication, hardware security, secure OS (components), security in mobile/wireless devices, and social engineering.

The best paper went to Ang Cui and Salvatore Stolfo from Columbia University, for their assessment of the vulnerability of network-enabled embedded devices. Basically, they performed a scan of the whole Internet in order to find embedded devices (typically gateways or routers) whose network managment interface was accessible via the manufacturer's default credentials. They identified a large number of vulnerable devices, especially gateways in ISP networks which typically act as the network point of entry for private home (NAT) networks. All these devices are potentially up for the taking by uploading malicious firmware, which could make them part of a botnet. This is especially alarming, as a botnet composed of such gateways could be much more potent than traditional botnets built from infected PCs. In terms of workload, these gateways are just as good as any infected machine residing behind it - in the end what counts is the rate at which packets (e.g. SPAM) can be sent out, and that's limited by the gateway's capabilities anyway. Moreover, most gateways are always switched on, giving rise to much higher availability of the bots. Also, infections on PCs usually get detected at some point by showing abnormal behavior like unusually high processor or network loads or weird disk access patterns. On the other had, it seems much harder for a "normal" user -who never even bothered to change the default password - to start suspecting the gateway to be infected with malware.

Another interesting talk given by Jonathan Valamehr involved potential use of 3D chip integration for attaching cryptographic coprocessors to regular embedded processors. 3D chip integration works by stacking several chip dies on top of each other and connecting them by intra-chip vias or similarly fine connections and it allows for much denser integration than would otherwise be possible. The contribution of the teams from UC Santa Barbara and UC San Diego is the development of special connector circuits which allow to add another die with matching landing points conditionally. Their example was an embedded processor which would work normally as a single die and could be stacked with a cryptographic coprocessor die for improved processing of security workloads.

In my talk - which immediately followed the 3D talk - I presented a detailled concept and FPGA prototype for a side-channel resistant embedded processor, which has been developed in the context of the Power-Trust project at my former university (Graz University of Technology, Austria). An ASIC prototype is currently under evaluation in a joint effort of Graz and Bristol.

Thomas Longstaff gave a very interesting invited talk on the lack of the scientic method in many works in the applied security community. He argued that certain pressures and realities in the present academic world would lead researchers to adapt experiments to fit the hypotheses instead of the (proper) other way around. Also he noted that many papers lack a sufficient description of their methodology - which he considered as one of the most important parts of any scientific paper. Also he plead for more care in the choice of program committee members and argued that PCs should contain a minimum number of members with formal scientific training as opposed to practitioners in certain fields.

The very last talk of the conference by Trajce Dimkov from the University of Twente discussed methodologies for evaluating the threat of social engineering attacks. The presentation compared the practical application of two different methodologies for penetration testing, i.e. basically they send in people into an organization who try to breach security via social engineering. In this case the goal of the penetration tester was to "steal" a laptop of a specific employee. The talk was accomanied by video footage take on some of the tester's "coups". The two methodologies differed in the number of involved people and who knows what. In the end there are several conflicting requirements and one must choose the best methodology which will create the least disturbance to the tested organization (e.g. disruption work or shattering existing trust relations).