[Cryptography] A modification to scrypt to reduce side channel risk

[Bill Cox]

On Fri, Dec 27, 2013 at 6:12 AM, Jerry Leichter <leichter at 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...
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20131227/2c07def8/attachment.html>