Re: scrypt Integerify

[Solar Designer <solar@openwall.com>]

On Sun, Nov 18, 2012 at 03:19:46AM -0800, Colin Percival wrote:
> On 11/16/12 21:17, Solar Designer wrote:
> > Curiously, the scrypt paper does not appear to fully define Integerify().
> 
> Definition 3 specifies that Integerify(B_0 .. B_{2 r - 1}) is defined as
> the result of interpreting B_{2 r - 1} as a little-endian integer.

Yes, there it is.  Thanks.

> I can't actually remember how interpreting B[2r - 1] as a little-endian
> value turned into accessing X[13]... did I permute the data somehow when
> I went from the -ref code to the -sse code?  It was a long time ago that
> I wrote that...

I took a closer look into this, and it appears that the -sse
implementation of SMix does in fact work on permuted data all the time.
This works fine due to everything outside of Salsa20 being just XOR's.

So, yes, some kind of permutation was in fact needed in integerify(),
and probably the index 13 is right, although I did not verify it.

In terms of optimization, the best we can do is produce a specialized
version for <= 512 GiB, which would use a 32-bit value only (and would
refuse to work if invoked with N >= 2^32).  Should we bother for a <1%
speedup?  Maybe not.

Thanks, and sorry for the confusion.

Alexander