A modification to scrypt to reduce side channel risk

[Arnold Reinhold <agr@me.com>]

On Dec 25, 2013, at 2:51 PM, Krisztián Pintér <pinterkr@gmail.com> wrote (responding to me):

but that is no excuse for failing to provide strong protection

like for example pbkdf2. (let me just stress like the thousandth time
that i don't like it. but it is safe, standard, and cpu-hungry.) in
comparison, scrypt is better in many situations, while worse or even
broken in some other situations. use with care.

But PBKDF2 is not transistor hungry. That's the problem. Rather than continuing to argue that side channel attacks are not as serious as the primary attack, I'd like to propose a way to minimize that risk. Here is the summary of scrypt from the draft RFC (tools.ietf.org/html/draft-josefsson-scrypt-kdf-00):

     1. B[0] || B[1] || ... || B[p - 1] =
          PBKDF2-HMAC-SHA256 (P, S, 1, p * 128 * r)

     2. for i = 0 to p - 1 do
          B[i] = scryptROMix (r, B[i], N)
        end for

     3. DK = PBKDF2-HMAC-SHA256 (P, B[0] || B[1] || ... || B[p - 1], 1, dkLen)

The B[i] are large memory blocks, one for each of p parallel processes, each 128*r octets. N is the cost parameter. DK is the derived key.

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. 

Since the salt is not a secret, there is nothing in memory, timing, acoustic signatures, power consumption, etc.  during steps 1 and 2 that provides any clue to the password. Step 3 is just PBKDF2 which is apparently considered safe from side channel attack and is, in any case, the standard of comparison here. This is in contrast to scrypt where knowledge of a few bytes of one of the B[i] captured at some stage could serve as an oracle for the password.

An attacker who can capture the entire state of the algorithm at some point during step 2 can bypass the work done up to that point, but still has to reverse step 3. Note that running PBKDF2 with a very large amount of pseudo-random data, even if known, is transistor-expensive. If desired, the iteration count in step 3 can be increased from 1 to a value that balances the work budgets in steps 2 and 3 against the different threats. 

Unless an attacker who captures the entire state of the algorithm during step 2 can then carry out their attack on the same machine, they also would have to communicate the entire state information to a machine they control. Anything less that all the B[i]'s minus a few bytes is useless. Carrying out the attack on the same machine would also require contemperanious knowledge of the output of step 3, which is not available to side channels due to the presumed strength of PBKDF2. Transmitting the state information in anticipation of a future leak of the password database would consume vast amounts of bandwidth that is hard to conceal. 

The salt would have to be big enough prevent precomputed exploded salt tables, but given the large amount of information that would have to be stored for each salt, 64 bits is likely enough. 80 bits would have a good margin of safety.

It seems like this simple modification to scrypt would address the concerns expressed by many on the cryptography list and is clearly at least as strong as PBKDF2 at the work level expended in step 3. Am I missing something?

Arnold Reinhold