Secure hash operations in a trusted execution environment
A method of secure hash table implementation includes performing a secret key exchange between a server enclave of a server device and a client enclave of a client device and establishing an encrypted channel between the server enclave and the client enclave using the exchanged secret keys. The method includes generating a random key for a keyed hash function or a pseudo random function (PRF) and communicating the random key to the client enclave. The method includes receiving hashes of input data at the server enclave. The method includes building a hash table based on key-value pairs included in the received hashes. The method includes receiving a hash table query that includes keys. The method includes retrieving values that correspond to the keys. The method includes returning the retrieved values that correspond to the keys or a null if a value has not been inserted into the hash table for one of the keys.
1. A method of secure hash table implementation, the method comprising:
performing a secret key exchange between a server enclave of a server device and a client enclave of a client device;
using the exchanged secret keys, establishing an encrypted channel between the server enclave and the client enclave;
generating a random key for a keyed hash function or a first pseudorandom function (PRF);
communicating the random key to the client enclave of the client device via the encrypted channel;
receiving from the client enclave, hashes of input data at the server enclave via the encrypted channel;
building a hash table based on a plurality of key-value pairs included in the received hashes, an order of the key-value pairs in the hash table based on a second pseudorandom function (PRF) seeded with the random key such that the order within the hash table is independent of the value of the key-value pairs;
receiving a hash table query from the client device, the hash table query including a plurality of keys;
responsive to the hash table query, retrieving values that correspond to the plurality of the keys; and
returning the retrieved values that correspond to the plurality of the keys or a null if a value has not been inserted into the hash table for one of the plurality of the keys included in the hash table query.
2. The method of claim 1 , wherein the generating the random key includes sampling the first pseudorandom function.
3. The method of claim 2 , wherein:
the plurality of key-value pairs are represented by a (key, value) pairs:
{(k 1 ,v 1 ), . . . , (k n ,v n )}, in which k 1 . . . k n represent keys, v 1 . . . v n represent values, and n is the maximum index variable for the keys and the values; and
the hashes of the input data are assigned according to expressions:
For iϵ[1,n]:
HT.Update(PRF sk (k π rk (i) ),v π rk (i) ), in which HT.Update represents an assignment function, sk represents the random key, PRF represents the second pseudorandom function, π represents a pseudorandom permutation from [1,n] to [1,n], and rk represents a pseudorandom permutation key.
4. The method of claim 3 , wherein:
the plurality of keys is represented by a key set:
(k 1 , . . . , k m ), in which k 1 . . . k m represent keys and m is the maximum index variable for the keys; and
the retrieving values is performed according to expressions:
For iϵ[1,m]:
v π rk (i)=HT.Find(PRF sk (k π rk (i) ), in which HT.Find represents a retrieve function for the hash table and π represents a pseudorandom permutation from [1,m] to [1,m].
5. The method of claim 2 , wherein the generating of the random key occurs only once.
6. The method of claim 1 , wherein:
the random key is generated for the keyed hash function; and
the keyed hash function is based on a secure hash algorithm (SHA) that includes SHA-1, SHA-2, or SHA-3.
7. The method of claim 1 , further comprising storing the hash table in an encrypted memory.
8. The method of claim 1 , wherein the server enclave and the client enclave are part of a trusted execution environment.
9. The method of claim 8 , wherein the trusted execution environment includes software guard extensions (SGX).
10. The method of claim 1 , wherein only a distribution of query collisions are vulnerable to being revealed to an unauthorized entity.
11. A non-transitory computer-readable medium having encoded therein programming code executable by one or more processors to perform or control performance of operations comprising:
performing a secret key exchange between a server enclave of a server device and a client enclave of a client device;
using the exchanged secret keys, establishing an encrypted channel between the server enclave and the client enclave;
generating a random key for a keyed hash function or a first pseudorandom function (PRF);
communicating the random key to the client enclave of the client device via the encrypted channel;
receiving from the client enclave, hashes of input data at the server enclave via the encrypted channel;
building a hash table based on a plurality of key-value pairs included in the received hashes, an order of the key-value pairs in the hash table based on a second pseudorandom function (PRF) seeded with the random key such that the order within the hash table is independent of the value of the key-value pairs;
receiving a hash table query from the client device, the hash table query including a plurality of keys;
responsive to the hash table query, retrieving values that correspond to the plurality of the keys; and
returning the retrieved values that correspond to the plurality of the keys or a null if a value has not been inserted into the hash table for one of the plurality of the keys included in the hash table query.
12. The non-transitory computer-readable medium of claim 11 , wherein the generating the random key includes sampling the first pseudorandom function.
13. The non-transitory computer-readable medium of claim 12 , wherein:
the plurality of key-value pairs are represented by a (key, value) pairs:
{(k 1 , v 1 ), . . . , (k n , v n )} in which k 1 . . . k n represent keys, v 1 . . . v n represent values, and n is the maximum index variable for the keys and the values; and
the hashes of the input data are assigned according to expressions:
For iϵ[1,n]:
HT.Update(PRF sk (k π rk (i) ),v π rk (i) ), in which HT.Update represents an assignment function, sk represents the random key, PRF represents the second pseudorandom function, π represents a pseudorandom permutation from [1,n] to [1,n], and rk represents a pseudorandom permutation key.
14. The non-transitory computer-readable medium of claim 13 , wherein:
the plurality of keys is represented by a key set:
(k 1 , . . . , k m ), in which k 1 . . . k m represent keys and m is the maximum index variable for the keys; and
the retrieving values is performed according to expressions:
For iϵ[1,m]:
v π rk =HT.Find(PRF sk (k π rk(i) )), in which HT.Find represents a retrieve function for the hash table and π represents a pseudorandom permutation from [1,m] to [1,m].
15. The non-transitory computer-readable medium of claim 12 , wherein the generating of the random key occurs only once.
16. The non-transitory computer-readable medium of claim 11 , wherein:
the random key is generated for the keyed hash function; and
the keyed hash function is based on a secure hash algorithm (SHA) that includes SHA-1, SHA-2, or SHA-3.
17. The non-transitory computer-readable medium of claim 11 , wherein the operations further comprise storing the hash table in an encrypted memory.
18. The non-transitory computer-readable medium of claim 11 , wherein the server enclave and the client enclave are part of a trusted execution environment.
19. The non-transitory computer-readable medium of claim 18 , wherein the trusted execution environment includes software guard extensions (SGX).
20. The non-transitory computer-readable medium of claim 11 , wherein only a distribution of query collisions are vulnerable to being revealed to an unauthorized entity.