An evaluation of CPU vs. GPU performance оf some combinatorial algorithms for cryptoanalysis
DOI:
https://doi.org/10.14529/cmse150306Keywords:
GPU, CUDA, cryptoanalysis, DPLL, SAT, SIMDAbstract
In this work we assess performance of CPU and GPU implementations of some widely-used cryptanalytic combinatorial algorithms. In particular, we analyze obstacles for effective GPU implementation of “smart” combinatorial algorithms. Next, to alleviate performance problems arising from inefficient processing of conditional expressions in SIMD-devices we devise some special control flow graph transformation techniques. Finally, we demonstrate that contemporary GPU’s memory access schemes are incompatible with typical memory access patterns of “smart” combinatorial algorithms studied. We use DES and A5/1 cryptographic functions as test cases.
References
TOP500 Supercomputer Site URL:http://www.top500.org (дата обращения: 01.01.2015)
Lee, V. W. Debunking the 100X GPU vs. CPU myth: an evaluation of throughput computing on CPU and GPU / V. W. Lee et al //ACM SIGARCH Computer Architecture News. — ACM, 2010. — Vol. 38, No. 3. — P. 451–460.
Flynn, M. Some computer organizations and their effectiveness / M. Flynn // Computers, IEEE Transactions on. — 1972. — Vol. 100, No. 9 — P. 948–960.
CUDA C Best Practices Guide — CUDA SDK v.6.0 — NVIDIA corp. — 2014. URL: http://docs.nvidia.com/cuda (дата обращения: 15.07.2014)
Percival, C. The scrypt Password-Based Key Derivation Function. — IETF Draft — 2012 / C. Percival, S. Josefsson URL: http://tools.ietf.org/html/josefsson-scrypt-kdf-00.txt (дата обращения: 30.11.2012)
Nohl, K. Attacking phone privacy / K. Nohl // Black Hat USA. — 2010. URL: https://srlabs.de/blog/wp-content/uploads/2010/07/Attacking.Phone_.Privacy_Karsten.Nohl_1.pdf (дата обращения: 01.01.2015)
Mironov, I. Applications of SAT solvers to cryptanalysis of hash functions / I. Mironov, L. Zhang // Theory and Applications of Satisfiability Testing-SAT 2006. — Springer Berlin Heidelberg, 2006. — P. 102–115.
Semenov, A. Parallel logical cryptanalysis of the generator A5/1 in BNB-Grid system / A. Semenov et al // Parallel Computing Technologies. — Springer Berlin Heidelberg, 2011. — P. 473–483.
Biryukov, A. Real Time Cryptanalysis of A5/1 on a PC / A. Biryukov, A. Shamir , D. Wagner // Fast Software Encryption. — Springer Berlin Heidelberg, 2001. — P. 1–18.
Goliс, J. D. Cryptanalysis of alleged A5 stream cipher / J. D. Goliс // Advances in Cryptology—EUROCRYPT’97. — Springer Berlin Heidelberg, 1997. — P. 239–255.
Kumar, S. Breaking ciphers with COPACOBANA—a cost-optimized parallel code breaker / S. Kumar et al. // Cryptographic Hardware and Embedded Systems-CHES 2006. — Springer Berlin Heidelberg, 2006. — P. 101–118.
Kwan, M. Reducing the Gate Count of Bitslice DES / M. Kwan //IACR Cryptology ePrint Archive. — 2000. — Vol. 2000. — P. 51.
John the Ripper password cracker — 2013 URL: http://www.openwall.com/john/ (дата обращения: 02.07.2014)
Davis, M. A machine program for theorem-proving / M. Davis, G. Logemann, D. Loveland // Communications of the ACM. — 1962. — Vol. 5, No. 7. — P. 394–397.
Moskewicz, M. W. Chaff: Engineering an efficient SAT solver / M. W. Moskewicz et al. //Proceedings of the 38th annual Design Automation Conference. — ACM, 2001. — P. 530–535.
Marques-Silva, J. P. GRASP: A search algorithm for propositional satisfiability / J. P Marques-Silva, K. A. Sakallah // Computers, IEEE Transactions on. — 1999. — Vol. 48, No. 5. — P. 506–521.
Blumofe, R. D. Scheduling multithreaded computations by work stealing / R. D. Blumofe, C. E. Leiserson //Journal of the ACM (JACM). — 1999. — Vol. 46, No. 5. — P. 720–748.
Backus, J. Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs / J. Backus // Communications of the ACM. — 1978. — Vol. 21, No. 8. — P. 613–641.
Molka, D. Memory performance and cache coherency effects on an Intel Nehalem multiprocessor system / D. Molka et al. // PACT'09. 18th International Conference on Parallel Architectures and Compilation Techniques. — IEEE, 2009. — P. 261–270.
Een, N. MiniSat: A SAT solver with conflict-clause minimization / N. Een, N. Sörensson // Proceedings of the International Symposium on the Theory and Applications of Satisfiability Testing (2005) — 2005. — Vol. 5 — P.55
