| Autor: |
Alexander Semenov, Kirill Antonov, Stepan Kochemazov, Artem Pavlenko |
| Jazyk: |
angličtina |
| Rok vydání: |
2023 |
| Předmět: |
|
| Zdroj: |
IEEE Access, Vol 11, Pp 120319-120333 (2023) |
| Druh dokumentu: |
article |
| ISSN: |
2169-3536 |
| DOI: |
10.1109/ACCESS.2023.3328215 |
| Popis: |
In this paper we describe a class of cryptographic guess-and-determine attacks which is based on the notion of a linearizing set. A linearizing set-based attack is applied to a system of Multivariate Quadratic equations (MQ) over $GF(2)$ field, which encodes how a considered cryptographic function works. By substituting into such MQ system a random (in some strict sense) assignment of variables from a linearizing set we aim to transform the system into a linear one. We introduce a probability of such an event and call it a probability of linearization. Then we describe a guess-and-determine attack, the hardness of which can be expressed via a probability of linearization. To estimate the latter it is possible to use a simple Monte Carlo algorithm. Also we describe a technique that allows to augment a considered MQ system by new linear equations and to construct a new MQ system, for which the probability of linearization is usually larger than that for an original one. For this purpose we apply a SAT oracle to a Boolean formula that is naturally associated with a considered MQ system. Finally, we reduce the problem of searching for a linearizing set that yields the best effectiveness of a constructed guess-and-determine attack to a pseudo-Boolean optimization problem, which can be solved using metaheuristic optimization algorithms. The important consequence of this is that this way we can construct guess-and-determine attacks automatically by solving the corresponding optimization problem. In the computational experiments we used the proposed methodology to construct attacks on several well-known stream ciphers. The runtime estimations of some of the attacks make it possible to implement them in reasonable time. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
