Colin, On pages 9 and 10 of the scrypt paper, you very briefly explain why BlockMix shuffles the output vector elements. I'd like more detail on this, if possible.
Specifically, footnote 14 says that if the shuffling is omitted, then BlockMix can be rapidly iterated given precomputed values B[0], since the computation would neatly "pipeline". I'd appreciate it if you describe this attack on non-shuffling BlockMix in more detail and non-ambiguously (pseudo-code would be best). What would the precomputed table be indexed with and what B[0] values would it produce (for one BlockMix invocation? for many iterated invocations at once?) How large would it need to be for certain k and r? By iterating BlockMix do you mean repeatedly invoking it with B' as the new input B? If so, in scrypt this occurs in the first of the two loops in SMix. The concern would thus be an up to ~2x speedup of SMix. Or does the attack also extend onto the less trivial second loop? In the special case of r=1, the shuffling is a no-op: BlockMix output is (Y[0], Y[1]) whether with shuffling or without. Does this mean that scrypt with r=1 is susceptible to some extra attack? I guess that in practice this is mitigated by k (for the case of using Salsa20/8 core) being way too large for having a precomputed table, right? If so, why did you bother with the shuffling (just to have scrypt theoretically sound irrespective of the value of k?) Thanks, Alexander
