A Formal Security Analysis of the Signal Messaging Protocol (2017) [pdf](eprint.iacr.org)
eprint.iacr.org
A Formal Security Analysis of the Signal Messaging Protocol (2017) [pdf]
https://eprint.iacr.org/2016/1013.pdf
5 comments
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?
> 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:
[0] yes, there's a desktop app, but it's not recommended, and you still need to do initial setup on a phone
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.
[0] yes, there's a desktop app, but it's not recommended, and you still need to do initial setup on a phone
Why try to break the protocol, when you can just SSH into the endpoint and read the keys and plaintext directly?
So there are 13 ratches, precompiled Rainbow Tables could be made to follow the decryption trail, no?
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.
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.
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.
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.