How to 'backdoor' an encryption app

Over the past week or so there's been a huge burst of interest in encryption software. Applications like Silent Circle and RedPhone have seen a major uptick in new installs. CryptoCat alone has seen a zillion new installs, prompting several infosec researchers to nearly die of irritation.

From my perspective this is a fantastic glass of lemonade, if one made from particular bitter lemons. It seems all we ever needed to get encryption into the mainstream was... ubiquitous NSA surveillance. Who knew?

Since I've written about encryption software before on this blog, I received several calls this week from reporters who want to know what these apps do. Sooner or later each interview runs into the same question: what happens when somebody plans a crime using one of these? Shouldn't law enforcement have some way to listen in?

This is not a theoretical matter. The FBI has been floating a very real proposal that will either mandate wiretap backdoors in these systems, or alternatively will impose fines on providers that fail to cough up user data. This legislation goes by the name 'CALEA II', after the CALEA act which governs traditional (POTS) phone wiretapping.

Personally I'm strongly against these measures, particularly the ones that target client software. Mandating wiretap capability jeopardizes users' legitimate privacy needs and will seriously hinder technical progress in this area. Such 'backdoors' may be compromised by the very same criminals we're trying to stop. Moreover, smart/serious criminals will easily bypass them.

To me, a more interesting question is how such 'backdoors' would even work. This isn't something you can really discuss in an interview, which is why I decided to blog about them. The answers range from 'dead stupid' to 'diabolically technical', with the best answers sitting somewhere in the middle. Even if many of these are pretty obvious from a technical perspective, we can't really have a debate until they've all been spelled out.

And so: in the rest of this post I'm going to discuss five of the most likely ways to add backdoors to end-to-end encryption systems.

1. Don't use end-to-end encryption in the first place (just say you do.)

There's no need to kick down the door when you already have the keys. Similarly there's no reason to add a 'backdoor' when you already have the plaintext. Unfortunately this is the case for a shocking number of popular chat systems -- ranging from Google Talk (er, 'Hangouts') to your typical commercial Voice-over-IP system. The same statement also applies to at least some components of more robust systems: for example, Skype text messages.

Many of these systems use encryption at some level, but typically only to protect communications from the end user to the company's servers. Once there, the data is available to capture or log to your heart's content.

2. Own the directory service (or be the Certificate Authority).

Fortunately an increasing number of applications really do encrypt voice and text messages end-to-end -- meaning that the data is encrypted all the way from sender directly to the recipient. This cuts the service out of the equation (mostly), which is nice. But unfortunately it's only half the story.

The problem here is that encrypting things is generally the easy bit. The hard part is distributing the keys (key signing parties anyone?) Many 'end-to-end' systems -- notably Skype*, Apple's iMessage and Wickr -- try to make your life easier by providing a convenient 'key lookup service', or else by acting as trusted certificate authorities to sign your keys. Some will even store your secret keys.**

This certainly does make life easier, both for you and the company, should it decide to eavesdrop on you. Since the service controls the key, it can just as easily send you its own public key -- or a public key belonging to the FBI. This approach makes it ridiculously easy for providers to run a Man-in-the-Middle attack (MITM) and intercept any data they want.

This is always 'best' way to distinguish seirous encryption systems from their lesser cousins. When a company tells you they're encrypting end-to-end, just ask them: how are you distributing keys? If they can't answer -- or worse, they blabber about 'military grade encryption' -- you might want to find another service.

3. Metadata is the new data.

The best encryption systems push key distribution offline, or even better, perform a true end-to-end key exchange that only involves the parties to the communication. The latter applies to several protocols -- notably OTR and ZRTP -- used by apps like Silent Circle, RedPhone and CryptoCat.

You still have to worry about the possibility that an attacker might substitute her own key material in the connection (an MITM attack). So the best of these systems add a verification phase in which the parties check a key fingerprint -- preferably in person, but possibly by reading it over a voice connection (you know what your friends' voice sounds like, don't you?) Some programs will even convert the fingerprint into a short 'authentication string' that you can read to your friend.


From a cryptographic perspective the design of these systems is quite good. But you don't need to attack the software to get useful information out of them. That's because while encryption may hide what you say, it doesn't necessarily hide who you're talking to.

The problem here is that someone needs to move your (encrypted) data from point A to point B. Typically this work is done by a server operated by the company that wrote the app. While the server may not be able to eavesdrop you, it can easily log the details (including IP addresses) of each call. This is essentially the same data the NSA collects from phone carriers.

Particularly when it comes to VoIP (where anonymity services like Tor just aren't very effective), this is a big problem. Some companies are out ahead of it: Silent Circle (a company whose founders have threatened chew off their own limbs rather than comply with surveillance orders) don't log any IP addresses. One hopes the other services are as careful.

But even this isn't perfect: just because you choose not to collect doesn't mean you can't. If the government shows up with a National Security Letter compelling your compliance -- or just hacks your servers -- that information will obtained.

4. Escrow your keys.

If you want to add real eavesdropping backdoors to a properly-designed encryption protocol you have to take things to a whole different level. Generally this requires that you modify the encryption software itself.

If you're doing this above board you'd refer to it as 'key escrow'. A simple technique is just to an extra field to the wire protocol. Each time your clients agree on a session key, you have one of the parties encrypt that key under the public key of a third party (say, the encryption service, or a law enforcement agency). The encrypted key gets shipped along with the rest of the handshake data. PGP used to provide this as an optional feature, and the US government unsuccessfully tried to mandate an escrow-capable system called Clipper.***

In theory key escrow features don't weaken the system. In practice this is debatable. The security of every connection now depends on the security of your master 'escrow' secret key. And experience tells us that wiretapping systems are surprisingly vulnerable. In 2009, for example, a group of Chinese hackers were able to breach the servers used to manage Google's law enforcement surveillance infrastructure -- giving them access to confidential data on every target the US government was surveilling.

One hopes that law enforcement escrow keys would be better secured. But they probably won't be.

5. Compromise, Update, Exflitrate. 

But what if your software doesn't have escrow functionality? Then it's time to change the software.

The simplest way to add an eavesdropping function is just to issue a software update. Ship a trustworthy client, ask your users to enable automatic updates, then deliver a new version when you need to. This gets even easier now that some operating systems are adding automatic background app updates.

If updates aren't an option, there are always software vulnerabilities. If you're the one developing the software you have some extra capabilities here. All you need to do is keep track of a few minor vulnerabilities in your server-client communication protocol -- which may be secured by SSL and thus protected from third party exploits. These can be weaknesses as minor as an uninitialized memory structure or a 'wild read' that can be used to scan key material.

Or better yet, put your vulnerabilities in at the level of the crypto implementation itself. It's terrifyingly easy to break crypto code -- for example, the difference between a working random number generator and a badly broken one can be a single line of code, or even a couple of instructions. Re-use some counters in your AES implementation, or (better yet) implement ECDSA without a proper random nonce. You can even exflitrate your keys using a subliminal channel.

Or just write a simple exploit like the normal kids do.

Unfortunately there's very little we can do about things like this. Probably the best defense is to use open source code, disable software updates until others have reviewed them, and then pray you're never the target of a National Security Letter. Because if you are -- none of this crap is going to save you.

Conclusion

I hope nobody comes away with the wrong idea about any of this. I wouldn't seriously recommend that anyone add backdoors to a piece of encryption software. In fact, this is just about the worst idea in the world.

That said, encryption software is likely to be a victim of its own success. Either we'll stay in the technical ghetto, with only a few boring nerds adopting the technology. Or the world will catch on. And then the pressure will come. At that point the authors of these applications are going to face some tough choices. I don't envy them one bit.

Notes:

* See this wildly out of date security analysis (still available on Skype's site) for a description of how this system worked circa 2005.

** A few systems (notably Hushmail back in the 90s) will store your secret keys encrypted under a password. This shouldn't inspire a lot of confidence, since passwords are notoriously easy to crack. Moreover, if the system has a 'password recovery' service (such as Apple's iForgot) you can more or less guarantee that even this kind of encryption isn't happening.

*** The story of Clipper (and how it failed) is a wonderful one. Go read Matt Blaze's paper.

On cellular encryption

If you're interested in technology/privacy issues then you probably heard last week's big news out of the Boston Marathon case. It comes by way of former FBI agent Tim Clemente, who insists that our government routinely records all domestic phone calls.

Clemente's claim generated lots of healthy skepticism. This isn't because the project is technically infeasible (the numbers mostly add up), or because there's no precedent for warrantless wiretapping. To me the most convincing objection was simple: it'd be hard to keep secret.* Mostly for boring phone company reasons.

But this led to another interesting discussion. What if we forget local phone eavesdropping and focus on an 'easier' problem: tapping only cellular phone calls.

Cellular eavesdropping seems a lot more tractable, if only because mobile calls are conducted on a broadcast channel. That means you can wiretap with almost no carrier involvement. In fact there's circumstancial evidence that this already happening -- just by different parties than you'd think. According to a new book by reporters Marc Ambinder and Dave Brown:

The FBI has quietly removed from several Washington, D.C.–area cell phone towers, transmitters that fed all data to wire rooms at foreign embassies.

This raises a few questions: once you've tapped someone's cellular signals, what do you do with the data? Isn't it all encrypted? And how easy would it be for the US or some foreign government to lay their hands on the plaintext?

All of this which serves as a wonderful excuse to noodle about the state of modern cellular encryption. Be warned that this is not going to be a short post! For those who don't like long articles, here's the TL;DR: cellular encryption is a whole lot worse than you think.

GSM

GSM is the granddaddy of all digital cellular protocols, and it remains of the most popular protocols in the world. One thing that makes GSM special is its call encryption capability: the protocol is designed to encrypt all calls in between the handset and the local tower.

Call encryption is facilitated by a long-term secret key (call it K) that's stored within the tamper-resistant SIM card in your GSM phone. Your carrier also has a copy of this key. When your GSM phone connects to a tower, the parties execute the following authentication and key agreement protocol:

GSM authentication and key agreement protocol (source). MS represents the 'mobile station' (phone) and
HLR is the 'home location register', a central database. The MS and HLR combine a long-term secret Ki
with a random nonce RAND to create the shared communication key Kc. A3 and A8 are
typically implemented using the COMP128 function.

The interaction above serves two purposes: first, both the phone and carrier (HLR) derive a pair of values that will be used for authentication and key agreement. This includes a session key Kc as well as a short authentication token SRES that the phone will use to authenticate itself to the tower. Derivation is performed using two functions (A3 and A8) that accept the long-term secret K and with a random nonce RAND.

There are a handful of well-known problems with the GSM security protocols. In no particular order, they are:

1. Lack of tower authentication. GSM phones authenticate to the tower, but the tower doesn't authenticate back. This means that anyone can create a 'fake' tower that your phone will connect to. The major problem here is that in GSM, the tower gets to pick the encryption algorithm! That means your attacker can simply turn encryption off (by setting encryption 'algorithm' A5/0) and simply route the cleartext data itself.
   
   In theory your phone is supposed to alert you to this kind of attack, but the SIM chip contains a bit that can de-active the warning. And (as researcher Chris Paget discovered) carriers often set this bit.
    
2. Bad key derivation algorithms. The GSM ciphers were developed using the 'make stuff up and pray nobody sees it' school of cryptographic algorithm design. This is a bad approach, since it's incredibly hard to keep algorithms secret -- and when they do leak, they tend to break badly. This was the case for the original A3/A8 algorithms, which are both implemented using single function called COMP128-1. Unfortunately COMP128 turns out to be seriously broken -- to the point where you can clone a user's SIM key in as few as 8 queries.
    
3. Bad encryption algorithms. Fortunately it's easy to replace COMP128-1 by swapping out your SIM card. Unfortunately the situation is much worse for GSM's A5/1 call encryption cipher, which is embedded in the hardware of most handsets and tower equipment. A5/1 was leaked around the same time as COMP128 and rapidly succumbed to a series of increasingly powerful attacks. Today it's possible to conduct an efficient known-plaintext attack on A5/1 using a series of rainbow tables you can obtain from BitTorrent. The upshot is that most A5/1 calls can now be decrypted on a high-end PC.
    
4. Terrible encryption algorithms. But it's actually worse than that. GSM phones support an 'export weakened' variant called A5/2, which is so weak you can break it in real time. The worst part is that A5/2 uses the same key as A5/1 -- which means an active attacker (see #1 above) can briefly activate the A5/2 mode, crack to recover the encryption key, then switch back to A5/1 with a known key. This is much faster than attacking A5/1 directly, and allows eavesdroppers to intercept incoming phone calls from a legitimate (A5/1 supporting) tower.  

Alleged 'Stingray' tracking device
mounted on an SUV (source).

Another unfortunate aspect of the GSM protocol is that you don't need to attack the crypto to do useful things. For example, if all you want to do is determine which devices area in an area, you simply present yourself as a valid tower -- and see which phones connect to you (by sending their IMSI values). This is the approach taken by IMSI-catchers like Stingray.

Now the 'good news' here is that attacks (1), (2) and (4) require active involvement by the attacker. This means they have to be after you specifically and -- at least in principal -- they're detectable if you know what to look for. (You don't.) However, the weaknesses in A5/1 are a whole different kettle of fish. They permit decryption of even passively recorded A5/1 GSM calls (in real time, or after the fact) even to an attacker with modest resources.

3G/4G/LTE

A valid response to the points above is to note that GSM is nearly 30 years old. You probably wouldn't blame today's Ford execs for the crash performance of a 1982 Ford Escort, and similarly you shouldn't hold the GSM designers responsible for a 1980s protocol -- even if billions of people still rely on it.

Overview of the 3G AKA protocol. Look familiar? 

The great news is that modern phones often support the improved '3G' (e.g., UMTS) or LTE standards. These offer a bundle of improvements that substantially improve security over the original GSM. These can be summed up as follows:

1. Mutual authentication. The 3G protocols use a new 'Authentication and Key Agreement' (AKA) protocol, which adds mutual authentication to the tower connection. To validate that the phone is speaking to a legitimate tower, the carrier now computes a MAC that the phone can verify before initiating a connection. This prevents many of the uglier protocol attacks that plagued GSM.
    
2. Better authentication algorithms. The session keys and authentication tags are still computed using proprietary algorithms -- now called f1-f5, f5* -- but the algorithms are purportedly much stronger. Since their design is carrier-specific it's not easy to say exactly how they work. However this 3GPP recommendation indicates that they might be based on a block cipher like AES.
    
3. Better encryption. Call encryption in 3G uses a proprietary block cipher called KASUMI. KASUMI is based off of a Mitsubishi proposal called MISTY1, which was heavy customized to make it faster in cellular hardware.

The biggest source of concern for 3G/LTE is that you may not be using it. Most phones are programmed to gracefully 'fail over' to GSM when a 3G/4G connection seems unavailable. Active attackers exploit this feature to implement a rollback attack -- jamming 3G/4G connections, and thus re-activating all of the GSM attacks described above.

A more subtle concern is the weakness of the KASUMI cipher. Unfortunately KASUMI seems much weaker than the original MISTY1 algorithm -- so much weaker that in 2010 Dunkelman, Keller and Shamir were able to implement a related-key attack that recovered a full 128 bit call key in just under two hours!

Now before you panic, you should know that executing this attack requires a substantial amount of data, all of which must all be encrypted under highly unrealistic attack conditions. Still, it's interesting to note that the same attack fails completely when applied to the original MISTY1 design.

Top: generation of keys (CK, IK) and authentication tags AUTN, XRES using the functions f1-f5. Bottom: one proposed implementation of those functions using a 128-bit block cipher Ek. This could be AES (source).
And yes, it looks complicated to me, too.

What if you have already the keys?

  

The encryption flaws above seem pretty significant, and they really are -- if you're a private eavesdropper or a foreign government. For US national security organizations they're probably beside the point. It seems unlikely that the NSA would have to 'break' any crypto at all.

This is because both the GSM and AKA protocols lack an important property known as forward secrecy. What this means is that if I can record an encrypted call, and later obtain the long-term key K for that phone, then I can still reliably decrypt the whole communication -- even months or years later. (Protocols such as Diffie-Hellman or ECMQV prevent this.) Worse, for cellular conversations I can do it even if I only have one half (the tower side) of the communication channel.

Unfortunately I don't think you have to be a conspiracy theorist to suppose that the carriers' key databases are probably stored somewhere in Ft. Meade. Thus to the truly paranoid: stop talking on cellphones.

In conclusion

Sometimes conspiracy theories can be fun. Sometimes they're downright creepy.

For me this discussion veers towards the 'creepy'. Not so much because I think the NSA really is tapping all our cellphones (I suspect they just read our Facebook). Rather, the creepiness is in seeing just how vulnerable our privacy infrastructure is, even to people who are far less capable than the NSA.

As a result, your data isn't just available to nation states: it's also potentially available to that goofball neighbor who bought an IMSI-catcher off the Internet. Or to your business competitor. Or even to that one girl who finally got GnuRadio to compile.

We're rapidly approaching a technological crossroads, one where we need to decide if we're going to keep trusting others to protect our data -- or if we're going to take charge of it and treat carriers as the dumb and insecure pipes that they are. I suspect that we're well on our way towards this world -- and sadly, so does the FBI. It'll be interesting to see how things play out.

Notes:

* The argument is that recording all local calls in real time is a bigger job than just splitting major trunks or re-routing a few specific targets. It would seem to require significant changes to the US phone infrastructure. This is particularly true at the local office, where you'd need to upgrade and provision thousands of devices to record all calls passing through them. Building this capability is possible, but would require a lot of effort -- not to mention the complicity of hundreds (or thousands) of collaborators at the local telcos. And that means a whole lot of people keeping a very big secret. People aren't so good at that.

We're still alive

It's been a busy couple of weeks chock full of deadlines, all of which have had a direct and negative impact on blogging productivity.

Still: things are happening in the world! In the next few weeks I hope to have posts up on exciting topics like convergent encryption, IBM's exciting open source Fully Homomorphic Encryption library (AES in less than 30 hours!), password hashing, cellular wiretapping... and plenty more on the hot mess that is the field of practice-oriented provable security.

Please hang in there. Normal service will resume shortly.

Zerocoin: making Bitcoin anonymous

This is what it's like to die of stupid.

Wow, what the heck is going on with Bitcoin?

When I started this post, the value of a single bitcoin had surged upwards of $250. It's corrected a bit since then (down $100 or so), but it's pretty clear that we live in a very different world than we did two weeks ago.

And I'm not sure I really like this world. It's a world where I have to listen to CNBC reporters try to understand Bitcoin. Ouch. I think we can all agree that we were better off before this happened.

The explosion of interest in Bitcoin is both wonderful and terrible. It's wonderful because Bitcoin is an amazing technical innovation -- the first decentralized electronic currency to actually make something of itself. It's terrible because Bitcoin has some technical rough edges that really need to be filed off before we start using it for anything.

The rough edge that particularly interests me is user privacy. Or rather, Bitcoin's troubling lack of it.

In this post I'm going to describe a new piece of research out of my lab at Johns Hopkins that provides one potential solution to this problem. This is joint work led by my hardworking students Ian Miers and Christina Garman, along with my colleague Avi Rubin. Our proposal is called Zerocoin, and we'll be presenting it at this year's IEEE S&P.

For those who just want the TL;DR, here it is:

Zerocoin is a new cryptographic extension to Bitcoin that (if adopted) would bring true cryptographic anonymity to Bitcoin. It works at the protocol level and doesn't require new trusted parties or services. With some engineering, it might (someday) turn Bitcoin into a completely untraceable, anonymous electronic currency.

In the rest of the post I'm going to explain Zerocoin, what it can do for Bitcoin, and how far away that 'someday' might be. This is going to be a long, wonky post, so I won't be offended if you stop here and take my word that it's all true.

For everyone else, strap in. I need to start with some background.

Bitcoin in 300 words

Before I get to Zerocoin I need to give the world's shortest explanation of how Bitcoin works. (See here for a slightly less terrible explanation.)

At its heart, Bitcoin is a transaction network with a distributed public ledger. Transactions are files that contains messages like "User X transfers 3 bitcoins to user Y" and "User Y transfers 2.5 of those bitcoins to user Z". Users aren't identified by name. Instead, their identities are public keys for a digital signature scheme.* This allows users to sign their transactions, and makes it very difficult to forge them.

Now none of this stuff is really new. What makes Bitcoin special is the way it maintains the transaction ledger. Rather than storing the whole thing on a single computer, the ledger -- called a block chain -- is massively replicated and updated by a swarm of mutually distrustful parties running in a peer-to-peer network.

To make this work, nodes pull transactions off of a peer-to-peer broadcast network, then compete for the opportunity to tack them on the end of the chain. To keep one party from dominating this process (and posting bad transations), competition is enforced by making the parties solve hard mathematical problems called 'proofs of work'. The integrity of the block chain is enforced using hash chaining, which makes it very difficult to change history.

Now the block chain is fascinating, and if you're interested in the gory details you should by all means see here. This post mostly isn't going to get into it. For now all you need to know is that the block chain works like a global ledger. It's easy to add (valid) transactions at the end, but it's astonishingly difficult to tamper with the transactions that are already there.

So what's the problem?

The block chain is Bitcoin's greatest strength. Unfortunately from a privacy perspective, it's also the currency's greatest weakness.

This is because the block chain contains a record of every single Bitcoin transaction that's ever been conducted. Due to the way Bitcoin works, this information can't be limited to just a few trustworthy parties, since there are no trusted parties. This means all of your transactions are conducted in public.

Illustration of a Bitcoin block chain. Each transaction is tied to the one that precedes it.
The transaction at far left is almost certainly a drug deal.

In a sense this makes Bitcoin less private than cash, and even worse than credit cards. If you choose to engage in sensitive transactions on Bitcoin, you should be aware that a record will be preserved for all eternity. Spend with care.

Now some will say this is unfair, since Bitcoin users are not identified by name -- the only identifier associated with your transactions is your public key. Moreover, you can make as many public keys as you'd like. In other words, Bitcoin offers privacy through pseudonymity, which some argue is almost as good as the real thing.

But don't get too comfortable. Already several academic works have succeeded in de-anonymizing Bitcoin transactions. And this work is just getting started. You see, there's an entire subfield of computer science that can roughly be described as 'pulling information out of things that look exactly like the Bitcoin transaction graph', and while these researchers haven't done much to Bitcoin yet -- that's only because they're still fighting over the grant money. We will see more.

If you're a Bitcoin user who values your privacy, this should worry you. The worst part is that right now your options are somewhat limited. Roughly speaking, they are:

Just be careful. Generate lots of public keys and make sure your client software is extremely careful not to use them in ways that could tie one to another (e.g., getting 'change' from one key sent to another). This seems to be the major privacy thrust of the current Bitcoin development effort, and we're all waiting to see how it pans out. 

Use a laundry. For the more paranoid, there are services called 'laundries' that take in bitcoins from a whole bunch of users, mix them up and shuffle them back out. In theory this makes it hard to track your money. Unfortunately, laundries suffer from a few problems. First, they only work well if lots of people are using them, and today's laundries have relatively low volume. More importantly, you're entirely dependent on the honesty and goodwill of the laundry itself. A dishonest (or hacked) laundry can steal your coins, or even trace its inputs and outputs -- which could completely undermine your privacy. 

Use a Chaumian e-cash system. On the wonkier side, there have been attempts to implement real anonymous cryptographic e-Cash for Bitcoin. I've written about these systems before and while I think they're neat, the existing schemes (from Chaum on forward) have one critical flaw: they all rely on a central 'bank' to issue and redeem e-Cash tokens. The need for this bank has been a major stumbling block in getting these systems up and running, and it's almost unworkable for Bitcoin -- since trusted parties are antithetical to Bitcoin's decentralized nature.

In short, the current solutions aren't perfect. It would be awfully nice if we had something better. Something with the power of cryptographic e-Cash, but without the need to change Bitcoin's network model. And this is where Zerocoin comes in.

Zerocoin

Zerocoin is not intended as a replacement for Bitcoin. It's actually a separate anonymous currency that's designed to live side-by-side with Bitcoin on the same block chain. Zerocoins are fully exchangeable on a one-to-one basis with bitcoins, which means (in principle) you can use them with existing merchants.

Zerocoins themselves can be thought of literally as coins. They're issued in a fixed denomination (for example, 1 BTC), and any user can purchase a zerocoin in exchange for the correct quantity of bitcoin. This purchase is done by placing a special new 'Zerocoin Mint' transaction onto the block chain.

Once a Mint transaction has been accepted by the Bitcoin peers, the same user can later redeem her zerocoin back into bitcoins. She simply embeds a (preferably new) destination Bitcoin address into a 'Zerocoin Spend' transaction, then sends it into the network. If the transaction checks out, the Bitcoin peers will treat it just like a normal Bitcoin transfer -- meaning that she'll receive the full bitcoin value of the coin (minus transaction fees) at the destination address.

Now you're probably wondering what any of this has to do with privacy. To explain that, I need to give you one more piece of information:

Aside from educated guesswork, there's no way to link a Zerocoin Mint transaction to the Zerocoin Spend transaction that redeems it.

Redeeming a zerocoin gives you a completely different set of bitcoins than the ones you used to purchase it. In fact, you can think of Zerocoin like the world's biggest laundry -- one that can handle millions of users, has no trusted party, and can't be compromised. Once as user converts her bitcoins into zerocoins, it's very hard to determine where she took them back out. Their funds are mixed up with all of the other users who also created zerocoins. And that's a pretty powerful guarantee.

Illustration of a Bitcoin/Zerocoin block chain. A user transforms bitcoins into a zerocoin,
then (at some unspecified later point) 'Spends' it to redeem the bitcoins. The linkage between Mint
and Spend (dotted line) cannot be determined from the block chain data.

The key to the whole process is to make it all work at the protocol level -- meaning, without adding new trusted parties. And doing that is the goal of Zerocoin.

How does it work?

Zerocoin uses a combination of digital commitments, one-way accumulators and zero-knowledge proofs, and some extensions to the existing Bitcoin protocol. It also shares some similarities to a previous work by Sander and Ta-Shma. For the details, you can see our paper. Here I'm going to try to give a very high-level intuition that avoids the muck.

The key idea in Zerocoin is that each coin commits to (read: encrypts) a random serial number. These coins are easy to create -- all you need to do is pick the serial number and run a fast commitment algorithm to wrap this up in a coin. The commitment works like encryption, in that the resulting coin completely hides the serial number . At the same time this coin 'binds' you to the number you've chosen. The serial number is secret, and it stays with you.

To 'Mint' the new coin you post it to the network along with a standard Bitcoin transaction containing enough (normal) bitcoins to 'pay for' it. The Mint transaction adds some new messages to the Bitcoin protocol, but fundamentally there's no magic here. The Bitcoin network will accept the transaction into the block chain as long as the input bitcoins check out.**

The Zerocoin 'Spend' transaction is a little bit more complicated. To redeem your zerocoin, you first create a new transaction that contains the coin's serial number (remember that you kept it secret after you made the coin). You also attach a zero-knowledge proof of the following two statements:

1. You previously posted a valid zerocoin on the block chain.
2. This particular zerocoin contained the serial number you put in your transaction.

The key to making this all work is that zero-knowledge proof. What you need to know about these is that anyone can verify such a proof, and she'll be absolutely convinced that you're telling the truth about these statements. At the same time, the proof reveals absolutely no other information (hence the 'zero' knowledge).

This means anyone who sees your Spend transaction will be convinced that you really did previously Mint a zerocoin, and that it contained the serial number you just revealed. They can then check the block chain to make sure that particular serial number has never been Spent before. At the same time, the zero knowledge property ensures that they they have absolutely no idea which zerocoin you're actually spending. The number of such coins could easily run into the millions.

All of this leads us to one final question: where do your bitcoins go after you Mint a zerocoin, and how do you get them back when you Spend? 

The simple answer is that they don't go anywhere at all. The bitcoins used in a 'Mint' transaction just sit there on the block chain. The Zerocoin protocol semantics require that nobody can access those coins again except by publishing a valid Zerocoin 'Spend'. When you publish a Spend, the protocol allows you to 'claim' any of the previously-committed bitcoins -- regardless of who posted them. In other words, you Mint with one set of bitcoins, and you leave with someone else's. 

When will Zerocoin be available?

For those looking to use Zerocoin tomorrow, I would advise patience. We've written a proof-of-concept implementation that extends the C++ bitcoind client to support Zerocoin, and we'll be releasing a cleaned up version of our code when we present the paper in May.

But before you get excited, I need to point out some pretty serious caveats.

First of all, Zerocoin is not cheap. Our current zero-knowledge proof averages around 40KB, and take nearly two seconds to verify. By the standards of advanced crypto primitives this is fantastic. At the same time, it poses some pretty serious engineering challenges -- not least of which is: where do you store all these proofs?

This probably isn't the end of the world. For one thing, it seems likely that we'll be able to reduce the size and cost of verifying the proof, and we think that even the current proof could be made to work with some careful engineering. Still, Zerocoin as currently construed is probably not going to go online anytime soon. But some version of Zerocoin might be ready in the near future.

Another problem with Zerocoin is the difficulty of incrementally deploying it. Supporting the new Mint and Spend functionality requires changes to every Bitcoin client. That's a big deal, and it's unlikely that the Bitcoin folks are going to accept a unilateral protocol change without some serious pushback. But even this isn't a dealbreaker: it should be possible to start Zerocoin off using some training wheels -- using a trusted central party to assist with the process, until enough Bitcoin clients trust it and are willing to support it natively.

In fact, one of the biggest barriers to adoption is human beings themselves. As complicated as Bitcoin is, you can explain the crypto even to non-experts. This makes people happy. Unfortunately Zerocoin is a different animal. It will take time to convince people that these new techniques are safe. We hope to be there when it happens.

In conclusion

I realize that this blog post has run slightly longer than usual. Thanks for sticking with me!

As regular readers of this blog know, I have a passion for anything that gets interesting crypto out into the world. Bitcoin is a great example of this. It would be wonderful if this gave us an opportunity to do even more interesting things. Perfectly untraceable e-Cash would definitely fit that bill.

But even if we don't get there, the fact that reputable computer science conferences are accepting papers about 'that crazy Bitcoin thing' tells you a lot about how much it's grown up. In the long run, this is good news for everyone.

Notes:

* There are a lot of simplifications in here. Identities are the hash of your public key. The block chain is really computed using a Merkle tree for efficiency reasons. The peer-to-peer network isn't quite a broadcast network. Did I mention you should read the paper?

** Note that for those who 'know' their Bitcoin, you can think of the Zerocoin as a piece of extra data that gets added to a Bitcoin transaction. The inputs are still standard bitcoins. There's just no output. Instead, the transaction contains the coin data.

The Ideal Cipher Model (wonky)

A friend who's learning cryptography writes with a few questions about block ciphers:

(1) Let's say we're using AES-128 -- 128 bit keys, 128 bit blocks.

• For a given 128 bit block of plaintext "P" - if I was to iterate through all 2**128 key permutations and encrypt the same plaintext P with each key, would the outputs all be unique, or would there be collisions?

• For a given 128 bit key "K", if I was to use K to encrypt every possible (2**128) plaintext, would the outputs all be unique, or would there be collisions?

These are all reasonable questions with simple answers. But I'm not going to give them. Why bother with two simple answers when we can give one really complicated intuition?

What's Claude Shannon got to do with it?

Back in the late 1940s when people were still thinking on this whole information theory business, a gentleman named Claude Shannon came up with a model for what a block cipher should do. His idea was -- and yes, I'm embellishing a lot here -- that an 'ideal' block cipher would work kind of like a magical elf.*

You could ask the elf to encipher and decipher things for you. But instead of using a mathematical algorithm, it would just keep a blackboard with a big table. The table would have three columns (Key, Plaintext, Ciphertext), and it would start off empty. 

When you asked the elf to encipher a plaintext P under a key K, it would do the following:

1. Check to see if (K, P) were already recorded in some row of the table. If they were, it would read off the corresponding ciphertext value C from the same row, and return C.
2. If no matching row was found, it would generate a perfectly random ciphertext C.
3. It would then check for an existing table entry containing the same key and ciphertext (K, C). If this entry was found in the table, it would throw C away and repeat step (2).
4. Otherwise it would add (K, P, C) to the table and return C to the caller.

Now I realize this looks complicated, but if you think about this for a little while you'll realize that this little thought experiment does 'work' a lot like a real block cipher.

Just like a block cipher, it will always give the same output when you pass it a given key and plaintext. Furthermore -- for a given key K, no two plaintexts will ever encipher to the same ciphertext. This models the fact that a block cipher is a permutation.

Lastly, the output of the encipherment is very 'random' -- in the sense that it's intuitively not linked to the input. Calling the cipher on different inputs should produce values that are very much unrelated.

Of course, you also need the elf to decipher stuff as well. Decipherment works mostly like the process above. When you ask to decipher (K, C), it checks to see whether the given key and ciphertext are already in the table (i.e., they were previously enciphered). If so it looks up and returns the corresponding plaintext. Otherwise it generates a new random plaintext, makes sure it hasn't previously appeared in the table with that key, and returns the result.

Under the assumption that AES works like our elf, we can now answer my friend's questions. Clearly if I encrypt the same plaintext with many different keys, I will get many different ciphertexts. They'll each be random and 128 bits long, which means the probability of any two ciphertexts being the same (colliding) is quite small. But there's no rule preventing it, and over a large enough set it's actually quite likely.

Similarly, the second question is answered by the fact that the cipher is a permutation, something that's captured in our elf's rule (3).

This is an awful lot of work to answer a few simple questions...

Yes, it certainly is. But the 'Elf' model is useful for answering much more interesting questions -- like: is a given encryption scheme secure?

For example, take the CBC mode of operation, which is a way to turn a block cipher into an encryption scheme:

CBC encryption takes in a random key (K) and a random 'Initialization Vector' (IV), both of which are chosen by the encryptor. Now let's see what happens if we CBC-encrypt an N-block message using our elf.

1. The encryptor XORs the first plaintext block with the (random) Initialization Vector (IV), which should give a randomly-distributed value. We'll call this P'.
2. He then sends (K, P') to be enciphered by the elf. Since the elf has never seen (K, P') -- meaning it's not in the table -- it will generate a random value (C1), which will become the first ciphertext block.
3. The encryptor now XORs the next plaintext block with C1, which again should yield a randomly-distributed value which we'll call P''. 
4. He sends (K, P'') to be enciphered by the elf. Since P'' is also random (and, say, 128 bits long), the probability that it's already in the table is astronomically low. Thus with high probability the elf will again generate a random value (C2), which becomes the second ciphertext block.
5. He then repeats steps (3) and (4) for all the remaining blocks.

Note that with overwhelming probability -- and unless you encrypt really long ciphertexts** -- the elf will generate a random value for each ciphertext block. Hence the entire ciphertext will consist of a random string, which means it really shouldn't leak anything about the message (except for the length).

Of course, an attacker might also talk to the elf to try to learn something about the message. But note that even this attack isn't useful unless he can guess the (random) key K, since the elf will give him random results unless he asks for a value that includes K. Since K is a randomly-chosen secret key, the attacker should not be able to guess it.

Do ideal ciphers exist?

Now all of this is well and good, but it leaves us with an important question: is AES actually as good as an ideal cipher? Unfortunately, the resounding answer to this question is no. 

The problem here is that ideal ciphers are totally unworkable. Obviously we can't have an actual elf randomly filling in a bulletin board as we encrypt things. I want to carry a copy of the block cipher around with me (in software or hardware). I also want my copy of the cipher to be consistent with your copy, so that I can send you messages and you can decrypt them.

To make the elf idea work, we would each need to carry around a copy of the elf's table that's completely filled in from the start -- meaning it would already contain entries for every possible plaintext (resp. ciphertext) and key I might ever need to encipher/decipher. When you consider that there would be 2^128 rows just for a single key, you realize that, no, this is not a question of running out to Best Buy and picking up some more SD cards. It's fundamentally hard.

So carrying ideal ciphers around is not possible. The question then is: is there something that's as good as an ideal cipher, without requiring us to carry around an exponentially-sized table.

The answer to that question is a mixed bag. The bad news is that nothing really works as well as an ideal cipher. Worse yet, there exists schemes that would be provably secure with an ideal cipher, but would fail catastrophically if you implemented them with any real block cipher. So that sucks.

On the other hand, those are theoretical results. Unless you're doing some very specific things, the ideal cipher model is a moderately helpful tool for understanding what block ciphers are capable of. It's also a good jumping off point for understanding the real proofs we actually use for modes like CBC. These proofs use more 'realistic' assumptions, e.g., that the block cipher is a pseudorandom permutation.

But those proofs will have to wait for another time. I've reached my wonkery limit for today.

Notes:

* For the record, at no point did Claude Shannon ever refer to an 'elf'. At least not in writing.

** The probability of a 'collision' (i.e., asking the elf to encipher a value that's already been enciphered) goes up as you put encipher more blocks. At a certain point (for AES, close to 2^64 blocks) it becomes quite high. Not coincidentally, this roughly coincides with the number of blocks NIST says you should encrypt with CBC mode.

Attack of the week: RC4 is kind of broken in TLS

Update: I've added a link to a page at Royal Holloway describing the new attack. 

Listen, if you're using RC4 as your primary ciphersuite in SSL/TLS, now would be a great time to stop. Ok, thanks, are we all on the same page?

No?

I guess we need to talk about this a bit more. You see, these slides have been making the rounds since this morning. Unfortunately, they contain a long presentation aimed at cryptographers, and nobody much seems to understand the real result that's buried around slide 306 (!). I'd like to help.

Here's the short summary:

According to AlFardan, Bernstein, Paterson, Poettering and Schuldt (a team from Royal Holloway, Eindhoven and UIC) the RC4 ciphersuite used in SSL/TLS is broken. If you choose to use it -- as do a ridiculous number of major sites, including Google -- then it may be possible for a dedicated attacker to recover your authentication cookies. The current attack is just on the edge of feasibility, and could probably be improved for specific applications.

This is bad and needs to change soon.

In the rest of this post I'll cover the details in the usual 'fun' question-and-answer format I save for these kinds of attacks.

What is RC4 and why should I care?

RC4 is a fast stream cipher invented in 1987 by Ron Rivest. If you like details, you can see this old post of mine for a longwinded discussion of RC4's history and flaws. Or you can take my word: RC4 is old and crummy.

Despite its age and crumminess, RC4 has become an extremely popular ciphersuite for SSL/TLS connections -- to the point where it accounts for something absurd like half of all TLS traffic. There are essentially two reasons for this:

1. RC4 does not require padding or IVs, which means it's immune to recent TLS attacks like BEAST and Lucky13. Many admins have recommended it as the solution to these threats.
2. RC4 is pretty fast. Faster encryption means less computation and therefore lower hardware requirements for big service providers like Google.

So what's wrong with RC4?

Like all stream ciphers, RC4 takes a short (e.g., 128-bit) key and stretches it into a long string of pseudo-random bytes. These bytes are XORed with the message you want to encrypt, resulting in what should be a pretty opaque (and random-looking) ciphertext.

The problem with RC4 is that the above statement is not quite true. The bytes come out of the RC4 aren't quite random looking -- they have small biases. A few of these biases have been known for years, but weren't considered useful. However, recent academic work has uncovered many small but significant additional biases running throughout the first 256 bytes of RC4 output. This new work has systematically identified many more.

At first blush this doesn't seem like a big deal. Cryptographically, however, it's a disaster. If I encrypt the same message (plaintext) with many different RC4 keys, then I should get a bunch of totally random looking ciphertexts. But these tiny biases mean that they won't be random -- a statistical analysis of different positions of the ciphertext will show that some values occur more often. 

By getting many different encryptions of the same message -- under different keys -- I can tally up these small deviations from random and thus figure out what was encrypted. 

If you like analogies, think of it like peeking at a picture with your hands over your eyes. By peeking through your fingers you might only see a tiny sliver of the scene you're looking at. But by repeating the observation many times, you may be able to combining those slivers and figure out what you're looking at.

Why would someone encrypt the same message many times?

The problem here (as usual) is your browser.

You see, there are certain common elements that your browser tends to send at the beginning of every HTTP(S) connection. One of these values is a cookie -- typically a fixed string that identifies you to a website. These cookies are what let you log into Gmail without typing your password every time.

If you use HTTPS (which is enforced in many sites by default), then your cookies should be safe. After all, they'll always be sent over an encrypted connection to the website.

Unfortunately, if your connection is encrypted using RC4 (as is the case with Gmail), then each time you make a fresh connection to the Gmail site, you're sending a new encrypted copy of the same cookie. If the session is renegotiated (i.e., uses a different key) between those connections, then the attacker can build up the list of ciphertexts he needs.

To make this happen quickly, an attacker can send you a piece of Javascript that your browser will run -- possibly on a non-HTTPS tab. This Javascript can then send many HTTPS requests to Google, ensuring that an eavesdropper will quickly build up thousands (or millions) of requests to analyze.

Probability of recovering a plaintext byte (y axis) at a particular byte position in the RC4-encrypted stream (x axis), assuming 2^24 ciphertexts. Increasing the number of ciphertexts to 2^32 gives almost guaranteed plaintext recovery at all positions. (source)

Millions of ciphertexts? Pah. This is just crypto-wankery.

It's true that the current attack requires an enormous number of TLS connections -- in the tens to hundreds of millions -- which means that it's not likely to bother you. Today. On the other hand, this is the naive version of the attack, without any special optimizations. 

For example, the results given by Bernstein assume no prior plaintext knowledge. But in practice we often know a lot about the structure of an interesting plaintext like a session cookie. For one thing, they're typically Base64 encoded -- reducing the number of possibilities for each byte -- and they may have some recognizable structure which can be teased out using advanced techiques.

It's not clear what impact these specific optimizations will have, but it tends to reinforce the old maxim: attacks only get better, they never get worse. And they can get a lot better while you're arguing about them.

So what do we do about it?

Treat this as a wakeup call. Sites (like Google) need to stop using RC4 -- before these attacks become practical. History tells us that nation-state attackers are already motivated to penetrate Gmail connections. The longer we stick with RC4, the more chances we're giving them.  

In the short term we have an ugly choice: stick with RC4 and hope for the best, or move back to CBC mode ciphersuites -- which many sites have avoided due to the BEAST and Lucky13 attacks.

We could probably cover ourselves a bit by changing the operation of browsers, so as to detect and block Javascript that seems clearly designed to exercise these attacks. We could also put tighter limits on the duration and lifespan of session cookies. In theory we could also drop the first few hundred bytes of each RC4 connection -- something that's a bit of a hack, and difficult to do without breaking the TLS spec.

In the longer term, we need to move towards authenticated encryption modes like the new AEAD TLS ciphersuites, which should put an end to most of these problems. The problem is that we'll need browsers to support these modes too, and that could take ages. 

In summary

I once made fun of Threatpost for sounding alarmist about SSL/TLS. After all, it's not like we really have an alternative. But the truth is that TLS (in its design, deployment and implementation) needs some active help. We're seeing too many attacks, and they're far too close to practical. Something needs to give.

We live in a world where NIST is happy to give us a new hash function every few years. Maybe it's time we put this level of effort and funding into the protocols that use these primitives? They certainly seem to need it.

Here come the encryption apps!

It seems like these days I can't eat breakfast without reading about some new encryption app that will (supposedly) revolutionize our communications -- while making tyrannical regimes fall like cheap confetti.

This is exciting stuff, and I want to believe. After all, I've spent a lot of my professional life working on crypto, and it's nice to imagine that people are actually going to start using it. At the same time, I worry that too much hype can be a bad thing -- and could even get people killed.

Given what's at stake, it seems worthwhile to sit down and look carefully at some of these new tools. How solid are they? What makes them different/better than what came before? And most importantly: should you trust them with your life?

To take a crack at answering these questions, I'm going to look at four apps that seem to be getting a lot of press in this area. In no particular order, these are Cryptocat, Silent Circle, RedPhone and Wickr.

A couple of notes...

Before we get to the details, a few stipulations. First, the apps we'll talk about here are hardly the only apps that use encryption. In fact, these days almost everyone advertises some form of 'end-to-end encryption' for your data. This has even gotten Skype and Blackberry into a bit of hot water with foreign governments.

However -- and this is a critical point -- 'end-to-end encryption' is rapidly becoming the most useless term in the security lexicon. That's because actually encrypting stuff is not the interesting part. The real challenge turns out to be distributing users' encryption keys securely, i.e., without relying on a trusted, central service.

The problem here is simple: if I can compromise such a service, then I can convince you to use my encryption key instead of your intended recipient's. In this scenario -- known as a Man in the Middle (MITM) attack -- all the encryption in the world won't help you.

Man in the Middle attack (image: Wikipedia). Mallory convinces Alice and Bob to use her key, then transparently passes messages between the two.

And this is where most 'end-to-end' commercial services (like Skype and iMessage) seem to fall down. Clients depend fundamentally on a central directly server to obtain their encryption keys. This works fine if the server really is trustworthy, but it's huge problem if the server is ever compromised -- or forced to engage in MITM attacks by a nosy government. 

(An even worse variant of this attack comes from services that actually store your secret keys for you. In this case you're truly dependent on their good behavior.*)

One important feature of the 'new' encryption apps is that they recognize this concern. That is, they don't require you to trust the service. A few even point this out in their marketing material, and have included their own dishonesty into the threat model. 

Cryptocat

Cryptocat is an IM application developed by Nadim Kobeissi, who -- when he's not busy being harassed by government officials -- manages to put out out a very useable app. What truly distinguishes Cryptocat is its platform: it's designed to run as a plugin inside of a web browser (Safari, Chrome and Firefox).

Living in a browser is Cryptocat's greatest strength and greatest weakness. It's a strength because (1) just about everyone has a browser, (2) the user interface is pretty and intuitive, and (3) the installation process is trivial. Cryptocat's impressive user base testifies to the demand for such an application.

The weakness is that it runs in a frigging web browser.

To put a finer point on it: web browsers are some of the most complex software packages you can run on a consumer device. They do eight million things, most of which require them to process arbitrary and untrusted data. Running security-critical code in a browser is like having surgery in a hospital that doubles as a sardine cannery and sewage-treatment plant -- maybe it's fine, but you should be aware of the risk you're taking. 

If that's not good enough for you: go check out this year's pwn2own results.

For non-group messaging, Cryptocat uses a protocol known as off-the-record (OTR) and ships the encrypted data over Jabber/XMPP -- using either Cryptocat's own server, or the XMPP server of your choice. OTR is a well-studied protocol that does a form of dynamic key agreement, which means that two parties who have never previously spoken can quickly agree on a cryptographic key. To ensure that your key is valid (i.e., you're not being tricked by a MITM attacker), Cryptocat presents users with a key fingerprint they can manually verify through a separate (voice) connection.

So how does Cryptocat stack up?

Code quality: Nadim has taken an enormous amount of crap from people over the past year or two, and the result has been a consistent and notable improvement in Cryptocat's code quality. While Cryptocat is written in Javascript (aaggh!), the application is distributed as a plugin and not dumped out to you like typical script. This negates some of the most serious complaints people level at Javascript crypto, but not all of them! Cryptocat has also been subject to a couple of commercial code audits.

Crypto: All of the protocols are well-studied and designed by experts. Update: Jake Appelbaum reminds me that while this is true for one-on-one communications, it's not true for the multi-party (group chat) OTR protocol -- which is basically hand-rolled. Don't use that.

Ease of use: My five year old can use Cryptocat.

  

Other notes: If the silent auto-update functionality is activated (in Chrome) it is technically possible for someone to compromise Cryptocat's update keys and quietly push out a malicious version of the app. This concern probably applies to most applications, but it is something you should be aware of.

Should I use it to fight an oppressive regime? Oh god no.

Silent Circle

Using SilentCircle on a
Huawei complete negates
the point of using SilentCircle.

Silent Circle is the brainchild of PGP inventor Phil Zimmerman and a cadre of smart/paranoid folks. It actually consists of multiple apps, supporting VoIP/IM/PGP-based Email and videoconferencing -- with an optional Snapchat-like self-destructing messages feature. The apps can essentially replace the standard Phone and Messages apps in your iPhone or Android device.

Silent Circle is a paid subscription service, which means it's marketed to folks who (in theory, anyway) really care about their security, but also don't want to scrounge around with messy open-source software -- for example, journalists working in dangerous locations or business executives running overseas operations. In exchange for $240/year you get the ability to securely call other SilentCircle subscribers and to dial ordinary telephone (POTS) numbers.

The termination to POTS is SilentCircle's best feature, and also its biggest concern. When you directly call another SilentCircle user, your connection is encrypted from your phone to theirs. When you dial a normal phone line, your connection will only be encrypted until it reaches SilentCircle's servers. From there it will travel on normal, tappable phone lines.

Now most users will probably understand this, and SilentCircle certainly does its best to make sure people do. Still, most users aren't experts, and it's easy to imagine a typical user getting confused -- and possibly assuming they're safer than they actually are. 

The SilentCircle short authentication string.

SilentCircle uses ZRTP (and a variant called SCIMP) to generate the keys used in communications. It doesn't require you to trust a central directory server, or to send your keys outside of the device. Your protection against MITM comes from two features: (1) the app presents a 'short authentication string' that users can verbally compare before they communicate, and (2) after you've successfully communicated the first time, it caches a 'secret' that can be used to protect future sessions.

Overall code quality: It took a while for SilentCircle to publish their code, but they've finally put most of it online. It's much less fun to look at SilentCircle than it is to poke at Cryptocat -- mostly because Nadim's reactions are more entertaining -- but the code for SilentCircle looks ok. (I've seen a couple of minor comments, but nobody's found any security issues.) Moreover, the app has been independently audited and given a clean bill of health.

Crypto: SilentCircle uses ZRTP, which I dislike because it's so complex -- it's like a choose-your-own-adventure by sadists. But ZRTP is old and well-studied so it's unlikely that there are any serious issues lurking in it. The messaging app uses a simplified variant called SCIMP (Silent Circle Instant Messaging Protocol) which seems much better, since it ditches most of the crazy options I dislike about ZRTP. I'm pretty confident that both of these protocols work just fine.

Ease of use: To quote SilentCircle's PR: so simple even an MBA can use it. (No, I'm kidding, they don't say that. They just think it.) 

Other thoughts: Rumor has it that the current market price for an iOS vulnerability is currently near $500,000. That doesn't mean iOS (or Silent Circle's app) is bulletproof. But it should give you a little bit of confidence. If you're being targeted with an iOS software vulnerability, then someone really wants you. 

Should I use this to fight my oppressive regime? SilentCircle's founders have made it clear that they'll chew off their own legs before they allow themselves to be a party to eavesdropping on their clients. But even so -- I would still have to think on this for a while.

RedPhone/TextSecure

RedPhone and TextSecure are developed by Moxie Marlinspike's Open Whisper Systems. Note that OWS is actually Moxie's second company -- the original Whisper Systems was purchased by Twitter a couple of years back -- not for the software, mind you; just to get hold of Moxie for a while. 

RedPhone does a much of what SilentCircle does, though without the paid subscription and termination to POTS. In fact, I'm not quite sure if you can terminate it to POTS (I'll update if I find out.)

Like Silent Circle, RedPhone uses ZRTP to establish keys, then encrypts voice data using AES. Consequently, most of what I said for SilentCircle also applies here, including the use of a short authentication string to prevent MITM attacks.

Overall code quality: After reading Moxie's RedPhone code the first time, I literally discovered a line of drool running down my face. It's really nice.

In fact, it was so nice that I decided to rough it up a little. I assigned it to the grad students in my Practical Crypto course -- assuming that they'd find something, anything to take the shine off of it. Unfortunately they basically failed on this score (though see 'Other thoughts' below). In short: it's very well written.

Crypto: Most of what I said about Silent Circle applies here, except that RedPhone uses only ZRTP, not SCIMP. However, RedPhone's implementation of ZRTP is somewhat simplified and avoids most of the options that make ZRTP a pain to deal with.

Other thoughts: In fairness to my students, they did point out that Redphone does not retain a cache of secrets from connection to connection. Technically this is an optional feature of ZRTP, so it's not wrong to omit it. However, it means that you have to verify the authentication string on every single call. Moxie is working on this, so it may change in the future.  

Should I use this to fight my oppressive regime? Oh look, a pony!

Wickr

Wickr is an encrypted Snapchat-like app for the iPhone. Like the above applications it provides for instant messaging, but it also focuses heavily on the message destruction feature. Chats/messages can be set to self-destruct after a pre-specified period of time. 

I've included Wickr on this list because I've seen it mentioned in a handful of respectable media outlets over the past few months. This means that people are either using Wickr, or that Wickr has very good PR folks. I also included it because it was at least partially designed by Dan Kaminsky, who generally knows his stuff.

Unfortunately I can't say too much about Wickr because -- to date -- there's virtually no technical information available on it. (Not even a white paper!) However, based on Tweets with Dan and this short post on the LiberationTech mailing list, I believe that Wickr uses a centralized directory server to share keys. In theory this could be ok if it provided a mechanism to compare key fingerprints between users, and/or detect invalid keys. But currently this does not seem to be the case.

As for the destruction of secrets, well, this does seem like a nice idea, particularly if the destruction is enforced cryptographically. Unfortunately this is a fundamentally hard problem to solve correctly: if I can get a copy of your phone's memory while the message is there, I can keep the message forever.

Overall code quality: Who knows. 

Crypto: Current versions use some kind of RSA-based key agreement. According to Dan, the next generation will use elliptic curve crypto with perfect forward secrecy. But the real horses head is the (apparent) reliance on a central directory server, which makes the service much more vulnerable to MITM.

Ease of use: Very easy. Just set your message expiration date, key in the destruct time, and send away.

Should I use this to fight my oppressive regime? Yes, as long your fight consists of sending naughty self-portraits to your comrades-at-arms. Otherwise, probably not.

In summary

If you've made it this far, I'm guessing you still have one burning question. Namely: What app should I use if I'm trying to overthrow my government?

The simple answer is that I just don't know. It's not an easy question.

Each of the above apps seem quite good, cryptographically speaking. But that's not the problem. The real issue is that they each run on a vulnerable, networked platform. If I really had to trust my life to a piece of software, I would probably use something much less flashy -- GnuPG, maybe, running on an isolated computer locked in a basement.

Then I would probably stay locked in the basement with it.

But not everyone is a coward like me. The widespread availability of smartphones has already changed the way people interact with their government. These encryption apps could well be the first wave in an entirely new revolution -- one that makes truly private communication a reality.

Notes:

* Some services actually know and store your private keys, while others operate as a Certificate Authority, allowing you to 'certify' new public keys under your name. Either of these models makes eavesdropping relatively easy for someone with access to the server.