In cryptography

Cryptography

Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

, New Data Seal (NDS) is a 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...

 that was designed at IBM

IBM

International Business Machines Corporation or IBM is an American multinational technology and consulting corporation headquartered in Armonk, New York, United States. IBM manufactures and sells computer hardware and software, and it offers infrastructure, hosting and consulting services in areas...

 in 1975, based on the Lucifer

Lucifer (cipher)

In cryptography, Lucifer was the name given to several of the earliest civilian block ciphers, developed by Horst Feistel and his colleagues at IBM. Lucifer was a direct precursor to the Data Encryption Standard...

 algorithm that became 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...

.

The cipher uses a block size

Block size (cryptography)

In modern cryptography, symmetric key ciphers are generally divided into stream ciphers and block ciphers. Block ciphers operate on a fixed length string of bits. The length of this bit string is the block size...

 of 128 bits, and a very large key size

Key size

In cryptography, key size or key length is the size measured in bits of the key used in a cryptographic algorithm . An algorithm's key length is distinct from its cryptographic security, which is a logarithmic measure of the fastest known computational attack on the algorithm, also measured in bits...

 of 2048 bits. Like DES it has a 16-round Feistel network

Feistel cipher

In cryptography, a Feistel cipher is a symmetric structure used in the construction of block ciphers, named after the German-born physicist and cryptographer Horst Feistel who did pioneering research while working for IBM ; it is also commonly known as a Feistel network. A large proportion of block...

 structure. The round function uses two fixed 4×4-bit 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 — Shannon's property of confusion...

, chosen to be non-affine

Affine transformation

In geometry, an affine transformation or affine map or an affinity is a transformation which preserves straight lines. It is the most general class of transformations with this property...

. The 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...

 is also treated as an 8×8-bit lookup table, using the first bit of each of the 8 bytes of the half-block as input. The nth bit of the output of this table determines whether or not the two nibble

Nibble

In computing, a nibble is a four-bit aggregation, or half an octet...

s of the nth byte are swapped after S-box substitution. All rounds use the same table. Each round function ends with a fixed permutation

Permutation

In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...

 of all 64 bits, preventing the cipher from being broken down and analyzed as a system of simpler independent subciphers.

In 1977, Edna Grossman

Edna Grossman

Edna Grossman is an American mathematician. She was born in Germany, grew up in Brooklyn, New York, and graduated with a B.S. in mathematics from Brooklyn College. She earned her M.S. in mathematics from New York University's Courant Institute of Mathematical Sciences, where she also received her...

 and Bryant Tuckerman

Bryant Tuckerman

Louis Bryant Tuckerman, III was an American mathematician, born in Lincoln, Nebraska. He was a member of the team that developed the Data Encryption Standard ....

 cryptanalyzed NDS using the first known
slide attack

Slide attack

The slide attack is a form of cryptanalysis designed to deal with the prevailing idea that even weak ciphers can become very strong by increasing the number of rounds, which can ward off a differential attack. The slide attack works in such a way as to make the number of rounds in a cipher irrelevant...

. This method uses no more than 4096 chosen plaintexts; in their best trial they recovered the key with only 556 chosen plaintexts.