Solving weakened cryptanalysis problems for the Bivium cipher in the volunteer computing project SAT@home

Oleg Zaikin, Alexander Semenov, Ilya Otpuschennikov

Abstract


In this paper, a SAT-based cryptanalysis of the Bivium stream cipher is considered. For encoding the initial cryptanalysis problem into SAT a special program system Transalg was used. For an obtained SAT instance we use Monte Carlo method to search for a partitioning with good time estimation. Several weakened cryptanalysis instances of the Bivium generator were successfully solved in the volunteer computing project SAT@home using corresponding partitionings found on a computing cluster.

Full Text:

PDF

References


M. N. Durrani and J. A. Shamsi, “Review: Volunteer computing: Requirements, challenges, and solutions,” J. Netw. Comput. Appl., vol. 39, pp. 369–380, 2014.

D. P. Anderson and G. Fedak, “The computational and storage potential of volunteer computing,” in Proc. 6th IEEE International Symposium on Cluster Computing and the Grid, Singapore, 2006, pp. 73–80.

Handbook of Satisfiability, Frontiers in Artificial Intelligence and Applications, vol. 185. IOS Press, 2009.

C. D. Canniere, “Trivium: A stream cipher construction inspired by block cipher design principles,” in Proc. 9th International Conference ISC, Samos Island, Greece, 2006, pp. 171–186.

A. Maximov and A. Biryukov, “Two trivial attacks on Trivium,” in Proc. 14th International Workshop on Selected Areas in Cryptography, Ottawa, Canada, 2007, pp. 36–55.

M. Soos, “Grain of Salt - an AutomatedWay to Test Stream Ciphers through SAT Solvers,” in Proc. Workshop on Tools for Cryptanalysis, London, UK, 2010, pp. 131–144.

T. Eibach, E. Pilz and G. Volkel, “Attacking Bivium Using SAT Solvers,” in Proc. 11th International Conference on Theory and Applications of Satisfiability Testing, Guangzhou, China, 2008, pp. 63–76.

I. V. Otpuschennikov, A. A. Semenov, S. E. Kochemazov, “Transalg: a tool for translating procedural descriptions of discrete functions to SAT,” in Proc. 5th International Workshop on Computer Science and Engineering: Information Processing and Control Engineering, Moscow, Russia, 2015, pp. 289-294.

G. S. Tseitin, “On the complexity of derivation in propositional calculus,” Automation of Reasoning 2: Classical Papers on Computational Logic 1967-1970, pp. 466–483, 1983.

M. Posypkin, A. Semenov and O. Zaikin, “Using BOINC desktop grid to solve large scale SAT problems,” Computer Science Journal, vol. 13, no. 1, pp. 25–34, 2012.

A. Semenov, O. Zaikin, “Using Monte Carlo method for searching partitionings of hard variants of Boolean satisfiability problem,” in Proc. 13th International Conference on Parallel Computing Technologies, Petrozavodsk, Russia, 2015, pp. 222–230.

N. Een and N. Sorensson, “An extensible SAT-solver,” in Proc. 6th International Conference on Theory and Applications of Satisfiability Testing, Santa Margherita Ligure, Italy, 2003, pp. 502–518.

A. P. Afanasiev, I. V. Bychkov, M. O. Manzyuk, M. A. Posypkin, A. A. Semenov and O. S. Zaikin, “Technology for Integrating Idle Computing Cluster Resources into Volunteer Computing Projects,” in Proc. of The 5th International Workshop on Computer Science and Engineering, Moscow, Russia, 2015, pp. 109-114.

M. Black and G. Bard, “SAT Over BOINC: An Application-Independent Volunteer Grid Project,” in Proc. 12th IEEE/ACM International Conference on Grid Computing, Lyon, France, 2011, pp. 226–227.

Y. Evtushenko, M. Posypkin and I. Sigal. “A framework for parallel large-scale global optimization,” Computer Science - Research and Development, vol. 23(3-4), pp. 211-215, 2009.


Refbacks

  • There are currently no refbacks.


Abava   FRUCT 2019

ISSN: 2307-8162