[Cryptography] Preventing correlation on rebinding connection identifiers.

Phillip Hallam-Baker phill at hallambaker.com
Thu Feb 11 16:04:12 EST 2021

So, a little curlicue just popped up.

One of the problems I am going to need to solve at some point is to rebind
a connection after the source IP address/port change. This can be caused by
a NAT reconfiguration, a DHCP event or the user simply changes from one
network to another.

The idea here is that Alice is going to establish a connection between her
device and her Mesh Service Provider Hosts that is persistent and survives
changes to the configuration on either end. We can assume the Host end will
be on a static IP address and port[1]. But the client end is going to vary
a great deal.

So in the ordinary state of affairs, the host recognizes packets from Alice
by their source address+port and this is used to obtain the shared secret
used to decrypt the remainder of the message.

If the client source address+port change, the host is going to respond with
a packet saying 'unrecognized connection' and bounce the source address and
port back to the client. The client then realizes that its outbound
connection config has changed and we need to rebind.

One option would be a packet 'claiming' the prior source address+ip but
that seems ugly. I would like to have as little connecting one packet to
another as possible enclair.

So the next thing would be to have an encrypted connection ID as follows:

When connecting, Host specifies rebinding key and the connection ID.

To rebind, the client takes the current time in ticks and creates a packet
{time, connectionID} and encrypts it under the rebinding key. This is then
accepted by the host if the  time value is close enough to the host idea of

This works a bit better but we still have something of an issue because the
rebinding key is the same for every connection to that host.

One possibility that is relatively cheap is to use a collection of n pairs
of encryption keys and issue a different set of pairs to each connection.
So if there are a maximum of 64K connections to a host, we have 16 pairs of
keys. Connections 0 and 1 will share the first 15 keys, only the last will
be different.

The client encrypts the value {nonce, time} under each of their keys, the
nonce value is different each time, the time changes. The nonce values are
then fed into a KDF to generate the session key to decrypt {time,

To verify the rebinding claim, the host attempts decryption under each of
the possible keys, discarding the values whose time values don't match.

The nice thing about this approach is that we could even extend it to
TOR/Mixmaster/etc. type applications in which nobody knows who is talking
to whom.

[1] The Host port/address should only change when Alice service provision
is transitioned to a different host. And this should (usually) be a planned
event that is properly managed.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20210211/fb3ca1e9/attachment.htm>

More information about the cryptography mailing list