Identity/CryptoIdeas/01-PBKDF-scrypt: Difference between revisions

Jump to navigation Jump to search

Identity/CryptoIdeas/01-PBKDF-scrypt (view source)

Revision as of 00:06, 20 April 2012

29 bytes added ,  20 April 2012
update text
(update text)
Line 7: Line 7:
Firefox Sync) to obtain full-strength per-domain encryption keys, which the
Firefox Sync) to obtain full-strength per-domain encryption keys, which the
user can regenerate any time they like using a password and information
user can regenerate any time they like using a password and information
stored on a Primary server (or on the BrowserID server, when it acts as a
stored on the BrowserID storage server. From the point-of-view of such
Secondary). From the point-of-view of such services, these keys really are
services, these keys really are full-strength: 256 bits of pure entropy. The
full-strength: 256 bits of pure entropy. The system looks basically like
system looks basically like this:
this:


[[File:01-key-wrapping.png|Basic Key Wrapping diagram]]
[[File:01-key-wrapping.png|Basic Key Wrapping diagram]]
Line 19: Line 18:
password and the data stored on the Primary, there must be places in the
password and the data stored on the Primary, there must be places in the
system for which the keys are less than full strength. The most vulnerable
system for which the keys are less than full strength. The most vulnerable
point is the Primary server which holds the wrapped user key ("WUK"). In
point is the server which holds the wrapped user key ("WUK"). In general,
general, attackers can be categorized into a few different groups:
attackers can be categorized into a few different groups:


; network eavesdroppers : since all connections are assumed to run over SSL, which does a great job of protecting against passive eavesdroppers, these attackers have nothing to work with
; network eavesdroppers : since all connections are assumed to run over SSL, which does a great job of protecting against passive eavesdroppers, these attackers have nothing to work with
Line 26: Line 25:
; man-in-the-middle : SSL does a less-great job of protecting against active attackers. There are too many CAs, users do not have enough information to identify the "right" site, and the security indicators are too fragile for users to reliably notice.
; man-in-the-middle : SSL does a less-great job of protecting against active attackers. There are too many CAs, users do not have enough information to identify the "right" site, and the security indicators are too fragile for users to reliably notice.


; Primary Server and Friends : the primary/secondary server holds the WUK, as well as other verification data used to decide whether to honor requests to update the WUK later, both of which can be used to attack the user's password and thus the Password-Wrapping-Key (PWK), which then combines with the WUK to get the ultimate goal: the User Key (UK). This category of attacker includes anyone who can get access to the WUK: admins of the server, anyone who successfully breaks into the server or gets a copy of a backup disk, and any party who can coerce/subpoena the admins into revealing a WUK.
; Storage Server and Friends : the server holds the WUK, as well as other verification data used to decide whether to honor requests to update the WUK later, both of which can be used to attack the user's password and thus the Password-Wrapping-Key (PWK), which then combines with the WUK to get the ultimate goal: the User Key (UK). This category of attacker includes anyone who can get access to the WUK: admins of the server, anyone who successfully breaks into the server or gets a copy of a backup disk, and any party who can coerce/subpoena the admins into revealing a WUK.


In general, attacks must start by stealing/possessing an
In general, attacks must start by stealing/possessing an
Line 51: Line 50:
the space of passwords that must be searched: a user who can make passwords
the space of passwords that must be searched: a user who can make passwords
with 40 bits of entropy will increase the attacker's costs by 32x over the
with 40 bits of entropy will increase the attacker's costs by 32x over the
baseline explored here.
baseline explored here. Someone who uses 6-digit PINs (20 bits) will lower
the attacker's costs by 32768x.


PBKDF is basically multiple rounds of SHA256 hashing, designed to increase
PBKDF is basically multiple rounds of SHA256 hashing, designed to increase
Line 74: Line 74:


This results in a brute-force cost of about $28.44 per key, for an attacker
This results in a brute-force cost of about $28.44 per key, for an attacker
in the "Primary Server and Friends" category. Note that this cost is
in the "Storage Server and Friends" category. Note that this cost is
per-user: by using the user's email address as a salt, the attacker is forced
per-user: by using the user's email address as a salt, the attacker is forced
to attack each key separately (without the salt, they could attack all user
to attack each key separately (without the salt, they could attack all user
Line 111: Line 111:
server. The browser code first spends 500ms computing 23k iterations of PBKDF
server. The browser code first spends 500ms computing 23k iterations of PBKDF
to generate an intermediate "A" value. It then sends A to the '''scrypt Helper''',
to generate an intermediate "A" value. It then sends A to the '''scrypt Helper''',
a service that we run (not the Primary). The Helper spends one second computing the
a service that we run (separate from the Storage Server). The Helper spends
scrypt function, then returns the derived "B" value. The Helper then
one second computing the scrypt function, then returns the derived "B" value.
carefully forgets everything about the computation.
The Helper then carefully forgets everything about the computation.


The browser receives the B value, then spends another 500ms computing PBKDF
The browser receives the B value, then spends another 500ms computing PBKDF
Line 162: Line 162:
system at frequent intervals to "shake out" any intruders.
system at frequent intervals to "shake out" any intruders.


As with the PBKDF-only design, the Primary Server '''must''' remember the
As with the PBKDF-only design, the Storage Server '''must''' remember the
long-term WUK value to function correctly, however in this proposal the WUK does
long-term WUK value to function correctly, however in this proposal the WUK
not provide the same low-cost attack vector.
does not provide the same low-cost attack vector.


(caveats: you should always be skeptical of models that claim to produce
(caveats: you should always be skeptical of models that claim to produce
Line 202: Line 202:
[[File:08-details.png|SRP Details]]
[[File:08-details.png|SRP Details]]


Fundamentally, the Primary Server holds a "mutable slot" that contains
Fundamentally, the Storage Server holds a "mutable slot" that contains
encrypted data. The client will frequently (perhaps once per browser session)
encrypted data. The client will frequently (perhaps once per browser session)
fetch that encrypted data. Less frequently, that client will want to change
fetch that encrypted data. Less frequently, that client will want to change
Line 273: Line 273:


* 10-Apr-2012: updated cost model: EC2 spot prices are 3x lower than on-demand, lowering scrypt "expensive" attack from $750k to $258k -warner
* 10-Apr-2012: updated cost model: EC2 spot prices are 3x lower than on-demand, lowering scrypt "expensive" attack from $750k to $258k -warner
* note that the current plan is to *not* store the WUK on a Primary IdP, but only on a mozila server -warner
* note that the current plan is to *not* store the WUK on a Primary IdP, but only on a mozilla server -warner
* 17-Apr-2012: PBKDF2, when used to create 3 keys, takes 3 times as long (i.e. we get one third the protection for a given user delay). I'd rather generate multiple keys with the HKDF expansion step, which is safe but doesn't repeat the stretching. And once we're using that, it easier to write the spec if we use the HKDF extraction step too (even though it's unnecessary here: the output of PBKDF is already uniform). So I'm going to rewrite that part to use do C=PBKDF2(P=join(B,password),S=constant), PWK,MAC,SRPpw=HKDF(XTS=constant, SKM=C, CTXinfo="", L=3*256/8).
* 17-Apr-2012: PBKDF2, when used to create 3 keys, takes 3 times as long (i.e. we get one third the protection for a given user delay). I'd rather generate multiple keys with the HKDF expansion step, which is safe but doesn't repeat the stretching. And once we're using that, it easier to write the spec if we use the HKDF extraction step too (even though it's unnecessary here: the output of PBKDF is already uniform). So I'm going to rewrite that part to use do C=PBKDF2(P=join(B,password),S=constant), PWK,MAC,SRPpw=HKDF(XTS=constant, SKM=C, CTXinfo="", L=3*256/8).
* I'm going to try cross-compiling the scrypt() code to JS with [http://emscripten.org/ Emscriptem] to see how much of a slowdown we get. On Chrome, we could use conceivably use [https://developers.google.com/native-client/overview NaCl] to run the scrypt() code at full speed, although currently they're only allowing NaCl code to run inside apps downloaded from their app store.
* I'm going to try cross-compiling the scrypt() code to JS with [http://emscripten.org/ Emscriptem] to see how much of a slowdown we get. On Chrome, we could use conceivably use [https://developers.google.com/native-client/overview NaCl] to run the scrypt() code at full speed, although currently they're only allowing NaCl code to run inside apps downloaded from their app store.
Warner
Confirmed users
471

edits

Retrieved from "https://wiki.mozilla.org/Special:MobileDiff/422321"

Navigation menu