Yarrow algorithm

The Yarrow algorithm is a family of cryptographic pseudorandom number generator (PRNG) devised by John Kelsey, Bruce Schneier and Niels Ferguson. The Yarrow algorithm is explicitly unpatented, royalty-free and open source; no license is required to use it. An improved design from Ferguson and Schneier, Fortuna, is described in their book, Practical Cryptography. Yarrow is incorporated in iOS and Mac OS X for their /dev/random devices. FreeBSD also used Yarrow for /dev/random, but phased it out in favor of Fortuna.

About the name

The name Yarrow is taken from the Yarrow plant. Since the Hsia dynasty, Chinese have been using Yarrow stalks for divination. The fortuneteller uses 50 Yarrow stalks into piles, and use modulo arithmetic recursively to generate two bits of random information that has a non-uniform distribution. The Yarrow algorithm is named after the Yarrow plant because of the random generating process in I Ching divination.

Principles

One of the most important principle of Yarrow is to make a PRNG that is better at resisting real-world attack. The former wildly used designs such as ANSI X9.17, RASREF 2.0 PRNG, have loopholes that provide attackers opportunities under some circumstances. Some of them are not intentionally designed to face real-world attacks. Another principle of Yarrow is that system designers with little knowledge about how the PRNG works can incorporate into their own real-world product fairly easily.

Design

Components

The design of Yarrow consists of four major components including an entropy accumulator, reseed mechanism, generation mechanism and reseed control.

Yarrow accumulate entropy into two pools: the fast pool, which provides frequent reseeds of the 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 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 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.

Reseed control component is leveraging between frequent reseeding, which is desirable but might cause iterative guessing attacks, and infrequent reseeding, which compromise more information for an attacker who has the key. Yarrow used the fast pool to reseed whenever the source passes some threshold values, and use the slow pool to reseed whenever at least two of its sources pass some other threshold value. The specific threshold values will be mentioned in the Yarrow-160 section.

Design philosophy

Yarrow assume that enough entropy can be accumulated to ensure that the PRNG is in an unpredictable state. The designers accumulate entropy in the purpose of keep 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 one-way hash function and a block cipher. The specific description and properties are listed under the table.

Algorithms	Properties	What Yarrow-160 uses
Hash function h(x)	• One-way • m-bit output size • collision intractable Given M input values, the |M| selections of output values are uniformly distributed over m-bit values.	SHA1 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

Yarrow-160 use three-key triple-DES in counter mode to generate outputs. C is n-bit counter value; K is the key. In order to generated the next output block, Yarrow follow the function

File:Functions for Generation Mechanism.png

Functions for Generation Mechanism

Yarrow keep count of the output block because once the key is compromised at some point, the leek of the old output before the compromised can be stopped immediately. Once some system security parameter Pg is reached, the algorithm will generate 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 Pg = 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 SHA1 and triple-DES as the hash function and block cipher. The details steps are in the original paper.

Implementation of Yarrow-160

Yarrow-160 can be implemented in JAVA, FreeBSD. The examples can be found in "An implementation of the Yarrow PRNG for FreeBSD" by Mark R. V. Murray.

Pros and cons of yarrow

Pros

• Yarrow reuses existing building blocks.

• Compare to other previous PRNGs, Yarrow is reasonably efficient.

• Yarrow can be used by programmer with no cryptography background in a reasonably secured way. Yarrow is portable and precisely defined. The interface is simple and clear. This somewhat decrease the chances of implementation errors.

• Yarrow was created using an attack oriented design process.

• The entropy estimation of Yarrow is very conservative, thus preventing exhaustive search attacks. It is very common that PRGNs fail in real-world applications because of entropy overestimation and guessable starting points.

• The reseeding process of Yarrow is relatively computationally-expensive, thus the cost of attempting to guess the PRNG’s key is higher.

• Yarrow uses functions to simplify the management of seed files, thus the files are constantly updated.

• To handle Cryptanalytic attacks, Yarrow is designed to be based on a secured block cipher. The level of security of the generation mechanism depends on the block cipher.

• Yarrow try to avoid data-dependent execution paths. This is done to prevent side-channel attacks such as timing attacks and power analysis. This is an improvement compare to PRNGs, for example RSAREF 2.0 PRNG, that will completely fall apart once additional information about the internal operations are no longer secured.

• Yarrow use cryptographic hash function to process input samples and then use a secure update function to combine the samples with the existing key. This makes sure that the attacker cannot easily manipulate the input samples. PRNGs such as RSAREF 2.0 PRNG does not have the ability to resist this kind of Chosen-Input attacks.

• Unlike ANSI X9.17 PRGN, Yarrow has the ability to recover from a key compromise. This means that even when the key is compromised, the attacker will not be able to predict future outputs forever. This is due to the reseeding mechanism of Yarrow.

• Yarrow has the entropy samples pool separated from the key, and only reseed the key when the entropy pool content is completely unpredictable. This design prevents the iterative guessing attacks, where an attacker with the key guess the next sample and check the result by observing the next output.

Cons

• Since the outputs of Yarrow are cryptographically derived, the systems that use those outputs can only be as secured as the generation mechanism itself. That means the attacker who can break the generation mechanism will easily break a system that depend on Yarrow’s outputs. This problem cannot be solved by increasing entropy accumulation.

• Yarrow requires entropy estimation, which is a very big challenge for implementation. It is hard to be sure how much entropy to collect before using it to reseed the PRNG. This problem is solved by Fortuna (PRNG), an improvement of Yarrow. Fortuna has 32 pools to collect entropy and removed the entropy estimator completely.

• Yarrow’s strength is limited by the size of the key. For example, Yarrow-160 has an effective key size of 160 bits. If the security requires 256 bit, Yarrow-160 is not capable of doing the job.

External links

• Yarrow algorithm page
• Yarrow-160: Notes on the Design and Analysis of the Yarrow Cryptographic Pseudorandom Number Generator, J. Kelsey, B. Schneier, and N. Ferguson
• "Yarrow implementation in Java"
• "Yarrow implementation in FreeBSD"
• "An implementation of the Yarrow PRNG for FreeBSD"