SKLOIS (Pseudo) Preimage Attack on Reduced-Round Grøstl Hash Function and Others Shuang Wu, Dengguo Feng, Wenling Wu, Jian Guo, Le Dong, Jian Zou March 20, 2012 Institute. of Software, Chinese Academy of Sciences Institute for Infocomm Research, Singapore
Outline Introduction Attack on Grøstl Other results Conclusion 2
Introduction Meet-in-the-Middle pre-image attacks Applied to full MD4, MD5,HAVAL-3/4,Tiger and reduced-round HAS-160, RIPEMD, SHA-0/1, SHA-2 etc. Tricks: Splice and Cut Techniques Bicliques, Initial Structure (Message Stealing), local collision Partial-Matching (Relations between deterministic values) 3
Introduction Meet-in-the-Middle pre-image attacks Yu Sasaki proposed the MitM preimage attack on AESlike structures for the first time at FSE 2011 Target: Whirlpool and AES hash modes Use freedom degrees of the state for chunk separation 4
Outline Introduction Attack on Grøstl Other results Conclusion 5
Pseudo-Preimage Attack on 5-round Grøstl-256 Specification of Grøstl hash function Wide-pipe MD structure with output transformation Permutations P and Q are AES-like structures with 8 8 states(grøstl-256) and 8 16 states(grøstl-512) 10 rounds for Grøstl-256 and 14 rounds for Grøstl-512 M Q H i-1 P H i X P 6
Pseudo-Preimage Attack on 5-round Grøstl-256 Properties of the compression function 2n-bit state, F H, M = P H M Q M H With H = H M,F H, M = P HH H Q M M Bounds for generic attacks Pre-image attack: 2 n P HH H Q M M = T birthday attack on 2n-bit state Collision attack: 2 2n 3 P H 1 H 1 Q M 1 M 1 P H 2 H 2 Q M 2 M 2 = 0 generalized birthday attack on 2n-bit state with four entries M H i-1 Q P H i 7
Outline of the attack 8
Pseudo-Preimage Attack on 5-round Grøstl-256 Attack outline Pseudo pre-image (H,M) F H, M = X, P X X = T X is a pre-image of the output transformation With H = H M, P H H Q M M X = 0 M Q X X H P P T 9
Pseudo-Preimage Attack on 5-round Grøstl-256 How to convert the partial pre-images of P X X into pseudo pre-image of the hash function P H H Q M M X = 0 2 x 3 2n-b 2n 2 x 1 b 2 x 2 2n 2 x 1+x 2 +x 3 2n 1 x 1 + x 2 + x 3 2n Lookup table 2 2 x 1+x 2 +x 3 2n 2 x 1+x 2 b 2n b Lookup table 1 2n-b zero unknown 10
Pseudo-Preimage Attack on 5-round Grøstl-256 Complexity evaluation X: Fixed position partial preimage (n-bit) of P X X Let complexity to find one X be 2 C 1(2n,n) M: Randomly chosen message with padding Complexity=one Q call=1/2 compression function call H : Chosen position partial preimage (b-bit) of P H H Let complexity to find one H be 2 C 2(2n,b) 11
Pseudo-Preimage Attack on 5-round Grøstl-256 Overall complexity of the attack is 2 x 1+C 1 (2n,n) + 2 x 3+C 2 (2n,b) + 2 x 2 1 + 2 x 1+x 2 b C TT 2 x 2 1 (1 + C TT ) P H H Q M M X = 0 2 x 3 b 2n-b 2 x 2 2n 2 x 1 2n 2 x 3+C 2 (2n,b) Lookup table 2 Lookup table 1 2 x 1+C 1 (2n,n) 2 x 1+x 2 b b 2n-b 2 x 1+x 2 b C TT 2 x 1+x 2 +x 3 2n 2n 12
Partial preimage attacks on P X X 13
Pseudo-Preimage Attack on 5-round Grøstl-256 Evaluation of C 1 (2n, n) (fixed position partial preimage) Freedom degrees in blue and red bytes: 64 and 48 bits Size of the matching point: 64 bits Size of the full match: 256 bits Complexity: 2 207 P(X) calls = 2 206 compression function calls 14
Pseudo-Preimage Attack on 5-round Grøstl-256 Evaluation of C 2 (2n, b) (chosen position partial preimage) Note: we can choose the positions of the target zero bits Choose optimal positions to maximize the size of the matching point 15
Pseudo-Preimage Attack on 5-round Grøstl-256 Graphs of m(b) and C 2 (2n, b) for different b Grøstl-256 16
Pseudo-Preimage Attack on 5-round Grøstl-256 Overall complexity of pseudo-preimage attack on 5-round Grøstl-256 When b = 35, the overall complexity reaches its minimum value 2 244.85 17
Results on Grøstl-512 18
Pseudo-Preimage Attack on 8-round Grøstl-512 Preimage attack on the output transformation 19
Summary of results Algorithm Target Type Rounds Time Memory Source Grøstl-256 Grøstl-512 Hash Function Collision 3 2 64 - Compression Function Semi-Free-Start Collision 6 2 112 2 64 Permutation Distinguisher 9 2 368 2 64 Permutation Output Transformation Hash Function Zero-Sum Distinguisher 10 2 509 - Martin Schlæffer Martin Schlæffer Jérémy Jean et al. Christina Boura et al. Preimage 5 2 206 2 48 Ours Pseudo Preimage 5 2 244.85 2 230.13 Ours Hash Function Collision 3 2 192 - Compression Function Semi-Free-Start Collision Martin Schlæffer 7 2 152 2 56 Yu Sasaki Permutation Distinguisher 10 2 392 2 64 Output Transformation Hash Function Jérémy Jean et al. Preimage 8 2 495 2 16 Ours Pseudo Preimage 8 2 507.32 2 507.00 Ours 20
Outline Introduction Attack on Grøstl Other results Conclusion 21
Other results in this paper Algorithm Target Type Rounds Time Memory Source Hash Function 2 nd Preimage 5 2 504 2 8 Yu Sasaki Whirlpool Hash Function 2 nd Preimage 5 2 448 2 64 Ours Hash Function Preimage 5 2 481.5 2 64 Ours Algorithm Hash Mode Type Rounds Time Memory Message Length Source MMO,MP 2 nd Preimage 7 2 120 2 8 - Yu Sasaki AES MMO,MP,DM 2 nd Preimage 7 2 128 k 2 k 2 k blocks John Kelsey et at. MMO,MP,DM 2 nd Preimage 7 2 120 min (k,24) 2 16 2 k blocks Ours DM Preimage 7 2 125 2 8 - Yu Sasaki DM Preimage 7 2 122.7 2 16 >2 8 blocks Ours 22
New Related Result Announcement Converting partial pre-images into pseudo collisions The technique is proposed by Ji Li et al. Target: 8-round Grøstl-512 output transformation The complexity is 2 248 23
Outline Introduction Attack on Grøstl Other results Conclusion 24
Conclusion We proposed: Pseudo preimage attack on 5-round Grøstl-256 and 8- round Grøstl-512 for the first time We found that partial preimage attack on P X X (n-bit size) can be converted in to pseudo preimage attack on the hash function An interesting observation: Properties of the permutation Q are not concerned in this attack, i.e. this attack works with any Q. So, our attack works on Grøstl-256 with 5-round P and full 10-round Q and Grøstl-512 with 8-round P and full 14-round Q. M Q H i-1 P P H i 25
Thank you! Any questions? 26