ºÝºÝߣ

ºÝºÝߣShare a Scribd company logo

Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 family

?
?
Alexandra
Alexandra

Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 family by Dmitry Khovratovich, Christian Rechberger, Alexandra Savelieva. Presented at 19th International Workshop on Fast Software Encryption - FSE 2012 (March 2012, Washington DC)

1 of 24
Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 family Dmitry Khovratovich1 Christian Rechberger2 Alexandra Savelieva3 1 Microsoft Research Redmond, USA 2 DTU MAT, Denmark 3 National Research University Higher School of Economics, Russia 19th International Workshop on Fast Software Encryption - FSE 2012 March 19-21, 2012
Recent Progress in Preimage Attacks ¨C MD4, MD5, and Tiger 2010 2009 Guo, Ling, Rechberger, and Wang. Advanced meet-in-the-middle 2008 Sasaki, Aoki: Finding preimage attacks: First Preimages in Full MD5 results on full Tiger, and Faster Than Exhaustive improved results on Sasaki and Aoki. Search. EUROCRYPT MD4 and SHA-2. Preimage attacks on 2009 ASIACRYPT'10 step-reduced MD5. ACISP'08. Introduction of Initial Structure Introduction of Splice-and-Cut Framework 2
Recent Progress in Preimage Attacks ¨C SHA-x Family 2010 2009 Guo, Ling, Rechberger, and Wang. Advanced meet-in-the-middle 2008 Aoki and Sasaki. Meet- preimage attacks: First in-the-middle preimage results on full Tiger, and attacks against reduced improved results on SHA-0 and SHA-1. MD4 and SHA-2. CRYPTO'09. ASIACRYPT'10. Introduction of Initial Structure Introduction of Splice-and-Cut Framework 3
Problem ? Concrete examples of the initial structure are extremely sophisticated and hard to generalize. ? Many ad-hoc / not formalized techniques are used to build initial structures ? While the other elements of splice-and-cut framework seem exhausted already, the concept behind initial structure has large potential and few boundaries. 4
Purpose of our Research ? To replace the idea of the initial structure with a more formal and generic concept ? To design generic algorithms for constructing the initial structure ? To reduce manual efforts and time to build the initial structure 5
Preimage Attacks ? Preimage attack on hash function. ? Given h, find M: H(M) = f (M; IV ) = h ? For an n-bit ideal hash function: complexity 2n ? Pseudo-preimage attack on compression function. ? Given h, find M and CV: f (M; CV) = h. ? For an n-bit ideal compression function: complexity 2n. ? Pseudo-preimage attacks yielding preimages ? If a pseudo-preimage for the n-bit compression function is constructed in time 2x , x < n - 2, then the full preimage can be found in time 21+(n+x)/2 . 6
New attacks on Skein-512 and the SHA-2 family Reference Target Steps Complexity, 2x Memory Pseudo- Second Preimage preimage preimage Our results Skein-512 22 508 511 - 26 Our results Skein-512 37 511.2 - - 264 Our results Skein-512 72 - 511.7 - Negl. Aoki et.al.¡¯09 SHA-256 43 251.9 254.9 254.9 26 Our results SHA-256 45 253 255.5 255.5 26 Our results SHA-256 52 255 - - 26 Aoki et.al.¡¯09 SHA-512 46 509 511.5 511.5 26 Our results SHA-512 50 509 511.5 511.5 24 Our results SHA-512 57 511 - - 26 7
Hash Functions with Merkle- Damg?rd Structure ? M is arbitrarily long ? Iterative design ? H(M) = f (M [s]; CV [s] ) ? CV[i+1] = f (M [i]; CV [i] ) 8
Compression Functions in Davies- Meier Mode ? Blockcipher-based compression function: f (M; CV) = EM(CV) ? CV; ? where E is a block cipher keyed with scheduled input M 9
Splice-and-Cut Attacks: Basic Strategy 10
Partial Matching and ~ Fixing 11
Initial Structure 12
Biclique ¨C Formal Definition 13
Biclique of dimension 2 in the MITM attack on a DM compression function 14
How it works ? Suppose message M[1,3] is a preimage
Advantage ? The complexity of testing 22d messages for preimages: C = 2d(Cbackward + Cforward) + Cbicl [+ Crecheck ] ? One needs 2n-2d bicliques of dimension d to test 2n preimage candidates. 16
Differential Perspective on Bicliques ? Vast pool of already existing tools when it comes to finding differential trails in hash functions ? Very precise and economic use of degrees of freedom in the resulting attacks 17
Biclique Construction Algorithms # Main idea Application Attacks 1 Fully specified or Bicliques of Reduced Skein truncated arbitrary hash function differential trails dimension 2 Modification of For the case when Reduced Algorithm 1 for we control internal SHA-2 hash hash functions in state and message and DM mode injections within compression the biclique functions 3 Use rebound For bicliques of Reduced Skein approach to get dimension 1 compression 18 more rounds function
Number of Attacked SHA-2 Hash Function Rounds - Our Improvements Hash Chunks Partial Partial Initial Total function matching fixing structure SHA-256 29 7 3 4+2 43+2 SHA-512 29 7 8 2+4 46+4 ? Compared to: ? Aoki, Guo, Matusiewicz, Sasaki, and Wang. Preimages for step-reduced SHA-2. In ASIACRYPT¡¯09. 19
Summary of Our Contributions ? Formalization of Initial Structure technique as a ¡®Biclique¡¯ ? 3 generic and flexible algorithms for constructing bicliques ? differential perspective that allows for application of differential trails, message modification techniques etc. in splice-and-cut framework ? SHA-2 family ? attack on 45-round SHA-256 and 50-round SHA-512 in the hash mode ? attack on 52-round SHA-256 and 57-round SHA-512 compression function ? SHA-3 finalist Skein ? attack on 22 rounds of Skein-512 hash function 20 ? attack on 37 rounds of Skein-512 compression function ? MITM speed-up of brute force attack on 72 rounds of Skein-512
Results in Perspective ? We targeted a main security property, not some artificial distinguishing property. ? We have results on the real hash, not some pseudo-attacks, or results that only work with full access to compression function, cipher or permutation 21
Follow-up Work ? Biclique Cryptanalysis of the Full AES by Bogdanov, Khovratovich, and Rechberger (2011) - First application to block ciphers ? A Meet-in-the-Middle Attack on the Full KASUMI by Jia, Yu, and Wang (2011) - Exploits a new property of the cipher ? Narrow Bicliques: Cryptanalysis of Full IDEA by Khovratovich, Leurent, and Rechberger (2012) - Variants of attacks that are many million times faster than brute-force ? Even more results on: SQUARE (by Mala, 2011), IDEA (by Biham, Dunkelman, Keller, and Shamir, 2011), and ARIA (by Chen and Xu, 2012) 22
Future Work ? Application of the Biclique framework to other hash functions and block ciphers ? Generalization of the Biclique technique, e.g. identifying situations where a graph can be used that deviates from the Biclique definition. ? New design criteria for hash-functions based on their ability to resist meet-in-the-middle attacks 23
Questions? Dmitry Khovratovich Christian Rechberger Alexandra Savelieva 24

More Related Content

Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 family

  • 1. Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 family Dmitry Khovratovich1 Christian Rechberger2 Alexandra Savelieva3 1 Microsoft Research Redmond, USA 2 DTU MAT, Denmark 3 National Research University Higher School of Economics, Russia 19th International Workshop on Fast Software Encryption - FSE 2012 March 19-21, 2012
  • 2. Recent Progress in Preimage Attacks ¨C MD4, MD5, and Tiger 2010 2009 Guo, Ling, Rechberger, and Wang. Advanced meet-in-the-middle 2008 Sasaki, Aoki: Finding preimage attacks: First Preimages in Full MD5 results on full Tiger, and Faster Than Exhaustive improved results on Sasaki and Aoki. Search. EUROCRYPT MD4 and SHA-2. Preimage attacks on 2009 ASIACRYPT'10 step-reduced MD5. ACISP'08. Introduction of Initial Structure Introduction of Splice-and-Cut Framework 2
  • 3. Recent Progress in Preimage Attacks ¨C SHA-x Family 2010 2009 Guo, Ling, Rechberger, and Wang. Advanced meet-in-the-middle 2008 Aoki and Sasaki. Meet- preimage attacks: First in-the-middle preimage results on full Tiger, and attacks against reduced improved results on SHA-0 and SHA-1. MD4 and SHA-2. CRYPTO'09. ASIACRYPT'10. Introduction of Initial Structure Introduction of Splice-and-Cut Framework 3
  • 4. Problem ? Concrete examples of the initial structure are extremely sophisticated and hard to generalize. ? Many ad-hoc / not formalized techniques are used to build initial structures ? While the other elements of splice-and-cut framework seem exhausted already, the concept behind initial structure has large potential and few boundaries. 4
  • 5. Purpose of our Research ? To replace the idea of the initial structure with a more formal and generic concept ? To design generic algorithms for constructing the initial structure ? To reduce manual efforts and time to build the initial structure 5
  • 6. Preimage Attacks ? Preimage attack on hash function. ? Given h, find M: H(M) = f (M; IV ) = h ? For an n-bit ideal hash function: complexity 2n ? Pseudo-preimage attack on compression function. ? Given h, find M and CV: f (M; CV) = h. ? For an n-bit ideal compression function: complexity 2n. ? Pseudo-preimage attacks yielding preimages ? If a pseudo-preimage for the n-bit compression function is constructed in time 2x , x < n - 2, then the full preimage can be found in time 21+(n+x)/2 . 6
  • 7. New attacks on Skein-512 and the SHA-2 family Reference Target Steps Complexity, 2x Memory Pseudo- Second Preimage preimage preimage Our results Skein-512 22 508 511 - 26 Our results Skein-512 37 511.2 - - 264 Our results Skein-512 72 - 511.7 - Negl. Aoki et.al.¡¯09 SHA-256 43 251.9 254.9 254.9 26 Our results SHA-256 45 253 255.5 255.5 26 Our results SHA-256 52 255 - - 26 Aoki et.al.¡¯09 SHA-512 46 509 511.5 511.5 26 Our results SHA-512 50 509 511.5 511.5 24 Our results SHA-512 57 511 - - 26 7
  • 8. Hash Functions with Merkle- Damg?rd Structure ? M is arbitrarily long ? Iterative design ? H(M) = f (M [s]; CV [s] ) ? CV[i+1] = f (M [i]; CV [i] ) 8
  • 9. Compression Functions in Davies- Meier Mode ? Blockcipher-based compression function: f (M; CV) = EM(CV) ? CV; ? where E is a block cipher keyed with scheduled input M 9
  • 11. Partial Matching and ~ Fixing 11
  • 13. Biclique ¨C Formal Definition 13
  • 14. Biclique of dimension 2 in the MITM attack on a DM compression function 14
  • 15. How it works ? Suppose message M[1,3] is a preimage
  • 16. Advantage ? The complexity of testing 22d messages for preimages: C = 2d(Cbackward + Cforward) + Cbicl [+ Crecheck ] ? One needs 2n-2d bicliques of dimension d to test 2n preimage candidates. 16
  • 17. Differential Perspective on Bicliques ? Vast pool of already existing tools when it comes to finding differential trails in hash functions ? Very precise and economic use of degrees of freedom in the resulting attacks 17
  • 18. Biclique Construction Algorithms # Main idea Application Attacks 1 Fully specified or Bicliques of Reduced Skein truncated arbitrary hash function differential trails dimension 2 Modification of For the case when Reduced Algorithm 1 for we control internal SHA-2 hash hash functions in state and message and DM mode injections within compression the biclique functions 3 Use rebound For bicliques of Reduced Skein approach to get dimension 1 compression 18 more rounds function
  • 19. Number of Attacked SHA-2 Hash Function Rounds - Our Improvements Hash Chunks Partial Partial Initial Total function matching fixing structure SHA-256 29 7 3 4+2 43+2 SHA-512 29 7 8 2+4 46+4 ? Compared to: ? Aoki, Guo, Matusiewicz, Sasaki, and Wang. Preimages for step-reduced SHA-2. In ASIACRYPT¡¯09. 19
  • 20. Summary of Our Contributions ? Formalization of Initial Structure technique as a ¡®Biclique¡¯ ? 3 generic and flexible algorithms for constructing bicliques ? differential perspective that allows for application of differential trails, message modification techniques etc. in splice-and-cut framework ? SHA-2 family ? attack on 45-round SHA-256 and 50-round SHA-512 in the hash mode ? attack on 52-round SHA-256 and 57-round SHA-512 compression function ? SHA-3 finalist Skein ? attack on 22 rounds of Skein-512 hash function 20 ? attack on 37 rounds of Skein-512 compression function ? MITM speed-up of brute force attack on 72 rounds of Skein-512
  • 21. Results in Perspective ? We targeted a main security property, not some artificial distinguishing property. ? We have results on the real hash, not some pseudo-attacks, or results that only work with full access to compression function, cipher or permutation 21
  • 22. Follow-up Work ? Biclique Cryptanalysis of the Full AES by Bogdanov, Khovratovich, and Rechberger (2011) - First application to block ciphers ? A Meet-in-the-Middle Attack on the Full KASUMI by Jia, Yu, and Wang (2011) - Exploits a new property of the cipher ? Narrow Bicliques: Cryptanalysis of Full IDEA by Khovratovich, Leurent, and Rechberger (2012) - Variants of attacks that are many million times faster than brute-force ? Even more results on: SQUARE (by Mala, 2011), IDEA (by Biham, Dunkelman, Keller, and Shamir, 2011), and ARIA (by Chen and Xu, 2012) 22
  • 23. Future Work ? Application of the Biclique framework to other hash functions and block ciphers ? Generalization of the Biclique technique, e.g. identifying situations where a graph can be used that deviates from the Biclique definition. ? New design criteria for hash-functions based on their ability to resist meet-in-the-middle attacks 23
  • 24. Questions? Dmitry Khovratovich Christian Rechberger Alexandra Savelieva 24