A new technique, developed by IBM, may allow us to protect our messages against tampering for little more than the cost of encryption - but only if they'll let us use it.
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

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

Now we encrypt with the one-time pad:
- - the key
- - the plaintext message
- - 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.

- - the ciphertext
- - the key
- - 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.

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

When we decrypt this tampered message, the plaintext is rather different:
- - new ciphertext (digit-wise sum)
- - the key
- - the plaintext: digit-wise subtraction (ignore carry)
- - transfer
- - from account 123
- - to account 654
- - 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.