On: Disappearing messages for Signal

[wtbob]

> They're relatively compact. Users compare 12 groups of 5 digits with each other, which is half the size of our previous hexadecimal format.

60 digits have 199 bits of security, so I suppose that's mostly okay, right? Does the birthday paradox apply here, reducing it to 98 bits?

[stavros → wtbob]

No, since you presumably want to match a specific user's key, not just find two users with the same key.

[lenish → stavros]

It is a similar problem, however: https://en.wikipedia.org/wiki/Birthday_problem#Same_birthday...

[lorenzhs → lenish]

That's still not the problem considered here. You're not asking "does anyone have the key I'm seeing here", you're asking "does this person next to me have the key I'm seeing here". No birthday paradoxes of any kind involved.

[lenish → lorenzhs]

Forgive me, as I haven't used signal, but I don't see how whether they are sitting next to you or not changes the problem.

If I can generate a key that hashes to the same value as your key, I can convince anyone I am you. If I can generate a second collision for a third party's key, I can convince you you are talking to that third party, as well. Generating hash collisions is, as I understand it, pretty well modelled with the birthday paradox (and variations like the one I linked). Physical proximity seems entirely unrelated.

[lorenzhs → lenish]

Right, sorry, I misunderstood. A preimage attack (that's the technical term for this) could indeed be modeled as a birthday problem with a fixed day ("someone with the same birthday as me"). This is much harder than finding a normal collision (two objects with the same hash, two people with the same birthday), though.

[lenish → wtbob]

>reducing it to 98 bits?

Did you mean 198?

198 bits is entirely reasonable assuming a brute force attack is the only option. Were it not we'd be in a panic over AES-128 and AES-192. :)

[wtbob → lenish]

No, hashes generally require twice as many bits in order to avoid birthday attacks — that's why one uses SHA-256 for 128-bit security.

98 bits is still plenty, of course, but it's not 128 bits.

[lenish → wtbob]

If we're talking about the actual hash signal uses for this value, then sure, but talking about the number of digits displayed isn't even the right thing to care about, since they're using SHA1 for the hash AFAICT: https://github.com/WhisperSystems/Signal-Android/blob/3.0.0/...

[wtbob → lenish]

SHA1? SHA1 SHA1‽ I'd always thought that OWS had incredibly good crypto — why are they using SHA1? If it's to support relatively short hashes … I just can't even.

There's simply no excuse to choose to use SHA1 in 2016. It's not completely broken, it's probably good enough, but why not just truncate SHA2?

[pfg → wtbob]

SHA-1 is fine in this context. SHA-1 isn't as collision-resistant as it was once thought to be, but that's not a property that you care about for this use-case.

The same principle applies to checksums that are sometimes published for binaries - many still use MD5 or SHA-1 - and that's fine too, as (second) preimage resistance is what counts here, rather than collision-resistance.