[messaging] countering active attacks against autocrypt messaging

Bryan Ford brynosaurus at gmail.com
Sun Jul 8 06:37:09 PDT 2018

Continuing feedback regarding the section 2.2 Verified Group Protocol:

In general, I’m not seeing why it’s either necessary or desirable to “roll together” the pairwise (Alice-Bob) verification workflow with the verified group-join protocol, instead of making them properly-linked but separate activities.  As currently designed, the protocol seems to make it fundamentally necessary for Alice and Bob go through the rigmarole of person-to-person device verification each time Alice wants to invite Bob to a new verified group or vice versa.  If Alice and Bob are longtime friends, which I expect and hope will be the common case especially for the most sensitive verified groups, then it seems more likely that Alice and Bob will likely already have a relationship verified via person-to-person secure connect (section 2.1), and just want to reuse or refer to that when one of them wants to invite the other to join a verified group.

In fact, the current rolled-together process seems like it’s optimized for, and perhaps even incentivizes, the less-secure behavior of inviting people to sensitive groups on first meeting them.  Suppose Alice meets Bob in-person at a meeting or party, for example, and let me try to channel Alice’s potential thought process:  “Hmmm, Bob seems interested in that topic that might make him a good potential member for this sensitive group I’m in…  But I just met him and don’t know him very well yet; I wonder if I should hold off on inviting him and first ask around to see if anyone else knows anything good or bad about him?  Oh crap, no, if I do that then Autocrypt is going to insist that I re-run that device connect rigmarole and re-verify him later once I decide to invite him to the group, and by then I’ll be back in Foozloo.  So @#$% security, I’ll just chance it and invite him to the group now.”  Maybe not really the user behavior we want to be incentivizing?

Again adopting building on ideas from my long-ago thesis work (Section 2.6 of [1]), it seems to me to make much more sense for Alice and Bob just to run the normal (section 2.1) pairwise device verification process, and then leverage that one or more times when one of them wants to invite the other to a verified group.  For example, as part of running the secure connect process, Alice and Bob might exchange self-timestamped and self-signed attestations saying “I, Alice, verified Bob at time T” and vice versa.  Both Alice and Bob store these attestations for later use.  Then, when Alice later wants to secure-invite Bob to a group, her device sends Bob an invitation - already encrypted to his public key - with the group-identification info he needs to get access to the group, and broadcasts to the other group members a message saying she’s inviting Bob and including both the most-recently-signed attestations as evidence that Alice verified Bob and vice versa.

If you’re worried about the freshness of Alice’s secure-connect with Bob, as may be reasonable, then it still seems to me that the right solution is to separate that out into a separately-enforced and perhaps configurable freshness policy.  For example, the group’s configuration might have a freshness requirement in terms of time, e.g., that for any current member to invite a new member, the two must have secure-connected with each other within the past month, or the past year.  When Alice tries to invite Bob to the sensitive group, if her most recent pair of secure-connect attestations are recent enough, her device just “does it” with no extra fuss.  If her most recent secure-connect with Bob is too old, her device tells her that and asks her to re-verify her connection with Bob afresh in order to satisfy the group’s security policy.  In any case, a more time-based freshness requirement seems to me both more secure and more usable than an arbitrary-seeming requirement of re-verifying at every secure-group-invitation event.

Now, on to other related topics...

Section 2.2.2, "More Asynchronous UI flow”: I think the UIA-like secure-connect workflow I outlined in my last E-mail can be made nearly as asynchronous and delay-tolerant as the current workflow, even though it requires user interaction at some point for confirmation (by selecting or entering ephemeral codes).  For example, phase 1 (Alice->Bob) of the secure-connect workflow is completely offline/disconnected, e.g., because Bob gets Alice’s business card with her static QR code printed on it, then Bob initiates phase 2 (vc-request Bob->Alice) later when he scans Alice’s business card at home.  Maybe he tries to call her then, but she’s not available, or he doesn’t yet try to call her because he knows she’s in a timezone where it would be a bad time for her.  Nevertheless, Alice’s and Bob’s devices can in the background go ahead with a (tentative) key-exchange process, Alice’s device sending Bob her full public-key, Bob verifying it against Alice’s fingerprint and sending her his public key, etc., leaving only the final check and confirmation using the ephemeral codes to be done later once Alice and Bob are ready.  Alice’s and Bob’s Autocrypt-enabled devices each give their respective users a sticky but non-intrusive status-indication that a secure-connect verification is waiting to be completed.  Whenever they’re ready to complete the process, either calls up the other by phone or another channel that we only trust for integrity and only ephemerally at that, and they each enter or confirm the other’s code, and they’re done.

In this background-mode workflow, perhaps with Bob’s configurable permission, Bob’s device might grant Alice’s device a dynamic online/offline indicator showing when Bob is online/available and hence when might be a good time to complete the process.  This might be the same as the usual online/offline indicator that many chat applications provide anyway, but just a temporary grant from Bob to Alice to view Bob’s online status while Bob’s connect request to Alice is outstanding.  But if Bob’s phase 2 message to Alice might be unsolicited, e.g., just from scanning a business card that Bob might as well have fished out of the dumpster, then obviously we wouldn’t want such an unconfirmed request to cause Alice’s device to grant Bob any access to privacy-sensitive information such as online status before she’s confirmed the connection.

Section 2.3: what does the “k” stand for in the “kg-“ prefix?

This history-verification mechanism again seems to conflate two conceptually separate processes unnecessarily and perhaps problematically: namely, (1) maintaining and exchanging history information, versus (2) actively verifying via an independent channel that two parties (Alice and Bob) have been seeing the same history.

Rolling parts (1) and (2) of this process together into a single sub-protocol, as currently specified, means that the verification sub-protocol will have to deal with the transfer of potentially-large lists of messages with their hashes.  What if it’s been a really long time, if ever, since they last verified their histories?  Do you add the complexity needed to the sub-protocol to break a huge batch of messages into smaller batches to be processed incrementally?  Do you need to be able to restart the processing of a batch of messages in the middle?  What if a batch of messages to be history-verified is so long that it consumes too much time, bandwidth, etc., to be practical, or it makes the freshness timeouts of the verification process expire?  Having the history-verification process incorporate a sub-protocol that potentially seems to require exchanging an unbounded amount of data just seems inherently problematic and really scary.

I think a vastly preferable approach would be to use an incremental, background-activity blockchain or ClaimChain-type mechanism for part (1) of this process, and then build part (2) on that in such a way that the actual verification process requires only a tiny amount of metadata exchange, the same as for normal secure-connect.  For example, if Alice’s and Bob’s devices have the history-verification feature enabled, then each of their devices silently accumulates (in the background) a list of messages received from the other as claims in its local ClaimChain.  Perhaps their devices wait until a sufficiently-large batch of messages is available or a given amount of time has passed, and bundle a list of received messages and their dates and hashes into a single Claim.  Then, still in the background, Alice’s device periodically sends new such Claims to Bob’s device via administrative messages.  Each time one device receives such a message-received claim, it also adds to its own chain a meta-claim with the hash of the head of its peer’s ClaimChain, thereby linking the devices’ timelines together automatically in classic hash-based vector-clock fashion.  All this happens constantly, and incrementally, without necessarily requiring any user interaction.

Then when Alice and Bob actually want to verify that they’re seeing the same view of each other’s histories, they just (re-)run more-or-less the standard secure-connect protocol, which depend on the hashes of the heads of their respective ClaimChains.  On success, this produces a new pair of secure-connect attestations that again go on the devices’ respective ClaimChains to further increase the entanglement and robustness of their respective histories.  And since the verify process only cares about ClaimChain head hashes, all messages can be small and more-or-less constant-size.

2.3.1 Device Loss:  I like the idea of enabling Alice to recover from a lost device with the help of her trusted friends in a group.  If Alice’s and Bob’s devices have been gossiping ClaimChains, for example, then perhaps Alice can recover the security-related essentials of her history by downloading it again from Bob.  But this will be tricky (the mentioned collusion attacks etc) and needs to be developed a lot further before it seems likely to be safe and usable.  Thresholds and Shamir secret sharing mechanisms and such might need to get involved somewhere.  That might be a task for a separate paper, spec, or sub-project.

Haven’t yet read section 3 on ClaimChains, so perhaps some of the above considerations are already accounted for in that part…  (If so, it would be helpful if the appropriate parts of section 2 were revised to reflect that.)


[1] Persistent Personal Names for Globally Connected Mobile Devices http://bford.info/pub/net/uia-osdi-abs.html <http://bford.info/pub/net/uia-osdi-abs.html>

> On Jun 30, 2018, at 1:00 PM, holger krekel <holger at merlinux.eu> wrote:
> Those interested in e-mail and more general messenging encryption
> security might find it interesting to read the countermitm-0.9.1 release
> of the "countering active attacks against Autocrypt" effort:
>    https://countermitm.readthedocs.io
> It discusses new key verification protocols which are implemented
> as a "Labs" feature in https://delta.chat, released to F-droid.
> It also discusses key consistency research and implementation
> efforts around https://claimchain.github.io/ .
> While the doc deliberately focuses on Autocrypt e-mail encryption
> (https://autocrypt.org) most of the results can likely be applied
> to other messengers.
> The research effort is ongoing and we'd welcome feedback
> and PRs against https://github.com/nextleap-project/countermitm
> We want to release a 1.0 version of this doc end of the year.
> Part of the work has been funded by the European Commission
> but lots is happening independently in various communities.
> holger
> _______________________________________________
> Messaging mailing list
> Messaging at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/messaging

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20180708/f2e41d64/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: Message signed with OpenPGP
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20180708/f2e41d64/attachment.sig>

More information about the Messaging mailing list