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

[Solar Designer <solar@openwall.com>]

Colin,

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.

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?)

For now, I am doing #1.  The advantages of it over #2 are: uniform
distribution of indices, fast Integerify(), matching standard scrypt.
The drawback is that it's not entirely flexible, affecting not only
total memory size (as desired), but also the size of individual V
elements.  In some cases, the elements become unnecessarily too large
(which benefits some attackers).  They also cross page boundaries more
often, which results in TLB misses that could otherwise be avoided (some
V elements require two TLB entries instead of just one), although this
is easily compensated for by r being just slightly larger.

Alexander