TCC : Tuesday PM

Draging oneself away from the lovely views of Mount Etna in Taormina to go to a bunch of talks on cryptography can be difficult. But the talks this afternoon made it worthwhile. There were a total of eight talks, so I only select a few highlights (mainly from the first part on PRFs).

The first two talks on constructing PRF's I thought were particularly well delivered. The first by Berman and Haitner looked at the problem of constructing an adaptively secure PRF (i.e. the adversaries queries are determined adaptively) from a weaker PRF (namely a non-adaptive PRF) F and a pairwise independent hash function H. The speaker showed that this could be done by simply applying H and then applying F; the hash function however needed to be restricted to have co-domain the size of the "running time" T of an adversary that could break F with probability 1/T. 

The second talk by Jain, Pietrzak and Tentes took a different approach to constructing a PRF namely from a PRG G whose co-domain is twice that of the input size. The trick was quite neat. Firstly they look athe GGM construction which compute PRF(k,x) in two steps:

•  First write G(y) as two functions G_0(y)||G_1(y) where G_i has co-domain n-bits in length.
• Write x in binary as x_n,....,x_1
• Output G_{x_n}(G_{x_{n-1}}(....G_{x_1}(k)))

Call this function GGM(k,x). This function requires we call the function G n-times to evaluate it on a string of size n bits.  A trick of Levin is to first apply a hash function with co-domain m-bit strings so as to compute the function  GGM(k,H(x)).  Which requires m calls of the PRG G, although the key-size of the PRF increases since one needs a key for the hash function H (I have hid this in the notation above).

The problem is that this has problems due to collisions in G. To get around this the authors propose the following construction

H'(GGM(k,H(x)),x)

where H' is different a keyed hash function with key GGM(k,H(x)) and message x. I thought this was rather neat myself.

The short mini-session on PRFs was completed by a talk by Krawczyk (co-authors Dachman-Soled, Gennaro and Malkin) who looked at various theoretical aspects, but at the end concluded that the PRF used in the TLS implementation of Diffie-Hellman key exchange is secure. This was much to Hugo's "distress" as he did not think it should be morally secure at all, so it was a surprise when it was indeed shown to be secure. 

For the other talks I had seen many of the papers before, so I was not so surprised or interested (such is the effect of e-Print on conference attention spans). However, the "Verifiable Computation from ABE" paper is definitely worth a look for people interested in this area. The key contribution is that they produce a VC scheme without needing FHE or PCP's (both being rather inefficient). They do this by utilizing an ABE. However, the efficiency of their own solution is still not really useful, since the scheme is based on functions with single-bit outputs, to extend the technique to other bit-lengths one needs to keep repeating the technique. Given the underlying techniques are ABE, which themselves are not that (practically) efficient, there seemed a lot of room for further work in this area.

TCC-Day 1, session 1: MPC

The first talk of the session, Computing on Authenticated Data, defined notions for deriving signatures on messages for which a certain predicate is satisfied. There has been much progress in this area recently with work on redaction and quoting of authenticated data, homomorphic signatures and transitive signatures. This can be seen as a signature analogue of fully homomorphic encryption in some sense. One particular new property identified in this work was context hiding: a derived signature on a message m' should not leak any information on the original source message, for example a signed quote should not leak any information about the message from which it was quoted. This property can be seen as a data analogue of the hiding a signer amongst a group of users in group signatures.

The second talk focused on constructions of identifiable secret sharing schemes. This is a SSS which during the reconstruction phase either outputs the correct secret or publicly identifies the set of all cheaters. In this work they modify the reconstruct algorithm to only inform the set of honest players of the cheaters (which is arguably a more natural requirement). Under this new notion they show unconditional MPC can be realized in the presence of a dishonest majority.

The final talk of the session given by Ivan Damgaard focused on two party secure computation with low communication. In this setting two parties with private inputs wish to compute some function of those inputs with low communication costs. Famously Yao showed that any poly time two party functionality can be computed securely even against a malicious adversary. For semi-honest adversaries there exists a straightforward solution based on FHE and NIZK proofs. In this work the authors succesfully build a protocol where the communication is only polylog in the circuit size, assuming the existence of collision resistant extractable hash functions, which can be instantiated via the knowledge of exponenet assumption.

Oblivious RAM

Today's study group was on Oblivious RAM - a concept introduced by Goldreich and Ostrovsky, which enables a client storing only a small amount of data locally to store a large amount of data in e.g the cloud and access them while hiding the identities of the items being accessed.

Roughly speaking the adversary model for Oblivious RAM is as follows - an adversary can't distinguish between equal length sequence of queries made by the client to the server. Early solutions required the server to store O(N*log(N)) data items and each access to a data item actually required O(log^3(N)) data requests. Later work of Pinkas & Reinman brought this down to O(N) storage and O(log^2(N)) requests. However their solution was insecure but an improvement later made this secure. Interestingly there is a theoretical lower bound on the number of requests of log(N). Essentially the overhead arises out of which data oblivious sorting algorithm one chooses.

We focus on the quadratic solution which is conceptually the simplest to understand. In essence we have a memory cell of adressess [0,N] which we expand by an extra sqrt(N) which will hold an extra sqrt(N) dummy data. We also have a "shelter" of size sqrt(N). The first step is to randomly permute all locations [0, N + sqrt(N)] (i.e everything outside the shelter) using a permutation derived from a random oracle. We carry out sqrt(N) memory accesses as follows: previously accessed memory is kept in the sheltered locations. An access to the original RAM works as follows: say we wish to access memory at location i. First we scan through the shelter and check whether the contents of the original memory is held at one of the locations [N+sqrt(N)+1,N+2*sqrt(N)]. If it's not there its at location pi(i) where pi is our permutation. If it is there, we access the next dummy word (i.e if we are on the j'th access for 1<= j <= sqrt(N) we use the dummy at pi(m+j)). For further details see http://dl.acm.org/citation.cfm?id=233553

The significantly more efficient "heirarchical" approach is a lot more involved. The interested reader should consult Goldreich & Ostrovsky paper. Also of interest is the multiparty approach of Damgaard et al. eprint.iacr.org/2010/108.pdf which removes the need for a random oracle.

Jake

Study Group: Computing models. Sublq etc.

The study group on Mar 9^th 2012 was done by Simon and Mike. The talk focused on computing models, sublq etc.

Subleq-OISC:

OISC stands for “one instruction set computer” – analogous to the well-known CISC and RISC abbreviations. The OISC instruction “set” indeed consists of only one instruction, but is nonetheless Turing-complete1. This instruction takes three parameters and is concisely described as “subtract and branch on

result less than or equal to zero,” abbreviated subleq a b c.

In “C” style pseudocode, this instruction does the following:

*b-= *a;

if (*b <= 0) goto c;

The followings are instrucions of some operations:

CLR a

subleq a a $+1

JMP c

subleq Z Z c

MOV a b

subleq b b $+1 *b=0

subleq a Z $+1 Z=-*a

subleq Z b $+1 *b=0-(-*a)=*a

subleq Z Z $+1 Z=0

ADD a b c

subleq a Z $+1

subleq b Z $+1

subleq c c $+1

subleq Z c $+1

sublez Z Z $+1

SUB a b c

subleq t t $+1

subleq s s $+1

subleq a t $+1

subleq b s $+1

subleq s t $+1

subleq c c $+1

subleq s s $+1

subleq t s $+1

subleq s c $+1

DIV abc

MOV b v

MOV a w

CLR c

subleq N c $+1

subleq w v $+4

subleq Z Z $-8

The Ultimate RISC :

The only instruction in the ultimate RISC `instruction set' is a two address instruction that moves a single word from one memory location to another. The instruction execution unit of such a machine can hardly be considered to be a processor, since it performs no computations; thus, the term central processing unit is inappropriate here. If such a machine is to be useful, it must, of course, be able to compute; this problem can be solved by adding a memory mapped arithmetic unit.

This architecture is not intended to be a practical architecture. However, the architecture can be made reasonably convenient with the addition of a small amount of extra hardware. For example, the attachment of a memory management unit between the instruction execution unit and the memory allows for indexing, and one additonal flipflop is enough to allow convenient conditional branches. Furthermore, this architecture may be pipelined, and doing this introduces all of the problems of instruction scheduling traditionally associated with RISC systems.

A minimal implementation of the ulitmate RISC architecture requires an instruction execution unit, a memory, input-output devices, and a bus to connect these. The basic algorithm executed by the instruction execution unit is most easily expressed if a memory address fits exactly in a word. This has been assumed by the register transfer description of the instruction execution unit shown as follow:

registers pc, addr, temp;

      repeat
          1: addr := M[pc]; pc := pc + 1;
          2: temp := M[addr];
          3: addr := M[pc]; pc := pc + 1;
          4: M[addr] := temp;
      forever;

The condition code tests shown in the following table are based on those available on machines descended from the PDP-11, where N signifies a negative result, Z signifies a result of zero, O signifies a 2's complement overflow, and C signifies a carry out of the sign bit. The representation of Boolean values produced by the arithmetic unit is determined by the need to perform conditional branch instructions. True is represented by the value 2, and False is represented by zero.

Table : Arithmetic Unit Operations
 


 
        
   
    
address 
   
   
    
write  
   
   
    
read
   
  
  
   
    
FFF0
   
   
    
acc = data 
data = acc
   
  
  
   
    
FFF1 
   
   
    
acc = acc-data  
   
   
    
data = N
   
  
  
   
    
FFF2
   
   
    
acc = data-acc 
   
   
    
data = Z
   
  
  
   
    
FFF3
   
   
    
acc = data+acc
   
   
    
data = O
   
  
  
   
    
FFF4
   
   
    
acc = data^acc 
   
   
    
data = C
   
  
  
   
    
FFF5
   
   
    
acc = data&acc
   
   
    
data = N^O
   
  
  
   
    
FFF6  
   
   
    
acc = data|acc 
   
   
    
data = (N^O)|Z
   
  
  
   
    
FFF7
   
   
    
acc = data>>1
   
   
    
data = C^not(Z)
   
  
 
 

 
   

 

CryptoForma Edinburgh

Last talk at the CryptoForma meeting held in Edinburgh was given by Nadhem AlFardan from Royal Holloway.
He presented the work titled "Plaintext-Recovery Attacks Against Datagram TLS" that received the best paper award at NDSS this year.

Datagram TLS (DTLS) is a TLS extension suitable for datagram transport. It was introduced in 2004 and its implementations can be found either in OpenSSL and GnuTSL.

The attack shown is a padding oracle attack. Informally, padding oracle attacks work by adjusting a ciphertext in some specific way before input it to an honest decryptor. If a padding error is returned, then the adversary is able to gain some information about the underlying plaintext.
For instance, the padding oracle attack mounted against TLS in OpenSSL introduced by Vaudenay, makes use of timing differences due to the fact that messages with bad padding were rejected faster than other messages.

Since DTLS does not return error messages when processing invalid padding, implementation of DTLS should be resistant to such kind of attacks.

Interestingly, the vulnerability presented by Nadhem shows that such attacks are still possible by exploiting the timing of heartbeat response messages or that of any responses with a predictable delay sent by any upper-level protocol instead of error messages. The work also introduces techniques to amplify the timing differences which makes use of "trains" of valid or invalid packets.

CryptoForma Edinburgh

Yesterday and today saw two days of CryptoForma in Edinburgh, discussing topics including voting (where I gave a talk on our Helios work) and the latest approaches to formal verification.
A topic that spanned many talks on different topics was the difficulty of verifying exactly what a protocol does - often a tiny difference down at the bit level between a security model and what the protocol actually does can make all the difference.

A very promising solution to this problem is to verify security properties on the actual source code, as presented in an excellent tutorial by Cédric Fournet today using the F#/F7 languages.
The properties that can be expressed here are not "just" a formal model that would need a computational soundness theorem to link it to the actual code but actual cryptographic properties like IND-CPA or CCA2.

Even MS research can't prove AES to be CCA2 (and as some would no doubt point out, an asymptotic result means only so much for n=256) but one can take a modular approach: assume that the cipher in the System.Cryptography library is CCA2 and then prove an RPC protocol secure under this assumption, using something that looks suspiciously like a game hop. Except that this is all done automatically in visual studio at compile time.

The key ingredient here are refined types, comprising a base type and predicates on these that can be verified by a theorem prover. For example, "block: bytes {length = 8}".
Furthermore, one can set predicates in the execution of a primitive, for example calling MAC(key, msg) sets the implicit predicate auth(msg) and VERIFY(key, msg, mac) has the postcondition "VERIFY(key, msg, mac) = 1 => auth(msg)", which models existential unforgeability.
Where this gets really interesting is when such predicates are set at the protocol level: auth(msg) is set not when MAC is called but when the message msg should logically/semantically be authenticated by a key-holder. The same postcondition on VERIFY can now be checked relative to the whole protocol, say a client-server RPC protocol.

Of course even this technique can't guarantee secure protocols in all settings (timing side-channels are not covered, nor malware that interferes with the checked program at runtime) but it would still be a great step in the right direction if compile-time formal modelling and verification became as natural a step in protocol implementation as unit testing.

Study Group on Attacks on Software

The study group on March 2, 2012, 10:00am was done by Valentina and Georg (and obviously scribed by me). The main theme was attacks on software, with four papers on various topics being presented.

The first paper presented by Valentina (Cappos et al., A look in the mirror: attacks on package managers, CCS 2008) examined the security of software package repositories. A software package contains the actual files of the software, metadata on dependencies und the package's functionality, and optionally a signature. Additionally there might be "root metadata" which contains the metadata of multiple packages and an optional signature. Multiple software packages are hosted on a repository (which is usually authorative) and a number of (non-autorative) mirrors. Clients run package managers, which collect the required packages for installation.

Four different security modes have been evaluated in the paper:

1. No security
2. Signatures embedded with package
3. Signature on detached metadata
4. Signature on root metadata

The threat model for the security evaluation assumes that the attacker can communicate (e.g. via MITM or a hijacked mirror) with the package manager running on client under the following conditions:

• Attacker can serve arbitrary files
  
• Attacker does not know in advance which package will be requested
• Attacker does not have the signing key used for signing packages, metadata, etc.
• Attacker has access to outdated packages, outdated package metadata, and outdated root metadata
  
• Attacker is aware of vulnerabilities in outdated packages and is able to exploit those
• Attacker does not know vulnerabilities in latest version of packets
• If packet manager supports signatues, they are used
• If supported, expiration times in root metadata are used

Various attacks have been evaluated for the four security modes:

• Sending an arbitrary package
• Replay attack (sending an older package version)
• Freeze attack (making newer package versions invisible)
• Extraneous dependencies (rewrite of metadata)
• Endless data (an endless data stream served by the attacker)

The results of the evaluation are that all security modes are vulnerable to at least some of the attacks. For sufficient security, several security mechanisms should be comined.

The second paper (presented by Georg) was Checkoway et al., Are Text-Only Data Formats Safe?
Or, Use This LaTeX Class File to Pwn Your Computer, LEET 2010.

The authors show how varios LaTeX/BiBTeX constructs could be used to infect machines with malware. The first example was the LaTeX \write command which allows (depending on the underlying platform) write access to the file system. On a MiKTeX installation on Windows this could allow access to any file, while on Linux, only files in or below the current directory with appropriate permissions would be subjected. A similar problem is posed by the LaTeX \read command, which allows to read from the file system. These threats could be partcularly harmful on servers which offer online LaTeX compilation services.

Countermeasures which scan selectively for \write and \read commands and sanitize them cannot be seen as a sufficient protection, due to the versatility of the LaTeX language. For example, the backslash character could be redefined (e.g. \ -> X) which in turn redefines the commands (Xwrite and Xread), thus defeating simple scanning.

Another possibility for introducing malware is the use of the BiBTeX @preamble{...} command, which inserts its argument into the LaTeX preamble. A virus could even be scattered across multiple @preamble commands to obscure it from scanners.

Also, LaTeX class and style files present another option for pushing malware onto a host, especially if their use is mandated for a specific conference.

Denial-of-service attacks (especially on online LaTeX processing services) could be achieved with "endless loop" constructs like "\loop \iftrue \repeat" and "\def \nothing {\nothing}".

The third paper, Brumley et al, Remote Timing attacks are still practical, IACR Eprint 2011/232, was again presented by Valentina. It examines the timing vulnerabilities in OpenSSL v0.98, which have been reported in CERT VU #36044. The concrete example is Montgomery point multiplication, which is usually immune to timing attacks, but in OpenSSL becomes vulnerable due to some optimization techniques applied in the software implementation. The attack works in two phases by 1) collecting a number of signatures and 2) a lattice attack. In the lattice attack, the attacker takes advantage of the length of the scalar k. For example, if the scalar k has 6 leading zeros, the success probablitliy of the attack is 1 with only 50 signatures.

Georg presented the last paper: Nguyen et al., Can We Trust Cryptographic Software? Cryptographic Flaws in GNU Privacy Guard v1.2.3, EUROCRYPT 2004. GNU Privacy Guard (GPG) is an open-source implementation of the PGP program, capable of encrypting and signing emails. It is deployed with all major Linux distributions and at the time of the writing of the paper, version 1.2.3 was the most current version of GPG.

It turns out that tweaks for efficiency (concerning the generation of random parameters) in the software create vulnerabilities. This concerns ElGamal signatures (selectable in "expert mode" over the default of DSA). The attack is very efficient, requiring only one signature and one second of CPU time. As mitigation, the use of DSA is suggested by the authors.