[messaging] Axolotl: Lacking deniability or MITM?

[Daniel Kahn Gillmor]

On 11/24/2014 04:47 PM, Alexey Kudinkin wrote:

> Cruising around Axolotl spec recently, i’ve just stumbled upon one grit constantly disturbing me:
> 
> https://whispersystems.org/blog/simplifying-otr-deniability/ <https://whispersystems.org/blog/simplifying-otr-deniability/>
> 
> Chapter dubbed “Potential Simplifications and Improvements” lists all the gains of replacement of OTR’s original handshake involving DSA, with 
> “Triple DH” involving just both sides’  identity keys (A and B) and ephemeral keypairs (a and b).
> 
> What confusing me is two following statements:
>> Reduced Algorithmic Complexity. We’ve eliminated DSA and have a nice authenticated key exchange that relies solely on the simplicity of Diffie-Hellman.
>> Increased Forgability. Since there are no signatures involved, anyone could take A’s public key, make up an ephemeral keypair for A (“a” in the diagram above), combine that with their own identity key and ephemeral key (“C” and “c”), and produce an entire forged transcript – even if they’ve never had a conversation with “A” before. Now anyone is capable of easily producing a forged message from anyone else, whether they’ve actually had a conversation with them before or not.
> Those two seems kinda mutually exclusive: if we do actually have an authenticated key exchange, then we’ re losing so promising statement of deniability, since any one could authenticate us during the handshake.
> The other way around, lacking authenticity, we’re making ourselves prone to MITM unless there is an established channel to verify public keys.
> 
> Have i missed something?

I think what you're missing is that authenticity and deniability have
two different "target audiences".  This means that both OTR and Axolotl
have peer authenicity and third-party deniability as part of their core
goals.  let me explain:

 * Authenticity is about one peer being able to know (with cryptographic
confidence) who the other peer is.

 * Deniability is about neither peer being able to cryptographically
prove to a third party who the other peer is.

Deniability works when either party could have forged the entire
conversation (because they know enough of the secrets involved).  For
example, in axolotl, anyone can make up two ephemeral DH keys; one of
the peers in the conversation also knows their own long-term DH key.  So
if they forge both ephemerals, and they know their own long-term secret
key, and they know their peer's long-term public key, they can make up
an arbitrary conversation.

So how does this impact authenticity?  If Alice trying to communicate
with Bob, then she knows that she must only make up one of the ephemeral
keys (and must wait to see the ephemeral public key offered by her
peer).  She then uses the two ephemeral public keys and Bob's known
long-term public key and her own long-term secret key to derive the
axolotl session keys.  The only person who could derive the same axolotl
session key is the person who knows Bob's long-term secret key.  So
Alice has authenticated Bob because *she knows she didn't make up her
peer's ephemeral key*.  But when she goes to show this information to
Carol, she has no way of proving to Carol that she didn't make up the
peer's ephemeral key.  It's simply something that she knows but can't prove.

Does this help to understand how the two concepts can co-exist in these
protocols?

	--dkg

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 949 bytes
Desc: OpenPGP digital signature
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20141124/a32abbe6/attachment.sig>