proposal for new AEAD+SPRP relay cell protocol
Cf. prop202; see also https://lists.torproject.org/pipermail/tor-dev/2012-March/003347.html
Advertised as a new Relay subprotocol and negotiated with a new HTYPE, in this new dual-cipher scheme, the relay cell is initially encrypted with an AEAD cipher for its final destination, then the outer layers of encryption use a length-preserving SPRP.
A single circuit may include a mix of this new relay cell crypto scheme for some hops, and the legacy AES-CTR cipher for other hops.
In the forward direction, when receiving a relay cell an OR performs trial decryption with the AEAD cipher. Successful decryption proves the cell was destined for the OR; on a failure, the OR decrypts it with the SPRP cipher and forwards it along the circuit, or tears down the circuit if the OR is the last hop.
In the backward direction, when receiving a relay cell, for each hop in the circuit (assuming all hops support the new crypto), the OP attempts decryption with that hop's AEAD key, and on a failure, decrypts it instead with that hop's SPRP key and repeats the trial decryption process with the next hop's keys. If the last hop's AEAD key fails to decrypt the relay cell, the OP tears down the circuit.
Relay cell payload
Using an AEAD cipher means allocating part of the 509 bytes of the relay cell's encrypted payload to a 16-byte authentication tag. However, 8 bytes of overhead can also be ripped out from the current payload: the Recognized field, the Digest field, and even the Length field can all go away.
Similar to how TLS 1.3 uses the ContentType byte to mark where the record-layer padding ends and the data begins, a relay cell can use the Relay command as a nonzero byte to separate padding from data, eliminating the need for an explicit length field:
Zeros [PLAINTEXT_PAYLOAD_LEN - 3 - len(Data) bytes]
Relay command [1 byte]
StreamID [2 bytes]
Data [PLAINTEXT_PAYLOAD_LEN - 3 - len(Zeros) bytes]
For this relay cell layout, PLAINTEXT_PAYLOAD_LEN is 493 bytes long, which wrapped in an AEAD cipher becomes 509 bytes of ciphertext. The maximum amount of useful data per cell is 490 bytes, 8 less than the current 498 bytes maximum.
AEAD cipher choice: AEAD_CHACHA20_POLY1305
Standardized in RFC 8439, widely deployed in TLS ciphersuites, it's fast and has constant-time software implementations without any specialized CPU instructions or hardware support. ChaCha20-Poly1305 is faster than AES-GCM on platforms that lack specialized AES instructions (like many smartphones do), and slower than AES-GCM on platforms that do have those instructions.
Benchmarks from 2014 https://www.imperialviolet.org/2014/02/27/tlssymmetriccrypto.html show about a 3x speed advantage on the sampled mobile chipsets, while it's half the speed of AES on an Intel chip with AESNI.
SPRP cipher choice: HBSH construction (Adiantum or HPolyC)
https://eprint.iacr.org/2018/720
HPolyC is HBSH mode instantiated with two invocations of Poly1305, one of XChaCha12, and a single AES block encryption/decryption of the last 16 bytes.
HPolyC is almost identical to but simpler than Adiantum, which is implemented in the Linux kernel and is widely deployed for disk encryption on smartphones launched with Android 10 or later. Using a SPRP construction that has more than just a single niche user seems like a plus.
Benchmarks on a Raspberry Pi (which lacks specialized AES instructions) in https://github.com/raspberrypi/linux/issues/3648 show speeds of 256.6 MiB/s
for adiantum and 71.0 MiB/s
for aes-xts.
Bonus stuff
While updating the Relay crypto scheme, maybe we also want a new KeyUpdate relay message, like they have in TLS 1.3?