Gateway opt-in makes onion routing over relays possible

[nothingmuch]

With payjoin/ohttp-relay#58, relays could also signal opt-in to accepting OHTTP traffic from other relays, exactly like the directory signals in #369.

When making an OHTTP request, the client constructs a request for the relay, and serializes it using binary HTTP. When this is a POST request with a PSBT, the body of the request is first padded to 7168 bytes, and then encrypted using the receiver or the sender's key. Then the binary HTTP request is padded to 8192 bytes encrypted that to the directory.

The encapsulation overhead is not 1024. The HPKE encapsulation overhead is 64 bytes for ECDH, uses uncompressed key, 16 bytes for AEAD tag. The binary HTTP overhead is 7 bytes, plus the HTTP method and target resource URI, which will vary.

When decapsulating, if an incoming message fails to decrypt, we could consider truncating it at 128 byte intervals, so 7 more decryption attempts (I believe the costly part is parsing the ECDH point and checking if it's on the curve [that only needs to be done once since it's a shared prefix], the AEAD and symmetric encryption should be comparatively cheap [and can be done by just checking if the last 128 byte aligned tags blocks match the tag, returning the one that matches if one matches]).

Instead of padding to 8192 bytes, clients could pad to one of these lengths: 7296, 7424, 7552, 7680, 7808, 7936, 8064, 8192 (ideally using randomness in the choice), before encrypting the next layer. The last request would be padded with random data that does not get encrypted, up to 8192 and sent to the first relay. Upon decrypting the first binary http request, that relay would then pad the result with random data to 8192, and forward to the next relay in the chain, etc.

Clients that don't use this mechanism should randomize the padding of the first request, so as to not reveal the fact that the next target resource is a directory instead of a relay, and to not reveal to the gateway whether or not this onion encryption mechanism was used prior to the most proximate relay.

See below for how to do constant size.

This suggests that for maximizing privacy against a global passive adversary, relay operators should also be directory operators and vice versa, and also opt-in to sending and receiving cover traffic to each other, consider relaying traffic as in a Poisson mix (c.f. loopix), and that relays should use http2 or http3 to communicate with gateways in order to take advantage of multiplexing, making traffic analysis more difficult.

[nothingmuch]

Having looked into this in more detail, we can do better than what I initially suggested, by borrowing from Sphinx similar to how LN does and avoid variable length packets.

Sphinx style onion wrapping

1. The Sphinx KEM trick can be used with HPKE KEM parameterized by secp256k1, so 65 byte overhead is paid only once.
2. The Sphinx KDFs can similarly be used with the HPKE KDF, and can be used to generate padding.
3. in the spirit of the improved construction, using a modern AEAD to authenticate both the header and the payload can be applied to OHTTP messages
4. Sphinx's padding scheme can be applied to binary HTTP encapsulation:

• the addressing information, which is variable width, is in the binary HTTP's request control data specified in URI terms (scheme, authority, etc)
• the next tag can be placed in a pseudo field. an alternative is to deviate from RFC 8439's specification that the tag follows the ciphertext, and instead prepend it to the ciphertext. this alleviate the need to copy the tag for the next layer from a pseudo field to the end of the next encrypted payload
• the nested payload would be padded analogously to Sphinx's header padding, to the same size as the encapsulating request. for simplicity this could decrypt to 0 bytes, but that would reveal to any node along the route the size of the stripped encapsulation of the previous hop, i think this is fine since that should only vary by information already known to that node (namely the URI where it can be reached), but it's also possible to stay truer to Sphinx's original specification and have the padding be noise, and to rely on RFC 9292's allowance for non 0 padding. I'm still mulling over this.

The main difference is that the addressing data is variable length, when in Sphinx's original description it's fixed size.

It's not clear how to handle HPKE parameter selection, the KEM has to be fixed, but the AEAD and KDF could be allowed to vary but this seems like asking for trouble with no clear motivation. A more rigid specification can also specify how to deviate from from RFC 8439's concatenation, while still maintaining compatibility with it apart from putting the tag at the beginning, but doing this in general while leaving the AEAD mode free to be parameterized seems like a recipe for disaster.

References RFC 9548 (OHTTP) and 9292 (binary HTTP) and 9180 (HPKE), and Sphinx (original paper, improved construction, and a general framework according to whom's taxonomy we probably want $S \bar{T} I \bar{R}$, i.e. service, untrusted receiver, with integrity and no reply block support, see below re reply blocks)

RFC 9292 privacy leaks

RFC 9292 specifies that lengths should be specified using a variable sized encoding, but does not require using the smallest byte size for a given numerical value, which means it's potentially non-canonical:

All lengths and numeric values are encoded using the variable-length integer encoding from Section 16 of [QUIC]. Integer values do not need to be encoded on the minimum number of bytes necessary.

Secondly, RFC 9113, on which RFC 9292 is based, does not specify a canonical order for pseudo fields.

This is a potential client fingerprint, and arguably a gap in the OHTTP specification, which should probably recommend that the encapsulated request be canonically encoded.

Reply Blocks & Privacy Preserving Introduction

Reply blocks are not required since OHTTP responses are given interactively. However, since the directory implements a store and forward service, similar to Sphinx nymservers, this suggests the possibility of using reply blocks in a manner similar to Pudding, which would allow establishment of a secure channel, e.g. for sender initiated payjoins (#559) and coalition formation with arbitrary co-spenders (#412)

[nothingmuch]

I spent some time working out the details. The coding effort required to make
this work seems a bit high, because the hpke and ohttp APIs are not really
designed for this. There are also some open questions.

The main conclusion is that we should use random padding instead of 0 padding in
order to avoid making future support for usage of such functionality
fingerprintable.

Actually implementing this will be painful since practically none of the public APIs for hpke, bhttp, or ohttp can be used in the manner described here. For this reason I first describe a simplified version, and separately Sphinx's KEM reuse trick.

The construction is similar to Sphinx, but with a payload size of 0 and a
variable sized routing information. Our current use of OHTTP is the special case where $r = 1$.

OHTTP configuration is assumed to be fixed as it currently is in rust-payjoin. The KEM can actually vary, but for the KEM blinding trick it needs to at least be consistent and support blinding like DH based KEM does. The symmetric crypto for the requests is arbitrary, though lengths are important, but for fixed size responses this assumes Poly1305, although it seems that a similar hack could be used for e.g. an HMAC the same one would have to be used throughout. The symmetric cipher and the KDF can vary along the route, for simplicity this assumes fixed parameters. If they are really fixed then the 7 byte OHTTP header could be reduced to just a 1 byte key ID per hop.

Minimal Approach

In this variation, only filler strings are used to pad as in Sphinx.

Variables are as in the Sphinx paper:

• $r$ is the number of hops, starting at 0 for the first relay, with hop $r$
  terminating at the OHTTP gateway of the directory
• $\alpha_i$ is the DHKEM curve point
• $s_i$ is the shared secret for relay $i$
• $\rho_i$ is the encryption keystream derived from $s_i$
• $\phi_i$ is a filler string (random padding)

With the following additions:

• $l_i$ is the OHTTP encapsulation overhead per hop
• $L_i$ is the cumulative overhead, see below
• $L$ is the total overhead

Determining per request overhead (variable)

First we can construct known size BHTTP request templates, one for each onion
layer, whose total size will be 8104 each, but whose body size is not yet known.

The per hop overhead is variable because each intermediate relay URI authority
could be of a different length.

At hop $r$ the authority is that of the directory server. Relay 0 is not
included, because the client directly submits to it a request which it will
forward to relay 1.

bhttp::Message has a Vec<u8> for the body and therefore acts as a
buffer. The QUIC variable length encoding uses the two most significant bits to
indicate length. For BIP 77, 8104 is an upper bound, necessitating 2 bytes. In
many circumstances GET requests to a mailbox may fit in the 63 byte limit of a 1
byte length encoding, so this must also be accounted for (not counting the
authority, only ~28 bytes are required to encode a GET request on a mailbox).

In principle (but not easily using the bhttp public API) this could be done in a
single buffer, with 88 bytes of padding between each level the next level of
nesting, which will be used for the OHTTP encapsulation. 88 = 65 + 16 + 7
accounting for for KEM, AEAD tag and OHTTP header respectively.

This envelope is analogous to Sphinx's $n_i$ components, the node address to
forward to, which are fixed size in the original design.

The length of these envelopes is denoted $e_i$. $i$ indexes recipients ranging
from 0 for the outermost layer to $r$ the innermost. The full per-hop overhead
$l_i = e_i + 88$, accounting for a 16 byte AEAD tag, 7 bytes of OHTTP header and
65 bytes of KEM (but see below).

These cumulative sums of overheads are the lengths of the filler strings (which
are denoted $\phi_i$ in the paper), and will be denoted
$L_i = \sum{j=0}^{i} l_j$ here.

The total onion routing overhead $L = L_{r-1} = \sum_{i=0}^{r-1} l_i$. Note that
this does not include $l_r$, the overhead of the current OHTTP encapsulation,
but only the additional layers.

Padding Innermost Payload

With the total overhead computed, we can pad the innermost string. The innermost
plaintext is the BHTTP request that interacts with the directory's target
resources (i.e. get or post a 7168 byte HPKE encrypted message on a mailbox).

The only difference from normal OHTTP handling from the point of view of the
final gateway (the directory), is that the encapsulated BHTTP request plaintext
for the OHTTP gateway necessarily ends up padded with tailing pseudorandom bytes
of the filler strings instead of being 0 padded all the way to the end. Note
that BHTTP does not require padding data be 0 bytes, so this is random padding
is valid (although not encouraged) in the specification.

For this reason in order to make the use of onion routing vs. only a single
ohttp relay indistinguishable, the current padding should switch from using 0
bytes to random padding:

diff --git a/payjoin/src/ohttp.rs b/payjoin/src/ohttp.rs
index fb1a744..986ac1b 100644
--- a/payjoin/src/ohttp.rs
+++ b/payjoin/src/ohttp.rs
@@ -3,6 +3,7 @@ use std::{error, fmt};

 use bitcoin::bech32::{self, EncodeError};
 use bitcoin::key::constants::UNCOMPRESSED_PUBLIC_KEY_SIZE;
+use hpke::rand_core::{OsRng, RngCore};

 use crate::directory::ENCAPSULATED_MESSAGE_BYTES;

@@ -41,6 +42,7 @@ pub fn ohttp_encapsulate(
     }

     let mut bhttp_req = [0u8; PADDED_BHTTP_REQ_BYTES];
+    OsRng.fill_bytes(&mut bhttp_req);
     bhttp_message.write_bhttp(bhttp::Mode::KnownLength, &mut bhttp_req.as_mut_slice())?;
     let (encapsulated, ohttp_ctx) = ctx.encapsulate(&bhttp_req)?;

Without this change, the directory will not only be able to detect whether or
not onion routed requests are in use for additional hops prior to the last
relay, but also estimate the route length based on the number of non 0 bytes
found in the final BHTTP plaintext (the application level request for the target
resource, not the OHTTP request for handled by the final OHTTP gateway).

The innermost plaintext should therefore padded with random bytes to length
$8104 - L$. Current behavior can be seen as a special case where $L = r-1 = 0$,
assuming padding with 0s is replaced with random padding.

Computing filler strings

Filler strings have lengths corresponding the cumulative overhead lengths $L_i$
are also computed from outermost to innermost (apart from for the last hop),
using the AEAD keystream. The purpose of the filler strings is to to allow each
intermediate relay $i$ to pad its plaintext, i.e. the ciphertext for the
next recipient $i+1$, to the same size as ciphertext $i$.

The outermost filler string $\phi_i$ is just the last $l_0$ bytes of the
keystream for that first hop. The next filler string is computed by appending
$l_1$ 0 bytes, and then XORing that with the last $l_0 + l_1$ bytes of recipient
$i$'s keystream. This process repeats, until $\phi_{r-1}$ is produced.

Finally $\phi_{r} = \phi_{r-1} \oplus \rho_{r}$, i.e. the last filler string is
not extended.

From a code perspective, it's not clear how to best do this without changing the
AeadCtx API to allow access to the keystream, but the keystream for an outer
hop must accessed before the plaintext for the nested payloads can be
constructed. This goes against the design of the AEAD traits (which combine
encryption and tagging using seal and open, and utilize &mut receiver to
avoid nonce reuse, etc). It seems like the most natural change would be
implementing an additional trait specific for computing Sphinx style filler
strings, and that could be implemented for it in parallel to the existing AEAD
traits, allowing the internal struct to be shared between normal HPKE and this
Sphinx like nested HPKE using the same internal types. ChaCha20 is a bit like a
block cipher in counter mode, i.e. it allows for random access, so given the key
and nonce the relevant parts of keystream can be computed independently of the
earlier part of the keystream, but not with the existing APIs.

Encryption

Encryption proceed from the innermost encapsulated request to the outermost.

After padding the innermost string, the filler string $\phi_{r}$ is appended
to it, resulting in a 8104 byte plaintext. This is encrypted with the keystream
$\rho_r$, which is derived from shared secret $s_r$.

The plaintext has the following structure, apart from random padding this is the
same as current behavior. As a reminder, $L = L_{r-1} = L_r - l_r$, and
$l_i = e_i + 88$:

[ 8104 plaintext
  [ 7168+e_r BHTTP request for target resource
    [ e_r BHTTP framing, control data, etc, with POST or GET method ]
    [ 7168 BHTTP content with BIP 77 payload if POST ]
  ]
  [ 8104-(7168+L+e_r) random padding ]
  [ L \phi_{r} ]
]

That is then encapsulated as the following OHTTP message, same as what is
constructed in the current implementation (and therefore what we want relay
$r-1$ to post to the directory):

[ 8192 OHTTP message
   [ 7 OHTTP header ]
   [ 65 KEM ]
   [ 8120 AEAD
     [ 8104 ciphertext ]
     [ 16 AEAD tag ] 
   ]
]

This is too large to encapsulate in an 8192 byte OHTTP request, but the last
$L_r$ bytes of the ciphertext are the same as $\phi_{r-1}$, and that the last
$l_{r-1}$ bytes of that are the same as $\rho_{r-1}$. This means that given
$s_{r-1}$ these bytes have no information content, so relay $r-1$ can
reconstruct this part of the ciphertext (relay $r-1$'s plaintext) before it
forwards, and therefore these bytes can be removed:

[ 8104 plaintext
  [ 16 copy of AEAD tag ]
  [ 8104 truncated BHTTP request for target gateway
    [ e_{r-1} BHTTP framing, control data, etc for POST req ]
    [ 8192-l_{r-1} BHTTP content with truncated OHTTP message ]
  ]
]

Note that the AEAD tag must be preserved, and ChaCha20-Poly1305 specifies that
it is appended, so this has to be copied to the beginning of the plaintext.
Since this plaintext is no longer a regular BHTTP request, the media type of its
encapsulation must indicate the onion format is being used.

This can then be encoded similarly a normal OHTTP message:

[ 8192 OHTTP onion message
   [ 7 OHTTP header ]
   [ 65 KEM ]
   [ 8120 AEAD
     [ 8104 ciphertext ]
     [ 16 AEAD tag ] 
   ]
]

This OHTTP onion message similarly has $l_{r-2}$ deterministic trailing bytes,
and can therefore be truncated when constructing the next message

[ 8104 plaintext
  [ 16 copy of AEAD tag ]
  [ 8104 BHTTP request for relay r-1
    [ e_{r-2} BHTTP framing, control data, etc for POST req ]
    [ 8192-l_{r-2} BHTTP content with truncated OHTTP onion message ]
  ]
]

This continues until the ciphertext for relay 1 is constructed, and it too can
be truncated to 8104 bytes, constructing the 8192 byte OHTTP message that is
posted by the client directly to relay 0.

Note that at this first hop OHTTP requests and OHTTP onion requests may be
distinguishable due to different regular HTTP requests to relay 0, so the media
type for onion requests should be the same length as message/ohttp-req, e.g.
x-message/ooh-req. These requests are still variable sized due to the
authority of relay 1 (and current behavior is the special case of $r = 1$), so
it might be preferable for clients to submit the initial messages as fixed size
OHTTP encapsulated messages directly to relay 0's gateway. This would also
facilitate transport layer encryption using double OHTTP over HTTP instead of
single OHTTP over HTTPS for making OHTTP requests without a TLS dependency (but
the OHTTP configuration of relay 0 would also need to be bootstrapped).

Decryption & Forwarding

Decryption of an onion request works exactly the same as with unmodified OHTTP,
but the handling of the encapsulated BHTTP request deviates.

The AEAD tag and BHTTP request containing the truncated internal OHTTP message
are parsed. Before handling the BHTTP request by POSTing its internal OHTTP
message to the next OHTTP gateway, the message is padded to 8176 bytes using
$\rho_i$. This can't be done as a decryption of 0 bytes since the length of the
truncated plaintext is not known before decryption. Appending the AEAD tag to
this results in a valid OHTTP message that can be forwarded to relay $i+1$, or
to the target gateway in the case of $i+1 = r$.

Response Handling

For response handling, each relay encrypts the data, but instead of appending
the tag, it sums it with the tag of the nested response.

The client decrypts by XORing the keystreams with the ciphertext, and computing
the authenticator tag sum, and comparing against the received sum. This leaves
the response size unmodified.

Unfortunately if using this trick for constant size responses, corruption is not
attributable to any particular relay.

Security should be argued more rigorously, but a hand-wavy argument for why this
still preserves end to end authenticity (well, i hope) is that because the tags
are one time authenticators indistinguishable from random strings (due to the
use of a blinding term) and because each relay only computes one tag at a time
as normal and the key material for it is determined, any malicious relay would
have a negligible probability of guessing a maliciously selected tag value that
when summed with the tags of any honest relays matches the tag of a corrupted
ciphertext.

That said, for now this trick should still be considered a crime against
cryptography.

KEM with blinding

In the Sphinx paper, $\alpha_i$ is computed as ${\alpha_{i-1}}^b$, where $b$ is a
blinding term that is derived from $s_{i-1}$ using a different KDF than for
$\rho_{i-1}$.

This means that the 65 bytes of secp256k1 DHKEM overhead can be shared between
all OHTTP messages.

In the bitcoin-hpke crate, an onion feature gated setup_onion_sender can be
introduced. This would not be generic over a KEM with KemTrait bound, but
specifically require SecpK256HkdfSha256 or a new trait representing
amenability of a KEM to blinding.

setup_onion_sender needs to accept &[<SecpK256HkdfSha256 as KemTrait>::PublicKey]
instead of just one recipient public key, the final one corresponding to
setup_sender's pk_recip. It must return a list that for each hop contains a
shared secret and an AEAD encryption context (i.e. each entry is like
setup_sender's return value).

First, a single sender ephemeral key sk_eph needs to be generated.

Then secpk256_hkdfsha256::encap_with_eph would be called with the recipient
public keys in sequence, generating a shared secret for each hop. The first
shared secret just uses sk_eph directly as the ephemeral key. From that shared
secret, a blinding term needs to be derived with the KDF, and so that the next
encap_with_eph call uses sk_eph * blinding_term. This allows the first
recipient to take the KEM curve point they received and multiply it by the
blinding term they derive from their shared secret, obtaining the KEM value for
the next hop.

The KDF for the encryption key and the blinding t erm must be domain separated
(this presents a slight complication since info is passed in as is for the
encryption context, so it makes sense to use a prefix of the empty string for
the encryption context, and a hard coded prefix prepended to the info string
used to derive the blinding term.

[nothingmuch]

If we assume an network combined relay+directory nodes, then this design also lends itself to async multi-hop OHTTP requests, i.e. a mixnet instead of just onion routed OHTTP.

An optional field on the proposal can include a reply block, again based on the Sphinx design, allowing the receiver to communicate with the sender on an arbitrary directory while hiding their chosen directory from the receiver.

The sender polls the mailbox named as the final destination in the reply block(s) as they wait for responses.

Multi hop OHTTP requests could be posted to something that isn't quite an OHTTP relay but an async mix node. This kind of relay returns immediately, with the HTTP status only indicating the OHTTP request was queued (i.e. no message/ohttp-res is given). The encapsulated OHTTP (multi hop) request could then be asynchronously POSTed to the next async-relay/directory.

A BHTTP pseudo-field can include a reply block as well or instead of the reply block given to the receiver. If such a reply block is included in an async onion OHTTP message, the nested OHTTP (multi hop) message should be forwarded synchronously, and the reply block should be used by the relay to deliver the OHTTP response back to the client.

If the $r-1$-th async relay always gets a BHTTP level reply block, then all directory requests always look the same to the directory, like the current protocol data, regardless of whether they originate from 1 hop or multi hop, sync or async clients, or whether an internal reply block is included.

All of this would be backwards compatible with plain OHTTP clients and receivers that don't support reply blocks.

[nothingmuch]

A $S\overline{T}IR$ construction for reply blocks (provides payload integrity):

https://iacr.org/archive/asiacrypt2021/130900100/130900100.pdf

Concrete updatable encryption (UAE with Bounded Updates) using nested symmetric crypto for reply blocks, provides padding with integrity protection analogous to forward paths:

https://eprint.iacr.org/2020/222.pdf

[riverKanies]

this was a very helpful resource for me when implementing onion wrapping for the BOSS program assignment https://ellemouton.com/posts/sphinx/

also the LN spec is informative (and they have test data) https://github.com/lightning/bolts/blob/master/04-onion-routing.md

I can share my code for this assignment if desirable (rust)

[nothingmuch]

https://arxiv.org/pdf/2501.02933