x3dh

Documentation

Overview

Package x3dh implements the Extended Triple Diffie-Hellman (X3DH) key agreement protocol as profiled by OMEMO, XEP-0384 version 0.9[4].

The original X3DH algorithm by Marlinspike and Perrin[0] provides a certain amount of leeway. OMEMO fixes those parameters as follows. The used curve is the Curve25519 resp. X25519 as the ECDH function, SHA-256 is the hash function and "OMEMO X3DH" is the HKDF info string.

OMEMO demands that every key agreement uses a one-time prekey (OPK) next to the signed prekey (SPK); key exchanges without an OPK MUST be rejected. Thus, four Diffie-Hellman calculations are performed.

Instead of XEdDSA[1], this package follows OMEMO's second option and uses Ed25519 identity keys (IK). Those keys are always transferred in their Ed25519 form and are mapped to their X25519 equivalent for each DH calculation, as described in RFC 7748[2] or this nice blog post by Filippo Valsorda[3].

[0] https://signal.org/docs/specifications/x3dh/
[1] https://signal.org/docs/specifications/xeddsa/
[2] https://tools.ietf.org/html/rfc7748#section-4.1
[3] https://blog.filippo.io/using-ed25519-keys-for-encryption/
[4] https://xmpp.org/extensions/xep-0384.html

The normal procedure is:

1. Bob creates a signed prekey (SPK) and one-time prekeys (OPK) and publishes them; CreateNewSpk and CreateNewOpk.
2. Alice fetches Bob's SPK including the signature as well as one OPK and crafts an initial message; CreateInitialMessage.
3. Bob receives this message and calculates the same session parameters.

This file implements the X3DH-style key agreement used by legacy OMEMO (eu.siacs.conversations.axolotl, pre-XEP-0384 standardization). Unlike x3dh.go's OMEMO 2 profile, identity keys are native Curve25519 - there is no Ed25519 wire form and no birational conversion for the identity key; the signed prekey is instead signed via XEdDSA (xeddsa.go) directly over the Curve25519 identity key. The DH-chain shape (IK-SPK, EK-IK, EK-SPK, EK-OPK) and one-time-prekey requirement are unchanged from the OMEMO 2 profile.

This file implements XEdDSA to sign with and verify against Curve25519 keys directly - no Ed25519 conversion of the identity key is involved, unlike x3dh.go's OMEMO 2 path. Legacy OMEMO (eu.siacs.conversations. axolotl) signs its bundle's signed prekey with the Curve25519 IdentityKey via this scheme.

This does NOT implement the algorithm as described on https://signal.org/docs/specifications/xeddsa/ (which negates the private scalar so the derived Edwards point's sign bit is always 0, and carries no extra sign information in the signature). That description is a later formalization that doesn't match what real legacy OMEMO clients actually verify against - deployed clients descend from libsignal's original "curve25519sign" scheme, which never negates the scalar and instead steals the otherwise-always-zero top bit of the signature's s value to carry the public point's natural sign bit. The two schemes only agree for the ~50% of identity keys whose natural sign bit happens to be 0; for the rest they produce signatures no real client accepts.

Verified against github.com/janimo/textsecure/curve25519sign, a real working Go port of that original scheme (in turn implementing the construction from https://moderncrypto.org/mail-archive/curves/2014/000205.html), rather than reconstructed from the newer spec text.

Index

• func CreateInitialMessage(idKey ed25519.PrivateKey, peerIdKey ed25519.PublicKey, ...) (sessKey, associatedData, ekPub []byte, err error)
• func CreateInitialMessageLegacy(idPriv, peerIdPub, spkPub, spkSig, opkPub []byte) (sessKey, associatedData, ekPub []byte, err error)
• func CreateNewOpk() (opkPub, opkPriv []byte, err error)
• func CreateNewSpk(idKey ed25519.PrivateKey) (spkPub, spkPriv, spkSig []byte, err error)
• func CreateNewSpkLegacy(idPriv []byte) (spkPub, spkPriv, spkSig []byte, err error)
• func ReceiveInitialMessage(idKey ed25519.PrivateKey, peerIdKey ed25519.PublicKey, ...) (sessKey, associatedData []byte, err error)
• func ReceiveInitialMessageLegacy(idPriv, peerIdPub, spkPriv, opkPriv, ekPub []byte) (sessKey, associatedData []byte, err error)
• func XEdDSASign(priv, message []byte) (signature []byte, err error)
• func XEdDSAVerify(pub, message, signature []byte) bool

Functions

func CreateInitialMessage

func CreateInitialMessage(
	idKey ed25519.PrivateKey, peerIdKey ed25519.PublicKey, spkPub, spkSig, opkPub []byte,
) (sessKey, associatedData, ekPub []byte, err error)

CreateInitialMessage based on the peer's published signed prekey and one of its one-time prekeys.

This function must be called by the active opening party, X3DH's Alice. Internally an ephemeral key (X25519) will be generated and used with the X25519 equivalent of the two identity keys as well as the peer's prekeys to establish an ECDH secret. The associated data are the concatenation of the two Ed25519 public identity keys, starting with the initiating party's one.

func CreateInitialMessageLegacy

func CreateInitialMessageLegacy(
	idPriv, peerIdPub, spkPub, spkSig, opkPub []byte,
) (sessKey, associatedData, ekPub []byte, err error)

CreateInitialMessageLegacy is CreateInitialMessage's legacy-OMEMO counterpart: idPriv/peerIdPub are native Curve25519 identity keys (no Ed25519 form), and spkSig is verified via XEdDSA rather than plain Ed25519.

func CreateNewOpk

func CreateNewOpk() (opkPub, opkPriv []byte, err error)

CreateNewOpk creates a new X25519 one-time prekey (OPK), both the public and private part.

OMEMO demands that a key agreement always uses a one-time prekey. A published bundle SHOULD contain around 100 and MUST contain at least 25 of them. A public OPK MUST NOT be used for more than one key agreement; its private part MUST be deleted afterwards.

func CreateNewSpk

func CreateNewSpk(idKey ed25519.PrivateKey) (spkPub, spkPriv, spkSig []byte, err error)

CreateNewSpk creates a new X25519 signed prekey (SPK), both the public and private part. The public part is signed by the identity key.

The resulting triple (public IK, public SPK, signed public SPK) should be either sent to a peer or published on some keyserver. Based on this data, another peer can initiate a session by the CreateInitialMessage function.

OMEMO suggests to rotate the SPK once a week to once a month and to keep the old private part for another rotation period.

func CreateNewSpkLegacy

func CreateNewSpkLegacy(idPriv []byte) (spkPub, spkPriv, spkSig []byte, err error)

CreateNewSpkLegacy creates a new X25519 signed prekey (SPK), signing its public part with idPriv's Curve25519 identity key via XEdDSA.

func ReceiveInitialMessage

func ReceiveInitialMessage(
	idKey ed25519.PrivateKey, peerIdKey ed25519.PublicKey, spkPriv, opkPriv, ekPub []byte,
) (sessKey, associatedData []byte, err error)

ReceiveInitialMessage handles the initial message from the active party.

Therefore the same calculation is performed as for CreateInitialMessage, just in reverse.

func ReceiveInitialMessageLegacy

func ReceiveInitialMessageLegacy(
	idPriv, peerIdPub, spkPriv, opkPriv, ekPub []byte,
) (sessKey, associatedData []byte, err error)

ReceiveInitialMessageLegacy is ReceiveInitialMessage's legacy-OMEMO counterpart.

func XEdDSASign

func XEdDSASign(priv, message []byte) (signature []byte, err error)

XEdDSASign signs message with the Curve25519 private key priv (a clamped 32-byte X25519 scalar), following the original libsignal curve25519sign construction: priv is used as-is, never negated: the derived public point's natural sign bit is instead stashed into the otherwise-always-zero top bit of the returned signature's s value.

func XEdDSAVerify

func XEdDSAVerify(pub, message, signature []byte) bool

XEdDSAVerify verifies signature against message and the Curve25519 public key pub (the Montgomery u-coordinate), reversing XEdDSASign's construction.