In
cryptographyCryptography is the practice and study of hiding information. Modern cryptography intersects the disciplines of mathematics, computer science, and engineering...
,
NewDES is a symmetric key
block cipherIn cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, termed 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
DESThe Data Encryption Standard is a block cipher that 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 based on a symmetric-key algorithm...
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
AESIn cryptography, the Advanced Encryption Standard is an encryption standard adopted by the U.S. government. 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...
. The algorithm was revised with a modified
key scheduleIn 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 cipher key, called a subkey...
in 1996 to counter a
related-key attackIn 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.
NewDES, unlike DES, has no bit-level permutations, making it easy to implement in software.
In
cryptographyCryptography is the practice and study of hiding information. Modern cryptography intersects the disciplines of mathematics, computer science, and engineering...
,
NewDES is a symmetric key
block cipherIn cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, termed 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
DESThe Data Encryption Standard is a block cipher that 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 based on a symmetric-key algorithm...
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
AESIn cryptography, the Advanced Encryption Standard is an encryption standard adopted by the U.S. government. 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...
. The algorithm was revised with a modified
key scheduleIn 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 cipher key, called a subkey...
in 1996 to counter a
related-key attackIn 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 cipherIn 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
keyIn 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. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa during decryption...
. In each round, subkey material is XORed with the 1-byte sub-blocks of data, then fed through an
S-boxIn 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 sleeveIn 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 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. 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 effectIn 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
ciphertextIn cryptography, ciphertext is the result of the process of transforming information using an algorithm to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key. This result is also known as encrypted information...
bit depends on every
plaintextIn cryptography, plaintext is information a sender wishes to transmit to a receiver. Cleartext is, sometimes confusingly, 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 attackIn cryptography, a brute force attack is a strategy used to break the encryption of data. It involves traversing the search space of possible keys until the correct key is found....
is reduced by a factor of 2.
Eli BihamEli 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 2
8.
Biham's related-key attack can break NewDES with 2
33 chosen-key chosen plaintexts, meaning that NewDES is not as secure as DES.
John KelseyJohn 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 SchneierBruce 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
David WagnerDavid 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...
used related-key cryptanalysis to develop another attack on NewDES; it requires 2
32 known plaintexts and one related key.
External links