reach/common/ecdh-omr

ECDH-OMR: ECDH based Oblivious Message Retrieval

ECDH-OMR aims to solve the following problem:

1. Alice wants to leave a message for Bob on a server.
2. The server is not supposed to know that the message is for Bob.
3. Eve should neither be able to count the amount of real messages available for pick-up on the server, nor if new messages came in or old ones were removed.
4. Bob should be able to pick their message up from the server without the server knowing whether this has happened or not.

ECDH-OMR solves this by using the commutative property of Diffie-Hellman key exchanges to implement a form of public key blinding, allowing third parties to send messages to a recipient this third party cannot identify at rest or when relaying it. It enables a form of Private Information Retrieval.

This library implements this scheme with x25519-dalek and (generically) with RustCrypto's elliptic-curves, as well as their AEADs (again, generically).

Warning

This work has not yet been independently audited!

While the scheme at its core received preliminary reviews with positive results, more rigorous proofs should be published before considering its use. The implementation is a first stab at what a reasonable generic API for this could look like and has not received any reviews so far.

For experimental use and research only.

Basics

Although its use is not widespread, ECDH supports shared secrets among multiple parties. Effectively, the whole reason why this scheme works is because these two statements are equivalent:

• ECDH ( ServerSK, ECDH ( AliceSK, BobPK ) )
• ECDH ( BobSK, ECDH ( ServerSK, AlicePK ) )

This allows a server (or another third party) to encrypt information for a recipient the real public key they don't know of, and a recipient to decrypt information without having identified themselves to the server (or another third party).

Scheme flow

For the purposes of the breakdown below, Alice sends an unencrypted message to Bob. How Alice would encrypt a message to Bob would have to be handled by a different layer of a protocol using this scheme.

1. Alice obtained Bob's public key. Alice blinds Bob's public key. This is done by generating an ephemeral secret key, and using it to create a shared secret with Bob's public key. This shared secret is Bob's blinded public key (BK). The ephemeral secret's public counterpart acts as a kind of blinding factor (BF). Both are sent to the server along with a message.
   Alice → Server:
   • BlindedBobBK = ECDH ( EphemeralSK, BobPK )
   • BlindedBobBF = G^EphemeralSK
   • Message
2. To field a request, the server generates its own ephemeral (per-request) key pair, and combines it with Bob's blinded public key and its blinding factor. A nonce is generated and used alongside the resulting shared secret to symmetrically encrypt the message. This library calls the resulting package Hint.
   Server → Anyone:
   • BlindedBlindingFactorBK = ECDH ( RequestSK, BlindedBobBF )
   • Nonce
   • Ciphertext = AEAD Enc ( ECDH ( RequestSK, BlindedBobBK ), Nonce, Message )
3. Bob now received an encrypted message from the server, even though the server was not aware of Bob's real public key. Bob also received all information they need to recover the message left by Alice.
   Bob → Bob:
   • Message = AEAD Dec ( ECDH ( BobSK, BlindedBlindingFactorBK ), Nonce, MessageCiphertext )

API Flow

For an annotated version of this that involves the use of "decoy hints", please see examples/decoyed.rs.

use ecdh_omr::{curves::X25519, Blind, Hinting, TakeTheHint};

use rand_core::{OsRng, RngCore};
use x25519_dalek::*;

type Hint = ecdh_omr::Hint<X25519, ocb3::Ocb3<aes::Aes128>, 32>;

fn main() {
    // Bob
    let bob_secret = StaticSecret::random_from_rng(&mut OsRng);
    let bob_public = PublicKey::from(&bob_secret); // -> Alice

    // Alice
    let bob_blinded = bob_public.blind(&mut OsRng); // -> Server
    let alice_message = [42u8; 32]; // -> Server

    // Server
    let mut salt = [0u8; 32];
    OsRng.fill_bytes(&mut salt); // -> Bob
    let hint = Hint::new(&bob_blinded, &alice_message, &salt, &mut OsRng).unwrap(); // -> Bob

    // Bob
    let bob_recovered_message = bob_secret.take_the(&hint, &salt).unwrap(); // ✅

    assert_eq!(alice_message, bob_recovered_message);
}

Notes

Terminology

ECDH-OMR's namesake is the 2022 paper Oblivious Message Retrieval (eprint) by Zeyu Liu and Eran Tromer, which describes a protocol using Fully Homomorphic Encryption to achieve similar properties where a server stays oblivious as to which messages a recipient decrypts.

A key difference in terminology between the two approaches though is that ECDH-OMR's uses the term hint where OMR would use clue. However, the author's use of hint precedes their awareness of OMR, and they decided to stick with it: Clues are usually more concrete pieces of evidence that directly point towards a solution or answer, whereas hints are commonly more veiled indications that can guide someone towards the intended meaning without giving away the game. Clues you can collect and combine, while hints you have to "get" by using pre-existing knowledge, or in a more adversarial setting you may also be asked to "take" them.

Scale

Fundamentally, because it is a polling based scheme, rather than Fuzzy Message Detection (eprint) for example where the server does matching work, its scale is limited by bandwidth in addition to compute.

Post-Quantum Considerations

• CSIDH/CTIDH technically supports this scheme, but aren't researched well enough to be viable at this point. Due to the scale limitations of ECDH-OMR though, it may be conceivable that CTIDH-OMR or ECDH-CTIDH-OMR could be usable in certain circumstances, provided the implementation is fast enough to handle a reasonable amount of hints. An experimental non-constant-time proof-of-concept is available.

• ML-KEM is not commutative, so this would require a way for a third party to change the ciphertext without changing the secret embedded within. We're not aware of whether this is possible or not.

Acknowledgements

ECDH based Oblivious Message Retrieval was developed by @eaon as part of Reach, an end-to-end encrypted communication platform designed for collaborative groups who wish to let anonymous individuals contact them with information and/or requests. Reach and the research that led to this crate has been self-funded so far, please get in touch if you would like to change that 😉

The author also contributed the scheme to SecureDrop's E2EE protocol research.

• The author would like to thank Davide @TheZero for his early contribution to the aforementioned research, whereby an unusual use of multi-party Diffie-Hellman key exchanges were used to ephemerally "prove" secret key possession in a challenge/response protocol.

• The author would also like to express their gratitude to Jacob Young for highlighting how the challenge/response protocol would allow servers to quickly correlate messages and infer identity properties of recipients, leading the author to take up this problem once again. And then also for taking even more time at Recurse Center to review the ECDH based Oblivious Message Retrieval scheme implemented in this crate. 🐙