Introduction to the EGTP version 2 Architecture:

document version 0.0.1

I. Background Material

I will not assume that you have read the following, but I do recommend them.

A. General Crypto Reference

 * Menezes, van Oorschot, Vanstone.  Handbook of Applied Cryptography 1996
http://www.cacr.math.uwaterloo.ca/hac/

B. General Crypto Protocol Design

 * Anderson. Why cryptosystems fail. Communications of the ACM, 
37(11):32--40, November 1994. 
http://citeseer.nj.nec.com/anderson94why.html

 * Abadi and Needham. 1996. Prudent engineering practice for 
cryptographic protocols. IEEE Trans. Softw. Eng. 22, 1 (Jan.), 6-15. 
http://citeseer.nj.nec.com/abadi95prudent.html

 * Anderson and Needham. "Programming Satan's Computer", in 
Computer Science Today, Springer LNCS v 1000 pp 426--441 
http://citeseer.nj.nec.com/22376.html

C. Replay Attacks/Active Attacks

 * Syverson. A taxonomy of replay attacks. In Computer Security Foundations 
Workshop VII. IEEE Computer Society Press, 1994.
http://citeseer.nj.nec.com/syverson94taxonomy.html 

[Zooko: write argument that EGTPv2 addresses all classes from this taxonomy.  
See if Paul Syverson will review it for you. --Zooko]

 * Aura. "Strategies Against Replay Attacks" 1997
http://citeseer.nj.nec.com/aura97strategies.html

 * Gong. Variations on the Themes of Message Freshness and Replay or, the 
Difficulty of Devising Formal Methods to Analyze Cryptographic Protocols. In 
Proceedings of the Computer Security Foundations Workshop VI, pages 131--136. 
IEEE Computer Society Press, Los Alamitos, California, 1993.
http://citeseer.nj.nec.com/gong93variations.html

D. Fail-Stop/Constructive Approaches

 * Gong and Syverson. Fail-stop protocols: An approach to designing 
secure protocols. In R. K. Iyer, M. Morganti, Fuchs W. K, and V. Gligor, 
editors, Dependable Computing for Critical Applications 5, pages 79--100. IEEE 
Computer Society, 1998.
http://citeseer.nj.nec.com/gong95failstop.html

[Zooko: write argument that EGTPv2 implements full fail-stop/fail-safe layer 
and any application-level user of EGTPv2 that uses EGTPv2 solely through 
EGTPv2's API automatically has a fail-stop/fail-safe protocol.  See if Li Gong 
and Paul Syverson will review it for you. :-)  ...  Also explain the subtle 
relation to SSL replay protection, state management.  :-{  --Zooko]

E. Newfangled Privacy Features

 * Goldberg, Borisov, and Brewer. Off-The-Record Messaging, or 
Why Not To Use PGP, 2002
http://www.cypherpunks.ca/otr

F. EGTPv1

 * Zooko and Art. Introduction to the EGTP version 1 Architecture
http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/egtp/egtp_new/doc/Architecture.txt?rev=HEAD&content-type=text/vnd.viewcvs-markup

G. Re-inventing TLS

[I haven't read this one yet, but I will read it carefully before completing EGTPv2 design.  --Zooko 2003-09-28]
 * Ferguson and Schneier. "Practical Cryptography" book

H. Other

 *  Kelsey, Schneier and Wagner, "Protocol Interactions and the 
Chosen Protocol Attack", in Security Protocols Workshop
http://citeseer.nj.nec.com/kelsey97protocol.html

II. Desiderata

A.  Automatic Fail Stop, Retrying, and State Management

This is the semi-novel bit, and the most important distinction from other 
secure comms layers.  It is complicated, involving all three of fail-stop, 
retrying, and state management.

B.  Unify Designation and Public Key

The API requires that you pass the public key Id in order to specify which 
recipient you mean.  No doing as so many do -- allowing public key and 
"recipient Id" to get separated, and then trying to tie them back together 
later...

C.  Forward Secrecy

D.  Key-Privacy

E.  Self-Healing

If an attacker knows your secret key, and he fails to intercept a message that 
you send to your interlocutor, then he no longer knows your current secret key.

F.  Protocol-Privacy

The protocol is indistinguishable from a random bitstream to someone who 
doesn't know the decryption key.  (This requires public key privacy.)  Also, 
"Silent Bob Mode" a la Freenet -- you can't find out if a given computer 
speaks this protocol unless you provide some secret or semi-secret challenge 
(e.g. use the right public key for that computer...). 
Hm.  Actually, it is impossible to implement this efficiently as far as I can 
tell.  There is a problem with choosing which of your secrets to use in order 
to decrypt an incoming message.  We'll try to make it as close to random as 
possible, but I think we'll have to include some tag info in the clear to help 
choose which secret key to use.

G.  Deniability

E.g. Ian Goldberg and Nikita Borisov's "Off The Record Messaging"

H.  Efficiency

Most importantly: minimal round-trips.  Secondly, minimal message size.  
Thirdly, minimal computation.  Fourthly, minimal storage.  (Of course, this 
hierarchy isn't strict -- there are trade-offs that we will take...)

I.  Simplicity

It's actually going to be rather subtle, but of course we always like 
simplicity when we can have it.  In particular, there will be no "protocol 
negotiation" where I say "I like AES, DES, and Anubis" and he says "Well 
*I* like 3DES-EDE, DES, and Serpent...".

III.  Summary

[this version of the protocol offers no ordering guarantee]

This is a first-pass -- there are probably errors and omissions in the 
protocol sketched here.

LPKA = long-term public key of Alice (used for verifying signatures on 
disposable public keys and for encrypting disposable public keys)

How to bootstrap shared secret:

1.  A -> B: LPKA (this is hopefully not actually transmitted point to point 
    directly from A to B, but instead published by A, bundled with metadata, 
    contact info, reputation, etc.)
2.  B -> A: {g^x mod p, LPKB}_eLPKA_sLPKB ; x is new random secret
    (_eLPKA means it is encrypted with Alice's long term public key, _sLPKB 
    means it is signed with Bob's long-term private key)
3.  A -> B: {g^y mod p}_eLPKB_sLPKA ; y is a new random secret
    Now each side sets s1 = g^xy.  This is the first shared secret.
4.  B -> A: {msg1}_s1

This is similar to the Station to Station Protocol (see e.g. _MOV_ 
chapter 12.57).

How to have forward-secret and self-healing symmetric keys:

Whenever have sent a message to your peer and received an ACK from them, then 
change your shared secret key, something like this:

s_n+1 = hash(s_n, LPKpeer, LPKself, msg)

There are a few open issues: 1.  How to manage the multiple overlapping shared 
secrets that arise from multiple asynchronous messaging.  2.  We don't want to 
hash the entire message (not only for efficiency, but for deniability) -- 
let's transmit some new key material in each message instead, or something...

Note that as soon as you have confidence that you won't receive any more 
messages encrypted to s_n, then you should forget s_n.  Likewise, as soon as 
you have computed s_1 you should forget your DH secret exponent.

How to get that confidence is tricky, and it is an area that hasn't been 
explored in any literature that I've yet stumbled across.