Cellular Message Encryption Algorithm

The Cellular Message Encryption Algorithm, usually shortened to CMEA, is a block cipher that was used to protect the control channel of digital cellular telephones in the United States. It is one of four cryptographic primitives named in a Telecommunications Industry Association standard, and it was meant to hide signalling data such as dialled digits rather than the voice itself. CMEA works on bytes and on blocks of variable size, typically two to six bytes, under a key of only 64 bits. Its three passes over the data are a keyed non-linear diffusion step, an unkeyed linear mixing step and a second non-linear step that is the inverse of the first. The non-linear steps use a keyed lookup table called the T-box, which in turn uses an unkeyed table called the CaveTable. Because the structure undoes itself, encrypting the ciphertext again with the same key recovers the plaintext. In 1997 a group of cryptographers published attacks showing the cipher to be severely weak, with an effective strength of roughly 24 to 32 bits, including a chosen-plaintext attack using 338 chosen plaintexts. The improved CMEA-I was not much better. The NSA denied accusations that it had pressured the designers to weaken the cipher, and the ECMEA and SCEMA ciphers are derived from CMEA. The design is described in US patent 5,159,634.