**VEST** High Level Structure of VEST | Designer(s): | Sean O'Neil | First published: | June 13 2005 | Key size(s): | any | Structure: | NLFSR, SPN, T-function | Best public cryptanalysis: | A. Joux, J.R. Reinhard, "Overtaking VEST" | | **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. VEST cannot be implemented efficiently in software. Image File history File links VEST_Structure. ...
In cryptography, the key size (alternatively key length) is a measure of the number of possible keys which can be used in a cipher. ...
A NLFSR (Non-Linear Feedback Shift Register) is a common component in modern stream ciphers, especially in RFID and smartcard applications. ...
Wikipedia does not yet have an article with this exact name. ...
VEST-4 T-function followed by a transposition layer 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...
Cryptanalysis (from the Greek kryptÃ³s, hidden, and analÃ½ein, to loosen or to untie) 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. ...
This article is about algorithms for encryption and decryption. ...
Authenticated Encryption (AE) is a term used to describe encryption systems which simultaneously protect privacy and authenticity. ...
In cryptography, a cryptographic hash function is a hash function with certain additional security properties to make it suitable for use as a primitive in various information security applications, such as authentication and message integrity. ...
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. VEST-4 T-function followed by a transposition layer 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...
In mathematics, a bijection, bijective function, or one-to-one correspondence is a function that is both injective (one-to-one) and surjective (onto), and therefore bijections are also called one_to_one and onto. ...
A NLFSR (Non-Linear Feedback Shift Register) is a common component in modern stream ciphers, especially in RFID and smartcard applications. ...
Wikipedia does not yet have an article with this exact name. ...
A residue number system (RNS) represents a large integer using a set of smaller integers, so that computation may be performed more efficiently. ...
IV may refer to: The Roman number for four â€” meaning one (I) less than five (V). ...
In cryptography, the key size (alternatively key length) is a measure of the number of possible keys which can be used in a cipher. ...
Synaptic Laboratories state that all the VEST variants are covered by several pending patent applications. VEST was submitted to the eSTREAM competition by Sean O'Neil (aka "Ruptor"), Benjamin Gittins and Howard Landman. It has been selected for Phase 2 of the process, but its patent claim ruled it out of being a focus candidate. eSTREAM is a project to identify new stream ciphers that might become suitable for widespread adoption, organised by the EU ECRYPT network. ...
## Overview Cipher: | VEST-4 | VEST-8 | VEST-16 | VEST-32 | AES-128 | Output, bits per call: | 4 | 8 | 16 | 32 | 128 | Claimed security, bits: | 80 | 128 | 160 | 256 | 128 | Recommended key length, bits: | 160 | 256 | 320 | 512 | 128 | Recommended hash length, bits: | 160 | 256 | 320 | 512 | Counter size, bits: | 163 | 163 | 171 | 171 | Core size, bits: | 83 | 211 | 331 | 587 | State size, bits: | 256 | 384 | 512 | 768 | 128 | ## 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. A NLFSR (Non-Linear Feedback Shift Register) is a common component in modern stream ciphers, especially in RFID and smartcard applications. ...
In mathematics, a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. ...
Wiktionary has related dictionary definitions, such as: period Wiktionary has related dictionary definitions, such as: periodic Period and periodic may refer to: Period (music) Period (rhetoric) Historical period Menstrual cycle, relating to the reproductive system Full stop, also known as a period, that marks the end of a sentence Science...
### 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: In cryptography, an SP-network, or substitution-permutation network (SPN), is a series of linked mathematical operations used in block cipher algorithms such as AES. These networks consist of S-boxes and P-boxes that transform blocks of input bits into output bits. ...
It accepts 10 bits (*d*_{0} - d_{9}) as its input. The least significant five bits (*p*_{0} - p_{4}) in the accumulator state are updated by a 5x5 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 (*e*_{0} - e_{3}) 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). Image File history File links VEST_Core4_HighLevel. ...
In cryptography, a substitution box (or S-box) is a basic component of symmetric key algorithms. ...
In general, substitution is the replacement of one thing with another. ...
A pseudo-random number is a number belonging to a sequence which appears to be random, but can in fact be generated by a finite computation. ...
In music, transposition is moving a note or collection of notes up or down in pitch by a constant interval. ...
## 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. Wiktionary has related dictionary definitions, such as: period Wiktionary has related dictionary definitions, such as: periodic Period and periodic may refer to: Period (music) Period (rhetoric) Historical period Menstrual cycle, relating to the reproductive system Full stop, also known as a period, that marks the end of a sentence Science...
### 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-4 | VEST-8 | VEST-16 | VEST-32 | Guaranteed Minimum | 2^{134} | 2^{134} | 2^{143} | 2^{143} | Longest Possible | 2^{251} | 2^{383} | 2^{519} | 2^{791} | ## 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 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). Image File history File links VEST_Core4_LowLevel. ...
Image File history File links VEST_Core4_LowLevel. ...
Implementation: | Clock | VEST-4 | VEST-8 | VEST-16 | VEST-32 | Hardware | 250 MHz | ~1 Gb/s | ~2 Gb/s | ~4 Gb/s | ~8 Gb/s | Software | 250 MHz | < 1.0 Mb/s | < 0.8 Mb/s | < 1.1 Mb/s | < 1.3 Mb/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 are 2-4 times slower than the 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. A field-programmable gate array or FPGA is a gate array that can be reprogrammed after it is manufactured, rather than having its programming fixed during the manufacturing — a programmable logic device. ...
The acronym ASIC, depending on context, may stand for: Application-specific integrated circuit ASIC programming language Australian Securities and Investments Commission This is a disambiguation page â€” a navigational aid which lists pages that might otherwise share the same title. ...
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 Gb/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 Gb/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: - Instantly loading the entire cipher state with a cryptographically strong key (100% entropy) supplied by a strong key generation or key exchange process;
- Instant reloading of the entire cipher state with a previously securely initialised cipher state;
- Incremental key loading (of an imperfect key) beginning with the least significant bit of the key loaded into the counter 15, sliding the 16-bit window down by one bit on each round until the single bit 1 that follows the most significant bit of the key is loaded into the counter 0. The process ends with 32 additional sealing rounds. The entire cipher state can now be stored for instant reloading.
Key Bits | Rounds to load a key | 80 | 128 | 160 | 208 | 256 | 304 | 320 | 368 | 512 | 560 | VEST ciphers offer only 1 resynchronisation strategy: - Hashing the (IV) by loading it incrementally 8-bits at a time into the first 8 RNS counters, followed by additional 32 sealing rounds.
IV Bits | Rounds to load an IV | 64 | 40 | 128 | 48 | 256 | 64 | ## History VEST was designed by Sean O'Neil and was submitted to the eStream competition in June 2005. This was the first publication of the cipher.
## Security The authors claim 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. Lars R. Knudsen Lars Ramkilde Knudsen (born February 21, 1962) is a Danish researcher in cryptography, particularly interested in the design and analysis of block ciphers, hash functions and message authentication codes (MACs). ...
Nicolas Courtois is a cryptographer who works on cryptosystems and cryptographic attacks based on multivariate polynomial equations over finite fields. ...
### 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 [1], 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 the 21st of January 2007, a few days prior to publication of the attack. It is currently unknown as to whether this correction will be accepted by ECRYPT, as the official window for accepting cipher tweaks has passed.
## External links ## References |