elligator2

Encode X25519 public keys as uniform random bit strings, and back.

[dependencies]
elligator2 = "0.1"

use elligator2::{from_representative, generate};

let key = generate(&mut rand::rng()).expect("a working RNG");

// Send this. It is indistinguishable from 32 random bytes.
let on_the_wire: &[u8; 32] = key.representative();

// The peer recovers the public point, and uses *that* for Diffie-Hellman
// and for anything the protocol hashes.
assert_eq!(from_representative(on_the_wire), *key.point());

no_std, no allocation, no unsafe. Built on formally verified field arithmetic and differentially tested against an independent implementation.

Why

A raw X25519 public key is not a random string. It is the u-coordinate of a curve point, so u³ + A·u² + u is a square for every one of them — a property anyone can test with a single Legendre symbol. A protocol that puts a public key at a fixed offset in its first packet is therefore separable from random traffic on that basis alone, no matter how good the cipher after it is.

Elligator2 removes the tell. About half of all curve points have a preimage under the map; those encode to a 32-byte string that is uniformly distributed, and every 32-byte string maps back to some point, so an observer cannot filter on "decodes to nothing" either.

This is the mechanism behind obfs4/Lyrebird's handshake and behind the various "random-looking" transports built since. It is not, on its own, an unobservable protocol — see What this does not hide.

Why this crate

As of writing, the Rust ecosystem offers curve25519-elligator2 — a full fork of curve25519-dalek, maintained by the Tor Project and pinned to the 4.x lineage — and qdsa, which is signature-focused. Neither is a small, standalone, bytes-in-bytes-out implementation you can drop into a protocol that already has its own curve stack.

That is the gap this fills. It is ~250 lines of map on top of fiat-crypto, with no opinion about your handshake, your wire format, or which curve library you already use.

API

Function	Feature	Does
to_representative(point, tweak)	—	encode a Montgomery u-coordinate; None for the ~half with no preimage
from_representative(bytes)	—	decode any 32 bytes to a point; total, never fails
is_montgomery_u(bytes)	—	the distinguisher itself, so your tests can measure
generate(rng)	keygen (default)	a keypair that is representable and torsion-dirty
HiddenKey::diffie_hellman(peer)	x25519	convenience DH, if you want it

Without keygen the crate is fiat-crypto + subtle and nothing else. With --no-default-features it builds for thumbv7em-none-eabi, which is checked in CI rather than claimed.

The rule

The representative goes on the wire. The point goes into the protocol.

This crate converts between the two and nothing else. If you are retrofitting it onto an existing protocol, keep hashing and DH-ing the point — then your transcript is byte-identical to what it was before, and whatever interoperability tests you already have stay meaningful. That property is worth protecting; it is the difference between "we added obfuscation" and "we added obfuscation and can still prove the handshake is correct".

Three traps

All three produce code that works, round-trips, and is broken.

1. Rejection sampling. Only about half of all curve points have a preimage, so key generation is a loop. The only one of the three that fails loudly.

2. Dirty keys. The one that silently produces a "uniform" encoding that is trivially distinguishable. A clamped X25519 public key always lies in the prime-order subgroup. If you only ever encode such points, an adversary decodes an observed string with the public map and asks whether the result has prime order: true ~1/8 of the time for genuinely random strings, and always for yours. Your strings are individually uniform and collectively a fingerprint.

The fix is to publish a point from the whole group: E_pub = clamp(e)·B + T, with T uniform among the points of order dividing 8. The Diffie-Hellman is unaffected, and the reason is the whole trick: every clamped X25519 scalar is a multiple of 8, and 8·T = O, so the peer's scalar annihilates the torsion component. generate does this; to_representative cannot tell whether you did.

3. High-bit randomisation. A representative is a field element below (p−1)/2, so bits 254 and 255 are always zero. Two always-zero bits at a fixed offset is a fingerprint in its own right, and free to remove. generate fills them from the RNG; from_representative masks them off, so no caller can forget.

What this does not hide

Packet lengths, timing, volume, and endpoint addresses. Elligator2 removes one specific, decisive tell. A protocol whose packets are a constant 192 bytes and arrive in a fixed request/response rhythm is still trivially fingerprinted, uniform keys or not. Treat this as one component of a transport design, not as the design.

Nor does it hide anything about your static keys. It encodes points you hand it.

Verification

The map is differentially tested against curve25519-elligator2 — the Tor Project's fork, used by the Rust obfs4/Lyrebird stack. It is a dev-dependency only and never ships.

Tier	Compares	Pins
1	our decoder vs theirs, 2 000 random strings + edge cases	the forward map, bit for bit
2	their decoder on our representatives	our inverse inverts their forward
3	our decoder on their representatives	closes the loop
4	both encoders, same point and tweak	the inverse map, bit for bit

Plus our_points_are_not_always_prime_order, which is the only test that catches trap 2 — a bug all four tiers above would pass, because the map would be perfectly correct and the output would still be fingerprintable.

$ cargo test --all-features

Constant time

The field arithmetic is not hand-written. It comes from fiat-crypto, machine-generated from a formal specification with proofs of functional correctness and constant-time behaviour. The composition on top — the exponentiation chains, the square-root-of-a-ratio trick, the canonical encoding — is hand-written and branch-free with respect to field values: selection and negation go through subtle::Choice, and there is no if on a field element anywhere.

One deliberate exception. to_representative returns None for non-representable points and generate loops until it gets a Some, so the retry count is observable in timing. It branches on the discarded candidates; the accepted key is uniform over the representable set, so the count says nothing about the key finally used.

No formal side-channel analysis has been done on the composition, and this crate has not been audited. Judge it accordingly.

Credits

The map's structure came from reading curve25519-elligator2's representative_from_pubkey and map_to_curve_parts and matching their observable behaviour bit for bit. No code was copied — the field arithmetic is fiat-crypto and the composition is this crate's — so nothing is owed under their BSD-3-Clause. The debt is intellectual, and worth stating plainly:

• The Tor Project, for curve25519-elligator2 and for the obfs4 work that established what a correct dirty-key implementation has to do.
• The fiat-crypto project, for verified field arithmetic that made building on top of it a reasonable idea rather than a reckless one.
• Bernstein, Hamburg, Krasnova and Lange, for Elligator (CCS 2013).

Extracted from secure_mesh, where it implements the obfuscated wire profile.

Licence

MIT OR Apache-2.0, at your option.