Blowfish (cipher)

	Email		Print
	Bookmark		Link

Blowfish (cipher)

In cryptography

Cryptography

Cryptography is the practice and study of hiding information. In modern times cryptography is considered a branch of both mathematics and computer science and is affiliated closely with information theory, computer security and engineering....
, Blowfish is a key

Key (cryptography)

Block cipher

In cryptography, a block cipher is a symmetric key algorithm cipher which operates on fixed-length groups of bits, termed blocks, with an unvarying transformation....
, designed in 1993 by Bruce Schneier

Bruce Schneier

Bruce Schneier is an American cryptographer, computer security specialist, and writer. He is the author of several books on computer security and cryptography, and is the founder and chief technology officer of BT Counterpane, formerly Counterpane Internet Security, Inc....
and included in a large number of cipher suites and encryption products. Blowfish provides a good encryption rate in software and no effective cryptanalysis

Cryptanalysis

Cryptanalysis is the study of methods for obtaining the meaning of encrypted information, without access to the secret information which is normally required to do so....
of it has been found to date. However, the Advanced Encryption Standard

Advanced Encryption Standard

In cryptography, the Advanced Encryption Standard is an encryption standard adopted by the Federal government of the United States. The standard comprises three block ciphers, AES-128, AES-192 and AES-256, adopted from a larger collection originally published as Rijndael. Each AES cipher has a 128 bit block size, with key sizes of 128...
now receives more attention.

Schneier designed Blowfish as a general-purpose algorithm, intended as a replacement for the aging DES

Data Encryption Standard

The Data Encryption Standard is a block cipher that was selected by National Bureau of Standards as an official Federal Information Processing Standard for the United States in 1976 and which has subsequently enjoyed widespread use internationally....
and free of the problems and constraints associated with other algorithms. At the time Blowfish was released, many other designs were proprietary, encumbered by patent

Patent

Discussion

Ask a question about 'Blowfish (cipher)'

Start a new discussion about 'Blowfish (cipher)'

Answer questions from other users

Full Discussion Forum

Encyclopedia

In cryptography

Cryptography

Key (cryptography)

Block cipher

Bruce Schneier

Cryptanalysis

Advanced Encryption Standard

Data Encryption Standard

Patent

A patent is a set of exclusive rights granted by a state to an inventor or his assignee for a term of patent in exchange for a disclosure of an invention....
s or were commercial/government secrets. Schneier has stated that, "Blowfish is unpatented, and will remain so in all countries. The algorithm is hereby placed in the public domain

Public domain

File:PD-icon.svgThe public domain is a range of abstract materials?commonly referred to as intellectual property?which are not owned or controlled by anyone....
, and can be freely used by anyone."

Notable features of the design include key-dependent S-boxes and a highly complex key schedule

Key schedule

In cryptography, the so-called product ciphers are a certain kind of ciphers, where the ciphering of data is done in "rounds". The general setup of each round is the same, except for some hard-coded parameters and a part of the key , called a subkey....
.

The algorithm

Blowfish has a 64-bit block size

Block size (cryptography)

In modern cryptography, symmetric key algorithm ciphers are generally divided into stream ciphers and block ciphers. Block ciphers operate on a fixed length string of bits....
and a variable key length from 32 up to 448 bits . It is a 16-round Feistel cipher

Feistel cipher

In cryptography, a Feistel cipher is a symmetric structure used in the construction of block ciphers, named after the German IBM cryptographer Horst Feistel; it is also commonly known as a Feistel network....
and uses large key-dependent S-boxes

Substitution box

In cryptography, an S-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 — Claude Shannon property of confusion and diffusion....
. It is similar in structure to CAST-128

CAST-128

In cryptography, CAST-128 is a block cipher used in a number of products, notably as the default cipher in some versions of GNU Privacy Guard and Pretty Good Privacy....
, which uses fixed S-boxes.

The diagram to the left shows the action of Blowfish. Each line represents 32 bits. The algorithm keeps two subkey arrays: the 18-entry P-array and four 256-entry S-boxes. The S-boxes accept 8-bit input and produce 32-bit output. One entry of the P-array is used every round, and after the final round, each half of the data block is XORed with one of the two remaining unused P-entries.

The diagram to the right shows Blowfish's F-function. The function splits the 32-bit input into four eight-bit quarters, and uses the quarters as input to the S-boxes. The outputs are added modulo

Modular arithmetic

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value — the modulus....
2³² and XORed to produce the final 32-bit output.

Since Blowfish is a Feistel network, it can be inverted simply by XORing P₁₇ and P₁₈ to the ciphertext block, then using the P-entries in reverse order.

Blowfish's key schedule

Key schedule

Hexadecimal

In mathematics and computer science, hexadecimal is a numeral system with a radix, or base, of 16. It uses sixteen distinct symbols, most often the symbols 0–9 to represent values zero to nine, and A, B, C, D, E, F to represent values ten to fifteen....
digits of pi

Pi or p is a mathematical constant whose value is the ratio of any circle's circumference to its diameter in Euclidean geometry; this is the same value as the ratio of a circle's area to the square of its radius....
, which contain no obvious pattern (see nothing up my sleeve number

Nothing up my sleeve number

In cryptography, nothing up my sleeve numbers are any numbers which, by their construction, are above suspicion of hidden properties. They are used in creating cryptographic functions such as cryptographic hash and ciphers....
). The secret key is then XORed with the P-entries in order (cycling the key if necessary). A 64-bit all-zero block is then encrypted with the algorithm as it stands. The resultant ciphertext replaces P₁ and P₂. The ciphertext is then encrypted again with the new subkeys, and P₃ and P₄ are replaced by the new ciphertext. This continues, replacing the entire P-array and all the S-box entries. In all, the Blowfish encryption algorithm will run 521 times to generate all the subkeys - about 4KB of data is processed.

Cryptanalysis of Blowfish

There is no effective cryptanalysis

Cryptanalysis

Cryptanalysis is the study of methods for obtaining the meaning of encrypted information, without access to the secret information which is normally required to do so....
on the full-round version of Blowfish known publicly . A sign extension

Sign extension

Sign extension is the operation, in computer arithmetic, of increasing the number of bits of a binary number while preserving the number's negative and non-negative numbers....
bug in one publication of C code has been identified.

In 1996, Serge Vaudenay

Serge Vaudenay

Serge Vaudenay is a well-known French people cryptographer.Serge Vaudenay entered the ?cole Normale Sup?rieure in Paris as a normalien student in 1989....
found a known-plaintext attack requiring 2^{8r + 1} known plaintexts to break, where r is the number of rounds. Moreover, he also found a class of weak key

Weak key

In cryptography, a weak key is a key which when used with a specific cipher, makes the cipher behave in some undesirable way. Weak keys usually represent a very small fraction of the overall keyspace, which usually means that if one generates a random key to encrypt a message weak keys are very unlikely to give rise to a security problem....
s that can be detected and broken by the same attack with only 2^{4r + 1} known plaintexts. This attack cannot be used against the regular Blowfish; it assumes knowledge of the key-dependent S-boxes. Vincent Rijmen

Vincent Rijmen

Vincent Rijmen is a Belgian cryptographer and one of the designers of the Rijndael, the Advanced Encryption Standard. Rijmen is also the co-designer of the WHIRLPOOL cryptographic hash function, and the block ciphers Anubis , KHAZAD, Square , NOEKEON and SHARK....
, in his Ph.D.

Doctor of Philosophy

Doctor of Philosophy, abbreviated Ph.D. or PhD for the Latin , meaning "teacher of philosophy", is an postgraduate academic degree awarded by University....
thesis, introduced a second-order differential attack that can break four rounds and no more. There remains no known way to break the full 16 rounds, apart from a brute-force search

Brute-force search

In computer science, brute-force search or exhaustive search, also known as generate and test, is a trivial but very general problem-solving technique that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's statement....
.

Bruce Schneier notes that while Blowfish is still in use, he recommends using the more recent Twofish

Twofish

In cryptography, Twofish is a Symmetric-key algorithm 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 process, but was not selected for standardisation....
algorithm instead.

Blowfish in practice

Blowfish is one of the fastest block cipher

Block cipher

In cryptography, a block cipher is a symmetric key algorithm cipher which operates on fixed-length groups of bits, termed blocks, with an unvarying transformation....
s in widespread use, except when changing keys. Each new key

Key (cryptography)

In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would have no result....
requires pre-processing equivalent to encrypting about 4 kilobytes of text, which is very slow compared to other block ciphers. This prevents its use in certain applications, but is not a problem in others. In one application, it is actually a benefit: the password

Password

A password is a secret word or string of Character that is used for authentication, to prove identity or gain access to a resource . The password must be kept Secrecy from those not allowed access....
-hashing method used in OpenBSD

OpenBSD

OpenBSD is a Unix-like computer operating system descended from Berkeley Software Distribution , a Unix derivative developed at the University of California, Berkeley....
uses an algorithm derived from Blowfish that makes use of the slow key schedule; the idea is that the extra computational effort required gives protection against dictionary attack

Dictionary attack

In cryptanalysis and computer security, a dictionary attack is a technique for defeating a cipher or authentication mechanism by trying to determine its decryption key or passphrase by searching likely possibilities....
s. See key strengthening

Key strengthening

In cryptography, key strengthening or key stretching refer to techniques used to make a possibly-weak Key , typically a password or passphrase, more secure against a brute force attack by increasing the time it takes to test each possible key....
.

Blowfish has a memory footprint of just over 4 kilobytes of RAM. This constraint is not a problem even for older desktop and laptop computers, though it does prevent use in the smallest embedded systems such as early smartcards.

Blowfish was one of the first secure block ciphers not subject to any patents and is therefore freely available for anyone to use. This benefit has contributed to its popularity in cryptographic software.

Blowfish (cipher)

The algorithm

Cryptanalysis of Blowfish

Blowfish in practice

See also

External links