Tuesday, December 28, 2010

Modern Digital Encryption: an Overview

(original post 5/7/2010)

Earlier I wrote about how to best avoid the dangers of surfing the web. Think of this as part two of my earlier blog post: Security on the Web. This time I'm going to focus on securing data on your computer, AKA your local machine. If your like me and love security-related topics, or watching paint dry, this article is for you.

Sometimes it is necessary to store information on your computer that could be considered sensitive information. If you were to secure paper records, such as the deed to your home, you would put it in a safe or bank deposit box. But how do you secure the private data residing on your computer's hard drive? Encryption! Encryption can be used to protect data "at rest", such as files on computers and storage devices (e.g. USB flash drives). In recent years there have been numerous reports of confidential data such as customers' personal records being exposed through loss or theft of laptops or backup drives. Encrypting such files at rest helps protect them should physical security measures fail.

Computer encryption is based on the science of cryptography, which has been used as long as humans have wanted to keep information secret. Although the history of cryptography is very interesting, I'll keep to the point. Encryption has come a long way since the ciphers of Julius Caesar. I'll point out the basic forms in modern use today.

Symmetric and public-key encryption

The first method is called symmetric-key encryption. This requires both a key and a password to decrypt the file. The key is used to unlock the ability to guess what the password is. Without the key, prying eyes would not even be given the opportunity to guess what the password is. As you can guess, there is no way of sending a key securely over a network, such as the Internet, without an additional layer of security. Otherwise the key itself would be pulled from the data stream while in transit. What this means is that you must copy the key to a storage device and physically carry that device over to each computer that you want to decrypt files from. In other words the sender and receiver must share the key in a secured way in advance.

The second method is called asymmetric-key encryption, AKA public-key encryption. This method solves the problem of the first method (sending a private key across a network) by involving two keys. It uses a key pair based on prime numbers of long length. This makes the system extremely secure, because there is essentially an infinite number of prime numbers available, meaning there are an infinite number of possibilities for keys (source).

The key pair that consists of a public key and a private key act exactly as their name implies. The public key goes out publicly. It is there for the taking for any computer on the network that wants it. Hiding within that public key is an algorithm directly related to your private key that can only be used by your your private key for decryption purposes. Essentially, the public key provides encryption for the private key. It's a dual-layer encryption operation. The reason this works is because the key used to encrypt a message is not the same as the key used to decrypt it. The keys are related mathematically, but the private key cannot be feasibly (in actual or projected practice) derived from the public key.

It's a tough concept for the average person to wrap their head around. So if you find that explanation confusing, go to this HowStuffWorks article for further clarification.

Modern banking institutions also use digital certificates, which establish trust from whom you want want to make a secure connection with. They use a third party certificate authority that verifies that they are who they say they are.

Here are a couple of good analogies pulled from Wikipedia:
An analogy to public-key encryption is that of a locked mailbox with a mail slot. The mail slot is exposed and accessible to the public; its location (the street address) is in essence the public key. Anyone knowing the street address can go to the door and drop a written message through the slot; however, only the person who possesses the private key can open the mailbox and read the message.
An analogy for digital signatures is the sealing of an envelope with a personal wax seal. The message can be opened by anyone, but the presence of the seal authenticates the sender.
And so it is the combination of these two that allow secure commerce over the Internet.

Security of key lengths

So just how secure are these algorithms? In the 1970's the United States developed an encryption standard called DES, which had a 56-bit encryption specification. This offered 70 quadrillion (70,000,000,000,000,000) possible combinations. This was considered more than adequate at the time. No one ever dreamed that computing power would advance to the point of making this standard obsolete. Well, guess what? That's exactly what happened! A modern consumer desktop computer could easily crack this in short order. It's too bad the U.S. government never heeded the implications predicted by Moore's Law around the same time period.

Necessarily, a new encryption standard was created: AES. This standard calls for 128, 192, or 256 bit length keys. The number of possible combinations increases exponentially in proportion to the key length. So a 128-bit key would have more than 300,000,000,000,000,000,000,000,000,000,000,000 key  combinations [source: CES Communications].

I should point out that there is a physical argument that a 128-bit symmetric key is secure against brute force attack. Let me back up a second and clarify. Many cryptographic systems have no (practical) known weaknesses and so the only way of "cracking" them is to use a "brute force attack" by trying all possible keys until the message can be decoded. The Von Neumann-Landauer Limit implied by the laws of physics sets a lower limit on the energy required to perform a computation, such as breaking an encryption cipher.

In order to simply flip through the possible values for a 128-bit symmetric key (ignoring doing the actual computing to check it) would require 2128 − 1 bit computations. If we assume that the calculation occurs near room temperature, ~25C, we can apply the Von Neumann-Landauer Limit to estimate the energy required as ~1018 joules, which is equivalent to consuming 30 gigawatts of power for one year. Whammy Blammy! The full actual computation—checking each key to see if you have found a solution—would consume many times this amount.

Note: this argument assumes that the register values are changed using conventional set and clear operations which inevitably generate entropy. It has been shown that computational hardware can be designed not to encounter this theoretical obstruction (see reversible computing), though no such computers are known to have been constructed.

The amount of time required to break a 128-bit key is also daunting. Each of the 2128(340,282,366,920,938,463,463,374,607,431,768,211,456 to be exact) possibilities must be checked. A device that could check a billion billion keys (1018) per second would still require about 1013 years to exhaust the key space. This is a thousand times longer than the age of the universe, which is about 13,000,000,000 (1.3×1010) years. Wowie Zowie!

Key length caveats

So why would you ever want to use more than 128-bit encryption? Ask the CIA. Their guidelines state that all information considered "Top Secret" is to be secured using the AES specification of no less than 192-bit encryption. An underlying assumption of brute-force computations is that the complete keyspace  is used to generate keys, something that relies on an effective random number generator, something that is still in the works.

For example, a number of systems that were originally thought to be impossible to crack by brute force have nevertheless been cracked in this way because the key space to search through was found to be much smaller than originally thought, due to a lack of entropy in their pseudorandom number generators.  These include Netscape's implementation of SSL (famously cracked by Ian Goldberg and David Wagner in 1995) and a Debian edition of OpenSSL discovered in 2008 to be flawed (source).

Using a truly random seed would fully utilize the entire keyspace, ensuring that AES keeps true to it's theoretical brute-force protection. The Swiss are working on such a system now using quantum cryptology in which key ciphers are seeded by a number generated using photons -- tiny, massless packets of light. Since this method uses physics instead of math to create the key used to encrypt the data, there's little chance it can be cracked using mathematics. This type of method looks extremely promising. For more information on this subject see Heisenburg's uncertainty principle and How Quantum Cryptology Works

Ironically this solution, quantum physics, may also present a challenge to the security of our data in the future. If quantum computing proves to propel computing power significantly ahead of the Moore's Law projection, it could present serious challenges to any encryption scheme. If any minor flaw is found in a cryptographic system, it effectively lowers the key length. As previously stated, this would be an exponential reduction rather than a direct linear reduction. Which means that a 128-bit key could possibly be cracked. Let's also not forget that there is a cosmological chance that any brute-force attack could discover the cipher in a short period of time due to pure dumb luck chance.

Because of these concerns, and the concerns of paranoid conspiracy theorists, most software applications that generate keys will go all the way up to 4096-bit encryption support. This is kinda like cutting your butter with a chainsaw. My personal opinion is that 256-bit encryption is just fine for the rest of our lifetimes. Besides, you're much more likely to get rubber-hosed or black-bagged. These are euphemisms for getting coerced or burglarized, respectively, for the possession of your cipher.

Believe it or not, there is actually a solution to these issues as well! Well, partially anyways. There is something called a hidden volume that offers plausible deniability. In countries such as Iran you can be targeted and prosecuted for encrypting your own data. As preposterous as that sounds, there are still many dictatorships around the world that smite free speech and treat you as a revolter if you even speak your opinion about something negative relating to your sovereign authority. Deniable encryption can offer things such as an encrypted decoy or even hide encrypted data altogether. Also, storing encrypted data on an Internet server that has no traceable connection to you is another preferred method.

Well, it's happened again. I've wrote too much and you've undoubtedly squandered another perfectly good block of time reading this. Signing out. 

1 comment: