Shark (cipher)

Shark (cipher). Shark is a block cipher designed in 1996 by a team of prominent cryptographers. It was one of the early ciphers to employ a Substitution–permutation network structure with operations derived from a finite field. The design principles pioneered in Shark directly influenced the development of the Advanced Encryption Standard.

History and development

The cipher was created by Vincent Rijmen and Joan Daemen, who were later joined by Lars Knudsen and Bart Preneel. Its development occurred during a period of intense cryptographic research following the public disclosure of Differential cryptanalysis. The designers sought to create an algorithm with provable security against known attacks like Linear cryptanalysis. Work on Shark was conducted in the Katholieke Universiteit Leuven and was presented at the Fast Software Encryption workshop in 1996. This period also saw the finalization of the Data Encryption Standard replacement process, which would later select the Rijndael (cipher) as the winner.

Design and algorithm

Shark operates on a 64-bit block size using a 128-bit key size and employs a Substitution–permutation network structure over six rounds (cryptography). Its core innovation was the use of an MDS code derived from a finite field for its linear transformation layer, providing optimal Diffusion (cryptography). The non-linear layer uses an S-box based on the mapping x^-1 in GF(2ⁿ), similar to that later used in the Advanced Encryption Standard. The key schedule expands the initial key using a Feistel-like structure to generate round keys for each iteration.

Security and cryptanalysis

Shark was designed with provable security bounds against Differential cryptanalysis and Linear cryptanalysis, a significant advancement at the time. However, Lars Knudsen discovered a dedicated Square attack against the cipher, which exploited the byte-oriented structure of its Substitution–permutation network. This attack was a crucial development in cryptanalysis, as it was the first of its kind and was later applied to the related Square (cipher). The vulnerability demonstrated the importance of analyzing rounds (cryptography) beyond theoretical bounds, influencing the design of subsequent ciphers like Rijndael (cipher).

Implementations and usage

Due to its status as a research cipher, Shark saw no widespread adoption in commercial products or government standards like Federal Information Processing Standards. However, it was implemented in various academic and research software libraries for analysis, including those at the Katholieke Universiteit Leuven. Its primary usage was as a testbed for the new design principles that would culminate in the Advanced Encryption Standard proposal. The cipher's structure influenced the development of the NESSIE project's evaluation framework.

Variants and related ciphers

The immediate successor to Shark was the Square (cipher), which modified the linear transformation to improve efficiency while inheriting the core structure. Both Shark and Square (cipher) are direct ancestors of Rijndael (cipher), which was selected as the Advanced Encryption Standard by National Institute of Standards and Technology. Other ciphers from the same design lineage include BKSQ, and the principles influenced later designs like Anubis (cipher) and KHAZAD. The MDS matrix concept from Shark also appears in the Twofish algorithm submitted to the Advanced Encryption Standard competition.

Category:Block ciphers