Facebook open-sources homomorphic hashing for secure update propagation

Last week the team at Facebook open-sourced homomorphic hashing for a secure update propagation. It is difficult to ensure consistency while propagating updates across a large network of peers. Even traditional methods aren’t useful as they can introduce compromises with respect to efficiency and scalability.

To address this problem, the research team of Facebook worked on this project and released a paper based on the same. The paper focuses on formalizing the problem of secure update propagation and propose a system that allows a centralized distributor to propagate signed updates across a network.

The researchers show that their system is secure against an attacker who can maliciously modify any update and its signature. The researchers have opted for a cryptographic primitive known as homomorphic hashing, introduced by Bellare, Goldreich, and Goldwasser.

The researchers have also studied about the instantiation of the lattice-based homomorphic hash, LtHash of Bellare and Miccancio. which is a specific homomorphic hashing algorithm.

The paper provides a detailed security analysis of the collision resistance of LtHash. It gives an idea about the implementation of LtHash using a selection of parameters that ensure security. This implementation has been deployed to secure update propagation in production at Facebook and is also included in the Folly open-source library.

The challenges of securing update propagation

A central distributor who is responsible for managing the master database and propagating updates to a set of subscribers in an efficient manner. To make this possible, the distributor has to be in charge of directly sending the updates to each subscribed client. As the number of subscribed clients and the rate of updates increases, this approach fails. This might saturate the network interface controller and further leaving it unable to finish distributing one update before the next one is ready to be pushed.

A better approach is to delegate the propagation through the clients. Some of the subscribers can participate in forwarding the distributor’s original updates to other subscribers. According to researchers, this approach would reduce the number of connections the distributor manages and the bandwidth will remain unaffected.

But the major issue is to ensure consistency. Each subscriber needs to trust a set of intermediate subscribers to have correctly propagated the original updates. The challenge is to maintain the integrity of the distributor’s updates across a network of subscribers that could alter those updates. And this is what is referred to as the secure update propagation problem.

Experimental approaches by the researchers

The possible solution could be that the distributor can use digital signatures to assert the authenticity and integrity of the messages it distributes. The distributor can generate a public and private key pair, publish the public key to every subscriber upon joining the network while keeping the private key secret. The signatures can then be constructed over the contents of the update or the contents of the updated database.

In the case of signing each update, handling update propagation securely is for the distributor to directly sign the contents of each update that sent to its subscribers. The signature can be used to verify the contents before applying it to the database.

While this approach prevents an attacker from modifying updates maliciously, it also adds complications to the handling of batch updates and offline database validation. So another approach suggested by researchers is to rely on a signature algorithm computed over the database contents after each update. But in this case, the distributor must iterate over the entire database to produce the signature.

Hashing approach - LtHash

An alternative approach is hashing where the distributor can use a hash function to hash the entire database into a small digest. The resulting digest can be directly signed, as opposed to having the distributor sign the database itself. The collision-resistant property of the hash function and the unforgeability of the signature algorithm ensures integrity through the sequence of updates.

However, an ideal solution would allow the distributor and its subscribers to update the database hash entirely irrespective of the size of the database. This is possible with the use of homomorphic hashing. The team used LtHash, a specific homomorphic hashing algorithm based on lattice cryptography, for creating an efficiently updatable checksum of a database.

The checksum, along with a signature from the distributor of the database, allows a subscriber to validate the integrity of database updates. LtHash was chosen in the favor of other homomorphic hashing algorithms for its performance and efficient implementation.

LtHash can take a set of arbitrarily long elements as input, and produce a 2KB hash value as output. Two LtHash outputs can be “added” together by breaking each output into 16-bit chunks and performing component-wise vector addition modulo 216.

To know more about the implementation of secure update propagation, check out the paper.

Facebook announces ‘Habitat’, a platform for embodied ArtificiaI Intelligence research

Facebook open sources Magma,a software platform for deploying mobile networks

The Verge spotlights the hidden cost of being a Facebook content moderator, a role Facebook outsources to 3rd parties to make the platform safe for users