Abstract
Important practical characteristics of a stream cipher are its throughput and its hardware size. A common hardware implementation technique for improving the throughput is to parallelize computations but this usually requires to insert additional memory cells for storing the intermediate results, hence at the expense of an increased hardware size.
For stream ciphers with feedback shift registers (FSRs), we present an alternative approach for parallelizing operations with almost no grow of the hardware size by cleverly re-using existing structures. It is based on the fact that FSRs are usually specified in Fibonacci configuration, meaning that at each clock-cycle all but one state entries are simply shifted. The idea is to temporarily store values of the stream cipher outside of the FSR, e.g., intermediate results of the output function, directly into the FSRs.
We formally describe the transformation and its preconditions and prove its correctness. Moreover, we demonstrate our technique on Grain-128, one of the eSTREAM finalists with low hardware size. Our technique allows implementations, realized by the Cadence RTL Compiler considering UMC L180 GII technology, where the throughput is increased in the initialization mode by 18% and in the keystream generation mode by 24%, when the compiler was set to optimize the timing, and by 20 % in both modes when the compiler was set to optimize the area. As opposed to other solutions, no additional memory is required. In fact the hardware size even decreased from 1794 GE to 1748 GE in the time-optimized implementation and only slightly increased from 1627 GE to 1656 GE in the area-optimized implementation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agren, M., Hell, M., Johansson, T., Meier, W.: Grain-128a: A new version of Grain-128 with optional authentication. Int. J. Wire. Mob. Comput. 5(1), 48–59 (2011)
Chabloz, J.-M., Mansouri, S.S., Dubrova, E.: An algorithm for constructing a fastest Galois NLFSR generating a given sequence. In: Carlet, C., Pott, A. (eds.) SETA 2010. LNCS, vol. 6338, pp. 41–54. Springer, Heidelberg (2010)
Dubrova, E.: Finding matching initial states for equivalent NLFSRs in the Fibonacci and the Galois configurations. IEEE Transactions on Information Theory 56(6), 2961–2966 (2010)
Dubrova, E.: A scalable method for constructing Galois NLFSRs with period 2n − 1 using cross-join pairs. IEEE Transactions on Information Theory 59(1), 703–709 (2013)
Dubrova, E.: How to speed-up your NLFSR-based stream cipher. In: Proceedings of the Conference on Design, Automation and Test in Europe, DATE 2009, 3001 Leuven, Belgium, Belgium, pp. 878–881. European Design and Automation Association (2009)
Dubrova, E.: A transformation from the Fibonacci to the Galois NLFSRs. IEEE Transactions on Information Theory 55(11), 5263–5271 (2009)
Good, T., Benaissa, M.: Hardware performance of eSTREAM phase-III stream cipher candidates. In: Proc. of Workshop on the State of the Art of Stream Ciphers (SACS 2008) (2008)
Sen Gupta, S., Chattopadhyay, A., Sinha, K., Maitra, S., Sinha, B.P.: High-performance hardware implementation for RC4 stream cipher. IEEE Transactions on Computers 62(4), 730–743 (2013)
Hell, M., Johansson, T., Maximov, A., Meier, W.: A stream cipher proposal: Grain-128. In: 2006 IEEE International Symposium on Information Theory, pp. 1614–1618. IEEE (2006)
Mansouri, S.S., Dubrova, E.: An improved hardware implementation of the Grain stream cipher. In: 2010 13th Euromicro Conference on Digital System Design: Architectures, Methods and Tools (DSD), pp. 433–440 (September 2010)
Mansouri, S.S., Dubrova, E.: An improved hardware implementation of the Grain-128a stream cipher. In: Kwon, T., Lee, M.-K., Kwon, D. (eds.) ICISC 2012. LNCS, vol. 7839, pp. 278–292. Springer, Heidelberg (2013)
Nakano, Y., Fukushima, K., Kiyomoto, S., Miyake, Y.: Fast implementation of stream cipher K2 on FPGA. In: International Conference on Computer and Information Engineering (ICCIE), pp. 117–123 (2011)
Note, S., Catthoor, F., Goossens, G., De Man, H.J.: Combined hardware selection and pipelining in high-performance data-path design. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 11(4), 413–423 (1992)
Stefan, D., Mitchell, C.: On the parallelization of the MICKEY-128 2.0 stream cipher. In: The State of the Art of Stream Ciphers, SASC, pp. 175–185 (2008)
Yan, J., Heys, H.M.: Hardware implementation of the Salsa20 and Phelix stream ciphers. In: Canadian Conference on Electrical and Computer Engineering, CCECE 2007, pp. 1125–1128. IEEE (2007)
Jing, J., Liu, Z., Zhang, L., Pan, W.: Efficient pipelined stream cipher ZUC algorithm in FPGA. In: The First International Workshop on ZUC Algorithm, Beijing, China, December 2-3 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Armknecht, F., Mikhalev, V. (2014). On Increasing the Throughput of Stream Ciphers. In: Benaloh, J. (eds) Topics in Cryptology – CT-RSA 2014. CT-RSA 2014. Lecture Notes in Computer Science, vol 8366. Springer, Cham. https://doi.org/10.1007/978-3-319-04852-9_7
Download citation
DOI: https://doi.org/10.1007/978-3-319-04852-9_7
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-04851-2
Online ISBN: 978-3-319-04852-9
eBook Packages: Computer ScienceComputer Science (R0)