Crypto Fails

Scott Arciszewski from Paragon Initiative pointed me to this example of PHP cryptography.

The code is bad and the crypto design is flawed, but as usual for this blog, we can learn something from it. Let's ignore the fact that it's using MCRYPT_RIJNDAEL_256 (the 256-bit block version of Rijndael, not AES) instead of MCRYPT_RIJNDAEL_128 (real AES), the fact that it's not checking the return value of substr(), and the fact that it's passing a hexadecimal-encoded key to a function that expects a binary string. I've covered all of these failings on this blog before, so I won't touch on them again.

Instead, let's focus on two facts. First, it is doing "MAC then Encrypt" (MtA), which means the Message Authentication Code (MAC) is being applied to the plaintext message before encryption -- contrary to modern crypto wisdom. Second, that the MAC is checked with a non-timing-safe comparison, which means that if an attacker can get really precise timing measurements of a failed decryption, they can find out how much of the MAC matches. In the "Encrypt then MAC" (EtM) design, where the MAC is applied to the ciphertext after encryption, this kind of a timing leak usually lets you forge a message. But this time, the MAC is inside the ciphertext, encrypted, so at a first glance, exploiting it seems more difficult.

Indeed, the issue was brought up in the comment section of the page. The author of the code responded as follows:

I had written code for a constant-time text comparison of the MAC but then realized that this is not an issue when using the MAC-then-encrypt method because the MAC is only compared after decryption to verify that the data is intact and the same as when it was encrypted. Since the correct MAC is only exposed when the correct encryption key is used it doesn’t matter whether the text comparison is done in constant-time or not. Changing to an encrypt-then-MAC method (requiring a constant-time MAC comparison) would not be backwards compatible with the current version.

Let's follow the logic of this statement. On a broad level, they are claiming that the timing attack does not matter because the MAC is inside the encryption. What is their reasoning for this claim? There are two ways to interpret what was written, depending on what you take "correct MAC" to mean.

In one interpretation, "correct MAC" means the MAC that's stored within the message, and they are saying you need the key to access it, so even if you could use the timing channel to match the calculated MAC by twiddling the "correct MAC" you couldn't actually learn what it is. This reasoning is flawed because to create a forgery you do not always need to know the MAC value, you just need to produce some new ciphertext that the decryption machinery will accept. Or perhaps they mean that even if you did know the calculated MAC value, you still couldn't place it inside the plaintext message without knowing the encryption key. This assumes the encryption itself is providing some sort of integrity protection. That may well be so, but a more rigorous argument is necessary to justify it.

In the other interpretation, "correct MAC" means the MAC that's computed from the plaintext message after decryption. This reading is hard to interpret in a positive light. It's true that it's only exposed after decryption with the correct key, but the side-channel in the code leaks information about it right after it is!

Neither of these readings may be what the author really meant, but I am trying to interpret their words in the best way possible.

I'm going to tell you how to attack against this code in just a moment, and the fact that an attack exists demonstrates that the author's reasoning must be unsound. So why spend so many words analysing the argument? Because it is an example of an extremely common mistake, which I'll call reasoning by Lego.

Reasoning by Lego happens when a designer or developer understands cryptography as Lego blocks stacked together. The blue block (the MAC) is sitting on top of the red block (the encryption), therefore the blue block won't fall down. Textbooks put cryptography algorithms on display as circuit diagrams with primitives like ciphers and hashes wired up to data like keys and plaintexts. This leads to the view that crypto algorithms should be thought of as simple components wired together.

The Lego view is not wrong. It's an intuitive way to think of crypto algorithms when you're writing the code. But it's the wrong way to think about cryptographic security. To talk about an algorithm's security, you need to consider the entire system as a whole. In your house, you can safely replace an old incandescent lightbulb with a more energy-efficient compact fluorescent without worrying that it will cause your microwave to explode. Cryptography is different. Making a small change to one part of your algorithm can completely break the other seemingly-unrelated parts. Just because the parts are spatially separated in the circuit diagram doesn't mean they don't influence each other. You need to look at the bigger picture.

Professional cryptographers do just that. Instead of reasoning from the bottom up, as by saying, "The green Lego block is connected to the red Lego block in this way, therefore the blue Lego block on top won't fall over." they take a top-down approach, closer to, "Let's suppose this Lego structure breaks in any way. The only way that's possible [rigorous proof details omitted] is if the green Lego block splits in two. We are assuming individual Lego blocks do not break, so the whole structure will not break."

In cryptographic terms, we start by assuming the system is vulnerable to a specific kind of adversary. Usually, we give the adversary as much power as possible. We let them encrypt chosen plaintexts and even decrypt chosen ciphertexts. Then we prove a claim along the lines of, "If that adversary can break the system as a whole (the entire Lego structure), then they can find a collision in the hash function (the indestructible Lego block)." This sort of reasoning lets us prove, formally, that if the crypto primitives we're using (ciphers, hash functions, MACs) are secure, then the system as a whole is secure. That is the right way to reason about security in cryptography.

I've personally found that the top-down mindset is a good way to break bad cryptography, too. If you want to break some crypto, first find an attack that shows it isn't secure according to the strict formal definitions of security (IND-CPA, IND-CCA2, etc.). The formal definitions of security are so strict that the attack you find might not have any practical relevance at all. Next, take that weakness and find a way to turn it into into a practically-relevant attack. For me, this works nearly every time.

The Attack (Proof of Concept)

Okay, I promised you earlier that I had an actual attack against this PHP encryption code, and now it's time to deliver.

I like this attack because it demonstrates everything I've been saying up until now. On the Lego block view, the timing side-channel in the code only seems relevant to message integrity. We were so distracted by integrity that we forgot to consider its effect on confidentiality. It turns out to have a big effect. The attack I found lets an attacker decrypt the first byte of every block in a ciphertext. The only preconditions are: (1) The attacker needs some (less than 2000) known plaintext blocks, and (2) the attacker needs to be able to provide ciphertexts to the decryption function and get an accurate measure of the running time (i.e. they can exploit the side-channel).

I'm not going to explain the attack here. I feel like doing so would distract away from the message of this post. If you are interested, you can find a simulated proof of concept implementation of the attack here. The code is well-commented, so if you want to know how it works, you should be able to understand it by reading (and running) that code.

In the proof of concept, I've removed the serialize() and unserialize() calls, as well as the call to trim(). I've also modified the decryption function to return 0 if the MAC comparison fails on the first byte or 1 if the MAC comparison makes it past the first byte, simulating a side-channel with one-byte granularity.

I made these changes to make the attack easier and more reliable. Without the changes, the attack is still possible in theory, but much harder to demonstrate. In particular, string-comparison timing leaks do not have one-byte granularity in practice. Instead, strings are usually compared word-by-word (4 or 8 bytes at a time), which increases the number of decryption queries required to carry out the attack. If the reader is interested, they might try to get the attack working in a realistic setting.

As they say, "Attacks always get better; they never get worse."

When we reason by Lego, we destroy the environment in favor of saving a single tree. In this case, we got distracted into thinking about MACs and forgeries and forgot to check the other security properties. Yes, that blue Lego block is held up by the red block, but until we took a step back, we couldn't see that the red block was hanging off the edge, about to fall, bringing the blue block with it.

Thinking of cryptography as Lego blocks put together will lead you astray. If you want to build secure cryptography, insist on a security proof in a strict model with powerful adversaries. If you want to break cryptography, start by showing that it isn't secure in a strict model, and then find a way to turn those weaknesses into practical attacks.

I Consult

This LinkedIn forum posting, tweeted by Scott Arciszewski (@voodooKobra), contains probably the worst password "hashing" code of all time. Yes, worse than plaintext.

Providing a SHA-2 checksum won't help people verify the integrity of the files they have downloaded. The reason is simple: If an attacker can modify the file the user gets, then they can probably modify the hash the user gets too.

Secure code delivery is a hard problem, but there are some things you can do right now to make it easier on your users:

Create a PGP or GnuPG key pair and sign your releases with it. Publish the public key on your website and on social media accounts. Include instructions for verifying the signature on your website.

Serve your downloads over HTTPS. Doing so will help prevent a network-level attacker from modifying the software as it downloads. Everyone should be checking the PGP signature, but this will help in case someone forgets or doesn't bother to do it.

(If you publish binaries.) Release your source code and publish instructions for reproducing the build. By following the instructions, it should be possible to reproduce the exact binaries that you have published.

Today I'm talking about this code. It's PHP code that's supposed to do encryption. It's ugly, broken, and insecure, but we can learn from it.

Thanks to @voodooKobra for pointing me to the code.

Open it in another tab and take a quick look through it. You'll see that there are two classes. One is called hash_encryption, and the other is called blowfish_encryption. I will only talk about hash_encryption in this post.

The comment in hash_encryption says that it is "Simple but secure encryption based on hash functions" and that it "provides a block cipher in ofb mode (output feedback mode)". As you can easily guess, none of that is true, except that it is "based on hash functions."

Initialization

To use the class, you have to first call hash_encryption(), passing the secret key as an argument. Inside this method, a "random" "salt" is generated and a class variable called hash_key is set to the hash of the key parameter. After you've done that, you can call encrypt() and decrypt() to encrypt and decrypt strings.

Generating the "Salt"

The salt is generated like this:

$this->salt = sha1('#num::'.md5(''.time()).'->'.'Date:'.date('Y-m-d H:i:s O')).'@'.md5('This is the RANDOM salt generator which must be used ! @$#&(#&)(*_*$^$*$%*$%*$^^^%&*$^($^%**!@#@^%#:"{}<>:?"');

The only thing that changes in this line of code is what time() and date() return, both of which are extremely predictable. It looks like someone tried to make it a little more random by typing some symbols into the string, but it doesn't help, since they're always the same.

Encrypting a String

The encryption looks even worse. First, it generates a random "Initialization Vector", which is just the hash of the "salt", a random number from rand() (which has been seeded with the time), and the contents of all global variables. Like the salt, it's very easy to predict.

Next, it XORs that predictable IV with the key, and adds the result to the output. We don't need to look any further to know that this encryption is useless. We can take the output, XOR it with the IV (which we can easily predict or guess), and get the key. But, for no good reason, I'll go on to finish describing how the encryption works.

Next, a variable called $key is set to the value of the IV. To avoid confusion with what we were calling the "key" in the last paragraph, I'll just keep calling this the "IV." The process from here on is like a stream cipher, where the key stream is generated by the following process: The first block of the stream is the IV, then the second block is the hash of the IV and the first block of plaintext, and so on. It's kind of like OFB mode, like the comment said, but not really. Again, since we can predict the IV, we can generate the keystream, so this is trivially broken.

Don't Write Your Own Crypto

I could tell you that it should be using a cipher instead of a hash, that it needs to provide authentication instead of just secrecy, that it needs to use a cryptographically secure pseudo-random number generator, and all of those things. But I've mentioned all of those on Crypto Fails before. This time I want to talk about something different: Why you shouldn't write your own crypto.

This is something a lot of people, including myself, have a hard time digesting. We're hackers, and we like to do things ourselves. When cryptographers tell us that there's a whole class of code we shouldn't be allowed to write, we feel bad. It's the ultimate argument from authority, and we don't like authority.

Or: Don't Release Your Crypto Code

I understand that point of view, so I'm going to rephrase the standard advice into: Don't release your crypto code. Write whatever you want, but if you write crypto code, don't release it. I hope cryptography experts will follow me by saying "Don't release." instead of "Don't write."

Edit: Just to be clear, in the context of closed-source software, you shouldn't release the software at all! Perhaps it would be even better to say "Don't use!"

Unknown Unknowns

Donald Rumsfeld said this:

There are known knowns. There are things we know that we know. There are known unknowns. That is to say, there are things that we know we don't know. But there are also unknown unknowns. There are things that we don't know we don't know.

I hypothesize that most crypto errors, especially the ones at the design level, are "unknown unknowns" to the designer. I have many examples of this.

My audit of EncFS found that MACs were not being compared in constant time. I think "Do you have to compare MACs in constant time?" was an unknown unknown to the EncFS authors. As were "Is incrementing the IV safe with CBC mode?" and "Is a 64-bit MAC good enough?" Once you know what to ask, it's easy to find answers. The authors didn't, so as a result, there are vulnerabilities.

When I looked at how Synergy encrypts its network traffic, I found it to be insecure, because it reuses the same IV for both communication directions (client to server and server to client). Another unknown unknown: "Is it safe to reuse an IV?"

If you look at the other posts on this blog, you'll find the same pattern. It's reasonable to believe that most problems are caused by the authors' unknown unknowns.

That's why you shouldn't release your crypto code. You don't know what you don't know. A cryptographer is a person whose set of unknown unknowns (about cryptography) is a lot smaller than yours or mine. An unknown unknown is a lot less likely to create a vulnerability in a protocol they design, or some code they write (but sometimes it still happens).

When I started the Crypto Fails blog, I promised myself that I'd try to say something constructive in each post, instead of just ranting about bad crypto. This bit of code, however, really puts that promise to the test.

I'll be talking about php-csprng. It's a "cryptographically secure" random number generator library, written in PHP.

The project has a website, on which the obviously well-meaning author explains his difficulty finding sources of entropy:

Developing CSPRNG in pure PHP was actually a lot harder than someone might think since there is no single function in PHP that can be called to guarantee enough entropy that will work on all web hosts and there is a ton of misinformation on the PHP website. This is partly the fault of PHP itself for being an incredibly flexible cross-platform tool so that it can run on a wide variety of hosts. Therein lies both its strength and weakness when it comes to application security for PHP.

He makes a good point. We really have to start building crypto primitives into our languages, especially CSPRNGs. You just can't do cryptography without one.

The author also mentions the lack of documentation on where to get entropy:

The hardest part of creating CSPRNG was that there was (and is) little to no documentation out there on how to actually get entropy. Lots of documentation exists on what to do once I had entropy but there is a huge amount of hand-waving when it comes to entropy gathering techniques.

The reason there is no documentation is because there is no way to generate secure random numbers in PHP without support from the environment. Unless you have a hardware true random number generator, entropy collection takes time and requires access to precise measurements of things like disk seek times, key presses, network packets, mouse movements, etc. You can't get that in a high-level cross-platform scripting language like PHP. The only documentation you need is: don't do it.

To write a cryptographically-secure random number generator in PHP:

Check if the system provides a CSPRNG.

If so, use that. If not, refuse to generate numbers until one is installed.

Ok, let's get on to some of the actual problems in the code.

Downloading Online Password Generators

The code collects entropy from system information (memory use, php version, etc.), user input (the $_GET and $_POST arrays), openssl_random_pseudo_bytes() (if available), and by downloading online password generators. These inputs are then feed into a hash, which becomes the seed for the generator.

function RSG_GetRootSeedURLs() { $result = array( "https://www.random.org/integers/?num=100&min=0... "https://www.fourmilab.ch/cgi-bin/Hotbits?nbytes=128... "https://www.grc.com/passwords.htm"... ); }

If the platform doesn't provide openssl_random_pseudo_bytes(), this is extremely bad. Obviously, if the system has no Internet access, or if the online generators start blocking this script's requests, it will fall back on the very weak entropy collected from system information and user input.

Worse, an adversary can purposefully interrupt the connections to the online generators, completely eliminating that entropy source, or forcing the script to fall back to unencrypted connections (yes, it does that).

When it does work, the script has to assume that the online generators are generating good random numbers and won't reveal them to anyone else. That's a big assumption.

Leaks User Input Verifier

Another problem with this generator is that it uses the user input as an entropy source. It's counter-intuitive, but this is actually a bad thing. If an adversary can predict all the other entropy sources, they can use the output of the generator to check guesses about the user's input.

For example, if this was used to generate a salt for hashing a password with a long scrypt computation, the adversary could use the salt alone to check the password (by re-running the random number generator with that password as input and seeing if it generates the same salt), instead of being forced to go through the computation and memory intensive scrypt hashing process.

If you have other reliable entropy sources, it's OK (and good) to use user input as an additional source. This code doesn't, so it's not OK here. This is only a minor issue, but it's something a good CSPRNG design needs to consider.

The Stream Generator

Once the seed is generated, it's fed into a homebrew hash-based deterministic stream generator. This is an iterative process:

next number = SHA1(mt_rand() || ctr || previous number || seed)

Here, || means concatenation, mt_rand() is PHP's non-cryptographic pseudo-random number generator, ctr is a number that increases by one each time the process is iterated, and, obviously, seed is the seed. If SHA512 is available, then it's used instead of SHA1.

This is not safe. The adversary knows everything except seed (ctr and mt_rand() are predictable). To predict the next number, they have to compute the hash without knowing seed. Put more simply, the adversary knows SHA1(X || Y) and X, and needs to compute SHA1(Z || Y).

It turns out that the formal requirements for a hash function (collision resistance) do not guarantee it's hard to do that. In this particular instance, I'm not smart enough to think of how to do it, but in very similar circumstances (when the adversary can choose X instead of it being chosen for them) it can be done quite easily using a length extension attack. So this construction probably isn't secure.

You shouldn't invent your own stream generator. Use AES in CTR mode or a good stream cipher, and re-seed often. Or, better, just rely on the platform's CSPRNG instead of implementing your own. If the platform's CSPRNG is broken, there's nothing you can do, and it's not your fault.

"Normal" Distribution Generator

Thankfully, this part of the code doesn't appear to be in use, but it's so bizarre that I have to mention it. The RSG_NormalizedStream class is supposed to generate a "normal distribution of random numbers."

It does nothing of the sort. What it actually does is repeatedly generate a random permutation of the numbers between $min and $max. The $balancer array is filled with all the numbers between $min and $max, then when one is chosen, it is removed from the array, so that it can't be chosen again.

public function RandomInt($entropy = "") { $num = $this->randgen->RandomInt( 0, count($this->balancer) - 1, $entropy . $this->counter ); $entropy = ""; $this->counter++; $result = $this->balancer[$num]; array_splice($this->balancer, $num, 1); if (!count($this->balancer)) { $range = $this->max - $this->min; for ($x = 0; $x <= $range; $x++) $this->balancer[$x] = $this->min + $x; } return $result; }

If we use this code to generate some random numbers between 1 and 9 (inclusive), you can see that each set of 9 is just a random permutation of "123456789."

6, 1, 4, 5, 8, 3, 7, 2, 0 9, 3, 7, 4, 9, 8, 2, 0, 1 5, 6, 3, 6, 1, 9, 0, 5, 2

This code doesn't belong in a CSPRNG. Someone might use it by accident, expecting the output to be secure.

Conclusion

There are probably more errors in this code, I just don't have the time to look for them. So in summary, we've learned:

Use the platform's CSPRNG.

Make it hard to mis-use your code.

Don't use secrets to help seed random number generators unless you have other reliable entropy sources. Otherwise, your RNG might leak a verifier.

Telegram is an encrypted instant messaging app for iOS and Android devices. Obviously, I wouldn't mention it on this blog if its crypto was perfect. In fact, it's far from perfect. It's almost horrifying.

I'm not sure if it was in response to some good criticism, but Telegram recently announced a crypto contest. Basically, if you can recover an email address that was encrypted with their app, you win $200,000 USD worth of Bitcoin.

This seems like a good thing. The massive award should get people looking for bugs in their code.

Unfortunately, the contest is useless. Neither users nor Telegram developers will learn anything from it. But Telegram will still be able to point to it and say, "Look! No one has won the contest, so our software is secure!" Naive users will believe it, and they will feel safe using dangerously broken encryption.

Why is the contest no good? To understand why, we need to learn how security is defined and analyzed in cryptography. This is a good opportunity to explain it, so that's what I'll do in the next section. If you already know what IND-CPA and IND-CCA mean, you can probably skip over this section.

What does "secure" mean?

In cryptography, we're always reasoning about "security", so we need to give the word "secure" a rigorous definition. This is done by defining security with respect to the capabilities of an adversary - a person (or computer) trying to break the system.

We have to define how much computing power the adversary has, what data they have access to, what data they can modify, how they can communicate with the honest users of the system, and so on.

Over the years, cryptographers have given names to various types of adversaries. We'll go over the important ones in the next three sections.

Known Plaintext Attack (KPA)

Let's start out by defining the adversary as having access to the system's ciphertext (encrypted data), and let's give them the full plaintext for a few ciphertexts. They have access to the ciphertexts and the plaintexts for some of them (these plaintext-ciphertext pairs are called known plaintexts), but they can not interact with the system in any way. We'll call this model the Known Plaintext Attack (KPA).

This seems like a reasonable model at first. In the case of a communication encryption system, the adversary in this model is like someone who can sniff the network traffic but can't change it or insert their own traffic.

As you could have probably guessed, this model is too weak. A system secure only in the KPA model is missing some very important properties that we'd like a "secure" system to have.

Imagine a system that always encrypts the same message to the same ciphertext. If two different messages are encrypted, their ciphertexts are different, but if the same message is encrypted twice, the ciphertexts are the same. An example would be a system that uses the same key to encrypt messages with AES in CBC mode with a zero Initialization Vector (IV).

The adversary is given a ciphertext and told that it's either the encryption of "YEA" or "NAY". Assuming the adversary is not given the encryption of "YEA" or "NAY" as one of the known-plaintext pairs, they can not figure out whether the ciphertext they have is the encryption of "YEA" or "NAY". That's good, a KPA adversary can't break this system.

But what if you could make the system encrypt messages of your choice? Since all messages encrypt to the same thing, you could send "YEA", get its ciphertext, and compare it to the one you're trying to decrypt. If it's the same, you know it is an encryption of "YEA", otherwise it is an encryption of "NAY."

This isn't just a theoretical ability. More often than not, you can make the system encrypt a message of your choice. One real example is a TLS connection between a web browser and a google.com. If another website, say bing.com, includes an image on one of its pages from google.com, the browser will encrypt the image URL and send it to google.com.

The KPA model doesn't agree with our intuitive notion of "security." We need to make our adversary more powerful in order to make our definition of "security" stronger.

That's the key point here: We give the adversary in our model more power, and this gives us a stronger definition of security. If you're building a tank, you don't test its armor with small arms fire, you shoot it with an RPG.

Chosen Plaintext Attack (CPA)

In the last section, we saw that if the adversary could encrypt messages of their choice, they could break a system that's only KPA-secure. So what if we let the adversary make the system encrypt arbitrary messages as well?

This is the Chosen Plaintext Attack (CPA) model. The adversary can make the system encrypt messages of his or her choice. Even with that power, they should not be able to learn anything about another ciphertext.

This is a much more reasonable security model, but it's still not good enough. A real adversary can modify ciphertexts.

Suppose there's a bank system that encrypts money transfers with AES in CTR mode with a unique nonce for each message. This is secure in the CPA model, which is good, because a user can make their own transfers to get chosen plaintext pairs.

Suppose the transaction orders look like this:

"Transfer $100 from Alice to Bob"

Encrypted, one might look like:

yAOB972Fs1KTDr8Mn84LT6psaT+w3qh8F/76n9F922Y68UQ4YYs7

The encryption (CTR mode) is malleable, so a real adversary can change the last part (highlighted with stars):

yAOB972Fs1KTDr8Mn84LT6psaT+w3qh8F/76n9F922Y68UQ4**XQPR**

Because of the change, it will be decrypted to:

"Transfer $100 from Alice to Eve"

So, by changing one of the ciphertexts, the adversary can redirect the money that Alice was sending to Bob to Eve. Obviously, we need to strengthen our security model even more. We have to be sure that even when an adversary can modify ciphertexts, the system is still secure.

Chosen Ciphertext Attack (CCA)

This brings us to the last security model we will discuss, called the Chosen Ciphertext Attack (CCA) model. In this model, the adversary is also allowed to choose ciphertexts and gets to see their decryptions. The adversary can essentially do anything they want besides telling the system to decrypt the actual ciphertext they are trying to decrypt. The adversary can modify messages in transit, drop messages, replay messages, etc.

The CCA model is the standard we hold all cryptography systems to today. If someone proposes a system that is not secure in the CCA model, it will be rejected (except in some very specific circumstances, like encrypted databases).

Telegram's Contest

By going through the attack models, I wanted to get across an idea that's very important when reasoning about crypto security. I'll repeat it again: If you want to show that a system is secure, give the adversary as much power as possible, and if they still can't break it, the security is good. Knowing that the system is secure in a weak model, like KPA, does not mean it's secure in a stronger (and more realistic) model like CCA. If a tank is bullet-proof, it might not be RPG-proof.

Okay, enough crypto theory. Back to the real problem: Telegram's contest. The contest works like this:

Every day, Paul sends a message to Nick containing an email address. You win the contest by sending an email to that address. You get a transcript of the network traffic coming in and out of Paul's account. According to the faq, you can send arbitrary packets to the server, but you can't intercept/modify the communication.

The problem should be clear now: Telegram's contest does not give the adversary enough power. The adversary doesn't doesn't get known plaintexts, can't choose plaintexts, can't choose ciphertexts, can't modify network traffic, or anything like we covered in the previous sections. The contest barely fits into the known plaintext attack (KPA) model.

If nobody wins the contest, it does not mean Telegram is secure. It means Telegram might be secure within the constraints of the contest. However, there are extremely weak systems that can survive a Telegram-style contest, so if nobody wins the contest, it won't give us any more confidence in Telegram's security.

So how good is Telegram's crypto?

Telegram's design seems to disregard all of the important crypto research from the past two decades. Their protocol is described here, and here's a diagram of their encryption:

Some problems are immediately apparent:

They use the broken SHA1 hash function.

They include a hash of the plaintext message in the ciphertext. Essentially, they are trying to do "Mac and Encrypt" which is not secure. They should be doing "Encrypt then Mac" with HMAC-SHA512.

They rely on an obscure cipher mode called "Infinite Garble Extension."

Some really weird stuff about factoring 64-bit integers as part of the protocol.

They do not authenticate public keys.

If their protocol is secure, it is so by accident, not because of good design. They claim the protocol was designed by "six ACM champions" and "Ph.Ds in math." Quite frankly, the protocol looks like it was made by an amateur. The tight coupling between primitives suggests the designer was not familiar with basic constructs, like authenticated encryption, that you can find in any cryptography textbook.

What should Telegram do?

Telegram's crypto is bad, and it needs to be scrapped. I know it's tough to throw away all of that work, but if they want to build a trustworthy product, it's what they need to do. Their protocol is already too complex to analyze (let alone prove secure), and adding band-aid fixes is only going to make it worse.

They should switch to an existing well-studied protocol like the one used by TextSecure. They need to bring in a real cryptographer to audit their design (and design process), and they need to make sure the programmers they've hired are qualified to write crypto code (most programmers are not).

If telegram wants, they can email me and I'll offer as much advice as I can. I think their hearts are in the right place, they just goofed on the crypto.

Telegram's Response

Telegram has responded to this post. I sincerely appreciate the time they took to reply, and I apologize for making them sign up for a Tumblr account to do it.

Here's a summary of their response and my replies.

Telegram notes in the contest FAQ that the scope of the contest will expand to active attacks if nobody wins this iteration. They should skip right to a contest that allows active attacks. The only reason not to is to avoid losing $200,000. It would not be more difficult for them to do. They would not need to set up any infrastructure for the contest except for a clear description of their threat model and criteria for an adequate attack demonstration.

Telegram justifies their use of SHA1 by noting that it has not been broken in practice (although there are theoretical attacks, so it is cryptographically broken), and that SHA1 is faster. That's not a good reason to use SHA1, especially since according to benchmarks, SHA256 less than 1.5x slower. The bottleneck is almost always in the network, not the encryption.

Telegram explains their use of Mac and Encrypt on their FAQ. They do not give a reason to use their system over the standard encrypt-then-HMAC, which is well-understood by cryptographers and has been proven secure.

According to their Tumblr reply, the 64-bit factorization is part of a DoS-protection scheme. Presumably it's just a proof of work and isn't part of their crypto. However, factoring is a poor choice for a proof of work, since it's vulnerable to lookup tables. A Bitcoin-style proof of work would have been better.

In the FAQ, Telegram attempts to argue for their system's security under KPA, CPA, and CCA. Their arguments are not convincing. They mistake the security of the primitive (AES in IGE mode) for the security of their use of the primitive. Just because AES in IGE mode is secure against known plaintext attacks does not mean the whole construction is. You have to look at the bigger picture.

Telegram's reason for creating their own protocol is as follows:

In order to achieve reliability on weak mobile connections as well as speed when dealing with large files (such as photos, large videos up to 1Gb and — coming soon — documents), MTProto uses an original approach.

In other words, they designed their own crypto for speed and reliability. I don't see how encrypt-then-HMAC is incompatible with reliability. As for speed, encrypt-then-HMAC-SHA1 would be faster, and encrypt-then-HMAC-SHA256 would not be significantly slower. @zooko points out that the BLAKE2 hash function is as fast or faster than SHA1, and much more secure.

The Emotiv EPOC is an EEG machine that can be connected to your PC wirelessly.

The protocol has been reverse engineered, and it turns out that the communications are encrypted with AES in ECB mode using a static key. Here's the key:

31003554381037423100354838003750

The Mozilla Firefox development team has done a horrible job bringing the latest versions of the TLS protocol to its users. These new versions of TLS, namely TLS v1.1 and TLS v1.2, fix critical security issues in the older version, TLS v1.0. Yet, despite the urgent need to update, Firefox is lagging behind to the point where it is now the only major browser that doesn't have TLS v1.1 and TLS v1.2 enabled by default.

These new versions are implemented in Firefox 26, and you can enable them by tweaking a setting in "about:config", but they still aren't turned on by default, so most users aren't benefiting from them. Instead of waiting for Mozilla to turn them on, you can do it yourself by setting:

security.tls.version.max = 3

Here's a simplified timeline of the TLS v1.1 and v1.2 deployment in Firefox.

In 2006, TLS v1.1 was standardized and published in RFC 4346.

In 2008, TLS v1.2 was standardized and published in RFC 5246.

In 2009, Mozilla created a ticket to implement TLS v1.2.

In 2010, Mozilla created a ticket to implement TLS v1.1.

In 2012, the TLS v1.1 implementation was finished.

In July 2013, the TLS v1.2 implementation was finished.

As of December 2013, TLS v1.1 and TLS v1.2 have not been enabled by default in the latest stable version of Firefox, version 26.

So, in summary, it took Mozilla four years to realize they had to implement TLS v1.1 after it was standardized. Once they did, it took two years to implement, and then another year just to get it turned on by default. I honestly don't know why it took so long.

The other major browsers (Chrome, IE, Opera, Safari) all had support for both new versions, turned on by default, by at least October 2013. Notably, Google Chrome had TLS v1.1 up and running all the way back in September of 2012.

I moved the Crypto Fails blog from Blogger to Tumblr. I did this mainly because Blogger started to feel clunky, and I like to be able to compose posts in markdown. I can also take advantage of the "ask questions" feature to make Crypto Noobs a little easier (and maybe I can start doing them more often than once per month).

What are side channel attacks and how do they affect cryptography?

Suppose your birthday is coming up soon, and your best friend told you that they bought a gift for you. You’re anxious to know what they got you, so you ask them:

"Is it a new watch?" “No.” "Is it a hat?" “No.” "Is it a computer?" “No.” "Is it a book?" “No.” "Is it a video game?" “No.”

You’re not getting anywhere. Your friend will say “No.” no matter what you guess, even if you guess right. You need another source of information. You try asking again, but this time you pay close attention to their actions as they reply:

"Is it a new watch?" “No.” (expression=neutral, eyes=looking at you) "Is it a hat?" “No.” (expression=neutral, eyes=looking at you) "Is it a computer?" “No.” (expression=neutral, eyes=looking at you) "Is it a book?" “No.” (expression=nervous, eyes=looking away from you) "Is it a video game?" “No.” (expression=relief, eyes=looking at you)

Now can you guess what your gift is? From these results, you can be pretty sure that your gift is a book. If you want to be even more sure, you can ask the questions again. If your friend’s expression and eye movements are always changing after asking, “Is it a book?” you can be pretty sure that’s what it is.

That’s a side channel attack. You’re getting no information from the actual data in the response (“No.”), but the way the response is delivered is leaking the secret information you want.

Computers don’t make side channel attacks quite so obvious. They don’t have faces to convey emotions. So how is the information leaked in a side channel attack against a computer? There are a bunch of different ways:

How much power the computer uses when it does something.

How long it takes the computer to do something.

Which areas of the computer’s memory have been accessed.

Unintentional electromagnetic radiation emanating from the system.

Sounds coming from the system (beeps, hard drives working, etc.).

The time that network packets get sent out of the system.

These are some of the ways a computer can unintentionally leak information about what it is doing and the secrets that are stored inside of it.

This leakage can be devastating to cryptography software. Even if the cipher is secure, there are no attacks against the protocol, and the implementation follows the specification exactly, a secret might still be leaked out through these avenues, which we call “side channels.”

The next sections present some real examples of side channel attacks. They should give you a good idea of how devastating these attacks are on cryptography software.

Timing Analysis of Keystrokes inside SSH

This attack was presented in Timing Analysis of Keystrokes and Timing Attacks on SSH by Dawn Xiaodong Song, David Wagner, and Xuqing Tian.

Secure Shell (SSH) is a secure way of connecting to another computer and controlling it with a shell (terminal). All of the commands and responses are encrypted and authenticated, so someone eavesdropping on your Internet connection should not be able to figure out what you're doing on the remote system.

The ciphers are good, the protocols are good, and the implementation is good. Even so, the trio of researchers realized that information about what the user still gets leaked, through the time between the user's key presses.

When connected to a computer over SSH, every time you press a key, your computer immediately generates an Internet packet and sends it to the remote computer. That means, if you're eavesdropping on an SSH connection, you see a packet sent shortly after each key press. You don't know which keys were pressed, but you know what times they were pressed, and, more importantly, the times between key presses.

The researchers showed that, when a user is typing, the time between their key presses leaks information about what they're typing. For example, on a QWERTY keyboard, the time between pressing "a" then "j" (which is on the home row and is pressed by the index finger of the left then the right hand) is going to be a lot shorter than the time between pressing "z" and "1" (which is pressed by the same finger and the keys are very far apart).

Using this fact, the researchers constructed an attack tool that extracts about 1 bit of information per character pair when a user is typing a password. This means that if you can observe an encrypted SSH connection, and the user types a password, the information leaked through the keystroke timings greatly reduces the number of passwords you'd need to search to find the right password.

To remove this side channel, SSH should send packets at a fixed rate, even if the user is not typing or is in between key presses. If a packet gets sent every 50 ms no matter what, and there is no way to distinguish a keystroke packet from a "chaff" packet, then the eavesdropper won't learn anything about the time between key presses.

Cache Attacks on the AES Cipher

This attack was presented in Cache Attacks and Countermeasures: the Case of AES by Dag Arne Osvik, Adi Shamir, and Eran Tromer. A similar attack was demonstrated by Daniel J. Bernstein in Cache-timing attacks on AES.

All modern computers have a "cache" between main memory (RAM) and the CPU. This cache speeds up access to areas of memory that have been used recently. If an area of memory has been accessed recently, it's probably in the cache, so accessing it again will be quick. If the area hasn't been accessed in a long time, it has probably been evicted from the cache, so accessing it will be slow. The difference in time can leak information about what a process is doing.

This attack was applied to the AES cipher in the two papers linked above. Essentially, fast implementations of AES use lookup tables, which are arrays used to quickly convert one value into another. The indexes AES uses into these tables depend on the secret key, so there's a possibility that the difference in memory access time caused by the cache can leak information about the secret key. That is exactly what the authors demonstrated.

The authors demonstrate two different techniques for extracting the key. I'll give a simplified explanation of each.

In the first, called the Evict+Time attack, they evict part of one of the lookup tables from the cache, so that all of the AES lookup tables are in the cache except for one index in one table, then they run the encryption. If the encryption accesses that index that has been evicted from the cache, it will run slower, otherwise it will run at a normal speed. So, by timing how long the encryption takes, they can figure out if that table index was accessed or not. Since the table index depends on the key, this leaks information about the key.

The second type of attack, called Prime+Probe, first completely fills the cache with the attacker's data. The encryption process is run, and as it is running, the parts of the lookup table that it uses are loaded from main memory into the cache. Since the cache is full of the attacker's data, some of it will have to be evicted to make room for the part of the table. Once the encryption is done, the attacker accesses their data again (to see which parts have been evicted from the cache), and this tells them which table indexes were used by the encryption process, leaking information about the key.

There is no good cross-platform cross-architecture defense against this kind of attack. The only sure defense is to write code whose memory access pattern does not depend on secret information. That means, among other things, no using secret information as indexes into an array.

Power Analysis of RSA

This attack was presented in Power Analysis Attacks of Modular Exponentiation in Smartcards by Thomas S. Messerges, Ezzy A. Dabbish, and Robert H. Sloan.

RSA is a public key cryptosystem. Encrypting a message involves raising it to the power of the secret key. This is done using an algorithm called "square and multiply."

Here's a simple way to think about it: Loop over all bits in the secret exponent, and for each bit, if it is one, perform a multiply operation then a square operation. If the bit is zero, do not perform the multiply, just go straight to the square operation.

It turns out that by watching the amount of power a device uses, you can determine whether the multiply routine executed or not. That leaks the corresponding bit of the secret exponent. If multiply was executed, the bit is 1, if multiply was not executed, the bit is 0. So, by watching the power usage, you can extract the entire secret key. Here's what it looks like in a simulation:

This is obviously a devastating attack, since it leaks the entire secret key. To defend against it, you have to make sure that the amount of power your code uses doesn't depend on secret information.

Noise Floor

At DEF CON 21, @0xabad1dea gave a talk in which she demonstrates how you can use cheap (~$15) software defined radio hardware to learn information about a (very unshielded) system, including getting a (very) rough view of what's being shown on the monitor.

Conclusion

There you have it. That's only a very small sample of the side channel attacks that have been found. I would love to have written about more, especially this one, but I don't want this post to go on forever.

Side channel attack research is still very active. If you're interested, check out some of the papers I've linked to and the papers that they cite. You can even try to implement some of the attacks yourself.

What is "Crypto Noobs"?

"Crypto Noobs" is a series of posts where I answer your crypto questions. Each month, I will select one question and answer it in the next "Crypto Noobs" post.

This study from Carnegie Mellon and UCSB analyzed 11,748 android apps that use crypto and found that 10,327 of them (88%) were flawed. They built a tool to check for extremely obvious crypto implementation errors like

Using ECB mode.

Using a non-random IV for CBC mode.

Using constant encryption keys.

Using constant salts for password hashing.

Using fewer than 1000 iterations in password hashing.

Seeding the random number generator with a static value.

Except for the “1000 iterations” one, these are all obvious flaws, and anyone who knows anything about cryptography should know that they are a bad idea. Especially “using constant encryption keys” - that’s insane. Anyway, here are their results summarized in a table.

Their results make two things clear:

You shouldn’t implement crypto yourself. Even when you have a high-level API.

CryptHook is a tool that hooks the send() and recv() system calls to apply encryption to a network application that does not provide encryption. The code is available here. It uses the same key for both directions of communication. Traffic flowing from the client to the server is encrypted with the same key as the traffic flowing from the server to the client. It tries to use GCM to provide message authentication, but unfortunately, since it uses the same key for both directions and doesn't use sequence numbers, it's possible to:

Replay a party's messages back to itself.

Re-order messages.

Selectively drop messages.

What are Initialization Vectors and how should they be exchanged?

tl;dr: The Initialization Vector (IV) is an unpredictable random number used to make sure that when the same message is encrypted twice, the ciphertext always different. It should be exchanged, in public, as part of the ciphertext.

We don’t want the ciphertexts to be the same when we encrypt the same message is because it leaks information. Suppose Alice is asking Bob a series of “yes or no” questions, and that the crypto software they’re using makes the mistake of always encrypting the same message to the same ciphertext.

Here is their encrypted conversation:

Alice: DCF0C50A96DC2D9B05F2AC4C24CB9B93

Bob: E0B554B341FF5632DE241FBF4B1DBB37

Alice: 6742FA9512C8C2ACE6942974C8C848FC

Bob: 824783C3B272FF7129F9E153EC10D1AE

Alice: C90BD345639368D951A8B5E267427514

Bob: E0B554B341FF5632DE241FBF4B1DBB37

Alice: AC797939F55E87C361A8F02B4CEA1A08

Bob: 824783C3B272FF7129F9E153EC10D1AE

As you can see, some of Bob’s ciphertexts repeat. The ones that are the same are highlighted in red and green. Since we know that Alice is asking Bob “yes or no” questions, we can assume that one of the ciphertexts corresponds to “yes” and the other to “no.”

Now, suppose we ask Alice what questions she asked Bob. Alice tells us she asked the following questions (in order):

Are you Bob?

Are you Eve?

Are you Smart?

Are you Tired?

Note: Alice tells us what she asked Bob, but not what Bob’s answers were.

If Bob answered the questions truthfully, then we find out that Bob’s first response, the ciphertext “E0B55…” is the encryption of “yes” and Bob’s second response, the ciphertext “82478…” is the encryption of “no”. So “E0B55…” is “yes,” and “82478…” is “no.” Now we know what Bob’s answers to the last two questions were:

Alice: DCF0C50A96DC2D9B05F2AC4C24CB9B93 <- Are you Bob?

Bob: E0B554B341FF5632DE241FBF4B1DBB37 <- yes

Alice: 6742FA9512C8C2ACE6942974C8C848FC <- Are you Eve?

Bob: 824783C3B272FF7129F9E153EC10D1AE <- no

Alice: C90BD345639368D951A8B5E267427514 <- Are you Smart?

Bob: E0B554B341FF5632DE241FBF4B1DBB37 <- yes

Alice: AC797939F55E87C361A8F02B4CEA1A08 <- Are you Tired?

Bob: 824783C3B272FF7129F9E153EC10D1AE <- no

So Bob is smart, but not tired. We can probably assume he's angry that we cracked his encryption, too.

To fix this problem, we have to make sure that encrypting the same message always results in a different ciphertext. We have to make sure that when Bob answers "yes", it encrypts to something different than the last time he answered "yes".

This is accomplished using either an Initialization Vector (IV) or a nonce.

An Initialization Vector is an unpredictable random number used to "initialize" an encryption function. It has to be random, and an adversary shouldn't be able to predict it before the message is encrypted. See here to learn why it needs to be unpredictable.

The term "nonce" comes from "number used once", which is exactly what it is. It's a unique number. It can be random, but it doesn't have to be. As long as it's unique (never used before).

IVs and nonces are used by encryption modes like CBC and CTR to make all plaintexts encrypt differently. The ciphertext is a function of the plaintext and the IV or nonce. When the same plaintext is encrypted many times, the IV or nonce will be different each time so the ciphertext will be different each time.

IVs and nonces do not have to be kept secret. They are usually prefixed to the ciphertext and transmitted in full public view.

IVs should be generated by a cryptographically-secure random number generator, and not derived from the secret key. CakePHP made the mistake of using the key as the IV, making its encryption very easy to crack.

Using a good IV doesn't automatically mean your crypto is secure. You have to authenticate your ciphertexts, too. When you do, don't forget to authenticate the IV.

What is "Crypto Noobs"?

"Crypto Noobs" is a new series of posts where I answer your crypto questions. Each month, I will select one question and answer it in a new "Crypto Noobs" post.

This post on How-To-Geek about generating passwords from the command line advocates generating passwords from the current date and time. The first command they give is (note double fail: base64-encoding hex):

date +%s | sha256sum | base64 | head -c 32 ; echo

They do provide a command that gives a good alphanumeric password:

tr -cd '[:alnum:]' < /dev/urandom | fold -w30 | head -n1

 However, they also mention this one:

date | md5sum

 About the above command, they say, "I'm sure that some people will complain that it’s not as random as some of the other options, but honestly, it’s random enough if you’re going to be using the whole thing." That is absolutely wrong and demonstrates a complete lack of understanding what a hash function is. Lessons Learned:

Hashing does not add randomness. The output of a hash is as random as its input.

This bit of php documentation has some interesting code:

$iv, 'key'=>$key); $fp = fopen('secret-file.enc', 'wb'); stream_filter_append($fp, 'mcrypt.tripledes', STREAM_FILTER_WRITE, $opts); fwrite($fp, 'Secret secret secret data'); fclose($fp); ?>

3DES takes a 192-bit key (actually 168), so the first two keys are taken from the first MD5 and the third key is taken from the second MD5. I have a strong suspicion that that alignment introduces some kind of vulnerability, but I can't quite put my finger on it. If anyone knows, please leave a comment. This tweet says it all:

@DefuseSec With documentation like that, it's no wonder we see so much crap code. :-\ — Adam Caudill (@adamcaudill) July 29, 2013

Lessons Learned:

Don't use MD5 to derive keys from passwords. Use PBKDF2.

Use a random, unique IV. Don't derive it from the password.

Here's a bit of password hashing fail. I'm not sure if it will win the Password Hashing Competition, but it certainly is novel. I really like how, after it goes through all of that sha1/md5/rot13 "encryption", it saves the plaintext to the database. Oh, and if it weren't for a misplaced '}', it would accept any password in the database, not just the one for your account. It's also vulnerable to SQL injection (pointed out by an Anonymous commenter). Hashing a password:

public function encryptData($string) { $stringORG = $string; $string = str_rot13($string); $string = md5($string); $string = substr($string, 5, 15); $string = sha1(SALT . $string); $string = md5($string); $string = sha1(SALT . $string); $string = str_rot13($string); $string = substr($string, 5, 15); $string = md5(SALT . $string); mysql_query("INSERT INTO `encryptions` (`encvalue`, `realvalue`) VALUES ('".$string."', '".$stringORG."');"); return $string; }

Testing a password:

public function tryEncryption($tried) { $query = mysql_query('SELECT * FROM encryptions'); while($row = mysql_fetch_assoc($query)) { $encVal = $row['encvalue']; $actVal = $row['realvalue']; } $actTried = $tried; $tried = str_rot13($tried); $tried = md5($tried); $tried = substr($tried, 5, 15); $tried = sha1(SALT . $tried); $tried = md5($tried); $tried = sha1(SALT . $tried); $tried = str_rot13($tried); $tried = substr($tried, 5, 15); $tried = md5(SALT . $tried); if($encVal==$tried) { if($actVal==$actTried) { return true; } } }

Lessons Learned:

When you encrypt something, make sure the plaintext is safely destroyed.

Hash passwords properly.