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

[Colin Percival <cperciva@tarsnap.com>]

On 11/15/13 18:08, Solar Designer wrote:
> On Fri, Nov 15, 2013 at 05:34:00PM -0800, Colin Percival wrote:
>> The scrypt algorithm is specified as operating on arbitrary N; it's just
>> this particular implementation which is limited in the values it can
>> handle.
> 
> 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.

> Which do you think is a better way to handle "odd" total memory sizes
> (if optimal for a certain platform and certain throughput and latency
> constraints):
> 
> 1. Use "odd" values of r.
> 
> -OR-
> 
> 2. Use "odd" values of N _and_ revise Integerify() accordingly
> (arbitrary modulo division?)

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.

-- 
Colin Percival
Security Officer Emeritus, FreeBSD | The power to serve
Founder, Tarsnap | www.tarsnap.com | Online backups for the truly paranoid