Re: A modification to scrypt to reduce side channel risk

[Krisztián Pintér <pinterkr@gmail.com>]

Arnold Reinhold (at Thursday, December 26, 2013, 9:29:24 PM):

> But PBKDF2 is not transistor hungry.

it is. if you double the iteration count, you effectively double the
necessary hw to break it (because you need twice as many units to
deliver the crack in the same time frame). it is the same as with
scrypt. the difference is not that, but scrypt has a huge headstart by
making one hw unit much more expensive.

> I propose replacing P, the password or passphrase, in step 1 with
> the null string. In other words all the memory banging in step 2
> would be determined solely by the salt, S. The password would only
> affect the algorithm output in step 3, which should be sufficient for security.

i believe this would severely reduce the hw cost, as you can share the
prepared memory block between multiple cores executing the 3rd step.

my main concern is that it still does not solve the bigger problem
that is not just my personal crusade, but rather, a recognized issue.
namely that the memory access pattern makes it susceptible to cache
timing attacks.

i'm wondering whether it is possible to maintain seq mem hardness
while having a fixed access pattern. i was thinking about gigantic
versions of existing primitives, like a keccak[25*2^28]. is that seq
mem hard? how close? i asked that on the PHC forum, but it did not
spark a whole lot of discussion (aka zero).

if not, maybe we could scramble the access pattern in some way. i'm
thinking about some random permutation of the index (mini block
cipher?). but that still leaks the frequency of hitting the same
location. like 12514323 and 53154232. you see the pattern there.