Fitness comparison by statistical testing in construction of SAT-based guess-and-determine cryptographic attacks

Artem Pavlenko, Maxim Buzdalov, Vladimir Ulyantsev

Allbwn ymchwil: Pennod mewn Llyfr/Adroddiad/Trafodion CynhadleddTrafodion Cynhadledd (Nid-Cyfnodolyn fathau)

8 Dyfyniadau(SciVal)

Crynodeb

Algebraic cryptanalysis studies breaking ciphers by solving algebraic equations. Some of the promising approaches use SAT solvers for this purpose. Although the corresponding satisfiability problems are hard, their difficulty can often be lowered by choosing a set of variables to brute force over, and by solving each of the corresponding reduced problems using a SAT solver, which is called the guess-and-determine attack. In many successful cipher breaking attempts this set was chosen analytically, however, the nature of the problem makes evolutionary computation a good choice.

We investigate one particular method for constructing guess-and-determine attacks based on evolutionary algorithms. This method estimates the fitness of a particular guessed bit set by Monte-Carlo simulations. We show that using statistical tests within the comparator of fitness values, which can be used to reduce the necessary number of samples, together with a dynamic strategy for the upper limit on the number of samples, speeds up the attack by a factor of 1.5 to 4.3 even on a distributed cluster.
Iaith wreiddiolSaesneg
TeitlGECCO '19
Is-deitlProceedings of the Genetic and Evolutionary Computation Conference
GolygyddionManuel López-Ibáñez
Tudalennau312-320
Nifer y tudalennau9
Dynodwyr Gwrthrych Digidol (DOIs)
StatwsCyhoeddwyd - 13 Gorff 2019
Cyhoeddwyd yn allanolIe
DigwyddiadGECCO 2019: The Genetic and Evolutionary Computation Conference - Prague, Y Weriniaeth Tsiec
Hyd: 13 Gorff 201917 Gorff 2019
https://gecco-2019.sigevo.org

Cynhadledd

CynhadleddGECCO 2019: The Genetic and Evolutionary Computation Conference
Gwlad/TiriogaethY Weriniaeth Tsiec
DinasPrague
Cyfnod13 Gorff 201917 Gorff 2019
Cyfeiriad rhyngrwyd

Ôl bys

Gweld gwybodaeth am bynciau ymchwil 'Fitness comparison by statistical testing in construction of SAT-based guess-and-determine cryptographic attacks'. Gyda’i gilydd, maen nhw’n ffurfio ôl bys unigryw.

Dyfynnu hyn