Project detail

Advancing cryptanalytic methods through evolutionary computing

Duration: 01.01.2016 — 31.12.2018

Funding resources

Czech Science Foundation - Standardní projekty

- whole funder (2016-01-01 - 2018-12-31)

On the project

Kryptografické algoritmy obvykle procházejí rozsáhlým testováním experty, kteří posuzují jejich bezpečnost. V našem projektu navrhujeme (částečně) nahradit tuto pracnou činnost automatizováním počátečních fází analýzy. Náš přístup je postaven na automatickém generování rozlišovačů", které hledají nechtěné statistické defekty ve výstupu algoritmu. Rozlišovač konstruujeme s použitím evolučních algoritmů (genetického programování) ve formě logické funkce s více výstupy. Již jsme prokázali, že náš přístup vede ke slibným výsledkům porovnatelnými se současnými technikami testování. Náš přístup konstruuje rozlišovač automaticky a adaptivně s ohledem na výstup testovaného algoritmu. To otevírá nové možnosti na nalezení takových potenciálních slabin v kryptografických algoritmech, které zůstaly skryty před statistickými testy nebo i zraky kryptoanalytika. Náš projekt cílí na zodpovězení dvou stěžejních otázek v oblasti bezpečnosti kryptografických algoritmů: (1) Je něco špatně s kryptografickým algoritmem? (2) Co je špatně v návrhu algoritmu?

Description in English
Cryptographic algorithms usually go through elaborate testing by skilled experts who assert their overall security. We suggest to partly replace such extensive human labour by automating initial parts of such analyses. We base our approach on automatically generated "distinguishers" that show undesired statistical anomalies in an algorithm output. We design a distinguisher in the form of a multiple-output logic function, using evolutionary algorithms (genetic programming). We show that such approach leads to promising results comparable to the state-of-the-art testing. Our approach builds a distinguisher automatically and adaptively to the evaluated algorithm output. This opens up new possibilities for discovering those potential weaknesses in cryptographic algorithms that remained hidden from statistical tests and cryptanalysts sights. Our research will aim to answer two crucial questions of atmost importance when considering an algorithm security: (1) Is there anything wrong with a crypto algorithm? (2) What is wrong in the algorithm design? 

Keywords
kryptoanalýza; kryptografický algoritmus; rozlišovač; bezpečnost; evoluční výpočty; optimalizace

Key words in English
cryptanalysis; cryptographic algorithm; distinguisher; security; evolutionary computing; optimization

Mark

GA16-08565S

Default language

Czech

People responsible

Dobai Roland, Ing., Ph.D. - fellow researcher
Grochol David, Ing., Ph.D. - fellow researcher
Matyáš Václav, Dr. - principal person responsible

Units

Department of Computer Systems
- co-beneficiary (2015-03-20 - 2018-12-31)
Faculty of Informatics MU
- beneficiary (2015-03-20 - 2018-12-31)

Results

DOBAI, R.; KOŘENEK, J.; SEKANINA, L. Adaptive Development of Hash Functions in FPGA-Based Network Routers. In 2016 IEEE Symposium Series on Computational Intelligence. Athens: IEEE Computational Intelligence Society, 2016. p. 1-8. ISBN: 978-1-5090-4240-1.
Detail

KIDOŇ, M.; DOBAI, R. Evolutionary design of hash functions for IP address hashing using genetic programming. In 2017 IEEE Congress on Evolutionary Computation (CEC). San Sebastian: Institute of Electrical and Electronics Engineers, 2017. p. 1720-1727. ISBN: 978-1-5090-4601-0.
Detail

GROCHOL, D.; SEKANINA, L. Multiobjective Evolution of Hash Functions for High Speed Networks. In Proceedings of the 2017 IEEE Congress on Evolutionary Computation. San Sebastian: IEEE Computer Society, 2017. p. 1533-1540. ISBN: 978-1-5090-4600-3.
Detail

MRÁZEK, V.; SEKANINA, L.; DOBAI, R.; SÝS, M.; ŠVENDA, P. Efficient On-Chip Randomness Testing Utilizing Machine Learning Techniques. IEEE Trans. on VLSI Systems., 2019, vol. 27, no. 12, p. 2734-2744. ISSN: 1063-8210.
Detail

GROCHOL, D.; SEKANINA, L. Multi-Objective Evolution of Ultra-Fast General-Purpose Hash Functions. In European Conference on Genetic Programming. Lecture Notes in Computer Science. Berlin: Springer International Publishing, 2018. p. 187-202. ISBN: 978-3-319-77553-1.
Detail

MRÁZEK, V.; SÝS, M.; VAŠÍČEK, Z.; SEKANINA, L.; MATYÁŠ, V. Evolving Boolean Functions for Fast and Efficient Randomness Testing. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '18). Kyoto: Association for Computing Machinery, 2018. p. 1302-1309. ISBN: 978-1-4503-5618-3.
Detail

HUSA, J.; DOBAI, R. Designing Bent Boolean Functions With Parallelized Linear Genetic Programming. In GECCO Companion '17 Proceedings of the Companion Publication of the 2017 on Genetic and Evolutionary Computation Conference. Berlín: Association for Computing Machinery, 2017. p. 1825-1832. ISBN: 978-1-4503-4939-0.
Detail

Responsibility: Matyáš Václav, Dr.