CAST (cipher)

CAST is a general procedure for constructing a family of block ciphers; individual ciphers have names like CAST-128 and CAST-256.

The original work on CAST was in Carlisle Adams' PhD thesis . A well-known paper is "Constructing Symmetric Ciphers using the CAST Design Procedure". . There is also a US patent on some of the techniques.

F function and S-boxes

CAST ciphers are Feistel ciphers using large S-boxes, 8*32 rather than the 6*4 of DES. They are primarily designed for software implementation, rather than the 1970s hardware DES was designed for, so looking up a full computer word at a time makes sense. An 8*32 S-box takes one K byte of storage; several can be used on a modern machine without difficulty.

In earlier Feistel ciphers, DES and GOST, the F function is essentially one round of an SP Network. These ciphers use eight 6*4 or 4*4 S-boxes to get 32 bits of S-box output. Those bits, reordered by a simple transformation, become the 32-bit output of the F function. Avalanche properties are less than ideal since each output bit depends only on the inputs to one S-box. The output transformation compensates for this, ensuring that the output from one S-box in one round affects several S-boxes in the next round so that good avalanche is achieved after a few rounds.

CAST ciphers, and Blowfish, use bigger S-boxes and do not use S-box bits directly as F function output. Instead, they take 32-bit words from several S-boxes and combine them to form a 32-bit output, so that the F function has ideal avalanche properties — every output bit depends on all S-box output words, and therefore on all input bits and all key bits. With the Feistel structure and such an F function, complete avalanche — all 64 output bits depend on all 64 input bits — is achieved in three rounds. This also requires fewer S-box lookups than the eight in DES or GOST so the F function, and therefore the whole cipher, can be reasonably efficient.

No output transformation is required in such an F function, but one may be used anyway; CAST-128 has a key-dependent rotation.

The CAST S-boxes use bent functions (the most highly nonlinear Boolean functions) as their columns. That is, the mapping from all the input bits to any single output bit is a bent function. Such S-boxes meet the strict avalanche criterion ; not only does every every bit of round input and every bit of round key affect every bit of round output, but complementing any input bit has exactly a 50% chance of changing any given output bit. A paper on generating the S-boxes is Mister & Adams "Practical S-box Design" . Bent functions are combined to get additional desirable traits — a balanced S-box (equal probability of 0 and 1 output), miniumum correlation among output bits, and high overall S-box nonlinearity.

The first CAST cipher (in the thesis) was a Feistel cipher with 64-bit blocks, a 64-bit key, 8 rounds with 16-bit round keys, a very simple key schedule, and six 8*32 S-boxes. For the F function, split the 32-bit input into 4 bytes and the round key into 2 bytes. Run each of the 6 bytes through a different S-box to get 6 32-bit outputs and combine those outputs using XOR. This cipher was not much used; when people mention "CAST", they almost always mean the widely deployed CAST-128.

Resisting linear & differential attacks

One objective of the CAST design procedure is to produce ciphers that are not vulnerable to either linear cryptanalysis or differential cryptanalysis . These are the only known attacks that break DES with less effort than brute force. More generally, they are the most powerful known cryptanalytic methods of attacking block ciphers. Both, however, require large numbers of known or chosen plaintexts, so a simple defense against them is to re-key often enough that the enemy cannot collect sufficient texts.

CAST goes further, building a cipher that is provably immune to linear or differential analysis with any number of texts. The method, taking linear cryptanalysis as our example and abbreviating it LC, is as follows:

start from properties of the F function, particularly the bent functions in the S-boxes

derive a limit m, the maximum possible quality of any linear approximation to a single round

consider the number of rounds, r, as a variable

derive an expression for e, the effort required to break the cipher by LC, in terms of r and m

find the minimum r such that e exceeds the effort required for brute force, making LC impractical

derive an expression for c, the number of chosen plaintexts required for LC, also in terms of r and m

(LC with only known plaintext requires more texts, so it can be ignored)

find the minimum r such that c exceeds the number of possible plaintexts, 2^blocksize, making LC impossible

A similar approach applied to differentials gives values for r that make differential cryptanalysis impractical or impossible. Choose the actual number of rounds so that, at a minimum, both attacks are impractical. Ideally, make both impossible, then add a safety factor.

This type of analysis is now a standard part of the cryptographer's toolkit. Many of the AES candidates, for example, included proofs along these lines in their design documentation, and AES itself uses such a calculation to determine the number of rounds required for various key sizes.

CAST-128

CAST-128, also called CAST5, is the best-known and most widely used CAST cipher. It replaced IDEA in PGP in version 3.0 and is specified in all versions of the Open PGP standard . Nortel and their spin-off Entrust also used it in several products; Adams worked for both companies.

CAST-128 is a Feistel cipher with 64-bit blocks and 16 rounds. Key sizes from 40 to 128 bits are supported; 128 is almost invariably used. There are eight 8*32 S-boxes, four used in the key schedule and the other four in actual encryption. Round keys are 37 bits.

The F function XORs the input with 32 bits of round key, splits the result into bytes and runs each byte through a different S-box to get four 32-bit results. Those are combined nonlinearly, using different combining functions in different rounds. Finally, the output is given a rotation controlled by the other 5 round key bits.

The cipher is freely available for any use. There is an RFC describing it; see external links. A descendant named CAST-256 was an AES candidate; there is also an RFC for that.

The RFCs provide a set of standard S-boxes that are normally used in any implementation of either CAST-128 or CAST-256. However, it would be possible for a large organisation to have its own version of either cipher, by generating its own S-boxes using the Mister & Adams paper as a guide.