Software Protection and Simulation on Oblivious RAMs

In the talk “Software Protection and Simulation on Oblivious RAMs”, we explored a very different and amazing side of Secure Computation that shows how widespread its applications are. The major motivation for designing Oblivious RAM (ORAM) was to prevent duplication of software. We know that to keep the contents of the memory secure, we can use an appropriate encryption scheme to encrypt the program code and data. Is that enough? No - Software protection needs to go beyond that.

An adversary can get valuable information looking at the sequence of memory accesses. Access patterns in programs having properties like, say, a loop structure for instance, can leak some information about the program / the input in the program execution. Consider the example of a sorting program – Suppose the adversary only knows that the program is a sorting algorithm, looking at the access patterns he may be able to figure out what kind of sorting algorithm is used – for example in case of a binary search. An adversary can conduct some experiments with different inputs and get more information than he is supposed to; by looking at the sequence of memory accesses. Oblivious RAM is proposed as a solution to prevent this type of security breach.               

What does “oblivious” mean in the context of machines? – A machine is oblivious if the sequence in which it accesses memory locations is equivalent for any two inputs with the same running time. We consider the following setup - CPU has a small number of registers which can be shielded but the encrypted data and program is not shielded. The adversary cannot inspect or modify the contents of the CPU registers but can see the communication between the CPU and memory. Consider a “smart CPU” that handles the program execution in such a way that the memory access patterns leak no extra information to the adversary. We looked at two different definitions –

1)      Consider two cases when given an encrypted program as input –

(a)    Let { ap₁ } denote the memory access pattern when the program is run on smart CPU.

(b)   Let { ap₂ } denote the memory access pattern when a dummy program with same running time is run on fake CPU.

The smart CPU achieves obliviousness if the access patterns are computationally indistinguishable. Mathematically, it can be denoted as { ap₁} » { ap₂}

2)      The conditional probability for a particular input given a sequence of memory accesses which occur during an execution on that input, equals the apriori probability for that particular input. Mathematically, this can be denoted as Pr[Input|{ap}] = Pr[Input]  

Let us look at a couple of ways to design such a smart CPU. Suppose a program runs in “t” steps. Here “t” is the number of memory accesses which can be either a read/ update or a write instruction. Suppose M denotes the content of the RAM. Its size can be denoted by |M| = m. We assume m >>> t. Memory contents of the ORAM are of the form (v, x) where v denotes the virtual address in the actual RAM and x denotes the data at that address.

A trivial way to design a smart CPU that can achieve obliviousness is as follows - For every access, the CPU scans the entire memory content. This will have O(t.m) complexity. This will clearly serve the purpose to defeat the adversary since for every access, irrespective of the input, all the locations of the memory are accessed. So the adversary will not be able to distinguish when the same program is run with two different inputs. The goal has been achieved but at a very high cost. We will see how this can be optimized.

 Let us look at the “square root” algorithm – RAM is simulated by an oblivious RAM of size (m + 2√m) as shown.

m words

√m dummy words

√m shelter words

Initialization : The first (m+√m) locations are allotted to the virtual m memory words and √m dummy words. The remaining √m locations serve to store shelter words as we shall see.

The algorithm runs in epoch of √m steps. In each epoch –

A.      Contents of locations from 1 to (m + √m) are randomly permuted. Let π(v) denote the current location of address v in this epoch.

B.      Shelter is used to maintain the values retrieved in the current epoch.

Consider a single memory access to virtual address ‘v’. There is a boolean variable “found” stored in one of the CPU register initialized to false. 

1.       First the entire shelter is scanned to check whether (v,x) is present in the shelter. If the address is found, the variable “found” is set to true and the scan is continued till the entire shelter has been scanned.

2.       If the address was not found in the shelter, it is retrieved from the actual word π(v) which is the current location of the content of address v in this epoch.

3.       If the virtual address had been found in the shelter, we still need to make an access in the first (m+√m) locations to maintain the obliviousness. We access a dummy word at location (m + count) which is currently present at π(m + count). “count” is a variable that increments through the √m steps of the epoch so that different dummy words are accessed in each iteration.

4.       Now the value retrieved (updated value if there was a change, the same value otherwise) is encrypted and written into the first empty location at the shelter. All the shelter words are scanned again. Since the encryption is randomized, the adversary will not be able to distinguish if the same value was written back or the updated value.

Analysis - The access pattern is independent of the input – For each virtual access we scan through the entire shelter (√m locations), then we access one location among the first (m + √m) locations (either the actual word location or the dummy word location – this cannot be distinguished since these locations are in permuted order) and during the write-back we access √m locations of the shelter again. Thus we access a total of (2√m + 1) locations for every virtual address access. The adversary will not be able to get any additional information looking at this access pattern.

How is the permutation on the first (m + √m) locations done? The elements are tagged with randomly chosen integers drawn from the set T = {1, 2 …… n²/Ꜫ }. Say τ: {1,2…n} à T is the function that does the random allocation of tags. Then π(i) = k iff  τ(i) is the kth smallest element in { τ(j) : 1<= j <= n} . The n elements can be sorted according to the tags using Batcher’s oblivious sorting. So, suppose we want to access a location i – we actually need to perform a binary search on the tag τ(i). This is how we can retrieve the location π(i) . So what we had considered as a single access for π(i) is actually log (m+√m) accesses needed for the binary search for the tag. We need a total of (2√m + log (m+√m)) = O(√m) accesses for every virtual address access. Thus, this algorithm shows a way to simulate ORAM of size (m + 2√m) and with a complexity of O(t.√m) accesses for t virtual address accesses.

                                              

Software Protection and Simulations on Oblivious RAMs

This paper provides a "theoretical treatment of software protection" by reducing the problem to the problem of efficient simulation on oblivious RAM. It tries to create a smart system which can defeat the adversary who is trying to duplicate the software. 

The problem with our normal software (even if encrypted) is that, adversary can view the memory access patterns made by the processor and infer the underlying algorithm. The adversary can run the program multiple times and record the patterns of memory accesses each time. As a simple example, take the binary search algorithm.  

Example Attack on Normal Systems

The processor will initially access the middle element and the depending on that element, will either access the middle element in the left half or the middle element in the right half and so on. The adversary has access to the memory and can see the (encrypted) data flowing from memory to the CPU. By noticing this access pattern the adversary can ascertain with high confidence that binary search is used in the underlying software. 

So there is a need to hide the data in the memory as well as the memory accesses (type and address) made by the CPU. The adversary should not be able to infer anything new by looking at the access pattern.  

Role of Hardware 

The paper claims that purely software-based solution is impossible to prevent piracy since any software (even if encrypted) can be copied bit by bit and can be run on any machine. Therefore a Software-Hardware-package consisting of a physically shielded CPU and an encrypted program needs to be used. 

Shielded CPU: 

·           Has a small amount of storage (registers) 

·          Will run the encrypted program using the memory and other components of the computer 

·          Has to be physically shielded (meaning adversary cannot see what is happening inside and cannot interfere with it in any way) 

The adversary tries to learn the software by initiating executions of the encrypted program on a choice of inputs and watching both the memory contents and the communication between CPU and memory. 

The CPU defeats the adversary if no probabilistic polynomial-time adversary can distinguish  

So there are two types of protection that is needed 

1.             The program along with the data needs to be encrypted 

2.              The access patterns must be hidden 

The example of binary search shows that encryption alone is not sufficient. We call a machine oblivious if the sequence in which it accesses memory locations is equivalent for any two inputs with the same running time. 

Hiding Access Patterns – Trivial Method 

Whenever CPU needs to access a variable, the entire contents of the memory is read and written in some fixed order. This shows that it is possible to completely hide the access pattern. For deterministic schemes, this is the best technique.  To do better, randomization needs to be introduced. 

Hiding Access Patterns – ORAM 

To hide the access patterns, RAM need to be simulated in an oblivious way. To do that ORAM technique is used. 

Let M be the RAM we need to simulate and let m=|M| 

Number of accesses is t. 

To simulate RAM of size m, ORAM of size m+2√m is required 

The ORAM can be visualized as 

<Virtual>	<Dummy>	<Shelter>
m	√m	√m

Each entry in the ORAM is of the form (v_i,d_i) where v_i is the address in the original RAM and d_i is the data stored at v_i. 

√m dummy values along with the m actual contents of the RAM are permuted in some random order using the permutation π(1, ..., m +√m ) and placed in the first m +√m locations (Virtual + Dummy) of the ORAM (rest are filled with empty values).  This permutation is done using Batcher's sorting network and the randomization comes from inside the secure CPU. So after this permutation, the adversary cannot make out the mapping of the order in ORAM to the actual order. 

The CPU keeps a counter count that counts the number of memory accesses. Initially this is kept to zero. 

1.       The CPU is trying to access address v_i . 

2.       Initialize found flag = false 

3.       First go to the shelter and scan (read) every element. Even if the address has been found, continue scanning. Total √m accesses. If v_i is found, set flag=true. 

4.       If flag=false, go to π(i) and take it to CPU. 

·          Write it back to count position of shelter. 

5.       If flag=true, go to π(m+count). This will be in the dummy part of ORAM. This is done so that adversary cannot learn whether a new address was accessed or an old one. 

6.       After accessing the updating is done on the shelter. If the address was found on the shelter, then that location is updated. Else the leftmost empty is updated.

7.       If count=m, permute again and repeat. 

In order to permute again, sort first based on v and then based on σ where σ=0 means the value was modified and σ=1 means it is unmodified. Then all the entries with σ=1 is made as empty in the sorted order. The permutation has to ensure that all the empty values will go to the shelter.

After the permutation, the first m+√m entries will have the m data along with some dummy data. The process can be repeated then.

Correctness

All the memory accesses look the same to the adversary.

Step 3 - √m accesses are fixed

Step 4 and Step 5 – are indistinguishable because the original data has been randomized throughout the first m+√m entries.

Step 6 - √m accesses are fixed

References:

Goldreich, O., Ostrovsky, R.: Software protection and simulation by oblivious RAMs. JACM (1996)

Improved OT Extension for Transferring Short Secrets

In this post, we see an efficient Oblivious Transfer (OT) Extension technique for short secrets.  The OT extension protocol of IKNP stands as the basis for this protocol. The building block is an IKNP-based framework for 1-out-of-n OT extension. Before going into the details of the protocol, let’s have a quick overview of the IKNP protocol.

IKNP Protocol

We assume the existence of a correlation-robust hash function, H, and the protocol works in the static semi-honest security model.

Protocol Overview

S first acts as the receiver and R as the sender in the underlying k OTs. S chooses a random string s ∈ {0,1}^k as the selection bits and R inputs (tⁱ, tⁱ ⊕ r), i ∈ [k], tⁱ ∈ {0,1}ⁿ where r are the actual selection bits of R. S calls her ith chosen message in the underlying OTs qⁱ = tⁱ ⊕ s_i .r, where qⁱ is the ith column of a m x k matrix Q. Note that jth row of matrix Q, q_j = t_j ⊕ r_j . s. Finally, S sends the actual messages by sending z_j,0 = H(q_j) ⊕ x_j,0 and z_j,1 = H(q_j ⊕ s) ⊕ x_j,1 and R recovers x_j,ri by computing x_j,ri = H(t_i) ⊕ z_j,ri , where j ∈ [m] and H(∙) is the hash function.

Protocol Efficiency

The protocol makes a single call to OT^k_m. In addition, each party evaluates at most 2m times (an implementation of) a random oracle mapping k+log m bits to l bits. All other costs are negligible. The cost of OT^k_m is no more than k times the cost of OT¹_k (the type of OT realized by most direct implementations) plus a generation of 2m pseudo-random bits. In terms of round complexity, the protocol requires a single message from S to R in addition to the round complexity of the OT^k_m implementation. To summarize, the communication complexity of IKNP is O(m(k+l)) and for bit messages (l=1), the complexity turns out to be O(mk).

Now we can look to the efficient Oblivious Transfer (OT) Extension protocol of KK13. The main difference from IKNP is that each row of the matrix possessed by S is now used to perform a 1-out-of-n OT instead of 1-out-of-2, but of shorter secrets. On a very intuitive level, the protocol works as follows: Let C denote a binary code, and let r_j denote the input of R to the j-th instance of 1-out-of-n OT. For each row j, S receives (via OT) the actual j-th row of the m x k matrix XORed with a vector that is the result of the r_j-th codeword in C bitwise ANDed with the k-bit selection vector. This allows S to generate n random pads from each row of the matrix- the i-th such pad being the j-th row it received (via OT) XORed with a vector that is the result of the i-th codeword in C bitwise ANDed with the k bit selection vector. These n random pads may then be used by S to carry out a 1-out-of-n OT with R

KK Protocol

We assume the existence of a hash function (in the random oracle model), H, and the protocol works in the static semi-honest security model. It trades the length of messages for more gained OTs from the extensions.

Protocol Overview

Input of S is m tuples (x_j,0, … ,x_j,n-1) of l-bit strings while input of R is an m element selection vector r = (r₁, … , r_m) where each r_i can ranges from 1 to n. S first acts as the receiver and R as the sender in the underlying k OTs. S chooses a random string s ∈ {0,1}^k as the selection bits. R forms m x k matrices T₀ and T₁ in the following way: Choose t_j,0 , t_j,1 ← {0,1}^k  at random such that t_j,0 ⊕  t_j,1 = c_rj , where c_rj  is a Walsh-Hadamard code. R then inputs {(t_j,0, t_j,1)}_j∈[k]  for each of the k base OTs. S calls her ith chosen message in the underlying OTs qⁱ = t_i,si , where qⁱ is the ith column of a m x k matrix Q. Note that jth row of matrix Q, q_j = t_j,0 ⊕ c_rj . s. Finally, S sends  messages z_j,r = x_j,r ⊕ H(j, q_j ⊕ c_r.s) for 1≤ r ≤ n  and R recovers x_j,ri by computing x_j,ri = H(j,t_j,0) ⊕ z_j,ri , where j ∈ [m] and H(∙) is the hash function.

Protocol Efficiency

The protocol makes a single call to OT^k_m. The cost of OT^k_m is the cost of OT^k_k (which is independent of m) plus a generation of 2k pseudo-random strings each of length m. Other than this, each party evaluates at most mn times a random oracle. Thus the total communication cost of  OT^m_l is the communication cost of implementing OT^k_m plus mnl bits transferred between S and R, which turns out to be O(m(k+nl). In the semi-honest model, a single instance of 1-out-of-n OT may be used to generate log n instances of 1-out-of-2 OT over slightly shorter strings with no additional cost. More precisely, the cost of OT^m_l is exactly equal to the cost of 1-out-of-n OT^{m/log n}_{l.log n} . To summarize, the communication complexity of KK for 1-out-of-2 OT extension is O(mk / log(k/l) ) and for bit messages (l=1), the complexity turns out to be O(mk / log k).

BMR: Extended version of Yao's protocol for n players

Here we discuss how to extend Yao's protocol for any arbitrary 'n' players. In Yao's protocol, the responsibilities of the two players (Circuit constructor and Circuit Evaluator) are not at all alike. Hence, it is not trivial to see how to extend the protocol for any 'n' number of parties.

We start by assuming that the logical circuit C corresponding to the multi-party computation function f is already given, and we expect Semi-honest behaviour (at worst) from the parties, and the threshold for corrupted parties is (n-1).

In this extended protocol (BMR protocol), both construction and evaluation of the circuit is done collaboratively. Now we see how the protocol works.

BMR Protocol is having an Offline Phase and an Online Phase.

Offline Phase:

In the offline phase, we need to know nothing other than the circuit. Let there be 'W' wires in the circuit, indexed from 0 to W-1. At first, all players will (collaboratively) choose one random bit for each wire, namely λ­₀, λ­_1…, λ­_­w-1. Each λ­_i values are secret shared among all n parties. Then λ_j is reconstructed to party P_i, if ‘j’ is one of the input wires of P_i.

Now, each player will choose two random string (we call them 'two seeds') of length 'k', for each wire. Without loss of generality, we name those seeds s_­­­­­­­­­ⁱ_w,0 and s_­­­­­­­­­ⁱ_w,1 for each player i, for each wire w. Now we define SuperSeed for a wire w.

            S_w,0 = s¹_w,0 || s²_w,0 || .. sⁱ_w,0 .. || sⁿ_w,0

            S_w,1 = s¹_w,1 || s²_w,1 || .. sⁱ_w,1 .. || sⁿ_w,1

These two SuperSeeds will act as two different keys, and bears the meaning of the bits; just like two keys for each wire in Yao's protocol. But here, the SuperSeed S_­w,j need not represent the bit 'j' ; instead S_w,0 represent the bit λ­_w, and S_w,0 represent the bit λ­_w^c.

Please note that individual players know only their seeds on each wire, and λ values of all wires.

For the implementation of 4 (generally, but for NOT gate it’s 2) encryption boxes of a logic gate, We need two PRGs G¹ and G² both maps {0,1}^k → {0,1}^nk. Let a and b be the input wires of the gate g, and c be output wire of g. The cyphertexts corresponding to each Encryption Box is of the form:

Box 1: C₁ := ( G¹_­(s¹_a,0) ⊕ G¹_­(s²_a,0) .. ⊕ G¹_­(sⁿ_a,0) ) ⊕ ( G¹_­(s¹_b,0) ⊕ G¹_­(s²_b,0) .. ⊕ G¹_­(sⁿ_b,0) ) ⊕ S_c,r  ,

(Where r = 0 if g(λ_a, λ_b) = λ_c ; r = 1 otherwise)

Box 2: C₂ := ( G²_­(s¹_a,0) ⊕ G²_­(s²_a,0) .. ⊕ G²_­(sⁿ_a,0) ) ⊕ ( G¹_­(s¹_b,1) ⊕ G¹_­(s²_b,1) .. ⊕ G¹_­(sⁿ_b,1) ) ⊕ S_c,r  ,

(Where r = 0 if g(λ_a, λ_b^c) = λ_c ; r = 1 otherwise)

Box 3: C₃ := ( G¹_­(s¹_a,1) ⊕ G¹_­(s²_a,1) .. ⊕ G¹_­(sⁿ_a,1) ) ⊕ ( G²_­(s¹_b,0) ⊕ G²_­(s²_b,0) .. ⊕ G²_­(sⁿ_b,0) ) ⊕ S_c,r  ,

(Where r = 0 if g(λ_a^c_, λ_b) = λ_c ; r = 1 otherwise)

Box 4: C₄ := ( G²_­(s¹_a,1) ⊕ G²_­(s²_a,1) .. ⊕ G²_­(sⁿ_a,1) ) ⊕ ( G²_­(s¹_b,1) ⊕ G²_­(s²_b,1) .. ⊕ G²_­(sⁿ_b,1) ) ⊕ S_c,r  ,

(Where r =0 if g(λ_a^c_, λ_b^c) = λ_c ; r = 1 otherwise)

We can see that, if each party just shares the PRG outputs of both seeds for the computation of these 4 cypherboxes and adversary have corrupted t parties, then the adversary can gain extra information about the messages in the boxes, that are not supposed to open in an execution (For eg: if t = n-1, and without loss of generality P₁ is the only honest player, then G¹(s¹_a,0)), G²(s¹_a,0)), G¹(s¹_a,1)), G²(s¹_a,1)) are leaked to the adversary, and he can compute all the S_c,r in all Boxes). So C₁, C₂, C₃ and C₄ should be a computed only by a Multi-Party Computation function. If that’s the case, adversary, who doesn’t know the seed(s) of honest party, will see the cypherboxes as One-Time padded messages with PRG outputs.

Now the λ_i for all output wires i are reconstructed and shared with every party. In the end of Offline phase, every party P_i knows,

•          2 Seeds of each wires
•          4 Cypherboxes for each gate g
•          Secret share of λ_j , for all wires j
•          λ_k , for all output wire k
•          λ_m , for all input wire (m) of the party P_i

Online Phase

Each party will evaluate the circuit in this phase. All parties know their input to their input wires. We define a new bit Δ_j of a wire j as follows:

                        Δ_j = b_j ⊕ λ_j

where b_j is the actual bit in a wire, in a specific evaluation. The Δ_j value of the input wire j of P_i can be calculated by the party P_i only; because only P_i knows λ_j. But everybody needs Δ to evaluate the circuit. So the owner of the input wire(s) will broadcast the Δ values of his input wires. In fact, after this step, all parties will get to know the Δ values of all the input wires in the circuit. For decrypting one logic gate, we need exactly one SuperSeed for each input wire. So every party will share their seeds sⁱ_w,Δ_w so that every party will get exactly one SuperSeed corresponding to Δ_j for each input wire j. With this information, players can decrypt exactly one CypherBox as follows:

Δa	Δb	Decryptable Box
0	0	C1
0	1	C2
1	0	C3
1	1	C­4

Using the SuperSeeds S_a,Δ_a and S_b,Δ_b , all parties can decrypt the CypherBox and get the SuperSeed of the output wire, and so on. But it’s not clear how to get Δ value of the new (output) wire. But every player knows their seeds on all the wires, and SuperSeed is nothing but appending all the seeds of players. So he will just check the seed bits corresponding to that player ((i-1)*k + 1 to i*k for player P_i) in the SuperSeed. If that happened to be equal to sⁱ_c,0 then the Δ_c is 0. Otherwise, it will be 1.

In short, after computing and sharing Δ_w values and SuperSeeds S_w,_Δw of all input wires w, no other communication between the parties are required. The entire circuit evaluation is done as local computation. Note that, Δ values are found and propagated in the circuit. As far as λ values are chosen random, by disclosing Δ values, no information about the actual bit b will be leaked.

Correctness

Consider the case when Δ_a = Δ_b = 0. We have to prove that Δ_c and S_c,Δc are correctly computed.

Δ_a = 0 ⇒ b_a = λ_a

Δ_b = 0 ⇒ b_b = λ_b

As per the table of decryptable cypherboxes, we will decrypt C₁.

• If g(λ_a, λ_b) = λ_c , that means g(b_a, b_b) = λ_c and we will be encrypting S_c,0 as message, in C₁ (see definition). We can see that Δ_c = 0, which is consistent with the definition of Δ. In this case,

1.      g(b_a, b_b) = λ_c

2.      g(b_a, b_b) = b_c

1 & 2 ⇒ λ_c = b_c

           ⇒ Δ_c = b_c ⊕ λ_c = 0

•  If g(λ_a, λ_b) = λ_c^c , that means g(b_a, b_b) = λ_c^c. We will de deciphering C₁, which is an encryption of SuperSeed S_c,1. We see Δ_c = 1 here, and consistent with definition of Δ. Here,

1.      g(b_a, b_b) = λ_c^c

2.      g(b_a, b_b) = b_c

1 & 2 ⇒ λ_c = b_c^c

          ⇒ Δ_c = λ_c ⊕ b_c  =  b_c^c ⊕ b_c = 1

When both Δ_a and Δ_b are 0, SuperSeed and Δ_c calculated are shown to be correct. All the other cypherboxes, we can prove with similar argument.

At the end of circuit evaluation, all parties will get to know the Δ values of output wires. We know the λ values of output wires (shared in offline phase). Hence we can compute b_c using the equation b_c =  λ_c ⊕ Δ_c  for each output wire c.