[messaging] channel-ID vs PAKE secrets

[Brian Warner]

On 2/18/14 3:30 PM, Trevor Perrin wrote:
> On Mon, Feb 17, 2014 at 11:51 PM, Brian Warner <warner at lothar.com> wrote:

> But for an online rendezvous, the meeting ID (derived from the shared
> secret) is the weak point:  An attacker can try to guess the shared
> secret by making a large number of online queries for the meeting ID,
> and the rendezvous server can try to crack the meeting ID with offline
> search.
> 
> You earlier suggested that users could agree on separate meeting IDs
> and shared secrets.  But I'm not sure that gains anything.  (Ex: if
> users can agree on 60 shared secret bits, splitting that into a 30-bit
> meeting ID and 30-bit shared secret weakens resistance against the
> offline attack to 30 bits).

Oh, I probably didn't explain myself well: the users must specifically
agree on two *independent* secrets. I agree that if they're related
(e.g. hash a passphrase into 60 bits, use the first 30 as a channel-ID,
that gets revealed to at least the rendezvous server, use the other 30
as the PAKE secret) means that the channel-ID is an oracle for guessing
the original passphrase, and once you get that, you know the PAKE
secret. And you can build that table offline.

But if the secrets are properly independent, then an attacker who wins
the 30-bit online attack against the channel-ID merely earns the right
to make the one (and only) guess at the 30-bit PAKE secret. There's no
offline attack against the PAKE secret, and online attacks are limited
by the user willing to initiate a new connection. The rendezvous server
could steal the one guess for themselves, but an external attacker must
figure out the channel-ID first.

It's like there's a race you must win before claiming the "guess the
PAKE secret" prize. The rendezvous server is the judge: it can cheat and
claim the prize all by itself. Anyone else must guess (online) the
channel-ID to claim the prize. But the prize is single-use, thanks to
PAKE.

I don't know how to get unassisted humans to create two independent
secrets, though. Even something like "think of something that flies",
"now think of a number", could produce a lot of "99 red baloons".

For FF Sync, where things were easier because the pairing codes were
computer-generated, we used the first 20 bits as a channel ID, and the
other 40 bits as a PAKE secret. So they were independent by design.

If the channel-ID isn't large enough, and they're randomly selected by
clients, then a busy/successful system will look like it's under attack
(e.g. collisions in the channel-ID will result in comparison of
unrelated PAKE secrets, probably failing most of the time). We'd
considered making the FF Sync channel-id minimally short, so if you were
the only person pairing a new device right now, you'd be allocated
channel-ID "1", and the total code would be shorter. But we decided that
having a consistent length was more important than making it short most
of the time. I think we also decided to use locally-generated random
channel-IDs, rather than making them centrally-allocated, which would
also make it easier to do without a central allocator.

In a centralized system, I've also proposed using elevated failure rates
as a clue that somebody is running an attack, and increasing the length
of the PAKE secret to maintain a reasonable security margin. Maybe
"p(successful-attack) < 10^-6 per year", which could mean that you start
with a 7-digit PAKE secret, and after you get the 9th failure in any
given year, you have to increase that to 8 digits.


cheers,
 -Brian