Paper 2018/799
Finding Ordinary Cube Variables for Keccak-MAC with Greedy Algorithm
Fukang Liu and Zhenfu Cao and Gaoli Wang
Abstract
In this paper, we introduce an alternative method to find ordinary cube variables for Keccak-MAC by making full use of the key-independent bit conditions. First, we select some potential candidates for ordinary cube variables by properly adding key-independent bit conditions, which do not multiply with the chosen conditional cube variables in the first two rounds. Then, we carefully determine the ordinary cube variables from the candidates to establish the conditional cube tester with an approach inspired from the greedy algorithm. Finally, based on our new method to recover the 128-bit key, the conditional cube attack on 7-round Keccak-MAC-128/256/384 is improved to $2^{71}$ and 6-round Keccak-MAC-512 can be attacked with at most $2^{40}$ calls to 6-round Keccak internal permutation. It should be emphasized that our new approach does not require sophisticated modeling nor usage of a solver.
Note: 1. Correct two mistakes for Keccak-MAC-512, i.e. two bit conditions on $A_{\theta}^{0}[3][3][20]$ and $A_{\theta}^{0}[3][4][21]$). 2. Provide the source code to verify our discovered 32-dimensional cube with fewer key-independent bit conditions. 3. Add a section to introduce our tracing algorithm in a formal way. 4. Add a subsection to introduce cube tester and conditional cube tester. 5. Some minor corrections such as Figures and statements.
Metadata
- Available format(s)
- Publication info
- Preprint. MINOR revision.
- Keywords
- KeccakKeccak-MACordinary cube variablesconditional cube attackcube tester
- Contact author(s)
- liufukangs @ 163 com
- History
- 2019-05-30: last of 12 revisions
- 2018-09-01: received
- See all versions
- Short URL
- https://ia.cr/2018/799
- License
-
CC BY