[messaging] Question regarding Whatsapp/Signal Safety Numbers

[Trevor Perrin]

On Thu, Sep 28, 2017 at 11:24 AM, Michael Rogers
<michael at briarproject.org> wrote:
>
> But to find A', B' such that safetyNumber(A',B) == safetyNumber(A,B'),
> the attacker has to perform stretching for every pair of candidates for
> A', B'. Doesn't the stretching make the collision search infeasible?
> (And if not, couldn't it be replaced with stretching that would, using
> Argon2 or whatever?)

Hi Michael,

Stretching increases an attacker's work in calculating each trial
value by the same factor that it increases the good user's work in
calculating the number.

So it's only feasible to get a modest benefit from it (e.g., if good
users have to iterate a SHA-512 hash ~5000 times to calculate a safety
number, that means the attacker must similarly iterate the hash for
every trial in a generic collision or pre-image search, so the
security level against such a search is raised by log(5000), or ~12
bits).  Adding an additional bit of security is twice as expensive for
the good guy, and so on.

So this isn't a panacea, and it affects attacker workload in generic
collision and pre-image searches in the same way.

Using a "memory-hard" hash, instead of a standard hash like SHA-512,
isn't a panacea either.  I discussed this once with Henry
Corrigan-Gibbs, designer of the memory-hard Balloon hash, and he
thought that for similar computation time that might increase attacker
costs by 4 or 5 bits of security.  That's a somewhat small benefit for
the hassle of porting and optimizing a new crypto algorithm to various
platforms.  Anyways, I think the important point is that stretching
only provides a modest - and similar - benefit regardless of whether
you have fingerprints or a combined hash value.

Trevor