[148751] in cryptography@c2.net mail archive
[Cryptography] A modification to scrypt to reduce side channel risk
daemon@ATHENA.MIT.EDU (Arnold Reinhold)
Thu Dec 26 15:37:44 2013
X-Original-To: cryptography@metzdowd.com
From: Arnold Reinhold <agr@me.com>
In-reply-to: <1927038653.20131225205111@gmail.com>
Date: Thu, 26 Dec 2013 15:29:24 -0500
To: =?iso-8859-1?Q?Kriszti=E1n_Pint=E9r?= <pinterkr@gmail.com>
Cc: Cryptography <cryptography@metzdowd.com>, scrypt@tarsnap.com
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
--===============4715227559961570933==
Content-type: multipart/alternative;
boundary="Apple-Mail=_FFE6D818-A4F3-493D-B711-1146B751835E"
--Apple-Mail=_FFE6D818-A4F3-493D-B711-1146B751835E
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
charset=iso-8859-1
On Dec 25, 2013, at 2:51 PM, Kriszti=E1n Pint=E9r <pinterkr@gmail.com> =
wrote (responding to me):
>=20
>> but that is no excuse for failing to provide strong protection
>=20
> 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.
>=20
>=20
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] =3D
> PBKDF2-HMAC-SHA256 (P, S, 1, p * 128 * r)
>=20
> 2. for i =3D 0 to p - 1 do
> B[i] =3D scryptROMix (r, B[i], N)
> end for
>=20
> 3. DK =3D 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.=20
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.=20
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.=20
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
--Apple-Mail=_FFE6D818-A4F3-493D-B711-1146B751835E
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html;
charset=iso-8859-1
<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html =
charset=3Diso-8859-1"></head><body style=3D"word-wrap: break-word; =
-webkit-nbsp-mode: space; -webkit-line-break: after-white-space; =
"><br><div><div>On Dec 25, 2013, at 2:51 PM, Kriszti=E1n Pint=E9r <<a =
href=3D"mailto:pinterkr@gmail.com">pinterkr@gmail.com</a>> wrote =
(responding to me):</div><br =
class=3D"Apple-interchange-newline"><blockquote =
type=3D"cite"><br><blockquote type=3D"cite">but that is no excuse for =
failing to provide strong protection<br></blockquote><br>like for =
example pbkdf2. (let me just stress like the thousandth time<br>that i =
don't like it. but it is safe, standard, and cpu-hungry.) =
in<br>comparison, scrypt is better in many situations, while worse or =
even<br>broken in some other situations. use with =
care.<br><br><br></blockquote></div><br><div>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 (<a =
href=3D"http://tools.ietf.org/html/draft-josefsson-scrypt-kdf-00">tools.ie=
tf.org/html/draft-josefsson-scrypt-kdf-00</a>):</div><div><br></div><div><=
pre class=3D"newpage" style=3D"font-size: 1em; margin-top: 0px; =
margin-bottom: 0px; page-break-before: always; "><blockquote =
type=3D"cite"><pre class=3D"newpage" style=3D"font-size: 1em; =
margin-top: 0px; margin-bottom: 0px; page-break-before: always; "> =
1. B[0] || B[1] || ... || B[p - 1] =3D
PBKDF2-HMAC-SHA256 (P, S, 1, p * 128 * r)
2. for i =3D 0 to p - 1 do
B[i] =3D scryptROMix (r, B[i], N)
end for
3. DK =3D PBKDF2-HMAC-SHA256 (P, B[0] || B[1] || ... || B[p - 1], =
1, dkLen)
</pre></blockquote><div><pre class=3D"newpage" style=3D"font-size: 1em; =
margin-top: 0px; margin-bottom: 0px; page-break-before: always; =
"><br></pre></div></pre><pre class=3D"newpage" style=3D"font-size: 1em; =
margin-top: 0px; margin-bottom: 0px; page-break-before: always; "><div =
style=3D"font-family: Helvetica; font-size: medium; white-space: normal; =
">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.</div><div style=3D"font-family: Helvetica; font-size: medium; =
white-space: normal; "><br></div><div style=3D"font-family: Helvetica; =
font-size: medium; white-space: normal; ">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<font face=3D"monospace"><span =
style=3D"font-size: 1em; white-space: pre; ">. </span></font></div><div =
style=3D"font-family: Helvetica; font-size: medium; white-space: normal; =
"><font face=3D"monospace"><span style=3D"font-size: 11px; white-space: =
pre; "><br></span></font></div></pre></div>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.<div><br></div><div>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. </div><div><br></div><div>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. </div><div><br></div><div>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.</div><div><br></div><div>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?</div><div><br></div><div>Arnold =
Reinhold</div><div><br><br><div><br></div></div></body></html>=
--Apple-Mail=_FFE6D818-A4F3-493D-B711-1146B751835E--
--===============4715227559961570933==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
--===============4715227559961570933==--
