Trait mc_oblivious_traits::ObliviousHashMap

pub trait ObliviousHashMap<KeySize: ArrayLength<u8>, ValueSize: ArrayLength<u8>> {
    fn len(&self) -> u64;
    fn capacity(&self) -> u64;
    fn read(
        &mut self, 
        key: &A8Bytes<KeySize>, 
        output: &mut A8Bytes<ValueSize>
    ) -> u32;
    fn access<F: FnOnce(u32, &mut A8Bytes<ValueSize>)>(
        &mut self, 
        key: &A8Bytes<KeySize>, 
        callback: F
    );
    fn remove(&mut self, key: &A8Bytes<KeySize>) -> u32;
    fn vartime_write_extended(
        &mut self, 
        key: &A8Bytes<KeySize>, 
        value: &A8Bytes<ValueSize>, 
        allow_overwrite: Choice, 
        allow_sideeffects_and_eviction: Choice
    ) -> u32;

    fn is_empty(&self) -> bool { ... }
    fn vartime_write(
        &mut self, 
        key: &A8Bytes<KeySize>, 
        value: &A8Bytes<ValueSize>, 
        allow_overwrite: Choice
    ) -> u32 { ... }
    fn access_and_insert<F: FnOnce(u32, &mut A8Bytes<ValueSize>), R: RngCore + CryptoRng>(
        &mut self, 
        key: &A8Bytes<KeySize>, 
        default_value: &A8Bytes<ValueSize>, 
        rng: &mut R, 
        callback: F
    ) -> u32 { ... }
}

Trait for an oblivious hash map, where READING and ACCESSING EXISTING ENTRIES have a strong oblivious property.

This is different from an ORAM in that it is like a hashmap rather than an array, and the keys can be byte chunks of any length, and need not be consecutive.

Oblivious here means: Timings, code and data access patterns are independent of the value of inputs when calling a function with the oblivious property. Generally this means the query (and the value).

• Read, access, and remove are strongly oblivious and have constant execution time. With the exception that, the all zeroes key may be invalid and they may early return if you use it.
• Write is not strongly oblivious and may take a different amount of time for different inputs. It may also fail, returning OMAP_OVERFLOW if an item could not be added.
• Write is the only way to add new values to the map.

In many use-cases, the writes are taking place at keys that are known to the SGX adversary (node operator). It would be okay to use e.g. a cuckoo-hashing type strategy, where different keys may take different amounts of time to insert, as long as the reads are strongly oblivious, because those are what what correspond to user queries. As long as the read timing and access patterns are independent of the write timings and access patterns, it meets the requirement. This is similar to the situation with “Read-Only ORAM” in the literature.

The access_and_insert function supports additional use cases where new inserts at secret locations, which might be new or old values, must be performed obliviously.

The API is designed to make it as easy as possible to write constant-time code that uses the map. This means, not using Option or Result, using status_code that implements CMov trait, conditionally writing to output parameters which can be on the stack, which can avoid copies, and avoiding a “checkout / checkin” API which while more powerful, is more complicated than a callback-based API.

We are not trying to mimic the rust hashmap API or the entry API because those are based on enums, option, etc. and can’t be used when constant-time, branchless code is a requirement. For planned use-cases, read, write and access are sufficient.

TODO: Should there be an explicit resize API? How should that work?

Required methods

fn len(&self) -> u64

Get the number of items in the map.

fn capacity(&self) -> u64

Get the capacity of the map. TODO: What should this be for the hashmap? At the moment this is number of buckets * bucket size. But this is not an achievable value of len in practice.

fn read(
    &mut self,
    key: &A8Bytes<KeySize>,
    output: &mut A8Bytes<ValueSize>
) -> u32

Read from the map at some position, without logically modifying it.

Note: This is strongly oblivious, regardless of whether the value was found, with the exception that we may early return if the all zeroes key is encountered.

Arguments:

• key: The data to query from the map
• output: A mutable location to write the found value.

Returns a status code:

• OMAP_FOUND: The value was found in the map, and output was overwritten.
• OMAP_NOT_FOUND: The value was not found in the map, and the output buffer was not modified.
• OMAP_INVALID_KEY: The key was rejected. The map is permitted to reject an all-zeroes key.

fn access<F: FnOnce(u32, &mut A8Bytes<ValueSize>)>(
    &mut self,
    key: &A8Bytes<KeySize>,
    callback: F
)

Access from the map at some position, and forward the value to a callback, which may modify it.

Note: This is strongly oblivious regardless of whether the value was found, with the exception that we may early return if the all zeroes key is encountered. The callback must also be oblivious for this property to hold.

Arguments:

• key: The data to query from the map
• callback: A function to call after the entry has been retrieved on the stack.

Callback: The callback is passed a status code and a mutable value. The status code indicates if this value already existed in the map (OMAP_FOUND) or if there was no match (OMAP_NOT_FOUND), or if the query was illegal (OMAP_INVALID_KEY).

This call cannot change the number of items in the map. If there was no match then it doesn’t matter what the callback does, nothing will be added. If there is a match then after the callback runs, the contents of the mutable buffer will be the value associated to this key.

fn remove(&mut self, key: &A8Bytes<KeySize>) -> u32

Remove an entry from the map, by its key.

Arguments:

• key: The key value to remove from the map

Returns a status code:

• OMAP_FOUND: Found an existing value which was removed.
• OMAP_NOT_FOUND: Did not find an existing value and nothing was removed.
• OMAP_INVALID_KEY: The key was rejected. The map is permitted to reject an all-zeroes key.

fn vartime_write_extended(
    &mut self,
    key: &A8Bytes<KeySize>,
    value: &A8Bytes<ValueSize>,
    allow_overwrite: Choice,
    allow_sideeffects_and_eviction: Choice
) -> u32

Write to the map at a position, OR, perform the same access patterns of this without actually writing to the map.

This has the same semantics as vartime_write, except, it takes an extra flag allow_sideeffects_and_eviction which, if false, prevents all side-effects to the map, and prevents the eviction procedure from happening, while still performing the same memory access patterns as a “simple” write to an existing entry of the map.

Arguments:

• key: The key to store data at
• value: The data to store
• allow_overwrite: Whether to allow overwriting an existing entry. If false, then when OMAP_FOUND occurs, the map will not be modified
• allow_sideffects_and_eviction: If false, then no side-effects are performed for the map, and access patterns are the same as if we performed a write at a key that is already in the map. The return code is the same as if we had performed a read operation at this key.

Returns a status code indicating if the key/value pair was

• not found (OMAP_NOT_FOUND), and so was added successfully (if condition was true)
• found (OMAP_FOUND), and so was overwritten (if condition and allow_overwrite were true)
• a table overflow occurred (OMAP_OVERFLOW) and so the operation failed,
• the key was rejected (OMAP_INVALID_KEY) and so the operation failed. the map implementation is allowed to reject the all zeroes key.

Loading content...

Provided methods

fn is_empty(&self) -> bool

Is the map empty

fn vartime_write(
    &mut self,
    key: &A8Bytes<KeySize>,
    value: &A8Bytes<ValueSize>,
    allow_overwrite: Choice
) -> u32

Write to the map at a position.

Note: This call IS NOT strongly constant-time, it may take different amounts of time depending on if the item is or isn’t in the map already, and how full the map is.

This allows to implement the map using e.g. a cuckoo hashing strategy.

Arguments:

• key: The key to store data at
• value: The data to store
• allow_overwrite: Whether to allow overwriting an existing entry. If false, then when OMAP_FOUND occurs, the map will not be modified

Returns a status code indicating if the key/value pair was

• not found (OMAP_NOT_FOUND), and so was added successfully,
• found (OMAP_FOUND), and so was overwritten,
• a table overflow occurred (OMAP_OVERFLOW) and so the operation failed,
• the key was rejected (OMAP_INVALID_KEY) and so the operation failed. the map implementation is allowed to reject the all zeroes key.

Security propreties:

• This call is completely oblivious with respect to value and allow_overwrite flag
• The call is not completely oblivious with respect to the key
• When the keys are both in the map, the call is constant-time.
• When both keys are not in the map, the call takes a variable amount of time, but the distribution of access patterns is indistinguishable for both keys. This requires the assumption that the hash function used to construct the table models a PRF.

This operation does not return the old value.

fn access_and_insert<F: FnOnce(u32, &mut A8Bytes<ValueSize>), R: RngCore + CryptoRng>(
    &mut self,
    key: &A8Bytes<KeySize>,
    default_value: &A8Bytes<ValueSize>,
    rng: &mut R,
    callback: F
) -> u32

Access the map at a position, inserting the item if it doesn’t exist, AND obliviously inserting a new item with a default value and random key if the targetted item DOES exist.

This complex call allows to both modify the map, and insert new items into the map, on the fly, obliviously.

This call is rather niche and you should only use it if you need it because it will be slower than a call to access or read, or vartime_write. It is implemented here as a trait function in terms of read and vartime_write_extended, but a specific implementation may be able to do it faster.

This call ALWAYS inserts a new item into the map, and so if used repeatedly, WILL eventually cause the map to overflow.

This call cannot remove an item from the map after accessing it.

The oblivious property here requires that the chance that a random key already exists in the map in negligibly small. This assumption is justified if the key size is e.g. 32 bytes. If the key size is only 8 bytes, then you will have less than a 64-bit security level for the oblivious property, as the map gets more and more full. It is questionable to use it for maps with a key size of less than 16 bytes.

Arguments:

• key: The key to store data at
• default_value: The default value to insert into the map.
• rng: An rng for the operation
• callback: A function to call after the value has been retrieved on the stack.

Callback: The callback is passed a status code indicating if the key/value pair was

• not found (OMAP_NOT_FOUND), and so was added successfully,
• found (OMAP_FOUND), and so was overwritten, And, it is passed the mutable buffer on the stack. This buffer either contains the value associated with this key in the map, or contains default_value. This buffer will be stored to the map after the callback returns, unless the key was invalid or overflow occurred.

Returns: A status code for the operation as whole:

• not found (OMAP_NOT_FOUND), the key was not found in the map, and so was added successfully
• found (OMAP_FOUND), the key was found in the map, and was overwritten successfully
• a table overflow occurred (OMAP_OVERFLOW), either when inserting the new item OR the random item. In this case the table is left in a consistent state but the write specified by the callback may or may not have been rolled back, and the random write may or may not have been rolled back.
• the key passed was invalid (OMAP_INVALID_KEY)

Security propreties:

• This call fails fast, returning early if OMAP_INVALID_KEY or OMAP_OVERFLOW occurs.
• OMAP_OVERFLOW is equally likely to occur no matter whether the key was already in the map or not. (This requires the assumption that the hash function used is a PRF, like SipHash.)
• This call is completely oblivious with respect to default_value parameter.
• This call is completely data-oblivious when considering two keys that are both in the map, or are both not in the map.
• This call is data-oblivious when considering two keys, one of which is in the map and one of which is not, with an error parameter of self.len() / 2^{KeySize} That is, the adversary can get at most this much advantage in distinguishing the two scenarios based on access patterns. This analysis requires the assumption that the hash function used in the map is a PRF. (https://en.wikipedia.org/wiki/SipHash).

Loading content...

Implementors

Loading content...