key-wrapping protocol: more details

[Brian Warner]

Hi folks..

I've been filling in the details on Ben's key-wrapping proposal from
last month (https://wiki.mozilla.org/BrowserID_Key_Wrapping). I've
posted some analysis and ideas on this page:

https://wiki.mozilla.org/Identity/CryptoIdeas/01-PBKDF-scrypt

The basic idea is to maximize the user's security given a set of
constraints. The biggest constraint is that everything be recoverable
from just the user's memorized email+password and the server-side data.
The second constraint is to make the user's normal login flow run as
quickly as possible.

It's pretty easy to lock out external attackers: passive eavesdroppers,
people trying to guess passwords by querying the service (we can
rate-limit guessing attempts). Active "man-in-the-middle" attacks are
also relatively easy to block, depending upon how much extra work we do
(SRP, pinned SSL certificates) or how much confidence you have in the CA
system.

So my analysis is focused on the most extreme category of attacker:
insiders. This includes admins of the server that holds the wrapped
keys, intruders who manage to compromise that server or steal a copy of
a backup tape, or someone who coerces/subpoenas the admins into
revealing data. The interesting security metric is: once you've fought
your way into this category, how many more dollars would it cost you to
recover a given user's password and/or data-encryption key.

Key-stretching lets us increase the attacker's cost by adding more time
to the user's login process. Basically: cost = constant *
password_entropy * login_time.

I'm still working on the analysis, in particular trying to find out how
fast scrypt() can run in our target environment compared to an
attacker's fast server, and working out the fiddly bits of the protocol.

Please take a look and tell me what you think!

cheers,
-Brian

[Stefan Arentz]

On 2012-04-19, at 8:26 PM, Brian Warner wrote:

> I'm still working on the analysis, in particular trying to find out how
> fast scrypt() can run in our target environment compared to an
> attacker's fast server, and working out the fiddly bits of the protocol.

The scrypt() stuff looks interesting. Do you know how much memory it actually requires? The paper and slides only talk about it in terms of logic gates,not in actual memory.

I understand the memory requirements are to rule out GPU attacks. But I am curious how it maps to an FPGA board with some SDRAM attached to it.

S.

[Brian Warner]

On 4/20/12 7:48 AM, Stefan Arentz wrote:
>
> On 2012-04-19, at 8:26 PM, Brian Warner wrote:
>
>> I'm still working on the analysis, in particular trying to find out
>> how fast scrypt() can run in our target environment compared to an
>> attacker's fast server, and working out the fiddly bits of the
>> protocol.
>
> The scrypt() stuff looks interesting. Do you know how much memory it
> actually requires? The paper and slides only talk about it in terms of
> logic gates,not in actual memory.

You can tune that. The algorithm itself is parameterized with an "N,r,p"
tuple, and the memory usage (and operation count) are functions of
those. The one implementation out there (written for Tarsnap) runs a
quick benchmark when it starts, then picks N,r,p to meet a user-provided
memory-footprint / runtime goal (the default being something like 1/8th
of available system memory and 5 seconds). Then of course the values are
recorded in the encrypted file, so the decryptor can do the same thing.

I'm starting with a target of 100MB and 1.0s (N=65536,r=8,p=7 on my
laptop). It'll require some experimentation to see how that works out on
various devices.. obviously there will be some tradeoffs to be made.

> But I am curious how it maps to an FPGA board with some SDRAM attached
> to it.

The specific limiting factor is actually memory bandwidth. FPGAs could
do the individual operations a lot faster than a general-purpose CPU,
but you couldn't get the data in/out of RAM fast enough to take
advantage of them. (GPUs can do SHA256 so fast because the dataset is
small enough to fit in registers or L1 cache; scrypt uses a much larger
dataset).

Memory subsystems depend upon locality of reference to achieve high
speed (L1/L2/L3 caches, reading whole pages at once, wide busses, etc).
scrypt has cryptographically-strong *non*-locality of reference:
maximally bad for caches. So to get an economical speedup, you'd have to
invent something significantly faster than current memory-bus
technology, that's cheaper, but which doesn't improve the most
general/profitable use-case (for which caches make more sense). That
rules out the usual industry R+D budgets, so you can't just wait for
normal market forces to build it for you, making it even more expensive.

cheers,
-Brian

[Stefan Arentz]

On 2012-04-20, at 2:46 PM, Brian Warner wrote:

> I'm starting with a target of 100MB and 1.0s (N=65536,r=8,p=7 on my
> laptop). It'll require some experimentation to see how that works out on
> various devices.. obviously there will be some tradeoffs to be made.

Do these parameters have to stay consistent between all devices that use scrypt for a specific account or key.

Asking because mobile devices have limited RAM. Allocating 100MB could be an issue on some phones.

The idea of offloading it to servers is very interesting. But I am wondering how that scales. If this is designed to specifically make scaling difficult then that will also not help us to build a well performing scrypt service cluster.

>> But I am curious how it maps to an FPGA board with some SDRAM attached
>> to it.
>
> The specific limiting factor is actually memory bandwidth.

Thanks for the explanation. Makes a lot of sense.

S.

[Brian Warner]

On 4/20/12 11:55 AM, Stefan Arentz wrote:
>
> Do these parameters have to stay consistent between all devices that
> use scrypt for a specific account or key. Asking because mobile
> devices have limited RAM. Allocating 100MB could be an issue on some
> phones.

Yes, all devices which want to decrypt that wrapped key must use the
same parameters. Basically the security level will be limited by the
slowest/smallest device that a particular user has.

Guessing what that device will be should be an interesting exercise :).
My vague idea is either 1: pick a least-common-denominator, something
that all supported devices can handle (maybe 10MB) and hope that it
still provides enough protection against attackers, or 2: measure the
user's first device to choose parameters, use that for the rest of their
devices, and hope that they started with their slowest device.

We could store the parameters next to the wrapped key, but that opens up
an attack where the server (or someone impersonating it) tells the
client to use unreasonably low parameters, so it can learn a
less-protected value and access a cheaper attack path. The client has no
way to validate the stored parameters until it finishes acting on them.
Although.. now that I think about it, we could store a MAC of the
parameters using the derived key, and not check it until after finishing
the scrypt step (but before we reveal anything about the output of the
KDF). I'll have to think about that.

> The idea of offloading it to servers is very interesting. But I am
> wondering how that scales. If this is designed to specifically make
> scaling difficult then that will also not help us to build a well
> performing scrypt service cluster.

Yup. Measuring how fast various EC2 flavors can run scrypt is on my TODO
list, but it's probably going to require 1.0s of dedicated server time
for each act of offloaded scrypt. There's tuning that can be done: the
attacker's cost is a linear function of the client/helper's cost, and we
might be comfortable with lower margins. The constraints are how long
users are willing to wait during that setup step, and how much CPU
(well, memory bandwidth) we can afford to burn for them during that
time. Then the attacker's cost is basically some constant times that.

Ideally, this only happens once per non-native browser per user account
setup (native code should do the scrypt locally, and all clients should
cache the scrypt output forever). Each server can provide 86400
operations per day. I'm hoping someone has estimated how many users
we're going to have and sort of rate that represents, so we can guess
how much this part will cost to operate.

cheers,
-Brian

[Stefan Arentz]

On 2012-04-19, at 8:26 PM, Brian Warner wrote:

> Hi folks..
>
> I've been filling in the details on Ben's key-wrapping proposal from
> last month (https://wiki.mozilla.org/BrowserID_Key_Wrapping). I've
> posted some analysis and ideas on this page:
>
> https://wiki.mozilla.org/Identity/CryptoIdeas/01-PBKDF-scrypt

…

> Please take a look and tell me what you think!

Some more thoughts:

When I look at the proposal through the eyes of someone who writes (web) applications, I am overwhelmed. There are a lot of moving parts in this system. A lot of scary crypto things that not every developer will be comfortable with and also a flow with a good number of local and remote operations, checks and decisions.

At Mozilla we are pretty smart and have done things similar to this before, so I don't think it will be much of a problem (other than time and resources) to implement all this for our own products and services.

I am more worried about third party developers. I think that we can do this only if we can abstract all this 'magic' away for them into something really simple. Very much like the current BrowserID shim that we have now, where using BrowserID is nothing more than including a remote js file and making a call and implementing a callback. (On the client side)

I think it is best to assume that only Firefox will implement this natively so the js shim is really super important. It has to work and perform on any browser and on any platform. On fast desktops but also on slow mobiles.

The other thing that worries me is native applications. I know this is controversial but they are here to stay and we need to support them. Many web applications or services have native counterparts and that is not going to change any time soon.

Those applications would either have to implement the full key wrapping stack natively, or run a (limited) web browser embedded in the app to bootstrap things, very much like a web-based twitter or Facebook authentication dialog. The latter is obviously simpler, but likely will have performance issues and might not even aways be possible.

This is of course all less important if we are developing this just to support our own services. But I am pretty sure we want the key wrapping/storage to be a integral part of BrowserID and encourage sites to use it, right?

S.

[Mike G]

Scared php dev here. LOVE the current setup. New js api is scaring me.
Looking at janrain for verified emails, nothing social.

> _______________________________________________
> dev-identity mailing list
> dev-id...@lists.mozilla.org
> https://lists.mozilla.org/listinfo/dev-identity
>

[Ben Adida]

On 4/28/12 7:17 AM, Stefan Arentz wrote:
>
> When I look at the proposal through the eyes of someone who writes (web) applications, I am overwhelmed.

Yes, you are right, of course, that many web developers will not want to
deal with the detailed complexity that Brian outlined. And what he's
outlining is not really the API, but the guts. I think it's important
that we talk about that here, too, though we probably want to tag our
discussion as "guts of the system" vs. "web developer facing API".

Francois Marier (who just joined the team, welcome Francois!) and I are
working on a sample application that uses key wrapping. This will be
developer-facing, nice and simple. I'll let Francois describe the
details next week, once he's acclimated a bit more!

-Ben

[Ben Adida]

On 4/28/12 7:33 AM, Mike G wrote:
> Scared php dev here. LOVE the current setup. New js api is scaring me.

Let's not confuse the new API and key wrapping :)

Is navigator.id.watch() confusing you? Or is key wrapping?

The latter, key wrapping, you can safely ignore for now unless you're
really interested in crypto. The former, the API, please tell us what's
problematic.

-Ben

[Mike G]

navigator.id.watch() but I will wait for proper thread. Thank you.

> ______________________________**_________________
> dev-identity mailing list
> dev-id...@lists.mozilla.org
> https://lists.mozilla.org/**listinfo/dev-identity<https://lists.mozilla.org/listinfo/dev-identity>
>

[Brian Warner]

On 4/28/12 7:17 AM, Stefan Arentz wrote:
>
> When I look at the proposal through the eyes of someone who writes

> (web) applications, I am overwhelmed. There are a lot of moving parts
> in this system.

Oh, yeah, as Ben pointed out, this is really about the internals of the
system. Web developers wouldn't see any of it, just an API with
something like:

navigator.something.wrap(key) -> wrapped_key
navigator.something.unwrap(wrapped_key) -> key

and maybe some utility libraries that then encrypt user data with that
key.

> I think it is best to assume that only Firefox will implement this
> natively so the js shim is really super important. It has to work and
> perform on any browser and on any platform. On fast desktops but also
> on slow mobiles.

Yeah, the "scrypt helper" is there to provide for the shimmed case. The
security story isn't as strong in that case, since you're adding new
parties into your TCB (trusted computing base), including the site
(browserid.org) which serves you the JS shim, plus the SSL CAs who you
use to determine that you're really talking to browserid.org. But we can
achieve at least the same level of security as the shimmed
verified-email case.

> The other thing that worries me is native applications.

I agree. Fortunately it's easier to do fast math in native code, so
native apps won't need the helper. It's just a question of implementing
this algorithm in a reusable library and teaching developers how to use
it. Nothing about the protocol requires the use of a web browser
(although nothing precludes it from being run inside a web browser, when
necessary).

> This is of course all less important if we are developing this just to
> support our own services. But I am pretty sure we want the key
> wrapping/storage to be a integral part of BrowserID and encourage
> sites to use it, right?

Yup. The basic message is "hey sites, your users' data will be safer if
you encrypt it with this wrapped key before sending it back up to your
server, let's make it easy to do that". Just like the basic message of
BrowserID is "hey sites, your users' login process will be easier and
safer if you do it this way". We want to provide easy libraries and
examples to make both things simple.


cheers,
-Brian