More Cryptography

My colleague Gen gave a very good primer on the basics of cryptography last week. In this post I’ll expand some more on the theory of cryptography, and in my next post I’ll talk about some of the main applications.

It is only in the last forty or so years that cryptography has been a formal science with mathematical backing. Prior to the 1970s, cryptosystems were usually designed in isolation and had little in the way of mathematical proof for their strength. It is the development of cheap, fast computing that has allowed cryptography to become a routine activity, and large amounts of theoretical work by government and academia in the 1970s on has created a systematic way of developing cryptosystems and proving their strength (or lack thereof!).

Terminology

Cryptography means literally “secret writing”. The parties communicating in cryptography are usually called Alice, “A” and Bob, “B”. A third party trying to eavesdrop on their communications is usually called Eve, “E”. We talk about ciphers, rather than codes – codes and encoding are a means of representing some message in another format, and in do not specifically imply secrecy.

Gen mentioned asymmetric cryptography, with a public and a private key. This is often referred to as “public-key cryptography”, because of the fact that one of the keys is public. Other encryption is called symmetric, because the same key is used for both encryption and decryption. This key has to be kept secret, thus symmetric cryptography is also called “secret-key cryptography”. A key feature of asymmetric encryption is that it is possible to establish a new, secret channel over a monitored communication channel – in other words, you can set up a secret session even if someone is watching every bit of traffic on your network connection. This is what you are doing every time you visit a secure website, or your Outlook mail client talks to the mail server.

I’ll explain one more cryptographic concept – the cryptographic hash. This is not a cipher as such. Instead, it’s a one-way, unique transformation of data of any length to a data string of a specific length, called the hash. One-way means you cannot find the original data from the hash, and unique means that different input data always produces a different hash.This might sound rather arbitrary and useless, but it is vital to the functioning of encryption systems.

Strength and Speed

Asymmetric encryption sounds like a better deal – you can set up a secure connection over a clear channel. Symmetric encryption is used far more often, however, because it is much faster and more space-efficient than asymmetric. The mathematical operations to perform asymmetric encryption (exponentiation or elliptic-curve calculations on big numbers) are much more demanding on a computer CPU than those for symmetric encryption. The usual process for a secure connection is for the client and server (browser and web server, Outlook and mail server) to perform a handshake with asymmetric encryption, use this secure channel to exchange a symmetric secret key, and then use symmetric encryption for the rest of the conversation.

Cryptosystems Become Obsolete

Computers are getting more powerful over time, and this has a specific meaning for cryptography. Systems that are strong when designed will usually be increasingly vulnerable to simple brute force attacks (trying every possible key against the encrypted message). Researchers will also work on the theory behind given cryptosystems, often finding weaknesses in the design or implementation, and leading to more efficient attacks.

A good example of this is the Digital Encryption Standard (DES), which is a US government standard first developed in the 1970s. This is a symmetric cipher with a 56-bit key size, and it has some very interesting features for the 1970s. IBM designed DES originally, and submitted it to the US government for approval. The National Security Agency (NSA) recommended some changes, and DES was accepted as a US government standard. Years later it was discovered that unclear changes recommended by the NSA at the time made DES more resistant to differential cryptanalysis (which was unknown at the time), and IBM admitted that this attack was known to IBM and the NSA at the time. Research has discovered other weaknesses in DES, however, and the short key length and cryptographic weaknesses means DES is no longer regarded as secure. It was first broken in 1997, and was replaced by AES (Advanced Encryption Standard) in 2002.

Some cryptosystems are designed with a variable key length, so keys can be made longer (and systems stronger) as required. Managing cryptosystems against performance and attacks is an ongoing process.

Next up – applications of cryptography!