4005-730 -- Distributed Systems

Alan Kaminsky

•

Department of Computer Science

•

Rochester Institute of Technology

•

4486 + 2220 = 6706

Home Page

Distributed Systems

4005-730-01

Spring Quarter 2013

Course Page

4005-730 Distributed Systems
Lecture Notes -- Module 10. Cloud/Grid Computing

Prof. Alan Kaminsky
Rochester Institute of Technology -- Department of Computer Science

The Cloud

http://xkcd.com/908/

http://www.dilbert.com/2012-10-21/

http://www.dilbert.com/2013-01-09/

Grid Computing

Grid computing provides unified access to heterogeneous, geographically dispersed computational resources
- Supercomputers
- Visualization computers
- File systems
- Software
Grid computing is usually associated with computational science and engineering
eXtreme Science and Engineering Discovery Environment (XSEDE)
- Successor to the TeraGrid
- National Science Foundation (NSF) funded
- Researchers don't pay to use XSEDE resources, but they must demonstrate funding for their projects
- Main web site: https://www.xsede.org
- User portal: https://portal.xsede.org
- XSEDE Resource Catalog: https://portal.xsede.org/web/guest-staging/resources
- Example resource: Georgia Tech Keeneland, https://www.xsede.org/web/guest/gatech-keeneland
Concepts
- User accounts and allocations
- Resources
- System monitoring
- Single sign-on remote login
- Job scheduling and execution
- Queue prediction
At the end of the day, you log into a computer and you run your program

Cloud Computing

Cloud computing provides unified access to heterogeneous, geographically dispersed computational resources
- Computers, servers
- File systems, databases
- Software
Cloud computing is a way for you to pay to use someone else's computational resources
- Rather than acquire and maintain the computational resources yourself
Use cases for cloud computing:
- Web sites, e-commerce
- Data storage
- Computational jobs
Popular cloud computing providers
- Amazon Web Services: http://aws.amazon.com/
- PiCloud: http://www.picloud.com/
I'm not all that impressed with "the cloud" per se
There are numerous issues many cloud enthusiasts tend to ignore, to do with security and privacy in the cloud

Secure Storage in the Cloud

Problem: You want to store a file of sensitive information on a cloud server
- You don't want anyone in the cloud to read the file contents
Solution: Encrypt the file; store the file in the cloud
Problem: But the file is actually a very large database
- You want the cloud server to carry out queries on the database and return only the relevant records

Example: Medical information

Name   Date      Wgt  Sys  Dia  Pul  Glu
----------------------------------------
Bob    1/1/2011  160  120  80   86   145
Carol  2/2/2011  120  118  81   94   110
Ted    3/3/2011  330  184  103  98   222
Alice  4/4/2011  140  115  76   82   101
Bob    5/5/2011  165  120  80   86   150
Carol  6/6/2011  119  118  81   94   107
Ted    7/7/2011  340  184  103  98   245
Alice  8/8/2011  135  115  76   82   103
. . .

Problem: You don't want the cloud server to know who each record is about -- private information

Solution: Store the one-way hashes of the database keys (names), not the database keys themselves

Client can query by specifying the hash of the desired name
Cloud can't determine the actual name from the hash (preimage resistant)

SHA-1(Name)                               Date      Wgt  Sys  Dia  Pul  Glu
---------------------------------------------------------------------------
a4380269bf9d4679ba39fed110b70a25ee78c457  1/1/2011  160  120  80   86   145
0cec26df63beba9d92796eb399775ae9c7693e86  2/2/2011  120  118  81   94   110
26fd617c74c7af144d2a094a3ddf83cb703373a1  3/3/2011  330  184  103  98   222
915d944fa078db55496e637522f61a6763a318c7  4/4/2011  140  115  76   82   101
a4380269bf9d4679ba39fed110b70a25ee78c457  5/5/2011  165  120  80   86   150
0cec26df63beba9d92796eb399775ae9c7693e86  6/6/2011  119  118  81   94   107
26fd617c74c7af144d2a094a3ddf83cb703373a1  7/7/2011  340  184  103  98   245
915d944fa078db55496e637522f61a6763a318c7  8/8/2011  135  115  76   82   103
. . .

Problem: But anyone can still look up Bob's records simply by querying with key = SHA-1("Bob")

Solution: Use a keyed hash function, i.e., a MAC, with a secret MAC key known only to the client

Client can query by specifying the MAC of the desired name
Cloud can't determine the actual name from the MAC (preimage resistant)
Cloud can't troll for data on specific names (MAC key is secret)

HMAC-SHA-1(Name,MAC-key)                  Date      Wgt  Sys  Dia  Pul  Glu
---------------------------------------------------------------------------
5e2a92841025963ed27faac1beec172c37e74006  1/1/2011  160  120  80   86   145
ccd3a41ce33cf4d53891e5e822cf30de56d186ea  2/2/2011  120  118  81   94   110
5e59ce29123598164ff8acd924046dbd5b157836  3/3/2011  330  184  103  98   222
99347b93d9522b73928cf75b16984490bffc25b4  4/4/2011  140  115  76   82   101
5e2a92841025963ed27faac1beec172c37e74006  5/5/2011  165  120  80   86   150
ccd3a41ce33cf4d53891e5e822cf30de56d186ea  6/6/2011  119  118  81   94   107
5e59ce29123598164ff8acd924046dbd5b157836  7/7/2011  340  184  103  98   245
99347b93d9522b73928cf75b16984490bffc25b4  8/8/2011  135  115  76   82   103
. . .

Problem: The cloud might accidentally or maliciously alter the stored data
Solution: Include a MAC of the entire record as an additional column
- Any tampering will be detected
- Not much we can do if the cloud alters the key field or deletes the entire record
- Need redundant copies of the database to deal with that
Problem: The cloud can't see the actual name, but it can see the other data
Solution: Encrypt each record (except the first column), using a secret encryption key known only to the client
- Either encrypt each column separately
- Or encrypt the whole record into one binary "blob"
- Include the MAC inside the encryption, to detect tampering
- We can still use the cloud's enormous database retrieval power to query for (encrypted) records based on (MACs of) names
- Decryption of the records takes place in the client, not in the cloud
There is a large and growing body of research on the topic of Private Information Retrieval
One interesting example:
- E. Blass, R. Di Pietro, R. Molva, and M. Onen. PRISM -- privacy-preserving search in MapReduce. Cryptology ePrint Archive, Report 2011/244, May 9, 2012. http://eprint.iacr.org/2011/244
- Given a group of large files, containing encrypted words, stored in the cloud . . .
- Determine which file(s) contain a given target word . . .
- By running a map-reduce job over the files in the cloud . . .
- Without the cloud learning what the words in the files are (data privacy) . . .
- And without the cloud learning what the target word is (query privacy, of input) . . .
- And without the cloud learning which file(s) contain the target word (query privacy, of output)
For further information and case studies:
- P. Wayner. Translucent Databases. Flyzone Press, 2002.
Problem: We might want the cloud to do more than just store and query databases
- We might want to do computations in the cloud as well
- But we still don't want the cloud to breach the privacy of the data
Solution . . .

Secure Computation in the Cloud: Scenarios

Scenario 1
- Client trusts server to do the computation correctly
- Client allows server to see intermediate and final results
- Client does not allow server to see input data
Scenario 2
- Client trusts server to do the computation correctly
- Client does not allow server to see intermediate and final results
- Client does not allow server to see input data
Scenario 3
- Client does not trust server to do the computation correctly
- Client does not allow server to see intermediate and final results
- Client does not allow server to see input data

Scenario 1: Private Input Data

Scenario 1
- Client trusts server to do the computation correctly
- Client allows server to see intermediate and final results
- Client does not allow server to see input data
Example: Database of executive bonuses stored in the cloud
Compute average bonus on the cloud server
- But we don't want anyone (e.g., the Occupy Wall Street protesters) to learn any executive's individual bonus
Solution
- Let m be a number greater than the sum of all the bonuses, e.g. m = 2³² (2⁶⁴?)
- For each bonus b_i, 1 ≤ i ≤ n, client picks a random number 0 ≤ r_i ≤ m−1 and computes c_i = b_i + r_i (mod m)
- Client stores a database of (name_i, c_i) entries in the cloud
- Client sends r = (Σ_i r_i) (mod m) to the server
- Server computes average bonus = ((Σ_i c_i) − r (mod m))/n

Example with m = 10⁹ -- server sees only the bold numbers

i       b_i        r_i        c_i
1     10000  167640642  167650642
2     20000  371105802  371125802
3     30000  746227085  746257085
4     40000  173922523  173962523
5     50000  619069655  619119655
Sum  150000   77965707   78115707 - 77965707 = 150000

Security
- If m is large enough, there is no way the server can figure out the individual r_i values, given their sum r
  - Integer partition problem
- So the server cannot figure out the b_i values, given the c_i values
- The server does know the sum and the average of the bonuses, but we said that's okay
- Also, there is no way the server can figure out the individual b_i values from their sum
There is a large and growing body of research on the topic of Functional Encryption
- D. Boneh, A. Sahai, and B. Waters. Functional encryption: a new vision for public-key cryptography. Communications of the ACM, 55(11):56-64, November 2012.
- There is a trusted third party (TTP)
- Anyone can encrypt data using a public encryption key EK: Ciphertext = Encrypt (EK, data)
- Anyone can give a function F to the TTP
- The TTP responds with a decryption key tied to that function, DK_F
- Anyone can now compute Decrypt (DK_F, ciphertext)
- The result is F(data)
- You don't learn what the data is, only the result of applying F to the encrypted data

Scenario 2: Private Input and Output Data

Scenario 2
- Client trusts server to do the computation correctly
- Client does not allow server to see intermediate and final results
- Client does not allow server to see input data
Way back in 1978, Rivest, Adleman, and Dertouzos proposed privacy homomorphisms for computing on encrypted data
- R. Rivest, L. Adleman, and M. Dertouzos. On data banks and privacy homomorphisms. In Foundations of Secure Computation, Academic Press, 1978, pages 169-177. http://people.csail.mit.edu/rivest/RivestAdlemanDertouzos-OnDataBanksAndPrivacyHomomorphisms.pdf
Homomorphism
- Given:
  - A function f(x₁,x₂,...,x_n)
  - Another function g(y₁,y₂,...,y_n)
  - An encoding function e(x)
- If, for all x₁, x₂, . . . , x_n, e(f(x₁,x₂,...,x_n)) = g(e(x₁),e(x₂),...,e(x_n)), then e is a homomorphism from g onto f
Privacy homomorphism
- Same as above, plus:
- e(x) is a cryptographically secure encryption function
- d(x) is the corresponding decryption function
Then we can do computation on encrypted data as follows:
- Input data x₁, x₂, . . . , x_n
- p = f(x₁,x₂,...,x_n) is the computation we want to do on the data
- g computes the encryption of f on the encryption of the data
- Encrypt data: y₁ = e(x₁), y₂ = e(x₂), y_n = e(x_n)
- Compute on encrypted data: c = g(y₁,y₂,...,y_n)
- Decrypt result: p = d(c)
In the cloud
- Client encrypts data
- Client stores encrypted data in the cloud
- Client tells cloud server to compute g on encrypted data
- Cloud server sends c to client
- Client decrypts c
- Note that cloud server does not need to know the encryption key -- the computation g yields the encrypted result directly
Example: Encrypted addition with discrete logarithms
- Let p and q be (secret) large prime numbers, n = pq (public) (same as RSA)
- Let r be a generator for Z_p^*
- Let p−1 be "smooth," i.e. have only small prime factors, so that computing discrete logarithms in Z_p^* is easy
- Unencrypted computation: f(x₁,x₂) = x₁ + x₂ (mod p−1)
- Encryption: y₁ = r^x₁ (mod n), y₂ = r^x₂ (mod n)
- Encrypted computation: g(y₁,y₂) = y₁⋅y₂ (mod n)
- This works because g(y₁,y₂) = y₁⋅y₂ (mod n) = r^x₁⋅r^x₂ (mod n) = r^x₁+x₂ (mod n) = e(f(x₁,x₂))
- Decryption: Find the discrete logarithm to the base r (mod p) of r^x₁+x₂; this yields x₁ + x₂
- The server can't decrypt the input data or the answer because the server doesn't know p, the server only knows n
Example: Encrypted multiplication with RSA
- Unencrypted computation: f(x₁,x₂) = x₁⋅x₂ (mod n)
- Encryption: y₁ = x₁^a (mod n), y₂ = x₂^a (mod n)
  - (a, n) is the RSA public encryption key
- Encrypted computation: g(y₁,y₂) = y₁⋅y₂ (mod n)
- This works because g(y₁,y₂) = y₁⋅y₂ (mod n) = x₁^a⋅x₂^a (mod n) = (x₁⋅x₂)^a (mod n) = f(x₁,x₂)^a (mod n) = e(f(x₁,x₂))
- Decryption: Use the RSA private decryption key
- The server can't decrypt the input data or the answer because the server doesn't know the RSA private decryption key
Problem:
- It's easy to do encrypted addition
- It's easy to do encrypted multiplication
- It's not so easy to do both addition and multiplication in the same encrypted system
Solution: Homomorphic encryption

Homomorphic Encryption

M. van Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan. Fully homomorphic encryption over the integers. Advances in Cryptology -- EUROCRYPT 2010, pages 24-43, 2010.
Key generation
- p = an n-bit odd integer (2ⁿ⁻¹ < p < 2ⁿ)
Encryption of a single bit m ∈ {0, 1}
- Choose a random integer q
- Choose a random integer r
- Ciphertext c = pq + 2r + m
- The ciphertext is a (large) number, not a single bit
- r is random "noise" that conceals the plaintext bit m
- q conceals the key p
Decryption of a ciphertext c
- m = (c mod p) mod 2
- This works because (c mod p) mod 2 = ((pq + 2r + m) mod p) mod 2 = (2r + m) mod 2 = m mod 2 = m
Homomorphic addition
- Plaintext bits m₁ and m₂
- Corresponding ciphertexts c₁ and c₂
- Then c₁ + c₂ is the encryption of (m₁ + m₂) mod 2
- To see this, decrypt the sum of the ciphertexts:
- ((c₁ + c₂) mod p) mod 2
  = ((pq₁ + 2r₁ + m₁ + pq₂ + 2r₂ + m₂) mod p) mod 2
  = (2r₁ + m₁ + 2r₂ + m₂) mod 2
  = (m₁ + m₂) mod 2
Homomorphic multiplication
- Plaintext bits m₁ and m₂
- Corresponding ciphertexts c₁ and c₂
- Then c₁c₂ is the encryption of (m₁m₂) mod 2
- To see this, decrypt the product of the ciphertexts:
- ((c₁c₂) mod p) mod 2
  = ((pq₁ + 2r₁ + m₁)(pq₂ + 2r₂ + m₂) mod p) mod 2
  = ((p²q₁q₂ + 2pq₁r₂ + pq₁m₂ + 2pq₂r₁ + 4r₁r₂ + 2r₁m₂ + pq₂m₁ + 2r₂m₁ + m₁m₂) mod p) mod 2
  = (4r₁r₂ + 2r₁m₂ + 2r₂m₁ + m₁m₂) mod 2
  = (m₁m₂) mod 2
We can now compute the encryption of (m₁ + m₂) mod 2, which is a two-input XOR gate
We can now compute the encryption of (m₁m₂) mod 2, which is a two-input AND gate
We can now compute the encryption of any Boolean function of any number of encrypted input bits
- By building the Boolean function out of two-input XOR and AND gates
We can now compute the encryption of arbitrary functions of any number of encrypted inputs
- By expressing the desired function as a Boolean function
- Sums, products, polynomials, comparators, etc.
The formulas for adding and multiplying encrypted bits can also be used for adding and multiplying encrypted integers (see paper)
Recommended sizes for a "security parameter" of λ = 64 bits
- Random number r: λ = 64 bits
- Key p: λ² = 4,096 bits
- Product pq: λ⁵ = 1,073,741,824 bits
- r needs to be large enough to prevent brute force attacks on the noise (2⁶⁴)
- p and q need to be so large to prevent attacks that try to find p
Problem Number 1: For one single plaintext bit, the ciphertext is λ⁵ = 1,073,741,824 bits = 1 gigabit = 125 megabytes
Problem Number 2: The ciphertexts get larger and larger as we do more and more operations
- The sum of two ciphertexts is 1 gigabit + 1 bit
- The product of two ciphertexts is 2 gigabits
- Additional calculations have to be done to bring the ciphertext size back down to 1 gigabit
Conclusion
- This encryption scheme is fully homomorphic
- I.e., it supports an arbitrary number of additions and multiplications on encrypted data
- However, it is not practical
- But many real-world applications don't need to do arbitrary numbers of additions and multiplications
Solution: "Somewhat" homomorphic encryption
- Supports an arbitrary number of additions and a limited number of multiplications on encrypted data
K. Lauter, M. Naehrig, and V. Vaikuntanathan. Can homomorphic encryption be practical? Cryptology ePrint Archive, Report 2011/405, September 1, 2011. http://eprint.iacr.org/2011/405
- Describes an implementation of . . .
Z. Brakerski and V. Vaikuntanathan. Fully homomorphic encryption from ring-LWE and security for key dependent messages. Advances in Cryptology -- CRYPTO 2011, pages 505-524, 2011.
- Describes a somewhat homomorphic encryption scheme
- And a fully homomorphic encryption scheme based on that
An integer is represented as an element of the polynomial ring Z_p[x]/(xⁿ+1)
- p is a prime number
- n is a power of 2
- A ring element is a polynomial in x: a_n−1xⁿ⁻¹ + a_n−2xⁿ⁻² + . . . + a₂x² + a₁x + a₀
- Each coefficient a_i is a member of Z_p; that is, 0 ≤ a_i ≤ p−1
- Ring elements are added and multiplied using polynomial arithmetic (mod p); result is the remainder when divided by xⁿ + 1
An encrypted integer (ciphertext) uses two ring elements
The formulas for encryption, homomorphic addition, homomorphic multiplication, and decryption are rather intricate (see papers)
Sizes that support unlimited homomorphic additions and no homomorphic multiplications
- Example: encrypted sum, mean
- n = 512 -- can encode 512-bit integers
- p = 19-bit prime
- Ring element size = 512×19 bits = 9,728 bits
- Ciphertext size = 2 ring elements = 19,456 bits
- Additional data needed for homomorphic operations = 21 ring elements = 204,288 bits
Sizes that support unlimited homomorphic additions and one homomorphic multiplication
- Example: encrypted variance, standard deviation
- n = 1,024 -- can encode 1,024-bit integers
- p = 38-bit prime
- Ring element size = 1,024×38 bits = 38,912 bits
- Ciphertext size = 2 ring elements = 77,824 bits
- Additional data needed for homomorphic operations = 40 ring elements = 1,556,480 bits
Conclusion
- 9.5 kilobytes (76 kilobits) for an encrypted 1024-bit integer
- This is a lot better than a gigabit
- Running time measurements on an unoptimized implementation in the Lauter et al. paper show this scheme is practical

Scenario 3: Untrusted Computation, Private Input and Output Data

Scenario 3
- Client does not trust server to do the computation correctly
- Client does not allow server to see intermediate and final results
- Client does not allow server to see input data
Now, in addition to all the above, the server must produce a proof of correctness
- To convince the client that the computation was carried out correctly
- Even though the server sees only the encrypted input and output data
An active research topic -- we won't go there

Deduplication

Bob and Carol and Ted and Alice all want to store the same file on a cloud storage server
Problem: If the server stores four copies of the same file, it's a waste of disk space
- (That could be used to store other files and generate more revenue)
Solution: Deduplication
- The server stores just one copy of the file contents
- In metadata associated with the file, the server somehow notes that Bob, Carol, Ted, and Alice have each stored the file
Detection of duplicates
- Solution 1: Compare entire file contents; takes too long
- Solution 2: Compare file tags; tag = Hash(file contents)
Problem: Bob and Carol and Ted and Alice don't want the server to know the file contents
Solution: Encryption
- Bob chooses a secret key, encrypts the file, uploads the ciphertext
- To retrieve the file, Bob downloads the ciphertext, decrypts it with the secret key
- Carol and Ted and Alice do the same
- Presumably, everyone chooses a different key
Problem: Deduplication is no longer possible
- The same file contents encrypted with different keys yield different ciphertexts (and tags)
- The server can no longer tell that everyone has the same file
Solution: Message-locked encryption
- Don't let each user choose a different key
- Instead, let key = Hash(file contents)
- Then ciphertext = Encrypt(key=Hash(file contents),plaintext=file contents)
- And tag = Hash(ciphertext)
There are subtle issues in designing a secure message-locked encryption scheme
- M. Bellare, S. Keelveedhi, and T. Ristenpart. Message-locked encryption and secure deduplication. Cryptology ePrint Archive, Report 2012/631, November 26, 2012. http://eprint.iacr.org/2012/631

Proof of Ownership

Problem: Users can convince the server they have files, when they don't
Legitimate user
- Bob wants to upload file contents X with tag T
- Bob to server: "Request to upload file with tag = T"
- Server sees there is no file stored with tag T
- Server to Bob: "Go ahead"
- Bob to server: "File contents = X"
- Server stores file and tag, and notes Bob owns the file
- Later, Bob wants to download the file
- Bob to server: "Request to download file with tag = T"
- Server sees there is a file stored with tag T
- Server to Bob: "File contents = X"
Malicious user
- Alice does not own the file and never uploads the file
- However, Alice knows the tag
- Alice to server: "Request to upload file with tag = T"
- Server sees there already is a file stored with tag T
- Server to Alice: "Don't bother"
- Server notes Alice owns the file
- Alice to server: "Request to download file with tag = T"
- Server sees there is a file stored with tag T
- Server to Alice: "File contents = X"
- This violates the file storage service model
- This lets users abuse the file storage service as a content distribution network
Solution: Proof of ownership
- Alice must do more than just provide the tag of the file to upload . . .
- Alice must prove that she has the entire file contents . . .
- But without requiring Alice to upload the entire file contents, which defeats the purpose of deduplication
Proof of ownership scheme based on Merkle hash trees
- S. Halevi, D. Harnik, B. Pinkas, and A. Shulman-Peleg. Proofs of ownership in remote storage systems. Cryptology ePrint Archive, Report 2011/207, August 11, 2011. http://eprint.iacr.org/2011/207
Related security concept: Proof of data possession
- Server proves to user that server has the correct file content . . .
- Without downloading the whole file content
- Q. Zheng and A. Xu. Secure and efficient proof of storage with deduplication. Cryptology ePrint Archive, Report 2011/529, September 29, 2011. http://eprint.iacr.org/2011/529

Distributed Systems 4005-730-01 Spring Quarter 2013

Course Page

Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706

Home Page

Copyright © 2013 Alan Kaminsky. All rights reserved. Last updated 11-May-2013. Please send comments to ark@cs.rit.edu.

4005-730 Distributed Systems Lecture Notes -- Module 10. Cloud/Grid Computing