[liberationtech] New protocol sacrifices bandwidth for metadata privacy

[Marc W. Abel]

/********
Aymeric Vitte wrote:

Maybe I did not find it, but is there a spec/description how it works
exactly (something else than the man pages)? If I understand correctly,
every peer broadcast its keys to everybody, then I (IP1) find out that
IP2 has my keys and I send the traffic messages directly to IP2, since
everybody is connected to everybody and discussing with everybody this
is difficult to trace, correct? But we might detect that IP1 is
discussing with IP2 for real, even if you mention that clique is not
about anonymity maybe it can be made more difficult.
********/

Hi Aymeric,

Thanks for all of your work with Peersm.  I am in the process of getting a paper submitted that will have a more thorough description of Clique's workings.  But questions are welcome at all times!

If these four assumptions hold:

1. The /only/ information an attacker has is what one or more intermediate routers can see ("plain old wiretapping" is employed).

2.  Clique's block cipher is secure.

3.  Linux's pseudorandom number generator /dev/urandom is secure.

4.  Clique's countermeasures against fine-grained timing analyses are adequate.

Then my answer to your question is:

To an observer with no keys, all Clique traffic looks the same, and all peers treat each other identically.  Alice can't just send Bob a message; if she is to send anything at all, she must continually send messages to everyone.

If an attacker does not have the key that is shared by Alice and Bob, then spotting traffic between them isn't merely difficult; it's impossible.  It is no longer true that "we might detect that IP1 is discussing with IP2 for real".

Clique's key discovery system is solely for finding peer IP addresses.  I'd rather not have this system at all, but considering the threat model Clique is designed for, the communicants have no other means of advising each other of IP address changes without risk of being discovered.

The way Clique's key broadcast protocol works is to encrypt a 128-bit block with the key in question, and set that encrypted block in a randomly selected slot of the outgoing packet.  There are 34 such slots, so a single packet can advertise as many as 34 different keys.  The rest of the packet is cryptographically secure random noise.

The only way, under the above four assumptions, that a key advertisement can be visible to someone is if she happens to hold the key in question.  In this case, the block will contain the following after decryption.  If the block didn't fall within expected parameters, the key did not match.

32 bits of zeroes
32 bits for the sender's IP address*
43 bits of time since UNIX Epoch, in seconds**
20 bits of microsecond within current second
  1 last bit that is also zero

*The sender's IP address is as it would be viewed from the recipient's perspective.

**This field has many leading zero bits, but no Year 2038 problem!

Note that in order to pretend to have someone else's key, but not actually have it, an attacker would need to replay a valid key discovery block that contains the correct IP address to which the key is bound.  Such an attack would work backwards:  all the imposter can do is send the truth.  Note also that the Clique protocol never has any peer forward any message.

Best wishes,

Marc