identity-misbinding attack on SLA

[Hugo Krawczyk <hugo@ee.technion.ac.il>]

In a message to this list on Dec 21st I referred to a possible
cryptographic weakness in the design of SLA (draft-hoffman-sla-00.txt).  
The following discussion is intended to present the problem and to
recommend a fix.  This story should be of interest to those that care
about the ikev2 design and not just to the SLA people.  Indeed it has a
moral that applies to the design of IKEv2 too (for your "enjoyment" I will
follow with another message regarding some related issues in the more
general IKEv2 setting).

This message is LONG and can be safely skipped by those that do not care
about the cryptographic design of ikev2 and SLA. Others please read this
message (and the one that follows about changes to ikev2).
For a more comprehensive explanation of these issues please refer to the 
SIGMA paper http://www.ee.technion.ac.il/~hugo/sigma.ps [.pdf]
 
The SLA Protocol
=================

The SLA (secure legacy authentication) protocol is described in
draft-hoffman-sla-00.txt: the Initiator is a client machine C that uses the
legacy authentication credentials of a user U to authenticate to a server S
(an ipsec gateway, authentication server, etc) which acts as the responder.

  Messages 1 and 2 of SLA are:

       Initiator (client)                  Responder (server)
      -----------                        -----------
       HDR, SAi1, KEi, Ni        -->

                                 <--    HDR, SAr1, KEr, Nr, AUTH

       (The responder's AUTH payload is computed over all of message 1
       concatenated with all of message 2.)

  The subsequent messages use the DH key g^xy (derived from KEi and KEr)
  to protect a legacy authentication from client C to server S.

First note that the protocol as described above only works when the client
machine knows in advance the identity AND certificate of the server.  
This assumption holds in some scenarios but certainly not in all remote user
authentication cases. In many instances the client machine will not have the
server's certificate but will rather have to receive the cert from the
server itself (this cert is verified at the client on the basis of some 
verification PK and policy settings installed at the client).  Moreover, in
the general case there may be more than one server responding to the
client's "call".  Therefore (and as agreed by Paul Hoffman in a previous
message) we will consider the augmented protocol where a cert (or identity)
of the server is sent back to the client in message 2 (this identity goes in
the clear, which is ok since we are not concerned with gateway's anonymity).

The attack
==========

For describing the attack let's assume two servers (or gateways), Sbad and
Sgood, that may legitmately answer C's (the client) call (i.e. both servers
have certs that C would accept as valid for running a legacy authentication
under SLA).  Now imagine that Sbad is controlled by an attacker, while Sgood
behaves correctly. Assume that the first to respond to C's first message is 
Sgood who sends message 2 to C.  Sbad intercepts this message, changes the
cert of Sgood to its own cert, and replaces Sgood's signature with Sbad's.
The rest of the message is unchaged.  (Note that the message contains KEr as
chosen by Sgood but this does not prevent Sbad from signing it.) 
The client receives the message from Sbad, checks Sbad's cert and signature,
and follows with message 3.  Sbad receives this message and relays it to
Sgood as if it came from C.  Sgood understands this as message 3 in its
half-open session and follows with message 4 in the protocol.  Sbad
intercepts this message and sends it to C as if it originated from Sbad 
(the SLA message itself is not changed). Messages 5 to N in SLA are treated
in the same way by Sbad (i.e. relayed unchanged between Sgood and C, except
that the messages to C originated at Sgood are sent to C as coming from 
Sbad -- for example they are sent to C with the source IP address of Sbad).

Consequences of the attack
==========================

At the end of the protocol's run the situation is as follows: The honest
server Sgood is convinced that it interacted and established an
authenticated key g^xy with C. The client C, however, is convinced that
this same authentication and key exchange session was run with Sbad
(in particular C believes that the key g^xy and its derivatives are shared
with Sbad).

In other words, two honest parties to the exchange end the protocol with
inconsistent views of who did they talk to. Sgood binds the exchange to C,
while C binds the exchange to Sbad. This is a clear break of the 
"consistency" (or "mutual belief") requirement of any generally sound key
exchange protocol. Note that this form of attack (discovered many years ago by
Diffie-van Oorschot and Wiener in their famous STS paper) is not a standard 
MitM attack against the secrecy of the key but an attack against the
authenticity of the exchange.  In particular, traffic coming from Sgood and
protected under the exchanged DH key is understood by C as originated at
Sbad, while traffic sent from C and intended for Sbad is understood by Sgood 
as intended for Sgood.

I refer to this type of attack as an "identity misbinding" attack; 
it is sometimes called in the literature "unknown key share" attack.
(I called it the "triangle attack" in the SIGMA paper mentioned above 
but this name has already been used elsewhere for a different attack so I'll
change the name to avoid confusion.)

While this attack may have very bad consequences in many key exchange
scenarios, its practical significance in the specific case of SLA is
debatable. Yet, it is hard to confidently claim that this weakness cannot be
exploited in the SLA context which is intended to work with a variety of
different user authentication mechanisms. In particular, the fact that two 
honest parties, C and Sgood, generate inconsistent records of the exchange
is something that one does not expect from a well designed key-exchange
protocol. For example, C could make wrong policy decisions on the basis of
the wrong server's identity (Sbad instead of Sgood).  

[A somewhat contrived example could work as follows: C's policy may dictate
different forms of information sent when talking to Sgood or Sbad. For
example, when talking to Sbad some confidential information is included that
should not be sent if talking to Sgood. In the above case, however, C will 
unintentionally disclose this information to Sgood since C believes that it 
is talking to Sbad.  One can argue that a misbehaving Sbad could directly
pass this information on to Sgood.  That is true, however this presumes some
collaboration between Sbad and Sgood, and even then Sbad may not be able to
convince Sgood that this information really came from C.  However through
the above attack Sgood gets this information directly from C, and
authenticated by C!]

Clearly, a weakness as above (if immediately exploitable or not) should 
not be a property of the protocol.

What went wrong?
================

Why is this attack possible in spite of the signature of the server in 
message 2? Simply because signing the DH exponentials in an authenticated DH
exchange is a NECESSARY BUT NOT SUFFICIENT authentication measure 
(see the sigma paper). What is missing for a consistent ("mutual belief") 
authentication is to BIND the DH key to the identity of the responder
(server) in message 2. This can be achieved by adding a MAC computed on the
responder's identity and keyed with (a derivative of) g^xy. 
It is important to note that in IKEv2 the above "identity misbinding attack"
cannot occur.  Indeed, when the responder authenticates to the initiator in
message 4 of ikev2, there is a MAC computed on the responder's identity
which guarantees the essential key-identity binding. The problem in ikev2 is
that this MAC is not explicit: it is there as part of the SK{} processing
that "happens" to include the responder's identity. I have criticiized this
lack of explicitness in ikev2 as a "design robustness" problem, namely, it
is easy to make apparently harmless changes to the protocol that break its
security. This is especially plaussible since the SK{} processing which
includes the binding MAC is usually seen as part of the encryption process
that is needed only for identity protection, not for key-exchange
authentication.

This lack of robustness in IKEv2 is exemplified very clearly in the SLA design.
The authors of SLA moved to message 2 what seemed to be the essence of the
authentication in message 4 (namely, the signature) and did not care about
the SK{} processing since identity protection was not an issue.

Note: SLA has a strong similarity to IKEv1's signature-based aggressive mode
and to PIC. Yet, the later protocols are not susceptible to the above attack
since they include a secure key-identity binding via the prf (which also
functions as a MAC) included under the signature (HASH-R in ikev1 terminology). 

The fix
=======

There are several ways to go about solving these issues:

1) assume that the client is willing to talk to a single server for which the
client knows the public key in advance. The above attack (which requires at
least two potential servers as responders) will not work in this case.

2) do not assume 1 but consider the attack impractical in this setting. Do
nothing to fix it.

3) Use ikev2 mechanism: add SK{} on top of message 2 (as in message 4).
This however is not possible: you cannot encrypt message 2 in SLA.
What  you can do is to define something like SK*{} which would mean: MAC but
do not encrypt.

4) Use IKEv1 mechanism: do not sign the message information direclty but first
apply to this information (which includes the server id) a prf (or mac) with a
key derived from g^xy and then sign the output of the prf.

5) Keep the signature as defined now but add to the signed information the
value MAC(SK_ar, IDr) where SK_ar is the authentication key derived in ikev2
for the responder, and IDr is the identity of the server (and/or its full
certificate). Note that this MAC value does not need to be transmitted,
it is recomputed at the other side.

Solution 1 seems too restrictive and probably unrealistic.
Solution 2 is dangerous and certainly not something to be proud of...

Solutions 3-5 are all valid cryptographically (they have a well-understood
analysis -- even proofs if anyone cares), and all require adding a mechanism
which is not defined in ikev2 now: (3) requires to define SK{} with null
encryption, (4) adds a prf processing before the signing, (5) needs to
include MAC(ID) under the signature.

I personally prefer either (4) or (5) as being clearer and cleaner
from a cryptographic point of view (and independent of identity protection
mechanisms). Possibly, (5) is the simplest to specify on the basis of the
current ikev2 document.

Instead of detailing a specific solution for SLA I will request to change
IKEv2's specification in a way that will automatically solve the SLA problem
and, more importantly, will make ikev2 more robust to future changes and
more amenable to analysis. I will send a separate message on this.

Hugo