FORK-256

In 2005, Xiaoyun Wang announced an order-$2^\{63\}$ collision attack on the government's hash standard SHA-1. 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. As part of this effort, NIST hosted two workshops where potential new algorithms, including FORK-256, were introduced and discussed. 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.

FORK-256 was introduced at the 2005 NIST Hash workshop and published the following year. 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). Matusiewicz et al. (2006) discovered a collision attack with complexity of $2^\{126.6\}$. Mendel et al. (2006) independently derived a similar attack. The following year Matusiewicz's team improved their attack to no worse than $2^\{108\},$ and (Contini 2007) demonstrated a practical implementation of the attack.

In response to these attacks, Hong and his team proposed an improved version of FORK-256. Markku-Juhani Saarinen derived a $2^\{112.9\}$-complexity attack again the improved algorithm. By way of comparison, the eventual SHA-3 standard withstands up to an order-$2^\{128\}$ attack.{{citation needed|date=August 2014}}

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.

{{reflist | refs=

{{cite book| last1=Wang | first1=Xiaoyun | last2=Yin | first2=Yiqun Lisa |author2-link= Yiqun Lisa Yin | last3=Yu | first3=Hongbo | title=Advances in Cryptology – CRYPTO 2005 | chapter=Finding Collisions in the Full SHA-1 | year=2005 | series=Lecture Notes in Computer Science | volume=3621 | pages=17–36 | doi=10.1007/11535218_2 | isbn=978-3-540-31870-5 }}{{subscription required}}

{{cite web | last=Schneier | first=Bruce | url=https://www.schneier.com/blog/archives/2005/02/sha1_broken.html | website=Schneier on Security | title=SHA-1 Broken | date=15 February 2005}}

{{cite web | last=Chen | first=Lily | title=NIST Comments on cryptanalytic attacks on SHA-1 | url=http://csrc.nist.gov/groups/ST/hash/statement.html | website=NIST Computer Security Division | date=25 April 2006}}

{{cite journal | last1=Chang | first1=Shu-jen | last2=Dworkin | first2=Morris | title=Workshop Report: The First Cryptographic Hash Workshop | publisher=Information Technology Laboratory, National Institute of Standards and Technology | url=http://csrc.nist.gov/groups/ST/hash/documents/HashWshop_2005_Report.pdf | date=2005}}

{{citation | last=Lloyd | first=Jack | date=25 May 2010 | url=http://lists.randombit.net/pipermail/botan-devel/2010-May/001123.html | publisher=Botan-devel mailing list | title=Removing FORK-256}}

{{cite web | url=http://csrc.nist.gov/groups/ST/hash/sha-3/index.html | website=National Institute of Standards and Technology, Computer Security Division | title=SHA-3 Competition (2007–2012) | date=31 March 2014}}

{{cite book | series=Lecture Notes in Computer Science | last1=Hong | first1=Deukjo | last2=Chang | first2=Donghoon | last3=Sung | first3=Jaechul | last4=Lee | first4=Sangjin | last5=Hong | first5=Seokhie | last6=Lee | first6=Jaesang | last7=Moon | first7=Dukjae | last8=Chee | first8=Sungtaek | title=Fast Software Encryption | chapter=A New Dedicated 256-Bit Hash Function: FORK-256 | volume=4047 | isbn=978-3-540-36598-3 | doi=10.1007/11799313_13 | pages=195–209 | year=2006}}

{{cite book | series=Lecture Notes in Computer Science | volume=4859 | year=2007 | pages=10–17 | last=Saarinen | first=Markku-Juhani | title=Progress in Cryptology – INDOCRYPT 2007 | chapter=A Meet-in-the-Middle Collision Attack Against the New FORK-256 | doi=10.1007/978-3-540-77026-8_2 | isbn=978-3-540-77026-8 | publisher=Springer Berlin Heidelberg | citeseerx=10.1.1.62.5191 }}{{subscription required}}

{{cite journal | title=Weaknesses of the FORK-256 compression function | journal=IACR ePrint Archive | year=2006 | last1=Matusiewicz | first=Krystian | last2=Contini | first2=Scott | last3=Pieprzyk | first3=Josef | url=https://eprint.iacr.org/2006/317 }}

{{cite book | series=Lecture Notes in Computer Science | pages=85–100 | last1=Mendel | first1=Florian | last2=Lano | first2=Joseph | last3=Preneel | first3=Bart | title=Topics in Cryptology – CT-RSA 2007 | chapter=Cryptanalysis of Reduced Variants of the FORK-256 Hash Function | year=2006 | doi=10.1007/11967668_6 | isbn=978-3-540-69328-4 | volume=4377 | publisher=Springer Berlin Heidelberg| url=https://lirias.kuleuven.be/handle/123456789/228666 }}{{subscription required}}

{{cite book | series=Lecture Notes in Computer Science | volume=4593 | year=2007 | pages=19–38 | last1=Matusiewicz | first1=Krystian | last2=Peyrin | first2=Thomas | last3=Billet | first3=Olivier | last4=Contini | first4=Scott | last5=Pieprzyk | first5=Josef | title=Fast Software Encryption | chapter=Cryptanalysis of FORK-256 | doi=10.1007/978-3-540-74619-5_2 | isbn=978-3-540-74619-5}}{{subscription required}}

{{cite journal | last1=Hong | first1=Deukjo | last2=Chang | first2=Donghoon | last3=Sung | first3=Jaechul | last4=Lee | first4=Sangjin | last5=Hong | first5=Seokhie | last6=Lee | first6=Jesang | last7=Moon | first7=Dukjae | last8=Chee | first8=Sungtaek | title=New FORK-256 | journal=IACR ePrint Archive | year=2007 | url=https://eprint.iacr.org/2007/185.pdf}}

{{cite book | series=Lecture Notes in Computer Science | volume=4861 | year=2007 | last1=Contini | first1=Scott | last2=Matusiewicz | first2=Krystian | last3=Pieprzyk | first3=Josef | title=Information and Communications Security | chapter=Extending FORK-256 Attack to the Full Hash Function | pages=296–305 | doi=10.1007/978-3-540-77048-0_23 | isbn=978-3-540-77048-0 | publisher= Springer Berlin Heidelberg| s2cid=15215802 }}

}}

{{DEFAULTSORT:Fork-256}}

Category:Cryptographic hash functions

{{crypto-stub}}