VEST

Last updated
VEST
VEST Structure.PNG
High Level Structure of VEST
General
DesignersSean O'Neil
First publishedJune 13, 2005
Cipher detail
Key sizes any
Security claims80256 bits
State size256 bits (VEST-4) to 768 (VEST-32)
Structure NLFSR, SPN, T-function

VEST (Very Efficient Substitution Transposition) ciphers are a set of families of general-purpose hardware-dedicated ciphers that support single pass authenticated encryption and can operate as collision-resistant hash functions designed by Sean O'Neil, Benjamin Gittins and Howard Landman. [1] VEST cannot be implemented efficiently in software.

Contents

VEST is based on a balanced T-function that can also be described as a bijective nonlinear feedback shift register with parallel feedback (NLPFSR) or as a substitution–permutation network, which is assisted by a non-linear RNS-based counter. The four VEST family trees described in the cipher specification are VEST-4, VEST-8, VEST-16, and VEST-32. VEST ciphers support keys and IVs of variable sizes and instant re-keying. All VEST ciphers release output on every clock cycle.

All the VEST variants are covered by European Patent Number EP 1820295(B1), owned by Synaptic Laboratories.

VEST was a Phase 2 Candidate in the eSTREAM competition in the hardware portfolio, but was not a Phase 3 or Focus candidate and so is not part of the final portfolio.

Overview

Cipher:VEST-4VEST-8VEST-16VEST-32AES-128
Output, bits per call:481632128
Claimed security, bits:80128160256128
Recommended key length, bits:160256320512128
Recommended hash length, bits:160256320512
Counter size, bits:163163171171
Core size, bits:83211331587
State size, bits:256384512768128

Design

Overall structure

VEST ciphers consist of four components: a non-linear counter, a linear counter diffusor, a bijective non-linear accumulator with a large state and a linear output combiner (as illustrated by the image on the top-right corner of this page). The RNS counter consists of sixteen NLFSRs with prime periods, the counter diffusor is a set of 5-to-1 linear combiners with feedback compressing outputs of the 16 counters into 10 bits while at the same time expanding the 8 data inputs into 9 bits, the core accumulator is an NLPFSR accepting 10 bits of the counter diffusor as its input, and the output combiner is a set of 6-to-1 linear combiners.

Accumulator

The core accumulator in VEST ciphers can be seen as a SPN constructed using non-linear 6-to-1 feedback functions, one for each bit, all of which are updated simultaneously. The VEST-4 core accumulator is illustrated below:

Partial high-level illustration of the VEST-4 core VEST-4 accumulator.png
Partial high-level illustration of the VEST-4 core

It accepts 10 bits (d0  d9) as its input. The least significant five bits (p0  p4) in the accumulator state are updated by a 5×5 substitution box and linearly combined with the first five input bits on each round. The next five accumulator bits are linearly combined with the next five input bits and with a non-linear function of four of the less significant accumulator bits. In authenticated encryption mode, the ciphertext feedback bits are also linearly fed back into the accumulator (e0  e3) with a non-linear function of four of the less significant accumulator bits. All the other bits in the VEST accumulator state are linearly combined with non-linear functions of five less significant bits of the accumulator state on each round. The use of only the less significant bits as inputs into the feedback functions for each bit is typical of T-functions and is responsible for the feedback bijectivity. This substitution operation is followed by a pseudorandom transposition of all the bits in the state (see picture below).

Data authentication

VEST ciphers can be executed in their native authenticated encryption mode similar to that of Phelix but authenticating ciphertext rather than plaintext at the same speed and occupying the same area as keystream generation. However, unkeyed authentication (hashing) is performed only 8 bits at a time by loading the plaintext into the counters rather than directly into the core accumulator.

Family keying

The four root VEST cipher families are referred to as VEST-4, VEST-8, VEST-16, and VEST-32. Each of the four family trees of VEST ciphers supports family keying to generate other independent cipher families of the same size. The family-keying process is a standard method to generate cipher families with unique substitutions and unique counters with different periods. Family keying enables the end-user to generate a unique secure cipher for every chip.

Periods

VEST ciphers are assisted by a non-linear RNS counter with a very long period. According to the authors, determining average periods of VEST ciphers or probabilities of the shortest periods of VEST-16 and VEST-32 falling below their advertised security ratings for some keys remains an open problem and is computationally infeasible. They believe that these probabilities are below 2−160 for VEST-16 and below 2−256 for VEST-32. The shortest theoretically possible periods of VEST-4 and VEST-8 are above their security ratings as can be seen from the following table.

Period:VEST-4VEST-8VEST-16VEST-32
Guaranteed Minimum2134213421432143
Longest Possible2251238325192791

Performance

Computational efficiency in software

The core accumulator in VEST ciphers has a complex, highly irregular structure that resists its efficient implementation in software.

The VEST-4 core: Substitution followed by Transposition VEST Core4 LowLevel.png
The VEST-4 core: Substitution followed by Transposition

The highly irregular input structure coupled with a unique set of inputs for each feedback function hinders efficient software execution. As a result, all the feedback functions need to be calculated sequentially in software, thus resulting in the hardware-software speed difference being approximately equal to the number of gates occupied by the feedback logic in hardware (see the column "Difference" in the table below).

Implementation:ClockVEST-4VEST-8VEST-16VEST-32
Hardware250 MHz~1 Gbit/s~2 Gbit/s~4 Gbit/s~8 Gbit/s
Software250 MHz< 1.0 Mbit/s< 0.8 Mbit/s< 1.1 Mbit/s< 1.3 Mbit/s
Difference> 1000 x> 2300 x> 3500 x> 6000 x

The large differential between VEST's optimised hardware execution and equivalently clocked software optimised execution offers a natural resistance against low cost general-purpose software processor clones masquerading as genuine hardware authentication tokens.

In bulk challenge-response scenarios such as RFID authentication applications, bitsliced implementations of VEST ciphers on 32-bit processors which process many independent messages simultaneously are 2–4 times slower per message byte than AES.

Hardware performance

VEST is submitted to the eStream competition under the Profile II as designed for "hardware applications with restricted resources such as limited storage, gate count, or power consumption", and shows high speeds in FPGA and ASIC hardware according to the evaluation by ETH Zurich.

The authors claim that according to their own implementations using "conservative standard RapidChip design front-end sign-off process", "VEST-32 can effortlessly satisfy a demand for 256-bit secure 10 Gbit/s authenticated encryption @ 167 MHz on 180ηm LSI Logic RapidChip platform ASIC technologies in less than 45K Gates and zero SRAM". On the 110ηm Rapidchip technologies, VEST-32 offers 20 Gbit/s authenticated encryption @ 320 MHz in less than 45 K gates". They also state that unrolling the round function of VEST can halve the clock-speed and reduce power consumption while doubling the output per clock-cycle, at the cost of increased area.

Key agility

VEST ciphers offer 3 keying strategies:

Key BitsRounds to load a key
80128
160208
256304
320368
512560

VEST ciphers offer only 1 resynchronisation strategy:

IV BitsRounds to load an IV
6440
12848
25664

History

VEST was designed by Sean O'Neil and submitted to the eStream competition in June 2005. This was the first publication of the cipher.[ citation needed ]

Security

The authors say that VEST security margins are inline with the guidelines proposed by Lars Knudsen in the paper "Some thoughts on the AES process" and the more conservative guidelines recently proposed by Nicolas Courtois in the paper “Cryptanalysis of Sfinks”. Although the authors are not publishing their own cryptanalysis, VEST ciphers have survived more than a year of public scrutiny as a part of the eStream competition organised by the ECRYPT. They were advanced to the second phase, albeit not as part of the focus group.

Attacks

At SASC 2007, Joux and Reinhard published an attack that recovered 53 bits of the counter state. By comparing the complexity of the attack to a parallelized brute-force attack, Bernstein evaluated the resultant strength of the cipher as 100 bits, [2] somewhat below the design strength of most of the VEST family members. The designers of VEST claimed the attack is due to a typographical error in the original cipher specification and published a correction on the Cryptology ePrint archive on 21 January 2007, a few days prior to publication of the attack.

Related Research Articles

<span class="mw-page-title-main">Advanced Encryption Standard</span> Standard for the encryption of electronic data

The Advanced Encryption Standard (AES), also known by its original name Rijndael, is a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001.

In cryptography, a block cipher is a deterministic algorithm that operates on fixed-length groups of bits, called blocks. Block ciphers are the elementary building blocks of many cryptographic protocols. They are ubiquitous in the storage and exchange of data, where such data is secured and authenticated via encryption.

<span class="mw-page-title-main">Data Encryption Standard</span> Early unclassified symmetric-key block cipher

The Data Encryption Standard is a symmetric-key algorithm for the encryption of digital data. Although its short key length of 56 bits makes it too insecure for modern applications, it has been highly influential in the advancement of cryptography.

Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in information input can affect the resultant difference at the output. In the case of a block cipher, it refers to a set of techniques for tracing differences through the network of transformation, discovering where the cipher exhibits non-random behavior, and exploiting such properties to recover the secret key.

<span class="mw-page-title-main">Stream cipher</span> Type of symmetric key cipher

A stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream, to give a digit of the ciphertext stream. Since encryption of each digit is dependent on the current state of the cipher, it is also known as state cipher. In practice, a digit is typically a bit and the combining operation is an exclusive-or (XOR).

In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state.

In cryptography, a block cipher mode of operation is an algorithm that uses a block cipher to provide information security such as confidentiality or authenticity. A block cipher by itself is only suitable for the secure cryptographic transformation of one fixed-length group of bits called a block. A mode of operation describes how to repeatedly apply a cipher's single-block operation to securely transform amounts of data larger than a block.

Articles related to cryptography include:

<span class="mw-page-title-main">Serpent (cipher)</span>

Serpent is a symmetric key block cipher that was a finalist in the Advanced Encryption Standard (AES) contest, in which it ranked second to Rijndael. Serpent was designed by Ross Anderson, Eli Biham, and Lars Knudsen.

<span class="mw-page-title-main">LOKI97</span> Block cipher

In cryptography, LOKI97 is a block cipher which was a candidate in the Advanced Encryption Standard competition. It is a member of the LOKI family of ciphers, with earlier instances being LOKI89 and LOKI91. LOKI97 was designed by Lawrie Brown, assisted by Jennifer Seberry and Josef Pieprzyk.

Phelix is a high-speed stream cipher with a built-in single-pass message authentication code (MAC) functionality, submitted in 2004 to the eSTREAM contest by Doug Whiting, Bruce Schneier, Stefan Lucks, and Frédéric Muller. The cipher uses only the operations of addition modulo 232, exclusive or, and rotation by a fixed number of bits. Phelix uses a 256-bit key and a 128-bit nonce, claiming a design strength of 128 bits. Concerns have been raised over the ability to recover the secret key if the cipher is used incorrectly.

In cryptography, MUGI is a pseudorandom number generator (PRNG) designed for use as a stream cipher. It was among the cryptographic techniques recommended for Japanese government use by CRYPTREC in 2003, however, has been dropped to "candidate" by CRYPTREC revision in 2013.

The Secure Real-time Transport Protocol (SRTP) is a profile for Real-time Transport Protocol (RTP) intended to provide encryption, message authentication and integrity, and replay attack protection to the RTP data in both unicast and multicast applications. It was developed by a small team of Internet Protocol and cryptographic experts from Cisco and Ericsson. It was first published by the IETF in March 2004 as RFC 3711.

<span class="mw-page-title-main">Salsa20</span> Stream ciphers

Salsa20 and the closely related ChaCha are stream ciphers developed by Daniel J. Bernstein. Salsa20, the original cipher, was designed in 2005, then later submitted to the eSTREAM European Union cryptographic validation process by Bernstein. ChaCha is a modification of Salsa20 published in 2008. It uses a new round function that increases diffusion and increases performance on some architectures.

Grain is a stream cipher submitted to eSTREAM in 2004 by Martin Hell, Thomas Johansson and Willi Meier. It has been selected for the final eSTREAM portfolio for Profile 2 by the eSTREAM project. Grain is designed primarily for restricted hardware environments. It accepts an 80-bit key and a 64-bit IV. The specifications do not recommend a maximum length of output per pair. A number of potential weaknesses in the cipher have been identified and corrected in Grain 128a which is now the recommended cipher to use for hardware environments providing both 128bit security and authentication.

HC-256 is a stream cipher designed to provide bulk encryption in software at high speeds while permitting strong confidence in its security. A 128-bit variant was submitted as an eSTREAM cipher candidate and has been selected as one of the four final contestants in the software profile.

In cryptography, Galois/Counter Mode (GCM) is a mode of operation for symmetric-key cryptographic block ciphers which is widely adopted for its performance. GCM throughput rates for state-of-the-art, high-speed communication channels can be achieved with inexpensive hardware resources.

KeeLoq is a proprietary hardware-dedicated block cipher that uses a non-linear feedback shift register (NLFSR). The uni-directional command transfer protocol was designed by Frederick Bruwer of Nanoteq (Pty) Ltd., the cryptographic algorithm was created by Gideon Kuhn at the University of Pretoria, and the silicon implementation was by Willem Smit at Nanoteq Pty Ltd in the mid-1980s. KeeLoq was sold to Microchip Technology Inc in 1995 for $10 million. It is used in "code hopping" encoders and decoders such as NTQ105/106/115/125D/129D, HCS101/2XX/3XX/4XX/5XX and MCS31X2. KeeLoq is or was used in many remote keyless entry systems by such companies as Chrysler, Daewoo, Fiat, GM, Honda, Toyota, Volvo, Volkswagen Group, Clifford, Shurlok, and Jaguar.

In cryptography, a T-function is a bijective mapping that updates every bit of the state in a way that can be described as , or in simple words an update function in which each bit of the state is updated by a linear combination of the same bit and a function of a subset of its less significant bits. If every single less significant bit is included in the update of every bit in the state, such a T-function is called triangular. Thanks to their bijectivity regardless of the used Boolean functions and regardless of the selection of inputs, T-functions are now widely used in cryptography to construct block ciphers, stream ciphers, PRNGs and hash functions. T-functions were first proposed in 2002 by A. Klimov and A. Shamir in their paper "A New Class of Invertible Mappings". Ciphers such as TSC-1, TSC-3, TSC-4, ABC, Mir-1 and VEST are built with different types of T-functions.

ChaCha20-Poly1305 is an authenticated encryption with additional data (AEAD) algorithm, that combines the ChaCha20 stream cipher with the Poly1305 message authentication code. Its usage in IETF protocols is standardized in RFC 8439. It has fast software performance, and without hardware acceleration, is usually faster than AES-GCM.

References

  1. Sean O’Neil; Benjamin Gittins; Howard Landman (2005-10-25). "VEST, Hardware-Dedicated Stream Ciphers" (PDF). ESTREAM Round 1 Submission. Retrieved 2007-05-15.
  2. "ECRYPT Forum: Attack status of the eSTREAM submissions". Archived from the original on 2011-12-28.