Subject: [Hipsec] Changing HIP BEX to support crypto agility

From: Robert Moskowitz <[email-masked]>
Date: Tue, 08 Dec 2009 21:36:02 -0500

As we brought up here on the list back in August, adding crypto agility 
results in some important changes to the BEX.  The negotiation of the 
Hash, MAC, and PK added to the DH affords some downgrade attacks.
Tobias Heer and Stefan Götz worked out the following after a set of 
discussions with them and Miika Kumo in the HIIT office back on Aug 5.

When we had the discussion we had not included the MAC as variable.  We 
missed that one, so the text below will have to be updated to support 
different MACs as well.

I also will follow this with discussions we had on changes to the DNS 
format for HIP.

========================================================================

Hi,

this is a summary based on discussions with Robert Moskowitz, Tobias
Heer, Stefan Götz and Miika Komu at HIIT during week 32. We discussed
about the problems associated with HIP algorithm agility and different
alternative solutions. After several design iterations (of which not all
are described in this email), Tobias came up with a solution which we
all agreed on. We'd suggest the working group to adopt it to get HIP on
standards track. All discussion is welcome!

Problems
========

HIP algorithms are attached quite statically to the HIP protocol and
namespace. We need a better way to deal with deprecating broken
algorithms and inclusion of new ones. Some examples below:

a) Although SHA1 is not broken yet, there will be a need to replace it
with something stronger (SHA256?) in the future.
b) We may want to support other public key algorithms such as elliptic
curve DSA.
c) We may want to support shared key generation with elliptic curve
Diffie-Hellman instead of the normal D-H.

This leads us to the following new challenges:

1.) We have several signature algos now and it cannot be assumed that
every host supports every algo.
2.) We have several hash algos for HITs now and it cannot be assumed
that every host supports every algo.
3.) We have several DH groups now and it we cannot fit all in the
R1 packet.

In effect, several hash and signature algorithms lead to a multitude of
HITs per each host. Several signature algorithms lead to a multitude of
HIs per host.

Opportunistic HIP introduces additional challenges with the HIT
algorithm selection. The I1 lacks a Responder HIT, so unless we
encode the PK and Hash of the Initiator into its HIT, we have a
decision problem for the Responder. Even if we do that, why did
the Initiator select THAT combination, perhaps the Responder does not
support it, but supports a different combination used by the
Initiator.

There is also a referral related issue, where the Initiator learned of a
HIT through some application-layer protocol or just by caching. The
problem arises if we don't encode the algorithm in HIT but rather just
encode this in DNS. When application connects to HIT and the system does
know the related algorithms, the connection can just fail due to
algorithm mismatch. This problem might arise for example in hipbone
environments.

Negotiation of Diffie-Hellman algorithm must be started already in the
I1 message to avoid overly large R1 packets filled with different D-H
parameters. This introduces the possibility for a man-in-the-middle
attack where the attacker mounts a downgrade attack on the Initiator and
Responder. The attacker can alter the I1 because it is unprotected. Thus,
the attacker can cause the Responder to offer unnecessarily too weak
algorithms or key lengths in R1 and enforce the parties to use unnecessarily
too weak crypto.

Solution 1: application selects algorithms
==========================================

The basic problem is that the Initiator and the Responder must select a
combination of algorithms supported by both hosts. Some of these
algorithms can be selected during the BEX (see DH below) but some must
be selected before the BEX since the applications may bind to source and
destination HITs before the system performs the BEX. In particular, the
applications selects the destination HIT (=hash algo + signature algo).
Hence, the application must make a "good" choice here. "Good" means here
that the application selects a combination of hash and signature
algorithms supported by both hosts.

We can't really shift the selection burden to the applications. It might
work on native HIP applications, but we should be able to use HIP with
legacy applications as well. So shifting the problem to the applications
is not a good solution.

Solution 2: resolver selects algorithms
=======================================

As a first approximation, the Initiator learns of the ciphers
supported by the Responder from DNS or some other service, selects its
HIT that matches the selected Responder's HIT and off it goes. The
local DNS resolver can filter the HITs and only provide locally
HITs supported by both hosts to the application. Hence, the application
can make a "good" choice. This requires the availability of additional
information about HITs in the DNS system. Specifically, the hash
function and signature algorithm must either be provided as additional
information through the DNS system or must be encoded within the HIT
itself (which increases chances for HIT collisions).

The main 'challenge' is selecting the DH mode, since including the DH
modes in DNS or in the bits of the HIT is not feasible (too many
resulting HITs).

The suggested solution
======================

We reuse the solution 2 and include hash and public key algorithm
support in the DNS resource records, but also signal algorithms in
the base exchange to support scenarios without name look up
infrastructure.

I1 packet has to be modified to include the hash, public keys and
diffie-hellman algorithms supported by the Initiator in a new "algo"
parameter.  The parameter should indicate which hash and public key
algorithm the Initiator used to generate its HIT.

The Responder receives the I1 packet and compares the algorithms
contained in the I1 parameter with its supported algorithms. It
sends back an R1 generated using the hash, public-key and diffie-
hellman algorithms supported by both of the hosts. The R1 always
includes two diffie-hellman keys and the signature covers the whole
packet as in the current RFC5201 specification.

The R1 also lists also the algorithms supported by the Responder in a
new "algo" parameter. This parameter is in the signed part of the R1.
The parameter also denotes which hash, public-key and diffie-Hellman
algorithms were used to produce the R1. It should be noticed that a
Responder implementing precomputed spools of R1 packets has to maintain
a large selection of R1s to support the various combinations of
algorithms.

This approach also works with opportunistic I1 packets as well. In such
a case, the Responder can select its source HIT for the R1 based on the
algo parameter in I1.

Protection against the dowgrade attack
======================================

If the offered DHs in R1 are strong enough for the Initiator,
everything proceeds as the current BEX. In the case of a detected
downgrade attack, the {DHlist} in the R1 supports a better algorithm
than the one chosen in R1. In such a case, the Initiator sends another
I1 in which it limits the choice of the supported algos to the
strongest matching algorithm.

It the attack case would look like this:

I1 {DHlist: 1,2,3} (attack)
-------------------------->
R1 {DHlist: 1,2,3} DHparameters-1
<-------------------------

(Initiator realizes that there is an attack)

I1 {DHlist: 3}
-------------------------->
R1 {DHlist: 1,2,3} DHparameters-3
<-------------------------
I2
-------------------------->
R2
<-------------------------

The MITM attacker could still modify the packets but that would only
lead to a situation in which the BEX would never finish (or would be
aborted after some retries). The attacker could also just drop the
packets which would lead to DoS (which is impossible to protect against)
but the attacker cannot mount an undetected downgrade attack any more.

As a drawback, this leads to an 6-way BEX which may seem bad at first.
However, since this only happens in an attack scenario and since the
attack can be handled (so it is not interesting to mount anymore), we
assume the additional messages are not a problem at all. Since Malice
cannot be successful with a downgrade attack against I1, these sorts of
attacks will only occur as 'nuisance' attacks. So, the base exchange
would still be usually just four packets even though implementations
must be prepared to protect themselves against the downgrade attack.

Also, a benefit of this approach is that it will only have minimal
impact on the state machines specifications and their implementations
(check the DHlists, restart if necessary).

HI bindings
===================
A host may now have a number of HIs (several signature algorithms). This
results in the question how to bind these HIs together. Until now we
have only discussed a DNS-(sec)-based binding but other bindings are
also possible (certificates, etc). However, the question of
signature-algo compatibility remains. If the signature algorithm of the
certificate is not understood, the binding is useless. In general, it
would probably make sense to not use crypto agility as a "comfort tool"
that enables to use of any arbitrary combination of algorithms but as a
tool that enables to increase the security of the system whenever the
currently used algorithms are threatened. Otherwise we will end up with
hosts that have a large number of HIs and even more HITs.