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.

Bar-Ilan Winter School on Cryptography - New trapdoors for Lattices. Simpler, Tighter, Faster, Smaller

This week some members of the group have been in Tel Aviv for the 2nd Bar-Ilan Winter School on Cryptography - Lattice-based Cryptography and Applications. The school was really well organized and useful: the programme was diversified (basics and hard problems on lattices, cryptographic constructions based on lattices, recent advances in fully homomorphic encryption), yet coherent and interesting for everyone.

In the session "Trapdoors and Application'', Chris Peikert presented some aspects of the joint work with Daniele Micciancio ([MP2012]) which will be published at Eurocrypt 2012.

The main idea of this work is a new method of generating random lattices  Λ┴(A) (defined by an uniformly random matrix A  in Z_q^{n x m}) together with an associated secret "strong''  trapdoor  ([GPV08])  S in Z_q^{m x m}, i.e.  short basis for Λ┴(A).  Such strong trapdoors are then used to give specialized inversion algorithms for the functions

                 f_A (x) = Ax  mod q    and   g_A (s; e) = s^t A + e^t      mod q

where  q=poly(n)  and   x, e are short integer vectors.

Recall that many cryptographic applications need to sample preimages for the SIS function f_A and/or invert the LWE function g_A  (Hash-and-sign digital signatures [GPV08], Standard Model signatures [CHKP10, R10, Boy10 ], SM CCA-secure encryption [PVW08,  Pei09], SM (H)IBE [GPV08, CHKP10, ABB10a , ABB10b]), and that general methods to solve these tasks are already known ([Bab85] for inverting  g_A  and [Klein01Klein00, GPV08, Pei10] for preimage sampling of  f_A) but they are complex and they trade quality for efficiency.

The general idea of the new method of trapdoor generation is the following. They design a fixed well-structured  public lattice defined by a ``gadget'' matrix  G for which the associated functions f_G and g_G admit fast, parallel and high-quality inversion algorithms.
Then they randomize G in two steps:

1. define a semi-random matrix  B = [ A |  G] for uniform A in  Z^{n x m'},  m' sufficiently large; 
2. apply to this matrix  B a  "nice'' unimodular transformation T and let  A =  B T.
    

 At this point the unimodular transformation  will be a trapdoor for A, and preimage sampling for   f_A and inversion of  g_A reduces efficiently to the corresponding tasks for  f_G and g_G.

It is worth to note that for G=0 we get Ajtai's original method ([Ajt96]) for constructing a random A together with a ``weak'' trapdoor of one or more short vectors (but not a full basis), while the comparison with the GGH approach ([GGH97]) is not appropriate as in GGH the private and public
lattices are the same.

The new trapdoor is an easily generated unimodular transformation instead of a short basis of a lattice as in  Ajt99 and AP09, but is at least as powerful since we can efficiently construct a basis for Λ┴(A) from a basis of Λ┴(G) and T. This new method does not require computations of Hermite normal forms or matrix inverses but only one matrix multiplication and the  inversion operations drastically decrease in comparison with the prior and general algorithms for these tasks.

The slides and the video of  the lecture will be available in the school website http://crypto.biu.ac.il/winterschool2012/.