Hardware implementation of the Salsa20 and phelix stream ciphers

Yan, Junjie (2007) Hardware implementation of the Salsa20 and phelix stream ciphers. Masters thesis, Memorial University of Newfoundland.

[English] PDF - Accepted Version Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. Download (7MB)

Abstract

This thesis investigates the hardware implementation and statistical analysis of new stream ciphers, Phelix and Salsa20. Both are candidates for the eSTREAM project, a project highlighting the state of stream cipher design and analysis. -- From a physical technology perspective, hardware implementation methodology consists of Application Specific Integrated Circuit (ASIC) design and Field Programmable Gate Array (FPGA) design. When high performance is required, an ASIC is typically chosen as the implementation platform. However, FPGA platforms have become increasingly popular due to their flexibility and a diminishing performance tradeoff as compared with ASIC technology. Following this trend we have developed two versions of Salsa20, one for deployment on an ASIC, the other for an FPGA. The cipher Phelix is studied for application to ASIC environment. -- Implementing a cipher requires detailed knowledge of the cryptographic algorithm itself, particularly the underlying arithmetic. In the case of Phelix and Salsa20, both of which are composed of several simple operations: 32-bit addition, bitwise addition (exclusive or) and rotation, the most important operation is the 32-bit addition, for which we have investigated multiple structures for the adders and compared them in both speed and area. Different adder architectures are chosen for different designs, and the basic criteria is the concern of speed or area the overall implementation consumes. -- Two structures for Phelix have been implemented, one is a high speed design and the other one is aimed at compactness. The simulation results shows that it consumes about 12,000 two-input NAND gates in the compact design and achieves more than one Gbps throughput in the high speed design. The speed of the compact design is 260 Mbps and the area of the high speed design is 64,200 two-input NAND gates. Up to four different structures are investigated for Salsa20 as extra considerations are given to the utilization of FPGA. The proposed VLSI implementations achieve a data throughput up to 4.8 Gbps, and a compact FPGA design uses 194 slices and 4 memory blocks in a Xilinx device. The proposed designs in the thesis serve mainly as a quick evaluation of their hardware performance; hence, further architectural optimizations are certainly possible. --Security analysis is an important concern in cipher designs. Thus, we have applied certain statistical tests, which are publicly available in the NIST (National Institute of Standards and Technology) test suite to test various sequences produced by using the Phelix and Salsa20 algorithms. Since the test suite has not considered the relationship between key, IV, internal state and the keystream, we also applied six novel tests to examine the ciphers. Two strategies are employed to interpret the test results: the examination of the proportion of sequences that pass a statistical test and the distribution of P-values to check for uniformity. NIST gives the definition of P-value: the probability that a perfect random number generator would have produced a sequence less random than the sequence that was tested. The experimental results show that both Salsa20 and Phelix have passed the tests in NIST, considering that P-value less than 0.01 indicate a possible weakness. An easily understood deviation is observed in the correlation test for the last internal state (the state after 9 double rounds) and the keystream in Salsa20. However, how this could be exploited in an attack is an open question.

Actions (login required)

View Item