HOME

TheInfoList



OR:

Serpent is a symmetric key
block cipher In cryptography, a block cipher is a deterministic algorithm operating on fixed-length groups of bits, called ''blocks''. Block ciphers are specified elementary components in the design of many cryptographic protocols and are widely used to en ...
that was a finalist in the Advanced Encryption Standard (AES) contest, where it was ranked second to Rijndael. Serpent was designed by Ross Anderson, Eli Biham, and
Lars Knudsen Lars Ramkilde Knudsen (born 21 February 1962) is a Danish researcher in cryptography, particularly interested in the design and analysis of block ciphers, hash functions and message authentication codes (MACs). Academic After some early work in ...
. Like other AES submissions, Serpent has a block size of 128 bits and supports a
key size In cryptography, key size, key length, or key space refer to the number of bits in a key used by a cryptographic algorithm (such as a cipher). Key length defines the upper-bound on an algorithm's security (i.e. a logarithmic measure of the faste ...
of 128, 192 or 256 bits. The
cipher In cryptography, a cipher (or cypher) is an algorithm for performing encryption or decryption—a series of well-defined steps that can be followed as a procedure. An alternative, less common term is ''encipherment''. To encipher or encode ...
is a 32-round
substitution–permutation network In cryptography, an SP-network, or substitution–permutation network (SPN), is a series of linked mathematical operations used in block cipher algorithms such as AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK, and Squar ...
operating on a block of four 32-bit
words A word is a basic element of language that carries an objective or practical meaning, can be used on its own, and is uninterruptible. Despite the fact that language speakers often have an intuitive grasp of what a word is, there is no conse ...
. Each round applies one of eight 4-bit to 4-bit S-boxes 32 times in parallel. Serpent was designed so that all operations can be executed in
parallel Parallel is a geometric term of location which may refer to: Computing * Parallel algorithm * Parallel computing * Parallel metaheuristic * Parallel (software), a UNIX utility for running programs in parallel * Parallel Sysplex, a cluster o ...
, using 32
bit slice Bit slicing is a technique for constructing a processor from modules of processors of smaller bit width, for the purpose of increasing the word length; in theory to make an arbitrary ''n''-bit central processing unit (CPU). Each of these com ...
s. This maximizes parallelism, but also allows use of the extensive
cryptanalysis Cryptanalysis (from the Greek ''kryptós'', "hidden", and ''analýein'', "to analyze") refers to the process of analyzing information systems in order to understand hidden aspects of the systems. Cryptanalysis is used to breach cryptographic s ...
work performed on
DES Des is a masculine given name, mostly a short form (hypocorism) of Desmond. People named Des include: People * Des Buckingham, English football manager * Des Corcoran, (1928–2004), Australian politician * Des Dillon (disambiguation), sever ...
. Serpent took a conservative approach to security, opting for a large security margin: the designers deemed 16 rounds to be sufficient against known types of attack, but specified 32 rounds as insurance against future discoveries in cryptanalysis. The official NIST report on AES competition classified Serpent as having a high security margin along with
MARS Mars is the fourth planet from the Sun and the second-smallest planet in the Solar System, only being larger than Mercury. In the English language, Mars is named for the Roman god of war. Mars is a terrestrial planet with a thin at ...
and
Twofish 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. T ...
, in contrast to the adequate security margin of RC6 and Rijndael (currently AES). In final voting, Serpent had the fewest negative votes among the finalists, but scored second place overall because Rijndael had substantially more positive votes, the deciding factor being that Rijndael allowed for a far more efficient software implementation. The Serpent cipher algorithm is in the
public domain The public domain (PD) consists of all the creative work to which no exclusive intellectual property rights apply. Those rights may have expired, been forfeited, expressly waived, or may be inapplicable. Because those rights have expired ...
and has not been
patented A patent is a type of intellectual property that gives its owner the legal right to exclude others from making, using, or selling an invention for a limited period of time in exchange for publishing an enabling disclosure of the invention."A p ...
. The reference code is
public domain software Public-domain software is software that has been placed in the public domain, in other words, software for which there is absolutely no ownership such as copyright, trademark, or patent. Software in the public domain can be modified, distribute ...
and the optimized code is under GPL. There are no restrictions or encumbrances whatsoever regarding its use. As a result, anyone is free to incorporate Serpent in their software (or hardware implementations) without paying license fees.


Key Schedule

The Serpent key schedule consists of 3 main stages. In the first stage the key is initialized by adding padding if necessary. This is done in order to make short keys map to long keys of 256-bits, one "1" bit is appended to the end of the short key followed by "0" bits until the short key is mapped to a long key length. In the next phase, the "prekeys" are derived using the previously initialized key. 32-bit key parts XORed, the ''FRAC'' which is the fraction of the
Golden ratio In mathematics, two quantities are in the golden ratio if their ratio is the same as the ratio of their sum to the larger of the two quantities. Expressed algebraically, for quantities a and b with a > b > 0, where the Greek letter phi ( ...
and the round index is XORed with the key parts, the result of the
XOR Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false). It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
operation is rotated to left by 11. The ''FRAC'' and round index were added to achieve an even distribution of the keys bits during the rounds. Finally the "subkeys" are derived from the previously generated "prekeys". This results in a total of 33 128-bit "subkeys". At the end the round key or "subkey" are placed in the "initial permutation IP" to place the key bits in the correct column.


Key Schedule pseudo code

#define FRAC 0x9e3779b9 // fractional part of the golden ratio #define ROTL(A, n) (A << n) , (A >> (32 - n)) uint32_t key // k uint32_t words 32 // w uint32_t subkey 34] // sk /* key schedule: get prekeys */ void w(uint32_t *w, uint32_t *k) /* key schedule: get subkeys */ void k(uint32_t *w, uint32_t (*sk)


S-Boxes

The Serpent s-boxes are 4-bit
permutations In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or p ...
, and subject to the following properties: * a 1-bit input difference will never lead to a 1-bit output difference, a differential characteristic has a probability of 1:4 or less. * linear characteristics have a probability between 1:2 and 1:4, linear relationship between input and output bits has a probability between 1:2 and 1:8. * the nonlinear order of the output bits as function of the input bits is 3. However there have been output bits found which in function of the input bits have an order of only 2. The Serpent s-boxes have been constructed based on the 32 rows of the
DES Des is a masculine given name, mostly a short form (hypocorism) of Desmond. People named Des include: People * Des Buckingham, English football manager * Des Corcoran, (1928–2004), Australian politician * Des Dillon (disambiguation), sever ...
s-boxes. These were transformed by swapping entries, resulting arrays with desired properties were stored as the Serpent s-boxes. This process was repeated until a total of 8 s-boxes were found. The following key was used in this process: "sboxesforserpent".


Permutations and Transformations


Initial permutation (IP)

The initial permutation works on 128 bits at a time moving bits around. for i in 0 .. 127 swap( bit(i), bit((32 * i) % 127) )


Final permutation (FP)

The final permutation works on 128 bits at a time moving bits around. for i in 0 .. 127 swap( bit(i), bit((2 * i) % 127) )


Linear transformation (LT)

Consists of XOR, S-Box, bit shift left and bit rotate left operations. These operations are performed on 4 32-bit words. for (short i = 0; i < 4; i++) X = ROTL(X 13); X = ROTL(X 3 ); X = X ^ X ^ X X = X ^ X ^ (X << 3); X = ROTL(X 1 ); X = ROTL(X 7 ); X = X ^ X ^ X X = X ^ X ^ (X << 7); X = ROTL(X 5 ); X = ROTL(X 22); for (short i = 0; i < 4; i++)


Rijndael vs. Serpent

Rijndael is a substitution-linear transformation network with ten, twelve, or fourteen rounds, depending on the key size, and with key sizes of 128 bits, 192 bits, or 256 bits, independently specified. Serpent is a substitution–permutation network which has thirty-two rounds, plus an initial and a final permutation to simplify an optimized implementation. The round function in Rijndael consists of three parts: a nonlinear layer, a linear mixing layer, and a key-mixing XOR layer. The round function in Serpent consists of key-mixing XOR, thirty-two parallel applications of the same 4×4 S-box, and a linear transformation, except in the last round, wherein another key-mixing XOR replaces the linear transformation. The nonlinear layer in Rijndael uses an 8×8 S-box whereas Serpent uses eight different 4×4 S-boxes. The 32 rounds mean that Serpent has a higher security margin than Rijndael; however, Rijndael with 10 rounds is faster and easier to implement for small blocks. Hence, Rijndael was selected as the winner in the AES competition.


Serpent-0 vs. Serpent-1

The original Serpent, Serpent-0, was presented at the 5th workshop on
Fast Software Encryption Fast or FAST may refer to: * Fast (noun), high speed or velocity * Fast (noun, verb), to practice fasting, abstaining from food and/or water for a certain period of time Acronyms and coded Computing and software * '' Faceted Application of Su ...
, but a somewhat tweaked version, Serpent-1, was submitted to the AES competition. The AES submission paper discusses the changes, which include key-scheduling differences.


Security

The XSL attack, if effective, would weaken Serpent (though not as much as it would weaken Rijndael, which became AES). However, many
cryptanalysts Cryptanalysis (from the Greek ''kryptós'', "hidden", and ''analýein'', "to analyze") refers to the process of analyzing information systems in order to understand hidden aspects of the systems. Cryptanalysis is used to breach cryptographic sec ...
believe that once implementation considerations are taken into account the XSL attack would be more expensive than a brute force attack. In 2000, a paper by Kohno et al. presents a meet-in-the-middle attack against 6 of 32 rounds of Serpent and an amplified boomerang attack against 9 of 32 rounds in Serpent. A 2001 attack by Eli Biham, Orr Dunkelman and Nathan Keller presents a linear cryptanalysis attack that breaks 10 of 32 rounds of Serpent-128 with 2118 known plaintexts and 289 time, and 11 rounds of Serpent-192/256 with 2118 known plaintexts and 2187 time. A 2009 paper has noticed that the nonlinear order of Serpent S-boxes were not 3 as was claimed by the designers. A 2011 attack by Hongjun Wu, Huaxiong Wang and Phuong Ha Nguyen, also using linear cryptanalysis, breaks 11 rounds of Serpent-128 with 2116 known plaintexts, 2107.5 time and 2104 memory. The same paper also describes two attacks which break 12 rounds of Serpent-256. The first requires 2118 known plaintexts, 2228.8 time and 2228 memory. The other attack requires 2116 known plaintexts and 2121 memory but also requires 2237.5 time.


See also

*
Tiger The tiger (''Panthera tigris'') is the largest living Felidae, cat species and a member of the genus ''Panthera''. It is most recognisable for its dark vertical stripes on orange fur with a white underside. An apex predator, it primarily pr ...
– hash function by the same authors


Footnotes


Further reading

* * * *


External links

*
256 bit ciphers
– SERPENT Reference implementation and derived code {{Cryptography navbox, block Block ciphers Free ciphers Public-domain software with source code Free software