This page uses content from Wikipedia and is licensed under CC BYSA.
High Level Structure of VEST


General  

Designers  Sean O'Neil 
First published  June 13, 2005 
Cipher detail  
Key sizes  any 
Security claims  80–256 bits 
State size  256 bits (VEST4) to 768 (VEST32) 
Structure  NLFSR, SPN, Tfunction 
VEST (Very Efficient Substitution Transposition) ciphers are a set of families of generalpurpose hardwarededicated ciphers that support single pass authenticated encryption and can operate as collisionresistant hash functions designed by Sean O'Neil, Benjamin Gittins and Howard Landman.^{[1]} VEST cannot be implemented efficiently in software.
VEST is based on a balanced Tfunction that can also be described as a bijective nonlinear feedback shift register with parallel feedback (NLPFSR) or as a substitutionpermutation network, which is assisted by a nonlinear RNSbased counter. The four VEST family trees described in the cipher specification are VEST4, VEST8, VEST16, and VEST32. VEST ciphers support keys and IVs of variable sizes and instant rekeying. 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.
Cipher:  VEST4  VEST8  VEST16  VEST32  AES128 

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 
VEST ciphers consist of four components: a nonlinear counter, a linear counter diffusor, a bijective nonlinear accumulator with a large state and a linear output combiner (as illustrated by the image on the topright corner of this page). The RNS counter consists of sixteen NLFSRs with prime periods, the counter diffusor is a set of 5to1 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 6to1 linear combiners.
The core accumulator in VEST ciphers can be seen as a SPN constructed using nonlinear 6to1 feedback functions, one for each bit, all of which are updated simultaneously. The VEST4 core accumulator is illustrated below:
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 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 nonlinear 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 nonlinear function of four of the less significant accumulator bits. All the other bits in the VEST accumulator state are linearly combined with nonlinear 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 Tfunctions 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).
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.
The four root VEST cipher families are referred to as VEST4, VEST8, VEST16, and VEST32. Each of the four family trees of VEST ciphers supports family keying to generate other independent cipher families of the same size. The familykeying process is a standard method to generate cipher families with unique substitutions and unique counters with different periods. Family keying enables the enduser to generate a unique secure cipher for every chip.
VEST ciphers are assisted by a nonlinear RNS counter with a very long period. According to the authors, determining average periods of VEST ciphers or probabilities of the shortest periods of VEST16 and VEST32 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 VEST16 and below 2^{−256} for VEST32. The shortest theoretically possible periods of VEST4 and VEST8 are above their security ratings as can be seen from the following table.
Period:  VEST4  VEST8  VEST16  VEST32 

Guaranteed Minimum  2^{134}  2^{134}  2^{143}  2^{143} 
Longest Possible  2^{251}  2^{383}  2^{519}  2^{791} 
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 hardwaresoftware 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  VEST4  VEST8  VEST16  VEST32 

Hardware  250 MHz  ~1 Gbit/s  ~2 Gbit/s  ~4 Gbit/s  ~8 Gbit/s 
Software  250 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 generalpurpose software processor clones masquerading as genuine hardware authentication tokens.
In bulk challengeresponse scenarios such as RFID authentication applications, bitsliced implementations of VEST ciphers on 32bit processors which process many independent messages simultaneously are 2–4 times slower per message byte than AES.
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 frontend signoff process", "VEST32 can effortlessly satisfy a demand for 256bit 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, VEST32 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 clockspeed and reduce power consumption while doubling the output per clockcycle, at the cost of increased area.
VEST ciphers offer 3 keying strategies:
Key Bits  Rounds to load a key 

80  128 
160  208 
256  304 
320  368 
512  560 
VEST ciphers offer only 1 resynchronisation strategy:
IV Bits  Rounds to load an IV 

64  40 
128  48 
256  64 
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]}
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.
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 bruteforce 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.