NewDES
Encyclopedia
In cryptography
, NewDES is a symmetric key block cipher
. It was created in 1984–1985 by Robert Scott as a potential DES
replacement. Despite its name, it is not derived from DES and has a quite different structure. Its intended niche as a DES replacement has now mostly been filled by AES
. The algorithm was revised with a modified key schedule
in 1996 to counter a related-key attack
; this version is sometimes referred to as NewDES-96.
In 2004, Scott posted some comments on sci.crypt reflecting on the motivation behind NewDES's design and what he might have done differently to make the cipher more secure http://groups.google.com/groups?selm=418062d6.30341101%40news.provide.net.
, consisting of 17 rounds performed on a 64-bit data block and makes use of a 120-bit key
. In each round, subkey material is XORed with the 1-byte sub-blocks of data, then fed through an S-box
, the output of which is then XORed with another sub-block of data. In total, 8 XORs are performed in each round. The S-box is derived from the United States Declaration of Independence (to show that Scott had nothing up his sleeve
).
Each set of two rounds uses seven 1-byte subkeys, which are derived by splitting 56 bits of the key into bytes. The key is then rotated 56 bits for use in the next two rounds.
has been published on NewDES. The designer showed that NewDES exhibits the full avalanche effect
after seven rounds: every ciphertext
bit depends on every plaintext
bit and key bit.
NewDES has the same complementation property that DES has: namely, that if
then
where
is the bitwise complement of x. This means that the work factor for a brute force attack
is reduced by a factor of 2. Eli Biham
also noticed that changing a full byte in all the key and data bytes leads to another complementation property. This reduces the work factor by 28.
Biham's related-key attack can break NewDES with 233 chosen-key chosen plaintexts, meaning that NewDES is not as secure as DES.
John Kelsey
, Bruce Schneier
, and David Wagner used related-key cryptanalysis to develop another attack on NewDES; it requires 232 known plaintexts and one related key.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, NewDES is a symmetric key 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...
. It was created in 1984–1985 by Robert Scott as a potential DES
Data Encryption Standard
The Data Encryption Standard is a block cipher that uses shared secret encryption. It was selected by the 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. It is...
replacement. Despite its name, it is not derived from DES and has a quite different structure. Its intended niche as a DES replacement has now mostly been filled by AES
Advanced Encryption Standard
Advanced Encryption Standard is a specification for the encryption of electronic data. It has been adopted by the U.S. government and is now used worldwide. It supersedes DES...
. The algorithm was revised with a modified 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 ("...
in 1996 to counter a related-key attack
Related-key attack
In cryptography, a related-key attack is any form of cryptanalysis where the attacker can observe the operation of a cipher under several different keys whose values are initially unknown, but where some mathematical relationship connecting the keys is known to the attacker...
; this version is sometimes referred to as NewDES-96.
In 2004, Scott posted some comments on sci.crypt reflecting on the motivation behind NewDES's design and what he might have done differently to make the cipher more secure http://groups.google.com/groups?selm=418062d6.30341101%40news.provide.net.
The algorithm
NewDES, unlike DES, has no bit-level permutations, making it easy to implement in software. All operations are performed on whole bytes. It is a product cipherProduct cipher
In cryptography, a product cipher combines two or more transformations in a manner intending that the resulting cipher is more secure than the individual components to make it resistant to cryptanalysis. The product cipher combines a sequence of simple transformations such as substitution,...
, consisting of 17 rounds performed on a 64-bit data block and makes use of a 120-bit 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 produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...
. In each round, subkey material is XORed with the 1-byte sub-blocks of data, then fed through an S-box
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 — Shannon's property of confusion...
, the output of which is then XORed with another sub-block of data. In total, 8 XORs are performed in each round. The S-box is derived from the United States Declaration of Independence (to show that Scott had nothing up his sleeve
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 hashes and ciphers. These algorithms often need randomized constants for mixing or initialization purposes...
).
Each set of two rounds uses seven 1-byte subkeys, which are derived by splitting 56 bits of the key into bytes. The key is then rotated 56 bits for use in the next two rounds.
Cryptanalysis of NewDES
Only a small amount of cryptanalysisCryptanalysis
Cryptanalysis is the study of methods for obtaining the meaning of encrypted information, without access to the secret information that is normally required to do so. Typically, this involves knowing how the system works and finding a secret key...
has been published on NewDES. The designer showed that NewDES exhibits the full avalanche effect
Avalanche effect
In cryptography, the avalanche effect refers to a desirable property of cryptographic algorithms, typically block ciphers and cryptographic hash functions. The avalanche effect is evident if, when an input is changed slightly the output changes significantly...
after seven rounds: every ciphertext
Ciphertext
In cryptography, ciphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext that is unreadable by a human or computer without the proper cipher...
bit depends on every plaintext
Plaintext
In cryptography, plaintext is information a sender wishes to transmit to a receiver. Cleartext is often used as a synonym. Before the computer era, plaintext most commonly meant message text in the language of the communicating parties....
bit and key bit.
NewDES has the same complementation property that DES has: namely, that if
then
where
is the bitwise complement of x. This means that the work factor for a brute force attack
Brute force attack
In cryptography, a brute-force attack, or exhaustive key search, is a strategy that can, in theory, be used against any encrypted data. Such an attack might be utilized when it is not possible to take advantage of other weaknesses in an encryption system that would make the task easier...
is reduced by a factor of 2. Eli Biham
Eli Biham
Eli Biham is an Israeli cryptographer and cryptanalyst, currently a professor at the Technion Israeli Institute of Technology Computer Science department. Starting from October 2008, Biham is the dean of the Technion Computer Science department, after serving for two years as chief of CS graduate...
also noticed that changing a full byte in all the key and data bytes leads to another complementation property. This reduces the work factor by 28.
Biham's related-key attack can break NewDES with 233 chosen-key chosen plaintexts, meaning that NewDES is not as secure as DES.
John Kelsey
John Kelsey (cryptanalyst)
John Kelsey is a cryptographer currently working at NIST. His research interests include cryptanalysis and design of symmetric cryptography primitives , analysis and design of cryptographic protocols, cryptographic random number generation, electronic voting, side-channel attacks on cryptography...
, Bruce Schneier
Bruce Schneier
Bruce Schneier is an American cryptographer, computer security specialist, and writer. He is the author of several books on general security topics, computer security and cryptography, and is the founder and chief technology officer of BT Managed Security Solutions, formerly Counterpane Internet...
, and David Wagner used related-key cryptanalysis to develop another attack on NewDES; it requires 232 known plaintexts and one related key.