Re: [Mipshop] comments on drafts using CGA

Thanks for your careful observations:) My comments inline.

Thanks
Zhen

On 10/24/06, Christian Vogt <chvogt@tm.uka.de> wrote:
>
> > 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.
>
> 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.

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.

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.

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

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.

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.

(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
>
> --
> Christian Vogt, Institute of Telematics, Universitaet Karlsruhe (TH)
> www.tm.uka.de/~chvogt/pubkey/
>
>
>
> 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
> > [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
>
>
>