NewDES

In cryptography, NewDES is a symmetric key block cipher. It was created in 1984–1985 by Robert Scott as a potential DES replacement.

NewDES

General
Designers	Robert Scott
First published	1985
Cipher detail
Key sizes	120 bits
Block sizes	64 bits
Rounds	17
Best public cryptanalysis
A related-key attack succeeds with 2^32 known plaintexts

Despite its name, it is not derived from DES and has quite a 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 so as to make the cipher more secure.[1]

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 cipher, 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.

Cryptanalysis

Only a small amount of cryptanalysis 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

${\displaystyle E_{K}(P)=C,}$

then

${\displaystyle E_{\overline {K}}({\overline {P}})={\overline {C}},}$

where

${\displaystyle {\overline {x}}}$

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 2⁸.

Biham's related-key attack can break NewDES with 2³³ 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 2³² known plaintexts and one related key.[2]

References

1. Robert Scott (2004-10-28). "newdes". Newsgroup: sci.crypt. Usenet: [email protected]. Retrieved 2018-10-10.
2. Kelsey, John; Schneier, Bruce; Wagner, David (1997). Han, Y.; Okamoto, T.; Qing, S. (eds.). Related-key cryptanalysis of 3-WAY, Biham-DES,CAST, DES-X, NewDES, RC2, and TEA. Lecture Notes in Computer Science. 1334. pp. 233–246. CiteSeerX 10.1.1.35.8112. doi:10.1007/BFb0028479. ISBN 978-3-540-63696-0. Retrieved 2018-10-10.

• Scott, Robert (January 1985). "Wide Open Encryption Design Offers Flexible Implementations". Cryptologia. 9 (1): 75–91. doi:10.1080/0161-118591859799.
• Schneier, Bruce (1996). Applied Cryptography, Second Edition. John Wiley & Sons. pp. 306–308. ISBN 978-0-471-11709-4.

External links

• Scott, Robert (1996-03-02). "Revision of NEWDES". Newsgroup: sci.crypt. Usenet: [email protected]. Retrieved 2018-10-10.
• NewDES source code implementations