Maginots and AK-47s

the weakest spot of crypto is not crypto

Arguably, the most widespread blunder in the design of cryptographic systems is perfectly described by XKCD#538: an unbreakable code may be broken by some other cheap non-cryptographic means. Let’s call it the Maginot syndrome. The recent NSA-Google wiretapping story is one perfect example: Google’s data was traveling by “internal” data links in clear text, meanwhile an “internal” link was actually some cable in the ocean that NSA (and many other entities) could wiretap. Another nice example is the Silent Circle SCIMP, a crypto messaging protocol developed by so many luminaries. SCIMP doc at page 24 has an example of its on-the-wire message format which, if slightly exaggerated, looks like:

<message type=”chat” 
 from=”snowden@nsa.gov”
 to=”glenn.greenwald@guardiannews.com”
 id=”0FF6CF98-32FE-4EED-9DEF-D66A0E50EA8F”>
 <body/><x xmlns=”http://silentcircle.com”>
 ?SCIMP:ToTalle_EncRYPtiD_DaTA_HEre

Sometimes, once the fact of the communication is known, XKCD#538 becomes fully relevant to the rest of the story. In any case, knowing message exchange patterns provides plenty of information to the observer (in academia, they call it social network analysis).

The recent Telegram story is just another example of that Maginot syndrome. One mishap was already uncovered. Another issue is the long list of permissions the Telegram app needs. Third issue is the amount of information kept on their servers: they know who is talking to whom and in most cases servers know what has been told. Given that Telegram is funded by one brother and developed by another, their parents probably is the single point of failure of the entire system (which is the fourth issue).

So, the problem is that transport-, infrastructure- and hardware-level issues tend to undermine the very purpose of crypto in so many cases. Devising a new enhanced crypto scheme is fully subjected to the law of diminishing returns as the protection is much thinner in so many other points.

Well, one shot at a better solution for a transport is BitMessage, a messaging protocol developed along the lines of BitCoin. To the best of my understanding, BitCoin in turn was developed along the lines of a digital notary scheme, which makes perfect sense. But that does not make much sense for a messaging system unless your top objective is non-repudiation. (Please let me know of any other attempts but BitMessage.)

Suppose, we are tired of crypto-Maginots so we want to develop a crypto-Kalashnikov. Some simple, cheap and reliable piece of technology that actually makes a difference. Something other people will blame us for. How this C-AK system may look like?

The first step is to separate layers according to the level of disclosure:

• end user mailboxes know who is writing what and to whom,
• middle-layer post offices (POs) know who is writing to whom,
• the core knows nothing: no senders, no recipients, no content.

How can we achieve that? Well, suppose that the core functions as a sort of a DHT: it only has put(key,data) and get(key,data) methods, where a key is some uint64_t and data is a completely opaque cryptogram, i.e. a binary blob. The data expires after some period. The key also “expires” in the sense it is not a permanent recipient’s identifier. For example:

key = (2^64-1) & SHA1(receiversPubKey+todaysNoonGMTUnixSeconds);

Then, the core effectively does message switching without much of knowledge of the actual content or even recipient of the message. We may imagine the core as some number of distributed servers managed by different entities dividing their key range responsibilities on the basis of a consistent hashing scheme. Then, every day, some user’s incoming mail is put on a different core server. Nothing prevents changing keys on an hourly basis.

Then, a post office has a basic API of: receive(publicKey) and send(publicKey,data). A post office’s behavior boils down to reinserting messages into the core till they are acknowledged or expired and polling the core for new messages to its mailboxes.

So, a message is created in a user’s mailbox and immediately encrypted. The post office server receives the recipient’s public key and the cryptogram and puts it into the core at the calculated current hash-key. The receiving post office collects the cryptogram and later delivers it to the recipient’s mailbox. The recipient’s mailbox app decodes the message so the user may finally read it. Note that the receiving post office only believes the message is for one of its clients. There is no way to know for sure (not to mention that sender and content are encrypted).

This C-AK architecture is nothing but a sketch, but let’s list some obvious benefits of the approach:

• it follows the “complexity at the edges” principle; the core is a really dumb DHT;
• as a consequence, virtually no architectural decision is cast in concrete; the particular crypto scheme or message format is decided and implemented entirely by end-points;
• the architecture is federated (like XMPP or SMTP), so there are no single point of failure or ownership issues;
• delivery is randomized, so a faulty node may be out of the loop in an hour;
• sender, receiver or content are unknown at the core, which is the sweet spot for wiretapping;
• delivery is not dependent on physical servers, domain names and such, so the secret key is the only thing that makes you a participant irrespectively of the entry point (i.e. post office) you use at the moment (that is the general upside of the data-centric approach, same with Usenet or git);
• mailbox-to-post-office access tech is not dictated as well, a minimalistic HTTP/JSON implementation or an SMTP/POP/XMPP front-end are equally possible.

The downside of AK-47’s simplicity is its lower accuracy; let’s list some obvious C-AK shortcomings as well.

• Given someone’s public key, which is essentially an address, anyone may listen to incoming cryptograms. Although, if we take the “NSA factor” seriously, then we should consider every wire tapped. Still, the physical aspect of security is not something to be brushed off too easily.
• DDoS scenarios are not covered; there are possible approaches like rate limiting, private channels, renegotiated keys and secrets. Same applies to spam.
• Incentives are rather important; successful federated protocols normally have some incentive scheme baked in (consider BGP, SMTP, BitTorrent, especially BitCoin which is too good on that front). One possible approach is to link post office and core relay functions, i.e. an entity that holds a post office must contribute proportional resources to the core.

Again, this post mostly aims to provoke some discussion and my actual point is: the weakest spot of crypto is not crypto.

Thanks.