ISAAC (cipher)

From Wikipedia, the free encyclopedia

ISAAC is a pseudorandom number generator designed by Bob Jenkins (1996) to be cryptographically secure. The name is an acronym for Indirection, Shift, Accumulate, Add, and Count.[1]

Contents

[edit] Operation

The ISAAC algorithm has similarities to RC4. It uses an array of 256 4-byte integers (called mm) as the internal state, writing the results to another 256-integer array, from which they are read one at a time until empty, at which point they are recomputed. The computation consists of altering mm[i] with mm[i^128], two elements of mm found by indirection, an accumulator, and a counter, for all values of i from 0 to 255. Since it only takes about 19 32-bit operations for each 32-bit output word, it is extremely fast on 32-bit computers.

[edit] Cryptanalysis

Cryptanalysis has been undertaken by Marina Pudovkina (2001)[2]. Her attack can recover the initial state with a complexity that is approximated to be less than the time needed for searching through the square root of all possible initial states. In practice this means that the attack needs 4.67 \times 10^{1240} instead of 102466. This result has had no practical impact on the security of ISAAC. As always with cryptographic primitives, future improvements, or another attack, might.

In 2006 Jean-Philippe Aumasson discovered several sets of weak states[3]. The fourth presented (and smallest) set of weak states leads to a highly biased output for the first round of ISAAC and allows the derivation of the internal state, similar to a weakness in RC4. He also shows that a previous attack[4] is not relevant, since based on an erroneous algorithm. An improved version of ISAAC is proposed, called ISAAC+.

[edit] References

  1. ^ Robert J. Jenkins Jr., ISAAC. Fast Software Encryption 1996, pp41–49.
  2. ^ Marina Pudovkina, A known plaintext attack on the ISAAC keystream generator, 2001, Cryptology ePrint Archive: Report 2001/049, [1].
  3. ^ Jean-Philippe Aumasson, On the pseudo-random generator ISAAC.Cryptology ePrint archive, report 2006/438, 2006.
  4. ^ Souradyuti Paul, Bart Preneel, On the (In)security of Stream Ciphers Based on Arrays and Modular Addition.Asiacrypt 2006.


[edit] External links

Stream ciphers
v  d  e
Algorithms: A5/1 | A5/2 | FISH | Grain | HC-256 | ISAAC | MUGI | Panama | Phelix | Pike | Py | Rabbit | RC4 | Salsa20 | Scream | SEAL | SOBER | SOBER-128 | SOSEMANUK | Trivium | VEST | WAKE
Theory: Shift register | LFSR | NLFSR | Shrinking generator   Standardization: eSTREAM
Cryptography
v  d  e
History of cryptography | Cryptanalysis | Cryptography portal | Topics in cryptography
Symmetric-key algorithm | Block cipher | Stream cipher | Public-key cryptography | Cryptographic hash function | Message authentication code | Random numbers