July 26, 2017

Be wary of one-time pads and other crypto unicorns

Yesterday, a new messaging app called Zendo got some very favorable coverage from Tech Crunch. At the core of their sales pitch is the fact that they use one-time pads for encryption. With a few strong assumptions, namely that the pads are truly random and are only used once, it’s true that this scheme is “unbreakable” or more precisely that it offers information-theoretic guarantees that no eavesdropper can learn anything about the encrypted message. Zendo’s founder calls it a “crypto unicorn” and claims it is a game-changer in terms of security.

It isn’t. In this post I’ll explain why we don’t need (and shouldn’t want) to use one-time pads for a consumer secure-messaging app and why we should generally be wary of products like Zendo making grandiose claims about solving security problems through magic crypto.

The one-time pad is very old and is quite simple: the sender and receiver agree on a random key or “pad” K, which is as long as the message M to be sent, and then the sender transmits a ciphertext C K. Because there is a possible value of K that would map C to every possible message M (of the given length, which is revealed), it’s easy to prove that no information about M can be obtained if an eavesdropper has no information about K. By contrast, with a stream cipher (one of two common types of symmetric cipher) the sender would transmit C = ⊕ F(K) for some function F which takes a constant-sized key K and expands it to a “stream” of bytes as long as M. The function F is designed to produce output that appears completely random, but there’s always a chance that the function F will produce output with some statistical bias and this can leak information about the encrypted message M. This has happened with RC4 over the years to the point that it’s no longer recommended.

It’s important to keep in mind that there are hundreds of things that can go wrong in a secure messaging app, ranging from entropy failures to backdoored devices to malware. One risk, which is a relatively low-priority one, is that the ciphers or other symmetric primitives will be broken. Removing this reliance on secure symmetric primitives is all the one-time pad can get you in a perfect world. Professional cryptographers would mostly say this is not a risk worth worrying about: RC4 is almost 30 years old now, and despite it being “broken” practical attacks still require enormous amounts of ciphertext and would probably not affect security in a meaningful way if you deployed it in a messaging app.

Anyway, one might say that if Zendo have really figured out how to make one-time pads practical, it’s worth using them just to remove this remote risk of a symmetric primitive break. We don’t know exactly how Zendo works, as there is no source code or design documentation available. But there’s the critical thing: As apparently implemented by Zendo, and as would be likely to be implemented by any other mobile messaging app, the use of one-time pads does not remove the reliance on symmetric crypto primitives. There are three reasons for this:

  1. Using one-time pads requires generating a lot of true random data and most mobile devices can’t do that. True randomness is very slow to generate for most devices without a special-purpose hardware RNG. As a result, in practice most personal computers and mobile devices have to “stretch” the limited amount of true randomness collected in an entropy pool like Linux’s /dev/urandom. This is done by by a cryptographic pseudorandom number generator, which is of course built using hash functions and is insecure if they’re broken. Zendo apparently uses Java SecureRandom. A reasonable choice, but not appropriate for generating one-time pads. In practice, most devices can’t afford to generate a truly-random one-time pad and use a pseudorandom one, which is equivalent security-wise and worse performance-wise than just having used a stream-cipher to begin with.
  2. We don’t have secure high-bandwidth channels for sharing one-time pads which don’t rely on symmetric cryptography. Before using the one-time pad, both users need to get a copy of it. With an app like Zendo, this requires an in-person meeting and taking a picture of a 2D barcode on the other person’s screen. The claim is that this “visual channel” cannot be eavesdropped on. This is a somewhat dubious claim-if anybody gets a picture of your screen during the exchange, they’ll be able to read all of your communication with that partner. It’s important to note that this is NOT a vulnerability for public-key verification using 2D barcodes as many other apps use, an attacker observing this process can’t break your security, so Zendo’s design seems to introduce a new vulnerability here. Anyway, even assuming this visual channel is secure, it’s not high-bandwidth enough to send a large amount of random data for one-time pads. What Zendo does under the hood is share an AES-256 key using the visual channel, then use this to encrypt the one-time pad data and send that electronically (not clear exactly which channel but this doesn’t really matter). So once again, this scheme depends inherently on a symmetric primitive (namely AES-256). If somebody can break AES, they can eavesdrop on the one-time pad exchange.
  3. One-time pads don’t assure integrity. It’s easy to flip bits in a transmitted ciphertext which was encrypted using a one-time pad (or stream cipher),which will result in the recipient decoding a message with the corresponding bits also flipped. Preventing this requires a MAC function, and the Zendo developers used the standard HMAC (they didn’t say which hash function but SHA-256 is a safe guess). Again a reasonable choice, only this is yet another symmetric primitive that can compromise security if broken. Unlike the first two issues, this is actually not a fundamental problem, just a classic design error often found in amateur-hour cryptography. One-time MACs exist and they are acceptably efficient, they’re just rarely used because eliminating reliance on symmetric primitives is usually not a design goal.

So, don’t believe the hype on Zendo and, in general, ignore any app claiming to use one-time pads. Problems 1 and 2 above are quite hard to address without relying on good symmetric crypto (as Zendo definitively does) at which point there’s no security advantage to using a one-time pad. There’s a reason why you rarely see one-time pads used or even mentioned-professional cryptographers know they aren’t actually adding any security value. They are cloak-and-dagger stuff for a reason, making sense if a spy needs to quickly dead drop a large amount of key material and then wants an encryption algorithm so simple it can be performed on pencil and paper.

In general, crypto primitives are not the first thing consumers should be worried about when choosing an encryption app. More important are a clear and properly-documented crypto design that has been subject to independent review, source code available for review, regular audits for implementation security, forward secrecy and a usable way to verify communication partner’s identities. These are the basic elements highlighted in the EFF’s Secure Messaging Scorecard. As Edward Snowden said “crypto works.” We don’t need crypto unicorns so much as we need diligent engineering to deploy the crypto we already have.

More broadly, there is an increasing amount of snake oil in the secure messaging space (some of which has been debunked here before). One-time pads are a classic warning sign, but I’d propose as an even more general rule of thumb:

If a new crypto tool is first announced in a press release or popular science magazine, don’t use it.

Security and crypto are hard to get right, as everybody in the field painfully knows. New projects which are designed by people with sufficient expertise and experience are almost always circulated on mailing lists, have design docs and code distributed, or have academic papers published for a long time to get sufficient review before they go to the press or encourage real users to sign up. Compare Zendo’s launch to that of Pond, which has been in development for years without any publicity outside of the security community and with active warnings that it isn’t advisable to use it yet because it hasn’t received enough security review. It’s possible a brilliant stealth-mode app could launch with marketing first and security details and review later, but this almost always is a sign that the developers don’t understand how reliable crypto tools come into existence.

Comments

  1. Seth Schoen says:

    In my experience reading people’s periodic proposal to use OTP-based cryptosystems, they usually don’t understand that a pad based on a CSPRNG or hash is equivalent to a stream cipher (part of your reason #1).

    It might be handy to write a really clear explanation of this point, maybe with examples that show how some CSPRNGs can be broken — although I also had trouble recently explaining to someone that if the CSPRNG has a seed smaller than the plaintext, the resulting stream cipher is inherently not information-theoretically secure (because an attacker who correctly guesses the seed, even by brute force, can tell that the guess was likely correct, which would not be the case with a true one-time pad, where attackers can’t usefully confirm if their guesses are right or wrong). So maybe a deeper problem is that plenty of people proposing using one-time pads don’t quite understand what the promise of perfect secrecy afforded by these systems means, and how it’s different from the secrecy afforded by other systems.

  2. John Millington says:

    I know nothing about Zendo and aren’t going to talk about their specific thing.

    But.

    1) Mobile devices should be good at finding entropy. They have CCDs, radio antennas, microphones and accelerometers. In terms of raw potential, I’ll put my phone’s hardware up against my desktop’s hardware any day.

    2) Two people’s mobile devices can sometimes be physically near one another. My wife’s phone and my phone spend something like 12 hours a day within a few feet of each other, so I’m not sure they need high bandwidth. A lot of data could go over bluetooth in a few hours, and is hard to “hear” just 20 feet outside the house. And if we plug ’em into the same USB hub for charging, why can’t they just talk to each other through cables? I think that in general, people who know each other in real life could reasonably practically exchange pads. Even moreso if we start putting more SD readers in phones as is more common with tablets: sneakernet!

    This stuff can happen and could be done fairly well, without major inconvenience.

    • Harry Johnston says:

      One problem with the idea of using things like radio antennas is that, unless you’re very careful, it means the adversary may be able to influence your entropy source.

  3. Jann Horn says:

    I installed Zendo on an android phone and started the key exchange thing. The QR code is just a JSON object with the largest values being 256 bits (base64-encoded), and it seems like the actual key material is transmitted over wifi.

  4. trailblazr says:

    I think you are basically right in having a close look on a solution before using it for something where your life depends on. Totally right procedure.

    I think where this post goes in the completely wrong direction is in just putting a lot of negativity on an actually “new” solution and some smart people trying to improve security of consumers.

    Why so negative? It’s a bit like those armchair economists… much talk not action or at least nothing else to show off that beats this new solution. I think it is quite a good idea to use OTP because those are easily verifiable by even total noobs. It is the simplicity of the concept that is a huge advantage here to review the software. Where all other crypto solutions are only understandable by experts and thus reviewable by experts, this can basically done – as you already mentioned – if necessary with paper and pencil. Isn’t that great? That is something that is a huge difference for not having to trust someone, but actually being able to check and control the output of this software easily.

    This lack of acknowledgement makes the post sound a bit like security guy bitch-fighting. Put your money where your mouth is and build something. I do not get it why dropping negativity should help anyone here.

    “The one-time pad is very old and is quite simple” yeah its proven technology and that is pure gold in crypto. On the one hand you condemn them because it is old, on the other you dismiss it because it is new (and not yet proven). i think you should decide for either the “old” is the bad thing or the “new” is the bad thing both things do not sound very convincing to me, sorry.

    Oh and why should one differentiate at all between one-time pads for a consumer secure-messaging and OTP for other kind of users? That is not necessary at all. Done right this OTP solution should be valid to use even for government top secret spies. As a consumer I would not demand less than that.

    I do not get where this post has some substance to help move things forward. It is just the usual skepticism without acknowledging that someone actually takes the risk to try. At least that should be acknowledged.

    Just my 2 cents.

    • Harry Johnston says:

      The point is that OTP *isn’t* “verifiable by total noobs” unless you generate the pad in a genuinely random way, i.e., by rolling dice. Any *computerized* implementation of OTP depends on the random number generator, as well as being vulnerable to problems in the way the OTP is distributed.

      And it isn’t Vendo that’s taking the risk. It’s the consumer. Don’t you think *someone* should warn consumers when a new product is badly designed?

      • trailblazr says:

        The principle of OTP is understandable by consumers. All other currently available crypto is not. For me that is something really interesting where this approach differs from all the currently available products which are not in any way verifiable by consumers or even good programmers. You need security experts.

        That is by the way the basic reason why we do not have working crypto until now… it needs experts to make it fly. The first automobiles were also machines which could only be driven by experts. The first planes were right the same thing. Technology we invent is at first only available as a tool to experts.

        From my point of view it is way overdue to get rid of the “needs experts” thing for crypto. The first solution that takes this path will win.

        Yes, you are right, random number generators or better, a lot of entropy are the eternal weakness of all devices which themselves create this data or need to create it and they are a vector of attack. But how about feeding in a picture by taking a photograph e.g. on a mobile? Why not use devices movement (gyroscopes are built into these things as a standard now).

        Also storing the OTP securely is a real issue. But more than all that it is absolutely useless, if the whole device (say iPhone, Google Phone, etc.) is compromised already on the OS layer which actually displays the clear text after it was decrypted. So what sense does all this make anyway one could argue?

        I think eliminating the expert need from crypto will be the enabler for innovative solutions. It is the next step we need. We do not need another even more complicated elliptic curve research or yet another asymmetric key tutorial.

        What we need is understandable crypto. That’s the challenge. Yeah, warn consumers, but if you start waring them, please tell them, that the devices they use are compromised on a completely different layer if the allow all their stuff e.g. being “backed up” to the “cloud”.

        • Your argument about crypto apps needing to be like cars which are simple to drive is dubious. Zendo is no simpler to use than TextSecure or iMessage or any other end-to-end encrypted app. Even the authors of Zendo acknowledge that using one-time pads imposes some usability challenges (in that keys must be exchanged before use).

          Cars are not simple to design (they have gotten progressively more complicated to engineer and even to repair). Arguing that a crypto app should be designed without the need for “expert cryptographers” is akin to arguing that you shouldn’t get in a car that was designed by expert mechanical engineers, just one that you could have designed yourself.

          If I designed my own car surely it would be inferior to what the “car experts” have spend decades working on, just like a crypto app designed by somebody who doesn’t understand modern cryptography is probably going to be full of design errors.

  5. I agree with some of the points in the article, however the author draws the wrong conclusion.

    Let’s list the reasons this Zendo app is not a true OTP solution:

    1) Closed design and closed source so you can’t trust it. At a bare minimum for trust in the product it needs to be open design and the source code needs to be available and compilable by the end user. The source code can have copyright on it if they want to protect their IP, but it needs to be readable by security experts. Also compiling it yourself means they haven’t slipped something in at compile time. We’ve also got no idea of the crypto specifics and whether it was designed properly.

    2) Uses app stores as a delivery model of the secure software. The app can be replaced with a backdoored one from Apple and Google as it’s signed by them. Maybe they wouldn’t do that willingly, but there is such things as National Security Letters. If you want trust in what you’ve just downloaded, you download the source code and verify the GnuPG fingerprint and signature it was shipped with. See the Tor project for examples. The developer also needs to put their public key fingerprint in the Namecoin blockchain otherwise you’re likely just downloading the NSA’s public key and getting a backdoored version.

    3) Doesn’t use a True Random Number Generator (TRNG). If the key or pad was generated from the system CSPRNG then it’s not a real OTP. It’s only as strong as the CSPRNG that generated it. As we have no idea what the real design or implementation is we can’t prove this part. However there are true entropy sources on a phone that can be used if you’re creative. E.g. accelerometer, camera, compass, GPS, microphone etc. The camera is probably not too good on phones and uses JPEG which reduces entropy, but with a standalone digital camera you can take photos of random things in nature and using a cryptographic hash to extract entropy from the photo.

    4) Phones are terrible for security. They can be spying or listening to you in a myriad of ways. If this was a serious solution, then it would be restricted to WiFi only devices (no closed baseband processor), then running open source mod of Android, compiled yourself, then security hardened using e.g. the Orbot Android hardening guide. A secure communication is only as secure as the weakest end point. If one partner is using Apple and the other hardened Android, then the NSA TAO unit will just hack and steal the OTPs from the weakest link i.e. the Apple device.

    5) Key exchange over WiFi. WiFi can have like 25m-50m range and even further on a good day. If you’re exchanging OTP keys over WiFi encrypted by AES, then the encryption is only ever as secure as the AES encryption. NSA/FBI can be outside with a StingRay van (or satellite?) and intercept it. Then if you’re only as secure as AES, you lose perfect secrecy because AES isn’t provably secure. A better solution is Bluetooth, NFC or just MicroSD for key exchange. Or use a WiFi exchange inside a Faraday cage if you have to. Or transfer them to an air-gapped computer first via USB cable, then onto the other device.

    6) How do they authenticate the OTP encrypted message? Standard HMAC? Doesn’t sound information-theoretically secure. If they encrypted the MAC tag as well with OTP then that’s reasonable. The OTP encryption hides the real MAC tag so no information about the plaintext can ever be revealed by it even if they try every key/message combination to get a valid MAC. After that it depends on the quality of the hash function to protect the integrity of the message. Some say it’s better to use a Carter-Wegman one-time MAC.

    This quote from the article:
    > “In general, crypto primitives are not the first thing consumers should be worried about when choosing an encryption app.”

    Actually they should be. The Snowden leaks showed that NSA have run multiple programs e.g. BULLRUN designed to weaken crypto standards and industry designs. They also have in house methods against block ciphers e.g. AES if you read the recent Der Spiegel article. We don’t know what standards are weak exactly because Snowden didn’t have full access to that information. That is classified ECI and restricted to the agency’s top cryptanalysts. Read more of The Intercept. It’s similar to how the UK spies kept the fact they’d cracked Enigma for over 40 years. At the moment anything standardised by the NIST who collaborate extensively with the NSA is likely secretly weak in more ways than one. NIST standardises stuff for *non-classified* government networks and their standards are (mistakenly) voluntarily adopted by the industry. If their Suite B standards were actually secure then they’d also be used by DoD, USAF, CENTCOM etc but they are not. NSA and the defense networks use Suite A. So there’s a telling hint about whether the US government thinks anything in Suite B is _actually_ secure for anything on the national security level.

    Finally I’m going to sum up by disagreeing with the author on this point as well:
    > “… in general, ignore any app claiming to use one-time pads.”

    OTPs can be done properly, if you have a TRNG, the design is good, it’s open source and it’s implemented properly (e.g. unit tested, peer reviewed and audited). There are certain situations where they can be used and simple text messaging is one of them. Military and governments also have a use for them e.g. Washington-Moscow hotline. If you don’t know which crypto standards are compromised, or the real capabilities of spy agencies (e.g. quantum computer), they definitely make sense. The only problem is it’s slightly inconvenient to do the initial physical meetup and key exchange. Even that can be made easier with clever software.

    I’ll leave a few examples of some open source, proof of concept projects using OTPs. They may be a bit rough around the edges and could use some external auditing and improvements but they are a work in progress and I believe they’re on the right track.

    1) github.com/maqp/tfc

    2) jerichochat.tk/information.html

  6. Your points 1, 2, and 4 are all risks that are probably greater than the underlying crypto primitives, which is exactly why I recommended that crypto primitives should not be one’s first concern when looking at encrypted communication apps.

    To point 6, there are one-time MAC algorithms which are information-theoretically secure (just like one-time pads). In fact I linked to some relevant info in this post.

    I don’t disagree that one-time pads can be done properly-but I don’t see you recommending a good solution for how to implement a true RNG on phones that can produce hundreds of kilobytes of entropy quickly with a convincing proof of randomness. I also don’t see a solution recommended for exchanging all of that data in a way that can’t easily be eavesdropped without relying on crypto. Some sort of NFC-in-a-Faraday-cage approach could work, but nobody is really recommending that.

  7. John Lloyd says:

    Can you demonstrate, perhaps in a quick video how the random numbers generated on an ipad are in fact not random, or not random enough?
    For example, take a 100Kb subset (made visible to you) out of a 1Mb randomly generated number from the mobile device (not visible to you)- and then start to predict the remainer of the string; afterwich the remainder of the string would be revealed and compared to you prediction.

    You may use any tools you wish, the only assumption being you do not see in advance the unrevealed portion of the string, prior to making your prediction.

    • Harry Johnston says:

      That’s not how it works. If you want to have a reasonable expectation of safety, you need to be able to demonstrate that it is random, or at least present evidence as to why it can reasonably be expected to be.

      Does the iPad even *have* a built-in random number generator? Presumably not, if Zendo uses Java’s SecureRandom.

  8. Roger Smith says:

    I tend to disagree with the criticisms here — a QR code plus wifi transmission of a OTP is a reasonable space for a product to fill, even if it’s not for everyone, and in terms of implementation that’s probably the best way to go about it.

    On the other hand, by sheer virtue of there being no source available, we can only guess as to what the app is doing and for that reason they lose any benefit of doubt.

    And here’s the crux: The killer/sole feature of an OTP messaging app would be that a beginner coder has a reasonable chance of auditing the implementation — but without that opportunity Zendo seems pointless.

  9. Interesting read, the question remains, do more encrypted tools make it harder for the spies or do they fool us into wrong security beliefs? I wonder what would happen if people switched from gmail to Tutanota (automatically encrypted webmail)? Email is still one of the moste widely used online communication so we have to something about the fact that it’s all in the open to spies, hackers, and the likes. Even if there is not 100% security, we have to do something about it, don’t you think? I would really like to see Tutanota on the EFF scorecard so that normal folks like me know what they are using and can recommend it to friends and family withou having any doubts.