flamenet-elligator2
Elligator2 over Curve25519, in Swift, in the flavour obfs4 uses.
This exists because CryptoKit gives you X25519 and nothing underneath it. Apple exposes key agreement; Elligator2 needs the field itself, square roots, Legendre symbols, inversion, so the field arithmetic is written here from scratch.
Why this is the piece that has to be right
Elligator2 is what makes an obfs4 handshake look like uniform random bytes. A Curve25519 public key on the wire is recognisable; its representative is not.
A wrong implementation does not fail. It produces 32 plausible bytes, handshakes still complete, keys still agree, the representatives are merely not quite uniform, which is exactly what a censor's entropy test is looking for. There is no exception, no error return, no runtime symptom of any kind.
So the only defence is agreeing with the reference implementation byte for byte,
on inputs neither side chose. That is what Reference/vectors is for, and it was
written before a line of Swift.
It earned its keep immediately. The first Swift version was wrong on 256 out of 256 vectors, because of this line in the Go:
_, isSquare := t1.SqrtRatio(montgomery.ONE, t1)
The receiver is the destination: t1 is replaced by √(1/t1), and every later
use of t1 means the root, not the denominator. The Swift kept the denominator.
Every output was a well-formed, entirely wrong 32 bytes.
What is here
Sources/Elligator2/Field.swift |
GF(2^255 − 19), radix 2^51, five limbs |
Sources/Elligator2/Elligator2.swift |
sqrtRatio, montgomeryFlavor, the direct map |
Sources/Elligator2/Elligator2Inverse.swift |
the inverse map: public key + tweak → representative |
Sources/Elligator2/DirtyScalarBaseMult.swift |
the Montgomery ladder, cofactor left intact |
Sources/Ntor/Ntor.swift |
the obfs4 ntor handshake, both sides, and the KDF |
Sources/Obfs4Framing/SipHash.swift |
SipHash-2-4 and the cumulative length DRBG |
Sources/Obfs4Framing/Salsa20.swift |
Salsa20, HSalsa20, XSalsa20 |
Sources/Obfs4Framing/Poly1305.swift |
Poly1305 |
Sources/Obfs4Framing/Secretbox.swift |
NaCl secretbox (XSalsa20-Poly1305) |
Sources/Obfs4Framing/Framing.swift |
the frame encoder and decoder |
Sources/Obfs4/Handshake.swift |
the handshake messages, marks and MACs |
Sources/Obfs4/Packet.swift |
the packet layer and the replay filter |
Sources/Obfs4/Connection.swift |
the sans-I/O session driver |
Sources/Obfs4NIO/Obfs4ClientHandler.swift |
the client channel handler |
Sources/Obfs4NIO/Obfs4ServerHandler.swift |
the bridge channel handler |
Sources/Obfs4NIO/PaddingPolicy.swift |
burst padding |
Sources/obfs4bridge/main.swift |
the deployable bridge |
Dockerfile |
the container it ships in |
Sources/Obfs4Framing/GoRandom.swift |
Go math/rand semantics and the length distribution |
Tests/Elligator2Tests/FieldTests.swift |
field identities, on carry-exercising values |
Tests/Elligator2Tests/Elligator2VectorTests.swift |
256 vectors against lyrebird |
Tests/Elligator2Tests/Elligator2InverseTests.swift |
round trip, exact match, and the rejection rate |
Tests/Elligator2Tests/DirtyScalarBaseMultTests.swift |
256 private keys against lyrebird, plus structure |
Tests/Elligator2Tests/NtorTests.swift |
64 handshakes against lyrebird, from both sides |
Tests/Elligator2Tests/SipHashTests.swift |
SipHash and the DRBG, ten blocks deep |
Tests/Elligator2Tests/FramingTests.swift |
each primitive, then whole frame runs |
Tests/Elligator2Tests/HandshakeTests.swift |
real handshakes captured off the wire |
Tests/Elligator2Tests/GoRandomTests.swift |
Go's RNG quirks, and the distribution |
Tests/Elligator2Tests/ConnectionTests.swift |
packets, replay, and a whole session |
Tests/Elligator2Tests/InteropTests.swift |
Swift client → a real lyrebird bridge |
Tests/Elligator2Tests/ReverseInteropTests.swift |
a real lyrebird client → the Swift bridge |
Tests/Elligator2Tests/NIOInteropTests.swift |
the NIO handlers, both directions, against lyrebird |
Reference/vectors/main.go |
the oracle, which generates the vectors |
swift test
Regenerating the vectors (needs Go, and network access to the Tor Project's GitLab):
cd Reference && go run ./vectors > ../Tests/Elligator2Tests/elligator-vectors.json
The generator refuses to emit anything the reference cannot round-trip, so a broken toolchain produces no vectors rather than bad ones.
Status
Both roles interoperate with real lyrebird, in both directions.
$ Scripts/interop.sh
bridge up at 127.0.0.1:50838
REVERSE INTEROP OK: lyrebird accepted the Swift bridge and its echo
Executed 3 tests, with 0 failures
INTEROP OK: both directions -- a real lyrebird bridge accepted the Swift
client, and a real lyrebird client accepted the Swift bridge.
--- bridge log ---
handshake refused: EOF ← the probe-resistance test
handshake accepted ← the Swift client
That is the claim everything else was building toward. This port can dial a bridge and be one, and the Tor Project's own code decides for itself in both cases.
- Field arithmetic, tested on its own
sqrtRatioreturns both the root and the squareness bit, because callers need the bit to pick a branch, not to detect an error- The direct map: representative → public key. 256/256.
- The inverse map: public key + tweak → representative, or
nil. Bytes match lyrebird; everything accepted round-trips; over 2048 random points it accepts 51.5% and rejects the rest. - Cofactor-dirty scalar base multiplication. 256/256 private keys produce lyrebird's exact public key.
- The ntor handshake, client and server, plus the HKDF-SHA256 KDF. 64/64 handshakes agree with lyrebird on KEY_SEED, AUTH, and key material.
- Link framing: SipHash-2-4, the length DRBG, XSalsa20, Poly1305, NaCl secretbox, and the frame codec. Whole runs of frames match lyrebird byte for byte, and decode back byte-at-a-time as a socket would deliver them.
- The handshake messages, both directions, including the mark and MAC that give obfs4 its probe resistance.
- The packet layer, replay filter, and a sans-I/O session driver.
- Go's
math/randsemantics, so the packet-length distribution derived from a seed matches lyrebird's exactly.
Recordings, not computed vectors
The handshake cannot be vectorised the usual way: it carries random padding chosen inside lyrebird and a MAC over the current epoch hour. So the generator runs a real lyrebird client against a real lyrebird server over a pipe, proves they round-trip actual traffic, and records exactly what each side sent.
The padding then turns out to be recoverable, it sits between a fixed-length prefix and the mark, so a parser that finds the mark recovers it. Re-generating from the recovered representative, padding and epoch hour reproduces the recording byte for byte, which makes these a test of generation and not only of parsing.
The epoch hour is a parameter, never read from the system clock inside the library. A MAC with a hidden clock dependency cannot be tested against a recording, because the recording rots within the hour.
What the interop test proves, and what it does not
Proves: a Swift client interoperates. Breaking the mark's truncation, or
encoding the epoch hour as binary, each turn the run red with the one diagnosis
that is true, the bridge refused to answer, and lyrebird's own log names the
cause (Failed to find M_[C,S]). Discarding the bytes that follow the handshake
in the same read fails at the frame decoder instead, so the two failure modes
are distinguishable.
Proves, since the reverse test: the server role too. Swapping the framing key halves by role leaves the forward test green, a client takes the first half either way, and fails the reverse one at the frame decoder. That asymmetry is the reason both exist.
Does not prove: anything that depends on the two ends disagreeing about something. Both runs share a machine and therefore a clock, so a server that MAC'd its reply under its own epoch hour instead of the client's passed both of them. That bug only shows against a client an hour out, precisely the case the ±1 window exists to serve, so it is covered by a unit test with a forced skew instead.
A correction it produced: substituting a dirty long-term identity key for a clean one also passed. The comment claiming that breaks every handshake was wrong: X25519 clamps its scalar, so the order-8 component cancels on both sides and the shared secrets still agree. Bridges use clean identity keys by convention and because every bridge-line tool expects it, not because the maths forces it.
A wire-format bug looks like a hang. obfs4 bridges do not reject handshakes they dislike, they go silent. Every read in the test has a timeout, and a timeout is reported as refusal rather than as a network fault, otherwise the first real bug costs an afternoon of tcpdump.
Indistinguishability is not interoperability
The length distribution is the one part of this port that could be wrong without anything breaking. Padding is padding: a peer reads the declared payload length and ignores the rest, so any distribution talks to a real bridge.
What a different distribution costs is the entire point of obfs4, looking like
other obfs4 traffic. Packet length is among the first things a censor would
model, so GoRandom reproduces Go's math/rand quirks exactly: Float64
divides an Int63 by 2^63 rather than using the cleaner form Go rejected, and
Perm swaps m[0] with itself on its first iteration. Both quirks consume
randomness. "Improving" either desynchronises every draw that follows, and both
were confirmed by falsification.
Sans-I/O, and why the socket layer still needed its own interop test
The connection layer takes bytes and returns bytes: no sockets, no async, no timers. A transport welded to a socket can only be tested by opening one, which is how protocol bugs in that shape reach production.
But "nothing left to get wrong" turned out to be too strong. The NIO client
handler crashed on its first run against a real bridge:
Range requires lowerBound <= upperBound. The handshake driver returned
consumed, an index into the buffer it had accumulated across all reads,
which a handler feeding it one socket read at a time cannot slice. It only
misfires when the server's handshake spans two reads: routine over a real
network, almost never over loopback, which is exactly why the POSIX interop
test had not found it.
The fix was to return the leftover bytes rather than an offset, removing the trap instead of documenting it. The lesson is the general one: sans-I/O moves the protocol somewhere testable, it does not make the I/O layer free of bugs: buffering writes that arrive before the handshake finishes, keeping the decoder fed across reads, not losing what shares a segment with the reply. Each of those loses data without producing a wrong byte anywhere.
The asymmetry that catches people
The server searches only the tail for the mark: a client cannot send anything valid past its MAC, since it has no server ephemeral key yet.
The client must substring-search, because a real server sends framed data immediately after its handshake, often in the same segment. Applying the tail trick to the client side is the obvious symmetry, and it fails against every real bridge. The captured vectors contain exactly that trailing data, so this suite catches it.
Why the ladder, not Edwards
lyrebird computes the dirty public key the way Monocypher's dirty_fast does:
Ed25519 scalar multiplication, plus a low-order point, converted to Montgomery.
That needs a full Edwards implementation with a precomputed base-point table.
Monocypher's dirty_small reaches the same answer by decoupling the cofactor
from the main factor, add lsb·L to the trimmed scalar and run an ordinary
Montgomery ladder against a base point of order 8·L. It is about half the
speed, a small fraction of the code, and constant-time by construction rather
than by careful table lookup. Monocypher says the two agree; the vectors
confirm it, which is why that claim did not have to be taken on faith.
Speed does not matter here: this runs once per connection, and the caller already discards about half its keys.
The wrong answer that sits next to the right one
The clean X25519 public key, what every library computes, is a perfectly good Curve25519 key. It agrees on shared secrets. It round-trips. It is simply confined to the prime-order subgroup, and therefore distinguishable, which defeats the entire purpose. Clamping the private key before the call is all it takes to get it.
So there is a structural test as well as the byte comparison: the dirty key must differ from the clean key exactly when the low three bits of the private key are non-zero, and equal it exactly when they are not. Both arms are asserted to actually occur, so neither can pass vacuously.
Every claim above was proven able to fail. Stopping the ladder at bit 255,
dropping the cofactor, removing the final compensating swap, or substituting the
ordinary base point each turn the suite red; the vector test reports 1 of 256
when a single entry is corrupted rather than passing quietly.
Where the reference lies
obfs4's ntorCommon documents its transcript ordering as
ID | B | Y | X | PROTOID, immediately above code that builds
B | B | X | Y | PROTOID | ID, with B twice, because the buffer is
constructed with it and then written to again. The code is the protocol.
Port from the comment and you get a handshake that computes cleanly, derives a respectable 32-byte KEY_SEED, and cannot talk to a single real bridge.
Both orderings were tried against this suite. Both leave
testTheTwoSidesAgreeWithEachOther green, two identically-wrong
implementations agree perfectly, and only the comparison against lyrebird
catches them. That test exists to make the point, not to prove correctness.
Corrections this port has had to make
The framing is XSalsa20-Poly1305, not AES-256-CTR with HMAC-SHA256. This README claimed the latter for its first three commits. Nothing was testing the claim, so nothing caught it; the vectors did, the moment the code was written.
The length DRBG is cumulative, not a fresh hash per block. obfs4's comment
describes IV[n] = H(K, IV[n-1]). The code never resets the SipHash state, so
block n is really SipHash(K, IV[0] ‖ … ‖ IV[n-1]). Both readings agree on
block one and diverge from block two, an implementation built from the
comment decodes the first frame of a connection perfectly and then fails. The
DRBG is checked ten blocks deep for exactly this reason.
ntor's transcript is B ‖ B ‖ X ‖ Y ‖ PROTOID ‖ ID, with B twice, while
the comment above it says ID ‖ B ‖ Y ‖ X ‖ PROTOID.
Three documentation errors in one protocol, none of which any amount of careful reading would have settled.
Not written yet:
- IAT (inter-arrival time) obfuscation,
iat-mode1 and 2. Mode 0 (disabled, and what every real deployment uses) is what is implemented. Modes 1 and 2 add per-write delays and need a timer in the handler.
Running a bridge
docker compose --profile obfs4 up -d obfs4bridge
docker compose logs obfs4bridge # prints the bridge line to hand to clients
The state volume holds the bridge's identity key and is escrow-critical.
Clients pin it through the cert= in their bridge line, so losing the volume
orphans every client that ever received one. The process refuses to start rather
than silently re-key, so an unmounted volume fails loudly instead of quietly
breaking reconnects.
Set FN_OBFS4_ADVERTISE to the public host:port. A container cannot know
its own public address, so without it the bridge line says <this-host> and
what you hand clients is not dialable.
There is no HEALTHCHECK, deliberately. A bridge is meant to be silent to anyone who cannot complete a handshake, so any probe proving it works would also prove it is there, the property obfs4 exists to deny. Watch the process, not the port.
Timing
Elligator2 in obfs4 touches a public key, its representative, and a tweak. The first two go on the wire in the clear. The scalar multiplication touches the private key itself.
Swift makes no constant-time guarantees, so neither does this. What is
written is constant-time style: no branch, loop bound, or memory index
depends on a secret. Conditional selection takes an all-ones/all-zeros mask
built arithmetically from the secret bit, never a Bool from a comparison,
because a Bool is an invitation to the compiler to branch. That is necessary
and not sufficient, an optimiser is free to undo it. Treat this as defence
in depth for an ephemeral session key, not as a hardened primitive.
One branch is deliberately variable-time: whether a point is representable at all. Monocypher makes the same call and explains it, this leaks only how many tries it took to find a representable key, which is safe precisely because keys are tried at random.
Field must never be reused for scalar multiplication on secret keys
without revisiting all of this.
See NOTICE.md for provenance, and read it before making this
repository public. The inverse map is taken from Monocypher rather than
lyrebird for a licensing reason that is recorded there.