Сравнение эффективности CPU и GPU реализаций некоторых комбинаторных алгоритмов на задачах обращения криптографических функций

Вадим Германович Булавинцев

Аннотация


Проводится сравнение эффективности CPU и GPU реализаций некоторых комбинаторных алгоритмов, используемых в криптоанализе. В частности, анализируются причины, по которым не удается эффективно реализовать на GPU алгоритмы, осуществляющие «интеллектуальный перебор». Показывается, что применение специальных техник трансформации потока управления позволяет существенно компенсировать потери производительности, возникающие из-за неэффективного исполнения условных переходов на SIMD-устройстве. Однако ограничения, которые накладывают механизмы работы с памятью, применяемые в современных GPU, для рассматриваемых алгоритмов оказываются непреодолимыми. В качестве тестовых задач рассматриваются задачи обращения криптографических функций DES и A5/1.

Ключевые слова


GPU, CUDA, криптоанализ, DPLL, SAT, SIMD

Полный текст:

PDF

Литература


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




DOI: http://dx.doi.org/10.14529/cmse150306