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').
The ideal block cipher will have the properties that:
- For most blocks B and keys K, E(K, B) is not very similar to B.
- For most blocks B and C which differ by one bit, E(K,B) and E(K,C)
will differ by much more than one bit. - Given E and K, for any block B, it's easy to compute E(K,B)
and E-1(K,B) - Given E and an encrypted text B, it's hard to compute either
the encryption key, or the plaintext block.
What happens to the block? It depends a lot on the particular block cipher. But in
general, it's treated as a set of sub-blocks, which are, in turn, treated as a sort of
large alphabet. The block is encrypted using what amounts to some substitutions, and some
transpositions, performed in sequence. In many block ciphers, there's a fairly simple
basic mechanism for substitution and transposition, which is repeated multiple times to
produce a final result. The specific set of substitutions and transpositions is determined
both by the specifics of the block cipher being used, and by the encryption key
used for the message. So the way that the key gets incorporated in the encryption of a
single block in a block cipher is by selecting the particular sequence of substitutions
and transpositions on the elements of the block.
Of course, there's a huge problem with the description so far, even given how
incomplete it is. Not all messages that we want to encrypt are the same size, but we've
only described the basic idea of encrypting a single block! Filling in that gap makes it
clear why this kind of crypto is called a block cipher. Take a message of arbitrary size,
S. To encrypt it with a block cipher with block size B, you break the message into
⌈S/B⌉ blocks, padding out the last block in some way to make it full. Then you
encrypt the blocks individually one at a time, and then...
You were expecting me to say something like "output them", right? Sorry. Not that
simple. There's another little trick for block ciphers. You don't really just
do the blocks in sequence, and then combine them. You usually add something: some kind of feedback between the blocks, some kind of transposition to re-order them, etc. Without that, you can get really poor results. Wikipedia has a fantastic example of what happens if you naively just encrypt each block, without any feedback or transposition. The
first figure to the right is a bitmap image of Tux the Linux penguin without any encryption. The second image is the Tux bitmap, encrypted with a block cipher without
any feedback or transposition.
So, given a message that consists of multiple blocks, you don't want to just naively
encode them and combine them into a message. In fact, there's no one answer to "How do you
generate the encrypted blocks and put them together to produce the ciphertext?" The answer
depends on something called the ciphers mode of operation.
I hate the term "Mode of operation". It's one of those terms that's so mundane that it
doesn't sound like it describes something important or technical. It sounds like
IBM-manager-speak for trying to pad out a description, to make it sound deep. You know,
like when a manager says "form-factor" instead of "size". But it really is something very
important. There are two key functions performed by the mode of operation (hereafter
"MoO"): the first, I've already mentioned: re-assemble the separately encrypted blocks to
produce a ciphertext message. The second is to provide an extra layer of security. Used
naively, two identical blocks of cleartext will produce two identical blocks of
ciphertext. That's bad: it gives someone trying to crack the message a major clue about
the structure of the message. The mode of operation can define some kind of additional
state mechanism which will alter the ciphertext, so that even identical blocks of
plaintext will generate different blocks of ciphertext.
The naive method of just encrypting each block separately and concatenating them is a
valid mode of operation, called the electronic codebook (ECB) MoO - it's just a lousy one
that no one in their right mind would use, because it provides such pathetic security.
As I get to real examples of block ciphers, I'll describe more modes of operation, but I'll use one here: the cipher-block chaining MoO. In cipher-block chaining (CBC) mode,
you maintain a state vector the size of a block. You initialize that with something
computed from the encryption key. Then, for each block, you first do a bitwise exclusive-or of the plaintext block with the state vector. Then you encrypt the modified plaintext, and set the state vector to the value of the encrypted block. So
in CBC mode, the blocks are output in sequence, but the ciphertext of each
block depends on the encryption key, the cleartext, and the ciphertext of the previous
block.
The selection of a mode of operation is critical for ensuring that the encryption
system works appropriately for your application. Selecting an appropriate MoO involves some fairly hairy tradeoffs between (among others):
- Ease of cracking;
- Ease of detecting errors
- Ease of detecting tampering
- Ease of detecting improper message duplication
In particular, most of the basic MoOs can provide either message
integrity (meaning that you can be confident that you got the complete message without
errors or tampering), or message confidentiality (meaning that you can be confident
that no one other that the intended recipient received the message). Basic MoOs
can't provide both.
The first major standardized block cipher was called DES, for "data encryption standard". It was a variation on one of the first published block ciphers, an IBM system called lucifer. In the next post, I'll describe the DEA - the data encryption algorithm of the DES. It's a pretty typical example of a block cipher. It's fairly complicated, and so it deserves a post of its own to describe its
basic mechanism, and its modes of operation.
- Log in to post comments
In the second paragraph you have " and B-1 (the decryption function)". I think you mean 'E' rather than 'B'.
You have &rciel; instead of ⌉ in paragraph 5.
The Wikipedia article with the penguin picture
Interesting article in your ongoing encryption series! Thanks for not writing about Sarah Palin.
I'm curious: why not use data compression prior to the cipher? Would that not destroy most of the structure of the message, removing most of the clues as to its content?
Heh. I used the same pictures when I talked about block cipher modes of operation on my blog. Wikipedia's good for something after all.
There's one more important requirement: given B, B', and E, it is difficult to compute K ("known plaintext attack"). Otherwise it would be easy to crack formatted messages that have a stable preamble.
And yes, compressing the message before encryption is a good idea. It also saves real bandwidth. Encrypted text isn't compressible.
BTW, the Wikipedia articles on encryption are quite good.
"why not use data compression prior to the cipher?"
The purpose of encryption is to attempt to guarantee safety against attackers that know the encryption algorithm.
Almost all compression algorithms/programs available today prefix their output with some header. This header can be used as a partial known-plaintext attack. In particular, if you know that the first 2 or 3 bytes of the plaintext input, then your decryption attacks only need to look at the first few bytes of the first block to be encrypted to quickly select from among the set of possible keys via brute force.
Even worse, some algorithms are actually able to be analyzed such that if you have a partial plaintext and the ciphertext, you can analyze the algorithm such that you can directly generate the set of keys that could have lead to the ciphertext.
This kind of attack is why a zip archive using standard pkzip encryption with more than 3 files is able to be cracked instantly.
I suppose that makes sense. But surely compression would make the job of making it difficult to crack the cipher dramatically easier, as it significantly reduces the number of patterns in the code?
I suppose, though, that if the compression header needs to be dealt with carefully anyway, the performance of compression may make it complete infeasible to use it as a matter of course in encryption.
You suggest that some MoO's can offer "message confidentiality (meaning that you can be confident that no one other that the intended recipient received the message)".
I simply cannot see how that could possibly be accomplished. Suppose the MoO causes us to output a particular encrypted text E1. Then suppose a coin is flipped: if it comes up heads then a copy of E1 is sent to Alice. Afterward, (regardless of the coin flip) a copy of E1 sent to Bob. Bob knows E1, and may know K and B as well. But regardless of what E1 contains, Bob doesn't know the outcome of the coin flip... so how can Bob know whether Alice has read it?
Of course, you're probably thinking of a different attack mechanism when you speak of message confidentiality... perhaps some certain category of man-in-the-middle attacks. Just what IS it that can be prevented by certain MoO's (but not others)?
The compression header isn't any worse than other known headers. All commercial software (like MS Office) use headers to identify the format of the file. If you don't like it, prefix the message with some random garbage ("salt").
I don't know what MarkCC plans write in this series, but I would suggest describing the use of Rainbow Tables, i.e. how to speed up brute force key search.
I'm pretty sure that message confidentiality means that only the intended recipient might recieve the plain-text. The trade-off being that even they might not get it if it was tampered with or corrupted.
Regarding your propery #3, wouldn't E-1 ideally be hard to compute, so as to make attempts to brute-force it more time consuming?
"For most blocks B and C which differ by one bit, E(K,B) and E(K,C) will differ by much more than one bit. "
Ideally, E(K,B) and E(K,C) should look random with respect to one another.