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

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

Revision as of 23:25, 5 April 2012

4,328 bytes added , 5 April 2012

m

→‎Key-Wrapping Techniques

Warner

Confirmed users

471

edits

@@ Line 1: / Line 1: @@
 == Key-Wrapping Techniques ==
-The basic key-wrapping proposal in [[BrowserID Key Wrapping]] looks basically like this:
+* Brian Warner, 05-Apr-2012
-[[Image:01-key-wrapping.png|Basic Key Wrapping diagram]]
+The basic key-wrapping proposal in [[BrowserID Key Wrapping]] describes an
+layered arrangement of encrypted keys that allow arbitrary sites (e.g.
+Firefox Sync) to obtain full-strength per-domain encryption keys, which the
+user can regenerate any time they like using information stored on a Primary
+server (or on the BrowserID server, when it acts as a Secondary). From the
+point-of-view of such services, these keys really are full-strength: 256 bits
+of pure entropy. The system looks basically like this:
+[[File:01-key-wrapping.png|Basic Key Wrapping diagram]]
+=== Attacks ===
+Since this model allows the user to get at their data using nothing but a
+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
+point is the Primary server which holds the wrapped user key ("WUK"). In
+general, 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
+; 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.
+In general, attacks must start are performed by stealing/possessing an
+"oracle" value (like the MAC portion of the WUK) which allows them to test
+whether a given password is correct or not. Then the attacker generates
+guesses for the user's password (which is the most predictable value in the
+system) and runs through same protocol as the user would, until they get to a
+value which can be tested against their oracle. They must do this a lot,
+since there are lots of possible passwords, so they're interested in
+minimizing the cost of each attempt.
+=== PBKDF User/Attacker Costs ===
+We can evaluate various techniques according to how much they cost the user
+(in units of time spent waiting for a login) versus how much they cost the
+attacker (in units of dollars spent finding a password).
+To start with, it's reasonable to hope that the user's password contains
+about 35 bits of entropy (when expressed as groups of purely-random base32
+characters, this looks like "rf-o5m-t6").
+PBKDF is basically multiple rounds of SHA256 hashing, designed to increase
+the cost of a brute-force attack. My 2010 MacBookPro takes about 22us to do
+each PBKDF iteration in Javascript (using the
+[[http://crypto.stanford.edu/sjcl/|SJCL]] library), and we can probably get
+away with a 500ms delay in the login process. This gives us about 23k
+iterations of PBKDF, and a user cost of about 500ms.
+Unfortunately, the attackers aren't limited to Javascript or the CPU in my
+laptop. A real attacker will use a highly-optimized GPU, which can do roughly
+one billion SHA256 hashes per second (1ns per iteration). We can use the
+[[http://www.bitcoinwatch.com/|Bitcoin]] network statistics and exchange
+rates to estimate the cost (including both the GPUs and the electricity) of
+doing a SHA256 hash using state-of-the-art technology. This works out to
+about 36*10<sup>-15</sup> (femtodollars) per hash, e.g. one USD will buy you
+about 28*10<sup>12</sup> = 28 trillion hashes. (as of 05-Apr-2012, where
+DF=1.626M, hashrate=11.37Thps, and a mtgox price of $4.91/BTC).
+[[File:02-PBKDF-cost.png|PBKDF costs for user and 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
+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
+accounts at the same time, and amortize the costs).