FORK-256

From Wikipedia, the free encyclopedia
Jump to: navigation, search

FORK-256 is a hash algorithm designed in response to security issues discovered in the earlier SHA-1 and MD5 algorithms. After substantial cryptanalysis, the algorithm is considered broken.

Background[edit]

In 2005, Xiaoyun Wang announced an order-2^{63} collision attack on the government's hash standard SHA-1.[1][2] The National Institute of Standards and Technology (NIST), the body responsible for setting cryptographic standards in the United States, concluded this was a practical attack (as previous estimates were order-2^{80}) and began encouraging additional research into hash functions and their weaknesses.[3] As part of this effort, NIST hosted two workshops where potential new algorithms, including FORK-256, were introduced and discussed.[4] Rather than immediately select any of these algorithms, NIST conducted a public competition from 2007–2012 which ultimately resulted in the Keccak algorithm being selected for use as the SHA-3 standard.[5]

Algorithm and Analysis[edit]

FORK-256 was introduced at the 2005 NIST Hash workshop and published the following year.[6] FORK-256 uses 512-bit blocks and implements preset constants that change after each repetition. Each block is hashed into a 256-bit block through four branches that divides each 512 block into sixteen 32-bit words that are further encrypted and rearranged.

The initial algorithm garnered significant cryptanalysis, summarized in (Saarinen 2007).[7] Matusiewicz et al. (2006) discovered a collision attack with complexity of 2^{126.6}.[8] Mendel et al. (2006) independently derived a similar attack.[9] The following year Matusiewicz's team improved their attack to no worse than 2^{108},[10] and (Contini 2007) demonstrated a practical implementation of the attack.[11]

In response to these attacks, Hong and his team proposed an improved version of FORK-256.[12] Markku-Juhani Saarinen derived a 2^{112.9}-complexity attack again the improved algorithm.[7] By was of comparison, the eventual SHA-3 standard withstands up to an order-2^{128} attack.[citation needed]

Deployment[edit]

FORK-256 was added to the Botan cryptographic library after its introduction. Botan developer Jack Lloyd removed the algorithm in 2010 after concluding the hash suffered from several weaknesses and had never become widely used.[13]

References[edit]

  1. ^ Wang, Xiaoyun; Yin, Yiqun Lisa; Yu, Hongbo (2005). "Finding Collisions in SHA-1". Advances in Cryptology (CRYPTO). Lecture Notes in Computer Science 3621: 17–36. doi:10.1007/11535218_2. ISBN 978-3-540-31870-5. (subscription required)
  2. ^ Schneier, Bruce (15 February 2005). "SHA-1 Broken". Schneier on Security. 
  3. ^ Chen, Lily (25 April 2006). "NIST Comments on cryptanalytic attacks on SHA-1". NIST Computer Security Division. 
  4. ^ Chang, Shu-jen; Dworkin, Morris (2005). "Workshop Report: The First Cryptographic Hash Workshop" (PDF). Information Technology Laboratory, National Institute of Standards and Technology. 
  5. ^ "SHA-3 Competition (2007–2012)". National Institute of Standards and Technology, Computer Security Division. 31 March 2014. 
  6. ^ Hong, Deukjo; Chang, Donghoon; Sung, Jaechul; Lee, Sangjin; Hong, Seokhie; Lee, Jaesang; Moon, Dukjae; Chee, Sungtaek (2006). "A New Dedicated 256-Bit Hash Function: FORK-256". Fast Software Encryption, 13th International Workshop. Lecture Notes in Computer Science 4047: 195–209. doi:10.1007/11799313_13. ISBN 978-3-540-36598-3. 
  7. ^ a b Saarinen, Markku-Juhani (2007). "A Meet-in-the-Middle Collision Attack Against the New FORK-256". Progress in Cryptology (INDOCRYPT 2007). Lecture Notes in Computer Science (Springer Berlin Heidelberg) 4859: 10–17. doi:10.1007/978-3-540-77026-8_2. ISBN 978-3-540-77026-8. (subscription required)
  8. ^ Matusiewicz, Krystian; Contini, Scott; Pieprzyk, Josef (2006). "Weaknesses of the FORK-256 compression function". IACR Eprint archive. 
  9. ^ Mendel, Florian; Lano, Joseph; Preneel, Bart (2006). "Cryptanalysis of Reduced Variants of the FORK-256 Hash Function". Topics in Cryptology (CT-RSA 2007). Lecture Notes in Computer Science (Springer Berlin Heidelberg) 4377: 85–100. doi:10.1007/11967668_6. ISBN 978-3-540-69328-4. (subscription required)
  10. ^ Matusiewicz, Krystian; Peyrin, Thomas; Billet, Olivier; Contini, Scott; Pieprzyk, Josef (2007). "Cryptanalysis of FORK-256". Fast Software Encryption (14th International Workshop). Lecture Notes in Computer Science 4593: 19–38. doi:10.1007/978-3-540-74619-5_2. ISBN 978-3-540-74619-5. (subscription required)
  11. ^ Contini, Scott; Matusiewicz, Krystian; Pieprzyk, Josef (2007). "Extending FORK-256 Attack to the Full Hash Function". Information and Communications Security (9th International Conference (ICICS). Lecture Notes in Computer Science (Springer Berlin Heidelberg) 4861: 296–305. doi:10.1007/978-3-540-77048-0_23. ISBN 978-3-540-77048-0. 
  12. ^ Hong, Deukjo; Chang, Donghoon; Sung, Jaechul; Lee, Sangjin; Hong, Seokhie; Lee, Jesang; Moon, Dukjae; Chee, Sungtaek (2007). "New FORK-256" (PDF). IACR Eprint archive. 
  13. ^ Lloyd, Jack (25 May 2010), Removing FORK-256, Botan-devel mailing list