Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[dawuud]

In the Loopix paper at the end of section 4.1.2 it says:

"""
If the number of messages in client’s inbox
is smaller than a constant threshold, the provider gen-
erates additional dummy messages. Thus, the adversary
observing the client-provider connection, as presented on
Figure 3, cannot learn how many messages were in the
user’s inbox. Note that, as long as the providers are hon-
est, the protection and receiver unobservability is perfect
and the adversary cannot learn any information about the
inbox and outbox of any client.

If the provider is dishonest, then they are still uncer-
tain whether a received message is genuine or the result
of a client loop – something that cannot be determined
from their bit pattern alone. However, further statistical
attacks may be possible, and we leave quantifying exact
security against this threat model as future work.
"""


On Fri, Nov 24, 2017 at 04:09:50PM +, Michael Rogers wrote:
> On 21/11/17 02:12, dawuud wrote:
> > Katzenpost is delivery by pull as well. Clients retreive messages from 
> > their Provider.
> > This paper:
> > 
> >  [DUMMYINTERSECTION] Berthold, O., Langos, H.,
> >  "Dummy Traffic Against Long Term Intersection Attacks",
> >  In the Proceedings of the PETS 2002,
> >  .
> > 
> > mentions that there are some constraints needed for the intersection attack 
> > to work:
> > 
> > a. the adversary is able to watch all user lines
> > b. the adversary is able to watch all Provider/server lines (see figure 1 
> > in paper)
> > c. the adversary knows how long it takes for a message to traverse the mix 
> > network
> > d. messages belonging to a certain session have to have the same property
> >that allows the adversary to link them each together
> > 
> > So in Katzenpost I don't think constraint "c" is met since we aren't using
> > synchronized batch mixing... but rather the Poisson mix strategy where
> > clients select the mix delay for each hop in the route which should be 
> > different
> > for every sent message, even retransmits... although client route hop 
> > delays are sampled
> > from an exponential distribution. The attacker can of course compute the
> > probability of a certain route delay having been choosen by a client.
> 
> Yes, I think the attack would still be possible given a probability
> distribution over delays instead of a fixed delay.
> 
> My starting point here is the statistical disclosure attack
> (https://www.freehaven.net/anonbib/cache/statistical-disclosure.pdf),
> which says that if I'm watching the inputs and outputs of a round-based
> anonymity system, and I see Alice sending messages into the system, and
> for each round where Alice sends a message I see all the messages
> exiting the system, then starting from a uniform probability
> distribution over all possible recipients I can refine that distribution
> with every observation, to eventually discover Alice's communication
> partners. The longer I watch the system, the closer my distribution gets
> to Alice's real distribution.
> 
> I think we can generalise that by replacing the rounds with a
> probability distribution over delays. So for each message Alice sends
> into the system, instead of having a set of output messages that
> definitely belong to the same round, I assign every future output
> message a probability of being Alice's message based on the delay. But
> the rest of the attack remains the same: I use the probabilities
> assigned to output messages to update the probability distribution over
> possible recipients, and over time that distribution approaches Alice's
> real distribution.
> 
> Of course the Loopix authors know this, hence all the dummy traffic to
> prevent an attacker from knowing which users are actually sending and
> receiving messages. I think the big question is whether that provides a
> useful amount of protection at a reasonable level of overhead.
> 
> > I also cannot think of a way that "d" is met... unless of course there
> > is collusion with the destination Provider.
> 
> If I understand right, condition d just means there must be some set of
> messages you're interested in, and you must know which messages they are.
> 
> In the statistical disclosure paper, the session is all messages sent by
> Alice and the goal is to identify the set of recipients. In the Berthold
> and Langos paper it's the other way round - the session is all messages
> sent by some unknown sender and the goal is to identify the sender. But
> either way, there's some set of interesting messages and the goal is to
> separate them from the uninteresting messages.
> 
> Just as we can generalise from rounds to a probability distribution over
> delays, I wonder if we can generalise from a fixed set of interesting
> messages to a probability of being interesting.
> 
> So in a system that uses dummy traffic, when I see Alice sending a
> message in

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[dawuud]

Hello grarpamp,

replying inline.

On Sat, Nov 25, 2017 at 03:57:41PM -0500, grarpamp wrote:
> Dummy / decoy / fill / chaff traffic itself alone seems insufficient.

Insufficient for what purpose? I listed three in my previous e-mail for
which it is most definitely sufficient. Again that is:

1. detection of n-1 attacks
(if unclear on this point see:
   [HEARTBEAT03]  Danezis, G., Sassaman, L., "Heartbeat Traffic to Counter 
(n-1) Attacks",
  Proceedings of the Workshop on Privacy in the Electronic 
Society, October 2003,
  
.
)

2. decrease needed latency for desired mix entropy
(if unclear on this point see:
   [LOOPIX]Piotrowska, A., Hayes, J., Elahi, T., Meiser, S., Danezis, G.,
   “The Loopix Anonymity System”,
   USENIX, August, 2017
   
)

3. prevent short term statistical disclosure attacks
(see many papers listed below)

> If a global passive adversary GPA can inject their own

First of all, global passive adversary don't inject anything because
they are passive. Passive means not sending anything!

Why even mention GPA? Are we still talking about statistical
disclosure attacks?  If so then, let it be known: "GPA not needed. a
weaker adversary will do".  The adversary must be able to watch two
parts of the network, the input and the output; this is much less than
global.

> traffic pattern into the net, and recognize it at some other
> useful vantage point, such as an exit or "hidden" destination,
> or intermediate hop towards a full disclosure... including if the
> pattern is being sent to or between you... they can surely
> do the same with whatever traffic a user pushes. Wherein

they can surely do what precisely?

> the users fill traffic may not be subject to the same influence
> or channel parameters as the users real data traffic.

what? no. decoy traffic is indistinguishable from legit traffic.
that's the whole point.

> Parhaps was talked with Briar / others on cryptography list,
> what would GPA proof Ethernet wire look like?

Again with the GPA. I don't understand what you mean here or why
the mention of a GPA is needed to make your point.

> The link level point to point p2p encrypted line / channel would

Do you mean link layer? We don't use link layer padding.

> be full 100% of the time, packet size outside attacker control,

Why?

> with fill traffic yielding for data traffic, with detection if it was ever
> not full or crypto failed (obviously includes received traffic suffered
> delays or missing packets), and all data traffic received from elsewhere
> for transport over such a line must be reclocked for insertion into the line
> to clean any timing / size / data perturbations received.
> It may be impossible to time or correlate a 100% full clocked bucket line,
> or network that uses the same principle.

I don't even understand a little of what you are saying here.

> The more strayed away towards looser more general more unchecked
> constraint upon random fill and the traffic channel, and the less network
> wide, perhaps the less benefit it is.

What do you mean by this?

> The lines may not need to be full, but they seem to must need
> to be fully parameterized, cleaned, checked and enforced.

I also do not understand this statement.

> These are only a few lines of thought among many out there.

Um ok.

> Is there a subset list of research papers being curated
> somewhere that deal specifically with these sorts of traffic
> issues (anti-GPA / fill / decoy / whatever)?

Currently our specifications do not *yet* include anything about decoy traffic:

https://github.com/Katzenpost/docs/tree/master/specs

I did previously post a few links to papers on the subject of
statistical disclosure attacks. I will be citing them as references
in our future decoy traffic specification. Here's a more complete list:


 [POOLDUMMY]  Diaz, C., Preneel, B.,
  "Reasoning about the Anonymity Provided by Pool Mixes that 
Generate Dummy Traffic",
  .

  [MIXDUMMY]  Diaz, C., Preneel, B.,
  "Taxonomy of Mixes and Dummy Traffic",
  .

   [DUMMYLIMITS]  Oya, S., Troncoso, C., Pérez-González, F.
  "Do dummies pay off? Limits of dummy traffic protection in 
anonymous communications",
  
.

 [DUMMYINTERSECTION] Berthold, O., Langos, H.,
 "Dummy Traffic Against Long Term Intersection Attacks",
 In the Proceedings of the PETS 2002,
 .

 [HANGBUDDIES]  Wolinksy, D., Syta, E., Ford, B.,
"Hang with Your Buddies to Resist Intersect

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[grarpamp]

Dummy / decoy / fill / chaff traffic itself alone seems insufficient.
If a global passive adversary GPA can inject their own
traffic pattern into the net, and recognize it at some other
useful vantage point, such as an exit or "hidden" destination,
or intermediate hop towards a full disclosure... including if the
pattern is being sent to or between you... they can surely
do the same with whatever traffic a user pushes. Wherein
the users fill traffic may not be subject to the same influence
or channel parameters as the users real data traffic.

Parhaps was talked with Briar / others on cryptography list,
what would GPA proof Ethernet wire look like?
The link level point to point p2p encrypted line / channel would
be full 100% of the time, packet size outside attacker control,
with fill traffic yielding for data traffic, with detection if it was ever
not full or crypto failed (obviously includes received traffic suffered
delays or missing packets), and all data traffic received from elsewhere
for transport over such a line must be reclocked for insertion into the line
to clean any timing / size / data perturbations received.
It may be impossible to time or correlate a 100% full clocked bucket line,
or network that uses the same principle.

The more strayed away towards looser more general more unchecked
constraint upon random fill and the traffic channel, and the less network
wide, perhaps the less benefit it is.

The lines may not need to be full, but they seem to must need
to be fully parameterized, cleaned, checked and enforced.

These are only a few lines of thought among many out there.

Is there a subset list of research papers being curated
somewhere that deal specifically with these sorts of traffic
issues (anti-GPA / fill / decoy / whatever)?


> zcash transactions: from client to blockchain.

For a "privacy" coin, it's counter productive that almost
all coins still don't support TLS, bootstrapping and full use
entirely within overlay networks, etc. The first I know of to
begin making those leaps is Zencash...
https://zensystem.io/
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[dawuud]

Hi Michael,

Thank you for your thoughtful e-mail. I think you are correct... longterm
statistical disclosure cannot be prevented, only delayed or made more
difficult given that users do at times disconnect from the network.
(unrealistic constraints are unrealistic)

That having been said, I think we need to get clear on exactly
how this attack will work for systems like Loopix/Katzenpost
because the literature is describing very different mixnet systems
that are more like peer to peer systems.

There are a couple of points that you didn't mention that
I would like to raise below.

But before diving in... say we were to use a mix network to transport
zcash transactions: from client to blockchain. For this case it's hard
for me to imagine how this attack would work. I mean... there is no receiver
of the message. The zcash blockchain is the receiver.

> Yes, I think the attack would still be possible given a probability
> distribution over delays instead of a fixed delay.
> 
> My starting point here is the statistical disclosure attack
> (https://www.freehaven.net/anonbib/cache/statistical-disclosure.pdf),
> which says that if I'm watching the inputs and outputs of a round-based
> anonymity system, and I see Alice sending messages into the system, and
> for each round where Alice sends a message I see all the messages
> exiting the system, then starting from a uniform probability

In this case, exiting the system means a message travels from the last
mix hop to the destination Provider where the message is
queued. Later, anytime later, the recipient client can retrieve the
message from their "mailbox" on the Provider.

> distribution over all possible recipients I can refine that distribution
> with every observation, to eventually discover Alice's communication
> partners. The longer I watch the system, the closer my distribution gets
> to Alice's real distribution.

Yes but how to discover the set of suspect recipients?
The passive adversary watches to see who connects to the recipient Provider
to receive messages from their mailbox. However it is unclear to me
how the adversary is able to reduce the suspect set size.

> I think we can generalise that by replacing the rounds with a
> probability distribution over delays. So for each message Alice sends
> into the system, instead of having a set of output messages that
> definitely belong to the same round, I assign every future output
> message a probability of being Alice's message based on the delay. But

Yes that sounds correct... but we are still missing the output side
of the attack in this explaination.

> the rest of the attack remains the same: I use the probabilities
> assigned to output messages to update the probability distribution over
> possible recipients, and over time that distribution approaches Alice's
> real distribution.

I should point out that when the Katzenpost design is upgraded to use
decoy traffic the way the Loopix paper describes, the client would
also receive decoy messages from the Provider when retrieving
messages. That is, all clients would receive the same amount of
"stuff" when polling the Provider for queued messages.

> Of course the Loopix authors know this, hence all the dummy traffic to
> prevent an attacker from knowing which users are actually sending and
> receiving messages. I think the big question is whether that provides a
> useful amount of protection at a reasonable level of overhead.
> 
> > I also cannot think of a way that "d" is met... unless of course there
> > is collusion with the destination Provider.
> 
> If I understand right, condition d just means there must be some set of
> messages you're interested in, and you must know which messages they are.
> 
> In the statistical disclosure paper, the session is all messages sent by
> Alice and the goal is to identify the set of recipients. In the Berthold
> and Langos paper it's the other way round - the session is all messages
> sent by some unknown sender and the goal is to identify the sender. But
> either way, there's some set of interesting messages and the goal is to
> separate them from the uninteresting messages.
> 
> Just as we can generalise from rounds to a probability distribution over
> delays, I wonder if we can generalise from a fixed set of interesting
> messages to a probability of being interesting.
> 
> So in a system that uses dummy traffic, when I see Alice sending a
> message into the system, I assign it a probability of being a real
> message. Then I assign every future output message a probability of
> being the same message based on the delay. And I update the recipient's
> probability of being one of Alice's communication partners based on the
> product of those two probabilities.

I see what you mean AND I think the Client to Provider decoy traffic as I
described above would make this a lot more difficult. I don't yet fully
understand how this attack would work because I don't see a way to reduce
the set of suspect output mess

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[Michael Rogers]

On 21/11/17 02:12, dawuud wrote:
> Katzenpost is delivery by pull as well. Clients retreive messages from their 
> Provider.
> This paper:
> 
>  [DUMMYINTERSECTION] Berthold, O., Langos, H.,
>  "Dummy Traffic Against Long Term Intersection Attacks",
>  In the Proceedings of the PETS 2002,
>  .
> 
> mentions that there are some constraints needed for the intersection attack 
> to work:
> 
> a. the adversary is able to watch all user lines
> b. the adversary is able to watch all Provider/server lines (see figure 1 in 
> paper)
> c. the adversary knows how long it takes for a message to traverse the mix 
> network
> d. messages belonging to a certain session have to have the same property
>that allows the adversary to link them each together
> 
> So in Katzenpost I don't think constraint "c" is met since we aren't using
> synchronized batch mixing... but rather the Poisson mix strategy where
> clients select the mix delay for each hop in the route which should be 
> different
> for every sent message, even retransmits... although client route hop delays 
> are sampled
> from an exponential distribution. The attacker can of course compute the
> probability of a certain route delay having been choosen by a client.

Yes, I think the attack would still be possible given a probability
distribution over delays instead of a fixed delay.

My starting point here is the statistical disclosure attack
(https://www.freehaven.net/anonbib/cache/statistical-disclosure.pdf),
which says that if I'm watching the inputs and outputs of a round-based
anonymity system, and I see Alice sending messages into the system, and
for each round where Alice sends a message I see all the messages
exiting the system, then starting from a uniform probability
distribution over all possible recipients I can refine that distribution
with every observation, to eventually discover Alice's communication
partners. The longer I watch the system, the closer my distribution gets
to Alice's real distribution.

I think we can generalise that by replacing the rounds with a
probability distribution over delays. So for each message Alice sends
into the system, instead of having a set of output messages that
definitely belong to the same round, I assign every future output
message a probability of being Alice's message based on the delay. But
the rest of the attack remains the same: I use the probabilities
assigned to output messages to update the probability distribution over
possible recipients, and over time that distribution approaches Alice's
real distribution.

Of course the Loopix authors know this, hence all the dummy traffic to
prevent an attacker from knowing which users are actually sending and
receiving messages. I think the big question is whether that provides a
useful amount of protection at a reasonable level of overhead.

> I also cannot think of a way that "d" is met... unless of course there
> is collusion with the destination Provider.

If I understand right, condition d just means there must be some set of
messages you're interested in, and you must know which messages they are.

In the statistical disclosure paper, the session is all messages sent by
Alice and the goal is to identify the set of recipients. In the Berthold
and Langos paper it's the other way round - the session is all messages
sent by some unknown sender and the goal is to identify the sender. But
either way, there's some set of interesting messages and the goal is to
separate them from the uninteresting messages.

Just as we can generalise from rounds to a probability distribution over
delays, I wonder if we can generalise from a fixed set of interesting
messages to a probability of being interesting.

So in a system that uses dummy traffic, when I see Alice sending a
message into the system, I assign it a probability of being a real
message. Then I assign every future output message a probability of
being the same message based on the delay. And I update the recipient's
probability of being one of Alice's communication partners based on the
product of those two probabilities.

In theory the attack still works, but my distribution converges more
slowly. On the other hand, the system is also more expensive to use. So
it comes down to a practical question: how long can the system conceal
sender-recipient relationships, at what cost in dummy traffic?

I'd love to see some back-of-an-envelope calculations of this for
Katzenpost. If Alice sends and receives n dummy bytes for each real
byte, what does that do to the attacker's probability distribution over
possible communication partners? How much longer does it take the
attacker's distribution to converge?

Cheers,
Michael


0x9FC527CC.asc
Description: application/pgp-keys


signature.asc
Description: OpenPGP digital signature
___
Messaging mailing list
Messaging@mod

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[dawuud]

> Can you explain that in some more detail? I don't see how it automatically 
> follows that, any attack that works on a typical deliver-by-push mixnet also 
> works with equal probability on a deliver-by-pull ("store-and-retrieve") 
> network - which is what you seem to be implying.

Yes, I think I was wrong about that...

Katzenpost is delivery by pull as well. Clients retreive messages from their 
Provider.
This paper:

 [DUMMYINTERSECTION] Berthold, O., Langos, H.,
 "Dummy Traffic Against Long Term Intersection Attacks",
 In the Proceedings of the PETS 2002,
 .

mentions that there are some constraints needed for the intersection attack to 
work:

a. the adversary is able to watch all user lines
b. the adversary is able to watch all Provider/server lines (see figure 1 in 
paper)
c. the adversary knows how long it takes for a message to traverse the mix 
network
d. messages belonging to a certain session have to have the same property
   that allows the adversary to link them each together

So in Katzenpost I don't think constraint "c" is met since we aren't using
synchronized batch mixing... but rather the Poisson mix strategy where
clients select the mix delay for each hop in the route which should be different
for every sent message, even retransmits... although client route hop delays 
are sampled
from an exponential distribution. The attacker can of course compute the
probability of a certain route delay having been choosen by a client.

I also cannot think of a way that "d" is met... unless of course there
is collusion with the destination Provider.

> For example, in a deliver-by-push network, an attacker knows roughly how long 
> a message is expected to take to cross the network, and this is the same for 
> everyone. In a deliver-by-pull network, different users may retrieve their 
> messages at different times and so the attacker no longer has this power. Or, 
> they can attempt to infer it but (a) it will be different for each message 
> and (b) they have less confidence in their results.

In Katzenpost, users retrieve their messages directly from their own
Provider and do not use the mix network when retrieving queued
messages. Although the Provider always sends the same amount of stuff
to the client... so that interaction cannot be used to discover is a
client has actually retrieved a message. Although the adversary could
attempt to link messages delivered to the destination Provider with
messages sent by online clients. Further, and then discover all the
clients that download messages from that Provider are in the set of
suspect recipient clients. That's as far as I can imagine this attack going...
but then I haven't read all the papers on the subject yet.

> One might even be able to do tricks like, to retrieve a message of size X you 
> have to send a request of size X. That might make it harder for an attacker 
> to distinguish between senders and recipients.

All katzenpost messages are padded to the same size and we have a
fragmentation scheme for messages larger than this.

> > Yeah that sounds good... although having client to client ACKs means they 
> > both have
> > to be online at the same time which is a constraint that is probably 
> > inconvenient
> > unless it's treated like a real-time chat application.

> They don't have to be online at exactly the same time, the application can 
> choose what time interval the ACKs are expected to arrive within. Depending 
> on the application this could be a few minutes to a few days. It's also 
> conceivable to adjust this timeout based on application-specific information.

Yes that's true. Maybe we'll add the end to end ACKs later.

> Of course, I agree that ACKs that are sent too predictably, will give more 
> information to an attacker.

Yes and if the adversary causes an ACK to get dropped or delayed then
this results in a retransmission from the sending client. Although
this shouldn't be a problem since clients send stuff at a constant
rate (unless we implement source squelch to try and prevent congestion
collapse).

> >> Wasn't Jeff Burdges exploring designs in this area at some point? I 
> >> vaguely remember him talking about it at various events a few years ago.
> > 
> > Yeah Jeff Burdges has been doing some very interesting mixnet research.
> > Some of his designs are here:
> > 
> > [..]
> 
> Thanks for the links, will have to be another day when I go through them 
> properly.
> 
> X
> 
> -- 
> GPG: ed25519/56034877E1F87C35
> GPG: rsa4096/1318EFAC5FBBDBCE
> https://github.com/infinity0/pubkeys.git


signature.asc
Description: PGP signature
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[Ximin Luo]

dawuud:
> 
>>> If my understanding is correct, the answer is No. No we cannot prevent
>>> longterm intersection attacks by using decoy traffic in the
>>> katzenpost/loopix system because users will go offline and come back
>>> online later which changes the anonymity set size and thus leaks
>>> information to a global network observer.
>>>
>>> I suspect that there are mixnet use cases which are not vulnerable or
>>> less vulnerable to this... such that user or application behavior does not
>>> form a "session" where users send multiple messages over long periods which
>>> can be linked by a passive observer.
>>>
>>
>> What about a store-and-retrieve design? You don't send "to" the receiver 
>> (not even indirectly), you send to a mailbox at an unpredictable address (or 
>> addresses) in a DHT-like distributed storage system, which is always online. 
>> Later, the receiver logs on and retrieves their own messages from their 
>> mailbox.
> 
> (none of that prevents longterm intersection attacks)
> 

Can you explain that in some more detail? I don't see how it automatically 
follows that, any attack that works on a typical deliver-by-push mixnet also 
works with equal probability on a deliver-by-pull ("store-and-retrieve") 
network - which is what you seem to be implying.

For example, in a deliver-by-push network, an attacker knows roughly how long a 
message is expected to take to cross the network, and this is the same for 
everyone. In a deliver-by-pull network, different users may retrieve their 
messages at different times and so the attacker no longer has this power. Or, 
they can attempt to infer it but (a) it will be different for each message and 
(b) they have less confidence in their results.

One might even be able to do tricks like, to retrieve a message of size X you 
have to send a request of size X. That might make it harder for an attacker to 
distinguish between senders and recipients.

> oh yes i love these ideas... and i was previously discussing them with
> str4d in the context of i2p bote mail which is described here:
> 
> https://github.com/i2p/i2p.i2p-bote/blob/master/doc/techdoc.txt
> 
> This spec is a bit encumbered by crypto packet format details whereas
> I would just use Sphinx.
> 
>> Storage nodes only store stuff for a fixed amount of time and then they drop 
>> it, to save space / prevent storage DoS attacks. Participants rely on 
>> end-to-end acks to guarantee reliability. If the recipient doesn't ack your 
>> message, you assume the network dropped it, and resend it, perhaps to a 
>> newly-generated unpredictable address.
> 
> Yeah that sounds good... although having client to client ACKs means they 
> both have
> to be online at the same time which is a constraint that is probably 
> inconvenient
> unless it's treated like a real-time chat application.
> 
> I like that this prevents some storage DoS attacks.
> 

They don't have to be online at exactly the same time, the application can 
choose what time interval the ACKs are expected to arrive within. Depending on 
the application this could be a few minutes to a few days. It's also 
conceivable to adjust this timeout based on application-specific information.

Of course, I agree that ACKs that are sent too predictably, will give more 
information to an attacker.

>> Wasn't Jeff Burdges exploring designs in this area at some point? I vaguely 
>> remember him talking about it at various events a few years ago.
> 
> Yeah Jeff Burdges has been doing some very interesting mixnet research.
> Some of his designs are here:
> 
> [..]

Thanks for the links, will have to be another day when I go through them 
properly.

X

-- 
GPG: ed25519/56034877E1F87C35
GPG: rsa4096/1318EFAC5FBBDBCE
https://github.com/infinity0/pubkeys.git
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[dawuud]

> > If my understanding is correct, the answer is No. No we cannot prevent
> > longterm intersection attacks by using decoy traffic in the
> > katzenpost/loopix system because users will go offline and come back
> > online later which changes the anonymity set size and thus leaks
> > information to a global network observer.
> > 
> > I suspect that there are mixnet use cases which are not vulnerable or
> > less vulnerable to this... such that user or application behavior does not
> > form a "session" where users send multiple messages over long periods which
> > can be linked by a passive observer.
> > 
> 
> What about a store-and-retrieve design? You don't send "to" the receiver (not 
> even indirectly), you send to a mailbox at an unpredictable address (or 
> addresses) in a DHT-like distributed storage system, which is always online. 
> Later, the receiver logs on and retrieves their own messages from their 
> mailbox.

(none of that prevents longterm intersection attacks)

oh yes i love these ideas... and i was previously discussing them with
str4d in the context of i2p bote mail which is described here:

https://github.com/i2p/i2p.i2p-bote/blob/master/doc/techdoc.txt

This spec is a bit encumbered by crypto packet format details whereas
I would just use Sphinx.

> Storage nodes only store stuff for a fixed amount of time and then they drop 
> it, to save space / prevent storage DoS attacks. Participants rely on 
> end-to-end acks to guarantee reliability. If the recipient doesn't ack your 
> message, you assume the network dropped it, and resend it, perhaps to a 
> newly-generated unpredictable address.

Yeah that sounds good... although having client to client ACKs means they both 
have
to be online at the same time which is a constraint that is probably 
inconvenient
unless it's treated like a real-time chat application.

I like that this prevents some storage DoS attacks.

> Wasn't Jeff Burdges exploring designs in this area at some point? I vaguely 
> remember him talking about it at various events a few years ago.

Yeah Jeff Burdges has been doing some very interesting mixnet research.
Some of his designs are here:

https://github.com/burdges/lake/tree/master/Xolotl/papers

One of the things he's done is expand on George Danezis's previous work:

Forward Secure Mixes
https://www.freehaven.net/anonbib/cache/Dan:SFMix03.pdf

Jeff has got a PQ ratchet design for forward secure mixes.

He also has a bunch of different designs for mixnet messaging systems
but so far none of them have an ARQ protocol scheme and therefore no 
reliability.
It might be possible to add an ARQ scheme to some of his designs.

In my opinion reliability is super important...
because "hey there's this new messaging app, but if you send a message
it might not make it to it's destination" does not sound appealing to use at 
all.

Also Jeff's designs seem to require SURBs with longish lifetimes whereas
our katzenpost/loopix thing uses SURBs with lifetimes of 3 hours... since
3 hours in our key rotation duration for mix keys. (it's good to have
MLAT aware path selection)

Having SURBs with long lifetimes increases vulnerability to compulsion attacks.
Although it might possibly be somewhat mitigated with the PQ forward secure 
mixes
if the ratchet state changes before "the man" compels the mix operator to give 
them
the private key material.

Which reminds me that there are some cool designs in this paper
that might help mitigate these kinds of attacks:

Compulsion Resistant Anonymous Communications
https://www.freehaven.net/anonbib/cache/ih05-danezisclulow.pdf


cheers,
David


signature.asc
Description: PGP signature
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[Ximin Luo]

dawuud:
> 
>> I wonder, in general can we have nice things? Can we finally have a
>> cryptographic messaging system that protects against intersection
>> attacks? To that end I've been putting together a reading list so that
> 
> If my understanding is correct, the answer is No. No we cannot prevent
> longterm intersection attacks by using decoy traffic in the
> katzenpost/loopix system because users will go offline and come back
> online later which changes the anonymity set size and thus leaks
> information to a global network observer.
> 
> I suspect that there are mixnet use cases which are not vulnerable or
> less vulnerable to this... such that user or application behavior does not
> form a "session" where users send multiple messages over long periods which
> can be linked by a passive observer.
> 

What about a store-and-retrieve design? You don't send "to" the receiver (not 
even indirectly), you send to a mailbox at an unpredictable address (or 
addresses) in a DHT-like distributed storage system, which is always online. 
Later, the receiver logs on and retrieves their own messages from their mailbox.

Storage nodes only store stuff for a fixed amount of time and then they drop 
it, to save space / prevent storage DoS attacks. Participants rely on 
end-to-end acks to guarantee reliability. If the recipient doesn't ack your 
message, you assume the network dropped it, and resend it, perhaps to a 
newly-generated unpredictable address.

Wasn't Jeff Burdges exploring designs in this area at some point? I vaguely 
remember him talking about it at various events a few years ago.

X

-- 
GPG: ed25519/56034877E1F87C35
GPG: rsa4096/1318EFAC5FBBDBCE
https://github.com/infinity0/pubkeys.git
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[dawuud]

german news article about panoramix and autocrypt/nextleap

http://fm4.orf.at/stories/2877814/


On Tue, Nov 14, 2017 at 04:10:25PM +, dawuud wrote:
> 
> > I wonder, in general can we have nice things? Can we finally have a
> > cryptographic messaging system that protects against intersection
> > attacks? To that end I've been putting together a reading list so that
> 
> If my understanding is correct, the answer is No. No we cannot prevent
> longterm intersection attacks by using decoy traffic in the
> katzenpost/loopix system because users will go offline and come back
> online later which changes the anonymity set size and thus leaks
> information to a global network observer.
> 
> I suspect that there are mixnet use cases which are not vulnerable or
> less vulnerable to this... such that user or application behavior does not
> form a "session" where users send multiple messages over long periods which
> can be linked by a passive observer.



> ___
> Messaging mailing list
> Messaging@moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/messaging



signature.asc
Description: PGP signature
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[dawuud]

> I wonder, in general can we have nice things? Can we finally have a
> cryptographic messaging system that protects against intersection
> attacks? To that end I've been putting together a reading list so that

If my understanding is correct, the answer is No. No we cannot prevent
longterm intersection attacks by using decoy traffic in the
katzenpost/loopix system because users will go offline and come back
online later which changes the anonymity set size and thus leaks
information to a global network observer.

I suspect that there are mixnet use cases which are not vulnerable or
less vulnerable to this... such that user or application behavior does not
form a "session" where users send multiple messages over long periods which
can be linked by a passive observer.


signature.asc
Description: PGP signature
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[dawuud]

OK... I've added three more papers to the references section of the
mixnet directory authority rough draft specification:

   [FINGERPRINTING] "Route Finger printing in Anonymous Communications",
.

   [BRIDGING] Danezis, G., Syverson, P.,
  "Bridging and Fingerprinting: Epistemic Attacks on Route 
Selection",
  In the Proceedings of PETS 2008, Leuven, Belgium, July 2008,
  .

   [LOCALVIEW] Gogolewski, M., Klonowski, M., Kutylowsky, M.,
   "Local View Attack on Anonymous Communication",
   
.

The whole point of this project is "traffic analysis resistance".
I wonder, in general can we have nice things? Can we finally have a
cryptographic messaging system that protects against intersection
attacks? To that end I've been putting together a reading list so that
I can better understand how to write our decoy traffic specification.

// decoy traffic defenses

 [POOLDUMMY]  Diaz, C., Preneel, B.,
  "Reasoning about the Anonymity Provided by Pool Mixes that 
Generate Dummy Traffic",
  .

  [MIXDUMMY]  Diaz, C., Preneel, B.,
  "Taxonomy of Mixes and Dummy Traffic",
  .

   [DUMMYLIMITS]  Oya, S., Troncoso, C., Pérez-González, F.
  "Do dummies pay off? Limits of dummy traffic protection in 
anonymous communications",
  
.

  Berthold, O., Langos, H.,
  "Dummy Traffic Against Long Term Intersection Attacks",
  In the Proceedings of the PETS 2002,
  .

// alternate defenses

Wolinksy, D., Syta, E., Ford, B.,
"Hang with Your Buddies to Resist Intersection Attacks",
In the Proceedings of the 20th ACM conference on CCS November 
2013,
.

// attacks

[STATSDISCO]  Danezis, G., Serjantov, A.,
  "Statistical Disclosure or Intersection Attacks on Anonymity 
Systems",
  In the Proceedings of 6th Information Hiding Workshop (IH 
2004), Toronto, May 2004.
  .

  Danezis, G., Diaz, C., Troncoso, C.,
  "Two-sided Statistical Disclosure Attack",
  In the Proceedings of the PETS 2007,
  .

  Troncoso, C., Gierlichs, B., Preneel, B., Verbauwhede, I.,
  "Perfect Matching Disclosure Attacks",
  In the Proceedings of the PETS 2008,
  
.

  Perez-Gonzalez, F., Troncoso, C.,
  "Understanding Statistical Disclosure: A Least Squares 
approach",
  In the Proceedings of the PETS 2012,
  
.



On Fri, Nov 10, 2017 at 07:28:00PM +, Ximin Luo wrote:
> Michael Rogers:
> > On 10/11/17 14:31, Ximin Luo wrote:
> >>> So if we're asking whether a system may be vulnerable to the attack, and
> >>> it has the properties above, then we need to ask whether the system is
> >>> doing something to produce that countervailing tendency. In other words,
> >>> is it actively preventing the attack?
> >>>
> >>
> >> Indeed, I noted that the specific simple attack "assumes that nodes are 
> >> unable 
> >> to use any other information to distinguish between faulty vs good 
> >> neighbours.
> >>
> >> There are various things you can do along those lines, and the paper you 
> >> linked 
> >> includes a defense that based on their analysis is moderately effective. 
> >> I'm 
> >> sure there are improvements to be made though.
> > 
> > Absolutely. I'm not saying the eclipse attack rules out decentralised
> > solutions. I'm saying any decentralised solution needs to specify how
> > it's going to prevent the attack.
> > 
> > If you think that's trivial, take a look at MorphMix and the attacks
> > against it, and the papers from 2006-2010 that tried to do anonymous
> > routing over P2P networks, or use P2P networks to replace the Tor
> > directory system. I think most of them are cited by these two papers:
> > 
> > https://www.princeton.edu/~pmittal/publications/information-leaks-ccs08.pdf
> > 
> > http://www.usenix.net/legacy/events/hotsec10/tech/full_papers/Mittal.pdf
> > 
> > Again, I'm not saying it's impossible and w

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[Ximin Luo]

Michael Rogers:
> On 10/11/17 14:31, Ximin Luo wrote:
>>> So if we're asking whether a system may be vulnerable to the attack, and
>>> it has the properties above, then we need to ask whether the system is
>>> doing something to produce that countervailing tendency. In other words,
>>> is it actively preventing the attack?
>>>
>>
>> Indeed, I noted that the specific simple attack "assumes that nodes are 
>> unable 
>> to use any other information to distinguish between faulty vs good 
>> neighbours.
>>
>> There are various things you can do along those lines, and the paper you 
>> linked 
>> includes a defense that based on their analysis is moderately effective. I'm 
>> sure there are improvements to be made though.
> 
> Absolutely. I'm not saying the eclipse attack rules out decentralised
> solutions. I'm saying any decentralised solution needs to specify how
> it's going to prevent the attack.
> 
> If you think that's trivial, take a look at MorphMix and the attacks
> against it, and the papers from 2006-2010 that tried to do anonymous
> routing over P2P networks, or use P2P networks to replace the Tor
> directory system. I think most of them are cited by these two papers:
> 
> https://www.princeton.edu/~pmittal/publications/information-leaks-ccs08.pdf
> 
> http://www.usenix.net/legacy/events/hotsec10/tech/full_papers/Mittal.pdf
> 
> Again, I'm not saying it's impossible and we should all go home, but
> it's definitely not a problem to be dismissed out of hand.
> 

I'm not suggesting that it's trivial, but rather than I haven't been too 
impressed with the examples and counterexamples cited so far as supposed 
arguments against decentralised networks in general - not just from this 
thread, but from other researchers as well. That's not meant to be taken 
personally, it's just my view of the topic as a whole.

The collusion detection of MorphMix does not seem *particularly* advanced to 
me, so I'm not surprised that an adversarial approach could break it. What 
would be interesting would be to see papers that try to tackle the problem from 
an adversarial point of view, including self-awareness about the flaws in their 
own defense. That might eventually lead to more general theories about the 
security and performance of decentralised networks, something that I haven't 
seen much of yet. Some of the later stuff about community detection was quite 
interesting, which is why I mentioned it earlier.

More generally, I can understand that this topic is a rabbit hole if all you 
want to do is "just build an anonymous messaging system" - you have to know 
much more about decentralised systems, etc. So if one's funding is limited 
specifically to "build an anonymous messaging system" I can understand why 
one's preference would be for centralised directory authorities. But I see the 
development of decentralised systems as a wider goal that can have much greater 
and wider benefits beyond just building anonymous messaging systems, so that's 
why I maintain this interest in it.

Thanks for the papers though, will be interesting to give them a read through 
in more detail.

 Going back to the original issue (epistemic attacks against mixnets), the 
 key
 point AFAIU is to ensure that n ~= N. Whether this is achieved in a 
 centralised
 or decentralised way seems immaterial to me.
>>>
>>> The question isn't really the size of the view, but how much overlap
>>> there is between the views of different users. Even if a user has some
>>> way to know the value of N in a decentralised system (which is a hard
>>> problem in its own right), how does she know whether the n ~= N nodes in
>>> her own view are also in other users' views?
>>>
>>
>> If n ~= N then the overlaps are much closer and you can follow the maths in 
>> the 
>> rest of the paper to see that the attack probabilities drop to very low.
> 
> That's fine for analysing the system from outside, where the set of N
> nodes can be objectively known. But a user of the system doesn't have
> that objective knowledge. She has a view of n nodes, but she doesn't
> know N, so she can't tell to what extent her view overlaps with those of
> other users. This isn't just an issue of user confidence, it's also a
> practical problem: how does she know when she's learned about enough
> nodes to start communicating?
> 

I agree but I think this is a "given" if one was working in this area - i.e. a 
system that claims to "guarantee n ~= N" would include the ability for each 
participant know that that with high probability, that's what "guarantee" 
means. If this wasn't met then the work would be a bad piece of work.

> Going back to the wider issue of epistemic attacks on anonymity systems,
> it may not even be necessary for a user's view to differ much from those
> of other users. For example, if the attacker can add a single node to a
> victim's view that's not in any other user's view, then any traffic
> passing through that node must come from the vict

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[Michael Rogers]

On 10/11/17 14:31, Ximin Luo wrote:
>> So if we're asking whether a system may be vulnerable to the attack, and
>> it has the properties above, then we need to ask whether the system is
>> doing something to produce that countervailing tendency. In other words,
>> is it actively preventing the attack?
>>
> 
> Indeed, I noted that the specific simple attack "assumes that nodes are 
> unable 
> to use any other information to distinguish between faulty vs good neighbours.
> 
> There are various things you can do along those lines, and the paper you 
> linked 
> includes a defense that based on their analysis is moderately effective. I'm 
> sure there are improvements to be made though.

Absolutely. I'm not saying the eclipse attack rules out decentralised
solutions. I'm saying any decentralised solution needs to specify how
it's going to prevent the attack.

If you think that's trivial, take a look at MorphMix and the attacks
against it, and the papers from 2006-2010 that tried to do anonymous
routing over P2P networks, or use P2P networks to replace the Tor
directory system. I think most of them are cited by these two papers:

https://www.princeton.edu/~pmittal/publications/information-leaks-ccs08.pdf

http://www.usenix.net/legacy/events/hotsec10/tech/full_papers/Mittal.pdf

Again, I'm not saying it's impossible and we should all go home, but
it's definitely not a problem to be dismissed out of hand.

>>> Going back to the original issue (epistemic attacks against mixnets), the 
>>> key
>>> point AFAIU is to ensure that n ~= N. Whether this is achieved in a 
>>> centralised
>>> or decentralised way seems immaterial to me.
>>
>> The question isn't really the size of the view, but how much overlap
>> there is between the views of different users. Even if a user has some
>> way to know the value of N in a decentralised system (which is a hard
>> problem in its own right), how does she know whether the n ~= N nodes in
>> her own view are also in other users' views?
>>
> 
> If n ~= N then the overlaps are much closer and you can follow the maths in 
> the 
> rest of the paper to see that the attack probabilities drop to very low.

That's fine for analysing the system from outside, where the set of N
nodes can be objectively known. But a user of the system doesn't have
that objective knowledge. She has a view of n nodes, but she doesn't
know N, so she can't tell to what extent her view overlaps with those of
other users. This isn't just an issue of user confidence, it's also a
practical problem: how does she know when she's learned about enough
nodes to start communicating?

Going back to the wider issue of epistemic attacks on anonymity systems,
it may not even be necessary for a user's view to differ much from those
of other users. For example, if the attacker can add a single node to a
victim's view that's not in any other user's view, then any traffic
passing through that node must come from the victim. So even n = N for
the victim, and n = N-1 for all other users, doesn't ensure safety.

>> I'm not interested in writing off decentralised systems any more than
>> you are, but there's a burden of proof here. Given the existence of a
>> pretty broad class of attacks that only apply to decentralised systems,
>> a decentralised system needs to show it's not vulnerable to those attacks.
>>
> 
> The attacks only work if the decentralised system literally makes no effort to
> defend itself.

That would only be true if every effort was effective. Look at MorphMix,
for example. It had a clever defence to prevent an eclipse-like attack,
but the defence was defeated by modelling its internal state.

Cheers,
Michael


0x9FC527CC.asc
Description: application/pgp-keys


signature.asc
Description: OpenPGP digital signature
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[Ximin Luo]

Michael Rogers:
> On 06/11/17 13:29, Ximin Luo wrote:
>> https://www.cs.rice.edu/~dwallach/pub/osdi2002.pdf
>>
>> This paper's description of the eclipse attack is as follows:
>>
>> "More precisely, routing updates from correct nodes point to a faulty node 
>> with
>> probability at least f whereas this probability can be as high as one for
>> routing updates from faulty nodes. Correct nodes receive updates from other
>> correct nodes with probability at most 1 − f and from faulty nodes with
>> probability at least f. Therefore, the probability that a routing table entry
>> is faulty after an update is at least (1 − f) × f + f × 1, which is greater
>> than f. This effect cascades with each subsequent update, causing the 
>> fraction
>> of faulty entries to tend towards one."
>>
>> This argument assumes that nodes have a (very) simple algorithm for selecting
>> their neighbours, one that is uniformly random over all offered neighbours. 
>> It
>> assumes that nodes are unable to use any other information to distinguish
>> between faulty vs good neighbours. Indeed, the paper you linked proposes
>> various more sophisticated algorithms to defend against the basic attack.
>>
>> I actually can't think of a selection algorithm that is less sophisticated 
>> than
>> "uniform random" and I think it's a bit unfair (and incorrect) to "write off"
>> all decentralised systems just because the simplest example one can think of,
>> has problems.
> 
> I don't think the attack in general depends on uniform random selection.
> That's just the easiest case to quantify. The attack applies to any
> system with the following properties: [..]
> 
> So if we're asking whether a system may be vulnerable to the attack, and
> it has the properties above, then we need to ask whether the system is
> doing something to produce that countervailing tendency. In other words,
> is it actively preventing the attack?
> 

Indeed, I noted that the specific simple attack "assumes that nodes are unable 
to use any other information to distinguish between faulty vs good neighbours.

There are various things you can do along those lines, and the paper you linked 
includes a defense that based on their analysis is moderately effective. I'm 
sure there are improvements to be made though.

>> Going back to the original issue (epistemic attacks against mixnets), the key
>> point AFAIU is to ensure that n ~= N. Whether this is achieved in a 
>> centralised
>> or decentralised way seems immaterial to me.
> 
> The question isn't really the size of the view, but how much overlap
> there is between the views of different users. Even if a user has some
> way to know the value of N in a decentralised system (which is a hard
> problem in its own right), how does she know whether the n ~= N nodes in
> her own view are also in other users' views?
> 

If n ~= N then the overlaps are much closer and you can follow the maths in the 
rest of the paper to see that the attack probabilities drop to very low.

> [..]
> 
> I'm not interested in writing off decentralised systems any more than
> you are, but there's a burden of proof here. Given the existence of a
> pretty broad class of attacks that only apply to decentralised systems,
> a decentralised system needs to show it's not vulnerable to those attacks.
> 

The attacks only work if the decentralised system literally makes no effort to
defend itself.

X

-- 
GPG: ed25519/56034877E1F87C35
GPG: rsa4096/1318EFAC5FBBDBCE
https://github.com/infinity0/pubkeys.git
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[Michael Rogers]

On 06/11/17 13:29, Ximin Luo wrote:
> https://www.cs.rice.edu/~dwallach/pub/osdi2002.pdf
> 
> This paper's description of the eclipse attack is as follows:
> 
> "More precisely, routing updates from correct nodes point to a faulty node 
> with
> probability at least f whereas this probability can be as high as one for
> routing updates from faulty nodes. Correct nodes receive updates from other
> correct nodes with probability at most 1 − f and from faulty nodes with
> probability at least f. Therefore, the probability that a routing table entry
> is faulty after an update is at least (1 − f) × f + f × 1, which is greater
> than f. This effect cascades with each subsequent update, causing the fraction
> of faulty entries to tend towards one."
> 
> This argument assumes that nodes have a (very) simple algorithm for selecting
> their neighbours, one that is uniformly random over all offered neighbours. It
> assumes that nodes are unable to use any other information to distinguish
> between faulty vs good neighbours. Indeed, the paper you linked proposes
> various more sophisticated algorithms to defend against the basic attack.
> 
> I actually can't think of a selection algorithm that is less sophisticated 
> than
> "uniform random" and I think it's a bit unfair (and incorrect) to "write off"
> all decentralised systems just because the simplest example one can think of,
> has problems.

I don't think the attack in general depends on uniform random selection.
That's just the easiest case to quantify. The attack applies to any
system with the following properties:

* The potential victim discovers nodes by asking some nodes she already
knows about for other nodes they know about
* The potential victim repeats the discovery process, so the outputs of
one discovery round become the inputs to another
* There are some dishonest nodes
* Dishonest nodes are disproportionately likely to return other
dishonest nodes when asked

The attack also applies if we replace "ask" with "tell", i.e. if nodes
proactively gossip.

Under these conditions, the proportion of nodes the victim knows about
that are dishonest will tend to increase with each discovery round,
unless there's some countervailing tendency for honest nodes to return
other honest nodes.

So if we're asking whether a system may be vulnerable to the attack, and
it has the properties above, then we need to ask whether the system is
doing something to produce that countervailing tendency. In other words,
is it actively preventing the attack?

> Going back to the original issue (epistemic attacks against mixnets), the key
> point AFAIU is to ensure that n ~= N. Whether this is achieved in a 
> centralised
> or decentralised way seems immaterial to me.

The question isn't really the size of the view, but how much overlap
there is between the views of different users. Even if a user has some
way to know the value of N in a decentralised system (which is a hard
problem in its own right), how does she know whether the n ~= N nodes in
her own view are also in other users' views?

In a centralised system, only trusted parties are allowed to contribute
to a user's view of the network (we ensure this by checking signatures
on a consensus document, for example). So it's easy to be sure that all
views are substantially the same.

In a decentralised system, untrusted parties can also contribute to a
user's view of the network (by responding to discovery queries, for
example). Clearly this introduces the potential for the view to be
manipulated. How does the system ensure that doesn't happen?

I'm not interested in writing off decentralised systems any more than
you are, but there's a burden of proof here. Given the existence of a
pretty broad class of attacks that only apply to decentralised systems,
a decentralised system needs to show it's not vulnerable to those attacks.

Cheers,
Michael


0x9FC527CC.asc
Description: application/pgp-keys


signature.asc
Description: OpenPGP digital signature
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[Ximin Luo]

Michael Rogers:
> On 01/11/17 01:40, Ximin Luo wrote:
>> After a quick web search on "epistemic attacks", the main paper I can find 
>> [1] has the result that attacks are very strong if each node only knows 
>> about a small fraction (n nodes) of the whole network (N nodes).
>>
>> They lay the motivation for this assumption (n << N), by describing a 
>> discovery-based p2p network where each node "samples" (i.e. directly 
>> contacts) a small fraction of the network. This is equating with mere 
>> "knowledge" of a node, so that the act of "sampling" an attacker-controlled 
>> node, gives them (or a GPA) the ability to know exactly which nodes "know" 
>> the target node.
>>
>> The paper does not seem to consider the possibility that nodes could 
>> discover more of the network without directly sampling every node, e.g. via 
>> gossip with their neighbours on "which other nodes exist".
> 
> The eclipse attack is relevant here. Briefly, if you discover nodes by
> asking each node you know about which other nodes it knows about, an
> attacker who controls some fraction d/n of the nodes can control a
> larger fraction of your view, because honest nodes return a sample with
> d/n dishonest nodes on average, whereas dishonest nodes can return a set
> containing only dishonest nodes.
> 
> If node discovery is ongoing - for example, if you replace nodes in your
> view that have gone offline by discovering more nodes - then the
> attacker can eventually control your whole view.
> 
> (This is from memory and may be inaccurate, it's been a long time since
> I read the paper.)
> 
> https://www.eecs.harvard.edu/~mema/courses/cs264/papers/eclipse-infocom06.pdf
> 

The paper above does not describe a specific eclipse attack, but it does
reference this paper for its definition of "eclipse attack":

https://www.cs.rice.edu/~dwallach/pub/osdi2002.pdf

This paper's description of the eclipse attack is as follows:

"More precisely, routing updates from correct nodes point to a faulty node with
probability at least f whereas this probability can be as high as one for
routing updates from faulty nodes. Correct nodes receive updates from other
correct nodes with probability at most 1 − f and from faulty nodes with
probability at least f. Therefore, the probability that a routing table entry
is faulty after an update is at least (1 − f) × f + f × 1, which is greater
than f. This effect cascades with each subsequent update, causing the fraction
of faulty entries to tend towards one."

This argument assumes that nodes have a (very) simple algorithm for selecting
their neighbours, one that is uniformly random over all offered neighbours. It
assumes that nodes are unable to use any other information to distinguish
between faulty vs good neighbours. Indeed, the paper you linked proposes
various more sophisticated algorithms to defend against the basic attack.

I actually can't think of a selection algorithm that is less sophisticated than
"uniform random" and I think it's a bit unfair (and incorrect) to "write off"
all decentralised systems just because the simplest example one can think of,
has problems.

Going back to the original issue (epistemic attacks against mixnets), the key
point AFAIU is to ensure that n ~= N. Whether this is achieved in a centralised
or decentralised way seems immaterial to me.

X

-- 
GPG: ed25519/56034877E1F87C35
GPG: rsa4096/1318EFAC5FBBDBCE
https://github.com/infinity0/pubkeys.git
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[dawuud]

> Directory authorities perform a different job, so I prefer to not call these 
> also "PKI". "Consensus service" would be less confusing - for me as a 
> security person but not specialised in anonymity research.

Ah yes, I see your point.

> > I've heard that I2p uses a completely different kind of PKI... involving a
> > gossip protocol. I suspect it is highly vulnerable to epistemic attacks 
> > which
> > is supposed to be one of the main reasons to use a design like Nick's.
> > 
> 
> After a quick web search on "epistemic attacks", the main paper I can find 
> [1] has the result that attacks are very strong if each node only knows about 
> a small fraction (n nodes) of the whole network (N nodes).
> 
> They lay the motivation for this assumption (n << N), by describing a 
> discovery-based p2p network where each node "samples" (i.e. directly 
> contacts) a small fraction of the network. This is equating with mere 
> "knowledge" of a node, so that the act of "sampling" an attacker-controlled 
> node, gives them (or a GPA) the ability to know exactly which nodes "know" 
> the target node.
> 
> The paper does not seem to consider the possibility that nodes could discover 
> more of the network without directly sampling every node, e.g. via gossip 
> with their neighbours on "which other nodes exist".
> 
> This does not invalidate the mathematics nor the proofs, but it does 
> invalidate the assumption that n << N, that is required to make the attacks 
> be practical. So if I2P has some convincing argument that n ~= N for their 
> gossip system, then AFAIU they can claim a reasonable level of defense 
> against the attack(s) described in this particular paper.
> 
> Furthermore, the assumption that nodes must "sample" other nodes in order to 
> "know" them, is required for some of the mentioned attacks to work, e.g. in 
> 3.1 "The adversary need only know the knowledge set of the target S0 for the 
> lower bound we have stated to hold". This assumption would also be false for 
> systems that involve indirect discovery. (A modified attack could still work, 
> by attempting to infer the knowledge-set of S0, but I assume it would cost 
> more and be less effective, especially if n ~= N).
> 
> (Indirect discovery could arguably be said to make it easier to spoof fake 
> identities but your ISP can do that anyway, even in a system that only 
> supports "direct" discovery.)
> 
> Therefore, I'm not sure if it's correct to discredit fully-decentralised 
> systems, based solely or primarily on those attacks. I could be interpreting 
> it wrong, and I'm also not well-read in this topic at all. I'd love for 
> further expansion upon this point, by anyone that does have more expertise.

This is a very thoughtful reply. Thanks for the paper link. Interesting.

> 
> X
> 
> [1] https://www.freehaven.net/anonbib/cache/danezis-pet2008.pdf
> Bridging and Fingerprinting: Epistemic Attacks on Route Selection. George 
> Danezis and Paul Syverson.
> 
> -- 
> GPG: ed25519/56034877E1F87C35
> GPG: rsa4096/1318EFAC5FBBDBCE
> https://github.com/infinity0/pubkeys.git


signature.asc
Description: PGP signature
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[Michael Rogers]

On 01/11/17 01:40, Ximin Luo wrote:
> After a quick web search on "epistemic attacks", the main paper I can find 
> [1] has the result that attacks are very strong if each node only knows about 
> a small fraction (n nodes) of the whole network (N nodes).
> 
> They lay the motivation for this assumption (n << N), by describing a 
> discovery-based p2p network where each node "samples" (i.e. directly 
> contacts) a small fraction of the network. This is equating with mere 
> "knowledge" of a node, so that the act of "sampling" an attacker-controlled 
> node, gives them (or a GPA) the ability to know exactly which nodes "know" 
> the target node.
> 
> The paper does not seem to consider the possibility that nodes could discover 
> more of the network without directly sampling every node, e.g. via gossip 
> with their neighbours on "which other nodes exist".

The eclipse attack is relevant here. Briefly, if you discover nodes by
asking each node you know about which other nodes it knows about, an
attacker who controls some fraction d/n of the nodes can control a
larger fraction of your view, because honest nodes return a sample with
d/n dishonest nodes on average, whereas dishonest nodes can return a set
containing only dishonest nodes.

If node discovery is ongoing - for example, if you replace nodes in your
view that have gone offline by discovering more nodes - then the
attacker can eventually control your whole view.

(This is from memory and may be inaccurate, it's been a long time since
I read the paper.)

https://www.eecs.harvard.edu/~mema/courses/cs264/papers/eclipse-infocom06.pdf

Cheers,
Michael


0x9FC527CC.asc
Description: application/pgp-keys


signature.asc
Description: OpenPGP digital signature
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[Ximin Luo]

dawuud:
> [..]
>>
>> Indeed no, but I understand now and the comparison was useful, thanks. I 
>> think I was originally thrown off because the term "PKI" brought to my head 
>> X509 and WoT mapping of real-identities-to-keys.
>>
>> If I understand correctly, what you mean here instead is a service to 
>> provide consistency guarantees for the nodes in the network, so that they 
>> have some confidence they're talking to "the right network" and that they're 
>> not getting eclipse- or sybil-attacked. AFAIU the tor consensus system 
>> identifies each node using the node public key, so real-identities are not 
>> relevant. Then it also provides mappings between these keys/ids and their 
>> physical addresses.
> 
> I do not agree that PKI is the wrong word to use. I am using the term
> PKI in the same way that much of the mixnet literature uses it. And
> when working with George, Ania and Claudia we used the PKI term as
> well. [..] I don't know what you mean by "real".
> 

I didn't say PKI is the "wrong" word to use. I *would* say that PKI is not the 
best term to use here, even if it is "established" in the academic literature. 
Sometimes, texts specialised in one topic, uses the same words to mean slightly 
different things, compared to texts that specialise in a different area. But 
it's confusing if you have to deal with both topics at the same time.

In the wider security field, "PKI" is also used for things like X509 and WoT 
and similar. These things do *different security jobs* than 
Directory-Authority-based systems, so I'd prefer not to call both groups "PKI".

By "real [identity]" I mean the abstract idea that I have, in the 
flesh-and-blood computer inside my head, of the remote party that I'm 
communicating with. Crypto protocols deal only with public keys - on the crypto 
level you are not talking with a person or organisation, but with "the 
computational entity that has knowledge of the private key corresponding to 
public key K". So we need a system outside of the crypto, to securely map 
public keys to these "communication entities" we imagine in our heads. Commonly 
this is called "PKI".

Directory authorities perform a different job, so I prefer to not call these 
also "PKI". "Consensus service" would be less confusing - for me as a security 
person but not specialised in anonymity research.

> [..]
> 
> This [MIRANDA] paper is a departure from what we are trying to do
> since they are using the PKI and other mechanisms to defend against
> n-1 attacks whereas the Loopix design uses decoy traffic loops to
> detect n-1 attacks. That having been said I think it's a brilliant
> paper and I'd to implement something like it in the future.
> 
>> [..]
>>
>> Do you know of any papers that quantify the security guarantees around 
>> consensus-based approaches? I'm not aware of any, and it would be good to 
>> read some if they exist. I do know that community-detection-based systems do 
>> quantify their security in terms of probabilities of reaching malicious 
>> nodes, based on various quantified assumptions about the link distribution 
>> of social networks and strengths of social connections. It would also be 
>> good to be able to quantifiably compare the two approaches.
> 
> Good question. I would also be greatful if anyone on this list could
> point us to papers that talk more about the security properties of
> consensus-based PKIs/Directory Authority system.  I don't know of
> any. I don't understand why you think social networks and strengths of
> social connections is relavant... but maybe it is. Really, the voting
> protocol that mixminion and Tor use is a deterministic document
> generation algorithm.
> 

I mentioned social networks because the Miranda paper you linked mentions 
community detection, and those sorts of assumptions and goals are typical, with 
community detection algorithms relating to security in a decentralised network. 
But on a closer reading, I see that it is meant as a secondary improvement to 
the main contribution of the paper, and was not meant as a decentralised 
alternative to a system based on directory authorities.

So yes, they are not relevant for the reasons that I originally thought. 
However, I'm still hopeful to see a decentralised alternative to directory 
authorities, and quantifying security properties would be a good start, to 
either constructing one or disproving any possibility that they can be secure.

>[MIXMINIONDIRAUTH] Danezis, G., Dingledine, R., Mathewson, N.,
>   "Type III (Mixminion) Mix Directory Specification",
>   December 2005, .
> 
>[TORDIRAUTH]  "Tor directory protocol, version 3",
>   
> .
> 
> I've heard that I2p uses a completely different kind of PKI... involving a
> gossip protocol. I suspect it is highly vulnerable to epistemic attacks which
> is supposed to be one

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[dawuud]

> > Yes you are right to point out the vagueness in the PKI spec draft I
> > sent you.  Mixnets like Tor require a PKI that clients can query to
> > gain a view of the network so that path selection is possible. Like
> > Tor's Directory Authority system we need to store various bits of
> > information about each mix in say, a "mix descriptor".
> >
> > By "same view" I mean each client (just like in Tor) should receive
> > the same network consensus document. The client uses this for path
> > selection.
> >
> 
> Might be worth mentioning here that Tor's design does not actually
> ensure that "each client should receive the same network consensus
> document".
> 
> There are multiple valid consensus documents at every point in time, and
> each client should have a valid one, but that doesn't mean they all have
> the same one.
> 
> The Tor network makes a consensus document every 60 minutes, and clients
> are not instructed to immediately fetch it because that would cause a
> "thundering herd" problem. So each client has its own consensus download
> schedule, which means that different clients will have different consensuses.
> 
> Not sure if that invalidates any loopix assumptions but thought it might
> be worth mentioning it.
> 

Thanks for the correction! Yes and it seems like if there are only a small 
number
of valid consensus files at any given time then this should serve to eliminate
epistemic attacks on client's view of the network.

Oh look, slides about mixnets by George Danezis here:

https://panoramix-project.eu/wp-content/uploads/2017/06/AnonHUJ.pdf

On slide 16 he mentions:

"""Problem: all clients need to use the same information to construct paths
through relays. Otherwise: attacks based on knowledge of the client
(epistemic)."""



signature.asc
Description: PGP signature
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[George Kadianakis]

dawuud  writes:

>> 2. Why is a PKI necessary? On a quick read, Loopix paper doesn't seem to 
>> mention this. You have a brief justification in pki.txt but the text does 
>> not make complete sense to me: "it gives each client the same view of the 
>> network, it links mix IDs to public routing keys."
>> 
>>   - If by "same view" you mean "same view of crypto identities" then this 
>> suggests the network can't scale, as I was worried about above.
>>   - If by "same view" you mean "same view of online/offline nodes" I think 
>> this is impossible to achieve due to well, networks being unreliable.
>> 
>>   If mix IDs are simply the public routing keys themselves, does that avoid 
>> the need for a PKI? I suppose you still need to map public keys to physical 
>> addresses, but there's probably an existing system you could re-use for that 
>> purpose.
>
> Yes you are right to point out the vagueness in the PKI spec draft I
> sent you.  Mixnets like Tor require a PKI that clients can query to
> gain a view of the network so that path selection is possible. Like
> Tor's Directory Authority system we need to store various bits of
> information about each mix in say, a "mix descriptor".
>
> By "same view" I mean each client (just like in Tor) should receive
> the same network consensus document. The client uses this for path
> selection.
>

Might be worth mentioning here that Tor's design does not actually
ensure that "each client should receive the same network consensus
document".

There are multiple valid consensus documents at every point in time, and
each client should have a valid one, but that doesn't mean they all have
the same one.

The Tor network makes a consensus document every 60 minutes, and clients
are not instructed to immediately fetch it because that would cause a
"thundering herd" problem. So each client has its own consensus download
schedule, which means that different clients will have different consensuses.

Not sure if that invalidates any loopix assumptions but thought it might
be worth mentioning it.

___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[dawuud]

replying inline

On Mon, Oct 30, 2017 at 09:19:00AM +, Ximin Luo wrote:
> dawuud:
> > No, it will scale as Loopix intended. The constraint that each Operator
> > will run an equal size set of mixes is a deployment constraint that may
> > not be adhered to strictly. We shall see, for now we haven't even finished 
> > our
> > implementation so we are a ways away from discovering what works for 
> > deployments.
> 
> Can you go into that in a bit more detail, e.g. what does "deployment 
> constraint" mean, cost constraints? What happens if one operator runs 10 
> times as many provider-nodes as any other operator?

No I cannot go into detail because I don't have details like that.
Maybe someone else involved in the project can answer this question for you.

> >> Yes you are right to point out the vagueness in the PKI spec draft I
> >> sent you.  Mixnets like Tor require a PKI that clients can query to
> > 
> > Of course I'm not saying that mixnets and Tor are the same... whereas
> > Tor does no mixing.  Although the similarities are useful when
> > discussing the PKI because they both have similar needs.
> > 
> 
> Indeed no, but I understand now and the comparison was useful, thanks. I 
> think I was originally thrown off because the term "PKI" brought to my head 
> X509 and WoT mapping of real-identities-to-keys.
> 
> If I understand correctly, what you mean here instead is a service to provide 
> consistency guarantees for the nodes in the network, so that they have some 
> confidence they're talking to "the right network" and that they're not 
> getting eclipse- or sybil-attacked. AFAIU the tor consensus system identifies 
> each node using the node public key, so real-identities are not relevant. 
> Then it also provides mappings between these keys/ids and their physical 
> addresses.

I do not agree that PKI is the wrong word to use. I am using the term
PKI in the same way that much of the mixnet literature uses it. And
when working with George, Ania and Claudia we used the PKI term as
well.

Yes I think your understanding here is correct however I would have
stated that it is a mapping between the identity and the
descriptor. That the identity is a public key is true... as it will be
in our Directory Authority (PKI) system as well.  I don't know what
you mean by "real".

> > Ania also coauthored another recent paper about mixnets that has some
> > interesting uses for their PKI to help prevent byzantine or n-1 attacks:
> > 
> >[MIRANDA] Leibowitz, H., Piotrowska, A., Danezis, G., Herzberg, A., 2017,
> >  "No right to ramain silent: Isolating Malicious Mixes"
> >  .
> > 
> 
> The term "PKI" appears once in this paper: "We assume a PKI providing an 
> authoritative mapping between mixes and their public keys." It sounds like 
> they mean a real-identities-to-keys mapper rather than a consistency provider 
> or a address-to-keys mapper.

Indeed PKI appears once because they adopt the terms of Nick Mathewson
and call the PKI servers Directury Authority servers.

The Sphinx paper also has the term PKI exactly once:

"We assume the presence of a PKI that publishes an authenticated list of all 
(n, y n ) pairs."

Yes that one sentence in the [MIRANDA] paper could be more articulate
but I don't think it is incorrect. If the authors were working on a
specification I'm sure they would write down different details and use
the term descriptor since mapping identities to keys clearly isn't
enough.

> Consistency and consensus are not explicitly mentioned. Instead they mention 
> community detection, which is a *different* strategy for providing similar 
> security properties (i.e. that you're talking to "the right network").

This [MIRANDA] paper is a departure from what we are trying to do
since they are using the PKI and other mechanisms to defend against
n-1 attacks whereas the Loopix design uses decoy traffic loops to
detect n-1 attacks. That having been said I think it's a brilliant
paper and I'd to implement something like it in the future.

> In other words, it seems to me they're not using the term "PKI" in the same 
> way that you're using that term. 
> 
> >> gain a view of the network so that path selection is possible. Like
> >> Tor's Directory Authority system we need to store various bits of
> >> information about each mix in say, a "mix descriptor".
> >>
> >> By "same view" I mean each client (just like in Tor) should receive
> >> the same network consensus document. The client uses this for path
> >> selection.
> >>
> 
> Do you know of any papers that quantify the security guarantees around 
> consensus-based approaches? I'm not aware of any, and it would be good to 
> read some if they exist. I do know that community-detection-based systems do 
> quantify their security in terms of probabilities of reaching malicious 
> nodes, based on various quantified assumptions about the link distribution of 
> social networks and strengths 

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[Ximin Luo]

dawuud:
> No, it will scale as Loopix intended. The constraint that each Operator
> will run an equal size set of mixes is a deployment constraint that may
> not be adhered to strictly. We shall see, for now we haven't even finished our
> implementation so we are a ways away from discovering what works for 
> deployments.

Can you go into that in a bit more detail, e.g. what does "deployment 
constraint" mean, cost constraints? What happens if one operator runs 10 times 
as many provider-nodes as any other operator?

> [..]
>> Yes you are right to point out the vagueness in the PKI spec draft I
>> sent you.  Mixnets like Tor require a PKI that clients can query to
> 
> Of course I'm not saying that mixnets and Tor are the same... whereas
> Tor does no mixing.  Although the similarities are useful when
> discussing the PKI because they both have similar needs.
> 

Indeed no, but I understand now and the comparison was useful, thanks. I think 
I was originally thrown off because the term "PKI" brought to my head X509 and 
WoT mapping of real-identities-to-keys.

If I understand correctly, what you mean here instead is a service to provide 
consistency guarantees for the nodes in the network, so that they have some 
confidence they're talking to "the right network" and that they're not getting 
eclipse- or sybil-attacked. AFAIU the tor consensus system identifies each node 
using the node public key, so real-identities are not relevant. Then it also 
provides mappings between these keys/ids and their physical addresses.

> Ania also coauthored another recent paper about mixnets that has some
> interesting uses for their PKI to help prevent byzantine or n-1 attacks:
> 
>[MIRANDA] Leibowitz, H., Piotrowska, A., Danezis, G., Herzberg, A., 2017,
>  "No right to ramain silent: Isolating Malicious Mixes"
>  .
> 

The term "PKI" appears once in this paper: "We assume a PKI providing an 
authoritative mapping between mixes and their public keys." It sounds like they 
mean a real-identities-to-keys mapper rather than a consistency provider or a 
address-to-keys mapper.

Consistency and consensus are not explicitly mentioned. Instead they mention 
community detection, which is a *different* strategy for providing similar 
security properties (i.e. that you're talking to "the right network").

In other words, it seems to me they're not using the term "PKI" in the same way 
that you're using that term. 

>> gain a view of the network so that path selection is possible. Like
>> Tor's Directory Authority system we need to store various bits of
>> information about each mix in say, a "mix descriptor".
>>
>> By "same view" I mean each client (just like in Tor) should receive
>> the same network consensus document. The client uses this for path
>> selection.
>>

Do you know of any papers that quantify the security guarantees around 
consensus-based approaches? I'm not aware of any, and it would be good to read 
some if they exist. I do know that community-detection-based systems do 
quantify their security in terms of probabilities of reaching malicious nodes, 
based on various quantified assumptions about the link distribution of social 
networks and strengths of social connections. It would also be good to be able 
to quantifiably compare the two approaches.

>> To be clear, we are totally punting on the load balancing problem because 
>> it's hard.
>> However, the new Peer Flow paper looks promising:
>>
>>[PEERFLOW] Johnson, A., Jansen, R., Segal, A., Syverson, P.,
>>   "PeerFlow: Secure Load Balancing in Tor",
>>   Preceedings on Privacy Enhancing Technologies, July 2017,
>>   
>> .

Thanks for the pointer!

X

-- 
GPG: ed25519/56034877E1F87C35
GPG: rsa4096/1318EFAC5FBBDBCE
https://github.com/infinity0/pubkeys.git



signature.asc
Description: OpenPGP digital signature
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[dawuud]

> Yes you are right to point out the vagueness in the PKI spec draft I
> sent you.  Mixnets like Tor require a PKI that clients can query to

Of course I'm not saying that mixnets and Tor are the same... whereas
Tor does no mixing.  Although the similarities are useful when
discussing the PKI because they both have similar needs.

Ania also coauthored another recent paper about mixnets that has some
interesting uses for their PKI to help prevent byzantine or n-1 attacks:

   [MIRANDA] Leibowitz, H., Piotrowska, A., Danezis, G., Herzberg, A., 2017,
 "No right to ramain silent: Isolating Malicious Mixes"
 .

> gain a view of the network so that path selection is possible. Like
> Tor's Directory Authority system we need to store various bits of
> information about each mix in say, a "mix descriptor".
> 
> By "same view" I mean each client (just like in Tor) should receive
> the same network consensus document. The client uses this for path
> selection.
> 
> To be clear, we are totally punting on the load balancing problem because 
> it's hard.
> However, the new Peer Flow paper looks promising:
> 
>[PEERFLOW] Johnson, A., Jansen, R., Segal, A., Syverson, P.,
>   "PeerFlow: Secure Load Balancing in Tor",
>   Preceedings on Privacy Enhancing Technologies, July 2017,
>   
> .


signature.asc
Description: PGP signature
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[dawuud]

> 1. The Loopix paper mentions "Furthermore, many mix nodes can be securely 
> added to a stratified topology to scale throughput" but your mixdesign.txt 
> states "Operators are a part of a fixed set who all agree to cooperatively 
> run an equal size set of mixes and network perimeter points". Hopefully I'm 
> understanding you wrong but it sounds like:
> 
>   a) The proposed network won't scale as Loopix intended to.

No, it will scale as Loopix intended. The constraint that each Operator
will run an equal size set of mixes is a deployment constraint that may
not be adhered to strictly. We shall see, for now we haven't even finished our
implementation so we are a ways away from discovering what works for 
deployments.

What is to be understood here about the stratified topology for mix
networks is that it the best option we have because it scales well,
has slightly better entropy than free route topology, much easier to
prove entropy than free route and allows for a fixed set of perimeter
mixes in this case we call them Providers. Whereas most mixnet papers
end up writing about cascade topology which doesn't scale well at all.

>   b) There are additional trust requirements/assumptions that Loopix doesn't 
> require.

The Loopix design does use the same model we are implementing where Provider 
authenticate clients.

> Could you clarify?
> 
> 2. Why is a PKI necessary? On a quick read, Loopix paper doesn't seem to 
> mention this. You have a brief justification in pki.txt but the text does not 
> make complete sense to me: "it gives each client the same view of the 
> network, it links mix IDs to public routing keys."
> 
>   - If by "same view" you mean "same view of crypto identities" then this 
> suggests the network can't scale, as I was worried about above.
>   - If by "same view" you mean "same view of online/offline nodes" I think 
> this is impossible to achieve due to well, networks being unreliable.
> 
>   If mix IDs are simply the public routing keys themselves, does that avoid 
> the need for a PKI? I suppose you still need to map public keys to physical 
> addresses, but there's probably an existing system you could re-use for that 
> purpose.

Yes you are right to point out the vagueness in the PKI spec draft I
sent you.  Mixnets like Tor require a PKI that clients can query to
gain a view of the network so that path selection is possible. Like
Tor's Directory Authority system we need to store various bits of
information about each mix in say, a "mix descriptor".

By "same view" I mean each client (just like in Tor) should receive
the same network consensus document. The client uses this for path
selection.

To be clear, we are totally punting on the load balancing problem because it's 
hard.
However, the new Peer Flow paper looks promising:

   [PEERFLOW] Johnson, A., Jansen, R., Segal, A., Syverson, P.,
  "PeerFlow: Secure Load Balancing in Tor",
  Preceedings on Privacy Enhancing Technologies, July 2017,
  
.
 

> 3. "The PKI also needs to hold network wide parameters."

I meant network parameters that cannot otherwise be detected such
as the Poisson mix strategy lambda parameter that all clients must
use with selecting their route hop delays.

>   - Why is this necessary, why can't each mix node detect this by itself? If 
> they rely on a "PKI" for these parameters, doesn't the "PKI" hold some 
> position of power over the network?

The PKI is the root of all authority in the network... it can decide
which mixes belong and what certain network parameters are set
to. This is also why making the PKI/Directory Authority into a
decentralized system is a good idea.

>   - How do these parameters relate to the exponential/poisson RV parameters 
> mentioned in the Loopix paper? Do those parameters also need to be uniform 
> across all mix nodes? I suppose not, since it is supposed to defend against 
> malicious mix nodes, but perhaps "most honest nodes" need to agree on the 
> same parameters. In any case, I don't see the point being explained in great 
> detail. (Again, this on a quick reading; I might have missed something.)
> 
> Those are the specific questions. Apart from that, it would be good if you 
> could summarise the differences between your design and Loopix plus some 
> motivation on why. (Because people like me naturally ask "why not just do 
> Loopix".)

We are essentially doing the Loopix design here. Ania, the primary
author of the Loopix paper spent 3.5 months with us in our
design team working on these specifications. We are adding to it's
design: reliability via Stop and Wait ARQ.

Also... we didn't get around to specifying decoy traffic and we intend
to do this later.

> I gather that you do already talk about this elsewhere, it just would be nice 
> to have it collected together in a separate document. For example the Loop

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[Ximin Luo]

dawuud:
> 
> https://github.com/Katzenpost/docs/blob/master/drafts/mixdesign.txt
> 
> [..]
Hi David, it's been a while since I read through this topic, and I only briefly 
scanned the Loopix paper, so forgive me if the following questions are ignorant:

1. The Loopix paper mentions "Furthermore, many mix nodes can be securely added 
to a stratified topology to scale throughput" but your mixdesign.txt states 
"Operators are a part of a fixed set who all agree to cooperatively run an 
equal size set of mixes and network perimeter points". Hopefully I'm 
understanding you wrong but it sounds like:

  a) The proposed network won't scale as Loopix intended to.
  b) There are additional trust requirements/assumptions that Loopix doesn't 
require.

Could you clarify?

2. Why is a PKI necessary? On a quick read, Loopix paper doesn't seem to 
mention this. You have a brief justification in pki.txt but the text does not 
make complete sense to me: "it gives each client the same view of the network, 
it links mix IDs to public routing keys."

  - If by "same view" you mean "same view of crypto identities" then this 
suggests the network can't scale, as I was worried about above.
  - If by "same view" you mean "same view of online/offline nodes" I think this 
is impossible to achieve due to well, networks being unreliable.

  If mix IDs are simply the public routing keys themselves, does that avoid the 
need for a PKI? I suppose you still need to map public keys to physical 
addresses, but there's probably an existing system you could re-use for that 
purpose.

3. "The PKI also needs to hold network wide parameters."

  - Why is this necessary, why can't each mix node detect this by itself? If 
they rely on a "PKI" for these parameters, doesn't the "PKI" hold some position 
of power over the network?
  - How do these parameters relate to the exponential/poisson RV parameters 
mentioned in the Loopix paper? Do those parameters also need to be uniform 
across all mix nodes? I suppose not, since it is supposed to defend against 
malicious mix nodes, but perhaps "most honest nodes" need to agree on the same 
parameters. In any case, I don't see the point being explained in great detail. 
(Again, this on a quick reading; I might have missed something.)

Those are the specific questions. Apart from that, it would be good if you 
could summarise the differences between your design and Loopix plus some 
motivation on why. (Because people like me naturally ask "why not just do 
Loopix".)

I gather that you do already talk about this elsewhere, it just would be nice 
to have it collected together in a separate document. For example the Loopix 
paper has a Section 6 "Related Work" and a Table 2 that summarises this - it 
was very nice to read that, especially for me who hasn't looked at this topic 
for a significant time.

In particular, it would be good if you could talk a bit about how your 
differences, affect Loopix's original security properties. I think Section 2.3 
"Security Goals" is quite a nice summary of what it's trying to achieve. If you 
could confirm that is indeed what your system is also aiming for, together with 
any other security properties it doesn't mention, it would be much easier to 
evaluate.

X

-- 
GPG: ed25519/56034877E1F87C35
GPG: rsa4096/1318EFAC5FBBDBCE
https://github.com/infinity0/pubkeys.git



signature.asc
Description: OpenPGP digital signature
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[dawuud]

> > the key material between the two orientations.  You could achieve that
> > split by building a SURB, and doing so may simplify the code elsewhere
> > or even enable multiple-ACKs, but it's nowhere near as messy as folks
> > imagine when they hear you say SURB though. 
> 
> Actually, I think the main obstable one encounters when mentioning
> this stuff to various autistic crypto nerds is essentially a 10 year
> old anti-mixnet prejudice by those who have not yet read the Loopix paper
> which is clearly the most advanced published mixnet paper to date.

Sorry, I didn't mean to sound anti-autistic. Cognitive diversity is a good 
thing.
I suppose I'm anti-"sneering" which is a thing that some rather unfriendly 
people
do when they encounter new information.


signature.asc
Description: PGP signature
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[dawuud]

> On Sat, 2017-09-16 at 22:21 +, dawuud wrote:
> > On the other hand the Loopix design as described in the paper does not
> > include any message reliability mechanism at all. In our design we do
> > not use the SURBs to achieve any identity-hiding property like
> > Mixminion does. Instead we only use SURBs to send ACKnowledgements in
> > our Stop and Wait ARQ protocol from Client to Provider.
> 
> I'm sure I've pointed this out to you guys before, David, but ACKs do
> not need SURBs per se.  At least not if the ACK comes from the mail
> server as opposed to the user.  You just send a packet in a loop, but
> execute a special command mid way that drops off the message and
> replaces it with the ACK.  It only requires that packet building split

That is equivalent to using a SURB... although it has some
disadvantages which include extreme packet header overhead; that is to
say: If your Sphinx packet format ensures that each hop's routing info
slot is the same size then you end up with lots of wasted space when
you stuff a payload into one of those slots because all the other
slots must pad to the same size. Further this adds complexity to the
implementation of the Sphinx packet format because it means that the
header size will be variable instead of fixed size; you cannot stuff a
fixed size header inside another header which is fixed to the same
size!

Further, if you use Sphinx headers in this way you don't really need
the packet "body" at all which is originally specified to be encrypted
with an SPRP/wide-block cipher such as Lioness. You are essentially
decapitating the Sphinx, where all you are left with is a human head
that is no longer attached to the body of a lion ;-p

The reason I say they are equivalent is that ultimately both ideas are
about sending a packet with enough routing information for the ACK to
reach the source whence it came.

So I appear to be arguing here that our specification for ACKs via SURBs is a
better design than sending loops where the payload is contained in the
header...  However, loops are great for other things such as
heartbeats to detect n-1 attacks and decoy traffic. Hence the name
Loopix which uses several kinds of looped messages in it's design.

> the key material between the two orientations.  You could achieve that
> split by building a SURB, and doing so may simplify the code elsewhere
> or even enable multiple-ACKs, but it's nowhere near as messy as folks
> imagine when they hear you say SURB though. 

Actually, I think the main obstable one encounters when mentioning
this stuff to various autistic crypto nerds is essentially a 10 year
old anti-mixnet prejudice by those who have not yet read the Loopix paper
which is clearly the most advanced published mixnet paper to date.


signature.asc
Description: PGP signature
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[dawuud]

Hi Michael,

> Ah, thanks for explaining. I thought the goal was to build a
> general-purpose mixnet infrastructure on which people could build
> as-yet-unknown applications. Hence all the questions about what options
> are available to applications and what interfaces are exposed by
> different layers.

You will have to write a new client and modify the Provider a bit to
get it working with your application. The Provider isn't written
yet... (nor is the mix) but I'm hoping Yawning will get to work on it
soon. As for the client component... it's fairly easy to write one
reusing much of our existing code. For instance our "core" repo has
our wire protocol library and a Sphinx library. The "client" repo has
our crypto/block library for end to end messages using noise_x. The
stuff that you don't want such as POP3 and SMTP can easily be omitted
from whatever client you end up writing.

> But even if the goal is just to support specific applications, I wonder
> if it would be useful for clients (by which I mean mixnet clients, not
> MUAs) to have some control over decoy traffic, because different clients
> will have different constraints. For example, a desktop client may
> prefer different power/bandwidth/anonymity tradeoffs to a mobile client.

Well, it depends what you means by "client"... it's gotten rather
blurred with how we've designed things. I would say that the mixnet
client *does* have control over the decoy traffic it emits; how would
it not have control? On the other hand I don't think users should be
burdened with these details. (then again i don't really want to
discuss user interfaces but if we were to discuss this then I would be
citing papers written by Ka Ping Yee and pointing out design
principles such as the principle of least resistance etc.)

Let me know if you have any questions about the specifications after you read 
them.


Cheers!
David



signature.asc
Description: PGP signature
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[Michael Rogers]

Hi David,

On 21/09/17 14:58, dawuud wrote:
> Our Stop and Wait ARQ scheme terminates on the destination Provider.
> If it was client to client then both clients would have to be online
> at the same time.

Thanks for explaining, that makes sense.

>> But I think the mix layer has been adapted to the needs of the
>> reliability layer to some extent by adding SURBs, right? And in a
> 
> No. The mix net gives zero fucks about reliability.
> Fundamentally mixnets are an unreliable packet switching network.

Sure, I understand that the mixnet is an unreliable packet switching
network. And then there are some other pieces - reply blocks, flow
control, ARQ - that are implemented by higher layers, or maybe
implemented by the mixnet and used by higher layers. I'm trying to
understand how the pieces fit together.

>> previous message you mentioned "source quench" from mixes to providers.
> 
> No. I didn't. Trevor mentioned it. This is an implementation detail
> and is more related to flow control. It's definitely not part of any
> ARQ protocol scheme.

Sorry for attributing the quote to the wrong person. I'll go and read
the specs to understand how flow control fits into the bigger picture.

> I suggest you read up on ARQ protocol schemes. Wikipedia has some decent 
> articles
> on the subject. There's a vast amount of literature on this subject which may
> help clear up your misunderstanding of what reliability means in the context
> of an unreliable packet switching network.

I have a fairly good understanding of ARQ and general networking
concepts. What I'm trying to understand is how those concepts are used
in the Katzenpost architecture. Ultimately I'd like to understand what
my options are for building applications on top of Katzenpost.

>> there are other considerations for mobile clients: decoy messages
>> consume bandwidth and power, and a mobile app may not be able to wake up
>> to send decoy messages on an arbitrary schedule. So my broader question
>> is how much control an application using Panoramix, or even an
>> individual client, will have over the decoy traffic parameters, and how
>> those choices will affect anonymity.
> 
> By the way the name Panoramix refers to a much bigger project than this
> decryption mixnet. So far we've named our implementation Katzenpost
> because the committee hasn't told us to rename it yet.
> 
> This is really a question about the Loopix paper if you are asking about
> the anonymity set size on mixes versus decoy traffic versus legit traffic.

Good point, I'll ask the Loopix authors about that part.

> On the other hand your question is also essentially a trick question
> because you are assuming that the application's interface with the
> mixnet includes control over decoy traffic whereas from my perspective
> the mixnet is designed to support specific applications and therefore
> the appropriate decoy traffic will have already been selected.
> 
> Or said another way: "Do you really think an e-mail client should let
> the user select the frequency of decoy messages sent over the mixnet?"

Ah, thanks for explaining. I thought the goal was to build a
general-purpose mixnet infrastructure on which people could build
as-yet-unknown applications. Hence all the questions about what options
are available to applications and what interfaces are exposed by
different layers.

But even if the goal is just to support specific applications, I wonder
if it would be useful for clients (by which I mean mixnet clients, not
MUAs) to have some control over decoy traffic, because different clients
will have different constraints. For example, a desktop client may
prefer different power/bandwidth/anonymity tradeoffs to a mobile client.

Cheers,
Michael


0x9FC527CC.asc
Description: application/pgp-keys


signature.asc
Description: OpenPGP digital signature
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[dawuud]

replying inline...

> > End to end reliability can only be achieved using an Automatic Repeat
> > reQuest protocol scheme which resides in the client. If you do not
> > require reliability then the client becomes a lot simpler in it's
> > design and implementation.
> > 
> > Take a moment to consider what might happen if we tried to make the
> > mix network reliable without involving the client. In this case we
> > could implement some sort of store and forward mechanism in each
> > component mix... but ultimately if there is a mix outage this cannot
> > guarantee reliable transmission of messages.
> > 
> > We have intentionally designed the client to be smart and the network
> > components to be relatively dumb in accordance with the End to End
> > Principle.
> 
> Thanks, that's good to know. So does this mean the mixes and providers
> aren't involved in reliability at all - it's all client to client?

Our Stop and Wait ARQ scheme terminates on the destination Provider.
If it was client to client then both clients would have to be online
at the same time.

> But I think the mix layer has been adapted to the needs of the
> reliability layer to some extent by adding SURBs, right? And in a

No. The mix net gives zero fucks about reliability.
Fundamentally mixnets are an unreliable packet switching network.

> previous message you mentioned "source quench" from mixes to providers.

No. I didn't. Trevor mentioned it. This is an implementation detail
and is more related to flow control. It's definitely not part of any
ARQ protocol scheme.

> So I'm trying to understand which bits of the reliability design are
> provided by which components.

The source client and the destination provider are involved. It's an ARQ 
protocol.
I suggest you read up on ARQ protocol schemes. Wikipedia has some decent 
articles
on the subject. There's a vast amount of literature on this subject which may
help clear up your misunderstanding of what reliability means in the context
of an unreliable packet switching network.

> Maybe I just need to read the specs, but I was hoping you could give me
> an overview.

Yes perhaps reading the specs would be helpful. I am trying to answer your
questions here but I don't know you and I don't know your technical background
so it's difficult for me to determine how much I need to explain and how much
is obvious to you.

> >> Sending a notification as
> >> soon as a message arrives at the provider exposes more metadata to a
> >> global passive adversary than holding onto the message until the user
> >> polls for it - but on the other hand users of some applications may
> > 
> > That is only a correct statement if there is no decoy traffic to the
> > client whereas we expect to specify decoy traffic in future revisions
> > of our design. If you pay close attention to the Loopix paper, you'll
> > see that it specifies several types of decoy traffic, some of which
> > terminate on the client. These are important aspects of the Loopix
> > design that should not be ignored.
> 
> Don't worry, I didn't ignore them. :-) I've read the paper but I'm
> interested in what design choices will be implemented in Panoramix.

I am not worried about anything.

> In the case I was talking about above, where the client's online but
> asleep, a network observer may be able to distinguish a decoy message
> that's silently consumed by the client from a real message that turns on
> the screen, causing other applications to wake up and hit the network.

That's stupid, we wouldn't do that. It totally defeats the purpose of
decoy traffic.  Do you see why I have to write this? We cannot have a
decoy traffic design which allows a passive network adversary to
distinguish between legit and decoy message.

Furthermore I really do not care about desiging user interfaces or
cell phone applications. Zero fucks given. I mean... I can work and
collaborate with others who are concerned with that but I'm not going
to do the design work for that stuff. Cognitive diversity is a huge
factor...  and I'm just not the right person to engage in conversation
on this particular topic but there are amazingly smart people that I'm
sure would be more than happy to chat with you about that... but I
would question if that belongs on this mailing list.

> That's just one scenario and I don't want to get hung up on it, but

OK good. Then let's just not talk about that anymore.

> there are other considerations for mobile clients: decoy messages
> consume bandwidth and power, and a mobile app may not be able to wake up
> to send decoy messages on an arbitrary schedule. So my broader question
> is how much control an application using Panoramix, or even an
> individual client, will have over the decoy traffic parameters, and how
> those choices will affect anonymity.

By the way the name Panoramix refers to a much bigger project than this
decryption mixnet. So far we've named our implementation Katzenpost
because the committee hasn't told us to rename 

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[Michael Rogers]

On 19/09/17 18:44, dawuud wrote:
> End to end reliability can only be achieved using an Automatic Repeat
> reQuest protocol scheme which resides in the client. If you do not
> require reliability then the client becomes a lot simpler in it's
> design and implementation.
> 
> Take a moment to consider what might happen if we tried to make the
> mix network reliable without involving the client. In this case we
> could implement some sort of store and forward mechanism in each
> component mix... but ultimately if there is a mix outage this cannot
> guarantee reliable transmission of messages.
> 
> We have intentionally designed the client to be smart and the network
> components to be relatively dumb in accordance with the End to End
> Principle.

Thanks, that's good to know. So does this mean the mixes and providers
aren't involved in reliability at all - it's all client to client?

But I think the mix layer has been adapted to the needs of the
reliability layer to some extent by adding SURBs, right? And in a
previous message you mentioned "source quench" from mixes to providers.
So I'm trying to understand which bits of the reliability design are
provided by which components.

Maybe I just need to read the specs, but I was hoping you could give me
an overview.

>> Sending a notification as
>> soon as a message arrives at the provider exposes more metadata to a
>> global passive adversary than holding onto the message until the user
>> polls for it - but on the other hand users of some applications may
> 
> That is only a correct statement if there is no decoy traffic to the
> client whereas we expect to specify decoy traffic in future revisions
> of our design. If you pay close attention to the Loopix paper, you'll
> see that it specifies several types of decoy traffic, some of which
> terminate on the client. These are important aspects of the Loopix
> design that should not be ignored.

Don't worry, I didn't ignore them. :-) I've read the paper but I'm
interested in what design choices will be implemented in Panoramix.

In the case I was talking about above, where the client's online but
asleep, a network observer may be able to distinguish a decoy message
that's silently consumed by the client from a real message that turns on
the screen, causing other applications to wake up and hit the network.

That's just one scenario and I don't want to get hung up on it, but
there are other considerations for mobile clients: decoy messages
consume bandwidth and power, and a mobile app may not be able to wake up
to send decoy messages on an arbitrary schedule. So my broader question
is how much control an application using Panoramix, or even an
individual client, will have over the decoy traffic parameters, and how
those choices will affect anonymity.

> That having been said, I can tell you that the current rough draft
> client I have written has a SMTP submition proxy and a POP3 receive
> proxy that are meant to run locally on the client's endpoint
> device. This flexible design blurs the definition of "client".
> 
> This mixnet client as written performs periodic polling of the
> Providers for which the user has an account. I'm willing to change the
> implementation of the client if our Android developer wishes it,
> however the primary goal of using SMTP and POP3 as interaction
> mechanisms was to avoid heavily modifying the k9mail client to perform
> lots of crypto operations. This was mainly done because we do not wish
> to write our mixnet crypto libraries in multiple languages at this
> time. Our code base is all in golang whereas k9mail is written in
> Java.
> 
> Of course this also means that our current "client" should work
> with well with all e-mail clients that use SMTP and POP3.

It's great to know you're working with k9mail - I'm excited to try out
the client, and then I can start pestering you with specific questions
rather than vague ones. ;-)

Cheers,
Michael


0x9FC527CC.asc
Description: application/pgp-keys


signature.asc
Description: OpenPGP digital signature
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[dawuud]

Hi Michael,

> Hi David,
> 
> It's really exciting to see mix networks becoming an active area of
> interest again. Can I ask a couple of high-level questions about Panoramix?

Yes, questions welcomed!

> First, you're adding a reliability layer on top of Loopix, right? I can

Yes, indeed it could be articulated in that way. However we do not currently
have specifications for decoy traffic but we plan to in the future.

> see the usefulness of that, but I also wonder whether all applications
> will have the same reliability needs - in the IP world some applications
> use UDP rather than TCP, some use multicast, etc. To what extent is the

No. Not all applications have the same needs in a network transport protocol.

> reliability layer fused with the mixnet layer? If I wanted to use a
> different reliability layer (or none), which parts of the system
> (clients, mixes, providers) would I need to replace?

End to end reliability can only be achieved using an Automatic Repeat
reQuest protocol scheme which resides in the client. If you do not
require reliability then the client becomes a lot simpler in it's
design and implementation.

Take a moment to consider what might happen if we tried to make the
mix network reliable without involving the client. In this case we
could implement some sort of store and forward mechanism in each
component mix... but ultimately if there is a mix outage this cannot
guarantee reliable transmission of messages.

We have intentionally designed the client to be smart and the network
components to be relatively dumb in accordance with the End to End
Principle.

Depending on the application, it is also possible to achieve
reliability without the use of ACKnowledge control messages. In this
thread I have previously mentioned my mixnet zcash transaction
transport idea where the blockchain is utilized in place of
ACKnowledge control messages in a Stop and Wait ARQ scheme. Here:

https://moderncrypto.org/mail-archive/messaging/2017/002368.html

and here:

https://moderncrypto.org/mail-archive/messaging/2017/002370.html

> Second, Loopix allows users to receive messages (via their providers)
> while they're offline, which is great. But for mobile devices there's
> another common situation, where the device is online but asleep. Email
> and messaging apps typically wake the device with a push notification
> when a message is available. On Android at least this can be done
> without going through Google's push service by keeping a connection to
> the provider open while the device is asleep. Sending a notification as
> soon as a message arrives at the provider exposes more metadata to a
> global passive adversary than holding onto the message until the user
> polls for it - but on the other hand users of some applications may

That is only a correct statement if there is no decoy traffic to the
client whereas we expect to specify decoy traffic in future revisions
of our design. If you pay close attention to the Loopix paper, you'll
see that it specifies several types of decoy traffic, some of which
terminate on the client. These are important aspects of the Loopix
design that should not be ignored.

> expect timely notifications. Are push notifications something you've
> considered in the Panoramix design, and if not, would you be interested
> in including them?

Yes I agree it sounds interesting but ultimately it's not up to me. I
am more involved in the overall mixnet design and the user facing
intricacies have not been my primary concern here. We are working with
a k9mail/Android developer who will ultimately be making these kinds of
decisions.

That having been said, I can tell you that the current rough draft
client I have written has a SMTP submition proxy and a POP3 receive
proxy that are meant to run locally on the client's endpoint
device. This flexible design blurs the definition of "client".

This mixnet client as written performs periodic polling of the
Providers for which the user has an account. I'm willing to change the
implementation of the client if our Android developer wishes it,
however the primary goal of using SMTP and POP3 as interaction
mechanisms was to avoid heavily modifying the k9mail client to perform
lots of crypto operations. This was mainly done because we do not wish
to write our mixnet crypto libraries in multiple languages at this
time. Our code base is all in golang whereas k9mail is written in
Java.

Of course this also means that our current "client" should work
with well with all e-mail clients that use SMTP and POP3.


Cheers,
David


signature.asc
Description: PGP signature
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[Michael Rogers]

On 09/08/17 03:53, dawuud wrote:
> I just wanted to make you all aware that I've published our design
> and specification documents for our mixnet project:
> 
> https://github.com/Katzenpost/docs

Hi David,

It's really exciting to see mix networks becoming an active area of
interest again. Can I ask a couple of high-level questions about Panoramix?

First, you're adding a reliability layer on top of Loopix, right? I can
see the usefulness of that, but I also wonder whether all applications
will have the same reliability needs - in the IP world some applications
use UDP rather than TCP, some use multicast, etc. To what extent is the
reliability layer fused with the mixnet layer? If I wanted to use a
different reliability layer (or none), which parts of the system
(clients, mixes, providers) would I need to replace?

Second, Loopix allows users to receive messages (via their providers)
while they're offline, which is great. But for mobile devices there's
another common situation, where the device is online but asleep. Email
and messaging apps typically wake the device with a push notification
when a message is available. On Android at least this can be done
without going through Google's push service by keeping a connection to
the provider open while the device is asleep. Sending a notification as
soon as a message arrives at the provider exposes more metadata to a
global passive adversary than holding onto the message until the user
polls for it - but on the other hand users of some applications may
expect timely notifications. Are push notifications something you've
considered in the Panoramix design, and if not, would you be interested
in including them?

Cheers,
Michael


0x9FC527CC.asc
Description: application/pgp-keys


signature.asc
Description: OpenPGP digital signature
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[Jeff Burdges]

On Sun, 2017-09-17 at 08:43 +, dawuud wrote:
> Sweet! I'm looking forward to reading this mountain of pros you've produced.
> As I've mentioned before, I'm a fan of your work.

It's almost all 5+ months old now, probably the last real additions were
due to a brief chat about ACKs with George in June.  It's also a
frigging mess so I'll do some cleanup today. 

I should emphasize that this document is not a spec.  It's an analysis
of the design choices one makes in implementing Sphinx and some of my
ideas.  It's the reasoning behind much of what one should write in a
spec for the protocol format.

Jeff



signature.asc
Description: This is a digitally signed message part
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[dawuud]

Jeff,

> I've an unfinished document that analyzes different forms the Sphinx
> packet format might take : 
> https://github.com/burdges/lake/tree/master/Xolotl/papers

Sweet! I'm looking forward to reading this mountain of pros you've produced.
As I've mentioned before, I'm a fan of your work.

> It's true, cross over points and SURBs add complexity to the
> implementation, and make the header larger, but actually they do not
> complicate the fields of the packet format.  In particular, the cross
> over point should extract the SURB from beta, not some separate SURB
> field or delta. 
> https://github.com/burdges/lake/blob/master/Xolotl/papers/Xolotl-2-sphinx.tex#L150-L180

Yes, for your use case this makes sense and for Katzenpost we've taken
a different approach. For those of you following along who haven't
read the Sphinx paper, by delta Jeff means the Sphinx packet
payload. And by beta he means "routing info" section of the header. In
our Sphinx spec we use descriptive names instead of Greek symbols:

https://github.com/Katzenpost/docs/blob/f45fa33a747fe908090756446259f7b67e543731/specs/sphinx.txt#L283

> In fact, SURBs do not complicate the implementation much either.
> Actually using SURBs does require a delicate strategy for distributing
> the SURBs though.  *That* is the real complexity.

Sure but it depends on how the SURBs are used. Our Katzenpost design
uses SURBs in a *very* simple manner. Our usage of Sphinx terminates
at the destination Provider, the payload contains two items:

1. a SURB for sending an ACKnowledgement message
2. end to end Noise_X ciphertext to be queued for later retrieval

It sounds like your usage of SURBs allows for some identity-hiding properties
such as:

* sender anonymity
* receiver anonymity

These are properties I would want in future mixnet messaging systems.

> Anyways, there is no reason a mix network must commit to using SURBs or
> not.  It should design the packet format to support SURBs regardless,
> and ideally even do cross over points, but may initially avoid the
> complexity of distributing SURBs.

I disagree with these two points. Firstly, SURB usage increases
exposure to compulsion attacks, which is a reason not to use them but
this reason may not be sufficiently established for all use cases.

Secondly, it is not necessary for all decryption mixnets to support
SURBs and cross over points. I think it really depends on the
application. My counter example was briefly mentioned in my previous
e-mail where a decryption mixnet is used as a transport for zcash
transactions. In this case, we can get away with a very simple design
where only forward messages are utilized.  The blockchain can later be
examined to determine if a retransmission is needed.

OK... but I admittedly cannot think of other applications with a similar
broadcast mechanism.

> On Sat, 2017-09-16 at 22:21 +, dawuud wrote:
> > On the other hand the Loopix design as described in the paper does not
> > include any message reliability mechanism at all. In our design we do
> > not use the SURBs to achieve any identity-hiding property like
> > Mixminion does. Instead we only use SURBs to send ACKnowledgements in
> > our Stop and Wait ARQ protocol from Client to Provider.
> 
> I'm sure I've pointed this out to you guys before, David, but ACKs do
> not need SURBs per se.  At least not if the ACK comes from the mail
> server as opposed to the user.  You just send a packet in a loop, but

Indeed! I think this is an excellent idea AND I think we should make a
note of all the different ways we can think of to send ACKs in mixnet
designs because each of them is going to have differing tradeoffs. For
instance, how big is your Sphinx header when stuffing SURBs into the
"routing info" section?  Do you force all "routing info" slots per hop
to be the same size?  Actually, it sounds like you've got a great many
variations to work with and that a chart to show features versus
overhead sizes might be helpful.

...and by "mail server" you mean "Provider" in the Loopix terminology.
I'm very pleased that our current design avoids running any mail servers.
We queue messages on the Providers. Similar but better. No SMTP!

> execute a special command mid way that drops off the message and
> replaces it with the ACK.  It only requires that packet building split
> the key material between the two orientations.  You could achieve that
> split by building a SURB, and doing so may simplify the code elsewhere
> or even enable multiple-ACKs, but it's nowhere near as messy as folks
> imagine when they hear you say SURB though. 

The Sphinx packet format is so flexible, I think it's great that you
are exploring various ways it can be used and thinking about
reliability.  I suspect most humans will not want to use an unreliable
crypto messaging system.


Regards,

David


signature.asc
Description: PGP signature
___
Messaging mailing list
Messaging@moderncrypto.org
https://mod

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[Jeff Burdges]

Trevor, 

I've an unfinished document that analyzes different forms the Sphinx
packet format might take : 
https://github.com/burdges/lake/tree/master/Xolotl/papers

It's true, cross over points and SURBs add complexity to the
implementation, and make the header larger, but actually they do not
complicate the fields of the packet format.  In particular, the cross
over point should extract the SURB from beta, not some separate SURB
field or delta. 
https://github.com/burdges/lake/blob/master/Xolotl/papers/Xolotl-2-sphinx.tex#L150-L180

In fact, SURBs do not complicate the implementation much either.
Actually using SURBs does require a delicate strategy for distributing
the SURBs though.  *That* is the real complexity.

Anyways, there is no reason a mix network must commit to using SURBs or
not.  It should design the packet format to support SURBs regardless,
and ideally even do cross over points, but may initially avoid the
complexity of distributing SURBs.


As an aside, if you want to be worried, you should check out my SURB log
idea here:
https://github.com/burdges/lake/blob/master/Xolotl/papers/Xolotl-3-mailboxes.tex#L118
It's stream cipher encrypted and unMACed!  It should be secure for the
limited purpose which it serves though.


On Sat, 2017-09-16 at 22:21 +, dawuud wrote:
> On the other hand the Loopix design as described in the paper does not
> include any message reliability mechanism at all. In our design we do
> not use the SURBs to achieve any identity-hiding property like
> Mixminion does. Instead we only use SURBs to send ACKnowledgements in
> our Stop and Wait ARQ protocol from Client to Provider.

I'm sure I've pointed this out to you guys before, David, but ACKs do
not need SURBs per se.  At least not if the ACK comes from the mail
server as opposed to the user.  You just send a packet in a loop, but
execute a special command mid way that drops off the message and
replaces it with the ACK.  It only requires that packet building split
the key material between the two orientations.  You could achieve that
split by building a SURB, and doing so may simplify the code elsewhere
or even enable multiple-ACKs, but it's nowhere near as messy as folks
imagine when they hear you say SURB though. 

Jeff




signature.asc
Description: This is a digitally signed message part
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[dawuud]

> Hi David,

Hi Trevor,

> Hope you don't mind belated comments:

That's a very thoughtful message you have written and I really appreciate it.
I'm hoping my mixnet design collegues will join this discussion because they
have lots of ideas on the subject and our specs are filled with many tradeoffs
that we made for the constraints of this particular project.

> This is an ambitious protocol stack!  I think the different layers and
> choices are something like:
> 
> Mix packet format = Sphinx
> Mix strategy = Poisson Mix (a simplified "Stop-and-Go Mix")
> Mixnet topology = Stratified
> Dummy traffic strategy = Loopix
> Reliability/retransmission = Stop-and-Wait ARQ
> Congestion control = "Source Quench" from mixes to providers
> Link protocol = TCP/Noise_XX
> End-to-end protocol = Email/Noise_X

yeeup that's right. I would also mention that our noise-based wire protocol
uses the NewHope_Simple handhshake (which we should later upgrade to Kyber).
I added the "rekey" feature to the go noise library.

In Yawning's noise fork he added the NewHope_Simple handshake here:

https://github.com/Katzenpost/noise

> It's interesting to see everything needed for a full mixnet architecture.
> I imagine these decisions might be different for different applications, so
> I hope you're building modularity between components.

Indeed we are building modular components, it's really the only way to
write decent code. For instance here's our wire protocol:

https://github.com/Katzenpost/core/tree/master/wire

and here's Yawning Sphinx implementation:

https://github.com/Katzenpost/core/tree/master/sphinx

The client is still in a very rough draft state here in the develop branch:

https://github.com/Katzenpost/client/tree/develop

> "Sphinx" and "Stop-and-Go mixes" seem particularly reusable within
> different architectures.  High-quality specs and code for them would be one
> great outcome here.

Yes we are striving for high-quality specs and code. So many years after the 
Sphinx
paper was written we finally have a Sphinx spec:

https://github.com/Katzenpost/docs/blob/master/specs/sphinx.txt

I think our other specs are pretty good too. Although we did not yet specify
decoy traffic because we plan to do that in another research and dev cycle
based on traffic statistics of legit traffic within the closed group of 
"Providers".

> (Though there's room for debate even within those components.  For example,
> SURB support in Sphinx adds complexity and requires an unusual
> "large-block" cipher.  SURBs don't seem necessary for Loopix, and I've
> wondered whether dropping SURB support would make things simpler [1])

Yes! I have discussed this subject extensively with many people. Our
design can *easily* be adapted to a totally different application
that will NOT require SURBs even if reliability of message transmission is
required e.g. "send zcash transaction to the blockchain over the mixnet".

In the case of this zcash mixnet transport, the client sends a zcash transaction
and then after the total Poisson mix route delay checks the blockchain for their
transaction. If the transaction is not present, retransmit!

This is essentially a Stop and Wait ARQ that uses a broadcast mechanism instead
of ACKnowledgement control messages.

I agree, in the Loopix design SURBs are not needed. Even the "decoy loops"
do not need SURBs:

1. clients send decoy loops to their Provider, the message is
routed through a series of mixes, one mix in each layer of strata and then to
the same Provider and finally back to the client.

2. mix decoy loops also do not need SURBs: the mix sends the message and it
gets routed through each layer of strata until it reaches a Provider which
subsequently routes the message back into the mix layers until it reaches
it's origin mix.

On the other hand the Loopix design as described in the paper does not
include any message reliability mechanism at all. In our design we do
not use the SURBs to achieve any identity-hiding property like
Mixminion does. Instead we only use SURBs to send ACKnowledgements in
our Stop and Wait ARQ protocol from Client to Provider.

> Anyways, the hardest decisions are probably around "mixnet topology" and
> "dummy traffic", since this is where real-world economic and deployability
> concerns come in:
>  * Who is going to run mixes?

For this particular project the Providers will be LEAP e-mail providers
who will also operate one or more mixes. (we are not even trying to make a
Tor-like volunteer run mixnet)

>  * How tolerable are latency and dummy-traffic requirements for real users?

Good question! I have a link to a paper which is relevant:

Obstacles to the Adoption of Secure Communication Tools
https://www.ieee-security.org/TC/SP2017/papers/84.pdf

This paper seems to indicate that the primary obstacles are lack of
interoperability and low quality of service. In the case of mixnets I
strongly believe that unreliable message delivery contributes just as
much to low quality of service as

Re: [messaging] Panoramix decryption mixnet messaging spec and design documents

[Trevor Perrin]

On Wed, Aug 9, 2017 at 2:53 AM, dawuud  wrote:

>
> I just wanted to make you all aware that I've published our design
> and specification documents for our mixnet project:
>
> https://github.com/Katzenpost/docs

[...]

> https://github.com/Katzenpost/docs/tree/master/specs

[...]

> https://github.com/Katzenpost/docs/blob/master/drafts/mixdesign.txt

[...]

> https://github.com/Katzenpost/docs/blob/master/drafts/user_interface.txt



Hi David,

Hope you don't mind belated comments:

This is an ambitious protocol stack!  I think the different layers and
choices are something like:

Mix packet format = Sphinx
Mix strategy = Poisson Mix (a simplified "Stop-and-Go Mix")
Mixnet topology = Stratified
Dummy traffic strategy = Loopix
Reliability/retransmission = Stop-and-Wait ARQ
Congestion control = "Source Quench" from mixes to providers
Link protocol = TCP/Noise_XX
End-to-end protocol = Email/Noise_X

It's interesting to see everything needed for a full mixnet architecture.
I imagine these decisions might be different for different applications, so
I hope you're building modularity between components.

"Sphinx" and "Stop-and-Go mixes" seem particularly reusable within
different architectures.  High-quality specs and code for them would be one
great outcome here.

(Though there's room for debate even within those components.  For example,
SURB support in Sphinx adds complexity and requires an unusual
"large-block" cipher.  SURBs don't seem necessary for Loopix, and I've
wondered whether dropping SURB support would make things simpler [1])

Anyways, the hardest decisions are probably around "mixnet topology" and
"dummy traffic", since this is where real-world economic and deployability
concerns come in:
 * Who is going to run mixes?
 * How tolerable are latency and dummy-traffic requirements for real users?

The Loopix paper [2] presents examples with:
 * Several independent mix nodes
 * A server acting as "provider" for each few hundred users
 * Each user sending a dummy message every few seconds (or faster!)
 * Each user downloading messages or dummy traffic from their provider at a
constant rate

Those all seem like difficult requirements for real systems, so I'm
wondering about your thoughts on near-term deployment.

In general, the security vs. practicality tradeoffs seem pretty brutal for
mixnets.  Most papers (like Loopix) push the slider towards the security
end so they can achieve their security goal, but with parameters unlikely
to be deployed at any scale.  I'd be more interested in the opposite sort
of analysis: how much security can be eked out of "minimum viable"
deployments.

Anyways, those are scattered thoughts.  It's great to see people working in
this area, keep us posted!

Trevor

[1]
https://moderncrypto.org/mail-archive/messaging/2014/000456.html
https://moderncrypto.org/mail-archive/messaging/2014/000471.html

[2] https://arxiv.org/pdf/1703.00536.pdf
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging

[messaging] Panoramix decryption mixnet messaging spec and design documents

[dawuud]

Hi,


I just wanted to make you all aware that I've published our design
and specification documents for our mixnet project:

https://github.com/Katzenpost/docs


Our design is based off of the Loopix anonymity system [LOOPIX].
   [LOOPIX]Piotrowska, A., Hayes, J., Elahi, T., Meiser, S.,
   and Danezis, G., “The Loopix Anonymity System”,
   USENIX, August, 2017
   


Firstly, we wrote specifications:
https://github.com/Katzenpost/docs/tree/master/specs

But that's a lot of reading and goes into fairly high detail suitable
as implementation guidelines. When I was at PETS2017 I repeatedly explained our
mixnet messaging system to people and I now realize we need a shorter document
to serve this purpose of introduction. Here's a rough draft design document
which can hopefully serve as an introduction:

https://github.com/Katzenpost/docs/blob/master/drafts/mixdesign.txt

Here's a rough draft user interface design doc:

https://github.com/Katzenpost/docs/blob/master/drafts/user_interface.txt

If you hate the name Katzenpost, I totally do not care at all. We can
change the name later. In conclusion, let's talk about mixnets. We can
talk mixnets here and/or on our mixnet mailing list:

https://lists.mixnetworks.org/listinfo/mixnetworks

If you hate mixnets then you are probably just grumpy and should go
for a walk and breath some fresh air.


Cheers!

David Stainton


signature.asc
Description: PGP signature
___
Messaging mailing list
Messaging@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/messaging