Subject: [Hipsec] Thoughts on crypto agility

From: Robert Moskowitz <[email-masked]>
Date: Tue, 11 Aug 2009 11:36:07 -0400

Below is a good writeup of what I hope will lead us to a KISS crypto 
agile BEX.

Tobias Heer wrote:
>
> 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.

For some reason, I read that "and." and am looking for some more text...

>
> 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.

Not always, I believe the 2nd DH is a "MAY"?  If only one DH fits the 
situation, why send two?  But this is a nit over all.

>
> 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).

This is important over other options we worked through.  It maintains 
the simplicity of HIP while providing the needed agility.

>
> 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.
>
> BR,
>
> Miika, Robert & Tobias
>
>
>
> -- q   
> Dipl.-Inform. Tobias Heer, Ph.D. Student
> Distributed Systems Group
> RWTH Aachen University, Germany
> tel: +49 241 80 207 76
> web: http://ds.cs.rwth-aachen.de/members/heer 

-- 

The Greatest Oak

Was once a little Nut

That held its ground.

---

From: Miika Komu <[email-masked]>
Date: Tue, 11 Aug 2009 22:33:12 +0300

> For some reason, I read that "and." and am looking for some more text...

...enforce the parties to use unnecessarily too weak crypto.