Subject: Re: [Hipsec] Eric Rescorla's No Objection on draft-ietf-hip-rfc4423-bis-19: (with COMMENT)

From: Eric Rescorla <[email-masked]>
Date: Tue, 8 Jan 2019 05:57:41 -0800

On Mon, Jan 7, 2019 at 9:58 PM Tom Henderson <[email-masked]> wrote:

> Eric, Miika asked me to share some off-list discussion we had on your
> questions about second preimage attacks in HIP (inline below, trimming to
> the relevant parts).
>
> - Tom
>
> On 11/21/18 11:37 AM, Eric Rescorla wrote:
>
>
>
> On Tue, Nov 20, 2018 at 12:07 PM Miika Komu <[email-masked]> wrote:
>
>>
>> > Eric Rescorla has entered the following ballot position for
>> > draft-ietf-hip-rfc4423-bis-19: No Objection
>> >
>> >
>
>
>
>
>> > COMMENTS
>> > S 3.1.
>> >>          were obtained.  For 64 bits, this number is roughly 4
>> billion.  A
>> >>          hash size of 64 bits may be too small to avoid collisions in a
>> >>          large population; for example, there is a 1% chance of
>> collision
>> >>          in a population of 640M.  For 100 bits (or more), we would not
>> >>          expect a collision until approximately 2**50 (1 quadrillion)
>> >>          hashes were generated.
>> >
>> > It's not just a matter of collisions being hard, but also of being
>> > difficult to produce an HI with a given name.
>>
>> ....where name would be the hash (i.e. HIT). So I added:
>>
>> Besides accidental collisions, it is also worth noting that intentional
>> collisions are difficult to accomplish because generating a valid,
>> colliding hash along with its private-public key is computationally
>> challenging.
>>
>> Did I capture your thinking correctly?
>>
>
> Well, this isn't a collision; it's what's called a preimage. I.e.,
> computing a public
> key with a given HIT. Anyway, as far as I can tell, in HIP being able to
> compute
> a preimage for HIT Y = H(K_X) is equivalent to breaking key K_X, so that
> means
> that that function must have reasonable strength. 2^64 is nowhere near
> enough and the typical expected security level of IETF protocols is 2^128,
> so that means that the full width of the IPv6 address has to be used.
>
> The second preimage attack resistance is 96 bits, plus whatever work is
> needed to generate the keys.
>
I agree that this is in RFC 7343, but it doesn't seem to be stated anywhere
in this document, and  given that this text talks about both 64 bit and >=
100 bit hash functions, I'm not sure how to get it from this text, which is
in context quite confusing/

There isn't any mechanism defined to extend this, such as the CGA Hash
> Extension, but it seems to me that HIP could be extended in a similar way.
> My recollection is that the WG had thought 96 bits to be strong enough
> preimage resistance.
>
Generally, we are targeting the 128-bit security level for new deployments

>
>
>
>> > S 4.3.
>> >>       packet.  Consequently, a HIT should be unique in the whole IP
>> >>       universe as long as it is being used.  In the extremely rare
>> case of
>> >>       a single HIT mapping to more than one Host Identity, the Host
>> >>       Identifiers (public keys) will make the final difference.  If
>> there
>> >>       is more than one public key for a given node, the HIT acts as a
>> hint
>> >>       for the correct public key to use.
>> >
>> > How do you handle second-preimage attacks on the hash?
>>
>> I guess you are referring to this:
>>
>> https://tools.ietf.org/html/rfc7343#section-5
>>
>> (Please let me know if an explicit reference is needed)
>>
>
> No, I'm referring to the point I raised above.
>
> Would you prefer to add a statement such as "The defense against second
> preimage attacks on the hash is the length of the hash truncation (96
> bits), the work required to generate keys to try, and the possible
> distribution of both the host identity and HIT to end systems."?
>
I think you need to lay the situation out rather more completely than this.
I mean, the current text doesn't even say "preimage". You need to describe
the threat, how the-potential attack works, and why it's difficult

-Ekr

---

From: Miika Komu <[email-masked]>
Date: Tue, 8 Jan 2019 15:48:54 +0000

Hi Eric,

(some other questions still remain to be discussed besides the second 
preimage collision issue)

On 11/21/18 21:37, Eric Rescorla wrote:
> 
> 
> On Tue, Nov 20, 2018 at 12:07 PM Miika Komu <[email-masked] 
> <mailto:[email-masked]>> wrote:
> 
>     Hi Eric,
> 
>     On 5/7/18 00:41, Eric Rescorla wrote:
>      > When responding, please keep the subject line intact and reply to all
>      > email addresses included in the To and CC lines. (Feel free to
>     cut this
>      > introductory paragraph, however.)
>      >
>      >
>      > Please refer to
>     https://www.ietf.org/iesg/statement/discuss-criteria.html
>      > for more information about IESG DISCUSS and COMMENT positions.
>      >
>      >
>      > The document, along with other ballot positions, can be found here:
>      > https://datatracker.ietf.org/doc/draft-ietf-hip-rfc4423-bis/
>      >
>      >
>      >
>      >
>     ----------------------------------------------------------------------
>      > COMMENT:
>      >
>     ----------------------------------------------------------------------
>      >
>      > Rich version of this review at:
>      > https://mozphab-ietf.devsvcdev.mozaws.net/D3709
>      >
>      >
>      > Maybe I'm missing something important, but I don't see in this
>      > document how you go from a HI (or HIT) to the corresponding IP
>      > locator. That seems pretty critical to making this work. Can you
>     point
>      > me in the right direction?
> 
>     (I interpret "right" direction here as how to implement this in
>     practice; please let me know if you were asking for something else)
> 
>     Existing applications can utilize LSIs or HITs, for instance, via
>     /etc/hosts in Linux or if the developer/user uses them directly.
>     Mappings can be configured manually. A better way is to use ,e.g., DNS
>     to store the FQDN, HIs, IP address mappings:
> 
>     https://tools.ietf.org/html/rfc8005
> 
>     An application can receive LSIs or HITs from DNS queries when a HI
>     record exists for a host. This can be implemented  in the local
>     resolver
>     library (e.g. glibc in Linux) supports it and sends the HI-to-IP
>     address
>     mapping to the local HIP daemon. As an alternative implementation
>     technique, dynamic relinking of applications (i.e., LD_PRELOAD in
>     Linux):
> 
>     https://tools.ietf.org/html/rfc6538#section-4.1
> 
>     As yet another alternative, RFC5338 (section 3.2) suggests interposing
>     HIP-aware agents (think about HIP-capable DNS proxy like "dnsmasq" in
>     Linux) that translate HIs into LSIs and HITs to the application and
>     cache the IP address mapping to the HIP daemon:
> 
>     https://tools.ietf.org/html/rfc5338#section-3.2
> 
>     That's all for existing applications. New HIP native applications could
>     use DNS library extensions for getaddrinfo() that would be implemented
>     e.g. in glibc in Linux:
> 
>     https://tools.ietf.org/html/rfc6317
> 
>     All of the mentioned references are mentioned in the draft. Should I
>     add
>     something more compressed along these lines of text or is this too
>     detailed?
> 
> 
> Maybe I'm missing something, but it seems like this is not an 
> interoperable state of affairs.

the WG has been experimenting with different ways implementing things. 
Some things are implementation specific (and hence outside of the focus 
of IETF), but, in general, I would argue the most common approach to "go 
from HI or HIT to the corresponding locator" in a typical Linux system 
in the case of a non-hip-aware application works as follows:

1. client app makes are getaddrinfo() call to look up foo.bar from DNS
2. local dns proxy (e.g. standard dnsmasq in Linux) catches the call
3. dns proxy looks up A, AAAA and HI records for foo.bar
3.a. no HI found: dns proxy operates as normally and returns only A/AAAA 
records to the getaddrinfo() call (via glibc) as it would normally
3.b. HI found:
- dnsmasq sends the HI, HIT and IP address to the local HIP daemon
- dnsmasq returns the HIT to the application

The "generic" approach listed here has been tested and implemented (in 
addition some other implementation alternatives mentioned in the HIP 
experiment report). And three different HIP implementations have been 
tested to interoperate with each other.

If this still does not address you concern, please be more specific?

>      > IMPORTANT
>      > S 11.3.1.
>      >>       avoiding manual configurations. The three components are
>     further
>      >>       described in the HIP experiment report [RFC6538].
>      >>
>      >>       Based on the interviews, Levae et al suggest further
>     directions to
>      >>       facilitate HIP deployment.  Transitioning the HIP
>     specifications to
>      >>       the standards track may help, but other measures could be
>     taken.  As
>      >
>      > This confuses me, because we seem to be looking to advance some
>     of the
>      > HIP specs (e.g., hip-dex) at PS
> 
>     Can you elaborate? And do you mean protocol stack by PS?
> 
> 
> Proposed Standard.

Would the following replacement text fix the issue?

"Transitioning a number of HIP specifications to the standards track in 
IETF has already taken place, but the authors suggest other additional 
measures  based on the interviews."

As an alternative, I can just omit the related paragraph.

>      > S 5.1.
>      >>       At the server side, utilizing DNS is a better alternative
>     than a
>      >>       shared Host Identity to implement load balancing.  A
>     single FQDN
>      >>       entry can be configured to refer to multiple Host
>     Identities.  Each
>      >>       of the FQDN entries can be associatedwith the related
>     locators, or a
>      >>       single shared locator in the case theservers are using
>     the same HIP
>      >>       rendezvous server Section 6.3 or HIP relay server Section 6.4.
>      >
>      > This is becoming a less common practice. How do you handle anycast,
>      > which is the modern practice?
> 
>     I added the following statement:
> 
>     "It is also worth noting that opportunistic mode is also required
> 
> 
>     in practice when anycast IP addresses would be utilized as locators:"
> 
>     Does this address your concern?
> 
>     Btw, opportunistic mode is further described in the following documents:
> 
> 
> I'm not following how this solves the problem. It seems like you're 
> still going to get
> badly suboptimal routing.

Without opportunistic HIP, i.e, by using a destination HIT explicitly, 
the situation is challenging because the HI(T)-IP binding at the client 
would be:

* A HI(T) belonging to server A (returned by DNS look up)
* IP anycast address (would be bound to some server B during routing 
process)

The challenge here is that we want make sure that server A is the same 
server as B. AFAIK, this has not been experimented before. Is this what 
you meant by suboptimal routing?

With opportunistic HIP, the problem is easier because the HI(T)-IP 
binding at the client would be:

* "Wild card" HIT (would be bound to a specific HIT after receiving R1 
packet from the anycast address)
* IP anycast address (would be bound to some server B during routing 
process)

Implementation experience exist on HIP opportunistic mode, but AFAIK 
none in the context of IP anycast.

Would this address your concern (so that I can draft some proposal text)?

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 8 Jan 2019 15:44:37 -0800

On Tue, Jan 8, 2019 at 9:50 AM Tom Henderson <[email-masked]> wrote:

> On 1/8/19 5:57 AM, Eric Rescorla wrote:
>
> >     The second preimage attack resistance is 96 bits, plus whatever work
> >     is needed to generate the keys.
> >
> > I agree that this is in RFC 7343, but it doesn't seem to be stated
> > anywhere in this document, and  given that this text talks about both 64
> > bit and >= 100 bit hash functions, I'm not sure how to get it from this
> > text, which is in context quite confusing/
>
> I agree that the text could be clarified; I will try to suggest
> something more.
>
> >
> >     There isn't any mechanism defined to extend this, such as the CGA
> >     Hash Extension, but it seems to me that HIP could be extended in a
> >     similar way.  My recollection is that the WG had thought 96 bits to
> >     be strong enough preimage resistance.
> >
> Can you provide a reference for the 128-bit recommendation?
>

I don't believe there is a policy, but for instance, see:
https://tools.ietf.org/html/rfc7525#section-4.1

> Also, how are legacy uses like SEND/CGA handling this new target (or are
> they just considered legacy at this point)?
>

As far as I understand it, they are legacy.

-Ekr

---

From: Miika Komu <[email-masked]>
Date: Wed, 23 Jan 2019 11:18:11 +0000

Hi,

On 1/20/19 07:59, Tom Henderson wrote:
> On 1/8/19 3:44 PM, Eric Rescorla wrote:
>>
>>
>> On Tue, Jan 8, 2019 at 9:50 AM Tom Henderson <[email-masked] 
>> <mailto:[email-masked]>> wrote:
>>
>>      >     The second preimage attack resistance is 96 bits, plus
>>     whatever work
>>      >     is needed to generate the keys.
>>      >
>>      > I agree that this is in RFC 7343, but it doesn't seem to be stated
>>      > anywhere in this document, and  given that this text talks about
>>     both 64
>>      > bit and >= 100 bit hash functions, I'm not sure how to get it
>>     from this
>>      > text, which is in context quite confusing/
>>
>>      >
>>      >     There isn't any mechanism defined to extend this, such as 
>> the CGA
>>      >     Hash Extension, but it seems to me that HIP could be extended
>>     in a
>>      >     similar way.  My recollection is that the WG had thought 96
>>     bits to
>>      >     be strong enough preimage resistance.
>>      >
>>      > Generally, we are targeting the 128-bit security level for new
>>     deployments
>>      >
>>
> Eric and all,
> In response to this thread, I propose below an additional paragraph to 
> the draft.
> 
> In section 3.1, it discusses requirements on the new namespace in
> general and mentions the desire to avoid collisions, but just lists a
> generic requirement to provide 'authentication services' because the
> cryptographic details are provided later.  As a result, I decided
> against describing second pre-image resistance here.
> 
> In section 4.3, the following paragraph currently concludes the section:
> 
>     In the HIP packets, the HITs identify the sender and recipient of a
>     universe as long as it is being used.  In the extremely rare case of
>     Identifiers (public keys) will make the final difference.  If there
>     is more than one public key for a given node, the HIT acts as a hint
> I suggest to add a paragraph as follows:
> 
>     Although it may be rare for an accidental collision to cause a single
>     HIT mapping to more than one Host Identity, it may be the case that
>     an attacker succeeds to find, by brute force or algorithmic weakness,
>     a second Host Identity hashing to the same HIT.  This type of attack
>     is known as a preimage attack, and the resistance to finding a second
>     Host Identifier (public key) that hashes to the same HIT is called
>     second preimage resistance.  Second preimage resistance in HIP is
>     based on the hash algorithm strength and the length of the hash
>     output used.  Through HIPv2 [RFC 7401], this resistance is 96 bits
>     (less than the 128 bit width of an IPv6 address field due to the
>     presence of the ORCHID prefix [RFC7343]).  96 bits of resistance
>     was considered acceptable strength during the design of HIP, but may
>     eventually be considered insufficient for the threat model of an
>     envisioned deployment.  One possible mitigation would be to augment
>     the use of HITs in the deployment with the HIs themselves (and
>     mechanisms to securely bind the HIs to the HITs), so that the HI
>     becomes the final authority.  It also may be possible to increase
>     the difficulty of brute force attack by making the generation of the
>     HI more computationally difficult, such as the hash extension
>     approach of SEND CGAs [RFC 3972], although the HIP specifications
>     through HIPv2 do not provide such a mechanism.  Finally, deployments
>     that do not use ORCHIDs (such as certain types of overlay networks)
>     might also use the full 128-bit width of an IPv6 address field for
>     the HIT.

thanks! Eric, does this address your concerns?