Derive

Ephemeral keys, or keys with short lifespans, have transformed direct communication. They mean that even if a message is brute-force decrypted, the rest of the data remain secure. However, these algorithms only are feasible for direct communication between two peers and do not scale to multicast or broadcast communication. Multicast networks still rely heavily on static keys for messages, meaning that if a key is compromised, any future communication is compromised as well.

Multicast matters more now than it ever has before thanks to video conferencing, live broadcasts, WiFi, and more. However, it is conceivable to efficiently ratchet (modify) keys in these networking scenarios, enabling substantial mitigation of decryption. Omnivoz brings the value of ratcheting to multicast networks.

How Omnivoz Derive Works

Omnivoz relies on evaluating polynomials at a given point to establish a shared key. Polynomials have a unique set of characteristics that make them perfect for multi-peer communication:

1. Deterministic
2. Defined for all x
3. Uncapped number of coefficients

At a high level, all client machines contain identical polynomials. Clients establish encryption and decryption keys by evaluating the polynomial at a predetermined x. These polynomials can be “ratcheted” by submitting a changelog, which clients apply to their respective polynomials, producing a new curve that is identical across clients, without ever sending the complete information needed for decryption across a multicast network.

Components

There are two primary components of a Omnivoz network: nodes and Keymasters.

Network Nodes

A Network Node is a device that can either only receive or both receive and send traffic on a Omnivoz network. In addition to the typical responsibilities of a network device, it must also keep track of the active polynomial coefficients.

Keymaster

A Keymaster is a specialized network node that can also onboard new devices onto the chain. It also must maintain the chain’s state and regenerate the coefficients should the chain need to be reset.

Multicast Exchange Procedure

Before any connections begin, a Keymaster generates a random number of random coefficients. These coefficients are the root coefficients.

When a node joins the network, it:

1. Authenticates (outside of the scope of Omnivoz)
2. Establishes a secure direct connection with the Keymaster
3. Obtains the coefficient set, next x, and metadata from the Keymaster

Upon receiving a message, a client:

1. Evaluates their current polynomial at their current x
2. Converts the polynomial result to a key
3. Decrypts the encrypted packet with the key
4. Extracts the changelog and next x from the packet
5. Applies the changelog to the local polynomial coefficients
6. Updates the local next x from the packet

To send a message, a client:

1. Generates a random number of random changelog entries
2. Generates a random next x value
3. Wraps the data to send in an object that contains the next x and changelog
4. Establishes a key at the current x given the current polynomial
5. Encrypts the object using the established key
6. Applies the changelog and next x to itself, readying it for future messages

With these procedures, we have a method for data to be encrypted and sent to multiple devices. Clients can use that data to apply the same transformation of polynomial coefficients as all of the other clients and an x to establish a single shared key.

Changelog

When a coefficient is changed, the degree of the polynomial does not shift. In this case, we see a vertical translation.

The changelog is the center of the security benefit. It is an ordered array consisting of an object with:

• An action (Insert at index, append, remove, replace)
• An index
• A value

Any ratchet will include a changelog. Client systems will apply the changelog on their polynomials, creating a new formula for finding keys.

Handling Failures

It is inevitable with multicast systems that some packets will not be delivered. In Omnivoz, that means that specific clients will not hold the same polynomial as the others. In this scenario, clients will receive a packet that errors when decrypting. At this point, the client will know that they have missed an update and will request the latest polynomial set from the Keymaster.

If the Keymaster loses power or otherwise loses its existing state, it should not store the keys on the system. Instead, it should send a direct TCP message to all connected computers (ensuring delivery) that they need a new set of keys. All clients will then begin the handshake process again, just like if they missed a frame.

Benefits over Other Methods

Omnivoz has some essential benefits compared to other methods.

Static Keys

Omnivoz improves on static keys by offering key ratcheting. That means that if a packet is compromised, it does not threaten the rest of the chain. Despite brute-force being inefficient, this feature is vital for exchanges over wireless or public networks since malicious actors can brute-force easily without detection.

Omnivoz also offers a way to remove nodes from the chain, a critical need for multicast networks. As long as at least one ratchet happens where a removed node fails to receive the changelog, it will be unable to decrypt any future packets. A practical implementation of this would likely involve a Keymaster sending a ratchet over unicast TCP to all legitimate nodes. Static keys, by contrast, still risk a former node being able to decrypt a packet even after it has been removed from the group, reducing the confidentiality of data on a network.

Including a Key in the Packet

Another option is to include a new shared key in multicast packets. However, while there is ratcheting, it still leaves significant exposure to the network. A malicious actor could capture packets, and once one packet is compromised, the actor could traverse later communications and easily reconstruct the chain. This system is better than static keys since if the actor fails to capture encrypted data, they need to restart the process.

Peer-to-Peer Diffie-Hellman Exchanges

Peer-to-Peer Diffie-Hellman Exchanges are very secure but quickly become extremely expensive. Under this system, a sending node has to perform a handshake with every other node on a network, so every new client means a new expensive handshake is needed. Omnivoz, by contrast, does not grow as more devices enter a network, so encryption only has to happen once. 

Security Analysis

Since Omnivoz is a mechanism for key exchange, it exclusively focuses on data confidentiality. Even then, it must incorporate other techniques, like symmetric encryption, to function.

It relies extensively on using large numbers to remain secure. If an actor can brute-force the polynomial coefficients at a given time, then the chain is compromised. Increased variation leads to lower risk because:

• Order matters; each coefficient index must be correct to evaluate correctly.
• Unspecified length; Polynomials may have bounded size, but the size can be any integer within that. A brute force attack would require guessing the coefficients and guessing the degree of the polynomial.
• Extreme detail; coefficients must be exact to resolve correctly. The room for error is minuscule, which is highly unlikely to be broken given the required quantity.

I will cover more details of my specific implementation in the following section. However, given my reference program:

• The chance of quickly brute-force decrypting an AES 256-encrypted message is minimal.
• The time to brute-force guess a correct array without a pre-established size and with values that are random 64-bit numbers is far greater than the likely lifespan of a chain.
• The most significant risk is that an actor compromises a client or Keymaster, at which point network security problems are far greater than multicast encryption.
• Given the above statements, Omnivoz provides substantial security for common risks for multicast systems.

Implementation Considerations

When I implemented the system, I used the following setup:

• Coefficients are a float64 between -1.0 and 1.0
• X values are a float64 between -1.0 and 1.0
• Polynomials have between 1024 and 8192 coefficients
• Polynomials evaluate to a float64
• Encryption is 256-bit AES in GCM mode
• Ratchets contain between 128 and 512 changes

While developing the technology, I encountered a couple of constraints to keep in mind:

• Avoid x-values or coefficients of zero
• Ensure that the result of formula evaluation within a valid domain will never overflow or resolve to infinity
• Mitigate array index out of bound exceptions when evaluating changelogs
• Prepare for massive packets, or reduce the number of ratchets per packet
• Consider resetting chains after a certain period to reduce the impact further if a chain becomes compromised

My test configuration focused on what a more extreme scenario might be. I would recommend reducing the number of ratchets and possibly the number of coefficients depending on the importance of your communication and resources on client devices. Despite excessive configurations, the entire Omnivoz, including encryption and decryption, added less than a millisecond of processing per message on my laptop.

Establishing a Key from a Polynomial

You may notice that the 64-bit float from evaluating the polynomial is less than the 256 bits required for encryption. Fortunately, there is a simple way to get 256 bits from a polynomial.

Rather than repeating values, I use a round-robin algorithm to divide the coefficients among four different polynomials. Then, the application assesses each polynomial at the specified x value and append the bits to form a 256-bit key. This solution has been a highly efficient way to create a new key while reducing security risks in my testing.

Real-World Multicast Scenarios

The idea of polynomial-based multicast has three potential configurations that it can address:

• Real-time infrequent data (Enterprise WiFi)
• Real-time frequent data (Livestream / IPTV)
• Stored data (Chat app)

I will address the implementation of Omnivoz in each of these scenarios.

Enterprise WiFi

Enterprise WiFi was the inspiration for Omnivoz. Given that most office buildings are not faraday cages, radio signals can leak outside offices into public areas and provide malicious actors an opportunity to learn about internal networks. 

In this scenario, the Keymaster would likely be a dedicated box. The DHCP response from the network would let the computer know that:

a) Multicast on the network requires Omnivoz and

b) the IP address of the Keymaster.

Then, an endpoint would authenticate with the Keymaster and receive the polynomials. At this point, the endpoint would be ready to listen for messages.

The primary benefit of a system like this would be to reduce the amount of information leaking through wireless multicast. Malicious actors outside or inside a building would be unable to see MDNS, ARP, SSDP, and other packets that could give more information about network setups. Instead, they would only do so if an actor were authenticated correctly or brute-forced the solution.

Multicast Livestreams and Video Calls

Omnivoz also offers excellent potential for DRM on live streams and IPTV streams. UDP packets are expected to drop, and data changes quickly, so ratcheting every block isn’t feasible. It would add enough delay noticeable with most systems but would be very prominent in a live stream.

As such, there should be a separate TCP socket used to ratchet keys. The Keymaster would run on the same cloud infrastructure as the rest of the application. It would likely have a message sent out notifying all participants that the new curve will be used on a particular frame, giving them enough time to respond if a message drops. Given that frame dropping is expected with live streams, having minor encryption issues requiring renegotiation would not severely impede the user experience.

While static keys are often sufficient for DRM, users still risk leak decryption keys and media endpoints. Widevine and other competing products reduce the risks by being baked into the browser, but companies may want a complete DRM solution, especially for cross-platform experiences. In these scenarios, having keys ratchet means that sharing media endpoints and decryption keys becomes nearly impossible. Users will have no feasible alternatives besides watching through an official client where the service provider can implement other content protection measures. 

Omnivoz is also useful for end-to-end encryption on video or audio conferencing applications, which have typically struggled to offer robust end-to-end encryption. It would work in a nearly identical manner to DRM but with multiple broadcasters using a shared key.

Chat App

Chat apps are unique in that they often store data in the cloud. That does not mean that Omnivoz is irrelevant, however. Instead, users would store Omnivoz original keys and a database index encrypted in their user account. It is simple to read a message chain. First, the application looks up the first message and decrypts it with the given polynomials. After that point, like traversing a linked list, the client goes through each entry, reads the data, and modifies the polynomial before continuing.

Besides the inherent security benefits of Omnivoz, there is another excellent benefit for obfuscation. Developers can store messages as a flat list rather than grouped by chat. Therefore, it would be impossible to identify which database records are associated with which chat if the chain is not compromised. 

Future Directions

Omnivoz works in my local development environment, but that is very different from the real world. Some challenges will likely arise based on a real-world setting:

• What happens if two ratchets happen from the same source block (data locking)
• How can a client identify that it has dropped a key?
• What happens if a ratchet happens during the handshake?

I am looking into solutions for these problems and have early concepts, but nothing tested so far. 

Conclusion

We have defined a broad protocol to enable key ratcheting with multiple clients while preventing communication leaks if any individual multicast packet is lost. It provides crucial safety for enterprise networks, communication applications, live streaming providers, and many other aspects of modern technology. The solution is very efficient, even on low-powered devices, and usually does not even require any clients storing keys on disk. While not perfect, the complexity involved in breaking a chain means that multicast communication should be secure enough to be trusted, even in high-risk environments.