A Formal Security Analysis of the Signal Messaging Protocol (2017) [pdf]

https://eprint.iacr.org/2016/1013.pdf

by godelmachine • 8 years ago

100 10 8 years ago

eprint.iacr.org

egberts• 8 years ago

So there are 13 ratches, precompiled Rainbow Tables could be made to follow the decryption trail, no?

tialaramex• 8 years ago

Two things

1. When mentioning a word you've heard in the hope that people think you have some clue what you're talking about you need to stay up to date. Rainbow Tables were 2008, this is 2018, try "Blockchain" instead.

2. No. Rainbow Tables are an improved time-space tradeoff. For situations where a time-space tradeoff is almost good enough, Rainbow Tables can take you over the line. Where you aren't even close (as is the case for Signal), it doesn't matter.

For the obsolete LM Hash a straight time-space attack needs maybe 50TB of disk to break it with 100% accuracy, which back in 2003 would have been really expensive. Rainbow Tables often shrank this to about 30GB, with < 1% penalty to recall and a modest additional time penalty, so it was made much cheaper.

With a Signal ratchet you need a lot more space. Imagine all the disk space that exists in the world today. OK, now imagine that this space doubles every year somehow, and that keeps happening for the next 100 years, and you have all that disk space for your project of breaking a Signal connection. You are still nowhere close, even with some very generously estimated Rainbow Tables.

tptacek• 8 years ago

Egberts, what he's trying to say is that you can't use a rainbow table to break elliptic curve Diffie-Hellman or AES-256-CBC.

doomrobo• 8 years ago

Original edition: 2016

Extended edition (this one): 2017

bob1122• 8 years ago

Thank you for pointing that out doom

sctb• 8 years ago

Thanks! We've updated the title.

motohagiography• 8 years ago

Great paper, there goes my weekend.

Initial impression is that theoretical place to look for attacks on an implementation would be simultaneously against the derivation components in the KDFs, (const0, 1), which appear to be the basis for iterating the chain keys to gen msg keys (other than the hmac of the previous one) - and on the derivation of a chains root key from (I think) the contents of that initial 3DH key agreement. If I were sabotaging an implementation, I would probably examine the impact of reducing the entropy of these components.

Even then, you would have to precompute chains of message keys for each sender/recipient combination.

Using the previous key HMAC in the KDF to increment message and chain is a really nice touch as it removes the dependency on a static counter or a universal GF counter seed across all client instances.

Whether these intuitions are correct or not, what the protocol effectively does (very well) is force an attacker to target an individual users device to get message cleartext, as even if an implementor made a bunch of mistakes, the diversity of keys across senders and recipients makes passive mass surveillance impractical.

IMHO, the most economical "mass," attack against it would be to identify its messages on the wire, then auto-exploit the endpoint devices, install screen grabbing spyware, and harvest that data. Hardly passive or scaleably undetectable.

Nice.

badrabbit• 8 years ago

Am I correct in my understanding that a mitm attack that starts with the initial messages could work and the only way to prevent this is to verify the safety number out of band?

chimeracoder• 8 years ago

Am I correct in my understanding that a mitm attack that starts with the initial messages could work and the only way to prevent this is to verify the safety number out of band?

That's pretty much inherent to any E2E encrypted system. You have to have one of:

    1) out-of-band verification
    2) a trusted party for verifying the identities for the initial key exchange
    3) a set of (multiple) trusted parties for verifying the identities for initial key exchange.

(3) is what PGP does with the web-of-trust. It's conceptually secure, but the user experience has proven to be an utter disaster. For the form factor that Signal is addressing (mobile-only[0], intended to be used by people who expect the same level of user experience as WhatsApp provides), it's much better to go with a combination of (1) and (2).

[0] yes, there's a desktop app, but it's not recommended, and you still need to do initial setup on a phone

Cieplak• 8 years ago

Why try to break the protocol, when you can just SSH into the endpoint and read the keys and plaintext directly?

A Formal Security Analysis of the Signal Messaging Protocol (2017) [pdf]

Related Stories