Ok, away from politics, and back to the good stuff. When I left off talking about
encryption, we were looking at
RSA, as an example of an asymmetric encryption system.

Since it’s been a while, I’ll start off with a quick review of RSA.

Asymmetric encryption systems like RSA are based on computations that are easy to perform if you know the keys, and incredibly hard to perform if you don’t. In the specific case
of RSA, everything is based on a pair of very large prime numbers. If you know those two
primes, and you know the public key, it’s really easy to compute the private key. But
if you don’t know the two prime numbers, then even given the public key,
it’s incredibly difficult to compute the private key.

To be a bit more specific, in RSA, you get a pair of large prime numbers, P and Q. You
compute from them a totient of their product, which is the number
N=(P-1)×(Q-1). Then you arbitrarily pick a public exponent, E, which is
smaller than N, and which is prime relative to N. You can then compute
the private key exponent, D. If you know what P and Q are, it’s pretty easy to compute
D.

Once you’ve got D and E, your public key is the pair is (N,E), and the private key is the pair is (N,D).

If you’ve got a plaintext message M, then encrypting it with the public key
is done by computing M^E mod N. If you’ve got a ciphertext C encrypted
with the public key, then decrypting it is done by computing C^D mod N.

Encrypting a plaintext with the public key is exactly the same process
as decrypting a ciphertext produced with the private key. And vice versa.

Continue reading →

Technorati Tags: cryptography, public-key, encryption, RSA, asymmetric encryption

The most successful public key cryptosystem in use today is RSA – named for its inventors Rivest, Shamir, and Adleman. I first learned about RSA in grad school from one of my professors, Errol Lloyd, who was one of Ron Rivest’s students. Errol is without a doubt the best teacher I’ve ever had (and also a thoroughly nice guy). If you want to go to grad school to study algorithms, you frankly couldn’t do better than heading to Delaware to work with Errol. I have very fond memories of Errol’s class where we talked about this. He’s got a way of teaching where he doesn’t come out and tell you anything; what he does is ask questions that lead you through the process of figuring it out yourself. That’s an incredibly effective way to teach if you can carry it off. Personally, I can’t. And I’ve never known anyone except Errol who could do it for a topic like RSA encryption!

Anyway, moving on… In general, public key cryptosystems are based on problems that are easy to solve computationally in one direction, but really hard to solve computationally in the other. In the case of RSA, the basic underlying problem involves prime numbers: if you’ve got two really large prime numbers, then multiplying them together is easy; but if you’ve got a number that’s the product of two really large primes, factoring it is very hard.

Continue reading →

I’ve been trying for a couple of weeks to put together a couple of interesting posts on the cryptographic modes of operation for confidentiality and integrity, and I just can’t do it. I’m finding it boring to write about, and if it bores me to write it, I know there’s no way that it’s going to be engaging to readers!

So, I’m going to move on. I’ve explained the basic idea of the message authentication code as an integrity check, and I’ve described one simple way of integrating it into a common mode of operation. If you’re really interested in learning more, I recommend Bruce Schnier’s book on cryptography, which has ton of material on modes of operation and protocols, how they work, and how they can fail.

Meanwhile, I’m going to move on to something that doesn’t bore me to write about, and therefore hopefully won’t bore you to read about: asymmetric cryptography, also commonly referred to (although not entirely accurately) as public key cryptography.

Continue reading →

In my last cryptography post, I wrote about using message authentication codes
(MACs) as a way of guaranteeing message integrity. To review briefly, most ciphers
are designed to provide message confidentiality – which means that no one but the
sender and the intended receiver can see the plain-text of the message. But
ciphers that provide confidentiality don’t necessarily make any guarantees that
the message received is exactly the message that was sent. There are a good number
of cryptographic attacks that work by altering the message in transit, and
depending on the cipher, that can result in a variety of undesirable
results.

For example, if you use DES encryption with the ECB mode of operation,
you can insert new blocks anywhere in a message that you want. By using
a replay attack (where you take encrypted blocks from other messages using
the same encryption, and resend them), an attacker can alter your messages, and
you won’t be able to detect it.

So in addition to just confidentiality, we need to provide integrity. What does integrity really mean? Basically, it expands the definition of the
decryption function. Written as a function signature, confidential message
decryption is a function decrypt : ciphertext × key → plaintext. With message integrity, we add the
option that decrypt can return a result saying that the message is invalid: decryptinteg : ciphertext × key → (plaintext | REJECT).

Continue reading →

Now, we’re finally reaching the point where the block-cipher stuff gets really fun: block cryptanalysis.

As I’ve explained before, the key properties of a really good
encryption system are:

1. It’s easy to compute the ciphertext given the plaintext and the key;
2. It’s easy to compute the plaintext given the ciphertext and the key;
3. It’s hard to compute the plaintext given the ciphertext
   but not the key;
4. It’s hard to compute the key.

That last property is actually a bit of a weasel. There are really a wide variety of attacks that try to crack an encryption
system – meaning, basically, to discover the key. What makes that
statement of the property so weasely is that it omits the information available to the person trying to crack it. In the first three properties, I clearly stated what information you had available to produce a result. In the last, I didn’t.

There’s a reason that I weaseled that. Partly, it’s because a correct statement of it would be ridiculously long and incomprehensible; and partly because it’s often deliberately set up differently for different encryption systems. You can design systems that are extremely strong against certain attacks, but not so good against others. There’s no universally ideal encryption system: it’s always a matter of tradeoffs, where you can handle some scenarios better than others.

Today we’re going to look at one particularly fascinating attack that’s used against block ciphers. It’s called differential cryptanalysis.

Continue reading →

So, as it turned out, I made a major screwup in my post earlier today on modes of operation. Rather than just edit the post, I’m adding a new post with the corrected description of the counter mode, and a bit of explanation. I figure that if I screw up badly, it’s more honest to make a second post explaining the error than it is to just correct it and pretend that all was well.

What I got wrong was the order in which things happen. In the counter mode,
you encrypt the counter using the key, and then you exclusive-or the result of that with the plaintext to get the ciphertext. The plaintext never enters the block cipher; the block cipher just produces a complex and random looking block of bits which are then used to obscure a block of plaintext.

What I said in the original post was that you exclusive or the plaintext with the counter, and then run it through the block cipher. In my screwed up version, the plaintext is being put through the block cipher mechanism; in the correct version, it’s not. Below is some of my psuedo-python showing my screwed up CTR mode,
and the (hopefully) correct CTR mode. I’ve also included a diagram of the correct CTR mode.

def EncryptWithMarksScrewedUpCTR(blocks, ctr, key):
for b in blocks:
encrypted = encrypt(key, b ^ ctr)
ctr = ctr + 1
output(encrypted)
def EncryptWithRealCTR(blocks, ctr, key):
for b in blocks:
e_ctr = encrypt(key, ctr)
encrypted = e_ctr ^ b
output(encrypted)
ctr = ctr + 1

This can make a big difference in the effectiveness of the cipher against various attacks. I’m not going to get into details now, but over the course of future posts, I hope that I’ll be able to make it clear why changes like this can have huge impacts on
the security and quality of a cipher.

Sorry for the slow pace of the blog lately. I’ve been sick with a horrible
sinus infection for the last month, and I’ve also been particularly busy with work, which have left me with neither the time nor the energy to do the research necessary to put together a decent blog post. After seeing an ENT a couple of days ago, I’m on a batch of new antibiotics plus some steroids, and together, those should knock the infection out.

With that out of the way: we’re going to look at how to get from simple block ciphers to stream ciphers, using the oh-so-imaginatively named modes of operation!

As a quick refresher, block encryption specifies an encryption scheme that operates on fixed-size blocks of bits. In the case of DES, that’s 64 bits. In the
real world, that’s not terribly useful on its own. What we want is something called
a stream cipher: a cipher that’s usable for messages with arbitrary lengths. The way to get from a block cipher to a stream cipher is by defining
some mechanism for taking an arbitrary-sized message, and describing how to break it into blocks, and how to connect those blocks together.

Modes of operation are formal descriptions of the way that you
use block encryption on a message that’s larger than a single block. Modes of operation (MOOs) are critical in making effective use of a block cipher. Of course, there’s always a tradeoff in things like this: you have to choose what properties of your encrypted communication you want to protect. Particularly for DES encryption, the standard MOOs can provide confidentiality (making sure that no one can read your encrypted communication), or integrity (making sure that your communication isn’t altered during transmission), but not both.

Continue reading →

As promised, now we’re going to look at the first major block
cipher: the DES. DES stands for “data encryption standard”; DES was the first encryption system standardized by the US government for official use. It’s an excellent example of a strong encryption system; to this day, while there are several theoretical attacks, there’s no feasible attack on a single DES-encrypted message that’s better than brute force. The main problem with DES is the shortness of its key: only 56 bits, which makes it downright practical to implement brute-force attacks against it using today’s hardware.

DES works with 64 bit blocks, and a 56 bit key. As an interesting aside, there are some serious questions about just why the standard key was 56 bits. Officially, the key length is 64 bits, but during the standardization process, the key was modified at the request of the NSA so that 8 of the bits were used as parity checks – that is, as extra bits that could be used for checking the validity of a key. 8 bits for parity checking on a 56 bit key is really overkill – in fact, putting parity checks into the key at all is really rather questionable. There’s been a lot of speculation that either
the NSA knew some kind of trick that could be used against a 56 bit key, or that 56 bits put the encryption within the range of what they could crack using a brute force attack. But no one has ever admitted to either solution, and as far as I know, no one knows of any way that a 56 bit key could have been feasibly cracked using brute force with the technology of the time.

Anyway – getting past the politics of it, it’s still a really interesting
system. It’s a rather elegant combination of simplicity and complexity. It’s got a simple repetitive structure based on lookup tables, which gives it its deceptive simplicity; but those lookup tables are actually an implementation of a very complex non-linear discrete mathematical system.

Continue reading →

Where encryption starts getting really interesting, in my opinion, is
block ciphers. Block ciphers are a general category of ciphers that
are sort of a combination of substitution and transposition ciphers, and
sort of something entirely different. They’re really fascinating
things, but they’re pretty complicated.

The basic core of block ciphers is encryption of blocks. A block is
a fixed-length series of bits. The basic cipher is a pair of functions (E,E^-1), where E (the encryption function) takes a block B and a key K, and generates a new block B’=E(K,B), which is the encrypted form of the block; and E^-1 (the decryption function) takes a key and an encrypted block, and returns the original plaintext block: B=E^-1(K,B’).

Continue reading →

The second major family of encryption techniques is called transposition ciphers. I find transposition ciphers to be
rather dull; in their pure form, they’re very simple, and not very difficult
to crack, even without computers. But some of the most sophisticated
modern ciphers can be looked at as a sort of strange combination of
substitution and transposition, so it’s worth looking at.

A transposition cipher doesn’t change the characters in the plain-text when it generates the cipher-text – it just re-arranges them. It applies some kind of permutation function to the text to produce a re-arrangement, which can be reversed if you know the secret to the the permutation.

Continue reading →