Geodesic
An evaluation of CPU vs. GPU performance of some combinatorial algorithms for cryptoanalysis
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 4 (2015) no. 3, pp. 67-84 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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 im-plementation 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.
Keywords: GPU, CUDA, cryptoanalysis, DPLL, SAT, SIMD. 
@article{VYURV_2015_4_3_a5,
     author = {V. G. Bulavintsev},
     title = {An evaluation of {CPU} vs. {GPU} performance of some combinatorial algorithms for cryptoanalysis},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a Vy\v{c}islitelʹna\^a matematika i informatika},
     pages = {67--84},
     year = {2015},
     volume = {4},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURV_2015_4_3_a5/}
}
TY  - JOUR
AU  - V. G. Bulavintsev
TI  - An evaluation of CPU vs. GPU performance of some combinatorial algorithms for cryptoanalysis
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
PY  - 2015
SP  - 67
EP  - 84
VL  - 4
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VYURV_2015_4_3_a5/
LA  - ru
ID  - VYURV_2015_4_3_a5
ER  - 
%0 Journal Article
%A V. G. Bulavintsev
%T An evaluation of CPU vs. GPU performance of some combinatorial algorithms for cryptoanalysis
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
%D 2015
%P 67-84
%V 4
%N 3
%U http://geodesic.mathdoc.fr/item/VYURV_2015_4_3_a5/
%G ru
%F VYURV_2015_4_3_a5
V. G. Bulavintsev. An evaluation of CPU vs. GPU performance of some combinatorial algorithms for cryptoanalysis. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 4 (2015) no. 3, pp. 67-84. http://geodesic.mathdoc.fr/item/VYURV_2015_4_3_a5/

[1] TOP500 Supercomputer Site, (data obrascheniya: 01.01.2015) http://www.top500.org

[2] V.W. Lee, C. Kim, J. Chhugani, M. Deisher, D. Kim, A.D. Nguyen, N. Satish, M. Smelyanskiy, S. Chennupaty, P. Hammarlund, R. Singhal, P. Dubey, “Debunking the 100X GPU vs. CPU myth: an evaluation of throughput computing on CPU and GPU”, ACM SIGARCH Computer Architecture News, 38:3 (2010), 451–460, ACM | DOI

[3] M. Flynn, “Some computer organizations and their effectiveness”, IEEE Transactions on Computers, 100:9 (1972), 948–960 | DOI | MR

[4] CUDA C Best Practices Guide—CUDA SDK v.6.0, , NVIDIA corp, 2014 (data obrascheniya: 15.07.2014) http://docs.nvidia.com/cuda

[5] C. Percival, S. Josefsson, The scrypt Password-Based Key Derivation Function, , IETF Draft, 2012 (data obrascheniya: 30.11.2012) http://tools.ietf.org/html/josefsson-scrypt-kdf-00.txt

[6] K. Nohl, Attacking phone privacy, , Black Hat USA, 2010 (data obrascheniya: 01.01.2015) https://srlabs.de/blog/wp-content/uploads/2010/07/Attacking.Phone_.Privacy_Karsten.Nohl_1.pdf

[7] I. Mironov, L. Zhang, “Applications of SAT solvers to cryptanalysis of hash functions”, Theory and Applications of Satisfiability Testing-SA, Springer, 2006, 102–115 | DOI | MR | Zbl

[8] A. Semenov, O. Zaikin, D. Bespalov, M. Posypkin, “Parallel logical cryptanalysis of the generator A5/1 in BNB-Grid system”, Parallel Computing Technologies, Springer, 2011, 473–483 | DOI

[9] A. Biryukov, A. Shamir, D. Wagner, “Real Time Cryptanalysis of A5/1 on a PC”, Fast Software Encryption, Springer, 2001, 1–18 | DOI | Zbl

[10] J.D. Golis, “Cryptanalysis of alleged A5 stream cipher”, Advances in Cryptology, EUROCRYPT-97, Springer, 1997, 239–255 | DOI

[11] S. Kumar, C. Paar, J. Pelzl, G. Pfeiffer, M. Schimmler, “Breaking ciphers with COPACOBANA — a cost-optimized parallel code breaker”, Cryptographic Hardware and Embedded Systems-CHE, Springer, 2006, 101–118 | DOI

[12] M. Kwan, Reducing the Gate Count of Bitslice DES, Cryptology ePrint Archive: Report 2000/051, 2000

[13] John the Ripper password cracker, , 2013 (data obrascheniya: 02.07.2014) http://www.openwall.com/john

[14] M. Davis, G. Logemann, D. Loveland, “A machine program for theorem-proving”, Communications of the ACM, 5:7 (1962), 394–397 | DOI | MR | Zbl

[15] M.W. Moskewicz, C.F. Madigan, Y. Zhao, L. Zhang, S. Malik, “Chaff: Engineering an efficient SAT solver”, Proceedings of the 38th annual Design Automation Conference, ACM, 2001, 530–535 | DOI

[16] J.P Marques-Silva, K.A. Sakallah, “GRASP: A search algorithm for propositional satisfiability”, IEEE Transactions on Computers, 48:5 (1999), 506–521 | DOI | MR

[17] R.D. Blumofe, C.E. Leiserson, “Scheduling multithreaded computations by work stealing”, Journal of the ACM, 46:5 (1999), 720–748 | DOI | MR | Zbl

[18] J. Backus, “Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs”, Communications of the ACM, 1978, no. 8, 613–641 | DOI | MR | Zbl

[19] D. Molka, D. Hackenberg, R. Schone, M.S. Muller, “Memory performance and cache coherency effects on an Intel Nehalem multiprocessor system”, 18th International Conference on Parallel Architectures and Compilation Techniques, IEEE, 2009, 261–270 | DOI

[20] N. Een, N. Sörensson, “MiniSat: A SAT solver with conflict-clause minimization”, Proceedings of the International Symposium on the Theory and Applications of Satisfiability Testing, v. 5, 2005, 55