View source for FORK-256

{{Short description|Hash algorithm}}
{{Orphan|date=October 2016}}

'''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, [[Wang Xiaoyun|Xiaoyun Wang]] announced an order-<math>2^{63}</math> [[collision attack]] on the government's hash standard [[SHA-1]].<ref name=Wang2005/><ref name=Schneier2005/>  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>2^{80}</math>) and began encouraging additional research into hash functions and their weaknesses.<ref name=Chen2006/>  As part of this effort, NIST hosted two workshops where potential new algorithms, including FORK-256, were introduced and discussed.<ref name=Chang2005/>  Rather than immediately select any of these algorithms, NIST conducted a public competition from 2007&ndash;2012 which ultimately resulted in the Keccak algorithm being selected for use as the [[SHA-3]] standard.<ref name=NIST1/>

==Algorithm and Analysis==
FORK-256 was introduced at the 2005 NIST Hash workshop and published the following year.<ref name=Hong2006/> FORK-256 uses 512-bit [[Block (telecommunications)|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).<ref name=Saarinen2007/>  Matusiewicz ''et al.'' (2006) discovered a [[collision attack]] with [[Computational complexity theory|complexity]] of <math>2^{126.6}</math>.<ref name=Matusiewicz2006/> Mendel ''et al.'' (2006) independently derived a similar attack.<ref name=Mendel2006/>  The following year Matusiewicz's team improved their attack to no worse than <math>2^{108},</math><ref name=Matusiewicz2007/> and (Contini 2007) demonstrated a practical implementation of the attack.<ref name=Contini2007/>

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

==Deployment==
FORK-256 was added to the [[Botan (programming library)|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.<ref name=Botan/>

==References==
{{reflist | refs=
<ref name=Wang2005>{{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&ndash;36 | doi=10.1007/11535218_2 | isbn=978-3-540-31870-5 }}{{subscription required}}</ref>

<ref name=Schneier2005>{{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}}</ref>

<ref name=Chen2006>{{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}}</ref>

<ref name=Chang2005>{{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}}</ref>

<ref name=Botan>{{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}}</ref>

<ref name=NIST1>{{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&ndash;2012) | date=31 March 2014}}</ref>

<ref name=Hong2006>{{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&ndash;209 | year=2006}}</ref>

<ref name=Saarinen2007>{{cite book | series=Lecture Notes in Computer Science | volume=4859 | year=2007 | pages=10&ndash;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}}</ref>

<ref name=Matusiewicz2006>{{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 }}</ref>

<ref name=Mendel2006>{{cite book | series=Lecture Notes in Computer Science | pages=85&ndash;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}}</ref>

<ref name=Matusiewicz2007>{{cite book | series=Lecture Notes in Computer Science | volume=4593 | year=2007 | pages=19&ndash;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}}</ref>

<ref name=Hong2007>{{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}}</ref>

<ref name=Contini2007>{{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&ndash;305 | doi=10.1007/978-3-540-77048-0_23 | isbn=978-3-540-77048-0 | publisher= Springer Berlin Heidelberg| s2cid=15215802 }}</ref>
}}

{{DEFAULTSORT:Fork-256}}
[[Category:Cryptographic hash functions]]


{{crypto-stub}}