Сравнение эффективности CPU и GPU реализаций некоторых комбинаторных алгоритмов на задачах обращения криптографических функций
Автор: Булавинцев Вадим Германович
Рубрика: Вычислительная математика
Статья в выпуске: 3 т.4, 2015 года.
Бесплатный доступ
Проводится сравнение эффективности CPU и GPU реализаций некоторых комбинаторных алгоритмов, используемых в криптоанализе. В частности, анализируются причины, по которым не удается эффективно реализовать на GPU алгоритмы, осуществляющие «интеллектуальный перебор». Показывается, что применение специальных техник трансформации потока управления позволяет существенно компенсировать потери производительности, возникающие из-за неэффективного исполнения условных переходов на SIMD-устройстве. Однако ограничения, которые накладывают механизмы работы с памятью, применяемые в современных GPU, для рассматриваемых алгоритмов оказываются непреодолимыми. В качестве тестовых задач рассматриваются задачи обращения криптографических функций DES и A5/1.
Криптоанализ
Короткий адрес: https://sciup.org/147160572
IDR: 147160572 | УДК: 004.272.32, | DOI: 10.14529/cmse150306
An evaluation of CPU vs. GPU performance of some combinatorial algorithms for cryptoanalysis
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.
Список литературы Сравнение эффективности CPU и GPU реализаций некоторых комбинаторных алгоритмов на задачах обращения криптографических функций
- 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. DOI: DOI: 10.1145/1816038.1816021
- Flynn, M. Some computer organizations and their effectiveness/M. Flynn//Computers, IEEE Transactions on. -1972. -Vol. 100, No. 9. -P. 948-960. DOI: DOI: 10.1109/tc.1972.5009071
- 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, 2006. -P. 102-115. DOI: DOI: 10.1007/11814948_13
- Semenov, A. Parallel logical cryptanalysis of the generator A5/1 in BNB-Grid system/A. Semenov et al.//Parallel Computing Technologies. -Springer, 2011. -P. 473-483. DOI: DOI: 10.1007/978-3-642-23178-0_43
- Biryukov, A. Real Time Cryptanalysis of A5/1 on a PC/A. Biryukov, A. Shamir, D. Wagner//Fast Software Encryption. -Springer, 2001. -P. 1-18. DOI: 10.1007/3-540-44706-7_1.
- Goliс, J.D. Cryptanalysis of alleged A5 stream cipher/J.D. Goliс//Advances in Cryptology-EUROCRYPT’97. -Springer, 1997. -P. 239-255. DOI: 0_17 DOI: 10.1007/3-540-69053-
- Kumar, S. Breaking ciphers with COPACOBANA -a cost-optimized parallel code breaker/S. Kumar et al.//Cryptographic Hardware and Embedded Systems-CHES 2006. -Springer, 2006. -P. 101-118. DOI: DOI: 10.1007/11894063_9
- 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. DOI: DOI: 10.1145/368273.368557
- 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. DOI: DOI: 10.1109/dac.2001.935565
- 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. DOI: DOI: 10.1109/12.769433
- 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. DOI: DOI: 10.1145/324133.324234
- 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. DOI: DOI: 10.1145/359576.359579
- 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. DOI: DOI: 10.1109/pact.2009.22
- 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.
