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 or old ones were removed.
5. 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 is a form of [Private Information
Retrieval][PIR].

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 it's 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.**

  [blind]: https://en.wikipedia.org/wiki/Blinding_(cryptography)
  [PIR]: https://en.wikipedia.org/wiki/Private_information_retrieval
  [x25519-dalek]: https://github.com/dalek-cryptography/curve25519-dalek/tree/main/x25519-dalek
  [elliptic-curves]: https://github.com/RustCrypto/elliptic-curves
  [AEADs]: https://github.com/RustCrypto/AEADs/


Basics
------

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

- ECDH ( Server<sub>_SK_</sub>, ECDH ( Alice<sub>_SK_</sub>, Bob<sub>_PK_</sub> ) )
- ECDH ( Bob<sub>_SK_</sub>, ECDH ( Server<sub>_SK_</sub>, Alice<sub>_PK_</sub> ) )

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 them
to the server (or another third party).

  [multi party secrets]: https://crypto.stackexchange.com/questions/1025/can-one-generalize-the-diffie-hellman-key-exchange-to-three-or-more-parties


### 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
   blinding factor (_BF_). Both of them are sent to the server along with a message.**<br>
   Alice → Server:
      - BlindedBob<sub>_BK_</sub> = ECDH ( Ephemeral<sub>_SK_</sub>, Bob<sub>_PK_</sub> )
      - BlindedBob<sub>_BF_</sub> = G^Ephemeral<sub>_SK_</sub>
      - 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:**<br>
   Server → Anyone:
      - BlindedBlindingFactor<sub>_BK_</sub> = ECDH ( Request<sub>_SK_</sub>, BlindedBob<sub>_BF_</sub> )
      - Nonce
      - MessageCiphertext = AEAD Enc ( ECDH ( Request<sub>_SK_</sub>, BlindedBob<sub>_BK_</sub>, Nonce, Message)
3. **Bob now received an encrypted message from the server, even though the server was not ware of
   Bob's real public key. Bob also received all information they need to recover the message left by
   Alice.:**<br>
   Bob → Bob:
      - Message = AEAD Dec ( ECDH ( Bob<sub>_SK_</sub>, BlindedBlindingFactor<sub>_BK_</sub> ),
        Nonce, MessageCiphertext )


### API Flow

For an annotated version of this that also includes "decoys" or, please see [`examples/decoyed.rs`]
which also shows the use of decoy hints.

```rust
use ecdh_omr::*;

use x25519_dalek::*;
use rand_core::OsRng;

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_by_alice = bob_public.blind(&mut OsRng); // -> Server
    let alice_message = [42u8; 32]; // -> Server

    // Server
    let hint = Hint::new(&bob_blinded_by_alice, &alice_message, &mut OsRng).unwrap(); // -> Bob

    // Bob 
    let bob_recovered_message = bob_secret.try_to_take_the(&hint).unwrap(); // ✅

    assert_eq!(alice_message, bob_recovered_message);
}
```

  [`examples/decoyed.rs`]: examples/decoyed.rs


Notes
-----

### API Documentation

… Yes. That is necessary. That will exist. Soon. Promise ✨


### Scale

Fundamentally, because it is a polling based scheme, rather than [Fuzzy Message Detection] for
example where the server does matching work, its scale is limited by bandwidth and compute.

  [Fuzzy Message Detection]: https://eprint.iacr.org/2021/089


### Post-Quantum Considerations

CSIDH/CTIDH technically supports this scheme, but aren't researched well enough researched 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.

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][niij] 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. 🐙

  [@eaon]: https://codeberg.org/eaon
  [niij]: https://niij.org/
  [Reach]: https://codeberg.org/reach/reach/
  [@TheZero]: https://thezero.org/
  [Jacob Young]: https://jry.io/