Re: scrypt with "odd" r or N (Re: Canonical way to invoke the KDF?)

[Solar Designer <solar@openwall.com>]

Colin,

On Sun, Nov 17, 2013 at 02:27:43AM +0400, Solar Designer wrote:
> On Sat, Nov 16, 2013 at 01:48:27PM -0800, Colin Percival wrote:
> > On 11/15/13 18:08, Solar Designer wrote:
> > > When N is not a power of 2, any definition of Integerify() would result
> > > in a non-uniform distribution of the resulting indices.  While this may
> > > be acceptable, it let's say does not feel nice.
> > 
> > Having probabilities which are off by less than 2^-128 doesn't exactly matter.
> 
> I agree.  In practice, an optimized implementation would be likely to
> process fewer bits of B_{2r-1}, resulting in the probabilities being off
> e.g. by up to 2^-64 or even 2^-32, but this is still acceptable.

Actually, such an optimized implementation would be incompatible with
the current scrypt specification (the paper).  The portion of B_{2r-1}
to be processed by Integerify has to be defined in the spec.  Which
brings us to:

> > No revision necessary: The scrypt algorithm as defined in my paper sets
> > Integerify = the 128-bit integer generated by interpreting B_{2r-1} as a
> > little-endian integer, and ROMix explicitly reduces this modulo N.
> > 
> > The "take the bottom n bits of the first word in B_{2r-1}" is just an
> > optimization for the case where N = 2^n.
> 
> You're right indeed.

Upon closer review:

Where does the "128-bit" you mentioned above come from?  B_{2r-1} is 64
bytes, not 128 bits.  Page 10 of the paper defines Integerify as
interpreting B_{2r-1} as a little-endian integer, without mentioning any
kind of truncation (at 128-bit or otherwise).

Dividing a 64 byte integer by arbitrary weird N may be quite slow.

(BTW, if Integerify were in fact 128-bit, the probabilities would be
off by about 2^-96 (assuming modulo division by non-power-of-2 N of
around 2^32), not the 2^-128 you mentioned.  Not that this makes any
difference now.  It may become relevant if we revise scrypt to allow
much smaller Integerify to be used with modulo division, for speed.)

Alexander