Editing Yarrow algorithm (section)

==Design==

===Components===
The design of Yarrow consists of four major components: an [[Entropy (computing)|entropy]] accumulator, a [[Random seed|reseed]] mechanism, a generation mechanism, and reseed control.

Yarrow accumulates entropy into two pools: the fast pool, which provides frequent reseeds of the [[Unique key|key]] to keep the duration of key compromises as short as possible; the slow pool, which provides rare but conservative reseeds of the key. This makes sure that the reseed is secured even when the entropy estimates are very optimistic.

The reseed mechanism connects the entropy accumulator to the generating mechanism. Reseeding from the fast pool uses the current key and the [[Hash value|hash]] of all inputs to the fast pool since startup to generate a new key; reseeding from the slow pool behaves similarly, except it also uses the hash of all inputs to the slow pool to generate a new key. Both of the reseedings reset the entropy estimation of the fast pool to zero, but the last one also sets the estimation of the slow pool to zero. The reseeding mechanism updates the key constantly, so that even if the key of pool information is known to the attacker before the reseed, they will be unknown to the attacker after the reseed.

The reseed control component is leveraging between frequent reseeding, which is desirable but might allow [[#Iterative guessing attack|iterative guessing attacks]], and infrequent reseeding, which compromises more information for an attacker who has the key. Yarrow uses the fast pool to reseed whenever the source passes some threshold values, and uses the slow pool to reseed whenever at least two of its sources pass some other threshold value. The specific threshold values are mentioned in the [[#Yarrow-160|Yarrow-160]] section.

===Design philosophy===
Yarrow assumes that enough entropy can be accumulated to ensure that the PRNG is in an unpredictable state. The designers accumulate entropy in the purpose of keeping the ability to recover the PRNG even when the key is compromised. Similar design philosophy is taken by RSAREF, DSA and ANSI X9.17 PRNGs.

===Yarrow-160===
The Yarrow uses two important algorithms: a [[cryptographic hash function|one-way hash function]] and a [[block cipher]]. The specific description and properties are listed in the table below.
{| class="wikitable"
|-
! Algorithms !! Properties !! What Yarrow-160 uses
|-
| Hash function h(x) ||
* One-way
* m-bit output size
* collision intractable
Given {{var|M}} input values, the |M| selections of output values are uniformly distributed over ''m''-bit values. 
|| [[SHA-1]] hash function
|-
| Block cipher E() ||
*Resistant to known-plaintext and chosen-plaintext attacks
High statistical performance of outputs when given highly patterned inputs. 
|| Three-key [[Triple DES]]
|}

====Generation====
[[File:Functions for Generation Mechanism.png|thumb|Functions for generation mechanism]]
Yarrow-160 uses three-key [[Triple DES]] in counter mode to generate outputs. ''{{math|C}}'' is an ''n''-bit counter value; ''{{math|K}}'' is the key. In order to generate the next output block, Yarrow follows the functions shown here.

Yarrow keeps count of the output block, because once the key is compromised, the leak of the old output before the compromised one can be stopped immediately. Once some system security parameter ''{{math|P<sub>g</sub>}}'' is reached, the algorithm will generate ''{{math|k}}'' bits of PRNG output and use them as the new key. In Yarrow-160, the system security parameter is set to be ''10'', which means ''{{math|P<sub>g</sub> {{=}} 10}}''. The parameter is intentionally set to be low to minimize the number of outputs that can be backtracked.

====Reseed====
The reseed mechanism of Yarrow-160 uses SHA-1 and Triple DES as the hash function and block cipher. The details steps are in the original paper.

====Implementation of Yarrow-160====
Yarrow-160 has been implemented in [[Java (programming language)|Java]], and for [[FreeBSD]]. The examples can be found in "An implementation of the Yarrow PRNG for FreeBSD"<ref>{{cite web|url=https://www.usenix.org/legacy/events/bsdcon02/full_papers/murray/murray_html/|title=An implementation of the Yarrow PRNG for FreeBSD|access-date=18 October 2016}}</ref> by Mark R. V. Murray.