Skip to content

Instantly share code, notes, and snippets.

@paragonie-scott

paragonie-scott/sidh-seal.md

Last active August 2, 2017 17:49
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save paragonie-scott/20091a6fdcc808e6be1fc5707bad7695 to your computer and use it in GitHub Desktop.
Save paragonie-scott/20091a6fdcc808e6be1fc5707bad7695 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
sidh-seal.md

As far as I know, none of the existing post-quantum cryptography candidates offer a viable replacement for libsodium's crypto_box_seal() functionality. That is: Anonymous public-key encryption.

An example for where this would be useful is encrypting credit card numbers in a database, but only being able to decrypt them with a key that is kept offline.

An attractive solution would be to use SIDH in place of ECDH, building a similar protocol (i.e. ECDH with one ephemeral keypair and one static keypair, then an authenticated cipher). However, as noted in this paper by Galbraith, et al., an active attack against SIDH with static keys is possible.

A possible workaround, following the examples set forth in OAEP, RFC 6979, etc. is to build a dedicated sealing API mode that looks like this.

SIDH Seal

Bob wants to send a message to Alice. He has Alice's public curve A.

  1. Bob calculates a random secret isogeny b and uses it to derive his public curve B.
  2. Bob uses a XOF (e.g. BLAKE2x) to calculate the public points for both him and Alice for the message.
    • XOF(publicCurve || message) -> points
  3. Bob proceeds with the normal SIDH calculation to determine a shared secret, which he then uses to encrypt the message with an AEAD construction. (e.g. XChaCha20-Poly1305)
  4. Bob sends his public key B, all 4 public points, and the authenticated ciphertext to Alice.

SIDH Unseal

Alice receives a message from Bob.

  1. Alice retrieves the public points from Bob's message.
  2. Using Bob's public curve and the public points, along with her secret isogeny a, Alice derives the shared secret.
  3. Alice decrypts the message, aborting if the (e.g. Poly1305) authentication tag fails.
  4. Alice recalculates the XOF for the decrypted plaintext and sender's public key, and attempts to derive the same public points.
    • If they match, return the plaintext.
    • If they do not match, wipe everything from memory and abort.

What's Happening Here?

The idea is to make the points deterministic from the message contents (and maybe the sender's public curve, if we want to follow the Ed25519 example), and then check it on the receiving end to prevent CCAs.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment