Category Archives: Three Paper Thursday

Three Paper Thursday: ISSISP2012

I’ve just returned from the 2012 International Summer School on Information Security and Protection (ISSISP2012) held at the University of Arizona. This annual summer school brings together a mix of academic researchers and industry practitioners in the field of software protection where the main philosophy, and indeed the only viable approach available, can be summed up as “Security through Obscurity”. The goal here is to impede reverse engineering and to hide algorithms and data in the presence of disassemblers, decompilers, debuggers as well as side-channel analysis – this is the Man-at-the-End (MATE) attack. White box cryptography, I’ve learnt, is the term used to describe the protection of cryptographic primitives and keys against this kind of attack. This week I wish to highlight 3 talks/papers which I found memorable – the first 2 describe techniques to address code injection and timing side-channel attacks; the last one discusses formally verified program obfuscators.

Continue reading Three Paper Thursday: ISSISP2012

Three paper Thursday: Shamir x3 at Eurocrypt

For the past 4 days Cambridge has been hosting Eurocrypt 2012.

There were many talks, probably interesting, but I will only comment on 3 talks given by Adi Shamir, 1 during the official conference and 2 during the rump session.
Among the other sessions I mention that the best paper was given to this paper by Antoine Joux and Vanessa Vitse for the enhancement of index calculus to break elliptic curves.

Official Talk: Minimalism in cryptography, the Even-Mansour scheme revisited

In this work, Adi et al. presented an analysis on the Even-Mansour scheme:

E(P) = F(P ⊕ K1) ⊕ K2

Such scheme, some times referred to as key whitening, is used in the DESX construction and in the AES-XTS mode of operation (just a few examples).

Adi et al. shown a new slide attack, called SLIDEX, which has been used to prove a tight bound on the security of the Even-Mansour scheme.

Even more, they show that using K1 = K2 you can achieve the same security.

Rump talk 1: security of multiple key encryption

Here Adi considered the case of encrypting data multiple times with multiple keys, as in 3DES:
data -> c1 = E_k1(data) ->  c2 = E_k2(c1) -> c3 = E_k3(c2) -> c4 = E_k3(c3) …. and so on.

The general approach to break a scheme where a key is used 2 times or 3 times (2DES, 3DES for e.g.) is the meet-in-the-middle attack, where you encrypt from one side and then decrypt from the other side, and by storing a table of the size of the key space (say n bits) you can eventually find the keys used in a scheme using only a few pairs of plaintext/ciphertext. For 2 keys such an attack would require 2^{n} time, for 3 keys 2^{2n}. Therefore some people may assume that increasing the number of keys by 1 (i.e. to use 4 keys) may increase the security of this scheme. This is in fact not true.

Adi shown that once we go beyond 3 keys (e.g. 4, 5, 6, etc…) the security only increases once every few keys. If you think of it, using 4 keys you can just apply the meet-in-the-middle attack in 2^{2n} time to the left 2 encryptions and also in 2^{2n} time to the right 2 decryptions. After this, he shown how to use the meet-in-the-middle attack to solve the knapsack problem and proposed the idea of using such an algorithm to solve other problems as well.

Rump talk 2: the cryptography of John Nash

Apparently John Nash, member of MIT during the 1950s, wrote some letters to the NSA in 1955 explaining the implications of computational complexity for security (this wasn’t known at the time).

John Nach also sent a proposal for an encryption scheme that is similar with today’s stream ciphers. However the NSA’s replied saying that the scheme didn’t match the security requirements of the US.
Adi Shamir and Ron Rivest then analysed the scheme and found that in the known plaintext model it would require something like 2^{sqrt(n)} time to break (which John Nach considered not to be a polynomial time, and therefore assumed would be secure).

The letters are now declassified. This blog also comments on the story.

Three Paper Thursday: full disk encryption

Information is often an important asset and today’s information is commonly stored as digital data (bytes). We store this data in our computers local hard disks and in our laptops disks. Many organisations wish to keep the data stored in their computers and laptops confidential. Therefore a natural desire is that a stolen disk or laptop should not be readable by an external person (an attacker in general terms). For this reason we use encryption.

A hard disk is commonly logically organised in multiple sections, often referred to as either partitions or volumes. These volumes can be used for various purposes, and they are often structured according to a file system format (e.g. NTFS, FAT, HFS, etc.). It is possible to have a single disk with 3 volumes, where the first volume is formatted with NTFS and contains a Windows operating system, the second volume is formatted with EXT3 file system and contains an installation of a Linux distribution, while the third volume is formatted with FAT file system and only contains data (no operating system).

Volume encryption is a mechanism used to encrypt the contents of an entire volume. This is sometimes referred as “full disk encryption”, which is misleading, since a physical disk can actually contain multiple volumes, each encrypted independently.  However, since the term has become very popular, I will continue to refer to this kind of encryption as “full disk encryption” but the reader should keep the above distinction in mind.

There are several products that offer full disk encryption, e.g. PGP Whole Disk Encryption, TrueCrypt, Sophos SafeGuard, or Check Point FDE. Bitlocker is the full disk encryption integrated with the Windows OS and Apple has recently introduced FileVault 2 as full disk encryption from MAC OS X 10.7.

There are several limitations that affect the encryption of an entire disk. These have to do with 3 important aspects among others: a) encryption must be fast (a user should not notice any extra latency); b) the operating system is encrypted as well (so there must be some way of bootstrapping the decryption process when the computer boots)  c) the encryption mechanism should not reduce the available storage space noticeable (that is, we cannot use an extra block of data for every few encrypted blocks).

The following 3 papers explain in detail these limitations. Two of them relate to currently deployed full disk encryption systems.

Continue reading Three Paper Thursday: full disk encryption

Three Paper Thursday: BGP and its security

BGP security was a hot topic a few years ago, but is not as much studied these years. However, with technologies such as IPv6 and DNSSEC, BGP security is making a comeback, especially in the industry. We academics also have much to contribute in this space. In today’s Three Paper Thursday, I will highlight three recent work related to BGP security. It is also a good starting point to catch up in BGP security for those whose last memories of BGP security involve proposals such as S-BGP and SoBGP.

Three Paper Thursday: Binary analysis and Security

Mention the phrase “binary reverse engineering” or “binary analysis” and it often conjures up an image of software pirates or hacking groups. However, there are practical reasons for doing analysis on machine code. For instance, machines don’t run source code, they run machine code – how do we know it’s running correctly? Malware doesn’t usually come with source code (but they are known to leak on occasion); How do we protect our software from discovered vulnerabilities if we’re unable to re-compile the program from the original source code? For three paper Thursday this week, my contribution is to highlight three representative security applications of binary analysis, namely software testing, malware analysis and software protection. Continue reading Three Paper Thursday: Binary analysis and Security

Three Paper Thursday: Financial Crypto 2012

I spent last week attending Financial Cryptography on Bonaire (a small Dutch island in the Caribbean), along with its attached workshops on Ethics in Computer Security Research and Usable Security.  As usual, the conference attracted a broad spectrum of papers mixing applied cryptography and miscellaneous financial security problems (including our own group’s work on PIN guessing statistics and Facebook’s photo-based backup authentication). All of the papers are now online. I’ll point to three papers which thought-provoking for me. I’m not going to claim these are the best or most important papers-the conference featured some very strong work on applying cryptography to practical problems like smart metering and oblivous printing, while perhaps the most newsworthy research was Wustrow et al.’s hacking of the Washington DC Internet voting prototype. I’ll just highlight why these papers were memorable for me. Continue reading Three Paper Thursday: Financial Crypto 2012

Three-paper Thursday: Android Malware Intelligence

Google’s mobile platform Android has been gaining increasingly popularity in the last few years. The policy of being open in its application marketplace is undoubtedly one of the keys that help Android grow so quickly. The low entry barriers as well as the non-vetting process help Android attract a lot of developers who have brought 450,000+ applications to the Android Market in 3 years. This success comes at a price though: Android is now the leading target of mobile malware also due to the less restrictive nature of the platform and the marketplace. The official Android Market and third-party marketplaces harbour benign applications as well as nefarious ones. On this week’s Three Paper Thursday, I’d like to introduce three papers that provide insights on intelligence of Android malware in the wild.

Continue reading Three-paper Thursday: Android Malware Intelligence

Three-paper Thursday: capability systems

This week, my contribution to our three-paper Thursday research reading list series is on capability systems. Capabilities are unforgeable tokens of authority — capability systems are hardware, operating, or programming systems in which access to resources can occur only using capabilities. Capability system research in the 1970s motivated many fundamental insights into practical articulations of the principle of least privilege, separation of mechanism and policy, and the interactions between program representation and security. They also formed the intellectual foundation for a recent renaissance in capability-oriented microkernels (L4, sel4) and programming languages (Joe-E, Caja, ECMAScript 5). Capability systems have a long history at Cambridge, including the CAP Computer, and more recently, our work on Capsicum: practical capabilities for UNIX. I’ve selected three “must read” papers, but there are plenty of other influential pieces that, unfortunately, space doesn’t allow for!
Continue reading Three-paper Thursday: capability systems

Cloudy with a Chance of Privacy

Three Paper Thursday is an experimental new feature in which we highlight research that group members find interesting.

When new technologies become popular, we privacy people are sometimes miffed that nobody asked for our opinions during the design phase. Sometimes this leads us to make sweeping generalisations such as “only use the Cloud for things you don’t care about protecting” or “Facebook is only for people who don’t care about privacy.” We have long accused others of assuming that the real world is incompatible with privacy, but are we guilty of assuming the converse?

On this Three Paper Thursday, I’d like to highlight three short papers that challenge these zero-sum assumptions. Each is eight pages long and none requires a degree in mathematics to understand; I hope you enjoy them.

Continue reading Cloudy with a Chance of Privacy