[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

A Photuris variant

This is a long note.
However, I encourage anybody interested in key management for IP
to read it. (Especially those who are going to comment on it ;-)

It presents a variation on Photuris which enjoys, in my opinion,
some advantages over the basic Photuris proposal, while keeping
the full functionality and basic goals of Photuris.
(Familiarity with Photuris, draft-karn-photuris-00.txt, is assumed).

Please send comments (no need to send directly to me if you also
send them to the list).
Phil, needless to say, your comments are a "must".


I start with a brief description and then go into commenting on the
design properties and comparison with basic Photuris.
A more detailed description of the protocol appears at the end of the
note (I am just affraid that by putting it at the beginning it will
discourage people from reading it).


For consistency with Photuris terminology,
I use I and R to denote the parties (initiator and responder).

As in Photuris, there are 6 messages exchanged between parties (in
implementation, can be collapsed to 5 by piggybacking). They correspond to
3 "phases" (with two messages each phase): Cookies, Share and

The cookies phase is identical to the cookies exchange of Photuris.

Then, in the Share phase,
the parties exchange a key K0 by each of them sending to the other
a half-key (denoted K1 and K2, resp.) each encrypted under the other's party
public key. After this phase they share a secret key K0=K1 xor K2.
The public key encryption of K1 sent from I to R is used also to encrypt
I's identity (thus, providing *anonymity*).

In the third phase, the parties perform a Diffie-Hellman exchange, where
the DH parts (g^x and g^y) are authenticated using a SYMETRIC message
authentication (or integrity check) function using the just exchanged
key K0 (keyed-MD5, for example, is such a message authentication function).
The output of the DH exchange is denoted K = g^(xy) mod p.

The public-key operation (in the Share phase) can be done using any public
key cryptosystem.  For performance considerations we assume RSA which
is the less expensive one (in our comparison with Photuris, we also assume
that Photuris does RSA for signatures; again this is not a requirement
but it's the most efficient implementation).



The scheme accomodates different levels of security and
provides for clear trade-offs security/performance.

Very importantly, it gives the *option* of two basic security levels:

   * full perfect forward secrecy provided by DH: an eavesdropper will
     not learn the exchanged key (K) even if eventually (e.g., much after
     K is no longer in use) it finds the private
     keys of both I and R (the only ways to learn the key are to steal the
     key itself, to actively impersonate one of the parties during the exchange
     or to break the DH scheme).

   * partial forward secrecy: if the DH exchange is omitted, then the
     exchanged key (K0) is secure for as long as at least one of the private
     keys of the parties is not exposed. (I.e., K0 is immune to the discovery
     of one party's private key).

In both cases:

   * an adversary willing to impersonate a party during a key exchange
     must know that party's private key.

The above first option is provided by Photuris. The second is not.
As for the third property, it exist in Photuris if the signature is performed
on-line and with some freshness parameter; it is not provided if the signature
is done off-line.

Against impersonation the scheme is as secure as Photuris with on-line
signatures and has the same performance cost. The relative drawback of our
variant is that it does not include an off-line signature option as in plain
Photuris. However, the off-line signature allows for replay and/or
impersonation based on stolen state information only which in some
cases may represent a "security hole" and then not desirable.
For constrained machines/applications the partial forward secrecy option
that we provide gives a clear trade-off security-performance
(it saves two DH exponentiations to each party!).
A discussion of scenarios where partial forward secrecy may be acceptable is
discussed below.


The overall communication required by the scheme is identical to Photuris,
the total computation of the full scheme is also the same
(one RSA (long) exponentiation, two DH exponentiations).


   * while Photuris allows for off-line performance of the RSA operation
     (a signature in Photuris) here this operation (a decryption) is
     done on-line only (with the resultant added security; see above).

   * while Photuris requires in any case the performance of the (two)
     Diffie-Hellman exponentiations, the present variant supports ALSO key
     exchange without these exponentiations.

Note: A detailed performance comparison should also include the cost of RSA
exponentiations vs DH exponentiations. The former are significantly cheaper
than the later via the Chinese Reminder Theorem; on the other hand, going
to short exponents in DH, as proposed by Photuris put the complexities
closer to each other (my opinion is that the short exponent, which is
a security "shortcut",  should not be mandated but exist as an option
for the user/implementation both in plain Photuris and the present variant).

The default scheme and the options

Shouldn't the full protocol including Diffie-Hellman be the default option?

YES! It gives better security and should be performed whenever possible.
On the other hand, a cheaper, still significantly secure OPTION is
desirable for whoever wants to use it.

Who may want to use partial forward secrecy?

We note that PGP, PEM and other systems provide keys that are breakable
by compromising ONLY ONE private key, and many people seem to be satisfied
with that.  The shared K0 is even better than that: it requires
the breaking of THE TWO private keys to find the key K0.

Following is an example where partial forward secrecy may be acceptable.
Assume a pair of nodes that exchange a key for use with IPv4/6 AH only
(i.e., authentication but not confidentiality).
Do they need Perfect Forward Secrecy? Not strictly, since the key is
used only for authentication of information and not for secrecy. Therefore,
a future compromise of this key (when no longer in use) is useless for
the adversary.  That is, the main attractiveness of DH for long term
protection of keys used for secrecy is irreleveant here. This is a fundamental
difference between secrecy and authentication scenarios (in the former a key
may be useful to the adversary even long after the key has expired).

(This is not to say that DH has no advantages even in the above authentication
scenario. Notice that an adversary that *already* knows I's and R's private
keys at the time of exchange can learn K0 by eavesdropping the Share
phase. If DH phase is also performed then to learn K the adversary needs
to participate actively in that phase).

An additional example for use of partial forward secrecy is when encryption
is used but with weak (for perfromance or export) algorithms. In that
case a long-term protection via DH is useless since the adversary can break
the encryption directly from the ciphertext (and some knowledge of the
plaintext). In this case, the best defense is to refresh keys as often as
possible to increase the adversary's work factor. And then a more efficient
key exchange is very valuable.

In addition, if one considers its own private keys well protected and/or
refreshed frequently (e.g., once a month) then partial forward secrecy may
be a reasonable option.

Compatibility with other key sharing models

Another important advantage of our proposed variant is the way it naturally
accomodates different security models.

For example, with a Key Distribution Center model a la Kerberos,
two parties get a common key from the center. Then they can use our protocol
by ignoring the share phase (they'll use as K0 the key provided by the center)
and going directly to the DH phase (where K0 is used for authentication
only via a (fast) symetric algorithm). Notice that by doing this, a corrupted
server (the KDC) will not learn anything which is protected via the shared
DH key K (except if it actively impersonates the parties during the DH
exchange).  This gives Kerberos-based key-sharing AND perfect forward secrecy.

Similarly, if two parties got K0 manually installed they can use it in the
above mode.

Other ways for parties to share keys are conceivable. In the SKIP proposal
parties share keys via public DH parts. The use of that technique can be
combined with our protocol by letting this shared key be K0, and then proceed
with our protocol without the share phase (and still get perfect forward

And so on, and so on.

The signature-less property

The proposed variant does not use digital signatures. We claim this as an
advantage.  Digital signatures provide non-repudiation; a great property when
needed and a bad one when forced.  For example, it can be used to prove
(by your interlocutor or third party) that you have been communicating
with somebody. Indeed, if for authentication purposes you sign a string
containing the identity of the party you are communicating with (this
may have good security reasons, e.g., against replay, etc.) , this
information can be later used to prove you talked to that party. In a
sense this is a worst privacy violation than not preserving anonymity.
Anonymity is usually protected against an eavesdropper in
the network, but this eavesdropper cannot necesarily prove that you talked
to somebody. Using your signature he can.

Protocols that use signature can (and should) be designed carefully not to force
a user to provide non-repudable information. However, this is one of the
aspects that can be easily overlooked in a design (or modifications to it in
the future). It is also a delicate issue to deal with, e.g.,
if you sign (among other things) a nonce sent by the other party, that
nonce could have been produced as the hash of the identity of that person, etc.

Another problem of signatures, related to anonymity, is that if you want to
protect anonymity you must encrypt the signatures. Otherwise, by simple
signature verification (using your public key) your identity can be tested.

The bottom line is: if we can do it w/o digital signature then better.
We can.

Transparent design for (improved) Anonymity

Photuris has introduced the requirement of keeping anonymity of the parties
(e.g., for mobile users). Photuris achieves that property but at a certain cost.
First it requires the delay of signatures (for DH authentication) until after
the completion of the DH exchange. Second it requires the encryption of
these signatures using the exchanged DH key. Even if the later does not have
a big computational cost, the addition of a symetric encryption algorithm
to the key exchange phase is otherwise unnecesary.

Our solution provides for the anonymity requirement as in Photuris,
but achieves it in a completely transparent way.
It only requires the inclusion of the initiator's
identity inside the encryption message where the half-key K1 is sent.
In cases where anonymity is not required then this identity is just
omitted from the encryption parameters.

Moreover, this solution improves anonymity since it protects it even
against an active attacker. Photuris only protects it against eavesdroppers.
(Photuris relies on a non-authenticated DH exchange for anonymity).


Here I present a more detiled description of this variant.
It is not a complete one (e.g., it does not specify the exact way
information is to structured before applying a PK encryption operation).
These details are left for future description.

The flows (or messages) of the protocol are as follows.
For consistency with Photuris terminology,
I use I and R to denote the parties (initiator and responder).

As in Photuris, there are 6 messages exchanged between parties (in
implementation, can be collapsed to 5 by peggy-backing). They correspond to
3 "phases" (with two messages each phase): Cookies, Share and

I denote them C1, C2, S1, S2, DH1, DH2.

1) Cookies

   C1 and C2 are EXACTLY Photuris cookies exchange (against clogging).

2) Share

   S1 and S2 are intended to exchange a key K0 between I and R (before
   Diffie-Hellman). It goes:

S1 (I --> R) : cookies, ENC_R(Id(I), K1)


  * cookies: are I's and R's cookies as exchanged in C1 and C2 (same as in

  * ENC_R(...) denotes encryption under R's public key of the information inside
    the parentheses.

  * Id(I) denotes the identity of I (hidden in the encryption for anonymity).

  * K1 is a random key chosen by I (its length and purpose will be discussed

S2 (R --> I) : cookies, ENC_I(K2)


  * cookies: are I's and R's cookies as exchanged in C1 and C2 (same as in

  * ENC_I(...) denotes encryption under I's public key of the information inside
    the parentheses.

  * K2 is a random key chosen by R (its length and purpose will be discussed

(see below for details on the way parameters to the encryption function
are encoded before encryption).

The parties, I and R, set K0=K1 XOR K2.

(Other combinations of K1, K2 into K0 are possible, e.g. K0=MD5(K1,K2),
 these details are omitted here).

3) Diffie-Hellman

   DH1, DH2 are Diffie-Hellman exchanges: correspond to DH_REQUEST and
   DH_RESPONSE in Photuris

DH1 (I --> R) : cookies, g^x , MAC_K0(g^x)


  * g^x  is the DH part sent by I (i.e., g^x mod p; the values of g and p
    may also be sent as part of the message if the values are not fixed or
    known in advance).

  * MAC_K0 means a message authentication code (or integrity check function)
    using the key K0 and applied to the information sent in the message.
    MAC_K0 can be keyed-MD5 (with K0 as the key), DES CBC-MAC, etc.

DH2 (R --> I) : cookies, g^y , MAC_K0(g^y)


  * g^y  is the DH part sent by R (i.e., g^y mod p; the values of g and p
    may also be sent as part of the message if the values are not fixed or
    known in advance).

  * MAC_K0 means a message authentication code (or integrity check function)
    using the key K0 and applied to the information sent in the message.
    MAC_K0 can be keyed-MD5 (with K0 as the key), DES CBC-MAC, etc.

The parties now share a Diffie-Hellman key:
                            K = g^(xy) (mod p)

The details of g,p and computation of x, y and exponentiations are all the
same as in Photuris. Also, the use of timers for retransmission, erasure
of old pairs (x,g^x) and so on are the same as in Photuris.

A more compact implementation of the protocol that merges the Share and DH
phases is as follows. It has the advantage of one less message and allows
carrying out the computation of g^(xy) while waiting for the other party's
response. (Cookies are omitted).

I-->R:  g^x, ENC_R(Id(I), K1)

R-->I:  g^y, ENC_R(K2), MAC_K0(g^y)

I-->R:  MAC_K0(g^x)