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

Abstract STS protocol

I was discussing a proposed STS variant with Whitfield Diffie
when he suggested that what makes sense here is an abstract form 
of the Diffie-Van Oorschot-Wiener STS protocol. 

(BTW, for those of you haven't read the Diffie-Van Oorschot-Wiener
paper, the STS protocol is similar to Photuris, with the difference
that the signature is computed over both parties' public exponentials, 
as opposed to merely over the sender's exponentials. This is the most 
important difference. There are other minor differences having to 
do with certified Diffie-Hellman parameters etc. STS stands for

Then Hugo Krawcyk made a proposal that is modular with respect to
accommodating different authentication models, which I believe
has many attractive qualities.

In thinking about this issue, I believe Diffie's suggestion
is a good one, and that the protocol that makes most sense is an abstract 
form of the STS protocol, where the authentication phase is abstracted 
out. This is in line with the modularity proposed by Hugo earlier.

I will observe that we already have to abstract out aspects
of the authentication phase, simply to accommodate different
trust models. Namely, I think we cannot go in with the belief
that a single trust model will emerge in the Internet (e.g.
Hierarchically delegated vs. Web of Trust). So we have to 
abstract this layer in any case.

The abstraction proposed here simply abstracts one level higher
and allows different types of symmetric and asymmetric keys 
for the authentication phase. This is in fact an important element
of Hugo's proposal, and to some extent this part can be considered
as reiterating this element of his proposal.

As will be described, this provides a clear system gain in many different 
environments. I will also present an informal argument as to why this 
doesn't adversely affect the security of the STS protocol. Although it 
may be possible to reduce this argument to a formal level, I will not 
attempt this reduction here.

The protocol is described as follows: (Photuris style cookies
are omitted here, as they are mostly orthogonal to the issues
being discussed, and for purposes of clarity).

I->R	g^x
R->I	g^y

This is simply vanilla Diffie-Hellman. The parties now 
encrypt/authenticate using g^xy or subset as the session key Ks. 
Now follows the authentication phase. This is as follows;

I->R	{I_AuthKeyInfo, I_Auth(g^x, g^y)}Ks
R->I	{R_AuthKeyInfo, R_Auth(g^y, g^x)}Ks

This is essentially the anonymity preserving variant of the STS 
protocol, with the signatures replaced with direction sensitive 
authentication information labelled I_Auth, and R_Auth. In order for 
the other party to be able to verify the authentication information, 
there is acommpanying key information to identify the authentication

One possibility is for the authentication information to be a
signature (e.g. RSA). In this case the key information would
be either a certificate path leading to the signature key, or 
a multiply signed PGP key etc. This would serve to identify (and 
authenticate) the signature key. In this case, the protocol 
described above is exactly the STS protocol, which also uses 
signatures for authentication purposes.

Another possibility is that the authentication information is a 
MAC computed using an authenticated symmetric key.

Some examples of an authenticated symmetric key are as follows.

It may be an existing session key with that party. In this
case the acommpanying key information would be the existing
SAID. This allows re-keying to be more efficient than initial
keying, while still maintaining separation of sessions for
the sake of perfect forward secrecy. This is because signatures
(which are computationally expensive) have been replaced
by MACs (e.g. MD5 based) which are far cheaper.

The symmetric key may be a manually distributed key, or a key 
obtained from a KDC (e.g. Kerberos), or even a share phase
as suggested by Hugo. The symmetric keys may be either short-lived 
(e.g. existing session keys) or long-lived (e.g. manually
distributed). The authentication aspect of the protocol is not 
dependent on freshness properties of the symmetric key.

Also, the symmetric authentication key may be derived from each 
parties' certified long-term Diffie-Hellman keys. The advantage of this 
approach is that the symmetric keys need only be computed once, or 
may be pre-computed. This gives the same performance advantage as 
signature pre-computation, without some of the associated 
weaknesses. In this case, the accompanying key information would be
either a certificate path leading to the certified DH key,
or a DH key signed by multiple PGP RSA keys etc.

In case there is no caching of keys from DH certificates,
the worst case performance of this protocol is similar
to the STS protocol, in that a single exponentiation
is required to compute the authenticated symmetric key.
(I am glossing over the difference between RSA and
DH exponentiations here). 

This worst case performance is also the same as that of Phil's 
recently proposed modification of Photuris, or Hugo's scheme when 
used with RSA based "share phase". Of course, if symmetric keys can 
be cached or precomputed, (which will be feasible with many kinds
of crypto-hw devices that we are evaluating) then these two real-time 
long RSA exponentiations are eliminated.

Using symmetric keys in general also has the advantage that
one doesn't use non-repudiable signatures in the protocol,
because as Hugo has mentioned, non-repudiable signatures
in protocols also represent a privacy concern.

Certified DH keys also give rise to a zero-message protocol 
like SKIP. This I believe has advantages in many different 

Because of these desirable aspects of using certified
DH keys, I believe that this is an authentication
mechanism that should be given serious consideration.
Of course, other authentication mechanisms may also
exist in the same protocol, as described above.

This abtsract form of the STS protocol is I believe 
cryptographically similar in intent to the original
STS protocol, because the only change is from signatures
to direction sensitive MACs. It may be argued that
the only intent of signatures in the STS protocol
was to serve as a directional integrity check. No one
other than the two parties needed to be able to verify
the signatures, so the integrity broadcast aspect of 
signatures was absent. Directional MACs serve exactly
the same cryptographic purpose.

The proposed abstraction allows performance enhancements
not possible if we consider the authentication phase
to be limited to signatures only. Specifically, this allows
removal of two real-time exponentiations from the STS 
protocol, bringing the total number of required real-time
exponentiations to 1 on each side (when coupled with
pre-computation of each party's public exponential).
This is a substantial system gain.

The difference between this proposal and Hugo's is that
this one is closely modelled on the Diffie-Van Oorschot-Wiener
STS protocol, which has the benefit of greater public 
scrutiny/analysis. However, I prefer to emphasize the similarities 
between this proposal and Hugo's and Phil Karn's recent 

Comments are, of course, welcomed.

Kind Regards,