BlockMix shuffling

[Solar Designer <solar@openwall.com>]

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