The Secure Neighbor Discovery (SEND) Hash Threat Analysis
draft-ietf-csi-hash-threat-12

[Ballot comment]
The review on version 11 of the draft perforned by Richard Woundy detected a number of issues which are non-blocking, but if fixed could improved the quality and clarity of the document:

1. Per idnits, "The document seems to lack an IANA Considerations section.  (See Section 2.2 of http://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.)" This issue may be moot, since Amanda Baber pointed out the same issue on 2010-09-14 (http://datatracker.ietf.org/doc/draft-ietf-csi-hash-threat/history/).

2. Section 2.

Per idnits, "The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text."

3. Section 3.

s/theaforementioned/the aforementioned
s/protocols ./protocols.

4. Section 3.1.

This is not a complete sentence: "Since CGAs do not provide non-repudiation features anyway." I would suggest: "However, CGAs do not provide non-repudiation features."

5. Section 7.2.

For [X509-COLL]: s/Identitites/Identities

Idnits points out four unused informational references:

  == Unused Reference: 'SHA1' is defined on line 220, but no explicit
    reference was found in the text
    '[SHA1]    NIST, FIBS PUB 180-1, "Secure Hash Standard", April 1995....'

  == Unused Reference: 'SLdeW2009' is defined on line 226, but no explicit
    reference was found in the text
    '[SLdeW2009] Stevens, M., Lenstra, A., de Weger, B., "Chosen-prefix C...'

  == Unused Reference: 'SSALMOdeW2009' is defined on line 232, but no
    explicit reference was found in the text
    '[SSALMOdeW2009] Stevens, M., Sotirov, A., Appelbaum, J., Lenstra, A....'

  == Unused Reference: 'STEV2007' is defined on line 238, but no explicit
    reference was found in the text
    '[STEV2007] Stevens, M., "On Collisions for MD5", <http:// www.win.tu...'

I note that Sean Turner made a similar observation on 2011-01-06 (http://datatracker.ietf.org/doc/draft-ietf-csi-hash-threat/history/). Sean suggests adding the last three unused references to the text in section 3.2: "Researchers demonstrated attacks against PKIX certificates with MD5 signatures in 2005 [NEW-HASHES], in 2007 [X509-COLL][STEV2007][SLdeW2007], and in 2009 [SSALMOdeW2009][SLdeW2009]."

Sean doesn't mention the [SHA1] reference but I suppose it could be added within the first sentence of section 1: "SEND [RFC3971] uses the SHA-1 hash algorithm [SHA1]..."

[Ballot discuss]
This is an updated discuss based on -11 (retaining the old numbering):

#1) addressed

#2) While working on the Updated MD5 security considerations Benne de Weger pointed me to some of the latest MD5 collision attacks on certificates that aren't in NEW-HASHES (listed below).  The last one is the latest.

[STEV2007] Stevens, M., On Collisions for MD5. http://www.win.tue.nl/hashclash/On%20Collisions%20for%20MD5%20-%20M.M.J.%20Stevens.pdf.

[SLdeW2007] Stevens, M., Lenstra, A., de Weger, B., Chosen-prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities. EuroCrypt 2007.

[SSALMOdeW2009] Stevens, M., Sotirov, A., Appelbaum, J., Lenstra, A., Molnar, D., Osvik, D., and B. de Weger. Short chosen-prefix collisions for MD5 and the creation of a rogue CA certificate, Crypto 2009.

[SLdeW2009] Stevens, M., Lenstra, A., de Weger, B., "Chosen-prefix Collisions for MD5 and Applications", Journal of Cryptology, 2009.
http://deweger.xs4all.nl/papers/%5B42%5DStLedW-MD5-JCryp%5B2009%5D.pdf.

Thanks for adding these references.  All you need to do is add them to the text in Section 3.2:

  Researchers demonstrated attacks against PKIX certificates with MD5 signatures
  in 2005 [NEW-HASHES], in 2007 [X509-COLL][STEV2007][SLdeW2007], and
  in 2009 [SSALMOdeW2009][SLdeW2009].

[Ballot discuss]
This is an updated discuss:

#1) Don't use references in the abstract.  Just remove [RFC3971], [SHA1], and [RFC5280] and you'll be good.

#2) While working on the Updated MD5 security considerations Benne de Weger pointed me to some of the latest MD5 collision attacks on certificates that aren't in NEW-HASHES (listed below).  The last one is the latest.

[STEV2007] Stevens, M., On Collisions for MD5. http://www.win.tue.nl/hashclash/On%20Collisions%20for%20MD5%20-%20M.M.J.%20Stevens.pdf.

[SLdeW2007] Stevens, M., Lenstra, A., de Weger, B., Chosen-prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities. EuroCrypt 2007.

[SSALMOdeW2009] Stevens, M., Sotirov, A., Appelbaum, J., Lenstra, A., Molnar, D., Osvik, D., and B. de Weger. Short chosen-prefix collisions for MD5 and the creation of a rogue CA certificate, Crypto 2009.

[SLdeW2009] Stevens, M., Lenstra, A., de Weger, B., "Chosen-prefix Collisions for MD5 and Applications", Journal of Cryptology, 2009.
http://deweger.xs4all.nl/papers/%5B42%5DStLedW-MD5-JCryp%5B2009%5D.pdf.

[Ballot discuss]
I am picking up Pasi's DISCUSS position on this ID.

Based on the SecDir reviews by Julien Laganier and Paul Hoffman,
it seems this document needs a major rewrite (and one of the
authors seems to agree):

http://www.ietf.org/mail-archive/web/secdir/current/msg01540.html
http://www.ietf.org/mail-archive/web/secdir/current/msg01537.html
http://www.ietf.org/mail-archive/web/secdir/current/msg01536.html

[Ballot comment]
There are a significant number of typos in the document that detract from its readability. 

Abstract

The first use of the acronym ‘SEND’ should be spelled out: /SEND/SEcure Neighbor Discovery (SEND)/

/Current SEND specification/The current SEND specification/

/for the hash algorithm agility/for hash algorithm agility/

/to provide analysis/to provide an analysis/


Section 1

/Cryptographically Generated Addresses (CGA)/Cryptographically Generated Addresses (CGAs)/

/Authorizaton Delegation Discovery/Authorization Delegation Discovery/

/variaty/variety/

/First hash attacks/The initial hash attacks/

/significantlly/significantly/

/Depending on the way how the Internet protocol uses the hash algorithm, Internet protocol can be affected/Depending on how the SEND protocol relies on the hash algorithm, Internet Protocol (IPv6) operation can be affected/


Section 3

/Up to date, all demonstrated attacks are attacks against a collision-free property./To date, all demonstrated attacks are attacks against the collision-free property./

/underlaying hash function/underlying hash function/

/no matter of the hash algorithm weaknesses/no matter the weaknesses of the hash algorithm/

/fingerprints/or fingerprints/

/on SEND by the cases of use/on SEND by the use cases/

/support the hash agility/support hash agility/


Section 3.2

/Router sends to a host/A router sends to a host/

/Potential problem for the attacker/The potential problem for the attacker/

/allowe/allow/

/does not allowe to provide/does not allow/

/biggest concer are/the biggest concerns are/

/such human-readble data such would prevent attacks/such human-readable data would prevent attacks /


Section 3.3

/is described [rfc3971]/is described in [rfc3971]/

/Private key corresponds/The private key corresponds/

/The Digital Signature field the example of the non-repudiation digital singature/The Digital Signature field is an example of a non-repudiation digital signature/

/Possible attacks on such explicit digital signature/A possible attack on the Digital Signature field/

/He underlays one of the messages to be signed/The attacker signs one of the messages/

/but in real-world situation is to achieve it/but in real-world situations it seems difficult to achieve/


Section 3.4

/the integrity protection/integrity protection/

/the collision attacks/collision attacks/

/a non human-readable data/non human-readable data/


Section 4

/Previous section/The previous section/

/SEND context prevents/The SEND context prevents/

/The most effective and secure would be/The most effective and secure solution would be/


Section 6

/offeres/offers/

/by providing solution for the hash agility support/by providing a solution to support hash agility/

[Ballot discuss]
The OPS-DIR review performed by Richard Woundy raised a number of issues that deserve consideration before the document can be approived:

1. Section 3. “Supposing that the hash function produces an n-bit long output, since each output is equally likely, an attack takes an order of 2^n operations to be successful.  Due to the birthday attack, if the hash function is supplied with a random input, it returns one of the k equally-likely values, and the number of operations can be reduced to the number of 1.2*2^(n/2) operations.”

About the use of ‘n’ and ‘k’ as variables. Does k = 2^n? Worse yet, the only other time ‘k’ is mentioned as a variable, it is defined as a key (in section 3.4). In any case, I would change the second sentence to something like the following for greater clarity: “Due the birthday attack, if the hash function is supplied with a series of random inputs, the likely number of inputs required to produce a single hash collision can be reduced to 1.2*2^(n/2).”

Is there a solid technical reference to the “birthday attack”? Since I am not a security expert but otherwise curious about this, I looked it up in Wikipedia: . The Wikipedia article suggests that the number of hash inputs to obtain a single hash collision can be reduced to about 1.25*2^(n/2) input – where 1.25 is approximately the square root of pi / 2 – but I am not sure about the mathematics. Again, I AM NOT A SECURITY EXPERT.

2. Section 4. There are five proposed solutions to enable SEND to leverage new hash algorithms (such as SHA-3) via hash algorithm agility.

Which of the solutions is the recommendation of this document? I am guessing it is number five: “negotiation approach for the SEND hash agility based on the Supported Signature Algorithm option described in [sig-agility]”, mostly because there is a reference to an actual draft in that proposal. But the document never comes out and says that explicitly. It should, especially since the Abstract claims to “decide” this.

There is no discussion in this section about hash agility concerning backwards compatibility, i.e. the situation where some SEND devices support sig-agility and others do not. At least it should be raised as an issue to be overcome. To be fair, this topic does seem to be addressed in http://tools.ietf.org/html/draft-cheneau-send-sig-agility-01#section-2.1.

3. Section 6. Security Considerations

“This issue can be mitigated with the appropriate local policies.” Maybe this is obvious to the author, but I would state what should be configurable in the local policies. Here is related text from the Security Considerations section of [sig-agility], http://tools.ietf.org/html/draft-cheneau-send-sig-agility-01#section-7: “To mitigate this issue, nodes are allowed, on a local policy, to refuse to check certain types of signature (i.e. those which are [known] to be flawed) and will treat the associated messages as unsecured.”

The threat analysis seems to rely on the existence of human readable fields in X.509 certificates for the ADD process (section 3.2). Is there an implicit requirement that a human that is managing the SEND device be able to read and validate these fields? Or is this validated in some automated manner?

[Ballot comment]
There are a couple of minor warnings reported by idnits, and it would be good to fix these if a new revision of the document is being prepared.

---

Section 3.2
s/concer/concern/

---

Section 3.2
  Even though real-world
  scenarios make SEND immune to recent hash attacks introduced through
  X.509 certificates, theoretically they are possible.

This feels like a contradiction or is confusing. If the attacks are possible, do we need to worry about them? If SEND is immune, we do not need to worry even if the attacks are easy and possible. If we *do* need to worry about them, then obviously SEND isn't immune.

[Ballot discuss]
Based on the SecDir reviews by Julien Laganier and Paul Hoffman,
it seems this document needs a major rewrite (and one of the
authors seems to agree):

http://www.ietf.org/mail-archive/web/secdir/current/msg01540.html
http://www.ietf.org/mail-archive/web/secdir/current/msg01537.html
http://www.ietf.org/mail-archive/web/secdir/current/msg01536.html

[Ballot comment]
Well written document, thanks. I had a few comments though:

Term ADD not defined.

> Theoretically this attack could harm
> SEND, but in real-world situation is to achieve it.

... is hard to achieve it?

> From the security
> point of view, at the moment, this solution is more reasonable
> then defining different hash algorithm for each hash.

... than defining ...?

> The computation of the Digital Signature field is described
> [rfc3971].

... described in?

> The computation of the Digital Signature field is described
> [rfc3971].  It is produced as the SHA-1 hash over the IPv6 addresses,
> the ICMPv6 header, the ND message and other fields, e.g. the Message
> Type Tag and ND options, and signed with the sender's private key.
> Private key corresponds to the public key in the CGA parameters
> structure.  It is usually authorized through CGAs. 

The signature field simply binds the private and public key together.
It works for both CGA and certificate-based SEND. Indeed, routers
use the certificate-based mode in practice exclusively.

> o  The third possible solution is to encode the algorithm in the CGA.
>    This would reduce the strength of the CGA and make it vulnerable
>    to brute force attacks.

... and also bidding down attacks, if I'm not mistaken. If the hash
algorithm is part of the CGA parameters structure, simply choose
a hash algorithm that is completely broken and find a value that
matches the victim's address AND uses the bad algorithm within the
CGA parameters structure.

> o  Possible solution is also the hybrid solution which would require
>    the hash algorithm to be the same as CGA, if CGA option is
>    present, and to use the Hash agility option if the CGA option is
>    not present.  In such way, SEND is not bound exclusively to CGA.

Isn't there also a hybrid solution where the hash is in the address
bits for CGA based addresses, and all certificate-related hash operations
are in the certificate? But maybe I'm missing something obvious.

> o  None of the previous solutions supports the negotiation of the
>    hash function.  One of possible solutions is the negotiation
>    approach for the SEND hash agility based on the Supported
>    Signature Algorithm option described in [sig-agility].

I would have noted the bidding-down issue already here (as you do
for some other alternatives).

> The negotiation approach for the hash agility in SEND based on the
> Supported Signature Algorithms option is vulnerable to bidding-down
> attacks, which is usual in the case of any negotiation approach.
> This issue can be mitigated with the appropriate local policies.

Perhaps some mitigation can be offered, but policy really isn't a
solution to the bidding down problem.

Anyway, the security consideration section kind of ends without
making a conclusion. My conclusion -- perhaps not surprisingly! --
is that the RFC 4982 approach seems to be valid approach. And this
is what current standards track specifications say. Do the authors
of this document want to change that situation, or not? It would be
useful to draw a conclusion.

[Ballot comment]
Assuming Informational RFC.

  The Gen-ART Review by Pete McCann on 2010-03-09 included some
  editorial comments.  Please consider them if an update to this
  document is needed for any reason.

[Ballot discuss]
Is this document INFORMATIONAL or STANDARDS TRACK? The ballot say INFO and the document says STANDARDS TRACK. If you meant to say INFORMATIONAL, I will be happy to clear this discuss.

[Ballot discuss]
INTRODUCTION, paragraph 2:
> Intended status: Standards Track

  DISCUSS: I may be missing something obvious, but why is this document
  on the standards track? It's a threat analysis that merely makes a few
  observations on hash agility might be added to SEND in the future.
  Wouldn't Informational be the appropriate category?

Document Shepherd Write-up for draft-ietf-csi-hash-threat-07.txt

  (1.a)  Who is the Document Shepherd for this document?  Has the
          Document Shepherd personally reviewed this version of the
          document and, in particular, does he or she believe this
          version is ready for forwarding to the IESG for publication?

          The document shepherd is Marcelo Bagnulo who has reviewed
          this version of the document and believes that us ready for
          forwarding to the IESG for publication.

  (1.b)  Has the document had adequate review both from key WG members
          and from key non-WG members?  Does the Document Shepherd have
          any concerns about the depth or breadth of the reviews that
          have been performed?

          The document has been reviewed by 6 reviewers and the reviews
          were thorough. We issues 2 WGLC. During the first one, we
          received the reviews and during the second one, nobody objected.

  (1.c)  Does the Document Shepherd have concerns that the document
          needs more review from a particular or broader perspective,
          e.g., security, operational complexity, someone familiar with
          AAA, internationalization, or XML?

          No.

  (1.d)  Does the Document Shepherd have any specific concerns or
          issues with this document that the Responsible Area Director
          and/or the IESG should be aware of?  For example, perhaps he
          or she is uncomfortable with certain parts of the document, or
          has concerns whether there really is a need for it.  In any
          event, if the WG has discussed those issues and has indicated
          that it still wishes to advance the document, detail those
          concerns here.  Has an IPR disclosure related to this document
          been filed?  If so, please include a reference to the
          disclosure and summarize the WG discussion and conclusion on
          this issue.

          No special concerns or issues. The document is an informational
          document describing the problem and the solution space.

  (1.e)  How solid is the WG consensus behind this document?  Does it
          represent the strong concurrence of a few individuals, with
          others being silent, or does the WG as a whole understand and
          agree with it?

          The document describes one of the main problems the CSI is
          chartered to work on. The understanding of the problem by the
          WG is good and this is reflected in the document.

  (1.f)  Has anyone threatened an appeal or otherwise indicated extreme
          discontent?  If so, please summarize the areas of conflict in
          separate email messages to the Responsible Area Director.  (It
          should be in a separate email because this questionnaire is
          entered into the ID Tracker.)

          No conflicts.

  (1.g)  Has the Document Shepherd personally verified that the
          document satisfies all ID nits?  (See
          http://www.ietf.org/ID-Checklist.html and
          http://tools.ietf.org/tools/idnits/.)  Boilerplate checks are
          not enough; this check needs to be thorough.  Has the document
          met all formal review criteria it needs to, such as the MIB
          Doctor, media type, and URI type reviews?  If the document
          does not already indicate its intended status at the top of
          the first page, please indicate the intended status here.

          I have verified the ID nits.
          There a couple of references that need updating (already
          informed the authors) and there is no disclaimer for
          pre-RFC5378 work, but i don't think it is needed in this case.

          No MIB Doctor, media type nor UR type reviews are needed for
          this document.

          The document intended status is informational.

  (1.h)  Has the document split its references into normative and
          informative?  Are there normative references to documents that
          are not ready for advancement or are otherwise in an unclear
          state?  If such normative references exist, what is the
          strategy for their completion?  Are there normative references
          that are downward references, as described in [RFC3967]?  If
          so, list these downward references to support the Area
          Director in the Last Call procedure for them [RFC3967].

          The references are split into normative and informative.
          All normative references are in RFC state. The is no
          downward dependency, since this is an informational document.

  (1.i)  Has the Document Shepherd verified that the document's IANA
          Considerations section exists and is consistent with the body
          of the document?  If the document specifies protocol
          extensions, are reservations requested in appropriate IANA
          registries?  Are the IANA registries clearly identified?  If
          the document creates a new registry, does it define the
          proposed initial contents of the registry and an allocation
          procedure for future registrations?  Does it suggest a
          reasonable name for the new registry?  See [RFC2434].  If the
          document describes an Expert Review process, has the Document
          Shepherd conferred with the Responsible Area Director so that
          the IESG can appoint the needed Expert during IESG Evaluation?

          The document has a IANA considerations section, but there is no
          IANA action required. No protocol extensions are required
          No new registry is created.

  (1.j)  Has the Document Shepherd verified that sections of the
          document that are written in a formal language, such as XML
          code, BNF rules, MIB definitions, etc., validate correctly in
          an automated checker?

          The document does no contain any section written in a formal
          language.
 
  (1.k)  The IESG approval announcement includes a Document
          Announcement Write-Up.  Please provide such a Document
          Announcement Write-Up.  Recent examples can be found in the
          "Action" announcements for approved documents.  The approval
          announcement contains the following sections:

          Technical Summary
            Relevant content can frequently be found in the abstract
            and/or introduction of the document.  If not, this may be
            an indication that there are deficiencies in the abstract
            or introduction.

  Neighbor Discovery Proxies are used to provide an address presence on
  a link for nodes that are no longer present on the link.  They allow
  a node to receive packets directed at its address by allowing another
  device to perform neighbor discovery operations on its behalf.

  Neighbor Discovery Proxy is used in Mobile IPv6 and related protocols
  to provide reachability from nodes on the home network when a Mobile
  Node is not at home, by allowing the Home Agent to act as proxy.  It
  is also used as a mechanism to allow a global prefix to span multiple
  links, where proxies act as relays for Neighbor discovery messages.

  Neighbor Discovery Proxy currently cannot be secured using SEND.
  Today, SEND assumes that a node advertising an address is the address
  owner and in possession of appropriate public and private keys for
  that node.  This document describes how existing practice for proxy
  Neighbor Discovery relates to Secured Neighbor Discovery.


          Working Group Summary
            Was there anything in the WG process that is worth noting?
            For example, was there controversy about particular points
            or were there decisions where the consensus was
            particularly rough?

          Nothing special that worth noting. Not a controversial document.

          Document Quality
            Are there existing implementations of the protocol?  Have a
            significant number of vendors indicated their plan to
            implement the specification?  Are there any reviewers that
            merit special mention as having done a thorough review,
            e.g., one that resulted in important changes or a
            conclusion that the document had no substantive issues?  If
            there was a MIB Doctor, Media Type, or other Expert Review,
            what was its course (briefly)?  In the case of a Media Type
            Review, on what date was the request posted?

          The document is an informational problem statement. The problem
          described in one of the main issues the CSI is chartered to
          work on. There is already a WG document describing a proposed
          solution to the problem.
          The document had 5 through reviews, including reviews from
          Julien Laganier, Sheng Jiang, Tony Cheneau, Jean Michel Combes
          and no substantive issues were identified.

          Personnel
            Who is the Document Shepherd for this document?  Who is the
            Responsible Area Director?  If the document requires IANA
            experts(s), insert 'The IANA Expert(s) for the registries
            in this document are .'

        Document shepherd: Marcelo Bagnulo
        Area Director: Ralf Droms