Ciphers: Hiding in Plain Sight

Image via Wikipedia

My last post talked about cryptography, its motivation and its primitive techniques.  In this post, we shall learn about modern security techniques and how they keep us secure.  We will touch upon the mathematical basis behind modern cryptography, talk about symmetric key cryptography and talk about a technique for exchanging secrets out in the open known as the Diffie-Hellman key exchange.  To start off the discussion, I would like you to consider the following situation.  Alice is a diplomat in a foreign country and has some sensitive information that she would like to communicate to Bob, her superior.  The only means of communication available to Alice is a phone line that she and Bob knows is constantly being monitored and eves dropped on.  How could Alice and Bob communicate a message in a secure manner starting from this state?  We saw in the last post how, with some pre-decided shared secret (such as a codebook when using a substitution cipher), one could attempt to obscure a message and make it hard (but not too hard) to guess.  More curiously, starting with no secret state between the two parties, is it possible to establish a secret codebook?  In other words, sharing no secrets beforehand, is it possible to begin sharing a secret?

Keys, Ciphers and Texts

Let us quickly establish some terminology to make the discussion easier to follow.  If you wanted to send a message to your friend, the raw message that is human comprehensible is known as the plain text.  You would never want to transmit a plain text message out in the open to your friend if you ever wanted the message to remain private.  Anyone could capture the data and could store it for further analysis.  To ensure your friend’s and your privacy, you need to use a cryptographic algorithm, a security technique, to obscure and hide the plain text such that only your friend is able to recover and read the plain text.  The obfuscated message is known as the cipher text.  The process of converting the plain text to cipher text is known as encryption and the converse process of recovering the plain text from the cipher text is known as decryption.  Two people will need to agree on what cryptographic algorithm they are using as each encryption technique can only be decrypted with one matching algorithm.

Most cryptographic algorithms deal with exchanging or sharing one private secret that underpins the entire technique known as a key.  The key used in cryptographic algorithms need to be closely guarded as any agent that controls the key is able to compromise the system – they may be able to read private messages, inject faked messages into the system or confuse the participants in some other way.  An example of a cryptographic system is the caesar cipher, where the key is the one number – the offset that each letter in the plain text is rotated by to arrive at the cipher text from the plain text.  The key is preshared amongst the participants who are privy to the message and must be kept confidential.

Confusion and Diffusion

Claude Shannon, the father of modern information and communication theory, published a number of papers right after World War II describing and formalizing concepts that are core to modern communication system.  He defined two concepts – confusion and diffusion.  Confusion refers to the complexity of the relationship between the key and ciphertext of a message.  In a caesar cipher, the relationship between the key and the cipher text is straight forward.  Each character in the ciphertext is independently rotated by an offset that is equal to the key.  This is not a confusing cryptographic algorithm.  The more confusing an algorithm, the more involved and less straight forward an attack on it is.  Note that the confusion of an algorithm is not related to how well it is understood or how well it is described.  It has more to do with how straight forward or how precarious an algorithm is.  There are plenty of well-studied and widely understood algorithms in the cryptographic community that are considered to have a high confusion.

Diffusion refers to the degree to which a small change in the plain text affects the cipher text.  A cryptographic algorithm is a high diffusion will cause the cipher text to vary a lot given a minor change in the plain text.  This helps thwart attempts to decode portions of an encrypted message while not knowing what the rest of the message means.  It also helps prevent statistical or distribution based attacks.  The best algorithms guarantee a very strict form of diffusion known as the Strict Avalanche Criterion.  This condition states that if a single bit of plain text is ever changed, each bit of the cipher text independently has a 50% chance of changing.  Or in other words, fiddling even slightly with the plain text should make the cipher text look unrecognizable.

Elementary Mathematics

Given two prime numbers, it is trivial to multiply them to produce a product.  We have a number of quick approaches to doing this and even the elementary school multiplication technique is reasonably quick at multiplying numbers — even really big ones.  Now, let’s try the opposite problem.  Given a large number that is the product of two prime numbers, can you find the prime numbers that will multiply to it?  In other words, can you factorize a given number into its prime factors?  You may realize that this is a much harder problem.  There is no straightforward way of knowing which numbers divide a given number.  There are tricks (such as divisibility tests) and some specialized algorithms but there is no general purpose way of factoring a number quickly.  Most techniques are not that much faster than simply trying a bunch of numbers in a brute force approach.  This problem is known as the prime factorization problem.  This is the type of problem that modern cryptography utilizes.  The algorithms utilize a mathematical problem that is easy to perform in one direction but extremely difficult and time-consuming to perform in the other direction.

Skeletons in the Closet

A Permutation-Substitution network

Let us look at the work horse of modern cryptography – the symmetric key algorithms.  These algorithms take a block of input and a string of bits known as the key and perform a reversible operation on it.  The key is secret and is shared between the participants who wish to write and read messages.  The operation can be written as a combination of substitution and permutation operations known as S and P blocks.  The key is usually weaved into the plain text using a simple operation such as bit-wise XOR.  As an aside, if you were wondering what Randal Monroe was talking about in this comic, now you know.  These operations, when designed correctly, correctly add confusion and diffusion to a message block.  When a big message needs to be encrypted, it is usually split up into a set of blocks and each block is encrypted.  But since we don’t want people to mathematically attack these blocks using frequency analysis (such as the one we used for the Caesar cipher), we chain each block together, feeding the output cipher text of one block to the input of the next block along with the plain text (usually through an XOR as well).  This makes sure that a change in the plain text in one block is propagated throughout the rest of the text, completely changing it.  This operation is known as cipher block chaining.  At this point, our cipher text looks like complete and utter gibberish.  It can be safely broadcast out in the open with the knowledge that only the intended recipient will be able to decrypt and understand the message.

When a web-browser sends your credit card info to iTunes or Amazon or any other internet vendor, these are the principles it uses.  There are a number of other steps involved (such as verifying that the website really is Amazon and that you really meant to access it) and the algorithms described here a pitifully simple when compared to their real-life brethren which are part of SSL (Secure Socket Layer) and HTTPS (Hyper-Text Transfer Protocol Secure).  Nevertheless, just as a toy airplane uses the same principles of flight as a real aircraft, the simple algorithm discussed above should describe the underlying mathematical techniques behind modern cryptography.  When used correctly, these kinds of algorithms can provide us with enough security and privacy that even with a computer the size of the entire earth, it would take more than the lifetime of the universe for an attacker to decipher or decrypt one of these messages in an unauthorized manner.

Open Secrets  (Advanced Math Warning)

Diffie-Hellman Key Exchange

One of the problems that modern cryptography addresses is the problem of securely establishing shared secrets over a hostile communication channel.  If Alice, from our foreign diplomat scenario, wanted to contact Bob but they have no pre-established secrets (or keys), they must be able to, in a secure manner, exchange keys.  Knowing that every word they utter is going to be heard and eves dropped on, how are they ever agree on something secret when they don’t have anything secret beforehand?  Well, we use a hard-to-reverse-engineer problem such as the one mentioned above.  We will use modular arithmetic for this problem.  If you have not encountered modular arithmetic before, Wikipedia has a good introduction to modular arithmetic here.  Let Alice and Bob publicly agree on a prime number p and a number g which is a primitive root modulo p.  g is a primitive root modulo p if for any  integer i that is coprime with p, there exists an integer k such that .  In other words, g can multiplicatively generate the group of integers modulo p.  It generates all integers   This exchange of p and g can happen in the open.  It can be assumed that any interested malicious party has access to p and g.  Now, both Alice and Bob each pick a secret value – let’s call them a and b.  Alice knows a.  Bob knows b.  These two numbers will never be transmitted publicly.  Alice instead sends Bob a derived value A such that and .  Deriving a from A is an extremely hard problem akin to the one we discussed above.  It is known as the discrete logarithm problem.  Bob does a similar thing to transmit B such that and .  Note that Alice cannot decode b from B and Bob cannot decode a from A. It seems we haven’t managed to communicate anything!  But notice something quite ingenuous:

Both Alice and Bob can derive a shared secret which is an integer where .  This is a unique integer that cannot be easily guessed by anyone overhearing without solving the discrete logarithm problem.  This joint secret can then be designated the key for further communication.  This method of sharing a common secret over a malicious channel is known as the Diffie-Hellman key exchange.  At the end of this exchange, both participants in the key exchange have a shared secret that they can then us as an appropriate key.  Care must be taken to make sure that p is not very small and satisfies certain properties that allow it to not be guessed quickly.