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

[Colin Percival <cperciva@tarsnap.com>]

On 11/21/13 04:37, Solar Designer wrote:
> 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:
>>> 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).

Oops, you're right -- I was thinking "16 bytes" rather than "16 32-bit words"
for some reason.

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

Yeah... not as bad as it sounds given that you could precompute (2^32)^i mod N
and then need "only" 16 multiplies+adds along with a single division, but still
a bit silly.

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