[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Forward and reply messages
-----BEGIN PGP SIGNED MESSAGE-----
Roger Dingledine wrote:
> On Sat, Apr 20, 2002 at 03:00:23AM +0000, David Hopwood wrote:
> > > We've been working on the problem of making forward and reply
> > > messages indistinguishable at all points, [...]
> >
> > The problem with that is:
> >
> > - Reply messages can't be made non-malleable over the full message.
> > - Therefore, if forward and reply messages are indistinguishable to nodes,
> > forward messages also can't be made non-malleable over the full message.
> > - If forward messages aren't fully non-malleable, then there is a traffic
> > confirmation tagging attack that works regardless of the number of hops
> > on the path:
>
> Well, we're hoping the confirmation attack won't work. (I'm sold on the
> swap option rather than strip, at this point, as described below and in
> the last post.) Assume we're looking at a forward message. The message
> goes from Alice over the first leg of her path, to the crossover point
> where the headers get swapped, and then goes over the second leg of her
> path to Bobby.
>
> Because the swap operation involves decrypting the second header
> with a hash of the second header and payload, then even a malicious
> crossover point can't determine what the second leg is if anything has
> been tampered.
Hmm, that's correct for forward-only messages (note that the resulting header
can also depend on the rest of the message for the "strip" and "replace"
options, so this is not specifically an advantage for "swap").
However, it halves the effective number of nodes on the path, since an
attacker now only needs to control *either* all of the nodes before, or
all the nodes after the crossover point, plus the crossover node itself.
Also, if fixed but secret paths are used, then the attacker gains some
information about the first half of Alice's path even if he can't immediately
break the second half; this information could then be used in subsequent
attacks.
So it's definitely not clear that this is better than having forward and
reply messages distinguishable: in the latter case, you could double the
number of messages and get (roughly) the same size of anonymity sets, but
still have the full effect of the chosen path length for each message, and
therefore potentially lower latency for a given security/paranoia level.
Also, the attack still works against forward-then-reply messages (note that
you can't swap twice on the forward part of a forward-then-reply path). That's
the most serious problem IMHO.
> > sufficient. The attack works for both forward-only and forward-then-reply
> > messages, and it also works if a small number of the intermediate nodes
> > check non-malleability of the full message (as George suggested), provided
> > those nodes are controlled by Bobby (since in that case each tagged input
> > message can be re-tagged when it is output).
>
> It's not just that they check for tagging -- the protocol actively breaks
> the next leg of the path if the message has been tagged.
Yes, I'd forgotten that because I was mainly thinking about forward-then-reply
messages, where it doesn't matter (the attacker just needs to detect tagged
messages in that case, not re-tag them).
[...]
> > Incidentally, there is another alternative to the 'swap' and 'strip'
> > methods described in the archive, that makes forward and reply messages
> > indistinguishable; it has a 'replace' operation that replaces part of
> > (say, the last half of) the message header with pseudo-random junk. This
> > would be more efficient in message size than 'swap', and slightly more
> > flexible than 'strip', but since it still doesn't prevent the traffic
> > confirmation tagging attack, it's not what I would recommend.
>
> Actually, this was what the strip operation was all about.
As far as I understand, 'strip' shunts the message to the left so that part
of the message that was previously in the body (equivalently, the second header)
is now in the main header. This is not the same as 'replace', which changes
part of the main header. (The changed part could depend on the payload of the
message, for example using PRF(key, seed_in_header XOR hash(payload).)
> What I can't solve is that if the second leg is built by the receiver and
> the first leg is built by the sender, then the 'replace' operation needs to
> happen at the end of the first leg but creating pseudo-random junk based on
> what the second leg expects.
Yes. The sender could set
seed_in_header = seed_from_reply_block XOR hash(payload), for instance.
> So when you make a reply block you also need to separately include a seed
> for generating the junk that the reply block expects.
Yes, but that's only a minor complication.
> So it seems klunkier than swap.
It's possible to have more than one 'replace' operation in a path; that's what
I meant by 'replace' being more flexible (unfortunately, this doesn't help to
fix the attack against forward-then-reply messages, because it's still not
possible to have more than one replace in the forward part of a forward-then-reply).
Other than that, there's very little to choose between swap, strip, and replace.
Basically I agree with Zooko's recent message - we have to lose a factor of
two somewhere, it's just a matter of where:
a) the "two payload" approach doubles message size,
b) the "distinguishable" approach halves anonymity sets (for nodes, not
passive observers), requiring twice as many messages to compensate,
c) the "swap", "strip" or "replace" approaches double the path length.
However, c) has other disadvantages: it is more complex because it needs
a variable-length block cipher, and it doesn't protect the forward part of
a forward-then-reply message from a traffic confirmation attack by the
recipient. I'm also not convinced that it doesn't leak information about
paths if they are fixed and secret. I think we should eliminate c) and
choose between a) and b).
> > In any case, having distinguishable forward and reply messages is not so
> > bad. If we arrange that exactly half of the messages are of each type (e.g.
> > by doubling the length of forward-only paths and making those messages look
> > like reply messages on the second half of the path), then it only halves
> > the size of the anonymity sets.
Actually what I meant to say here is that the size of the resulting anonymity
sets are about the same, except that the sets of senders and recipients are
different: forward-type messages always go from a sender to a node, and
reply-type messages always go from a node to a recipient.
Alternatively, we can keep the path length the same (or add just one or two
reply-type hops on the end of paths for forward messages to hide whether users
are receiving forward messages or replies) and add more dummy messages for
whichever type is less common. That's probably more efficient, although it
is not equivalent in security terms.
> > The effect of that is pretty easy to analyse,
> > and can be partly compensated by adding more cover traffic.
> >
> > Another advantage of not trying to make forward and reply types
> > indistinguishable is that in that case we can do without a variable-length
> > block cipher (I think).
>
> Fair enough. It's certainly worth comparing. Tell me more?
Neither the "two payload" nor the "distinguishable" approaches require a
variable-length block cipher, because:
- in the "two payload" case, the part of the message that is not
authenticated is either just random, or it can only be distinguished
from random by the recipient who receives it encrypted. Therefore no
benefit can be derived from tagging it.
- in the "distinguishable" case, forward messages (including the
forward part of a forward-then-reply path) are authenticated at
every hop, so cannot be tagged without immediate detection.
Reply messages can only be distinguished from random by the recipient,
the same as in the "two payload" case.
So a XOR-based stream cipher (including CTR mode) is sufficient, since
we just need to randomise the message and not expand it.
Have a look at the attached diagram again (I fixed a couple of mistakes
in the previous version), which shows the "distinguishable" approach with
1 forward hop followed by 3 reply hops. The other difference between this
and the protocol you've been discussing is that the per-hop headers can be
variable-length.
To process any incoming message, a node does this:
1. Decrypt the public-key-encrypted part, using an IND-CCA2-secure scheme.
Drop if the PK ciphertext is invalid.
2. If the current time is after a deadline in the decrypted part, or the
message is a replay, drop it.
3. The decrypted part also includes a MAC value and the range of the message
covered by the MAC (either up to L_HEADER or the whole message); check
this and drop if incorrect.
4. Decrypt the same range that is covered by the MAC and shift to the left,
filling at the end with deterministic padding.
5. If the MAC only covered up to L_HEADER, decrypt the rest of the message
in-place.
6. Forward or process the message as specified by the header.
A reply block is contructed in the same way as a forward-only onion,
except for the length. To construct any onion:
1. Work out the total length taken up by per-hop headers and overhead.
2. Fill a buffer starting from that index with arbitrary padding to the
required length [dark blue in the diagram].
3. For each layer from outer- to innermost, decrypt that padding in the
same way as would be done by a node [light blue], filling at the end
with deterministic padding [magenta].
4. For each layer from inner- to outermost, encrypt the per-hop headers
[green for the public-key-encrypted parts, yellow for symmetrically
encrypted], and include a MAC of the ciphertext [input shown by the
red lines] in a field of each header.
Note that no special processing is needed at the crossover point for a
forward-then-reply message; from the point of view of the sender, the
reply block just forms the first part of the plaintext of an ordinary
forward message.
In the case of RSA, because all but a constant-size overhead can be recovered
from the RSA-encrypted block, the per-hop increase in length is independent
of the RSA key size. For RSA-OAEP+ [1], the length increase only needs to be
about 70 bytes per hop (the diagram shows it larger than the RSA key size
in some cases just to show that that isn't a limit). The node public keys can
be different lengths.
The fact that the headers are variable-length is independent of the choice
of how to do replies, fortunately.
[1] Victor Shoup,
"A Proposal for an ISO Standard for Public Key Encryption (version 2.1),"
Revised December 20, 2001.
<http://www.shoup.net/papers/>
- --
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
iQEVAwUBPMWdFzkCAxeYt5gVAQHO1ggAunf+aAwMh8z2cxpJ0/qK6A43v9ysWUEe
6RS6CpVh9DutRrGGWiY70vEKdw9JaH9Vc9RSYjTt4H4VdyX2cZeC3cBKIn/YI2WC
nY0Gat3kckBAtfN1K9RPdvRbRgt1MhL4yFM5eh7coEBq+x7QjChUyhnNIT4ps1iY
ow40lo5pbdBpRZ04wVaLXFk83qqdpP6PRUODWV7MQ+ZYTtzh8ePmCTERlba99voc
cd1F2FVCPJ25pO2CfOSnAIfSIw/5kH+0XIHeeAG11tjK9i/OhbmLLP5kYvB7/PEm
VbkQJiYNzRqInRBiKDc1mcwDzMtB/ZUCG7oX1W08YKj88zmt3T2tKg==
=67oF
-----END PGP SIGNATURE-----
