Peer to peer Tweeting, explored

Had another laymen discussion with my dad today (laymen since he's a statistical physicist and I'm a hacker, so neither of us are experts on information theory) and became even more convinced that Twitter could only truly unfold its potential as a political censorship-buster if it worked in a decentralized fashion, as I described some weeks ago.

Here's a bit of a brainstorm, listing several points.

Requirements

Short messages must be distributed quickly throughout a scalable network without relying on any individual node. Individual peers must not be able to trace messages back to their physical origin, yet messages must be authenticated as originating from common sources to establish a reputation system.

Authentication

In order to prove that a message originated from the same source as another message, both can be digitally signed using a public key scheme. While the paper on Off-the-Record Communication, or, Why Not To Use PGP warns that signing in this fashion negates deniability, that seems to be an inherent price paid for one-to-many communication. Multiple recipients are by definition multiple witnesses to the exchange.

What doesn't seem to be necessary is an authentication of the intermediary nodes. IE, if a message is sent by Alice to Bob, Bob passes it on to Carl, and Carl sends it to Daniel, then Daniel has absolutely no need to know that Bob was involved in the chain. Alice's signature is enough to establish the message as Alice's message. (The security of Alice's secret key, and contingency in the event it is compromised, are separate problems.)

UDP

A popular tool of disruption (particularly in China) appears to be a manufactured interruption of TCP connections via an RST (reset) packet. The messages this protocol sends are by nature tiny (Twitter's great innovation) and could easily fit into a single UDP packet, crypto overhead and all (UDP's theoretical maximum is 64kB). UDP offers the advantage of being harder to eavesdrop on, immune to RST forgery, and able to be sent via broadcast and multicast.

A disadvantage is the loss of a handshake-based key exchange. Messages either have to be passed on in clear, or the initial introduction of two peers must include a key exchange that will be used for all succeeding encryption (regular expiration of the key may be a good idea).

Blind relays

As the requirements state, the origin of a message must be untraceable, as politically sensitive messages originate with valuable and endangered sources. Ideally, even the first recipient (Bob) should not be aware that they are in contact with the original author (Alice). That means that Alice would sign a message, pass it on to Bob, who would then pass it on to further peers without modification or further authentication. The number of hops a message has been through must not be recorded. Likewise, a precise creation timestamp (to within less than an hour) must not be recorded as Bob could then derive that all messages sent by Alice's computer are brand-new and likely originated with her.

The network cannot, by definition, notice circular transmissions, at least without journalling messages sent recently. But the journal doesn't need to be long to prevent a self-amplified flood - it would probably be enough to remember messages received in the past day, and drop any messages received again within that time.

However, this system still has some vulnerability: If Alice persistently sends her own messages to Bob, Bob will eventually notice that all his messages signed by Alice tend to first reach him from Alice's computer, and might guess that Alice owns Alice's computer. I can see two countermeasures for this that may or may not be mutually exclusive:

1. Alice needs to send her own messages to a few of a wide pool of recipients. When messages signed by Alice are sent by Alice's computer to 1 out of n peers with equal likelihood, then to each of those peers will get their first copy from Alice's computer only with 1/n likelihood. The larger n is, the less Alice's computer will stand out as a sender ot Alice's messages.
2. Bob must be limited to a small number of peers that will pass anything on to him. If Bob receives messages from n peers, then his likelihood of receiving a particular message from a particular peer is 1/n. The larger n is, the more suspicious Bob will be to receive multiple messages signed by Alice from the same (Alice's) computer.

Discovery without discovery

In order to keep peers blind, the second idea above dictates that no single node is allowed to explore a wide section of the network. When Alice introduces Bob and Carl to each other, Bob and Carl both know the other is one of Alice's peers. If Bob finds out a significant portion of Alice's peers, he might start guessing which of them sent her a particular message she passed on to him. More so, if Bob also learns Carl's peers, he can find the intersect of both their peers and try to triangulate the origin of a message he received from both Alice and Carl.

I note that tiredness increasingly instills paranoia in me, so some of the above might be less worrisome than I fear now (especially if Alice and Carl delay their messages by a random number of seconds, so Bob cannot guess whether the message he got from both Alice and Carl reached both of them via the same peer.

Godfathering

It goes without saying that to be secure, the network must not rely on any single tracker reachable via a public site (analogous to The Pirate Bay for BitTorrent). Even when the tracker is outside the censor's reach, access to it can be blocked too easily. My idea is that the prime contact ("Godfather", so to speak) of every new initiate is the person they received the software from. But this poses a significant risk of deception: When Eve gives the software to Alice, Eve has complete power over Alice's initial contacts. By feeding Alice only peers owned by a single entity (eg the Iranian government), Alice is unknowingly immersed in a hostile network - whenever she sends out a message, the government knows she wrote it. How do you ensure that the Godfather is not a double agent?

Will brainstorm more when I'm awake again.

News Category: 

Comments

I'm very much a cryptology novice as well (and know nothing of Twitter), but you should look into onion routing if you haven't already, specifically TOR. It has a lot of the same requirements that you stated, and you've figured out most of the fundamental weaknesses as well (doesn't it feel awesome when you discover stuff by first principles?).

How keys are exchanged is always a problem. Short of a key signing party, there's no way you can be sure that you're not being spoofed. And, of course, even with face-to-face contact there's always the possibility of social engineering hacks. Not to mention the fact that most users will not be technologically proficient, and most security holes will be due to errors on the lusers' part. C'est la vie.

But definitely an interesting topic. You've got a brilliant thesis right there.

- Dintiradan

I agree that the problem Onion Routing aims to solve is extremely similar to this one. I'm still trying to grasp some of its finer points to better understand what is already known. :)

There are some properties in this scenario that may make it easier than the Onion Routing problem - in particular, the lack of clearly defined end-points and persistent connections. Others make it more complex.

When I first began to toy with this concept, I also thought this is what I could eventually write my thesis on. Now I just need to get the academic background to actually get serious about all this stuff.

-Aran

© 2006-2012: All content, unless otherwise noted, is the property of Arancaytar. It may be copied and modified with attribution for non-commercial purposes. By publishing comments on this site, you grant Arancaytar a non-exclusive, perpetual license to reproduce and publish these comments along with any identifying information provided. (You may request your comments to be deleted or edited voluntarily.)