2
$\begingroup$

Is there a way of getting the nth random number from a particular seed run in ISAAC? i.e. one day run a selection of 256 numbers and the next day run from the 256th number to get the next 256 random numbers? I presume no as I haven't been able to and I've tried everything I can think of but there may be a mathematical solution.

$\endgroup$
  • $\begingroup$ Seems somewhat off-topic. I guess you mean something other than the obvious solution of saving and restoring the context. $\endgroup$ – gammatester Jun 1 '17 at 14:53
  • $\begingroup$ Yes, if possible. Sorry, didn't know it would be off topic. $\endgroup$ – Bipman Jun 1 '17 at 14:57
3
$\begingroup$

No, that won't work, and we don't even need to assume anything about the security of ISAAC to prove that. A simple counting argument is sufficient.

Basically, the internal state of the ISAAC cipher consists of slightly over one kilobyte of data (consisting of an array of 256 32-bit integers initialized using the key/seed, plus three additional 32-bit values that don't depend on the seed). On each call to the isaac() function, this internal state is mixed in a somewhat complicated way, and also used to compute a kilobyte of pseudorandom keystream output (also represented as an array of 256 32-bit integers).

The important part here is that, in order to compute the next kilobyte of output, you need to know the entire kilobyte of internal state. While the output of ISAAC does not directly expose this internal state, in principle it might be possible for an attacker with unlimited computing power to reconstruct the whole internal state from the previous kilobyte (or more) of the output. However, if you only have a single 32-bit integer of the output, then there's no way to do that even in principle — there are many, many possible internal states that could've produced those 32 bits of output, and each of those states will yield a different further keystream.

Now, there's one notable exception to this: if you know that ISAAC was seeded poorly, so that there are less than $2^{32}$ distinct possible seed values, then you can simply try each of these seeds and see which one produces the same 256th output integer that you observed. This is because the entire ISAAC internal state is initially generated based on the seed input, so that a limited number of possible seeds implies an equally limited number of possible states.

(Note that, depending on the number of possible seeds, you might get more than one match, but probably not too many more. In particular, for $n$ possible seeds, the expected number of coincidental extra matches is $\lambda = n/2^{32}$, and the actual number of extra matches observed is approximately Poisson distributed with rate $\lambda$. This distribution is not specific to ISAAC in any way; any sufficiently random-looking map from $n$ possible inputs to $2^{32}$ possible observed outputs will have approximately the same statistical behavior.)

| improve this answer | |
$\endgroup$
2
$\begingroup$

No.

ISAAC ins't the most popular random number generator /cipher system, but as far as current evidence goes, it is considered unbroken and safe for cryptographic use. This might change though when we all start using it for serious stuff, and enough academic manpower is focused on it.

If you look at all the array cell swapping and bit shifting, it's very much akin to repetitive hashing. You can see the similarly to a cryptographic hash:-

 x = state[i];
        acc ^= acc >>> 16;
        acc += state[j++];
        state[i] = y = state[(x & MASK) >> 2] + acc + lastResult;
        results[i++] = lastResult = state[((y >> SIZEL) & MASK) >> 2] + x;

A close parallel to what you're asking is can you predict the next 32 bytes of a SHA-256 hash output, whilst knowing the previous set. Not yet. Whilst hash inversions faster than via brute forces have been found for some hashes, there is no such shortcut yet for ISAAC.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Understood. Thinking about it again it would be a serious issue if we could ! But then again, I never thought it would be possible to say what the nth digit of pi would be without calculating all the others. $\endgroup$ – Bipman Jun 1 '17 at 16:13
  • $\begingroup$ @Bipman Ah ha! But consider the huge summations in the BBP formula. It's logarithmic in complexity so just try to calculate the billionth value of pi using your watch calculator. Nature doesn't give you something for nothing. Also consider that BBP probably exists because nature isn't trying to obfuscate pi's digits. Hashes and the output function of ISAAC deliberately is. $\endgroup$ – Paul Uszak Jun 1 '17 at 16:40
  • $\begingroup$ True. I wonder if a Quantum program could speed up the breaking of ISAAC. $\endgroup$ – Bipman Jun 1 '17 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.