Re: [CGA-EXT] Public Key algorithm agility in CGAs

[Tony Cheneau <[e-mail]>]

Hello Marcelo,

As Sean stated, we (Michaela, Sean, Maryline and I) are currently working on
some solutions for the problems you exposed. Unfortunately, we didn't finish
writing the drafts yet. The comments during the last WG meeting provided us
some really good insight. We hope this discussion will make clearer what is
possible and what is not.

I will try to explain how we envision to solve theses problems. Comments
inline.


On Sun, 14 Dec 2008, marcelo bagnulo braun wrote:

> Hi,
>
> there have been some discussion about how to support multiple public key 
> algorithms in CGAs.
We think multiple keys can be a good transition mechanism in network
that are (or will be) deployed with 3971 version of SEND. I explain why
this is good and how we can make it backward compatible with the actual
SEND specification.

> RFC3972 states that only RSA are supported and there is a mandatory Public 
> Key filed in the CGA PDS that contains:
>
>      The public key MUST be formatted as a DER-encoded
>      [ITU.X690.2002] ASN.1 structure of the type SubjectPublicKeyInfo,
>      defined in the Internet X.509 certificate profile [RFC3280].  SEND
>      SHOULD use an RSA public/private key pair.  When RSA is used, the
>      algorithm identifier MUST be rsaEncryption, which is
>      1.2.840.113549.1.1.1, and the RSA public key MUST be formatted by
>      using the RSAPublicKey type as specified in Section 2.3.1 of RFC
>      3279 [RFC3279].  The RSA key length SHOULD be at least 384 bits.
>      Other public key types are undesirable in SEND, as they may result
>      in incompatibilities between implementations.  The length of this
>      field is determined by the ASN.1 encoding.
>
> So we have two options to support alternative public key algorithms in CGAs:
> - one option is to allow to include a public key of another algortihm in the 
> Public Key field. In order to do that, we must provide a way to tell which 
> algorithm is used.
> According to RFC3280,
>   SubjectPublicKeyInfo  ::=  SEQUENCE  {
>        algorithm            AlgorithmIdentifier,
>        subjectPublicKey     BIT STRING  }
> and
>
>   AlgorithmIdentifier  ::=  SEQUENCE  {
>        algorithm               OBJECT IDENTIFIER,
>        parameters              ANY DEFINED BY algorithm OPTIONAL  }
>
> I understand that RFC3279 defines the different algorithm identifiers for 
> RSA.
> So, this option would be to simply allow to use other algorithms and see if 
> the Algorithm identifiers for these algorithms have been properly defined.
> While it seems that current RFC3972 allows this already, we may want to 
> update it to make it more explicitly.
> In addition, we want to make sure that the ECC support is properly defined.
This is one way to do it. We plan to use it when the node only support
one type of Signature Algorithm. ECDSA SubjectPublicKeyInfo already has a
been defined if I'm not wrong (in RFC3279 I think).

We also defined a way for the node to support multiple Public Keys as a
transition mechanism.
For this, we use the CGA PDS extension field and define (in a separate
draft) the structure of the extension. It basically looks like this:

     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |         Extension Type        |      Extension Length         |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                                                               |
    ~                       Public Key                              ~
    |                                                               |
    +                               +-+-+-+- - - - - - - - -+-+-+-+-+
    |                               |          Padding              |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Public Key will encoded the same way as the Public Key field in the CGA
PDS (DER-encoded, etc.).

When constructing the CGA, we will have to compute a  hash of a CGA PDS
looking like this:
                        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                        |                             |
                        +         Modifier            |
                        |                             |
                        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                        |                             |
                        +      Subnet Prefix          +
                        |                             |
                        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                        |Col Count|                   |
+-+-+-+-+-+-+-+-+      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|               |      |        Public Key           |
~  Public Key 1 ~ ->   ~                             ~
|               |      |     (variable length)       |
+-+-+-+-+-+-+-+-+      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+-+-+-+-+-+-+-+-+      |         Extension           |
|               |      ~       Public Key 2          ~
~  Public Key 2 ~ ->   |     (variable length)       |
|               |      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+-+-+-+-+-+-+-+-+      |                             |
                        ~           ...               ~
                        |                             |
+-+-+-+-+-+-+-+-+      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|               |      |         Extension           |
~  Public Key N ~ ->   ~       Public Key N          ~
|               |      |     (variable length)       |
+-+-+-+-+-+-+-+-+      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                        |      Extension Fields       |
                        ~                             ~
                        | (optional, variable length) |
                        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

This way, all the Public Keys are linked to the CGA address. Note here that it
is only a transitional mechanism as it will make the messages grow bigger as
more Public Keys are added.

Now that a node can have multiple public keys, we need to differentiate
which one are in used to sign the message. For this reason, we update
the format of the current RSA signature option:

     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |     Type      |    Length     | Key Position  |  Reserved     |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                                                               |
    |                          Key Hash                             |
    |                                                               |
    |                                                               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                                                               |
    .                                                               .
    .                       Digital Signature                       .
    .                                                               .
    |                                                               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                                                               |
    .                                                               .
    .                           Padding                             .
    .                                                               .
    |                                                               |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

We merely redefined the Reserved field to suit our needs. The Key
Position indicates which Public Key was used to build the signature in
the Digital Signature field. Value 0 indicates it was signed with the
CGA PDS Public Key field. Value 1, signed with the first Public Key
extension in the Extension field of the PDS. And so on. The construction
of the Digital Signature field will be define in separate specific
documents for each Signature Algorithm scheme (e.g. draft-shen-csi-ecc
for ECDSA).

A node using a RSA Signature will place its RSA Public Key in the CGA
PDS Public Key field. When using the "not-RSA-only-anymore Signature
Option", it will set the Key Position to 0. This way, it is fully
backward compatible with 3971 enabled nodes.

Will the WG allow us to do such modification to RFC3971 ?

If not, we can as well use the Key Hash to determine which Public Key in the
CGA PDS was used to perform the Digital Signature, but we think it is neither
really optimal (as the node may have to compute a lot of extra hashs) nor
elegant.

> The main issue here is that we need a mechanism to deal with the case that 
> different nodes support different algorithms.
We address this problem by introducing a new SEND option named
"Supported Signature Algorithm Option" (name it itself being clear):

   0                   1                   2                   3
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     Type      |    Length     |R| Nr. supp. Algos | Reserved  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | Sig. Alg. 1   | Sig. Alg. 2   |  Sig. Alg 3.  | Sig. Alg 4.   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   ~                                                               ~
   |                          ...                                  |
   ~                                                               ~
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     ...      | Sig. Alg. N  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

This option contains signature algorithm that are supported by a node.
The receiver can determine which Signature Algorithm is more suited for
the emitter.

The 'R' flag (generally set by the message sent by the nodes that
respond to the initial request) helps to diagnosis when a resent of the
message is needed:

It helps in this case:
Node A                                      Node B

NS
{CGA option,
RSA Signature option. 
Supported-Signature-Algo option
        (RSA, ECC, R=0)} -------->
                                    NA
                                    {CGA option,
                                    ECC Signature option
                                    Supported-Signature-Algo option
                        <--------       (ECC, R=1)}
NA
{CGA option,
ECC Signature option. 
Supported-Signature-Algo option
(RSA, ECC, R=0)}        -------->

IPv6 traffic            <------->  IPv6 traffic



> Note that today, CGAs are used by SEND, MIPv6 and SHIM6 and they all assume 
> that the key is RSA
> I understand that in the case that a different AlgorithmIdentifier is 
> included in the Public Key field of the CGA PDS, the receiving peer will fail 
> the verification. Since the key is bound to the address, the sender will need 
> to retry, but using a different public key, hence using a different address. 
> It seems that what may be needed then is an error message in these protocols. 
> The potential problem of such error message is that it could open the door 
> for downgrading attacks.
I'm not sure an error message could cause any harms.
If we request the error message to be signed and secured with SEND
option.
For example:
After a request from a node A, the node B send its reply. In the
meantime, the attacker send a fake error message supposed to come from
node B. 
- case 1: node A can check the signature on B's message, it won't fall
   for it. 
- case 2: node A can't check B's signature, it won't trust be, the error
   message won't help the attacker since it won't be trusted either

In any cases, if the attacker is in position to drop any of B's packet,
the error message won't help the attacker to become more powerful.

This error message may not be needed at all, when using the "Supported
Signature Algorithm option".

> In any case, it seems clear that if we go this path, we should reccomend that 
> the usage of alternative aplgorithms would break the aforementioned protocols 
> assumptions and needs to be deployed and used in a controlled manner, to 
> avoid failure modes.
We didn't evaluate the needed changes for MIPv6 and SHIM6, but for SEND,
we tried to make changes as smooth as possible. We made a separate draft on
Multiple-key CGA and an other one about modification on the SEND protocol. We
think we can success to make RFC3971 capable nodes and new nodes compatible
through a small negotiation process.

> The other option is to define a new CGA extension that could carry an 
> additional public key (of eventually a different algorithm)
> In this case, a node could have multipla public keys of different algorithms, 
> associated to the same CGA. this would have no backward compatibility 
> problems, since the "main" public key would be RSA and the additional ones 
> could be of other algortihms.
That is the path we plan to take when we consider nodes with multiple
keys deployment.

> The problem here, is that in order to do this, we impose that all nodes must 
> have a RSA public key and one of the motivations for this was that some 
> lighweight nodes couldn't use RSA. However, this approach seems particularly 
> attractive imho for routers and servers, that need to communicate both with 
> normal SEND nodes and lighweight nodes. In this case,they can choose to use 
> RSA for backward comaptibility and also to use ECC when talking to lighwieght 
> nodes.
We believe we can make use of routers in heterogeneous network that  will
support multiple kind of signature option in the same message. Receiver
will only have to check one of the signature to trust a router.  If I
remember correctly, the WG wasn't really happy with this idea. 
This is to my mind a really important feature. Consider the following example:
a router is in a heterogeneous network were nodes are using ECC or RSA (not
both at the same time). If we don't allow multiple signatures, the router will
have to send 2 messages so all node can be aware of the same information. If
we allow multiple signature, we have only one message. Allowing multiple
signatures for routers will reduce the overhead. 
However, our analysis is that for host, multiple signature shouldn't be used.
Host will more likely resend a message with another Signature Option when
need.

> One intermediate approach could be to require to all nodes to always be 
> capable of verifying RSA signatures, but not requiring to have a RSA key 
> itself. This would allow to always be able to fall back to RSA when at least 
> one of the nodes has an rsa key to have a secure channel
> .
>
> I think we probably need to do both, but i am not certian yet.
We think the choice should be made on deployment. An administrator may
have full control on the network, choosing one Signature Algorithm on
the same network (PK only contained in CGA PDS Public Key field). On the
other side, administrator may not have any control and faces host with a
lot of different type of Signature Algorithm (routers will have to
support multiple Signature Algorithms, controlled host will have to use
multiple-key CGA). The modification of the protocol we propose should be
fitted for these usages.


We also plan to introduce an optional Router-as-a-notary function, that
helps nodes that don't have any common Signature Algorithm to securely
communicate NDP informations together. Basically: when a node doesn't
understand the signature of a message, it will forward the packet to a
router (that will be trusted for this role via its certificate), that
have more processing capabilities (and functionalities) and that will
check the signature on the nodes behalf. Once the signature has been
checked, the status is transfered to the node. This may induce
specification of two new ICMP messages.
This is useful for scenario with really lightweight nodes (that can only
support on type of specific Signature Algorithm) mixing with normal nodes.

Things as I told them may be fuzzy, we will post the drafts as soon as
possible for reviews.

Regards,
 	Tony Cheneau

_______________________________________________
CGA-EXT mailing list
[e-mail]
https://www.ietf.org/mailman/listinfo/cga-ext