Optimizing Fast Near Collision Attack on Grain Using Linear Programming
| Autor: | Yueping Wu, Senshan Pan, Liangmin Wang |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
Key-recovery attack
General Computer Science Linear programming time-memory-data tradeoff attacks Computer science General Engineering Phase (waves) stream ciphers near collision Reduction (complexity) Cryptanalysis Collision attack General Materials Science eSTREAM State (computer science) lcsh:Electrical engineering. Electronics. Nuclear engineering grain Algorithm Time complexity lcsh:TK1-9971 |
| Zdroj: | IEEE Access, Vol 7, Pp 181191-181201 (2019) |
| ISSN: | 2169-3536 |
| Popis: | In 2018, an attack named fast-near-collision attack (FNCA) was proposed, which is an improved version of near-collision attack (NCA) on Grain-v1, one of the three hardware-oriented finalists of the eSTREAM project. FNCA is designed as a key recovery attack and takes a divide-and-conquer strategy that needs a merging phase. We propose an improved FNCA where the merging phase is optimized by a linear programming based strategy. It decreases the candidates of the internal state vectors (ISVs) in each step of merging and has a reduction in the overall time complexity. Since the merging phase is vital for a divide-and-conquer strategy, where the most of bits of the full internal state are recovered, other analyses on Grain family with FNCA can get optimized by our method in varying degrees. This paper offers an experiment on a reduced Grain and a theoretical analysis on Grain-v1 to confirm the results. In the case of the reduced Grain of an 80-bit internal state, the time complexity is 237.1096, which has a 27.8% reduction. For Grain-v1, its theoretical time complexity is around 273.4, which is reduced by 79.4% compared with the original one. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|