[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: Colin Percival <cperciva@tarsnap.com>*Subject*: Re: scrypt with "odd" r or N (Re: Canonical way to invoke the KDF?)*From*: Solar Designer <solar@openwall.com>*Date*: Thu, 21 Nov 2013 16:37:34 +0400*Cc*: scrypt@tarsnap.com*In-reply-to*: <20131116222743.GA10439@openwall.com>*References*: <CAE_Hg6Zcj_XxkTTwdnXf_pufXymn_td33vkEXoA+iAssjpOMEg@mail.gmail.com> <5286A858.3060906@tarsnap.com> <8D59C062-A34A-4FF9-9B76-5034B1918779@flownet.com> <5286CB88.5010100@tarsnap.com> <20131116020854.GA4910@openwall.com> <5287E82B.7090809@tarsnap.com> <20131116222743.GA10439@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

**Follow-Ups**:**Re: scrypt with "odd" r or N (Re: Canonical way to invoke the KDF?)***From:*Colin Percival <cperciva@tarsnap.com>

**References**:**Canonical way to invoke the KDF?***From:*Laurens Van Houtven <_@lvh.cc>

**Re: Canonical way to invoke the KDF?***From:*Colin Percival <cperciva@tarsnap.com>

**Re: Canonical way to invoke the KDF?***From:*Ron Garret <ron@flownet.com>

**Re: Canonical way to invoke the KDF?***From:*Colin Percival <cperciva@tarsnap.com>

**scrypt with "odd" r or N (Re: Canonical way to invoke the KDF?)***From:*Solar Designer <solar@openwall.com>

**Re: scrypt with "odd" r or N (Re: Canonical way to invoke the KDF?)***From:*Colin Percival <cperciva@tarsnap.com>

**Re: scrypt with "odd" r or N (Re: Canonical way to invoke the KDF?)***From:*Solar Designer <solar@openwall.com>

- Prev by Date:
**Re: Canonical way to invoke the KDF?** - Next by Date:
**Re: scrypt with "odd" r or N (Re: Canonical way to invoke the KDF?)** - Previous by thread:
**Re: scrypt with "odd" r or N (Re: Canonical way to invoke the KDF?)** - Next by thread:
**Re: scrypt with "odd" r or N (Re: Canonical way to invoke the KDF?)** - Index(es):