[guardian-dev] Messaging Moving Forward

[Jacob Appelbaum]

Michael Rogers:
> On 18/05/13 19:11, Hans-Christoph Steiner wrote:
> 
>> I like the general idea of the actual contact address being
>> something that changes frequently, and is then communicated to
>> contacts when there is a live connection between them, something
>> like "next time we talk, call me at 987239871ef1b123b".  There are
>> two hard problems here:
> 
>> 1) how do you find new contacts?  If you give a new contact the
>> address 908a80a8b10810fe0, then you need to keep that one active
>> until that contact makes the connection.  What if they never do, or
>> it takes them a few months? Then you have something that is
>> basically the same as the standard long-lived registration.
> 
>> 2) what about contacts that are not regularly talking to each
>> other?  Or there is a long gap in correspondance?  Its again the
>> problem above, you need to keep a long lived ID, otherwise you'll
>> loose contact.
> 

I actually have a draft paper that solves this exact problem. I've been
working on this problem for a few years in my spare time. I didn't
submit it to FOCI this year as I had planned because of other commitments.

I've been calling it PANDA.

Going Dark: Phrase Automated Nym Discovery Authentication
                          or,
Finding friends and lovers using the PANDA protocol to re-nymber after
everything is lost.

"We consider the problem of two parties seeking to establish secure
communications given only a shared secret. Communication between two
parties relies on in-band and out-of-band methods when addressing
identifiers change. We propose a system by which a pair or a group
of people or machines may derive new identifiers using only a password
or shared key. Thus we remove the requirement that any new communication
must occur before re-establishing entirely new identifiers.

Working code for the general idea is here:

  https://github.com/agl/panda
  https://github.com/agl/panda/blob/master/panda.go

"Package panda implements the PANDA key agreement protocol.

"PANDA is a protocol for two parties in possession of a shared secret to
exchange a short message (e.g. a public key) asynchronously. In order
for the process to be asynchronous, a server is assumed to exist which
accepts messages posted with a binary 'tag' and returns another message,
if any, posted to the same tag. Posting the same message to the same tag
is idempotent. The server should not evict one of the two messages
posted to a tag if a third is presented. Rather the third attempt should
be rejected until the tag is garbage collected after, say, a week.

"The shared secret is assumed to be human memorable over the span of a
few days. It's processed with an expensive scrypt invocation to make it
hard to brute-force as it cannot be salted. Additionally, PANDA is a two
round protocol. In the first round, an iteration of SPAKE2 is performed
to establish a shared key and, in the second round, that shared key is
used to pass the messages.

"This means that the messages cannot be decrypted after the fact by
brute-forcing the human-memorable secret. That is only valuable to an
attacker during the course of an exchange.

Though at the moment in our paper, we've switched to EKE2 rather than
SPAKE2. I've also started a patch for Pond[0] that allows people to meet
via PANDA.

The idea is generalized into various forms of discovery, we cover how
people generally solve the discovery problem at the moment - physically,
socially, technically, etc. We also cover some ideas for distributed
renymbering as well as ways to apply it to semi-centralized systems or
even centralized systems.

> I guess you could take an approach similar to the one used for forward
> secrecy in Briar: each pair of contacts would establish a shared
> secret and use it to generate identical pseudo-random sequences, from
> which they could derive each other's temporary identities for any
> given period.
> 
> So Alice and Bob would both know that on 20 May 2013, Alice would be
> dvnbwvveirbvhbrjshdgebok at example.com and Bob would be
> jahgkjgdkjadvbjhbvekwrbc at example.org, but nobody else would be able to
> link those identities to Alice and Bob's other temporary identities.
> 
> (Someone wiretapping the conversation would, however, be able to tell
> that Alice and Bob were using the same long-term OTR keypairs.)
> 

That doesn't seem right - the outside[1] of an OTR connection is an
anonymous DH. How does someone see the long term keys by wiretapping?

All the best,
Jake

[0] https://github.com/agl/pond/
[1] http://www.cypherpunks.ca/otr/Protocol-v3-4.0.0.html