Crab (cipher)

# Crab (cipher)

Discussion

Encyclopedia
In cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

, Crab is a block cipher
Block cipher
In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...

proposed by Burt Kaliski
Burt Kaliski
Burton S. "Burt" Kaliski, Jr. is a cryptographer, director of the EMC Innovation Network at EMC Corporation since its 2006 acquisition of RSA Security...

and Matt Robshaw
Matt Robshaw
Matthew John Barton "Matt" Robshaw is a cryptographer. Formerly a lecturer at Royal Holloway, University of London, Robshaw currently belongs to the cryptography research group at France Telecom's Orange Labs. He also coordinates the Symmetric Techniques Virtual Lab for ECRYPT...

at the first Fast Software Encryption
Fast Software Encryption
Fast Software Encryption, often abbreviated FSE, is a workshop for cryptography research, focused on symmetric-key cryptography with an emphasis on fast, practical techniques, as opposed to theory...

workshop in 1993. Not really intended for use, Crab was developed to demonstrate how ideas from hash functions
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...

could be used to create a fast cipher.

Crab has an unusually large block size
Block size (cryptography)
In modern cryptography, symmetric key ciphers are generally divided into stream ciphers and block ciphers. Block ciphers operate on a fixed length string of bits. The length of this bit string is the block size...

of 8192 bits. Its creators suggested using an 80-bit key, but the cipher could use any key size
Key size
In cryptography, key size or key length is the size measured in bits of the key used in a cryptographic algorithm . An algorithm's key length is distinct from its cryptographic security, which is a logarithmic measure of the fastest known computational attack on the algorithm, also measured in bits...

. The authors didn't specify an actual key schedule
Key schedule
[[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES [[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES [[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES ("[[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES ("...

, only that the key is used to generate two large sets of subkey
Subkey
Subkey can refer to:* A hard-coded parameter in a key schedule* A key in OpenPGP that is bound by a master key...

s: a permutation of the numbers 0 through 255, and an array of 2048 32-bit numbers. The block is divided into 256 32-bit subblocks, which are permuted at the beginning. Then the algorithm makes four passes over the data, each time applying one of four transformations adapted from MD5
MD5
The MD5 Message-Digest Algorithm is a widely used cryptographic hash function that produces a 128-bit hash value. Specified in RFC 1321, MD5 has been employed in a wide variety of security applications, and is also commonly used to check data integrity...

.

A brief note on the cryptanalysis of Crab is included in Markku-Juhani Saarinen's paper on block ciphers based on SHA-1 and MD5, published at FSE 2003. The author demonstrates a weakness in Crab that permits a distinguisher using no more than a dozen chosen plaintexts, and speculates that this can be converted into a full key-recovery attack using no more than 216 chosen plaintexts. Such an attack would depend on the key schedule used.