[messaging] Peerio

[Trevor Perrin]

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 [1].
Assuming I can rent cores at ~$0.04/hr [2] = $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 [3]
suggests choosing a sentence "that is unique to you, like moments
shared with friends, or childhood memories", and gives a couple
examples:
 "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 [4].  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.


Trevor


[1] http://www.tarsnap.com/scrypt/scrypt.pdf
[2] https://cloud.google.com/compute/#pricing
[3] https://www.youtube.com/watch?v=1jrtAnwHU14
[4] http://en.wikipedia.org/wiki/Entropy_(information_theory)