[freehaven-dev] (FWD) Re: paper comments - 1st impressions

[Roger Dingledine <arma@mit.edu>]

----- Forwarded message from David Hopwood <hopwood@zetnet.co.uk> -----

Date: Sun, 25 Feb 2001 07:11:38 +0000
From: David Hopwood <hopwood@zetnet.co.uk>
To: freehaven@freehaven.net
Subject: Re: paper comments - 1st impressions

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

Michael J Freedman wrote:
> It sounds like maybe we should sit around "after" the "Free Haven" meeting
> tomorrow and talk about the paper and how we best want to go about this.
> 
> David (Hopwood):  If it would be possible to give some feedback before
> Sunday 2-ish (EST) -- that's like 7pm GMT -- and what you think you can
> work on, that would be great!

OK, this is my feedback.

> >> ______________________________________________________
> >> Reviewer 4: Score 50
> >>
> >> Review summary: Severe practical problems associated with the
> >> requirement for everybody to read everything all the time.
> >
> >Yes and no.

Yes. This does cause very severe practical problems. Fortunately, I
think it's possible to eliminate the ledger entirely.

The purpose of the ledger in the original protocol was to split
sending a message from receiving it, in such a way that anyone can
determine later whether a message was sent. The problem it solves
is that if A fails to send a message to B, we want an observer
to be able to determine whether that is A's fault or B's fault.

I suggested before a method of reducing reliance on the ledger by
using receipts. Suppose we use that idea, and also replace the remaining
use of the ledger with a set of "judges" (who are fairly well respected,
but none of which need be trusted absolutely). The judges should have
reasonably reliable, high-bandwidth Internet connections.

If N_i tries to send a message to N_{i+1} but cannot obtain a receipt,
then instead of publishing the message, it sends it to all of the
judges (if N_i cannot manage to contact any judges, then it should be
considered unreliable, so it is OK that it does not obtain a receipt).

Each judge then independently tries to send the message to N_{i+1}
(who must provide a separate receipt for each connection). If a judge
obtains a receipt, it sends it back to N_i. If N_i receives at least
one valid receipt from a judge, it will store one of them as if it had
obtained it directly from N_{i+1}. If a judge cannot obtain a receipt,
it concludes that N_{i+1} was unreliable, and publishes that fact
(here we are communicating the fact that N_{i+1} is unreliable to
human listeners, rather than to programs, which allows use of various
channels that are unlikely to all be attacked). If someone hears enough
judges that they trust say that N_{i+1} is unreliable, they will
believe that it is.

This also simplifies the failure proofs, because all messages should
have receipts (rather than having to consider the two cases of messages
that are sent directly, and those that are published to the ledger, as
in my previous suggestion).

To accuse N_j of being unreliable, send an accusation (that it received
a message M and did not pass it on in time) to all of the judges.
N_j can refute it by sending back its receipt for M to each judge.
The judges who do not get back a receipt that refutes the accusation
will conclude that N_j is unreliable, and publish that as before.

[back to the original protocol...]
> >You could do periodic updates or reads, if you're willing to
> >accept a risk of being behind.

There has to be at least one update and read by each mix in each
time period, or the protocol doesn't work. Reviewer 4 is saying that
that is impractical if all messages have to be published on the ledger,
and I think I agree.

[re: fungible payments]
> >> Page 4, section 2.4 "some kind of digital cash". Why only like that?
> >> Why not accounts?

Because accounts are not anonymous. Certainly it wouldn't be secure to
give a bank an instruction to transfer payment from the sender's account
to the mix node's account, because then you would be entrusting the
sender's anonymity entirely to the bank, which would defeat the point
of using a mix-net with chaining. You might as well use the bank as a
single, completely trusted mix node in that case.

That leaves protocols in which the sender obtains some kind of
unforgeable token from its bank, gets it to the node anonymously
(it doesn't make sense to use anything but the mix-net for that), and
then the node deposits it at its own (possibly the same) bank. Also,
the token cannot reference the sender's account (which excludes
e-cheques). That is pretty much the definition of a digital cash
protocol.

> >> Makes no sense.

Makes perfect sense, although the paper didn't go into enough detail.

> >We should talk about recompense or payment more generally, without
> >discussing digital cash unless we really need to do so. The point still
> >stands that there's no good way to pay MIXes in place.

Yes there is. I will post a protocol for this (that can also pay for
storage and other things).

> >> Page 4, sect 3. "negligible probability" should be "negligible
> >> advantage". Define "passive adversary"! Otherwise it is a meaningless
> >> statement. The part about traffic analysis being in its infancy is not
> >> convincing.
> >
> >This goes back to the model being moved up earlier in the paper. then we
> >can define a passive adversary. Negligible advantage is correct.
> >
> >> It is well understood how to perform traffic analysis if
> >> you have unbounded (but polynomial) resources. That is the kind of
> >> attack you have to consider!
> >
> >It is? I mean, it is the attack we have to consider, but I didn't know
> >that it was well understood. Show me the papers.

I'm also not convinced it is well understood (and I'm pretty sure that
active traffic analysis attacks are not).

> >> Page 5: you require that the ledger is fully trusted. This is not made
> >> clear. Why should I trust the ledger and not the servers? Why will
> >> the ledger not constitute a bottleneck? Alice would have to read ALL
> >> information available at the ledger. Otherwise, she reveals what
> >> messages she is interested in checking the routing of.

Yes, this is correct.

> >> That means that she has to read everything ALL the time -- stopping
> >> to be interested would also reveal that the message has been delivered!

But this isn't, necessarily.

> >Why do we need to check immediately after the message has been delivered?
> >
> >> This is amazingly inefficient. If you read selectively, a lot of
> >> information can be gleaned. That might be devastating.
> >
> >First, yes, we need to make the trust requirements for the ledger more
> >explicit!

IMHO, we should get rid of the ledger. The trust requirements on the
judges in the suggestion above are much simpler.

[...]
> >> p 7. "Unambiguous etc"> You are saying that D(E(m1))=m2 -> m1=m2. This
> >> is absolutely standard, and it is meaningless to have it any other
> >> way.

Yep.

> >Yeah, I thought so too, until talking to Anna and Chris. We should
> >probably cook up some example to show how this might not hold for
> >different public keys,

Not relevant (well, I found it interesting, but it's not relevant to
the subject of the paper). Just state that D(E(r, m1))=m2 => m1=m2,
which is all that is needed in the proof.

> >> p 7 Do you need timestamps? By whom? If you trust the ledger anyway,
> >> it only has to write down the time, no real time stamp.
> >
> >What do they consider a real time stamp?

I think the reviewer must be thinking of timestamping based on digital
signatures. The paper did mean that the ledger "just writes down the
time". To me, 'timestamp' just means the recorded time and date of any
event (which is also what it means in realtime software), but if people
are going to be confused, we should probably use some other word.

> >> p 9 "hash cash". Why such a solution? How do you verify the
> >> correctness of an "access token"? If this has a cost associated with it
> >> that is not way smaller than that of generating a random string and
> >> submit that, it can still be abused for attacks.

My suggestion on how to do hash cash in detail addressed that, but wasn't
in the paper.

> >> So it won't
> >> work. This seems to be irrelevant to the remaining paper, and not
> >> described in sufficient detail.

The reviewer is right that this wasn't well motivated by the rest of the
paper. The protocol using digital cash that I referred to above will do
that, I think, but I need to work on it some more.

> >> p 14. If you prove misbehavior, you give out identifying information,
> >> as you state somewhere.

Fixed by sending accusations via the mix-net (in the protocol using judges,
the accuser would probably send to each judge by a different route - this
works as long as the mix-net is not so unreliable that none of the
messages get through, or not enough get through that people will trust
that many judges).

> >> That is a very low degree of robustness. A
> >> last mix server on the line could always replace the outgoing message
> >> with what he feels like.

To prevent this, the final recipient should look like another mix
node, and should send a receipt back to the sender using a one-time
reply block. Obviously this doesn't apply for recipients who don't have
any compatible software, but nothing can be done about that.

> >> p 18 Yes, it is known how to make universally verifiable mixes. Many
> >> of the mixes you quote as related work have that property.
> >
> >Universally verifiable via the use of ZKPs which prove that all MIXes
> >worked correctly.

And what if they didn't - is it possible with these protocols to identify
a specific mix that failed?

> >Except for the Desmedt-Kurosawa MIX from Eurocrypt 2000
> >which isn't just ZKPs.

Are any of the papers on mix-nets from EUROCRYPT and ASIACRYPT 2000 on-line?

> >> ______________________________________________________
> >> Reviewer 5:Score 50
...
> >> lengthy presentations of trivial statements, like "Ciphertext
> >> Collision Free Encryption;" please note that decryption is usually
> >> deterministic, and in any case correctness requires that almost always
> >> D(E(m)) = m for correctly chosen keys.
> >
> >Again, we could probably get away with showing why PK schemes aren't for
> >multiple keys, then showing that they are for single keys and then that
> >we're ok with single keys.

Same comment as above. I'll rewrite this part of the paper.

> >> Regarding Sections 1-4, I disagree with your statement "The
> >> reliability and efficiency of MIXes have been a secondary concern."
> >> Reliability is the main motivation for using majority threshold
> >> decryption for MIXes (your bibliography contains several such articles
> >> ...).

Hmm. I suppose I'd better read those papers first.

> >Actually, I read those papers as trying to acheive anonymity via a process
> >which can't be compromised unless k out of n MIXes are compromised. as in,
> >anonymity with better guarantees against traffic analysis. So time to look
> >at them again.
> >
> >The point we should probably look at here is that our protocol requires
> >less modification to existing MIXes,

I don't think this is important. If it's simpler (and therefore probably
easier to analyse), that is important.

> >and that it's a new idea for MIX reliability.

Yes.

> >> Sections 5-9 are somewhat new, but offer no surprises.  There is no
> >> discussion on active attacks. For instance, usually a mix network
> >
> >Yes, this is a good point. We should explicitly say what we can do about
> >these attacks.

I can do that.

> >> Or another example: if users choose
> >> mixed according to their reputation then an adversary might simply try
> >> to offer the best and most reliable service on many mixes, so that
> >> often only his mixes are chosen.
> >
> >Didn't we say exactly this in the paper?

Yes. I don't think it's a serious problem - hopefully it will be feasible
for legitimate mixes to offer a service which is almost as reliable as a
well-resourced attacker could, and in that case the attacker won't be
able to obtain any significant advantage because of this.

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

iQEVAwUBOpiv8jkCAxeYt5gVAQHz6AgAh/HDDkQFkm9qnNWgXH0EEaZOh3KTxFrG
okcV7zSsMzJl+M5ND3te8FT/g1AysSQdL1fTSo14zB0VQbw8GiOkLP6RvVemP+Vm
MWV+A3k9UHidnTdDxYHOptIJ61jOceomcWACQdAwWvHqbDIav1JDqAl5drSR1lkt
vJSM3IT3iepbv2cmctrDCAT26hY9GbVw/ijSjFbdpWtQNEZIDUHk/1vJ+t/NbWGG
iAQb2b3Nj6M6CYM4og6wRkAEIZuzn4u0fF4JzeTjFaoiMROwDlrlGvG+uL+30wKZ
UhdxxBiOzw6B4MkR+WV7OsLDKMXMg8JumLq1azBRzbnr9GKtKIzzvQ==
=0Cne
-----END PGP SIGNATURE-----

----- End forwarded message -----