trevp at trevp.net
Sat Feb 28 11:46:12 PST 2015
On Fri, Feb 27, 2015 at 7:26 AM, Daniel Kahn Gillmor
<dkg at fifthhorseman.net> wrote:
> On Fri 2015-02-27 04:50:19 -0500, Nadim Kobeissi wrote:
>> On Thu, Feb 26, 2015 at 11:55 PM, Daniel Kahn Gillmor <dkg at fifthhorseman.net> wrote:
>>> I agree that this part of the peerio/minilock approach is pretty
>>> disconcerting, and not just because it goes against years of practice
>>> and convention. it opens an obvious hole (offline dictionary attacks
>>> for high-value key material) and i'd love to see some more analysis of
>>> the underlying tradeoffs involved.
>> My understanding is that any search would be currently simply too expensive.
> I'm glad to hear that. Do you have pointers to details of your
> analysis? I'd love to read those thoughts.
I echo dkg - I'd really like to see more analysis, it's not obvious
the attack cost is that high.
Back of envelope:
The peerio scrypt parameters (N=2^14, r=8) have been estimated to take
< 100 milliseconds on a single core of a 2009 Intel processor .
Assuming I can rent cores at ~$0.04/hr  = $1/day, that means:
- about $1 per 2^20 (~1 million) guesses
- about $1K per 2^30 guesses
- about $1M per 2^40 guesses
How much entropy is in peerio passphrases? The tutorial video 
suggests choosing a sentence "that is unique to you, like moments
shared with friends, or childhood memories", and gives a couple
"My mother makes the best cheesecake." (36 chars)
"Waffles the cat had blue eyes" (29 chars)
You'll find various estimates for entropy-per-English character, but 1
to 1.5 bits per character seems common . This is very crude, but
that would put sentences like above in the 30-50 bit range. So it
seems plausible that a million-dollar 2^40 attacker might have a good
chance of success targeting a single account.
(I guess the zxcvbn password-strength-checker is estimating these as
>100 bits entropy? That seems high. Maybe zxcvbn is tuned for
passwords, not sentences?).
If the attacker spread his bets he'd do better. For example, the
milllion-dollar attacker could try a billion common phrases against a
thousand accounts. Specialized hardware would be even more efficient.
Note also that this is a powerful attack - if it succeeds, the
attacker can log in as you and read your old messages, without needing
server compromise or traffic interception.
Anyways, these numbers are so rough there's huge uncertainty - maybe
people will do a good job choosing weird, high-entropy sentences. Or
maybe they'll just choose song lyrics, or simple facts about their
life well known to their estranged spouse / family members. I don't
know what data exists for this, it would be a great M-Turk study.
More information about the Messaging