[toast0]

> So how fast does cycling happen if the server is under an attacker's control and trying to ensure that cycling is delayed as long as possible?

If you're getting bi-directional communication with your partner, you're getting key cycling. The server can only delay key cycling in a session by delaying one direction of communication.

The server can't hand out the same pre-key to multiple users, because the client will delete pre-key pairs on first use, with the exception of a "last resort" pre-key. The server could exclusively hand out the last resort pre-key to all users attempting to contact you, and refuse to accept new pre-keys. Then the first flight of messages from users establishing a new session would not be PFS, but any messages sent once you respond would have PFS.

Adding, of course, the server could also hand out incorrect keys and man in the middle all the steps; so long as users don't verify the keys. And a malicious client and server could conspire to include the correct keys for verification and the MITM keys for transport. This would be visible in the shipped code, but if the backdoored client is only distributed to a limited set of users, it wouldn't be subject to random reverse engineering like the normal client is. But I assume everybody downloads multiple copies of apks from different networks and compares to ensure they're byte identical ;)

[lmm]

> If you're getting bi-directional communication with your partner, you're getting key cycling. The server can only delay key cycling in a session by delaying one direction of communication.

That implies the client has to have a code path for sending multiple messages without cycling. And it forces a tough choice between losing messages that are received out of order and not destroying keys quite as quickly as nominally expected.

Maybe it's fine, but for me it pushed the complexity threshold over the point where I could feel any confidence in it. I'm comfortable with traditional PKI. I'm comfortable with the online-only OTR/axolotl ratchet. But I'm very dubious of having this many edge cases.

> The server could exclusively hand out the last resort pre-key to all users attempting to contact you, and refuse to accept new pre-keys. Then the first flight of messages from users establishing a new session would not be PFS, but any messages sent once you respond would have PFS.

Assuming there's no way for the client to end up on the initial-message codepath.

Again, yeah, maybe it's fine. But it all just feels so hacky and fiddly. These edge cases aren't where anyone studying the protocol is going to spend any time, but it's security-critical that they be implemented right.

[bjoli]

I just re-read your message, and thought I should clarify: The client has two ratchets going. One is an opportunistic DH ratchet, and the other is a hash-based one that provides forward secrecy if the contents of the last DH ratchet was not intercepted and decrypted. Which, if you have verified the keys and no device key change has happened, it hasn't.

If you have a successful compromise of one message, a missed message is all it takes for the ratchet to self-heal and you have lost the ability to decrypt future messages. It is PFS+ in a sense.