Editing ISAAC (cipher)

{{Short description|Cryptographic number generator}}
'''ISAAC''' ('''indirection, shift, accumulate, add, and count''') is a [[cryptographically secure pseudorandom number generator]] and a [[stream cipher]] designed by [[Robert John Jenkins Junior|Robert J. Jenkins Jr.]] in 1993.<ref>Robert J. Jenkins Jr., ISAAC. Fast Software Encryption 1996, pp. 41&ndash;49.</ref> The [[reference implementation]] [[source code]] was dedicated to the [[public domain]].<ref>[http://rosettacode.org/wiki/The_ISAAC_Cipher The ISAAC Cipher]</ref>

"I developed (...) tests to break a generator, and I developed the generator to pass the tests. The generator is ISAAC."<ref>{{Cite web |last=Jenkins |first=Bob |date=2023-03-17 |title=Tests for Random Number Generators |url=https://www.burtleburtle.net/bob/rand/testsfor.html }}</ref>

== Operation ==

The ISAAC [[algorithm]] has similarities with [[RC4]]. It uses an [[Array data structure|array]] of 256 four-octet [[Integer (computer science)|integers]] as the internal state, writing the results to another 256 four-octet integer array, from which they are read one at a time until empty, at which point they are recomputed. The computation consists of altering ''i''-element with (''i''⊕128)-element, two elements of the state array 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 very fast on 32-bit computers.

== Cryptanalysis ==

[[Cryptanalysis]] has been undertaken by Marina Pudovkina (2001).<ref>Marina Pudovkina, A known plaintext attack on the ISAAC keystream generator, 2001, Cryptology ePrint Archive: Report 2001/049, [http://eprint.iacr.org/2001/049/].</ref> 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 <math>4.67 \times 10^{1240}</math> instead of <math>10^{2466}</math>. This result has had no practical impact on the security of ISAAC.<ref name=":0">{{cite web|title=On the pseudo-random generator ISAAC|url=https://eprint.iacr.org/2006/438.pdf|publisher=Cryptology ePrint Archive|access-date=21 August 2016}}</ref>

In 2006 Jean-Philippe Aumasson discovered several sets of weak states.<ref>Jean-Philippe Aumasson, [http://eprint.iacr.org/2006/438 On the pseudo-random generator ISAAC]. Cryptology ePrint archive, report 2006/438, 2006.</ref> 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 [[Fluhrer, Mantin and Shamir attack|weakness in RC4]]. It is not clear if an attacker can tell from just the output whether the generator is in one of these weak states or not. He also shows that a previous attack<ref>Souradyuti Paul, Bart Preneel, On the (In)security of Stream Ciphers Based on Arrays and Modular Addition.Asiacrypt 2006.</ref> is flawed, since the [[Souradyuti Paul|Paul]]-[[Bart Preneel|Preneel]] attack is based on an erroneous algorithm rather than the real ISAAC.
An improved version of ISAAC is proposed, called ISAAC+.<ref name=":0" />

== Usage outside cryptography ==

Many implementations of ISAAC are so fast that they can compete with other high speed PRNGs, even with those designed primarily for speed not for security. Only a few other generators of such high quality and speed exist in usage.{{citation needed|date=March 2023}}
ISAAC is used in the Unix tool [[shred (Unix)|shred]] to securely overwrite data.<ref>[http://git.savannah.gnu.org/cgit/coreutils.git/tree/gl/lib/rand-isaac.c GNU coreutils git]</ref>,

Also, ISAAC algorithm is implemented in Java Apache Commons Math library.<ref>{{Cite web |url=https://commons.apache.org/proper/commons-math/javadocs/api-3.4/org/apache/commons/math3/random/ISAACRandom.html |title=Apache Commons Math reference |access-date=2022-02-16 |archive-date=2022-02-16 |archive-url=https://web.archive.org/web/20220216084357/https://commons.apache.org/proper/commons-math/javadocs/api-3.4/org/apache/commons/math3/random/ISAACRandom.html |url-status=dead }}</ref>, and in [[NetHack]] for its RNG.<ref>{{Cite web |title=NetHack/src/isaac64.c at NetHack-3.7 · NetHack/NetHack |url=https://github.com/NetHack/NetHack/blob/NetHack-3.7/src/isaac64.c |access-date=2025-02-10 |website=GitHub |language=en}}</ref>

== References ==
{{reflist|30em}}

== External links ==
* [http://www.burtleburtle.net/bob/rand/isaacafa.html Official ISAAC website]
* [http://rosettacode.org/wiki/The_ISAAC_Cipher Multiple ISAAC implementations at Rosetta Code]
* [https://web.archive.org/web/20130208031625/http://www.wolfgang-ehrhardt.de/misc_en.html#prng  Pascal/Delphi port]
* [https://metacpan.org/pod/Math::Random::ISAAC Math::Random::ISAAC], a Perl module implementation of the algorithm
* [https://github.com/rubycon/isaac.js isaac.js], a JavaScript implementation
{{Cryptography navbox | stream}}

{{DEFAULTSORT:Isaac (Cipher)}}
[[Category:Cryptographically secure pseudorandom number generators]]
[[Category:Stream ciphers]]
[[Category:Public-domain software with source code]]