Source timing and replies

[David Hopwood <david.hopwood@zetnet.co.uk>]

-----BEGIN PGP SIGNED MESSAGE-----

I wrote:
> [...] More generally, we can use a source-timed network, where each hop
> header specifies the time that a message must be received from the previous
> hop, and the time it must be sent to the next hop.

There's a problem with using this for replies - the reply block would have
to specify exactly when the reply message will be sent.

There are two possible approaches:

 a) Live with this limitation. Note that it only really affects replies that
    don't go via a nymserver, since if we use the IMAP-like protocol for
    nymservers, they can be supplied with reply blocks that can be used to
    send any pending messages immediately. Most protocols built on top of
    Mixminion will probably also only need immediate replies.

    Another possibility for replies that don't use nymservers is to give
    the replier several reply blocks that can be used at different times.
    This isn't as inefficient as it sounds, because reply blocks can be quite
    small (about 1 Kbyte, I think). Since each block is single-use, we
    would normally need to give out more than one anyway (when not using a
    nymserver).

 b) Have the hop header for second-half hops specify a set of possible
    times when it could be received, specified by an arithmetic progression
    and an expiration time, i.e. { t_first + t_batch * i : i = 0..k }.
    Also make the time it is sent to the next hop relative rather than
    absolute.

    This prevents attacks that would be possible if messages could
    be delayed to a different mini-batch, but not attacks that delay
    messages by a whole number of batches (the latter are less serious
    for a synchronous batching network). Note that this only affects the
    second half of the path, and if a cascade is used for part of it,
    that should provide sufficient security; but the analysis is still
    more complicated.


Note that for a), there is no need for nodes to keep any record of message
hashes across mini-batches to prevent replays; it only needs to check
whether a message is repeated in a mini-batch. For b), OTOH, some message
hashes will have to be retained for as long as the maximum validity time
of a reply block, and there are potential problems with the expiration time
giving away information that reduces the anonymity set.

I think overall I prefer a).

- -- 
David Hopwood <david.hopwood@zetnet.co.uk>

Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5  0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip


-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: noconv

iQEVAwUBPN/ZzTkCAxeYt5gVAQG6Mgf+JbeZcHlk7ICMdMhCoiSfKegqqQ77nAGE
hzwS9q87OEGz77eVz6LPogHzIIZoTWGdREaHHB550X6OQgE/P0f+s+ZKzgpov6uZ
LouzTEkX3xhuXx+nt7k8qhgMFsWOff7WnY5gRRGAUtbgsTvCv+wf7ZsdsnwdCNtH
EXslVj+6qer3K7JEnhDyMkFu79Ml9EX2cdJgxrYL5rB3/3iHxcGzNLmeBvsRup0j
5dC4LAMEbQpxfFttcVm4rQFojAUet2owGbhGZKpkNd1l9wm+xq11h0Xds7WGv3Hs
xKj/HKUiwjHSIxwYkIls51NXK5vUSm10LVY7O2eDKS+o+PlltNfmbw==
=UDof
-----END PGP SIGNATURE-----