This started life as a diary entry but I was encouraged to post
it as a story. If I get the energy, I might even write more
than one of these, and try and put together some snippets that
add up to an introduction to those parts of cryptology and data
security that I understand.

Let's suppose you're writing a banking application. And suppose
you encrypt with the One Time Pad, the only cipher proven
secure. To make the illustration simpler, we'll pretend your
message, and your key, consist entirely of decimal digits:

03 123 654 000123
means
03 - a code meaning transfer (that I just made up)
123 - from account 123
654 - to account 654
000123 - the sum of $1.23

Now we encrypt with the one-time pad:

92364162348364 - the key
03123654000123 - the plaintext message
95487716348487 - ciphertext: digit-wise sum (ignore carry)

Of course I generated the key by banging on the keyboard, but a
real one-time pad would be generated in a secure way and used
only once.

Decryption is simple - just subtract.

95487716348487 - the ciphertext
92364162348364 - the key
03123654000123 - the plaintext: digit-wise subtraction (ignore carry)

This method is perfectly secure, literally, as far as
confidentiality is concerned. But what about security against
tampering?

It turns out that if you hold account 654, and you can tamper
with this message in transit, you can change things very much to
your advantage. Just add a 9 to the 6th digit from the end.

95487716348487 - ciphertext before tampering
00000000900000 - tamper string
95487716248487 - new ciphertext (digit-wise sum)

When we decrypt this tampered message, the plaintext is rather
different:

95487716248487 - new ciphertext (digit-wise sum)
92364162348364 - the key
03123654900123 - the plaintext: digit-wise subtraction (ignore carry)
03 - transfer
123 - from account 123
654 - to account 654
900123 - the sum of $9001.23

What can you do? One solution might be to use digital
signatures. If every message is signed with the private key of
the sender, it's integrity will be preserved by the signature
scheme. This works, but it's massive overkill: digital
signatures are very slow to compute. In general, when you've
got a shared secret with the other party, you want to use
symmetric, secret key techniques rather than assymmetric, public
key techniques, since they tend to be more efficient in every
way. And the secret key equivalent of a digital signature is a
Message Authentication Code, or a MAC.

A MAC is a very short (perhaps 64 bit) addenum to a message that
verifies it hasn't been tampered with. To generate, or verify
the MAC, you need the MAC secret. A randomly generated message
will have only one chance in 2^64 of passing the MAC check.
MACs are very like message digest functions (otherwise known as
hash functions; MD5 and SHA are examples) except with a secret
ingredient that you need to generate or verify the digest.
Indeed, there are simple ways to use a function like SHA to make
a MAC simply by sprinkling in a secret along with the data being
hashed. If you need encryption and message integrity, just
append a MAC to the message, then encrypt the whole thing.

But for some environments, like smart cards, you might find that
the only cryptographic primitive you've got room for is the AES
block cipher. NIST standardised on a block cipher because block
ciphers are to cryptologists what towels are to hitch hikers -
you can turn them to useful objects in pretty much any crypto
situation. And it's pretty simple to MAC with a block cipher.
Divide the message into blocks M_1 .. M_n; start with a start
value unique to this message R, encrypt it with the block
cipher to make X_0 = E(R), then make X_i = E(X_(i-1) XOR M_i),
and use X_n as your MAC.

This kind of MAC is known as CBC-MAC - because it's exactly the
same as CBC mode encryption, except that you throw away all but
the last block when you've finished. This means that when you
MAC and encrypt, you're effectively doing the work of
encrypting the message twice. It's occured to quite a few
people that there must be a way of doing the work only once, and
getting both encryption and message integrity out of one block
cipher pass over the message. But it's not as easy as it looks,
and lots of attempts to solve the problem have been broken.

It now seems that the problem is solved. NIST put out a
call to help create standard chaining modes to go along with
the standard block cipher, and one of the submissions - by
Charinjit S Jutla of IBM - proposes chaining modes (IACBC, IAPM)
that give both encryption and integrity securly for little more
than the cost of one alone. A flurry of new activity has
resulted, and now there are several excellent chaining modes
with this property.

Unfortunately, it seems likely that all of these techniques will
be subject to a patent held by IBM. Unless NIST can persuade
IBM to give the world a royalty-free license to these techniques
in return for the credit of being the name behind a national
standard, it seems we may be faced with a choice between giving
IBM ownership of our protocols, or having our encryption run at
half the speed we could.