Re: [freehaven-dev] Re: request for comments on Mixnet Reputations paper

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

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

David Hopwood wrote:
>   False claims are rejected
> [...]
>      Thus N_j can obtain (I_{j+1}, bar) from foo. If such an entry
>      was on the ledger (who wrote it there is irrelevant), and N_j
>      did not later post "To N_{j+1}: bar" to the ledger, then N_j
>      really did fail. Alice's claim is therefore true.
> 
>   Therefore, we satisfy Goal 2. Note that this also covers the
>   case where Alice attempts to send N_j ill-formed messages, since
>   (I_{j+1}, bar) is not ill-formed, and we have proven that when
>   Alice's claim is accepted, N_j must have received a message with
>   that as the plaintext. Any other messages that N_j may have received
>   are irrelevant.

There is a case I forgot - when foo is on the ledger and decrypts to
(I_{j+1}, bar), but N_j legitimately does not send it on, either
because:

1. (I_{j+1}, bar) appears to N_j to be a replay.

   If (I_{j+1}, bar) actually is a replay, then N_j has already
   processed it, so "To N_{j+1}: bar" will already have been added
   to the ledger. Provided that it is still on the ledger when
   a verifier tries to find it (assuming worst case timings), there
   is no problem. This does complicate the analysis of how long
   messages need to remain on the ledger, though; the analysis in
   section 4.1 of the paper is not correct. It also has to be taken
   into account that the timestamp of the message to N_{j+1} might
   be *before* that of the message to N_j.

   [To be fully rigourous, the proofs of goals 1 and 2 would have to
   specify what constraints on the relative timestamps of messages
   are needed for a valid proof, and show that:
    - for goal 1, there is sufficient time during which a delivery
      failure can be proven,
    - for goal 2, the messages produced when N_j correctly follows
      the protocol are never interpreted as a delivery failure,
      regardless of the timing of any previous messages and of
      the verification,
   taking into account message expiry from the ledger in each case.]

   Note that it would not be correct to assume that "To N_j: foo"
   has appeared on the ledger before, because there are many other
   possible ciphertexts that can decrypt to (I_{j+1}, bar).


   That leaves cases where N_j might be fooled into thinking that
   (I_{j+1}, bar) is a replay when it is not. To prevent this, the
   tags that N_j remembers in order to prevent replay attacks must
   include the plaintext (I_{j+1}, bar), or more likely in practice,
   a *collision-resistant* hash of it. They must not use hashes of
   the ciphertext, again because many ciphertexts decrypt to
   (I_{j+1}, bar).

   Here collision resistance is an extra condition that is needed to
   prevent Alice from preparing two distinct messages such that one
   will be considered a replay of the other. In a mix-net without
   delivery failure proofs, it is not normally necessary to prevent
   Alice from doing replay attacks on her own path, so I think only
   a pre-image resistant hash would be required in that case. The
   Babel protocol uses the session key of the message, which would
   also trivially allow Alice to cheat.

   [To prevent marking attacks, the encryption scheme must be
   "hop-by-hop non-malleable" over at least the portion of the
   message that is used to detect replays. In the case of reply
   messages, it might not be possible to make the scheme hop-by-hop
   non-malleable over the whole plaintext, because the message and
   the routing header are prepared by different principals who do
   not (normally) share any secrets. Finding a secure workaround
   for this could be quite complicated - probably the paper should
   just note that Here Be Dragons.]

2. (I_{j+1}, bar) is the last message in the chain, is cleartext
   (for example because it is being posted to a newsgroup), and
   triggers a filter for spam, viruses, or whatever.

   In this case to prove that the message was not delivered, Alice
   will have to provide the cleartext message bar, which allows a
   verifier to see whether it was reasonable to filter it (at
   least in the verifier's opinion).

   One way of reducing reliability problems caused by filters would be
   to insist that nodes either post the message, or bounce it back to
   the sender. Then the ledger could be used to verify that one of
   these actions occurred.

   Note that ciphertext messages should never be dropped by filters.
   In general, it has to be the responsibility of anyone receiving
   ciphertext to make sure that the contents are not harmful, since
   no-one who does not know the key can do that for them.

- -- 
David Hopwood <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

iQEVAwUBOjbgnjkCAxeYt5gVAQEdhwf/YwCqpa5dhstT7xfVzRpZaNMNY1BpltVa
NY9if6EhzJ52Fw5NgPk6Pcwt1cjDW+UXjAtI6pHhUv/8Z2y1Hg+IryJqdQmAfJKa
q44WLOGWTAm5lBwUTrSsAermUe5CdpptQ6pSaI1qDMloorgeFBrUhQc/vg26Ig9a
iFUMHWrr65fUrOG5YlZHF6CnI61NToRmvkKwtaFrbtZgia2NkuVfW/kkCRV1NBP+
50n1eUNffiuygnL2FNsUfOpXNl9gZfA5BT0Ssn9tod1RoKJDcy+v81jaEGerz015
V0cOLZUQRwJWqe4q+AjPmFkvLhNqHVfnPEBt1D7nFkmXrLVBbfh4lg==
=ZDmN
-----END PGP SIGNATURE-----