Silk Road forums

I would like something that could replace Tormail this year, and that relies on no central server. That is Torchat's greatest strength. Nobody can take it down or overwhelm the network / server, like what appears to happen to Tormail every time there's a database error. The trade off is that Torchat is a live messaging system. Both parties must be online at the same time. If it stored messages like BitMessage, that would be perfect.

Freenet sounds like what you want.

Also, if they are anonymous users connecting over Tor, then why does it matter? Why not ask for the message directly?

Because I don't trust the anonymity of Tor and I am trying to make a system that can resist the NSA . If I simply wanted to make a distributed encrypted forum that uses Tor I would have been done last year. The anonymity part is what really makes things fucking hard.

Quote from: kmfkewm on August 01, 2013, 09:00 am

Quote from: astor on August 01, 2013, 08:16 am

How can you ask a server for a block of data without the server knowing which block it is?

The answer to that question is in several papers on Computational Single Server PIR (CPIR). Please let me know if you find one that will work for what I am trying to do, I will read it after you suggest it to me .

LOL. I thought the explanation with Alice and Carol was in response to my question, and I thought, that allows Carol to determine a message for her exists, but still, how does she ask the server for that message? I suppose she could ask for the whole database or a block of it that happens to include the message, so there's some plausible deniability.

Also, I want to know what Alice and Carol's secret is!

How she asks the server for the message after she determines it exists is part two hehe. I suppose she could do some private stream searching algorithm, but as far as I know all of these sort of assume that each message is padded to the same size, gah. Alice knowing that the server has a message for her is good, it would be even better if she could determine where in the database the message is. The simplest solution would be for the server to keep track of every contact string and send to every client the list of contact strings, the size of the message they point to, and where in the database they start. That is bandwidth prohibitive when things scale up to hundreds of thousands of clients. Assuming every message has 1 kb of associated data, and there are 500,000 clients getting 10 messages a day, that means there is about 4.8 gigabytes of metadata a day. Sending that to 500,000 clients is not going to fly, so the clients need to be able to query for the data that is relevant to them without the server being able to determine that the data is relevant. I think with a bloom filter and PIR I can hopefully maybe get it so the clients can determine if they have a message waiting for them with low bandwidth, but then the problem is how do the clients find out where the message to them is in the database, and how do they get it without the server knowing it is the message they got.

The biggest issue I am running into is that all of these systems seem to really like the idea of related data being blocked together into sequential buckets that are all padded to the same size instead of thrown up all over the database with 1kb here and 4kb there. Perhaps I could have every message broken down into like 1KB packets, with each packet tagged with the contact string and obtained with private stream searching. But the problem is that the server cannot learn the total number of packets that an individual message consists of. I want to have messages of various different sizes and let clients get them from random spots in the database, and then padding to a certain size, without the server being able to tell the number of individual packets that are returned for a single keyword search. Gah it is really hard to even think about this shit for me honestly, it is a level or two beyond what I know about cryptography and math, and I am struggling to think of how to do it. It is like I am right on the verge of a break through but I just cannot quite get all the way there. I wish I just knew some papers that will work to do what I want when I implement them, I have a much easier time being told what to implement, getting the paper and studying my ass off until I can do it, than I do trying to figure out exactly how to describe what I want and then reading fifty papers trying to find if any of them sound similar hehe.

So basically the database server never knows who it has a message for, only that said message exists. The more "Bobs" there are, the less likely the knowledge of the recipient of such a message is, which would be further obscured by increasing string length?

Yep. In Pynchon Gate the server knows who it has a message for, but not who gets the message. I want a system where the server doesn't know who it gets a message for and doesn't know who gets the message, to protect from network analysis attacks when I scale things to group communications.

Thanks for suggestion of Percy++ SS, it looks like it has a very nicely written paper and I can probably figure out if it will work fairly quickly. It actually looks quite promising right now, after a brief read of the whitepaper, but I need to be sober and spend some time reading it before I conclude it will work. It is already implemented in C++ though, and has a really nice and well explained whitepaper, so it shouldn't take me too long to see if it will work for me. The biggest problem I see with it immediately is that it is multi-server, I would prefer computational single server PIR, but distributed database isn't the end of the world it just adds some to the complexity.

I note from the paper that it was actually designed with the intention of improving on the pynchon gate PIR, so in either case I will probably use this for Pynchon Gate if I end up not being able to do what I want.

of PIR, an “item” is often thought of as a single bit out of
an n-bit database, but it could also be a “block” of size b
bits. In the latter case, the n-bit database is considered to be
composed of n/b blocks, each of size b bits.

I really need a PIR system where it is a single bit out of an n-bit database, pynchon gate style PIR works great for blocks but when it comes to single bits it is worse than everybody gets everything.

A number of
applications have been proposed for PIR, including patent
and pharmaceutical databases [1], online census informa-
tion [17], and real-time stock quotes [17]. The Pynchon
Gate [11] shows how to use PIR for an arguably more real-
istic purpose: retrieving pseudonymously addressed email;
it argues that PIR is a more suitable primitive for this appli-
cation than previous proposals.
    A trivial solution to the PIR problem is simply to ask
the server for the whole database and look up the desired
bit or block yourself. To make things more interesting (not
to mention practical), we analyze the communication cost
of the protocol—the total number of bits transmitted—and
insist that it be sublinear; that is, less than n.
    There are two main types of PIR: information-theoretic
and computational. In information-theoretic PIR, the server
is unable to determine any information about your query
even with unbounded computing power. In computational
PIR (CPIR) [3, 8], the privacy of the query need only
be guaranteed against servers restricted to polynomial-time
computations. Note that in the information-theoretic case
the unbounded power is only to be used to try to compro-
mise your privacy; in either case we still insist that you and
the servers use only polynomial-time computations in order
to perform the protocol.
    It is an unsurprising fact that information-theoretic sub-
linear PIR is impossible with a single server. However, it is
possible when there are l servers, each with a copy of the
database—assuming that the servers do not collude in order
to determine your query. A t-private l-server PIR is a PIR
system in which the privacy of the query is information-
theoretically protected, even if up to t of the l servers col-
lude. (Of course, it must be the case that t < l.)
    Beimel and Stahl [2] investigate the case where servers
can fail to respond. In this event, it is important that the

Pretty much here is where I am at. I have been working for about two years now coding a system for secure communications, and have tens of thousands of lines of source code already done. I have been sort of designing this thing as I go. At first I tried to make entire design by myself. That was a bad plan. Then I focused on the academic literature and implemented other peoples ideas. That was a much better plan. I have Sphinx cryptographic packet format completely implemented in C (as well as LIONESS block cipher that it uses). I have greatly wrapped OpenSSL crypto library, and can do ECDH key exchange, AES counter encryption, MAC, and all of the other stuff, with a simple call. I have a NIST password entropy estimator implemented, as well as a bloom filter, as well as wrapped database libraries for easy database management, secure wipe, tons of shit. I also have Alpha mixing mix network system almost fully implemented, and distributed directory servers almost fully implemented, tons of networking code, and a lot of other shit I am sure I cannot remember right now (I have taken a multi month break on working on this because of various reasons). I also have the PIR of Pynchon Gate implemented. So I am close to having the entire Pynchon Gate whitepaper implemented, using Sphinx and Alpha mixing for forward messages, with automatic ECDH between communicating parties, etc. I also have Tor wrapped up and integrated, as all mixes are run as hidden services and all clients use Tor.

But I want to diverge from Pynchon Gate at this point. I don't like that Pynchon gate has a semi-trusted nymserver that gathers all messages to me and then puts them in a bucket that is distributed for PIR. I also don't like that Pynchon gate assumes person to person communications rather than group communications. I want to remove the nymserver by having contact strings between communicating parties. Essentially the communicating parties do ECDH key exchange and have now shared secrets which can be iteratively hashed out to tag to messages for identification. Now I do not need a trusted nymserver that gets messages for Bob and puts them in Bobs bucket, because each individual message is tagged with an unlinkable string that Bob can identify is for him. Okay that is great, except for two things. One thing is that Pynchon gate has buckets that are all padded to the same size, so every PIR cycle Bob always gets his entire bucket of messages and then sorts out the individual messages. This is made possible because of the Nymserver, which bunches all messages to Bob together for retrieval with block PIR. So instead I want Bob to have these contact strings for a thousand people he is communicating with, and every cycle I want Bob to query the PIR server to find out which of his contacts have sent him a message. This is what I am talking about in my original post, how Alice can ask Bob if he has a message for her without Bob knowing which message Alice is asking for. After Alice finds that Bob does have a message for her she then needs to retrieve it. I am a bit shakey on this part as well. If messages are not all the same size then using block PIR to get messages will be a waste of time since the message sizing leaks the message. So all things must be padded to the same size before they are retrieved. But I would rather for the user to be able to do non-sequential PIR to get say 6 KB of messaging data tagged with one contact string in one spot of the database and 2 KB of messaging data tagged with another contact string in another part of the database, and then 2 KB of padding, instead of the user having all of their total message data put in a sequential bucket with 2 KB of padding. So essentially I am working on figuring out

1. How can Alice ask Bob if Bob has a message for Alice without Bob knowing which Message Alice is interested in?
2. Once Alice knows she has a message, how can she get the message without leaking what the message is? 

without having to individually pad each message to the same size (bandwidth prohibitive) and without a trusted nymserver being able to group messages to Alice together so she can get them (padded to the same bucket size) with sequential byte PIR.

If I can find good answers to question 1 and 2 then I will have a very very secure and anonymous encrypted messaging system that can scale to group communications. If that fails I will probably just fall back to finishing Pynchon Gate, but honestly it is not exactly what I want. The hardest part is making shit scale to group communications, doing person to person is soooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo much easier than group communications.

I want Alice to be able to ask Bob if he has a message for her, without Bob knowing which messages Alice is looking for. The easiest solution is for Bob to tell Alice all of the messages he has. This is great unless there are 500,000 users sending 10 messages a day each tagged with 128 bit string. Now the meta data alone is about 76 megabytes, and there are 500,000 users so Bob now takes about 36 terabytes of bandwidth a day just letting everybody know the metadata of which messages are available. If everybody checks for 1,000 messages a day and the PIR cost is even 512 bits per query, 500,000 * 1,000 * 512 = 29.8 gigabytes of bandwidth for all clients to check for so many messages. But the results are dependent on the cost of the PIR, and the only PIR I know would not work well for this at all (only theoretically would it work, in practice it would be absolutely stupid).

Essentially you and I do ECDH key exchange and come to a shared secret. We communicate with each other through Bob by tagging messages with our shared secret prior to uploading them to Bob anonymously. Now you know the message tags that indicate that a message is waiting for you, but you cannot ask Bob "Hey do you have this message tag?" because then Bob knows what message will be for you. So you need a way to ask Bob if he has something without him being able to tell what you are asking if he has. The solution could be for Bob to keep a bloom filter. Bloom filter is essentially a block of bits , a fresh bloom filter all bits are set to 0. When Bob gets an item he takes its hash value, translates the hash value into a series of numbers that map to a bit position in the grid, and Bob sets the bit positions in the grid to be 1. If all bit positions mapping to an inserted item are set to 1 then you can query the bloom filter and see that the message has probabilistically been added. So now we have Bob with his bloom filter, and he gets these message tags when people send messages to him for others to download and he puts the tags in his bloom filter. Now I can ask Bob if he has the message by doing PIR to get the bits at the positions in his bloom filter (Since I know the message tag I know the bits that will be set to 1 if the message has been added, since I also have the public parameters of Bob's bloom filter). If after I do PIR and get all of the bits they are all 1, then I know Bob has my message, if any of them are 0 then I know Bob doesn't have my message, but in either case Bob cannot tell which messages I asked him if he has. And now Bob doesn't need to send me and 500,000 other people 76 megabytes a day.

So you use Tor and tell me you use BobVPN. So now that is great because I can go to BobVPN and see who all is using Tor. Okay there are twenty people using BobVPN and connecting to Tor, you are probably one of them. Now if I can watch traffic over BobVPN I can quickly pinpoint your traffic with fingerprinting attacks, since I already see the posts you make here and the size of the posts. Only one of the twenty people using BobVPN to connect to Tor is likely to have traffic pattern correlating with the posts I can see you making on the forum here. Also many VPN providers keep logs of who is connected to the VPN when, even if they don't keep traffic logs. So now I can use these logs and see who of the twenty are connected to the VPN when I see traffic from you on this site. Over a small period of time I can use intersection attack to deduce who you are. You could say well my VPN keeps no logs blah blah, and I say fine that is great but you still have essentially changed your security model from Tor to your VPN provider, and that makes life easier for me if I am trying to trace you.