Subject: [Mipshop] comments on drafts using CGA

From: "CAO, ZHEN" <[email-masked]>
Date: Sun, 22 Oct 2006 14:52:42 +0800

Hi everybody,

CGA was proposed in RFC3972, and it was originally used in SEND related
protocols. Recently it has witnessed the proliferation of taking advantages
of CGA in many protocols such as [draft-ietf-mipshop-cga-cba-00.txt] and [
draft-haddad-mipshop-hmipv6-security-06.txt]. But unfortunately, CGA was
originally designed for SEND related protocols, which means we should give
more considerations than the original CGA if we apply it in other
protocols.

Actually it has already been suggested in section 7.4 of RFC3972:

<snip>

   Finally, a strong cautionary note has to be made about using CGA
   signatures for purposes other than SEND.  First, the other protocols
   MUST include a type tag and the sender address in all signed messages
   in the same way that SEND does.  Each protocol MUST define its own
   type tag values as explained in Section 8.  Moreover, because of the
   possibility of related-protocol attacks, the public key MUST be used
   only for signing, and it MUST NOT be used for encryption.  Second,
   the minimum RSA key length of 384 bits may be too short for many
   applications and the impact of key compromise on the particular
   protocol must be evaluated.  Third, CGA-based authorization is
   particularly suitable for securing neighbor discovery [RFC2461] and
   duplicate address detection [RFC2462] because these are network-layer
   signaling protocols for which IPv6 addresses are natural endpoint
   identifiers.  In any protocol that uses other identifiers, such as
   DNS names, CGA signatures alone are not a sufficient security
   mechanism.  There must also be a secure way of mapping the other
   identifiers to IPv6 addresses.  If the goal is not to verify claims
   about IPv6 addresses, CGA signatures are probably not the right
   solution.

<snip>

I do not think all the drafts meet the requirements above well. [
draft-haddad-mipshop-hmipv6-security-06.txt] does not include a type tag and
makes use of the public key to distribute a shared key between MN and MAP; [
draft-ietf-mipshop-cga-cba-00.txt] does not give any consideration on the
justification of using this short RSA key. As a result, I suggest that the
draft using CGA for authentication or authorization add a subsection in the
Security Consideration section to address the problems mentioned above.

What's more, by signing a message with the private key, the address owner
can assert (a) that somebody owns this address and (b) that the message was
sent by the address owner. But it cannot assert whether the address owner is
a trusted entity. An attack can auto-configure a RSA public-private key pair
and then configure a CGA ipv6 address, cheating the receiver to trust him.
If the keys are generated and distributed by a trusted entity in the
network, this problem can be avoided. Identity-based Cryptosystem (IBC) does
the very thing for private/public keys generation binding with an IBC-ID,
and it does not introduce a long chain of certificates as PKI does. The CGA
address is computed with the public key of IBC system, so by signing a
message with private key, the address owner can assert three points: (a)that
somebody owns this address and (b) that the message was sent by the address
owner, and (c) the address owner is a trusted entity. This is what we have
suggested in [draft-cao-mipshop-ibc-cga-00.txt] and it sounds better than
what the CGA has guaranteed.

Thanks,
Zhen
_______________________________________________
Mipshop mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/mipshop

---

From: "James Kempf" <[email-masked]>
Date: Sun, 22 Oct 2006 04:34:39 -0700

Zhen,

A few years ago, some of us published some drafts on how to use ID crypto 
for address security. Basically it came down to using the address as the 
public key. The problem is the need for provisioning of the private key by 
the KDC. The two problems with this were 1) the KDC knows the private key 
and therefore could compromise it and 2) the KDC and the client need to 
support some other kind of cryptosystem to provide confidentiality during 
the key distribution. The first problem can be limited using a couple of 
techniques, like HIDE (Hierarchical Identity-based Encryption) but the 
second one seems insoluble. Given that RSA is a logical choice for the 
cryptosystem between the KDC and the client, why not simply use CGA in the 
first place? From a system perspective, ID crypto is like Kerberos, and it 
suffers from the same limitations when used for deployment scenerios that 
are open-ended, i.e. not limited to particular organizations or other 
groups. Possibly you have some new insights into solving these problems, I 
have not read your draft so I cannot say.

Regarding your other criticisms of the drafts that use CGAs, I haven't 
looked at the drafts with this perspective in mind, but if they are not 
abiding by the guidelines in RFC 3872, then they probably need some work. 
Also, there is IPR on CGAs, and the IPR holders only released it for SEND, 
so that issue would need to be addressed before the other drafts could 
become standards.

I'll send you the drafts under separate email.

            jak

----- Original Message ----- 
From: "CAO, ZHEN" <[email-masked]>
To: <[email-masked]>
Sent: Saturday, October 21, 2006 11:52 PM
Subject: [Mipshop] comments on drafts using CGA

> what the CGA has guaranteed.

--------------------------------------------------------------------------------

---

From: "CAO, ZHEN" <[email-masked]>
Date: Sun, 22 Oct 2006 20:22:53 +0800

Thanks for your comments, it helps me a lot. Please see my comments inline.

Thanks,
Zhen

> techniques, like HIDE (Hierarchical Identity-based Encryption) but the

For the first problem: the KDC is much more robust than client with respect
to key compromise. Yes, if the KDC is compromised, all the keys are
disclosed. But I think the KDC is the infrastructure of the network, such as
Certificate Authority and AAA. We rely on those infrastructures so the
assumption has always been that 'the infrastructure is secure enough'. If
they are assumed compromised, any mechanisms MUST fail.

> have not read your draft so I cannot say.

Simply using CGA in the first place is not a problem. But what if we have
more efficient and effective substitutions. We try to promote what CGA has
guaranteed.

As for the open-ended deployment scenarios, we have not considered yet.
Do you have suggested reference?

> abiding by the guidelines in RFC 3872, then they probably need some work.

You meant RFC 3972? Yes, I think we should have more considerations rather
than just assert that we will take advantage of CGA.
_______________________________________________
Mipshop mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/mipshop

---

From: "James Kempf" <[email-masked]>
Date: Sun, 22 Oct 2006 16:21:31 -0700

> Do you have suggested reference?

No references, but SEND is an example of an open-ended deployment scenerio. 
I can take my laptop and connect up to the network anywhere. A more closed 
case is something like a health information system, where users are 
authenticated for access to health records.

            jak

---

From: Christian Vogt <[email-masked]>
Date: Mon, 23 Oct 2006 17:26:11 +0200

Hi Zhen,

I read your draft [1].  You are proposing a combined technique for
address ownership verification and trust management by integrating CGAs
and identity-based cryptosystems.  This is interesting, though I have
the three comments/questions further below.

  [1] draft-cao-mipshop-ibc-cga-00.txt

For those folks who did not read your draft, here is a brief summary of
your proposal:  A node X obtains from a KDC an IBC ID plus a
public/private key pair that is bound to this IBC ID.  The node then
generates a CGA from the IBC ID (rather than from the public key, which
is how it is done in RFC 3972).  A CGA verifier Y recomputes the CGA,
again based on the IBC ID rather than on the public key, and it verifies
that node X really owns the CGA by verifying a signature supplied by
node X.  Y then proceeds to establish a trust relationship with X in
that it inquires at the KDC whether the public key, based on which the
CGA signature was verified, has really been bound to X's IBC ID.

Three comments/questions:

- Regarding the use of CGAs:  In your approach, the KDC gives node X an
IBC ID which is different than an IP address, and node X then goes ahead
and generates a CGA from this IBC ID.  But it seems that it would be
more straightforward to just have the KDC directly assign an IP address
(as the IBC ID) to the node, i.e., IBC ID == IP address.  In that case,
node Y could inquire at the KBC whether node X's IP address is bound to
the public key based on which node X's signature was verified.  If this
is so, then node Y knows that (i) node X really owns the claimed IP
address, and that (ii) it can trust node X based on the knowledge that
the KDC has given node X the right public/private key pair.  You don't
need CGAs if you use an identity-based cryptosystem anyway.

- Regarding the trust relationship between nodes X and Y:  For which
purpose do you need this trust relationship?  IMO, "trust" is very
application-dependent.  E.g., in Mobile IPv6, there is an assumption
that a home agent can trust its mobile nodes that they do not spoof
care-of addresses.  But such trust relationship may not be sufficient
for the home agent to let the mobile nodes do other, more critical
things.  E.g., if the home agent is responsible for accounting, it would
still collect the accounting information itself rather than asking the
mobile nodes in retrospective how much they did communicate and do the
accounting based on the mobile nodes' reporting.  In this respect, it is
also important to consider that the mobile nodes may get compromised, so
they may not be trustworthy even if they get the necessary credentials
from the KDC.  I think your draft is missing a statement on the purpose
of the trust that you establish.

- Regarding mobility:  Since you designed your proposed technique for a
Mobile IPv6 environment, but you did not design it for open-ended
deployment, why not avoid route optimization and thereby make mobility
transparent to correspondent nodes?  You could use Hierarchical Mobile
IPv6, NETLMM, or tunnel all traffic of mobile nodes through their
standard (local) home agent.  In all cases, the mobile node's IP address
does not change from the CN's perspective, so there is no
mobility-related requirement for IP address ownership verification and
CGAs.  You could then use a standard identity-based cryptosystem for
establishing trust relationships between mobile and correspondent nodes.

Best regards,
- Christian

-- 
Christian Vogt, Institute of Telematics, Universitaet Karlsruhe (TH)
www.tm.uka.de/~chvogt/pubkey/

CAO, ZHEN wrote:
> protocols. Recently it has witnessed the proliferation of taking
> advantages of CGA in many protocols such as
> [draft-ietf-mipshop-cga-cba-00.txt ] and
> [draft-haddad-mipshop-hmipv6-security-06.txt]. But unfortunately, CGA
> was originally designed for SEND related protocols, which means we
> should give more considerations than the original CGA if we apply it in
> other protocols.  
> 
> draft-haddad-mipshop-hmipv6-security-06.txt] does not include a type tag
> and makes use of the public key to distribute a shared key between MN
> and MAP; [draft-ietf-mipshop-cga-cba-00.txt] does not give any
> consideration on the justification of using this short RSA key. As a
> result, I suggest that the draft using CGA for authentication or
> authorization add a subsection in the Security Consideration section to
> address the problems mentioned above.
> 
> What's more, by signing a message with the private key, the address
> owner can assert (a) that somebody owns this address and (b) that the
> message was sent by the address owner. But it cannot assert whether the
> address owner is a trusted entity. An attack can auto-configure a RSA
> public-private key pair and then configure a CGA ipv6 address, cheating
> the receiver to trust him. If the keys are generated and distributed by
> a trusted entity in the network, this problem can be avoided.
> Identity-based Cryptosystem (IBC) does the very thing for private/public
> keys generation binding with an IBC-ID, and it does not introduce a long
> chain of certificates as PKI does. The CGA address is computed with the
> public key of IBC system, so by signing a message with private key, the
> address owner can assert three points: (a)that somebody owns this
> address and (b) that the message was sent by the address owner, and (c)
> the address owner is a trusted entity. This is what we have suggested in
> [ draft-cao-mipshop-ibc-cga-00.txt] and it sounds better than what the
> CGA has guaranteed. 
> 
>  
> Thanks, 
> Zhen

---

From: "CAO, ZHEN" <[email-masked]>
Date: Tue, 24 Oct 2006 10:33:11 +0800

Thanks for your comments. My reply inline.

Zhen

> CGA signature was verified, has really been bound to X's IBC ID.

Thanks for your brief summary. But note as well: the public/private key pair
is computed from the IBC ID that the node registers on KDC, and the CGA is
generated from the public key (same as RFC 3972), in which way we can say
the CGA is generated from IBC ID

> need CGAs if you use an identity-based cryptosystem anyway.

If IP address is used as the IBC ID, the node should re-register its ID on
the KDC when it has changed its IP address, resulting in changes in the
private/public key pair. The IBC ID is a permanent identity which is
required by the IBC scheme, so that is not applicable to use the IP address
as the IBC ID.

> of the trust that you establish.

Considering the attacker can auto configure a private/public key pair and
generates a CGA address, hence cheating CGA verifier to accept it as an
valid entity, the trust relationship can be of help. It is the trust
relationship's purpose to avoid this kind of attacks somewhat. Yes, as far
as compromising problem, IMO, (a) it is still not easy to compromise the
mobile node or the private/public key pair. (b) the IBC scheme serves
recovery service that the compromised entities can report their compromised
ID.

> establishing trust relationships between mobile and correspondent nodes.

Thanks for your advice. We will put more emphasis on those questions.

Best regards,

---

From: Christian Vogt <[email-masked]>
Date: Tue, 24 Oct 2006 12:26:39 +0200

> draft-haddad-mipshop-hmipv6-security-06.txt] does not include a type 
> tag and makes use of the public key to distribute a shared key 
> between MN and MAP; [draft-ietf-mipshop-cga-cba-00.txt] does not give
>  any consideration on the justification of using this short RSA key.

Zhen,

you are raising an interesting point.  RFC 3972 specifies a minimum
public/private key length of 384 bits.  The reasons why we so far
considered this length sufficient for the CGA/CBA protocol
[draft-ietf-mipshop-cga-cba-01] are the following.

First of all, the length of the RSA keys does not necessarily increase
the security of a CGA; it's more the length of the hash extension that
is significant.  This is because an attacker does not need to know the
victim's private key in order to spoof the victim's CGA.  The attacker
can simply use an *arbitrary* public/private key pair and then iterate
through possible modifier values until it finds one which produces the
victim's CGA in conjunction with the chosen public key.

So for an attacker to break a victim's CGA, the attacker has two
options:  It could either integer-factor the victim's RSA public key, or
it could choose an arbitrary RSA key pair and do a brute-force search
for a suitable modifier.  If the attacker chooses to integer-factor the
victim's public key, it does no longer need to do a brute-force search
for a modifier.  It can simply copy the modifier from the victim.

Whether we need longer keys therefore depends on the complexity of
integer-factoring a *specific* 384-bit RSA public key relative to the
complexity of a brute-force search for a suitable modifier given an
*arbitrary* RSA public key.  The latter is 2^(59+H) hash operations,
where H is the length of the hash extension encoded into the CGA and 59
is the number of cryptographic bits in the CGA.  I'm not sure about the
former, as I am not a crypto expert.  (Maybe someone can help?)
2^(384/2) = 2^192 factor tests should be an upper bound for the
complexity of integer-factoring a 384-bit key, but there are certainly
more efficient algorithms.

Note that the complexity of one hash operation is lower than the
complexity of one factor test, so we cannot simply compare each of
2^(59+H) hashes with each of the 2^192 factor tests.  But even if we
conservatively assume that a factor test is as easy as a hash operation,
we still find that the complexity of integer-factoring a 384-bit key is
higher than the complexity of a brute-force modifier search even for
very large values of H.

Specifically, if we assume that the complexity for integer-factoring a
384-bit key is 2^192 steps, and the complexity for a brute-force
modifier search is 2^(59+H) steps, then it would be worthwhile for an
attacker to integer-factor the victim's public key, and thus we would
need a longer key size, only when 2^192 < 2^(59+H), which is true if and
only if H > 133.  This is a pretty long hash extension.  So it should
take a while until it becomes worthwhile for an attacker to
integer-factor its victim's 384-bit RSA public key.  This means that the
current 384-bit key length should be sufficient at least in the medium term.

Again, there are two weaknesses in the above estimation:  First, 2^192
steps is an upper bound on the effort for integer-factoring a 384-bit
RSA public key, so the derived threshold for H may in fact be lower.
Second, a hash operation is in reality less complex than a factor test,
which in turn would lead to a higher thresholf for H.  Maybe folks with
a better background in cryptography can help to improve the estimation?

The key length becomes more critical when the attacker wishes to
generate multiple CGAs which are all based on the same public/private
key pair.  E.g., an attacker that wants to DoS a node during Duplicate
Address Detection must repeatedly generate a new CGA (in order to
generate a false Neighbor Advertisement message "defending" that CGA),
whereas only the collision count changes on the victim side.  It would
then be of advantage for the attacker to integer-factor the CGA's
owner's public key, and thus get the private key that it needs to spoof
/any/ CGA from the victim without doing another brute-force search. (The
modifier remains stable if only the collision count changes amongst the
CGA parameters.)

But as far as the CGA/CBA protocol goes, an attacker needs to spoof only
/one/ CGA, namely, the victim's home address.  So my personal opinion is
that we do not need a minimum key length longer than 384 bits in this case.

If folks would prefer longer keys nonetheless, we could do one of the
following three options:

(1)  Specify a higher minimum key length as part of the CGA/CBA
protocol.  This is what you are suggesting.

(2)  Let the correspondent node set the minimum key length, and specify
an error code in the CGA/CBA protocol which the correspondent node can
use in Binding Acknowledgment messages to inform a mobile node that its
public key is too short.  The mobile node can then either generate a
longer RSA key pair and try again, or it can fall back to a standard
IPv6 home address.  The CGA/CBA protocol draft already covers the case
where the home address is not a CGA.

(3)  Extend the CGA Sec registry entry specified in
draft-bagnulo-multiple-hash-cga-01 by a minimum key length.  This would
enable the mobile node to set the key length and force an attacker to
use the same key length.  (If you allow the mobile node to set the key
length without encoding the key length into the CGA, then there is
nothing that prevents an attacker from spoofing the CGA with a shorter
key pair.  In other words, downgrading attacks would be possible.)

One additional word regarding option (3):  A CGA Sec registry entry
points to an RFC that specifies a hash algorithm and possibly other
parameters to be used in CGA generation and verification.  But CGA Sec
registry entries currently do not include a minimum key length.  It has
been extensively discussed whether a minimum key length should be
specified by the CGA Sec registry and the conclusion was that it need
not.  I don't know the exact reasons, but they should be in line with
the discussion above.

Best regards,
- Christian

CAO, ZHEN wrote:
> Hi everybody,
> 
> CGA was proposed in RFC3972, and it was originally used in SEND
> related protocols. Recently it has witnessed the proliferation of
> taking advantages of CGA in many protocols such as 
> should give more considerations than the original CGA if we apply it
> in other protocols.
> 
> draft-haddad-mipshop-hmipv6-security-06.txt] does not include a type
> tag and makes use of the public key to distribute a shared key
> between MN and MAP; [draft-ietf-mipshop-cga-cba-00.txt] does not give
> any consideration on the justification of using this short RSA key.
> As a result, I suggest that the draft using CGA for authentication or
>  authorization add a subsection in the Security Consideration section
> to address the problems mentioned above.
> 
>  message was sent by the address owner. But it cannot assert whether
> the address owner is a trusted entity. An attack can auto-configure a
> RSA public-private key pair and then configure a CGA ipv6 address,
> cheating the receiver to trust him. If the keys are generated and
> distributed by a trusted entity in the network, this problem can be
> avoided. Identity-based Cryptosystem (IBC) does the very thing for
> private/public keys generation binding with an IBC-ID, and it does
> not introduce a long chain of certificates as PKI does. The CGA
> address is computed with the public key of IBC system, so by signing
> a message with private key, the address owner can assert three
> points: (a)that somebody owns this address and (b) that the message
> was sent by the address owner, and (c) the address owner is a trusted
> entity. This is what we have suggested in [
> draft-cao-mipshop-ibc-cga-00.txt] and it sounds better than what the 
> CGA has guaranteed.
> 
> 
> Thanks, Zhen

---

From: "CAO, ZHEN" <[email-masked]>
Date: Tue, 24 Oct 2006 20:34:39 +0800

Thanks for your careful observations:) My comments inline.

Thanks
Zhen

> for a modifier.  It can simply copy the modifier from the victim.

Note as well that the two methods are different, because the
integer-factoring of the victim's public key will result in permanent risk
before the victim changes its key pair, but the brute-force search attack is
one-off since the victim may change its address and then the attacker should
have brute-forced again. From this respect, the following analysis does not
stand well. The integer-factoring costs more but the attacker gains more.

> more efficient algorithms.

some results on integer factoring can be found on
http://en.wikipedia.org/wiki/Integer_factorization, it should be much better
than 2^(192)

> protocol.  This is what you are suggesting.

We are suggesting a security consideration should be given. IMO, e.g., some
words should be added to the Security Consideration section of drafts using
CGA.

---

From: Christian Vogt <[email-masked]>
Date: Tue, 24 Oct 2006 21:15:10 +0200

Hi Zhen!

> options:  It could either integer-factor the victim's RSA public key,
>  or it could choose an arbitrary RSA key pair and do a brute-force 
> search for a suitable modifier.  If the attacker chooses to 
> integer-factor the victim's public key, it does no longer need to do
>  a brute-force search for a modifier.  It can simply copy the
> modifier from the victim.
> 
>> integer-factoring of the victim's public key will result in 
>> permanent risk before the victim changes its key pair, but the 
>> brute-force search attack is one-off since the victim may change 
>> its address and then the attacker should have brute-forced again. 
>> From this respect, the following analysis does not stand well. The 
>> integer-factoring costs more but the attacker gains more.

I agree with you.  But note that I did attend to this issue further down
in my email where I described the case that the attacker wants to spoof
multiple CGAs from the same victim which are all generated from the same
RSA key pair.

The example that I was giving below is a DoS attack against the victim
during Duplicate Address Detection.  But other situations are also
conceivable.  E.g., the victim may change its CGA for location privacy
reasons.  The normal operation in such a case is to keep the same RSA
key pair and use a different modifier.  An attacker that has previously
integer-factored the victim's key can then spoof the victim's new CGA
without going through another brute-force search.

Note that the attacker actually spends *less* effort than the victim in
such a case:  While the victim must do another brute-force search for a
modifier that suffices the desired hash extension length, the attacker
can simply "copy and paste" that modifier.  So the attacker is at an
advantage over the victim.

>> generate multiple CGAs which are all based on the same 
>> public/private key pair.  E.g., an attacker that wants to DoS a 
>> node during Duplicate Address Detection must repeatedly generate a
>>  new CGA (in order to generate a false Neighbor Advertisement 
>> message "defending" that CGA), whereas only the collision count 
>> changes on the victim side.  It would then be of advantage for the
>>  attacker to integer-factor the CGA's owner's public key, and thus
>>  get the private key that it needs to spoof /any/ CGA from the 
>> victim without doing another brute-force search. (The modifier 
>> remains stable if only the collision count changes amongst the CGA
>>  parameters.)

But I must revise something else that I said, which is this:

>> But as far as the CGA/CBA protocol goes, an attacker needs to spoof
>>  only /one/ CGA, namely, the victim's home address.

This is not necessarily true.  The victim may change its home address
every once in a while for location privacy reasons.  This might increase
the motivation for an attacker to integer-factor the victim's public
key.  OTOH, the purpose of the home address is to sustain reachability,
which means that most mobile nodes would likely change their home
address only occasionally.

> where H is the length of the hash extension encoded into the CGA and 
> 59 is the number of cryptographic bits in the CGA.  I'm not sure 
> about the former, as I am not a crypto expert.  (Maybe someone can 
> help?) 2^(384/2) = 2^192 factor tests should be an upper bound for 
> the complexity of integer-factoring a 384-bit key, but there are 
> certainly more efficient algorithms.
> 
>> http://en.wikipedia.org/wiki/Integer_factorization, it should be
>> much better than 2^(192)

Right, I know.  I wanted to keep things simple in the email.  If we
really require a longer key length, then we will need the help of
security experts from the IETF anyway.  We should not rely on Wikipedia
in that case. ;-)

<snip>

>> We are suggesting a security consideration should be given. IMO, 
>> e.g., some words should be added to the Security Consideration 
>> section of drafts using CGA.

Yes, you are definitely right about that.  Will include text on that in
the next draft version.

Thanks!
- Christian

---

From: "CAO, ZHEN" <[email-masked]>
Date: Thu, 26 Oct 2006 00:02:22 +0800

Hi Christian,

I agree with you.

Thanks for your detailed explanation:)

Many thanks,
Zhen