[148770] in cryptography@c2.net mail archive
Re: [Cryptography] A modification to scrypt to reduce side channel
daemon@ATHENA.MIT.EDU (Bill Cox)
Fri Dec 27 12:08:21 2013
X-Original-To: cryptography@metzdowd.com
In-Reply-To: <44BEE4B3-22FB-488A-900E-E0EDDD19AC5A@lrw.com>
Date: Fri, 27 Dec 2013 07:02:30 -0500
From: Bill Cox <waywardgeek@gmail.com>
Cc: Cryptography <cryptography@metzdowd.com>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
--===============0226064987881026159==
Content-Type: multipart/alternative; boundary=001a11c24dbc5e3e8904ee82deeb
--001a11c24dbc5e3e8904ee82deeb
Content-Type: text/plain; charset=ISO-8859-1
On Fri, Dec 27, 2013 at 6:12 AM, Jerry Leichter <leichter@lrw.com> wrote:
> On Dec 26, 2013, at 8:09 PM, Bill Cox wrote:
>
> .... If we use a memory hard KDF that hashes 4 GB with RNG data on our
> PCs in 1 second....
>
> OK, so now we've moved from abstraction to a concrete proposal.
>
> And just who would use such a KDF? Tying up 4GB for a second is a very
> expensive proposition on a server. People have to manage thousands of
> logins a second, so you're talking about devoting Terabytes of main memory
> - not disk or SSD - *just to logins*.
>
I saw code in script to automatically generate good parameters. Basically
it fills and hashes memory for about a second. If you use it that way, it
works on a mobile phone or a high end gaming machine perfectly well. I
think to make it friendly to most users, this is how implementations need
to work.
> You've suggested doing the KDF computation on the client. How many
> clients have 4GB of free memory? I've got a laptop with 8GB of memory.
> WHen in active use, it never has even 2GB free. Maybe my laptop can do
> the computation - but it will take a while because it'll have to swap stuff
> out. (And of course then they'll have to swap it back in.) I see this
> happen periodically when I've got a bit too much stuff running, and it
> ain't pretty. Hardly any user would be willing to accept the performance
> loss.
>
Actually, I'm proposing splitting the load between the client and server,
allowing any ratio at all. Basically both the client and server should run
the KDF. If the client is just running non-Javascript-enabled HTML, then
he's entirely dependent on the server for KDF. If he's running Javascript,
the server would likely prefer that the client to take some, but not all,
of the load. Long KDF times like a second of hashing and using half of all
available memory is something you really want to offload to the client.
However, the server should not assume the client did KDF properly, and
should do at least a little, like hashing memory for 10 to 100
milliseconds. The only thing required here is that the server save KDF
parameters for both the client and server, rather than just the server, so
it's not a huge step in complexity. However, I think it adds a great deal
of security and flexibility. And my favorite reason for this proposal:
maybe it will end the endless server-side/client-side KDF debate.
> As for portable devices - I'm not sure any of the actually *have* 4GB of
> RAM in total. And the power costs of pegging the CPU for a second are
> non-trivial, too. So basically you're writing them all off.
>
No, 4GB was just an example, based on my 8GB linux desktop. Parameters
should most likely be determined automatically in most cases, so old cell
phones would be fine. However, you wouldn't want to enter a password with
major client side processing on a high end desktop and still expect to be
able to login to that site on your phone. Assuming this is generally up to
the server, since users wont generally know what KDF is anyway, it would be
up to the server admins to decide what kind of client-side hashing is
reasonable. Facebook probably would want to assume very little, but an
online bank might prefer to assume you've at least got a 1GB netbook worth
of power.
Also, remember this client/server thing remains a side issue. My poor ssh
private key is sitting on disk with at most 256 rounds of SHA-256, which is
basically worthless vs hardware based guessing.
> The parameters you've suggested basically limit secure communication to
> someone with the NSA's resources. :-)
>
Or my son's gaming machine, which I is a converted BitCoin miner. He loves
that graphics card. Actually the linux box I'm using as my reference is
also his. He wanted a Minecraft server capable of hosting 4 simultaneous
games. I discovered yesterday what happens when I use all the memory and
lock it down with mlock... all the Minecraft servers crash! Getting this
KDF right is tricky...
--001a11c24dbc5e3e8904ee82deeb
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On F=
ri, Dec 27, 2013 at 6:12 AM, Jerry Leichter <span dir=3D"ltr"><<a href=
=3D"mailto:leichter@lrw.com" target=3D"_blank">leichter@lrw.com</a>></sp=
an> wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex"><div style=3D"word-wrap:break-word"><div><di=
v>On Dec 26, 2013, at 8:09 PM, Bill Cox wrote:</div><blockquote type=3D"cit=
e"><div dir=3D"ltr">
<div class=3D"gmail_extra"><div class=3D"gmail_quote"><div><font color=3D"#=
000000">...</font>. =A0If we use a memory hard KDF that hashes 4 GB with RN=
G data on our PCs in 1 second....</div></div></div></div></blockquote>OK, s=
o now we've moved from abstraction to a concrete proposal.</div>
<div><br></div><div>And just who would use such a KDF? =A0Tying up 4GB for =
a second is a very expensive proposition on a server. =A0People have to man=
age thousands of logins a second, so you're talking about devoting Tera=
bytes of main memory - not disk or SSD - *just to logins*.</div>
</div></blockquote><div><br></div><div>I saw code in script to automaticall=
y generate good parameters. =A0Basically it fills and hashes memory for abo=
ut a second. =A0If you use it that way, it works on a mobile phone or a hig=
h end gaming machine perfectly well. =A0I think to make it friendly to most=
users, this is how implementations need to work.</div>
<div>=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;=
border-left:1px #ccc solid;padding-left:1ex"><div style=3D"word-wrap:break-=
word"><div>You've suggested doing the KDF computation on the client. =
=A0How many clients have 4GB of free memory? =A0I've got a laptop with =
8GB of memory. =A0WHen in active use, it never has even 2GB free. =A0Maybe =
my laptop can do the computation - but it will take a while because it'=
ll have to swap stuff out. =A0(And of course then they'll have to swap =
it back in.) =A0I see this happen periodically when I've got a bit too =
much stuff running, and it ain't pretty. =A0Hardly any user would be wi=
lling to accept the performance loss.</div>
</div></blockquote><div><br></div><div>Actually, I'm proposing splittin=
g the load between the client and server, allowing any ratio at all. =A0Bas=
ically both the client and server should run the KDF. =A0If the client is j=
ust running non-Javascript-enabled HTML, then he's entirely dependent o=
n the server for KDF. =A0If he's running Javascript, the server would l=
ikely prefer that the client to take some, but not all, of the load. =A0Lon=
g KDF times like a second of hashing and using half of all available memory=
is something you really want to offload to the client. =A0However, the ser=
ver should not assume the client did KDF properly, and should do at least a=
little, like hashing memory for 10 to 100 milliseconds. =A0The only thing =
required here is that the server save KDF parameters for both the client an=
d server, rather than just the server, so it's not a huge step in compl=
exity. =A0However, I think it adds a great deal of security and flexibility=
. =A0And my favorite reason for this proposal: maybe it will end the endles=
s server-side/client-side KDF debate.</div>
<div>=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;=
border-left:1px #ccc solid;padding-left:1ex"><div style=3D"word-wrap:break-=
word"><div>As for portable devices - I'm not sure any of the actually *=
have* 4GB of RAM in total. =A0And the power costs of pegging the CPU for a =
second are non-trivial, too. =A0So basically you're writing them all of=
f.</div>
</div></blockquote><div><br></div><div>No, 4GB was just an example, based o=
n my 8GB linux desktop. =A0Parameters should most likely be determined auto=
matically in most cases, so old cell phones would be fine. =A0However, you =
wouldn't want to enter a password with major client side processing on =
a high end desktop and still expect to be able to login to that site on you=
r phone. =A0Assuming this is generally up to the server, since users wont g=
enerally know what KDF is anyway, it would be up to the server admins to de=
cide what kind of client-side hashing is reasonable. =A0Facebook probably w=
ould want to assume very little, but an online bank might prefer to assume =
you've at least got a 1GB netbook worth of power.</div>
<div><br></div><div>Also, remember this client/server thing remains a side =
issue. =A0My poor ssh private key is sitting on disk with at most 256 round=
s of SHA-256, which is basically worthless vs hardware based guessing.</div=
>
<div>=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;=
border-left:1px #ccc solid;padding-left:1ex"><div style=3D"word-wrap:break-=
word"><div>The parameters you've suggested basically limit secure commu=
nication to someone with the NSA's resources. =A0:-)</div>
</div></blockquote><div><br></div><div>Or my son's gaming machine, whic=
h I is a converted BitCoin miner. =A0He loves that graphics card. =A0Actual=
ly the linux box I'm using as my reference is also his. =A0He wanted a =
Minecraft server capable of hosting 4 simultaneous games. =A0I discovered y=
esterday what happens when I use all the memory and lock it down with mlock=
... =A0all the Minecraft servers crash! =A0Getting this KDF right is tricky=
...</div>
</div></div></div>
--001a11c24dbc5e3e8904ee82deeb--
--===============0226064987881026159==
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
--===============0226064987881026159==--
