Yarrow algorithm

Last updated

The Yarrow algorithm is a family of cryptographic pseudorandom number generators (CPRNG) devised by John Kelsey, Bruce Schneier, and Niels Ferguson and published in 1999. 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

Contents

Yarrow was used in FreeBSD, but is now superseded by Fortuna. [1] Yarrow was also incorporated in iOS [2] and macOS for their /dev/random devices, but Apple has switched to Fortuna since 2020 Q1. [3]

Name

The name Yarrow alludes to the use of the yarrow plant in the random generating process of I Ching divination. Since the Xia dynasty (c.2070 to c.1600 BCE), Chinese have used yarrow stalks for divination. Fortunetellers divide a set of 50 yarrow stalks into piles and use modular arithmetic recursively to generate two bits of random information [4] that have a non-uniform distribution.

Principles

Yarrow's main design principles are: resistance to attacks, easy use by programmers with no cryptography background, and reusability of existing building blocks. The former widely used designs such as ANSI X9.17 and RSAREF 2.0 PRNG have loopholes that provide attack opportunities under some circumstances. Some of them are not designed with real-world attacks in mind. Yarrow also aims to provide easy integration, to enable system designers with little knowledge of PRNG functionality.

Design

Components

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

Yarrow accumulates 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 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 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 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 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 one-way hash function and a block cipher. The specific description and properties are listed in the table below.

AlgorithmsPropertiesWhat 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.

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

Functions for generation mechanism Functions for Generation Mechanism.png
Functions for generation mechanism

Yarrow-160 uses three-key Triple DES in counter mode to generate outputs. C is an n-bit counter value; 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 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 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, and for FreeBSD. The examples can be found in "An implementation of the Yarrow PRNG for FreeBSD" [5] by Mark R. V. Murray.

Pros and cons of Yarrow

Pros

Cons

Related Research Articles

Blowfish is a symmetric-key block cipher, designed in 1993 by Bruce Schneier and included in many cipher suites and encryption products. Blowfish provides a good encryption rate in software, and no effective cryptanalysis of it has been found to date. However, the Advanced Encryption Standard (AES) now receives more attention, and Schneier recommends Twofish for modern applications.

In cryptography, RC4 is a stream cipher. While it is remarkable for its simplicity and speed in software, multiple vulnerabilities have been discovered in RC4, rendering it insecure. It is especially vulnerable when the beginning of the output keystream is not discarded, or when nonrandom or related keys are used. Particularly problematic uses of RC4 have led to very insecure protocols such as WEP.

<span class="mw-page-title-main">Stream cipher</span> Type of symmetric key cipher

A stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream, to give a digit of the ciphertext stream. Since encryption of each digit is dependent on the current state of the cipher, it is also known as state cipher. In practice, a digit is typically a bit and the combining operation is an exclusive-or (XOR).

A key in cryptography is a piece of information, usually a string of numbers or letters that are stored in a file, which, when processed through a cryptographic algorithm, can encode or decode cryptographic data. Based on the used method, the key can be different sizes and varieties, but in all cases, the strength of the encryption relies on the security of the key being maintained. A key's security strength is dependent on its algorithm, the size of the key, the generation of the key, and the process of key exchange.

In cryptography, an initialization vector (IV) or starting variable is an input to a cryptographic primitive being used to provide the initial state. The IV is typically required to be random or pseudorandom, but sometimes an IV only needs to be unpredictable or unique. Randomization is crucial for some encryption schemes to achieve semantic security, a property whereby repeated usage of the scheme under the same key does not allow an attacker to infer relationships between segments of the encrypted message. For block ciphers, the use of an IV is described by the modes of operation.

In cryptography, a block cipher mode of operation is an algorithm that uses a block cipher to provide information security such as confidentiality or authenticity. A block cipher by itself is only suitable for the secure cryptographic transformation of one fixed-length group of bits called a block. A mode of operation describes how to repeatedly apply a cipher's single-block operation to securely transform amounts of data larger than a block.

A cryptographically secure pseudorandom number generator (CSPRNG) or cryptographic pseudorandom number generator (CPRNG) is a pseudorandom number generator (PRNG) with properties that make it suitable for use in cryptography. It is also loosely known as a cryptographic random number generator (CRNG).

Niels T. Ferguson is a Dutch cryptographer and consultant who currently works for Microsoft. He has worked with others, including Bruce Schneier, designing cryptographic algorithms, testing algorithms and protocols, and writing papers and books. Among the designs Ferguson has contributed to is the AES finalist block cipher algorithm Twofish as well as the stream cipher Helix and the Skein hash function.

<span class="mw-page-title-main">Cryptographic hash function</span> Hash function that is suitable for use in cryptography

A cryptographic hash function (CHF) is a hash algorithm that has special properties desirable for a cryptographic application:

<span class="mw-page-title-main">/dev/random</span> Pseudorandom number generator file in Unix-like operating systems

In Unix-like operating systems, /dev/random and /dev/urandom are special files that serve as cryptographically secure pseudorandom number generators. They allow access to environmental noise collected from device drivers and other sources. /dev/random typically blocks if there was less entropy available than requested; more recently it usually blocks at startup until sufficient entropy has been gathered, then unblocks permanently. The /dev/urandom device typically was never a blocking device, even if the pseudorandom number generator seed was not fully initialized with entropy since boot. Not all operating systems implement the same methods for /dev/random and /dev/urandom.

The security of cryptographic systems depends on some secret data that is known to authorized persons but unknown and unpredictable to others. To achieve this unpredictability, some randomization is typically employed. Modern cryptographic protocols often require frequent generation of random quantities. Cryptographic attacks that subvert or exploit weaknesses in this process are known as random number generator attacks.

Fortuna is a cryptographically secure pseudorandom number generator (PRNG) devised by Bruce Schneier and Niels Ferguson and published in 2003. It is named after Fortuna, the Roman goddess of chance. FreeBSD uses Fortuna for /dev/random and /dev/urandom is symbolically linked to it since FreeBSD 11. Apple OSes have switched to Fortuna since 2020 Q1.

<span class="mw-page-title-main">Random number generation</span> Producing a sequence that cannot be predicted better than by random chance

Random number generation is a process by which, often by means of a random number generator (RNG), a sequence of numbers or symbols that cannot be reasonably predicted better than by random chance is generated. This means that the particular outcome sequence will contain some patterns detectable in hindsight but impossible to foresee. True random number generators can be hardware random-number generators (HRNGs), wherein each generation is a function of the current value of a physical environment's attribute that is constantly changing in a manner that is practically impossible to model. This would be in contrast to so-called "random number generations" done by pseudorandom number generators (PRNGs), which generate numbers that only look random but are in fact pre-determined—these generations can be reproduced simply by knowing the state of the PRNG.

The Microsoft Windows platform specific Cryptographic Application Programming Interface is an application programming interface included with Microsoft Windows operating systems that provides services to enable developers to secure Windows-based applications using cryptography. It is a set of dynamically linked libraries that provides an abstraction layer which isolates programmers from the code used to encrypt the data. The Crypto API was first introduced in Windows NT 4.0 and enhanced in subsequent versions.

<span class="mw-page-title-main">One-way compression function</span> Cryptographic primitive

In cryptography, a one-way compression function is a function that transforms two fixed-length inputs into a fixed-length output. The transformation is "one-way", meaning that it is difficult given a particular output to compute inputs which compress to that output. One-way compression functions are not related to conventional data compression algorithms, which instead can be inverted exactly or approximately to the original data.

In cryptography, key stretching techniques are used to make a possibly weak key, typically a password or passphrase, more secure against a brute-force attack by increasing the resources it takes to test each possible key. Passwords or passphrases created by humans are often short or predictable enough to allow password cracking, and key stretching is intended to make such attacks more difficult by complicating a basic step of trying a single password candidate. Key stretching also improves security in some real-world applications where the key length has been constrained, by mimicking a longer key length from the perspective of a brute-force attacker.

CryptGenRandom is a deprecated cryptographically secure pseudorandom number generator function that is included in Microsoft CryptoAPI. In Win32 programs, Microsoft recommends its use anywhere random number generation is needed. A 2007 paper from Hebrew University suggested security problems in the Windows 2000 implementation of CryptGenRandom. Microsoft later acknowledged that the same problems exist in Windows XP, but not in Vista. Microsoft released a fix for the bug with Windows XP Service Pack 3 in mid-2008.

<span class="mw-page-title-main">Skein (hash function)</span> Cryptographic hash function

Skein is a cryptographic hash function and one of five finalists in the NIST hash function competition. Entered as a candidate to become the SHA-3 standard, the successor of SHA-1 and SHA-2, it ultimately lost to NIST hash candidate Keccak.

The following outline is provided as an overview of and topical guide to cryptography:

References

  1. "[base] Revision 284959". Svnweb.freebsd.org. Retrieved 18 October 2016.
  2. "iOS Security" (PDF). Apple.com. October 2012. Retrieved 2016-10-21.
  3. "Random number generation". Apple Support. Retrieved 2020-10-26.
  4. Schneier, Bruce. "Questions & Answers about Yarrow". Schneier on Security. Retrieved 2016-02-15. The fortuneteller would divide a set of 50 stalks into piles, then repeatedly use modular arithmetic to generate two random bits.
  5. "An implementation of the Yarrow PRNG for FreeBSD" . Retrieved 18 October 2016.
  6. Stevens, Marc; Bursztein, Elie; Karpman, Pierre; Albertini, Ange; Markov, Yarik (2017-02-23). "SHAttered". SHAttered. Retrieved 2017-04-27.
  7. "Fortuna Cryptographically Secure PRNG : AN0806 - Application Note" (PDF). Silabs.com. Retrieved 2016-10-21.
  8. citadel (4 March 2004). "Fortuna – A Cryptographically Secure Pseudo Random Number Generator – CodeProject" . Retrieved 18 October 2016.