On 29/12/13 02:17, Trevor Perrin wrote: > Hi Ximin, > > I think this has worse forward-secrecy than Axolotl [1]. > > Suppose Alice sends a stream of messages (M1, M2, M3) to Bob. With > Axolotl, Bob destroys the key for each message immediately after > decrypting the message. > > With your ratchet, Bob cannot do this, since (M1, M2, M3) are all > encrypted to Bob's same secret keys. >
Hm, you are right. I originally was only thinking about the derived message key. But a network attacker who has sniffed the traffic, i.e. who has A's per-message ephemeral keys (g^ephemeral secret), and later compromises B's ephemeral secret, can re-derive the message keys for all of M1, M2, M3. It does have better future-secrecy properties, but this is much less important than forward-secrecy, since real-world compromises presumably have the ability to compromise those future "healed" keys too. George Kadianakis later mentioned to me that there might have been an impossibility result for 1-step ratchets (he can't remember), does that bring anything to mind for you? (If not, then I might keep trying. :p) > As far as using a TripleDH instead of a single DH for each ratchet > message: we decided against that, since it makes key rollover harder. > Alice might periodically wish to destroy her old identity key and > introduce a new one, and it seemed better for this not to interrupt > all of Alice's conversations. > OK, I see now. This way, the long term keys are only needed at the start; the security of the rest of the conversation only depends on recent history. Thanks for the comments! IIRC, there was some confusion on when it's important to destroy the secret - I was originally thinking that we should destroy it vaguely "as soon as possible" after sending the corresponding g^secret, leading to my note #3. But the critical thing for optimal forward-secrecy is to destroy it precisely after using it to decrypt *one* message, and also to convince the other participants to only use g^secret for *one* encryption. X > Trevor > > [1] https://github.com/trevp/axolotl/wiki > > > > On Sat, Dec 28, 2013 at 2:49 PM, Ximin Luo <[email protected]> wrote: >> I realise how this must sound; I am sure I made a mistake somewhere. :) >> >> I *have* spotted one irregularity which *potentially* could lead to a >> side-channel attack; please read on. >> >> But if I got everything right, it does provide deniability and >> forward-secrecy. >> >> ## 2-party case >> >> No key agreement - I am not trolling! (But note #1 talks about >> initialisation, a special case.) >> >> Transmitter T sends a message M with msgID i to receiver R. >> M = (g^ephem_sec_of_T, P = parents of M, AuthEnc[k](P, plaintext)); i = >> hash(M) >> >> - A new random ephem_sec_of_T is generated for each message, and is stored >> until as described in note #3. >> - k is generated via 3DH as below. >> - The parents point to the last non-replied-to messages that T knows about, >> similar to OldBlue[3] and git. >> - This lets us reduce the 2-step Axolotl ratchet[2] to a 1-step 3DH[1] >> ratchet; the recipient can infer k too. >> - In the 2-party case, there is only one parent; I say parents because >> this generalises to mpOTR - see later. >> - plaintext P is a potential problem, even though it is also under AuthEnc >> - P must be plaintext to infer k in the first place >> - P must also be AuthEnc, since multiple P can lead to the same k >> - would be good to prove this is safe >> >> R executes the following, to verify-decrypt the ciphertext: >> >> 1. In the 2-party case, P contains one single ID, sent by R. Find the >> message with this ID, it contains an g^ephem_sec_of_R. >> 2. Find ephem_sec_of_R, stored from earlier. >> 3. Generate k using 3DH[1]: >> k = KDF ( g^ephem_sec_of_T ^ ID_KEY_of_R, >> g^ephem_sec_of_R ^ ID_KEY_of_T, >> g^ephem_sec_of_T ^ ephem_sec_of_R ) >> assuming all public ID_KEYs are validated, this protects against MitM >> 4. Verify-decrypt using k. >> >> Non-rigorous justification ("pseudo-proof") for security: >> - auth/conf from AuthEnc[k] - k is known only to R, T >> - assuming plaintext P is OK >> - fwd-sec from per-message g^ephem_sec_of_T, plus forgetting keys as per >> note #3 >> - deniability from 3DH, all values are forgeable, no signatures anywhere >> - no "initial key agreement" necessary (but see note #1) >> >> 3DH, OldBlue and Axolotl work together to protect against MITM, provide den, >> fwd-sec, and auth/conf. >> >> ## Multi-party case >> >> - Naive extension: T needs to generate a k for each recipient, and AuthEnc >> for each. This is not as efficient as we'd like. >> - also, probably better to let i = hash(g^ephem_sec_of_T, P, plaintext) >> - each R finds the correct ephem_sec_of_R by following P's ancestors until >> it finds a message authored by itself. >> - This message is unique, even when each message may have multiple >> parents, due to the consistency properties of OldBlue DAG transcripts - >> messages from one single author are totally-ordered, it is the full >> transcript that is only partially-ordered. >> - pairwise keys only, no group handshake >> >> ## Notes >> >> 1. To ensure there is always a "last-sent-message", we can start a convo >> with everyone announcing their first g^ephem_sec. This means we need to wait >> for everyone before the conversation can begin; this potentially can be >> improved. >> 2. As-described, there is no concept of "a conversation", so you can't have >> 2 separate conversations with the same set of participants. We can easily >> add a channel-id for each message, though. This can be picked by the >> conversation initiator. >> 3. T needs to keep each ephem_sec_of_T until they know that all recipients >> have received and verified his message, in case he must resend it. This can >> be done by waiting until (r sends a message with M as an ancestor, for all >> r). >> >> ## Story >> >> - George Danezis asked me how Paxos worked. I asked why he was asking the >> question (since nobody solves byzantine just for the sake of it :p) and he >> mentioned mpOTR. >> - I remembered the previous otr-dev discussion about consistency, and how >> the DAG transcript turns consistency into a non-byzantine problem. "I don't >> need to rely on others to act myself." >> - We need a 1-step ratchet to turn key agreement into a non-byzantine >> problem. I started reading up on the Axolotl algorithm. >> - An initial misunderstanding had me modelling that protocol with a 3DH >> ratchet rather than a DH ratchet. >> - I eventually realised it could be turned into the above algorithm. >> >> [1] https://whispersystems.org/blog/simplifying-otr-deniability/ >> [2] https://whispersystems.org/blog/advanced-ratcheting/ >> [3] http://matt.singlethink.net/projects/mpotr/oldblue-draft.pdf >> >> -- >> GPG: 4096R/1318EFAC5FBBDBCE >> git://github.com/infinity0/pubkeys.git >> >> >> _______________________________________________ >> OTR-dev mailing list >> [email protected] >> http://lists.cypherpunks.ca/mailman/listinfo/otr-dev >> -- GPG: 4096R/1318EFAC5FBBDBCE git://github.com/infinity0/pubkeys.git
signature.asc
Description: OpenPGP digital signature
_______________________________________________ OTR-dev mailing list [email protected] http://lists.cypherpunks.ca/mailman/listinfo/otr-dev
