extant2000git a9339a02ff
ci / secret-sweep (push) Successful in 4s
ci / swift-test (push) Successful in 4m45s
ci / interop (push) Successful in 7m56s
Merge pull request 'Move CI from GitLab to Gitea Actions' (#6) from ci/gitea-actions-20261025 into main
2026-10-26 00:12:57 +00:00

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
  • sqrtRatio returns 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/rand semantics, 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-mode 1 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.

S
Description
Elligator2 over Curve25519 in Swift, verified byte-for-byte against the obfs4 reference. Foundation for a native Swift obfs4 client.
Readme MIT
552 KiB
Languages
Swift 81.4%
Go 14.2%
Shell 3.6%
Dockerfile 0.8%