Max Hodak Writings

Computer security

June 2013

In the most general terms, there is no such thing as computer security. It’s much easier to destroy security than it is to create it. Most of this article discusses specific techniques and technologies for securing data in the face of different classes of adversaries. This article is geared at “relative” laymen: people who are computer savvy, okay programmers, but not experts; for more sophisticated readers, Colin Percival’s Cryptographic Right Answers is a great read (and, unlike me, Colin is an actual cryptographer).

I’ll break up this post into two parts: a discussion of threat models, and a practical discussion of six classes of techniques:

Throughout this article, keep in mind that probably only symmetric encryption, strong hash functions, and one-time pads are effective against all adversaries. Discount everything else in proportion to your belief that someone can steal the decrypted data from the government.

What’s your threat model?

In the real world, attackers don’t go after the algorithm. Organized crime (of which there’s a lot on the internet!) isn’t going to have a breakthrough in the cryptanalysis of SHA-256. Instead, they’ll infect your computer with malware and log all of your keystrokes, or steal the plain text out of your computer’s memory. These types of attacks are called “endpoint” attacks or “side-channel” attacks. Side-channel attacks can be incredibly intricate. One research group showed that you could learn a lot about a victim’s information by looking at power consumption data, since the CPU had subtly characteristic behavior when it was processing the encrypted data.

Improperly constructed encryption, endpoint attacks (malware), and side-channel attacks are the real threat, and they’re endemic.

It’s important to be clear on what kind of security you need to create. Who are you defending against? How valuable is the data that you have? How long does it need to stay secure, assuming that your adversary is logging all of the encrypted text when you send it?

For four different extremes, your threat model might consist of:

Obviously, the range here is quite wide. If you’re an international terrorist, your security is probably an impossible problem. At the very least, nothing in this post will help you. I won’t discuss the first world nation-state adversary case here. Any global attacker (that is, an attacker who can see all communications at all times, even if it’s only ciphertext), is going to be a problem to defend against, and even moreso when national security assets are available to find you. Whether it’s an “oppressive regime” or a Western democracy is a moral distinction, but I’m not sure how important the difference is for security purposes. But, luckily, that isn’t usually who we’re interested in being protected from.

Some people will say, “but even in Western democracies we’re having privacy taken away!” Yes, but there are better ways to address that than treating the government as an adversary. We have a political process. Use it. The government isn’t malicious; it’s not out to get you. Yeah, not needing to trust anyone is nice, but if privacy is the issue, Washington is what you need, not PGP.

The other cases are much more tractable. The simplest case, casual hiding of basic data from unsophisticated attackers, can usually be solved without any cryptography at all. There are myriad “secret SMS” apps on the Android and iOS app stores, and only one or two use real encryption. In most cases, it doesn’t matter. Your 15-year-old classmate who’s after gossip isn’t going to get a memory dump of the handset, target you with a custom rootkit, or intercept wireless transmissions. A corporate attacker or foreign government, though, might.

Four important things to realize:

Netgear routers are famously vulnerable. And, they’re usually accessible from the internet. It’s very possible, therefore, to be owned as soon as you connect to your Wifi access point, before even visiting any webpages. And, once you’re infected, you’re done. There is no way to securely remove a virus. Depending on the level of paranoia, that hardware might be forever gone. The most sophisticated rootkits can hide in microcode on hardware, so even wiping the hard drive won’t save you.

Clearly security is hard. The gold-standard way to create computer security is with an “air gap” – that is, a computer with no internet connection, USB port, serial port, or CD-R drive. This creates an environment where data can flow “down” to that machine, but since it lacks any way of writing to media, unauthorized data can never leave. One good way to transfer off data – slowly – is to use QR codes and a camera. This gives a strong guarantee that the only data leaving the machine is authorized. Many highly confidential corporate environments include RF scanners in their security plan, and if you leave your cellphone on in your pocket you can expect to be promptly interrupted and asked to check it in.

Now, the forgoing is an awfully bleak picture, but it doesn’t matter for most people. That’s why it’s important to understand your threat model.

The key is to find a scheme that is likely to last for some time longer than the information will remain sensitive and/or actionable.

The techniques below are useful for anything up to, but not including, a first world nation-state adversary. In particular, I’m worried about corporate espionage and sophisticated organized crime, both of which are huge causes of loss every year. Organized crime is amazingly advanced on the internet and has control of almost unimaginably large botnets – networks of normal peoples’ compromised computers that are under the criminals’ control. The techniques here are designed to protect data from theft and not prevent intrusion – that’s a totally different game and beyond the the scope of this post. They also assume that the attackers have no legal authority to compel cooperation or key disclosure. I also assume that your partners are sophisticated, or at least trainable, and can use complex software that may not have a shiny, point-and-click interface. I also assume that the data being protected is of locally significant, but not globally significant, value. The aim is to cause your adversaries to decide to pick a different, easier victim. I assume that you are not their mythical whale.

First, a note about randomness

All sources of randomness are not created equal. Most random number generators are only “pseudorandom” – they follow some mathematical function which ensures “good distribution”, but they aren’t actually random (see the Mersenne twister for one popular algorithm). Pseudorandom number generators (PRNGs) start with a “seed” value, and if you invoke a PRNG twice with the same seed you’ll get the same sequence of numbers. You can’t use a PRNG for cryptographic applications. You might as well not be using any encryption at all. I’m not going to argue that using a PRNG is actually worse that not using encryption (if only because of the fact that the average attacker is probably not that sophisticated), but it’s pretty close.

There’s a philosophical debate to be had about whether true randomness is really possible in the physical universe, but in practice we derive “true randomness” from any number of phenomena. One popular mechanism that is easy to implement in cheap hardware is running current backwards through a diode at just above its breakdown potential, leading to a random series of penetrating electrons known as Avalanche noise. For higher security applications, the gold standard of random is to detect the decay events of a radioactive source. Unstable isotopes decay at a predictable rate, though the exact timing of an individual decay event is impossible to predict.

Many commercial randomness sources use true randomness but are perhaps biased in some way; for example, a diode breakdown source that’s accidentally influenced by a strong electric field in the room (say, a CRT monitor). This will add statistical structure to the random data in a way the weakens the resulting encryption.

After failing to keep your key properly secure, bad randomness is the classic way good encryption fails.

Public key encryption is useful for transmitting data.

Public key encryption (PKE) is built on the idea that some mathematical problem is “hard”. For example, if you find two large prime numbers and multiply them together, it’s impractical for anyone to ever figure out what the original numbers you used were. This is known as the “factoring problem”, from which the RSA problem – the basis for the RSA encryption scheme – is derived.

Public key encryption is also called asymmetric encryption, because it uses two keys: a private key and a public key. You generate a private key in secret and derive a public key from it, which you can distribute to the world. Whenever someone wants to send you something confidential, they simply encrypt it with your public key. Data encrypted with a public key can only be decrypted by the corresponding private key. This makes the encrypted data safe to send however they want – for example, over email – and doesn’t require you to ever have a trusted channel to exchange, say, a secret password ahead of time. The secret key never leaves your computer.

There’s a public infrastructure of key servers that host an index of public keys, like a phone book of PKE users. Using a server like http://pgp.mit.edu, you can easily search for an email address to see what public key you should use to encrypt a message for someone, even if you’ve never met them.

The two major asymmetric algorithms are RSA and Elliptic Curve Cryptography (“ECC”). As RSA is based on the factoring problem, ECC is based on the problem that it’s very difficult to compute the multiplicand for a point multiplication given an original and resulting point on a given elliptic curve. Don’t worry if that doesn’t make any sense; all that matters is that mathematicians have reasons to believe that it is a “difficult problem” for very deep reasons. ECC is sometimes also called “number-theoretic cryptography” because it depends on intuitions from pure maths.

RSA is much older than ECC. Ultimately, the only verification of security in cryptography is the test of time. Because of this, RSA should have an advantage. However, it is beginning to show its age in many respects. First, RSA requires much larger keys than ECC. A 384-bit ECC key is equivalent in security to a 3096-bit RSA key. This means ECC is faster in some cases, but this speed really doesn’t matter for most things.

People have wondered for years whether the NSA has broken RSA. While most people think that is unlikely, it is seen as a matter of time. For example, both RSA and ECC would be readily broken using a quantum computer. There are several companies working on quantum computers, which are well within the accepted laws of physics, and while we don’t believe any are available today with enough “qubits” to be useful for breaking cryptography, it’s instructive to remember that the first conventional computers were built in secret for breaking codes. (It’s also instructive to remember that the Enimga cryptosystem would have been unbreakable if it weren’t for user error.)

In my exceptional paranoia, it doesn’t help that RSA has never been rated for securing US Top Secret information. In fact, no public key cryptography is included in the NSA’s Suite B family of algorithms, and the Suite B guidlines note that “a key aspect of Suite B Cryptography is its use of elliptic curve technology instead of classic public key technology.”

I’m going to advocate an ECC-based key system, mostly because of the NSA guidance. There’s some reason to believe that when NSA officials described making an “enormous breakthrough several years ago” it had to do with breaking RSA, at least for some key length (a view Bruce Schneier finds plausible). It’s important to note that there’s never been a proof of the hardness of either the factoring problem or the basis for ECC. In fact, it’s probably the case that breaking a specific message encrypted with RSA is much easier than the factoring problem: whereas solving the factoring problem reveals the private key and all ciphertexts, solving the RSA problem only reveals one ciphertext.

Provided that the RSA problem is as hard as we presently think it is, modern key lengths mean that it would take multiples of the age of the universe to crack a ciphertext on a conventional computer. However, especially given quantum computing on the horizon, public key cryptography only creates publication delays.

Recommendation: Use PGP with a 4096-bit RSA/RSA key, but switch to ECC as soon as support becomes wider spread.

Symmetric key encryption is useful for storing data.

The “symmetric” in symmetric key encryption means that you use the same key to decrypt as you to encrypt. This creates a problem if you’re trying to transmit data to someone else and you don’t have a safe way to tell them the key (password) ahead of time. However, symmetric encryption can be theoretically much stronger than public key encryption, so if you’re only storing data locally, it’s the way to go. There are a bunch of historical standards for symmetric encryption, but today you should just stick with AES-256. AES-256 is a part of the NSA’s Suite B collection of algorithms and is used regularly to protect the highest level of classified information (or so we’re told). It should be sufficient protection from even the most motivated industrial espionage or organized crime. However, it only works if you’re very thorough with protecting your keys.

It’s a no-brainer to enable on-the-fly whole disk encryption for hard drives. On Ubuntu, LUKS is the easiest option. On Mac, it’s FileVault 2 (Lion and newer, not legacy FileVault on older machines). On Windows, TrueCrypt is great. TrueCrypt has a really cool hidden volumes feature that creates plausible deniability: you can create multiple passwords and if forced to disclose your password under duress (a technique known euphemistically as “rubber hose cryptanalysis”) you can disclose the password for the sanitized partition. Due to the way the data is protected, it’s impossible to prove that there’s any other data on the disk. The guarantee is better than just a “oh, you can’t prove it” – it’s impossible to tell if anything is really there or not and there are lots of better explanations for the rest of the disk than “secretly encrypted hidden volume”.

AES is known as a “block cipher”: it acts on fixed-length blocks of data at a time. If you have 200 bytes of data, you might encrypt it as 14 128-bit blocks (AES always uses a block size of 128 bits). Notice that 12 * 128 bits = 224 bytes: since the cipher acts on whole blocks, if your data is not evenly divisible by the block size you must pad your data so that it is. A good AES implementation will do this for you.

This brings us to ciper modes: you have to be careful about the relationships between blocks. The simplest ciper mode, Electronic Code Book (ECB), simply encrypts each block independently. This turns out to be a very bad idea: if two blocks have the same content, they’ll generate the same ciphertext, meaning that patterns present in the input data will be present in the ciphertext. Another mode, Ciper Block Chaining (CBC) XORs the input data from each block with the ciphertext from the previous block before encrypting, so that each cipertext block depends on all blocks leading up to that one. The first block requires an “initialization vector” (IV), and if the same data is encrypted twice with the same IV, the same cipertext will results. Reusing IVs over time weakens the security of the system. A third mode, Counter Mode (CTR), shares many security properties with CBC, with the big difference being that it is parallelizable. Both encryption and decryption can be done on blocks in parallel, whereas CBC must be done serially due to the relationships between blocks.

There are dozens of block cipher modes out there; CBC and CTR are both good options. The most important piece of information to take away from the last paragraph, though, is probably “ECB is not encryption.”

Recommendation: Use AES-256. If this fails you, it will be because you either didn’t properly protect your key, you used ECB mode, or there’s a flaw in the implementation.

Hash functions are useful for validating data.

Hash functions are mathematical functions that take arbitrary data and generate a fingerprint. For example, using MD5 algorithm:

MD5("hi this is a message") => "146581bccff06f2750bdc5c8f8f725bd"

Common uses for hash functions are to store passwords, publishing a fact that allows you to prove a statement at a later point in time without giving away the statement now, and validating the correctness of a downloaded file.

The two ever-present concerns with hash functions are collisions and pre-image attacks. A collision is said to occur when two inputs generate the same hash output. Since a hash function is projecting a large space onto a smaller one (the inputs to MD5 above could be any size, but the output will always be 32 bytes long), every hash algorithm will theoretically have an infinite number of collisions. In a magical hash function where this wasn’t the case, infinite compression of arbitrary inputs would be possible and several fundamental laws of physics would be invalidated. Really. However, this doesn’t mean that it should be easy to find an algorithm’s collisions. Once collisions can be easily generated for an algorithm, it’s time to abandon that algorithm. That’s what happened with SHA1, MD4, MD5, and countless others that preceded the family of algorithms currently in heavy use. Once you can generate collisions on demand, you’re halfway to a preimage attack, where you can generate a set of likely input texts from a given hash. As should be obvious, it’s impossible to determine a single input that generated a hash, but the correct choice is usually apparent.

There are tradeoffs that go into a choice of hash function:

Back in the early days of the internet, everyone hashed passwords with MD5. Since MD5 was developed to hash lots of data at once, it’s very fast. It’s so fast on modern hardware, in fact, that people just made lookup tables of all of the MD5 hashes for passwords shorter than a given length. These lookup tables, called Rainbow Tables, are now searchable online. Developers started adding unique “salts” – random unique data – to passwords before they hashed them to thwart a single global Rainbow table, but MD5 is still so fast that it’s usually feasible to brute force the salted password anyway.

Bcrypt is designed to be CPU intensive and has a configurable “work” factor that can be increased over time as computers get faster. Scrypt is an extension to bcrypt that is expensive in memory (RAM) as well as CPU, meaning that even if you made custom password-cracking hardware it would be very difficult to accelerate. Bcrypt and scrypt can be configured to take as long as 100 ms or more to hash a single password. That delay isn’t enough for humans to notice, but it completely rules out the idea of brute forcing a hash. Whereas MD5 hash rates can exceed 500 million per second, bcrypt or scrypt will only do 10 - 100 per second.

There’s an ongoing debate on the internet about a method called PBKDF2 as opposed to bcrypt. Technically, PBKDF2 is recommended by NIST over bcrypt, mostly because it’s better understood cryptanalytically (PBKDF2 is built on SHA-256). It’s hypothetically better accelerable on hardware like GPUs and FPGAs, though. I think “use bcrypt” is good to a first approximation.

Recommendation: Use bcrypt for passwords and SHA-256 for everything else.

Signatures are useful for authenticating data.

Normally when people think of digital signatures they think of typing their name in a box to e-sign a contract. “Real” digital signatures are possible through the same public key techniques mentioned above. The basic idea of PKE as applied to asymmetric encryption is that if you encrypt a plaintext with a public key, only the possessor of the corresponding private key can recover the original message. If you instead encrypt a plaintext with a private key, however, anyone possessing the corresponding private key can verify that you are in possession of that private key.

Let’s say that someone sends you an email encrypted for your public key. They send it from an email address you recognize, but email addresses are easy to spoof. How do you know if it really came from them? Well, they could sign the message with their private key to produce a signature that will easily let anyone with the public key verify that the person who sent the message is in possession of your partner’s private key. Of course, the key could have been stolen, but that’s probably not what happened, especially since private keys should also be symmetrically encrypted. (See the discussion on threat models.)

Another concrete example of this in use is to distribute trusted software for devices like iPhones. You don’t want to run just any software that ends up on the device, since it could be malicious. Instead, once the software is compiled and packaged, the trusted party uses their private key to digitally sign the distributable. The public key is broadcast (or hard-coded into the handset), so the device can know that the program doesn’t come from a hacker.

Signatures don’t usually create non-deniability on their own. If Bob gets a message from Alice signed by Alice’s private key, Alice can always claim that her key was stolen.

There’s an equivalent scheme for authenticating email domains called DKIM, or Domain Keys, the goal is which is to make it harder to spoof sending addresses. It relies on the client checking the DKIM of the sending domain against the signature in the email to work, though; the email will still go through in all cases, though the receiving server will have an opportunity to drop it if the signatures don’t line up. Be sure to use at least 1024-bit DKIM keys. 512-bit keys are now easily broken.

It’s surprisingly easy to overlook this stuff. There’s a famous case of an engineer finding that Google.com was only using 512-bit DKIM keys, which he assumed must be a recruiting puzzle. He spoofed an email as Sergey Brin to Larry Page to declare victory. It wasn’t a recruiting puzzle, and three days later Google was on 2048-bit keys.

Recommendation: Use the same PGP setup as for public key cryptography. If you run your own email domain, don’t forget to set up DKIM.

Transport layer security protects web traffic.

Transport layer security (TLS), the most popular implementation of which is SSL, is commonly used to encrypt web traffic. If you’ve ever seen HTTPS, a green address bar, or a lock icon in the address bar, that’s TLS. Using TLS is a very good idea; if you ever use a site that requires a login at a public location like a coffee shop and don’t use TLS, it’s trivially easy for someone to steal your session and impersonate you. (Wifi security like WEP or WPA can also fix this for the coffee shop example, even if the website doesn’t support SSL. But anyone listening from somewhere past the wireless router could still intercept your session.)

In general, you should be careful using insecure public wifi – if you do connect to a public network, make sure you’re always using HTTPS connections. The HTTPS Everywhere browser extension helps with this, but it can’t do anything if the server simply doesn’t offer SSL.

For example, let’s say I want to intercept traffic to Facebook.com. Since Facebook uses SSL, if I created just any certificate and put myself in between you and Facebook, your browser would throw an error and abandon ship. However, if I convinced (or paid off) one of these less reputable certificate authorities to sell me a certificate for Facebook.com, your browser would happily accept it.

TLS is relies on a hierarchy of trust stemming from mutually agreed upon certificate signers. Anyone – you, me, Verisign, Google – can easily generate SSL certificates. For a certificate to be trusted, though, it has to be signed in turn by another certificate already known to the user’s browser. This means that the final word lies with the browser vendors. While it’s hypothetically possible for anyone to get approvals from all of the browser vendors to be a trusted issuer, expensive compliance – including procedures like elaborate “Key Ceremonies” – and auditing requirements mean that there’s a relatively high barrier to entry.

If the browser teams catch onto a bad issuer, they’ll blacklist it overnight to revoke any certificates its ever issued, impacting every customer they’ve ever sold to, not just the certificates found to be fraudulent. This is known as the “Internet death penalty”. In the few cases where a bad registrars have been found, no one has hesitated to follow through with revocation.

Many browser now “pin” the certificates of certain high-profile sites like Google or Facebook in the browser itself and avoid relying on the web of trust for those targets. Of course, that means that when Facebook needs to change its certificate it has to make calls to Firefox, Google, Microsoft, and Apple, but that’s an acceptable cost.

TLS is based on public-key cryptography, so in addition to these problems, if RSA is broken, so is SSL.

By default, if an attacker logs encrypted web traffic and later discovers the private key they can then decrypt the back traffic. However, a configuration known as Perfect Forward Secrecy (PFS) exists that guarantees that if an attacker gets the private key, they’ll only be able to decrypt future traffic. PFS is a property of the key exchange protocol – the process by which the server and your browser agree on security when you connect. PFS works because the actual data being sent is encrypted with a Session Key, not the SSL certificate itself; formally, PFS is the property that even though the Session Key is derived from the SSL certificate, the Session Key will not be compromised even if the SSL certificate is at a future date. See Elliptic Curve Diffie-Hellman Key Exchange (ECDHE) for more information.

SSL keys shorter than 2048 bits are now considered weak. 1024 bit SSL keys can be cracked on a consumer laptop in a matter of days.

Recommendation: If a site isn’t using TLS/SSL, it’s trivially easy for someone to log and read everything you do. Use SSL on all sites you own, and insist on it on sites you use.

One-time pads are the only way to guarantee true security.

A one-time pad, or OTP, is random data exactly the same length as the message you want to encrypt. By combining each character from the message and the pad you can generate a ciphertext that has no statistical structure at all. To decrypt, the recipient will need the same random data that you used to encrypt.

For example, consider encrypting the text “Hi this is a message” by XORing the message with a one-time pad:

Text:         H  i  \s t  h  i  s  \s i  s  \s a  \s m  e  s  s  a  g  e
Text Bytes:   48 69 20 74 68 69 73 20 69 73 20 61 20 6D 65 73 73 61 67 65
One Time Pad: 06 0F BF 18 F5 DD 08 F4 E6 D7 14 C7 9D 1C 1A 98 6C 18 9B D0
Ciphertext:   4E 66 9F 6C 9D B4 7B D4 8F A4 34 A6 BD 71 7F EB 1F 79 FC B5

The one-time pad is a very simple idea with a clear proof of security. OTP requires prior planning between the communicating parties and a careful attention to the security of the pad. Most one-time pad systems fail because the pad (the random data) is not properly secured. This extends to the generation of the pad: if your randomness source is not random enough, or you otherwise vulnerable to any number of side channel attacks, the pad won’t be secure. The cautions about sources of randomness above are doubly important when working with OTPs.

An OTP can never be re-used, hence the “one time”. Re-using a pad, even once, is disastrous for the security of the system. Since OTPs can never be re-used, and an OTP must be the same length as the data being encrypted, using an OTP-based system is space intensive and requires substantial forethought to communicate effectively over an extended period of time.

A properly used OTP is “perfectly secure” because the amount of information necessary to decrypt is exactly the same as the amount of information in the message. In other words, the ciphertext has exactly zero structure. Different pads will let you “decrypt” the data as any message of the given length, and the length can be obscured by simply inserting extra NULLs into the message.

Supposedly the phones on Air Force One use an OTP-based system for communicating with the Pentagon.

Recommendation: You probably don’t need a one-time pad system. If you do, you already know it and aren’t learning much from this article.

###

Does using encryption make you more of a target? I think that depends on your threat model. Since encryption is relatively rare today, if you ever ended up on the government’s radar and they found that you were heavily encrypting all of your communications, it will probably at least make them curious. Of course, in the US there’s the Fourth Amendment, Fifth Amendment, and a huge slew of case law preventing them from going on fishing expeditions through your inbox. But if they have a reason to be curious to begin with, it will probably make you stand out.

At the other end of the spectrum are corporate hackers, who we don’t care if it makes you a target. You should assume that you’re a target anyway and they don’t get to complain that your inbox is unreadable once they steal your password. On balance, there are few downsides to using encryption in the US, but internationally it depends on the jurisdiction. In many countries it’s sadly just illegal, so check your local laws.