 The Twofish algorithm | |
| General | |
|---|---|
| Designers | Bruce Schneier |
| First published | 1998 |
| Derived from | Blowfish,SAFER,Square |
| Related to | Threefish |
| Certification | AES finalist |
| Cipher detail | |
| Key sizes | 128, 192 or 256 bits |
| Block sizes | 128 bits |
| Structure | Feistel network |
| Rounds | 16 |
| Best publiccryptanalysis | |
| Truncated differential cryptanalysis requiring roughly 251 chosen plaintexts.[1]Impossible differential attack that breaks 6 rounds out of 16 of the 256-bit key version using 2256 steps.[2] | |
Incryptography,Twofish is asymmetric keyblock cipher with ablock size of 128bits andkey sizes up to 256 bits. It was one of the five finalists of theAdvanced Encryption Standard contest, but it was not selected for standardization. Twofish is related to the earlier block cipherBlowfish.
Twofish's distinctive features are the use of pre-computed key-dependentS-boxes, and a relatively complexkey schedule. One half of an n-bit key is used as the actual encryption key and the other half of the n-bit key is used to modify the encryption algorithm (key-dependent S-boxes). Twofish borrows some elements from other designs; for example, thepseudo-Hadamard transform[3] (PHT) from theSAFER family of ciphers. Twofish has aFeistel structure likeDES. Twofish also employs aMaximum Distance Separable matrix.
When it was introduced in 1998, Twofish was slightly slower thanRijndael (the chosen algorithm forAdvanced Encryption Standard) for 128-bitkeys, but somewhat faster for 256-bit keys. Since 2008, virtually all AMD and Intel processors have included hardware acceleration of the Rijndael algorithm via theAES instruction set; Rijndael implementations that use the instruction set are now orders of magnitude faster than (software) Twofish implementations.[4]
Twofish was designed byBruce Schneier,John Kelsey,Doug Whiting,David Wagner,Chris Hall, andNiels Ferguson: the "extended Twofish team" met to perform furthercryptanalysis of Twofish. Other AES contest entrants includedStefan Lucks,Tadayoshi Kohno, andMike Stay.
The Twofish cipher has not beenpatented, and thereference implementation has been placed in thepublic domain. As a result, the Twofish algorithm is free for anyone to use without any restrictions whatsoever. It is one of a few ciphers included in theOpenPGP standard (RFC 9580). However, Twofish has seen less widespread usage thanBlowfish, which has been available longer.
During the design of Twofish, performance was always an important factor. It was designed to allow for several layers of performance trade offs, depending on the importance of encryption speed, memory usage, hardware gate count, key setup and other parameters. This allows a highly flexible algorithm, which can be implemented in a variety of applications.
There are multiple space–time tradeoffs that can be made, in software as well as in hardware for Twofish. An example of such a tradeoff would be the precomputation of round subkeys or s-boxes, which can lead to speed increases of a factor of two or more. These come, however, at the cost of moreRAM needed to store them.
The estimates in the table below are all based on existing 0.35 μmCMOS technology.
| Gate counts | h blocks | Clocks per block | Pipeline levels | Clock speed | Throughput (Mbit/s) | Startup clocks | Comments |
|---|---|---|---|---|---|---|---|
| 14000 | 1 | 64 | 1 | 40 MHz | 80 | 4 | subkeys on the fly |
| 19000 | 1 | 32 | 1 | 40 MHz | 160 | 40 | |
| 23000 | 2 | 16 | 1 | 40 MHz | 320 | 20 | |
| 26000 | 2 | 32 | 2 | 80 MHz | 640 | 20 | |
| 28000 | 2 | 48 | 3 | 120 MHz | 960 | 20 | |
| 30000 | 2 | 64 | 4 | 150 MHz | 1200 | 20 | |
| 80000 | 2 | 16 | 1 | 80 MHz | 640 | 300 | S-box RAMs |
In 1999,Niels Ferguson published animpossible differential attack that breaks 6 rounds out of 16 of the 256-bit key version using 2256 steps.[2]
As of 2000[update], the best published cryptanalysis of the Twofish block cipher is atruncated differential cryptanalysis of the full 16-round version. The paper claims that the probability of truncated differentials is 2−57.3 per block and that it will take roughly 251 chosen plaintexts (32 petabytes worth of data) to find a good pair of truncated differentials.[6]
Bruce Schneier responded in a 2005 blog entry that this paper did not present a full cryptanalytic attack, but only some hypothesized differential characteristics: "But even from a theoretical perspective, Twofish isn't even remotely broken. There have been no extensions to these results since they were published in 2000."[7]
{{cite journal}}:Cite journal requires|journal= (help){{cite journal}}:Cite journal requires|journal= (help){{cite journal}}:Cite journal requires|journal= (help){{cite journal}}:Cite journal requires|journal= (help){{cite journal}}:Cite journal requires|journal= (help)