Advancing cryptanalytic methods through evolutionary computing
Project goals
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 cryptanalyst’s 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
cryptanalysiscryptographic algorithmdistinguishersecurityevolutionary computingoptimization
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 20 (SGA0201600001)
Main participants
Masarykova univerzita / Fakulta informatiky
Vysoké učení technické v Brně / Fakulta informačních technologiíContest type
VS - Public tender
Contract ID
16-08565S
Alternative language
Project name in Czech
Rozvoj kryptoanalytických metod prostřednictvím evolučních výpočtů
Annotation in Czech
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?
Scientific branches
Completed project evaluation
Provider evaluation
V - Vynikající výsledky projektu (s mezinárodním významem atd.)
Project results evaluation
The goals of the project were fulfilled. Several high quality publications were created. The results concern the field of cryptography, are directly applicable and will have a practical impact.
Solution timeline
Realization period - beginning
Jan 1, 2016
Realization period - end
Dec 31, 2018
Project status
U - Finished project
Latest support payment
Apr 26, 2018
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP19-GA0-GA-U/01:1
Data delivery date
Jun 12, 2019
Finance
Total approved costs
8,474 thou. CZK
Public financial support
7,188 thou. CZK
Other public sources
1,282 thou. CZK
Non public and foreign sources
0 thou. CZK
Recognised costs
8 474 CZK thou.
Public support
7 188 CZK thou.
0%
Provider
Czech Science Foundation
CEP
IN - Informatics
Solution period
01. 01. 2016 - 31. 12. 2018