Subject: [xmpp] Some Thoughts on E2E Directions

From: Matt Miller <[email-masked]>
Date: Tue, 24 Jan 2012 08:47:26 -0700

In working more on the end-to-end encryption proposals, I have some concerns about the current direction.  To recap the proposal-in-progress:

* sender encrypts stanza using message cipher
* for each known-good public key for the recipient, sender encrypts message key
* sender generates a single stanza, which contains the encrypted data + all message key encryptions:

<message  xmlns='jabber:client'
         from=[email-masked]/balcony'
         id='6410ed123'
         to=[email-masked]'
         type='chat'>
 <e2e   xmlns="urn:ietf:params:xml:ns:xmpp-objenc:0">
   <key    cipher-algo="RSAES-OAEP-SHA-256-MFG1"
           id="recipient-key-1">
     OPfr4zudqiEeLcOQazZJIB6B9gx3zrVbyHKTU8a/aDb0wiZevztxxCi8hto0+Qw
     Foyhcupj547WbFZJNlB2dsAPhlJzeH9SuGLJShjhbkOyKjmqZLLCZr3OQtJjcTU
     sAVj7IZZsOOPDmwsb4Dxv5sz+icsDpi5l+5APfthDaoHbcrvz2pA1CJ5IFQoob4
     a0i0WevcAFyB+vWXsRqQCxjn5sHdb6G4vjQ/m1lzTWahzKvi56pNUm7ll18oI8L
     mPi1VWUEqH3aayGLVlJ9fhBDSSpW4jTQ/ts1nzPJwVlKdTqdgNBusFEhrRMhJD5
     1JdLOhxx+Ov2Xbs22++XQ1tS8/A==
   </key>
   <key    cipher-algo="RSAES-OAEP-SHA-256-MFG1"
           id="recipient-key-2">
     OPfr4zudqiEeLcOQazZJIB6B9gx3zrVbyHKTU8a/aDb0wiZevztxxCi8hto0+Qw
     Foyhcupj547WbFZJNlB2dsAPhlJzeH9SuGLJShjhbkOyKjmqZLLCZr3OQtJjcTU
     sAVj7IZZsOOPDmwsb4Dxv5sz+icsDpi5l+5APfthDaoHbcrvz2pA1CJ5IFQoob4
     a0i0WevcAFyB+vWXsRqQCxjn5sHdb6G4vjQ/m1lzTWahzKvi56pNUm7ll18oI8L
     mPi1VWUEqH3aayGLVlJ9fhBDSSpW4jTQ/ts1nzPJwVlKdTqdgNBusFEhrRMhJD5
     1JdLOhxx+Ov2Xbs22++XQ1tS8/A==
   </key>
   <data   cipher-algo="AES-256-CBC-PKCS5-WITH-IV"
           mac-algo="HMACSHA256"
           mac-data="HSGmwUFd4sESB+O12S32xsXVvMnO4gjRPaQITIrjWbs=">
     a8zpjgRcO1VHZ9CoqU19/jB7nn58Gzu5/sQm8YQe4F9zz+YKUfqTS9LaHcqdAwa
     z8BG1a24Z72VYb5Ptjh7nQ19f5QQdA/P4lZ3oqeTJTsA4DkhvJaSUhrjYib/NOk
     3lkMoatR/OSbfvhPdqXQ/dutLuRFjkilXGVwNWkgLm3iSnKUiYSdUzWvj88RgR3
     ldVHFeyrdgufU9qu/FyO6MZXjfEtD80O+3ZBbESqllzmYFXnfkzBrhfi14iCba6
     /b5Io5zhFUyWaq5e6qq2z72a+1bjeWkG8F9XBiMkyaxkB64wAS0o6aDpWdir5Oi
     +Rnms4LV/wxL4Is/oe8Fo9xR3UmrdlAiaehdGBh+EnJGqprKa9eccOKqSu7/lJQ
     ObAdJGEOeAVs8JEkQkxw+qR8edkEDuv6ZXN7JCWQx9LNaiiwsfAzApJJbqfrtDx
     koQ3JaBbxQ+8FE3TM0E4Tbr9V8NDZC8abgBramlpUBfgknJvLYMTzx1lnsiCUxo
     6ezC0xqV
   </data>
 </e2e>
</message>

The concerns I have are:

* it makes the public key management problem worse, not better
* it makes for a very large stanza, most of which has no use to the recipient(s)

So, an approach I'm starting to look at is the following alternative:

* sender encrypts stanza using message cipher
* sender generates a single stanza, which contains the encrypted data ONLY:

<message  xmlns='jabber:client'
         from=[email-masked]/balcony'
         id='6410ed123'
         to=[email-masked]'
         type='chat'>
 <e2e   xmlns="urn:ietf:params:xml:ns:xmpp-objenc:1">
   <data   cipher-algo="AES-256-CBC-PKCS5-WITH-IV"
           mac-algo="HMACSHA256"
           mac-data="HSGmwUFd4sESB+O12S32xsXVvMnO4gjRPaQITIrjWbs=">
     a8zpjgRcO1VHZ9CoqU19/jB7nn58Gzu5/sQm8YQe4F9zz+YKUfqTS9LaHcqdAwa
     z8BG1a24Z72VYb5Ptjh7nQ19f5QQdA/P4lZ3oqeTJTsA4DkhvJaSUhrjYib/NOk
     3lkMoatR/OSbfvhPdqXQ/dutLuRFjkilXGVwNWkgLm3iSnKUiYSdUzWvj88RgR3
     ldVHFeyrdgufU9qu/FyO6MZXjfEtD80O+3ZBbESqllzmYFXnfkzBrhfi14iCba6
     /b5Io5zhFUyWaq5e6qq2z72a+1bjeWkG8F9XBiMkyaxkB64wAS0o6aDpWdir5Oi
     +Rnms4LV/wxL4Is/oe8Fo9xR3UmrdlAiaehdGBh+EnJGqprKa9eccOKqSu7/lJQ
     ObAdJGEOeAVs8JEkQkxw+qR8edkEDuv6ZXN7JCWQx9LNaiiwsfAzApJJbqfrtDx
     koQ3JaBbxQ+8FE3TM0E4Tbr9V8NDZC8abgBramlpUBfgknJvLYMTzx1lnsiCUxo
     6ezC0xqV
   </data>
 </e2e>
</message>

* Recipient requests message cipher information, providing its public key:

<iq xmlns="jabber:client"
    from="[email-masked]/garden"
    id="41a313f2bc"
    to="[email-masked]/balcony"
    type="get">
  <keyreq xmlns="urn:ietf:params:xml:ns:xmpp-objenc:1">
    <pubkey>
        OPfr4zudqiEeLcOQazZJIB6B9gx3zrVbyHKTU8a/aDb0wiZevztxxCi8hto0+Qw
        Foyhcupj547WbFZJNlB2dsAPhlJzeH9SuGLJShjhbkOyKjmqZLLCZr3OQtJjcTU
        sAVj7IZZsOOPDmwsb4Dxv5sz+icsDpi5l+5APfthDaoHbcrvz2pA1CJ5IFQoob4
        a0i0WevcAFyB+vWXsRqQCxjn5sHdb6G4vjQ/m1lzTWahzKvi56pNUm7ll18oI8L
        mPi1VWUEqH3aayGLVlJ9fhBDSSpW4jTQ/ts1nzPJwVlKdTqdgNBusFEhrRMhJD5
        1JdLOhxx+Ov2Xbs22++XQ1tS8/A==
    </pubkey>
  </keyreq>
</iq>

* If accepted, sender provides message cipher information, encrypted using provided public key:

<iq xmlns="jabber:client"
    from="[email-masked]/balcony"
    id="41a313f2bc"
    to="[email-masked]/garden"
    type="result">
  <keyreq xmlns="urn:ietf:params:xml:ns:xmpp-objenc:1">
    <msgkey cipher-algo="RSAES-OAEP-SHA-256-MFG1">
        OPfr4zudqiEeLcOQazZJIB6B9gx3zrVbyHKTU8a/aDb0wiZevztxxCi8hto0+Qw
        Foyhcupj547WbFZJNlB2dsAPhlJzeH9SuGLJShjhbkOyKjmqZLLCZr3OQtJjcTU
        sAVj7IZZsOOPDmwsb4Dxv5sz+icsDpi5l+5APfthDaoHbcrvz2pA1CJ5IFQoob4
        a0i0WevcAFyB+vWXsRqQCxjn5sHdb6G4vjQ/m1lzTWahzKvi56pNUm7ll18oI8L
        mPi1VWUEqH3aayGLVlJ9fhBDSSpW4jTQ/ts1nzPJwVlKdTqdgNBusFEhrRMhJD5
        1JdLOhxx+Ov2Xbs22++XQ1tS8/A==
    </msgkey>
  </keyreq>
</iq>

I think this one deals with the key management problem better than my original proposal, and still has a chance to survive offline (e.g. the recipient comes online before the sender goes offline).  It's more individual stanzas, but less irrelevant data per stanza, which I think is an acceptable tradeoff.

I'm starting on a draft for my current direction; the specifics still need to be fleshed out, but I think this provides enough information we can start talking about it.

Thoughts?

- m&m

Matt Miller - <[email-masked]>
Collaboration Software Group - Cisco Systems, Inc.

---

From: Ben Campbell <[email-masked]>
Date: Tue, 24 Jan 2012 10:09:37 -0600

(As individual, with apologies in advance if I rehash things already discussed)

On Jan 24, 2012, at 9:47 AM, Matt Miller wrote:

> I think this one deals with the key management problem better than my original proposal,

Can you elaborate on that?

> and still has a chance to survive offline (e.g. the recipient comes online before the sender goes offline).

That's not really an offline case then, is it? (Assuming the key request is e2e--does it have to be?)

>  It's more individual stanzas, but less irrelevant data per stanza, which I think is an acceptable tradeoff.

I infer from your overall wording we are talking about single-recipient cases, right? I don't recall, is MUC in scope?

The amount of data is based on the number of public keys per target recipient, right? And the relevancy of that data is based on whether the recipient tries to read the message using any particular public key? How many public keys do we expect, on average, a recipient to have?

---

From: Matt Miller <[email-masked]>
Date: Tue, 24 Jan 2012 12:24:35 -0700

> Can you elaborate on that?

I think it's better because, instead of the sender guessing which of the recipient's public keys to use, the send is told by the recipient which key (or maybe keys) to use.

It doesn't completely solve the problem, but it narrows the window of possibilities.

> That's not really an offline case then, is it? (Assuming the key request is e2e--does it have to be?)

I'm not sure I would necessarily qualify the key request as e2e, but am willing to accept different interpretations.

> I infer from your overall wording we are talking about single-recipient cases, right? I don't recall, is MUC in scope?

I have been concentrating on single-recipient, where "single-recipient" refers to the concept of a user (or something similar), which can have multiple end-points that represent or approximate that user.

I don't remember if MUC is strictly in scope, either.  At this point, I'm trying to not preclude it, and hoping for the best.

> The amount of data is based on the number of public keys per target recipient, right? And the relevancy of that data is based on whether the recipient tries to read the message using any particular…

The amount of data is based on the number of public keys per target recipient.  I don't have hard numbers here, but I have a need for at least 5 (desktop + mobile phone + tablet + 2 XMPP-enabled web apps), and the last two are ephemeral enough that it's possible to approach 10's of keys; the web-app needs to generate and publish a key-pair because it can't utilize any previous.

I'm not entirely sure how much of a problem size will really be, but I am concerned about the amount of wasted effort on the part of the sender (lots of encryption == lots of cycles, lots of wasted encryption == lots of wasted cycles).  It could be an interesting attack...

- m&m

---

From: Alexander Holler <[email-masked]>
Date: Thu, 26 Jan 2012 05:00:16 +0100

> * sender generates a single stanza, which contains the encrypted data ONLY:
...
> * Recipient requests message cipher information, providing its public key:
...

> Thoughts?

If a recipient has to dial back, than why sending any encrypted data at
all in the first step? A digest or something similiar would be enough
for the recipient to pull the message later on.

Regards,

Alexander

---

From: Peter Saint-Andre <[email-masked]>
Date: Wed, 25 Jan 2012 21:11:19 -0700

> for the recipient to pull the message later on.

Interesting. That would be similar to IM2000:

http://cr.yp.to/im2000.html

Peter

-- 
Peter Saint-Andre
https://stpeter.im/

---

From: Alexander Holler <[email-masked]>
Date: Thu, 26 Jan 2012 05:24:56 +0100

> http://cr.yp.to/im2000.html

Thinking further it will end in a pubsub-extension. ;)

Regards,

Alexander

---

From: Greg Troxel <[email-masked]>
Date: Thu, 26 Jan 2012 08:15:48 -0500

An additional concern is the lack of perfect forward secrecy.  Given
that xmpp is often interactive, PFS seems achievable.  And, it seems to
me that e2e encryption without PFS risks appearing to give users more
confidentiality than they actually get.

---

From: Matt Miller <[email-masked]>
Date: Thu, 26 Jan 2012 07:59:58 -0700

> confidentiality than they actually get.

The concern is noted.  I don't think there's enough with my latest strawman to declare PFS failure or success yet.

- m&m

---

From: Matt Miller <[email-masked]>
Date: Thu, 26 Jan 2012 08:20:54 -0700

> for the recipient to pull the message later on.

Part of my reasoning is the follow-on <message/>s as other end-points for the recipient (and possibly the sender!) become available.  I would like the flow for "cold start" to be as similar to "arrives in the middle" as possible.  And, yes, I do realize that wording probably makes it sound scarier that it actually is.

This is because there are XMPP technologies in development and use that fork messages across all available non-negative resources, such as Carbons[1].  There's also MUC[2], which it would be nice if the e2e work extended into it without significant changes.

- m&m

[1] XEP-0280: Message Carbons <http://xmpp.org/extensions/xep-0280.html>
[2] XEP-0045: Multi-User Chat <http://xmpp.org/extensions/xep-0045.html>

---

From: "Richard L. Barnes" <[email-masked]>
Date: Thu, 26 Jan 2012 10:21:19 -0500

I wonder if PFS is actually worth the cost in this case.  It seems like in the great majority of cases, the private key is going to reside on the same device as possible plaintext message logs.  So if an attacker gets access to the private key (other than by cryptanalysis) then he could have stolen the logs anyway.  Even without PFS, then, the security considerations are the same as before -- if you want forward secrecy, delete the messages.

OTOH, the cost is an additional RTT with each recipient with a few KB of crypto payload.  Seems like that could get expensive quickly.

Just a thought,
--Richard

On Jan 26, 2012, at 9:59 AM, Matt Miller wrote:

> _______________________________________________
> xmpp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/xmpp

---

From: Greg Troxel <[email-masked]>
Date: Thu, 26 Jan 2012 10:27:56 -0500

"Richard L. Barnes" <[email-masked]> writes:

> I wonder if PFS is actually worth the cost in this case.  It seems
> like in the great majority of cases, the private key is going to
> reside on the same device as possible plaintext message logs.  So if
> an attacker gets access to the private key (other than by
> cryptanalysis) then he could have stolen the logs anyway.  Even
> without PFS, then, the security considerations are the same as before
> -- if you want forward secrecy, delete the messages.

Agreed - obviously you have to not keep logs.  I was thinking of the no
log case, since I don't log xmpp.

That raises the question of whether there should be the equivalent of an
X-No-Archive: flag to ask that counterparties not log.  Obviously that's
not enforceable, but it may make sense for an implementation that
doesn't respect that to be deemed noncompliant.

> OTOH, the cost is an additional RTT with each recipient with a few KB
> of crypto payload.  Seems like that could get expensive quickly.

With pairwise chat (vs conferencing), the cost seems quite low (in my
own use of OTR), one extra RTT per conversation/client restart.  With
multiparty conferencing, then it could be more expensive, and the
security gains of PFS are perhaps illusory anyway.  (Sorry if I jumped
into a multi-party thread with two-party assumptions.)

---

From: "Richard L. Barnes" <[email-masked]>
Date: Thu, 26 Jan 2012 10:38:07 -0500

> I think it's better because, instead of the sender guessing which of the recipient's public keys to use, the send is told by the recipient which key (or maybe keys) to use.

It seems like these two mechanisms don't necessarily have to be mutually exclusive.  You can send to recipients for which you have cached keys immediately, then keep this "I would like the key" interface open to allow additional recipients.  

In the first case, maybe you could optimize a little over the base case with the following pattern:

1. Sender sends message keys to each recipient with a known key, along with a digest of the message they go along with.
<key cipher-algo="RSAES-OAEP-SHA-256-MFG1"
     id="recipient-key-1"
     msgid="580CCA51-9AA7-4BB0-817D-ADB3C1A9EFBC"
     digest="di:sha-256;B_K97zTtFuOhug27fke4_Zgc4Myz4b_lZNgsQjy6fkc">
...
</key>

2. Sender sends message content multicast to all recipients
<data id="580CCA51-9AA7-4BB0-817D-ADB3C1A9EFBC"
      cipher-algo="AES-256-CBC-PKCS5-WITH-IV"
      mac-algo="HMACSHA256"
      mac-data="HSGmwUFd4sESB+O12S32xsXVvMnO4gjRPaQITIrjWbs=" >
...
</data>

That way:
  * Key blocks only get sent to target recipients
  * No additional stanzas for key exchange when keys known

--Richard

---

From: Alexander Holler <[email-masked]>
Date: Thu, 26 Jan 2012 17:05:17 +0100

Am 26.01.2012 16:20, schrieb Matt Miller:
> Part of my reasoning is the follow-on<message/>s as other end-points for the recipient (and possibly the sender!) become available.  I would like the flow for "cold start" to be as similar to "arrives in the middle" as possible.  And, yes, I do realize that wording probably makes it sound scarier that it actually is.
>

Hmm, carbon is new for me, thanks for the pointer. Have to read that.

But in regard to MUC I don't see a problem (at a first glance) if just 
hashes would send around, while leaving the content on the senders 
server until the recipient actually decides to fetch it.

But I've missed the beginning of the discussion about e2e, and don't 
know what are all the targets of it.

The problem (with the im2000-concept) would be to decide how long the 
content is stored, but that looks for me somewhat comparable to decide 
how long the message cipher is available (and to whom) in your approach.

Regards,

Alexander

---

From: Matt Miller <[email-masked]>
Date: Thu, 26 Jan 2012 10:38:36 -0700

On Jan 26, 2012, at 09:05, Alexander Holler wrote:

> But in regard to MUC I don't see a problem (at a first glance) if just hashes would send around, while leaving the content on the senders server until the recipient actually decides to fetch it.
> 

That sounds like a pretty radical change to the XMPP infrastructure.  I'd really like to avoid that if at all possible.

> But I've missed the beginning of the discussion about e2e, and don't know what are all the targets of it.
> 
> The problem (with the im2000-concept) would be to decide how long the content is stored, but that looks for me somewhat comparable to decide how long the message cipher is available (and to whom) in your approach.
> 

There might be some comparisons, and we can see glance in occasionally on where that's going.

- m&m

---

From: Matt Miller <[email-masked]>
Date: Thu, 26 Jan 2012 14:37:58 -0700

>  * No additional stanzas for key exchange when keys known

This seems reasonable.  As long as we're not relying on keys being known-good (which the original proposal did).

- m&m

---

From: "Richard L. Barnes" <[email-masked]>
Date: Thu, 26 Jan 2012 16:44:53 -0500

For what definition of "good"?  Are you worried about someone unauthorized getting a message, or someone getting a message with a key the can no longer use (e.g., rollover, different device)?

The first definition is definitely a type of goodness we should require (key belongs or belonged to the right party). I agree the second is more difficult; that's where the dialback mechanism would be helpful ("Oops, you used the wrong key").

I do have to say, though, that the dialback mechanism does creep me out a little bit.  You need to know that the person asking for a key is the right person -- it's  not secure to just accept a public key because it came in a message from someone, but if you already know a key for someone you could have just used it in the first place.  So there's a residual need for some other authentication step here to bootstrap the public key distribution.

--Richard

---

From: Matt Miller <[email-masked]>
Date: Thu, 26 Jan 2012 15:03:11 -0700

> The first definition is definitely a type of goodness we should require (key belongs or belonged to the right party). I agree the second is more difficult; that's where the dialback mechanism would…

I am most concerned with the latter case.  This is a case that can happen in web-based applications, a lot.

> I do have to say, though, that the dialback mechanism does creep me out a little bit.  You need to know that the person asking for a key is the right person -- it's  not secure to just accept a pub…

Well, some mitigation can be done with the addresses; if the 'from' bare-JID of the keyreq doesn't match the 'to' bare-JID of the data stanza (or 'me' in the case of Carbons), the request MUST be rejected.  After that, I'm open to suggestions.

- m&m