display | more...

This is the original name for IBM, standing for Computing Tabulating and Recording Company. This company was formed in 1911 by a merger between Hermann Hollerith's Tabulating Machine Company and some other companies. Thomas J. Watson changed the name to International Business Machines Corporation 1924.


Also, CTR is an abbreviation for "Choose the Right," one of many catch-phrases of the Mormon Chruch, more properly known as the Church of Jesus Christ of Latter-Day Saints. The intent of this particular piece of propaganda is, I suppose, roughly equivelent to "Do the Right Thing." You can buy all sorts of hats, keychains, shirts, and assorted novelties emlazoned with this TLA. Mormons think they're quite risque and witty when they pun this to "Choose the Left."

CTR is counter mode, one of the NIST-recognized modes of operation of a block cipher, such as AES. However, it is not limited to any particular block cipher, and provides the same security or insecurity properties (in terms of the underlying block cipher's security) for any block cipher. In fact, CTR mode could even be used with a secure non-invertible "cipher", such as a good keyed hash function. However I know of no cases where this has been analyzed (or done). In essence, CTR mode transforms block cipher into a stream cipher in a parallelizable manner.

We assume the two parties have a shared key K. Like most stream ciphers, CTR mode creates a keystream out of the key K and an initialization vector ("IV") I. This keystream doesn't depend on the plaintext in any way. The ciphertext is just the plaintext, XORed with the keystream. In particular, the following is essential for security: No portion of the keystream may ever be repeated! (If an attacker identifies 2 ciphertexts with a repeating keystream, then the XOR of them is the XOR of the 2 corresponding plaintexts; this immediately becomes trivial to break.)

To re-use the same key for multiple messages, an initialization vector I is randomly selected by the sender in a manner which ensures no repetition of keystream will occur. I is transmitted (insecurely!) to the other side, and the keystream is

EK(I+0), EK(I+1), EK(I+2), ...
This is XORed with the plaintext, to give the ciphertext. That is, a counter is encrypted, and the result XORed with the plaintext; the rest are "technicalities", but ones required (if not sufficient!) for a secure system. Note that unlike (most) other block cipher modes, CTR doesn't require any padding: if the last block is shorter than the blocksize of the underlying cipher, just don't use the excess bits from the last encrypted block!

CTR also has these neat properties:

  1. Decryption proceeds in exactly the same manner as encryption. In particular, ...
  2. ... Only the block cipher's encryption needs to be implemented! This can be a bonus in small environments (not to mention the fact that fewer lines of code suggest fewer bugs).
  3. Both encryption and decryption are embarrassingly parallel -- each block can be processed separately.
  4. Encryption can be precomputed, by precomputation of the keystream. (Decryption cannot usually be precomputed, as the IV I is not known to the other side in most protocols that use CTR mode. There is no explicit weakness that comes from advance knowledge of the keystream, but randomizing and transmitting I makes synchronization (always a problem with stream ciphers!) easy, and block sizes today are large enough to make the "lost" counter values a small problem.)

You can create other variants of counter mode, by choosing some other form for your counter. For instance, a linear feedback shift register can be used instead of the regular counter. If the underlying block cipher is any good, it doesn't matter which type of counter you pick. However, an LFSR or similar (a Gray code could be used, though I know of no such usage) might be easier or faster to implement in hardware.

It can be shown that the ciphertext for block i, Pj⊕EK(I+j), is both hard to predict and reveals no more information about Pi than the information that the cipher EK(⋅) reveals about I+j. For suppose an attacker had a method for revealing information about X=Pj from X⊕EK(I+j) for many values of I+j. Both I and j are known to the attacker, so that attacker could break the encryption EK(I+j) at these points, merely by pretending to break the cipher for X=EK(I+j).

The major problem with CTR mode is that, as a stream cipher, it is very vulnerable to modification. For instance, say Mallory knows that Alice is planning to wire Bob the phrase

ILOVEYOU.
Jealous Mallory will be unable to forge this message without information, or even to read it once Alice sends it. But if Mallory is in a position to replace Alice's messages with his own, he merely writes down
ILOVEYOU.
IHATEYOU.
XORs the two lines, and then XORs Alice's message with his own modifier. When Bob decrypts, he will read "IHATEYOU", and assume it came from Alice. This ease of bit flipping means that authentication must be used with CTR mode. CBC also has a problem with a similar type of message forging, but it leaves more trails and cannot be used to flip single bits undetected.

So CTR mode MUST be used with authentication. Authentication tends to lessen advantages 3 and 4 above (by its nature, authentication is not parallel or known in advance), but CTR mode is still a useful and mature encryption mode -- particularly if you can find a protocol known to be safe and free of patent issues.

Another, less severe, weakness is that the encrypted counter used in CTR mode cannot ever be re-used with the same key. To overcome this, IVs must be selected very far apart from each other. When using AES as your encryption algorithm this becomes much easier -- the block size is 128 bits, so e.g. the draft for using CTR mode for IPsec says (in essence) to select the first 96 bits as IV, and pad I with another 32 zero bits. As long as no IV is ever selected twice, and as long as no packet exceeds 232×128 = 239 ~ 5×1011 bits, no counter value will ever be re-used. Ciphers with smaller block sizes (such as DES) may find these restrictions more severe.

Further reading:

  • The IETF's Internet draft draft-ietf-ipsec-ciph-aes-ctr-05.txt is a specific protocol for using AES in CTR mode as an ESP protocol for IPsec.

Log in or register to write something here or to contact authors.