I really like these ideas, especially the use of ephemeral addresses to achieve anonymity and perfect forward secrecy. If you are looking for volunteer developers to help get a proof of concept off the ground I would likely be pretty keen.

I do however have a few questions ...

Offline use

Im a little concerned about the offline-use-case. I understand that advertisement packets have a limited lifespan (any idea how long?), so if I shutdown my machine for the weekend only to reconnect the following monday, it is possible that I miss advertisements meant for me. This means I would need to interrogate a 'storage node' at the cost of giving up valuable information that may help an attacker link an address with my real identity.

For an email replacement, the offline-use-case would be quite common, peers would come and go rather fleetingly. But perhaps this is not your target market, and one of your assumptions is that people will generally stay regularly connected.

Attacker makes lots of connections, analyses origin of permission packet

Thankfully you have included link-layer-encryption, so assuming that the crypto is good, it makes it harder for a global passive adversary. Am I right in assuming that any attacker trying to make large numbers of connections in order to perform statistical analysis on say the origins of a permission packet, would be very quickly blacklisted? i.e. due to the attacker needing to honour a bandwidth/storage 'contract' with each peer he connects with?

What about well funded attackers?

Global packets and scalability


So here I get a little worried. "a peer must continually relay all ad packets within the network".

Say we have a network with 1 Billion peers who are all actively sending messages. For each message that is sent, we require numerous advertisement packets to be broadcast on the network. Depending on the lifetime and regularity at which advertisements are resent, the number of global packets that need to be move across each peer-peer link will be huuuge.

If I have interpreted this correctly, how can the network scale and how can low-bandwidth/low-storage nodes participate?

Getting permission to communicate, both parties need to be online?

Do Alice and Bob need to be simultaneously online for Alice's permission packet to reach Bob and for its response to come back to Alice? Or are permission packets also referenced by advertisements in a similar way to messages?

Enforcing behavioural contracts

I like your idea of making sure that nodes behave correctly and continue to store messages they have agreed to store etc.

I am wondering though, do peers need to be exact mirrors of each other? How can Alice check that Bob still stores messages for which Alice does not store herself?

What happens when Alice becomes disconnected from the network, and reconnects to a different set of peers? How do the new peers enforce her (preexisting storage contract) ? Or will she agree to a new contract when she makes the new connections?


Sorry to overload you with questions, im just trying to understand your proposal a little better

Hey greBit,

First off, really good questions; I left out a few of my thoughts from the paper, and you managed to hit a good portion of them!  Thanks for taking the time to read my paper!

For offline use, one could use a storage peer and query all messages in a large address range to preserve anonymity, but as you mentioned, that wouldn't be possible for low-bandwidth users.  One of the things I sort of glossed over in my paper that is important to offline use is the fact that instead of using special acknowledgement messages like Bitmessage, a peer can simply send another message back with an additional ephemeral key to let a peer know that he received his message.  In other words, acknowledgment messages are sent in the form of regular messages.

With this in mind, I think the easiest way of approaching offline use would be the following scenario:

1) Alice sends a message to Bob, who is currently offline

2) After waiting a certain amount of time, Alice never receives a message from Bob acknowledging that he received the message

3) Alice then sends a permission packet to Bob to restart the conversation with a new ephemeral key, and then resend the previously missed message.  One probably doesn't need to go through the whole permission packet process though, seeing as the one-time/ephemeral address concept I use is really only to mask bias in downloading messages (ie: the origin of broadcast for permission and ad packets is anonymized assuming the min spanning tree assumption)

4) Alice can continually resend permission packets every so often until Bob is back online

And yes, users need to be online to answer permission packets.  No reply means the user if offline.  Permission requests should be re-sent randomly, to preserve anonymity (ie: not have a constant amount of time hardcoded in the client)


Attackers making lots of connections is a subset of an area I'm still thinking about, that area being how to best bootstrap the network and how to handle conencting to new peers.  If a peer could gurantee that he is connected to every peer in the network, or even a large subset, he could theoretically start to aproximate network topologies and reduce anonymity depending on how peers are choosing to broadcast ads and permission packets.

To experiment and to try and find out best practices for maximizing anonymity in proportion to the amount of users in the network,  my next step is to create a visual simulator to aproximate network flow and p2p interactions.  This will be used as a proof of concept to estimate the anonymity of users given different topologies, as well as show how the network can react and defend against attempted attacks.  If this goes well, I'll then start client development.

As far as global packets and scalability, that is going to come down to coming up with clever ways of compressing address data, which is on my list of things to think about.  Another thought I had regarding this was to allow messages to be tagged as belonging to a certain category, such as e-mail, files, or twitter-esque service messgae, and then let peers decide what categories/services they want to participate in and relay (ie: think of this as a multiplexing different bitmask networks into one client)

For your behavioral contract question, the beauty of ads is that by relaying an ad to another peer and making them aware of the message's presence, you are simply letting them know that you are serving as a contact for obtaining this message; you don't necessarily have the message cached when you go to pass on the ad.  That way, you only ever checkup on a peer after they have requested a message from you and have received it, meaning you always know which files they should have from you.

When a peer disconnects, new contracts/agreements must be made.  If a peer disconnects too frequently, the peers he was connected to will blacklist him.

With regards to blacklisting, I had only thought of it as being an individual list per peer when I originally wrote the paper.  I'm not sure yet if network knowledge can be done in a trustless manner, as I'm still exploring that.  One idea I had was that you could allocate weight/trust to a node everytime he successfully transfers a message that belongs to you, but it would need to be done in a way that doesn't create an attack vector for discovering which messages you're interested in.

Thanks again, and keep those questions coming

Hey Tommy, thanks for the replies!

I guess I am still a little concerned about the scalability issue. Despite the advertisements being quite small, I see this quickly becoming a bottleneck in similar way to the problems caused by the receive-it-all approach of BitMessage.  

What I have understood is that these advertisement packets will actually be flooded across the network (?) which is pretty expensive, and as the network size grows, the cost will increase non-linearly.

So I feel that you may need to find some way of partitioning the network in order to keep in manageable.

---
Anyway, allow me digress and detail a few of my motivations so we can see if there is some common ground for a potential collaboration

Basically I have a few projects in mind that depend on a layer one could call 'anonymous-message-passing'. The functional requirements being as follows:

• Alice can send a private message to Bob
• Alice can send a public message to the world (publishing model)
• Bob may be offline and can 'check for messages' by connecting to the network. His 'inbox' is stored by the network.
• Anyone can read any message. Private messages are kept private with cryptography.
• Messages are sent reliably, Alice should not need to receive an ACK, in the same way that I do not expect an ACK from gmail

Some of the key non functionals:

• Perfect forward secrecy
• inability for someone other than the person concerned to be able to relate a network identity(pub key) with the real world identity (an IP)

I believe that if this is done well, with a combination of a good technical solution with the appropriate incentive structures for participants, this could become a very useful tool.

I think this could go far beyond just having an alternative to email. When you consider that the endpoints of a communication could be API servers, HTML5 web-apps etc, there is a ton of things this could be useful for.

One example is that this could help remove reliance on Tor/I2p, since the anonymity is taken care of. Silk-road could be re-implemented as an open source browser extension for example!

So your work is a fine start to all of this. Please keep me updated with your progress on your paper and simulations etc and I will surely bother you soon with some more questions.

In the meantime, here is one:

Why not use an anonymous-PUT, anonymous-GET DHT as a basis? I just found a paper on a DHT which aims to do just that http://arxiv.org/pdf/1203.2668v1.pdf and of course we should not forget Freenet which was designed for this very purpose.

Could a messaging system not be implemented as a thin-layer over the top of 'Octopus' Freenet I2P ?

Interesting ideas with BitMask.
If you are have ideas to integrate with Namecoin identities also you can start a thread on the Namecoin forum also.
http://dot-bit.org/forum/index.php

Looks like he is quoting outdated critiques of BitMessage's early encryption.

BitMessage has all the potential of becoming the first crypto currency that will really offer intrinsic value and will be backed by something. It is backed by a 100% reserve stored security of your Internet communication. It'll be the first anti-NSA (and the likes) currency. Good job NSA! You're the driving force and engine for developing secure Internet communication systems and protocols. Keep up building big computer centers!

I see no reason why BitMessage insists on addresses being a hash of the public key rather than the actual public key.  It isn't like anyone can remember or will manually type in the address.  This would allow you to get rid of the entire discovery step.

The ACK can be delayed by several hours and thus no one would know who sent the ack...

You need link-level encryption, plus modify the broadcast algorithm to randomly pick only one of your peers to broadcast to first.   Your peer would randomly pick one other peer to broadcast to... if after X amount of time you have not received an inv from all of your other peers you pick another random peer from the subset that haven't acked and broadcast to them... everyone else is doing the same thing.

Then increase the connections-per-node to 32.

The result of this kind of broadcast is that a node that is 'connected to everyone' would only have a 1 in 32 chance of detecting the first broadcast, a 2 in 64 chance of detecting one hop removed, a 4 in 128 chance of first receiving the message after 3 hops.....   At this point it becomes clear that being the 'first to broadcast' something as seen from a peer connected to everyone becomes meaningless... and link-level encryption prevents outside observers from watching the propagation of the message.

The only remaining attack is to man-in-the-middle the ECDH exchange used to establish the link-layer encryption...

 

Easier to copy/paste than the huge public key, + possible deterrent to quantum computing?

I have attempted to use Freenet's mail... it doesn't work!

I believe this sort of hashing is helpful for spam prevention.  In a network of this type, an identifier is needed for determining whether or not a message is intended for a specific peer, so that the peer can then retrieve and decrypt it.  If a public key is used as an identifier, any peer could simply monitor the network, scrape these keys, and send out spam messages for the user to decrypt.  If a hash is used instead, not only can a peer still identify that a message is for him, but he can reject any messages that fail to decrypt properly, as a result of spam bots not knowing his public key.

With this is in mind, users still need a way of securely sharing public keys, while minimizing spam to the simplest of problems, that problem being whether or not you want to speak to someone.  I propose such a way in the Bitmask paper with regards to permission packets and identity profile messages.  Think of it as using skype, and only accepting communication from either those who have added you to their list of contacts, or vice-versa.