Enhanced Ant Colony-Inspired Parallel Algorithm to Improve Cryptographic PRNGs

Authors

  • Jorg Keller FernUniversit¨at in Hagen, Germany
  • Gabriele Spenger FernUniversit¨at in Hagen, Germany
  • Steffen Wendzel Worms University of Applied Science, Germany

DOI:

https://doi.org/10.13052/2245-1439.623

Keywords:

Pseudo-Random Generators, Parallel Efficiency, Ant Colony, Lightweight Cryptography

Abstract

We present and motivate a parallel algorithm to compute promising candidate states for modifying the state space of a pseudo-random number generator in order to increase its cycle length. This is important for generators in low-power devices where increase of state space to achieve longer cycles is not an alternative. The runtime of the parallel algorithm is improved by an analogy to ant colony behavior: if two paths meet, the resulting path is followed at accelerated speed just as ants tend to reinforce paths that have been used by other ants. We evaluate our algorithm with simulations and demonstrate high parallel efficiency that makes the algorithm well-suited even for massively parallel systems like GPUs. Furthermore, the accelerated path variant of the algorithm achieves a runtime improvement of up to 4% over the straightforward implementation.1

 

Downloads

Download data is not yet available.

Author Biographies

Jorg Keller, FernUniversit¨at in Hagen, Germany

Jörg Keller is a professor of computer engineering at FernUniversität in Hagen, Germany, and heads the Parallelism & VLSI group since 1996. His research interests are parallel and energy-efficient computing, security and fault-tolerance of computer systems, and web-based learning in engineering. He received M.Sc. and Ph.D. degrees from Saarland University, Germany, in 1989 and 1992, respectively, and spent his PostDoc phase at CWI (Netherland’s Research Centre for Mathematics and Computer Science) in Amsterdam.

Gabriele Spenger, FernUniversit¨at in Hagen, Germany

Gabriele Spenger is a Ph.D. student at the Parallelism & VLSI group of FernUniversität in Hagen, Germany. Her research focus is on security and RFID. She received her diploma in Mathematics from Friedrich-Alexander-Universität, Germany in 1998.

Steffen Wendzel, Worms University of Applied Science, Germany

Steffen Wendzel received his Ph.D. degree in computer science from the University of Hagen in 2013, Germany. Between 2013 and 2016, he was head of a smart building security research team at Fraunhofer FKIE, Germany. He joined Worms University of Applied Sciences as a professor of information security and computer networks in 2016. Steffen wrote five books and his research focuses on information hiding and security in the Internet of Things.

References

Andreas Beckmann, Jaroslaw Fedorowicz, Jörg Keller, and Ulrich Meyer. A structural analysis of the A5/1 state transition graph. In Proc. First Workshop on GRAPH Inspection and Traversal Engineering, volume 99 of Electronic Proceedings in Theoretical Computer Science, pages 5–19. Open Publishing Association, 2012.

Alex Biryukov, Adi Shamir, and David Wagner. Real time cryptanalysis of A5/1 on a PC. In Fast Software Encryption, pages 37–44. Springer, 2001.

Anand Desai, Alejandro Hevia, and Yiqun Lisa Yin. A practice-oriented treatment of pseudorandom number generators. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 368–383. Springer, 2002.

Yevgeniy Dodis, David Pointcheval, Sylvain Ruhault, Damien Vergniaud, and Daniel Wichs. Security analysis of pseudo-random number generators with input:/dev/random is not robust. In Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security, pages 647–658. ACM, 2013.

Marco Dorigo and Luca Maria Gambardella. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on evolutionary computation, 1(1):53–66, 1997.

Philippe Flajolet and Andrew M. Odlyzko. Random mapping statistics. In Advances in Cryptology, pages 329–354. Springer, 1990.

Jovan Golic. Cryptanalysis of alleged A5 stream cipher. In Walter Fumy, editor, Advances in Cryptology (EUROCRYPT ’97), volume 1233 of Lecture Notes in Computer Science, pages 239–255. Springer Berlin Heidelberg, 1997.

Jan Heichler, Jörg Keller, and Jop F. Sibeyn. Parallel storage allocation for intermediate results during exploration of random mappings. In Proc. 20th Workshop Parallel-Algorithmen, -Rechnerstrukturen und -Systemsoftware (PARS ’05), pages 126–134. GI, June 2005.

Jörg Keller. Parallel exploration of the structure of random functions. In Proceedings of the 6th Workshop on Parallel Systems and Algorithms (PASA) in conjunction with the International Conference on Architecture of Computing Systems, ARCS, pages 233–236. VDE, 2002.

Jörg Keller, Gabriele Spenger, and Steffen Wendzel. Ant colony-inspired parallel algorithm to improve cryptographic pseudo random number generators. In Proc. BioSTAR/IEEE Security & Privacy Workshops, May 2017.

Donald E. Knuth. Mathematical analysis of algorithms. In Proc. of IFIP Congress 1971, Information Processing 71, pages 19–27. North-Holland Publ. Co., 1972.

Leslie Lamport. Password authentication with insecure communication. Commun. ACM, 24(11):770–772, November 1981.

George Marsaglia. The marsaglia random number cdrom including the diehard battery of tests of randomness, 1995.

Honorio Martin, Enrique San Millan, Luis Entrena, Pedro Peris Lopez, and Julio Cesar Hernandez Castro. AKARI-X: A pseudorandom number generator for secure lightweight systems. 11th IEEE International On-Line Testing Symposium, pages 228–233, 2011.

Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996.

Ronald L. Rivest and Jacob C. N. Schuldt. Spritz—a spongy RC4-like stream cipher and hash function. Cryptology ePrint Archive, Report 2016/856, 2016. http://eprint.iacr.org/2016/856.

Andrew Rukhin, Juan Soto, James Nechvatal, Miles Smid, and Elaine Barker. Statistical test suite for random and pseudorandom number generators for cryptographic applications: Special publication 800-22, revision 1a, 2010.

Gabriele Spenger and Jörg Keller. Tweaking cryptographic primitives with moderate state space by direct manipulation. In Proc. IEEE International Conference on Communications (ICC’17), pages 1–7. IEEE, May 2017.

Downloads

Published

2017-04-22

How to Cite

1.
Keller J, Spenger G, Wendzel S. Enhanced Ant Colony-Inspired Parallel Algorithm to Improve Cryptographic PRNGs. JCSANDM [Internet]. 2017 Apr. 22 [cited 2024 Mar. 29];6(2):147-70. Available from: https://journals.riverpublishers.com/index.php/JCSANDM/article/view/5215

Issue

Section

Articles

Most read articles by the same author(s)