Re: [freehaven-dev] POKs for mix accountability transcript

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

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

dmolnar wrote:
> On Wed, 3 Jan 2001 dmolnar@belegost.mit.edu wrote:
> > David Hopwood wrote:
> > > We would like to be able to prove to any observer that:
> > >   1) N_j received C (this part is easy)
> > >   2) E_pk_j(N_{j+1}, M) = C
> > >   3) M was not sent to N_{j+1}
> > >
> > > without giving away M or N_{j+1}. I'm not sure this is even possible
> > > [i.e. if M or N_{j+1} cannot be given away].

Actually I think I've been looking at this the wrong way. The leakage
of information is due to the fact that M and N_{j+1} can be linked with
Alice. That can be fixed by allowing Alice to publish the accusation
that N_j failed anonymously. Note that (C, M, N_j, N_{j+1}) is already
part of the view of N_j, so provided it cannot be linked with Alice,
the proof does not reveal any information that would not in any case
be assumed to be available to an adversary that had corrupted N_j.
This is true even if N_{j+1} is Bob, which is the worst case.

To implement this, we need to be able to give nodes an instruction
to publish a message on the ledger (i.e. all types of message, not
just "To N_i: M"). Alice also needs to be able to determine which node
failed before publishing the accusation. When all messages are
published on the ledger, this is easy assuming that the ledger
can be read anonymously, but in the modified protocol described below
using receipts, it requires being able to request a receipt and receive
the response from a node anonymously and privately. The routes used for
the original message, each receipt-request and reply, and the
accusation should probably be independent.


Here is the idea that I was discussing with David Molnar by email:

> I've had an idea about how to prove delivery failures without revealing
> as much information about messages to passive attackers:
> 
> Normally messages would be sent directly between mixes using secure
> channels. For each message, a signed receipt is given to say that a
> message has been received, and the recipient is responsible for
> forwarding it. If Alice accuses N_j of not forwarding a message to
> N_{j+1}, N_j produces its receipt (signed by N_{j+1}) to prove that
> it did. Receipts are held for as long as ledger entries would need
> to be held in the original protocol. Alice authenticates her request
> to see a receipt held by N_j using a field from the original message
> (i.e. from 'bar' below).
> 
> If for any reason N_j cannot obtain a valid receipt for a message
> (this can happen because N_{j+1} is down, is the subject of a DoS
> attack, or is dishonest), it instead publishes the message to the
> ledger. Mixes are also responsible for forwarding published messages
> that are addressed to them, just as in the original protocol.
> 
> So, suppose that Alice wants to accuse N_j of not forwarding a message
> (i.e. j is the index of the *first* mix on the route that did not
> follow the protocol). She shows that N_j received a message
> "To N_j: foo" either by obtaining from N_{j-1} a receipt for it
> signed by N_j, or because N_{j-1} wrote it to the ledger. Then she
> exhibits (r_j, N_{j+1}, bar) such that E_j(r_j, (N_{j+1}, bar)) = foo.
> If "To N_{j+1}: bar" is not on the ledger *and* N_j cannot produce
> a receipt for it signed by N_{j+1}, then it is blamed for not
> forwarding the message.
> 
> Note that (r_j, N_{j+1}, bar) does not stand on its own as a proof
> that N_j failed. However, if we also publish to the ledger the request
> to N_j to see its receipt, and N_j does not respond to that on the
> ledger within a given time, then we can reasonably conclude that N_j
> is unreliable (either because it failed to forward the original
> message, or because it failed to respond to the receipt request). I.e.
> as with the original protocol, any third party verifying the proof
> only needs to look at the ledger, not interact with N_j.
> 
> Disadvantage:
>  - By disrupting a channel between two mixes, an attacker can force
>    those messages to be published instead of sent securely, which
>    is not as good as using only secure channels. This requires an
>    active attack on the specific channel, though, so we are no
>    longer promoting all attackers to global passive attackers.
> 
> Advantages:
>  - Much fewer messages should need to be handled by the ledger,
>  - Messages are not published in the normal case,
>  - The presence of any message on the ledger is suspicious, and
>    indicates a possible attack that should be investigated.

More about this later; I've done some work on formalising it, but
that's not ready to post yet.

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

iQEVAwUBOlbDEzkCAxeYt5gVAQHMCwgAzTaQGXha1H7Z2YEvwoRK5YGXQeVFsnUG
8cbpafmUNNPKLdFw059L4f65X0PTC1pJy6Qu30I7bfn7SqPtDD5oSPzWoek6fTW8
qItRyIrbwC5y+UPxUSOwC5+8i4gvNO9WM2eGjDVb8LSQmw7opoR/72B2ou3h/NIQ
llyd3LbCvI2ze4q2RWrIaHkUAvkRAT8FPtu8IlLb8h+y9QmayD6UdRpwgaoDNjkm
HmbfQggzaHBnvkTXSGNsE1Y9jmNQUmDDJDkGhTAS/FcJ9cx9TkJe08ZPGxbs1MR+
+KB+gYzvLvEQrQxLGTKlJRPovzFyHaOZZgY4QUz8QqmkvRSaZKQ/3w==
=fZhh
-----END PGP SIGNATURE-----