Scan existing bridges for the obfs4 distinguishability bug (pre-v0.0.12 obfs4proxy)

tl;dr, this is nothing urgent. It's about a distinguishability bug in obfs4proxy that was fixed at the same time as another bug. The ticket is private because we have an opportunity to scan existing bridges for both bugs simultaneously, and we might want to do that before public disclosure.

We have talked about a bug in a package that obfs4proxy relied on that supposedly made handshakes distinguishable from random, and which, after being fixed in version v0.0.12, caused probabilistic interoperability problems when one side had upgraded and the other had not. I have been making progress at understanding the nature of the bug and the interoperability problems resulting from the fix. It should be possible to write a remote prober (or a passive distinguisher) to detect the bug, though it will require doing some actual elliptic curve math.

Something I have not seen discussed yet, and which I discovered only yesterday, is that old versions of obfs4proxy have another, distinct bug: the most significant bit (the 255th bit, counting from 0) of Elligator-encoded ephemeral public keys is always 0. Encoded public keys are 32 bytes long and are stored in little-endian order; therefore bit 255 is the most significant bit of byte 31. This bit is always 0 in any TCP stream produced by a pre-v0.0.12 obfs4proxy, client or server.

To be clear, there are two different bugs. Elligator-encoded keys are 254 bits long; the top 2 bits must be randomized separately, in order to get a uniformly random string of 32 bytes. The noncanonical representative bug in agl/ed25519, the bug we knew about, was that the second-most significant bit, bit 254, one of the two bits that encoding is supposed to leave unset, was sometimes set and sometimes not, in a way not statistically independent of the lower-order bits. This bug in obfs4proxy is that it does not randomize the most significant bit, bit 255, which instead remains 0, as it is output by the Elligator encoder. See the tweak parameter in the patched v0.0.12 code, and how it is used to randomize the top 2 bits; that part is missing in versions before v0.0.12. Compare with "It is the caller's responsibility to randomize the 2 high bits of the representative..." in libelligator.

The bit that is always 0 makes for an easy distinguisher that doesn't require any math: watch connections to a suspected server, and if the 255th bit is always 0, the server is pre-v0.0.12 obfs4proxy. It works for clients too, because the obfs4 protocol has both clients and servers send Elligator-encoded ephemeral public keys at the same place in the stream. If you know a server's node ID and public key (which are encoded in the cert parameter of the bridge line), you can even actively scan the server to see if it is affected.

The good news is that both bugs were fixed in the same commit, which overhauled how Elligator is done in obfs4proxy. Therefore you can remotely scan an obfs4 server, and if it is free of the always-0 bug, it is also free of the noncanonical representative bug. Below is a program to scan for the always-0 bug. You provide it a host:port address and the cert parameter from a bridge line. The program connects to the server 20 times, and if bit 255 is 0 all 20 times it outputs "FAIL"; otherwise it outputs "PASS".

#!/usr/bin/env python3

# Usage: obfs4-bug-check 192.95.36.142:443 qUVQ0srL1JI/vO6V6m/24anYXiJD3QP2HgzUKQtQ7GRqqUvs7P+tG43RtAqdhLOALP7DJQ

import base64
import getopt
import hmac
import os
import socket
import re
import sys
import time

NUM_TRIALS = 20 # control with -n option
TIMEOUT = 5     # control with -t option

opts, (addr, cert) = getopt.gnu_getopt(sys.argv[1:], "n:t:")
for o, a in opts:
    if o == "-n":
        NUM_TRIALS = int(a)
    elif o == "-t":
        TIMEOUT = float(a)
host, port = re.match(r'^\[?(.*?)\]?:(\d+)$', addr).groups()
port = int(port)
cert = base64.b64decode(cert + "==="[:(4-len(cert)%4)%4])
nodeid = cert[:20]
pubkey = cert[20:]
assert len(nodeid) == 20
assert len(pubkey) == 32

def mac(msg):
    return hmac.digest(pubkey + nodeid, msg, "sha256")[0:16]

def trial():
    # https://gitlab.com/yawning/obfs4/-/blob/obfs4proxy-0.0.13/doc/obfs4-spec.txt#L156-163
    repr = os.urandom(32)
    padding = os.urandom(85)
    mark = mac(repr)
    epoch_hours = str(int(time.time()) // 3600).encode()
    s = socket.create_connection((host, port), TIMEOUT)
    try:
        s.send(repr + padding + mark + mac(repr + padding + mark + epoch_hours))
        r = s.recv(32)
        return (r[31] & 0x80) != 0
    finally:
        s.close()

num_ones = 0
err = None
try:
    for _ in range(NUM_TRIALS):
        if trial():
            dot = "1"
            num_ones += 1
        else:
            dot = "."
        print(dot, flush = True, end = "")
except Exception as e:
    print("X", flush = True, end = "")
    err = e
    report = ("ERROR", str(err))
else:
    report = ("PASS" if num_ones > 0 else "FAIL", f"{num_ones}/{NUM_TRIALS}")
print(*(("", addr) + report))
if err is not None:
    sys.exit(2)
elif num_ones == 0:
    sys.exit(1)
else:
    sys.exit(0)

Tests of existing bridges

I grabbed three bridges from bridges.torproject.org and scanned them. Two of them had not upgraded and had bit 255 stuck at 0.

$ perl -an -e '/^obfs4 (\S*) (?:\S+) cert=(\S+)/ && print "$1 $2\n";' bridges.txt | while read addr cert; do ./obfs4-bug-check $addr $cert; done
.................... 185.31.174.60:443 FAIL 0/20
.................... 142.132.237.143:2538 FAIL 0/20
1.111...1...1..11..1 90.127.32.238:42024 PASS 9/20

All the default Tor Browser bridges have upgraded:

$ perl -an -e '/^obfs4 (\S*) (?:\S+) cert=(\S+)/ && print "$1 $2\n";' tor-browser-build/projects/common/bridges_list.obfs4.txt | while read addr cert; do ./obfs4-bug-check $addr $cert; done
1..111.111.11.1111.. 192.95.36.142:443 PASS 13/20
1.111.111.11..1.1111 38.229.1.78:80 PASS 14/20
1..111.1.1.11....11. 38.229.33.83:80 PASS 10/20
.11111..11.....1..11 37.218.245.14:38224 PASS 10/20
11..111.11....111..1 85.31.186.98:443 PASS 11/20
1111...1.1111.1.111. 85.31.186.26:443 PASS 13/20
1.1.111.1111..1111.. 193.11.166.194:27015 PASS 13/20
11..1.....111.1.1111 193.11.166.194:27020 PASS 11/20
.111.1....11.......1 193.11.166.194:27025 PASS 7/20
...1.....11..111.111 209.148.46.65:443 PASS 9/20
1111....1.1.111..... 146.57.248.225:22 PASS 9/20
1.11.1111.1.1....111 45.145.95.6:27015 PASS 12/20
..11..1...1.11...11. [2a0c:4d80:42:702::1]:27015 PASS 8/20
1.111..1..1111.1..1. 51.222.13.177:80 PASS 11/20

How to reproduce locally

Build a pre-v0.0.12 version of obfs4proxy:

$ git clone https://gitlab.com/yawning/obfs4
$ cd obfs4/obfs4proxy
$ git checkout e330d1b7024b4ab04f7d96cc1afc61325744fafc
$ go build

Create this torrc file:

SocksPort 0
ORPort 127.0.0.1:auto
PublishServerDescriptor 0
BridgeRelay 1
DataDirectory datadir
ServerTransportListenAddr obfs4 127.0.0.1:12345
ServerTransportPlugin obfs4 exec ./obfs4proxy -unsafeLogging -logLevel DEBUG -enableLogging

Run tor:

$ tor -f torrc

Grab the cert parameter from datadir/pt_state/obfs4_bridgeline.txt. Run the bug checker script and see "FAIL":

$ ./obfs4-bug-check 127.0.0.1:12345 hNzHgvwEUmPV7PhuhRasLGyWx/TjnCIUxYcOQ7fDl2p7EmQ9Tm8EzLmuAtevceE6LoS9Dw
.................... 127.0.0.1:12345 FAIL 0/20

Stop the tor process. Build a post-v0.0.12 version of obfs4proxy:

$ git checkout 77af0cba934d73c4baeb709560bcfc9a9fbc661c
$ go build

Run tor again:

$ tor -f torrc

Run the bug checker script again and see "PASS":

$ ./obfs4-bug-check 127.0.0.1:12345 hNzHgvwEUmPV7PhuhRasLGyWx/TjnCIUxYcOQ7fDl2p7EmQ9Tm8EzLmuAtevceE6LoS9Dw
.1...11...1111111.11 127.0.0.1:12345 PASS 12/20