FORK-256

From HandWiki
Short description: Hash algorithm


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

In 2005, Xiaoyun Wang announced an order-[math]\displaystyle{ 2^{63} }[/math] 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-[math]\displaystyle{ 2^{80} }[/math]) 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

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 [math]\displaystyle{ 2^{126.6} }[/math].[8] Mendel et al. (2006) independently derived a similar attack.[9] The following year Matusiewicz's team improved their attack to no worse than [math]\displaystyle{ 2^{108}, }[/math][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 [math]\displaystyle{ 2^{112.9} }[/math]-complexity attack again the improved algorithm.[7] By way of comparison, the eventual SHA-3 standard withstands up to an order-[math]\displaystyle{ 2^{128} }[/math] attack.[citation needed]

Deployment

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

  1. ↑ Wang, Xiaoyun; Yin, Yiqun Lisa; Yu, Hongbo (2005). "Finding Collisions in the Full SHA-1". Advances in Cryptology – CRYPTO 2005. Lecture Notes in Computer Science. 3621. pp. 17–36. doi:10.1007/11535218_2. ISBN 978-3-540-31870-5. 
  2. ↑ Schneier, Bruce (15 February 2005). "SHA-1 Broken". https://www.schneier.com/blog/archives/2005/02/sha1_broken.html. 
  3. ↑ Chen, Lily (25 April 2006). "NIST Comments on cryptanalytic attacks on SHA-1". http://csrc.nist.gov/groups/ST/hash/statement.html. 
  4. ↑ Chang, Shu-jen; Dworkin, Morris (2005). Workshop Report: The First Cryptographic Hash Workshop. Information Technology Laboratory, National Institute of Standards and Technology. http://csrc.nist.gov/groups/ST/hash/documents/HashWshop_2005_Report.pdf. 
  5. ↑ "SHA-3 Competition (2007–2012)". 31 March 2014. http://csrc.nist.gov/groups/ST/hash/sha-3/index.html. 
  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. Lecture Notes in Computer Science. 4047. pp. 195–209. doi:10.1007/11799313_13. ISBN 978-3-540-36598-3. 
  7. ↑ 7.0 7.1 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. 4859. Springer Berlin Heidelberg. pp. 10–17. doi:10.1007/978-3-540-77026-8_2. ISBN 978-3-540-77026-8. (Subscription content?)
  8. ↑ Matusiewicz, Krystian; Contini, Scott; Pieprzyk, Josef (2006). "Weaknesses of the FORK-256 compression function". IACR ePrint Archive. https://eprint.iacr.org/2006/317. 
  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. 4377. Springer Berlin Heidelberg. pp. 85–100. doi:10.1007/11967668_6. ISBN 978-3-540-69328-4. https://lirias.kuleuven.be/handle/123456789/228666. (Subscription content?)
  10. ↑ Matusiewicz, Krystian; Peyrin, Thomas; Billet, Olivier; Contini, Scott; Pieprzyk, Josef (2007). "Cryptanalysis of FORK-256". Fast Software Encryption. Lecture Notes in Computer Science. 4593. pp. 19–38. doi:10.1007/978-3-540-74619-5_2. ISBN 978-3-540-74619-5. (Subscription content?)
  11. ↑ Contini, Scott; Matusiewicz, Krystian; Pieprzyk, Josef (2007). "Extending FORK-256 Attack to the Full Hash Function". Information and Communications Security. Lecture Notes in Computer Science. 4861. Springer Berlin Heidelberg. pp. 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". IACR ePrint Archive. https://eprint.iacr.org/2007/185.pdf. 
  13. ↑ Lloyd, Jack (25 May 2010), Removing FORK-256, Botan-devel mailing list, http://lists.randombit.net/pipermail/botan-devel/2010-May/001123.html 




Retrieved from "https://handwiki.org/wiki/index.php?title=FORK-256&oldid=3365663"