VEST
From Wikipedia, the free encyclopedia
 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.
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.
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 was announced at FSE 2007 that VEST will not be selected as part of the hardware portfolio proposed by the eSTREAM.
Contents |
[edit] 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 |
[edit] Design
[edit] 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.
[edit] 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:
It accepts 10 bits (d0 - d9) as its input. The least significant five bits (p0 - p4) 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 (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).
[edit] 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.
[edit] 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.
[edit] 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 | 2134 | 2134 | 2143 | 2143 |
| Longest Possible | 2251 | 2383 | 2519 | 2791 |
[edit] Performance
[edit] Computational Efficiency in Software
The core accumulator in VEST ciphers has a complex, highly irregular structure that resists its efficient implementation in software.
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: | 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.
[edit] 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 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.
[edit] 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 |
[edit] 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.
[edit] 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.
[edit] 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.
[edit] External links
- Latest correct VEST specification
- Synaptic Laboratories Ltd. BVI website
- eSTREAM page on VEST
- VEST eStream Phase II specification
- VEST C reference source code and test vectors
- ETH Zurich Hardware Performance Review
[edit] References
- "Some thoughts on the AES process" paper by Lars R. Knudsen
- "Cryptanalysis of Sfinks" paper by Nicolas Courtois
- "Rediscovery of Time Memory Tradeoffs" paper by J. Hong and P. Sarkar
- "Understanding Brute Force" paper by Daniel J. Bernstein
- "Comments on the Rediscovery of Time Memory Data Tradeoffs" paper by C. De Cannière, J. Lano and B. Preneel
- Ideal-to-Realized Security Assurance In Cryptographic Keys by Justin Troutman
