[liberationtech] New protocol sacrifices bandwidth for metadata privacy

[Marc W. Abel]

Greetings Natanael, Seth, Tom, Gregory, and the list,

Without exception, I have been delighted with the quality and 
thoughtfulness of your feedback. I am also very grateful for the time so 
many more have spent looking at the website as well as the tarball. It's 
been hard for me to resist responding immediately to each of your posts, 
but now that the pace has settled a little, I hope to slip in a 
thank-you and some responses without dominating the conversation.

NATANAEL, pointing me toward I2P's Bote Mail is a great help because I 
will be expected to demonstrate knowledge of and differences from 
similar systems.

SETH, your mention of Pond is similarly helpful. I also like Pond's 
threat model documentation, and I think that Clique should have a 
similar disclosure. You are right that Clique needs forward secrecy, 
something that I haven't a clue yet how to implement against the threat 
model Clique is designed for. This could be a whole new thread or two or 
three, but the very short explanation is that Marc thinks that P = NP 
and that protocols such as Diffie-Hellman may fail or already have 
failed. I don't maintain that I'm right on these points, but I do think 
our planet has too many eggs in the asymmetric cryptography basket.

Good news: Clique peers do not broadcast message traffic (although they 
do broadcast announcements about the keys they have available). It's 
actually not feasible to broadcast, because the peers negotiate their 
own connection speeds. A high-bandwidth peer would have a lot of work to 
do force-feeding traffic to everybody and keeping track of it. A message 
goes directly to the (most recent) IP address where its key has been 
observed.

I really like your comments about authenticating the host and hash, 
because I have only considered my own perspective. Yours is valid and 
will be shared by some. Prior to seeing your input, my view was simply 
this. Asymmetric cryptography is already suspect (P = NP today). 
High-profile implementations fail catastrophically. No server can be 
made physically secure. And most importantly from my perspective, Clique 
is designed with a very specific type of adversary in mind -- exactly 
the type of adversary who can issue browser-trusted SSL certificates at 
will. So in my mind (as opposed to the Reasonable Not-Marc User's mind), 
adding HTTPS (Everywhere!) to the server I wrote is only going to give 
the site visitor a warm feeling of overconfidence. If I don't offer a 
"secure" connection, I don't need to worry that you might trust it. 
Instead, you'll seek some other measure of assurance.

What I take away from your feedback here is that not everyone is Marc, 
and that I can address my concerns without heightening yours. I can add 
TLS support to Subpoena, the Recordless Web Server (that really is what 
I named it), and post a conspicuous warning next to the download link. 
Then we're both placated.

My comments about "truly unlimited computing power" stem from my 
original and eventual plan for Clique. Rijndael is only a fallback for 
users who don't want to use one-time pads. But implementing Rijndael is 
much simpler than implementing a workable, real-world OTP system, so the 
former got done first.

TOM, your comments are great also. You asked why I modified the Rijndael 
key schedule. Indeed I need to be careful how I write things on the 
website. I only "modified" the schedule in the sense that I eliminated 
it entirely (modified, in this case, by replacing it with an identity 
transformation). And "quasi-4096 bit symmetric cipher" wasn't a great 
wording choice either; there really are 4096 bits and there's nothing 
quasi- about it. At best, quasi- was meant to express that I can't 
guarantee key sizes to be directly comparable, because Rijndael does not 
treat all bits of the key identically (although it tries to approach this).

But your question still stands: why didn't I leave Rijndael alone? 
Because no one has answered the opposite question: why does AES insist 
on reducing the key space to such tiny sizes (128, 192, or 256 bits), 
when the only computational advantage of this is for an eavesdropper's 
benefit? It seems to me like the world has been on a Honey, I Shrunk the 
Keys craze since about 1970, and I am a skeptic. I have a lot more faith 
in the intellect of you four list members, or any four readers of this 
list for that matter, than I do in the strength of a 256-bit toy puzzle. 
4096 bits isn't an ideal fix, but I'm hoping it might buy a little more 
time than we have.

I appreciate your kind words about the decision and effort to have an 
implementation. It's one thing to say that something will work, but 
human factors need to be measured too. Even the little things, like 
"will people even hear about the software?" become part of the security 
discussion. And real implementations will be scrutinized better, with 
problematic issues found sooner.

Broadcasting questions: yes! If 30,000 users are connected at 50,000 
bits per second (unrealistic situation but easy to consider), the 
interval between packets between any two peers is around 49 minutes, and 
plaintext throughput between any two peers is about 16 kilobytes per 
day. This might not sound fast, but the application has to be 
considered, too. That would have been enough to command a submarine 
fleet, for instance, for many decades. It would easily swallow most of 
my personal correspondence, too, and even this list response if we slim 
down its headers. And yes, throughput creeps downward as we add users, 
but the elegance of this solution is that so few would want to fuss with 
it, I think there will be enough bandwidth for the 1% of the 1% who 
would give it a go.

Extensive consideration and countermeasures to DoS issues has gone into 
the protocol design, although there is never a final solution. This is 
one reason that working on real implementations is more fun than papers, 
because you need to be ready for real problems. "Deaf" attackers who 
spoof IP addresses that they can't actually receive messages to are 
precluded from joining cliques. Botnet machines that are behind NAT 
firewalls that they don't know how to configure can't join, either. 
There is a small (twofold) UDP packet amplification concern with the 
current peer discovery protocol; this could turn a clique into a 
platform for DDoS attacks, but much stronger amplification is available 
from more machines with other protocols.

GREGORY, the bitmessage reference is particularly helpful. You gentlemen 
seem to be writing my dissertation for me this week.

I'm thrilled with your candor about the "extremely concerning" 
modifications to Rijndael. We well know the sad history of unvetted 
cryptography mechanisms. And there is such a shortage of truly expert 
cryptographers, that few ciphers other than those standardized by NIST 
get a whole lot of scrutiny. Your concern about any departure from what 
is broadly reviewed, as well as healthy concern you ought to have about 
my credentials, are merited.

A choice had to be made. Trust that 10, 12, or 14 rounds of AES is okay, 
for the type of attacker contemplated by Clique's (unwritten) threat 
model? An upper limit of 256 bits on the key size? I couldn't. So I went 
looking for a middle ground. I was okay with the 
substitution-permutation network AES uses in principle. I kept the same 
S boxes, the same row and column operations, invented nothing, gutted 
the subkey system, added more rounds, and wrote the code. I tested that 
code against NIST's own AES test vector in appendix C.1 of FIPS 197, to 
ensure that my rounds work in the same way that theirs do. I had to use 
their subkey expansion in order to do this test, as I did not write 
anything to work with subkeys. One weak decision I made is that having 
that code tested, I removed the test code from the tarball entirely. I 
shouldn't have. I still have that test code and its output, and I will 
put it back.

The question I don't have the skills to answer, but hope I might find a 
credible answer for, is whether a string of independent and identically 
distributed random variables is stronger or weaker than a deterministic 
key schedule that has undergone peer review from a very small number of 
random variables. I think I've made the cryptography stronger -- a lot 
stronger -- but there are people who know a whole lot more about this 
than me. This is why I will be facing anonymous peer reviewers and a 
faculty committee; the end product will be a better considered one.

I might have a compromise that would leave you perhaps not wholly 
satisfied, but at least not feeling like you're stuck with my approach 
and no other option. I could add a command-line flag to clique-keygen, 
probably -A, that would do a full AES subkey expansion within the 
4096-bit key itself. If I go with AES-256, that would reduce the key 
strength by 1792 bits from my perspective, but it would guarantee that a 
complete AES encryption is performed on your data exactly by the book, 
with some extra bit twiddles to placate me. We can actually do this with 
two entirely separate AES-256 keys, doing everything by the book twice 
with 512 bits of source key material, plus 256 extra bits for the extra 
messing around. This option would require no code changes at all, except 
to the key generation utility. If there is a drawback from your 
perspective, it's that a user must opt in to this feature.

ALL, many thanks again. I look forward to more discussion as your time 
permits.

Marc