Twofish

Last updated
Twofish
Twofishalgo.svg
The Twofish algorithm
General
Designers Bruce Schneier
First published1998
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 public cryptanalysis
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]

In cryptography, Twofish is a symmetric key block cipher with a block size of 128 bits and key sizes up to 256 bits. It was one of the five finalists of the Advanced Encryption Standard contest, but it was not selected for standardization. Twofish is related to the earlier block cipher Blowfish.

Contents

Twofish's distinctive features are the use of pre-computed key-dependent S-boxes, and a relatively complex key 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, the pseudo-Hadamard transform [3] (PHT) from the SAFER family of ciphers. Twofish has a Feistel structure like DES. Twofish also employs a Maximum Distance Separable matrix.

When it was introduced in 1998, Twofish was slightly slower than Rijndael (the chosen algorithm for Advanced Encryption Standard) for 128-bit keys, but somewhat faster for 256-bit keys. Since 2008, virtually all AMD and Intel processors have included hardware acceleration of the Rijndael algorithm via the AES instruction set; Rijndael implementations that use the instruction set are now orders of magnitude faster than (software) Twofish implementations. [4]

Twofish was designed by Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, and Niels Ferguson: the "extended Twofish team" met to perform further cryptanalysis of Twofish. Other AES contest entrants included Stefan Lucks, Tadayoshi Kohno, and Mike Stay.

The Twofish cipher has not been patented, and the reference implementation has been placed in the public 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 the OpenPGP standard (RFC 4880). However, Twofish has seen less widespread usage than Blowfish [ dubious ], which has been available longer.

Performance

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 more RAM needed to store them.

The estimates in the table below are all based on existing 0.35 μm CMOS technology.

Hardware trade offs (128-bit key) [5]
Gate countsh blocksClocks
per block
Pipeline
levels
Clock speedThroughput
(Mbit/s)
Startup
clocks
Comments
14000164140 MHz804subkeys on the fly
19000132140 MHz16040
23000216140 Mhz32020
26000232280 MHz64020
280002483120 MHz96020
300002644150 MHz120020
80000216180 MHz640300S-box RAMs

Cryptanalysis

In 1999, Niels Ferguson published an impossible differential attack that breaks 6 rounds out of 16 of the 256-bit key version using 2256 steps. [2]

As of 2000, the best published cryptanalysis of the Twofish block cipher is a truncated 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]

See also

Related Research Articles

<span class="mw-page-title-main">Advanced Encryption Standard</span> Standard for the encryption of electronic data

The Advanced Encryption Standard (AES), also known by its original name Rijndael, is a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001.

Blowfish is a symmetric-key block cipher, designed in 1993 by Bruce Schneier and included in many cipher suites and encryption products. Blowfish provides a good encryption rate in software, and no effective cryptanalysis of it has been found to date. However, the Advanced Encryption Standard (AES) now receives more attention, and Schneier recommends Twofish for modern applications.

In cryptography, a block cipher is a deterministic algorithm that operates on fixed-length groups of bits, called blocks. Block ciphers are the elementary building blocks of many cryptographic protocols. They are ubiquitous in the storage and exchange of data, where such data is secured and authenticated via encryption.

<span class="mw-page-title-main">Data Encryption Standard</span> Early unclassified symmetric-key block cipher

The Data Encryption Standard is a symmetric-key algorithm for the encryption of digital data. Although its short key length of 56 bits makes it too insecure for modern applications, it has been highly influential in the advancement of cryptography.

The Advanced Encryption Standard (AES), the symmetric block cipher ratified as a standard by National Institute of Standards and Technology of the United States (NIST), was chosen using a process lasting from 1997 to 2000 that was markedly more open and transparent than its predecessor, the Data Encryption Standard (DES). This process won praise from the open cryptographic community, and helped to increase confidence in the security of the winning algorithm from those who were suspicious of backdoors in the predecessor, DES.

In cryptography, an S-box (substitution-box) is a basic component of symmetric key algorithms which performs substitution. In block ciphers, they are typically used to obscure the relationship between the key and the ciphertext, thus ensuring Shannon's property of confusion. Mathematically, an S-box is a nonlinear vectorial Boolean function.

<span class="mw-page-title-main">David A. Wagner</span> American computer scientist

David A. Wagner is a professor of computer science at the University of California, Berkeley and a well-known researcher in cryptography and computer security. He is a member of the Election Assistance Commission's Technical Guidelines Development Committee, tasked with assisting the EAC in drafting the Voluntary Voting System Guidelines. He is also a member of the ACCURATE project.

<span class="mw-page-title-main">Serpent (cipher)</span>

Serpent is a symmetric key block cipher that was a finalist in the Advanced Encryption Standard (AES) contest, in which it ranked second to Rijndael. Serpent was designed by Ross Anderson, Eli Biham, and Lars Knudsen.

In cryptography, Skipjack is a block cipher—an algorithm for encryption—developed by the U.S. National Security Agency (NSA). Initially classified, it was originally intended for use in the controversial Clipper chip. Subsequently, the algorithm was declassified.

MARS is a block cipher that was IBM's submission to the Advanced Encryption Standard process. MARS was selected as an AES finalist in August 1999, after the AES2 conference in March 1999, where it was voted as the fifth and last finalist algorithm.

<span class="mw-page-title-main">DEAL</span> Block cipher

In cryptography, DEAL is a symmetric block cipher derived from the Data Encryption Standard (DES). Its design was presented Lars Knudsen at the SAC conference in 1997, and submitted as a proposal to the AES contest in 1998 by Richard Outerbridge.

Phelix is a high-speed stream cipher with a built-in single-pass message authentication code (MAC) functionality, submitted in 2004 to the eSTREAM contest by Doug Whiting, Bruce Schneier, Stefan Lucks, and Frédéric Muller. The cipher uses only the operations of addition modulo 232, exclusive or, and rotation by a fixed number of bits. Phelix uses a 256-bit key and a 128-bit nonce, claiming a design strength of 128 bits. Concerns have been raised over the ability to recover the secret key if the cipher is used incorrectly.

In cryptography, impossible differential cryptanalysis is a form of differential cryptanalysis for block ciphers. While ordinary differential cryptanalysis tracks differences that propagate through the cipher with greater than expected probability, impossible differential cryptanalysis exploits differences that are impossible at some intermediate state of the cipher algorithm.

The Hasty Pudding cipher (HPC) is a variable-block-size block cipher designed by Richard Schroeppel, which was an unsuccessful candidate in the competition for selecting the U.S. Advanced Encryption Standard (AES). It has a number of unusual properties for a block cipher: its input block size and key length are variable, and it includes an additional input parameter called the "spice" for use as a secondary, non-secret key. The Hasty Pudding cipher was the only AES candidate designed exclusively by U.S. cryptographers.

In cryptography, integral cryptanalysis is a cryptanalytic attack that is particularly applicable to block ciphers based on substitution–permutation networks. It was originally designed by Lars Knudsen as a dedicated attack against Square, so it is commonly known as the Square attack. It was also extended to a few other ciphers related to Square: CRYPTON, Rijndael, and SHARK. Stefan Lucks generalized the attack to what he called a saturation attack and used it to attack Twofish, which is not at all similar to Square, having a radically different Feistel network structure. Forms of integral cryptanalysis have since been applied to a variety of ciphers, including Hierocrypt, IDEA, Camellia, Skipjack, MISTY1, MISTY2, SAFER++, KHAZAD, and FOX.

In cryptography, truncated differential cryptanalysis is a generalization of differential cryptanalysis, an attack against block ciphers. Lars Knudsen developed the technique in 1994. Whereas ordinary differential cryptanalysis analyzes the full difference between two texts, the truncated variant considers differences that are only partially determined. That is, the attack makes predictions of only some of the bits instead of the full block. This technique has been applied to SAFER, IDEA, Skipjack, E2, Twofish, Camellia, CRYPTON, and even the stream cipher Salsa20.

<span class="mw-page-title-main">Skein (hash function)</span> Cryptographic hash function

Skein is a cryptographic hash function and one of five finalists in the NIST hash function competition. Entered as a candidate to become the SHA-3 standard, the successor of SHA-1 and SHA-2, it ultimately lost to NIST hash candidate Keccak.

The following outline is provided as an overview of and topical guide to cryptography:

This article summarizes publicly known attacks against block ciphers and stream ciphers. Note that there are perhaps attacks that are not publicly known, and not all entries may be up to date.

In cryptography, security level is a measure of the strength that a cryptographic primitive — such as a cipher or hash function — achieves. Security level is usually expressed as a number of "bits of security", where n-bit security means that the attacker would have to perform 2n operations to break it, but other methods have been proposed that more closely model the costs for an attacker. This allows for convenient comparison between algorithms and is useful when combining multiple primitives in a hybrid cryptosystem, so there is no clear weakest link. For example, AES-128 is designed to offer a 128-bit security level, which is considered roughly equivalent to a RSA using 3072-bit key.

References

  1. Ship Moriai; Yiqun Lisa Yin (2000). "Cryptanalysis of Twofish (II)" (PDF). Retrieved 2013-01-14.{{cite journal}}: Cite journal requires |journal= (help)
  2. 1 2 Niels Ferguson (1999-10-05). "Impossible differentials in Twofish" (PDF). Retrieved 2013-01-14.{{cite journal}}: Cite journal requires |journal= (help)
  3. "Team Men In Black Presents: TwoFish" (PDF). Archived from the original (PDF) on 26 September 2017. Retrieved 26 September 2017.
  4. Bruce Schneier; Doug Whiting (2000-04-07). "A Performance Comparison of the Five AES Finalists" (PDF/PostScript). Retrieved 2013-01-14.{{cite journal}}: Cite journal requires |journal= (help)
  5. Schneier, Bruce (15 June 1998). "Twofish: A 128-Bit Block Cipher" (PDF). Counterpane: 68.
  6. Shiho Moriai; Yiqun Lisa Yin (2000). "Cryptanalysis of Twofish (II)" (PDF). Retrieved 2013-01-14.{{cite journal}}: Cite journal requires |journal= (help)
  7. Schneier, Bruce (2005-11-23). "Twofish Cryptanalysis Rumors". Schneier on Security blog. Retrieved 2013-01-14.

Articles