Subject: RE: Last Call: 'Cryptographically Generated Addresses (CGA)' to Proposed Standard

From: "Tuomas Aura" <[email-masked]>
Date: Tue, 3 Feb 2004 19:46:01 -0800

Pekka, thank you for your careful review of the draft. 
I'll submit a new version on Wednesday next week if there are
no further changes.

> That is, the sections up to 5 aren't sufficiently clear, IMHO, that
> using CGA itself gives you nothing (security considerations is OK
> though).  Anyone possessing the public key can generate the CGA, so
> that in itself provides no ownership.  Ownership can only be proven
> through other protocols, or by applying the private key in a
> signature.

In the spirit of your proposed additions, the intro now has the 
following wording:

  "In order to verify the association between the address and the 
  public key, the verifier needs to know the address itself, the 
  public key, and the values of the auxiliary parameters. The 
  verifier can then go on to verify messages signed by the owner of 
  the public key (i.e., the address owner). No additional security 
  infrastructure, such as a public key infrastructure (PKI), 
  certification authorities, or other trusted servers, is needed.

  It is important to note that because CGAs themselves are not 
  certified, an attacker can create a new CGA from any subnet prefix 
  and its own (or anyone else's) public key. What the attacker cannot 
  do is to take a CGA created by someone else and send signed messages 
  that appear to come from the owner of that address." 

> Another thing which I don't think has been discussed sufficiently is
> the CPU resource exhaustion attacks.  Are there ways using which the
> nodes might be forced to perform heavy signature or CGA verification
> steps (e.g., flood with a lot of CGA addresses, where the parameters
> etc. were trivially calculated)?  Luckily enough, you can't force the
> receivers to perform heavy hash2 computation (i.e., sec > 0) unless
> you first break sec=0.

First, the address verification procedure described in this document 
is very light-weight. It takes two calculations of the SHA-1 hash 
function (or only one if Sec=0). Only the generation of a new CGA
from a new public key requires the expensive brute-force search 
(and even then only if Sec>0). I'll return to this below as you seem
to have misunderstood this bit. 

Second, the signature verification could be used for DoS attacks.
That, however, is beyond the scope of this paper. Such attacks and
defenses against them should be considered in the protocols (e.g.,
draft-ietf-send-ndopt) that use the signatures if the threat is
considered significant for the particular protocol.

> ==> the modifier is a random number.  Do you increment it by *one*
> (not specified but implicit I guess) or re-randomize it?  If not
> re-randomize, why not?

Increment *by one*. I'll clarify this. Re-randomization has no 
security advantages compared to linear search from a random initial 
value. The generation of random values is also expensive and would
slow down the linear search by orders of magnitude. Note that even
if the honest address generator did re-randomize, the attacker could
anyway use the faster linear search during a brute-force attack. 

> ==> so, 7. seems to say that for the verification to succeed,
> the hash2 value must be zero.  Looking again at the generation of
> hash values (rules 2. and 3.) it seems that for e.g. sec=3, you'd
> probably have to generate the hash function billions of times, until
> the first 48 bits are all zeros.  What kind of hash computation is
> that?!?!  What's the point?  Shouldn't you just generate the hash,
> and when verifying it, check that it's equal? (now it checks that it's
> zero)?

There is no loop in the verification algorithm. At most two hashes
are computed. It seems the meaning of "verification fails" is not 
clear enough. It does not mean "loop back and try again". I have added 
the following clarification: "If the verification fails at any step, 
the execution of the algorithm MUST be stopped immediately."

> If this kind of very heavy computation is intended, it should be
> spelled out explicitly I think.

It is not needed. I made a small change to the following sentence 
to clarify this even further:
  "The verification procedure is relatively fast and always requires 
  at most two computations of the SHA-1 hash function."

>    If the verification succeeds, the verifier knows that the public
key
>    in the CGA Parameters is the authentic public key of the address
>    owner.
> 
> ==> this is an inaccurate statement.  This verification gives you
> nothing except the knowledge that the CGA address has been generated
> using a public key -- anyone with the public key can do it.  

This depends on the definition of "address owner". The way the term is
used in the draft, I can generate an address that you own (provided 
I know your public key). This is consistent with the fact that the 
expensive address generation procedure can be offloaded, e.g., to a 
fast server or to a bunch of volunteers. I'd rather not change this 
terminology as it is used consistently throughout the draft.

However, if you think it is critical, I could change the text to: 
  "If the verification succeeds, the verifier knows that it can use the 
  public key to verify signatures on messages that the address owner
  sends from this address."
Personally, I think it would be more cumbersome to read.

>    In particular, the verifier SHOULD NOT have any security policy
that
>    differentiates between addresses based on the value of Sec. That
way,
>    the address generator is free choose any value of Sec.
> 
> ==> I find it difficult to justify this SHOULD NOT.  I feel it's
> totally wrong for this document to state that you SHOULD not
> differentiate between the different strengths of an address
> (e.g., if a site considers sec=0 too light, it could only treat
> sec >= 1 as being "good").  This seems to be something we should
> not disallow.  This would seem to be similar to saying that one SHOULD
> not differentiate security policies whether e.g. a single DES or 3DES
> was being used.

Continuing your analogy with DES/3DES, consider a situation where 
I send *my* secrets to you through the encrypted channel (but you 
don't send any secrets to me). In that case, *I* should decide how 
strong encryption my secrets require. Asking your opinion is 
unnecessary and causes an extra roundtrip of algorithm negotiation.
 
Similarly, in SEND, higher Sec values give the address owner 
better protection against DoS attacks. The Sec value that I use
for generating *my* address does not affect your security. Thus,
asking your opinion about my Sec value is unnecessary and 
causes incompatibility between nodes that choose different Sec
values. (The node with lower Sec could not generate a new address
in real time to meet peer's requirement for a higher Sec.)

Admittedly, if CGAs are used for authenticating a key exchange,
the situation changes. But that is beyond the scope of the SEND WG.
To make sure that there is no mistake, I added "in the SEND protocol"
to the text: 
  "In the SEND protocol, after the verification succeeds, 
  the verifier SHOULD process all CGAs in the same way regardless 
  of the Sec, modifier and collision count values. In particular, 
  the verifier in the SEND protocol SHOULD NOT have any security 
  policy that differentiates between addresses based on the 
  value of Sec."  

>    For each valid CGA Parameters data structure, there are 4*(Sec+1)
>    different CGAs that match the value. This is because decrementing
the
>    Sec value in the three leftmost bits of the interface identifier
does
>    not invalidate the address,
> 
> ==> s/decrementing/changing (typically decrementing)/ -- you can up
the
> sec as well, even though for an attacker that's probably not lucrative
--
> unless maybe if CPU resource exhaustion is the goal.

No, this is not true. Assume that Sec=2 and Hash2 starts with (at least)

32 zero bits. The attacker can decrement Sec to Sec=1 because (the same)

Hash2 certainly start with (at least) 16 zero bits. On the other hand, 
the attacker cannot increment Sec to Sec=3 because it is *very* unlikely

that Hash2 would start with 48 zero bits.

> ==> this doesn't include the note that the IETF has been notified
> of some claims.  This is a must.

The statement is currently whatever xml2rfc puts there. If I remember
correctly, I was told by lawyers that the IPR statements are filed
separately and there is no need to include anything in the draft.
But I may be wrong. This is not the type of thing I live for.
Anyway, the RFC editor guidelines say: "An RFC should never itself 
contain an assertion of rights to technology." and not much else. 
If anyone knows what I should put into the draft, PLEASE let me know.
Preferably in a format that is acceptable to xml2rfc. 

Editorial comments ok, except for the following:

>    address (e.g., as an RFC-3041 address [RFC3041]). An attacker does
> ==> s/RFC-/RFC /

Sorry, no. The hyphen is grammatically correct here. (For example, 
"RFC-3041 addresses are defined in RFC 3041.")

Again, thank you for reading the draft so carefully.

Tuomas

--------------------------------------------------------------------
To unsubscribe from this list, send email with "UNSUBSCRIBE" in the
body to <[email-masked]>.
Archive: http://standards.ericsson.net/lists/ietf-send/maillist.html
--------------------------------------------------------------------

This communication is confidential and intended solely for the addressee(s). Any unauthorized review, use, disclosure or distribution is prohibited. If you believe this message has been sent to you in error, please notify the sender by replying to this transmission and delete the message without disclosing it. Thank you.

E-mail including attachments is susceptible to data corruption, interruption, unauthorized amendment, tampering and viruses, and we only send and receive e-mails on the basis that we are not liable for any such corruption, interception, amendment, tampering or viruses or any consequences thereof.

---

From: Pekka Savola <[email-masked]>
Date: Wed, 4 Feb 2004 08:22:06 +0200 (EET)

>   that appear to come from the owner of that address." 

Good.

> considered significant for the particular protocol.

True.  A mention in security considerations (CGA check = easy,
verification = more complex, but out of scope) section might not hurt,
though.

Further, I wonder if it's possible to force an implementation to heavy 
computation resulting from the generation of a new address, e.g., by a 
DAD attack.  This doesn't seem to be the case, because the really 
expensive Hash2 is only computed once even if there were collisions.

> anyway use the faster linear search during a brute-force attack. 

OK. (I think the term "increment" has been used elsewhere in the spec 
as well.)
 
> the execution of the algorithm MUST be stopped immediately."

OK.
 
>   at most two computations of the SHA-1 hash function."

This clarifies the verification part -- my comment also included
(maybe a misunderstanding) about the generation process.  For sec>1
you have to generate the hash, to look for all zeros, thousands,
millions (or even more) times.  That may be pretty bad.  I didn't
understand right out the purpose for this.  Now it seems that the
reason may be to optimize it for those that are checking CGA's.  Maybe 
this needs a bit spelling out.
 
> Personally, I think it would be more cumbersome to read.

OK, let's keep that as-is.  With the clarification in Introduction, 
this is probably enough.

> unnecessary and causes an extra roundtrip of algorithm negotiation.

OK, true.
  
>   policy that differentiates between addresses based on the 

OK.

> > ==> s/decrementing/changing (typically decrementing)/ -- you can
> > up the sec as well, even though for an attacker that's probably
> > not lucrative -- unless maybe if CPU resource exhaustion is the
> > goal.
> 
> No, this is not true. Assume that Sec=2 and Hash2 starts with (at
> least) 32 zero bits. The attacker can decrement Sec to Sec=1 because
> (the same) Hash2 certainly start with (at least) 16 zero bits. On
> the other hand, the attacker cannot increment Sec to Sec=3 because
> it is *very* unlikely that Hash2 would start with 48 zero bits.

Ok, right.
 
> contain an assertion of rights to technology." and not much else. 

There must not be any specific claims on the document, but in case
there is knowledge that some have already been made, there must be a
note which says so (or that's my understanding):

   The IETF has been notified of intellectual property rights claimed in
   regard to some or all of the specification contained in this
   document. For more information consult the online list of claimed
   rights.

> Preferably in a format that is acceptable to xml2rfc. 

This can be achieved with adding up front:

  <?rfc iprnotified="yes"?>

> "RFC-3041 addresses are defined in RFC 3041.")

OK.

-- 
Pekka Savola                 "You each name yourselves king, yet the
Netcore Oy                    kingdom bleeds."
Systems. Networks. Security. -- George R.R. Martin: A Clash of Kings