Subject: [sidr] Modifiation request: draft-ietf-sidr-bgpsec-protocol-14

From: "Borchert, Oliver" <[email-masked]>
Date: Wed, 10 Feb 2016 20:05:31 +0000

Hello Matt,

after reading version 14 of the BGPSec protocol draft and after discussing the

update between us, Michael Baer (BIRD implementer) and I (Quagga Implementer)

want to propose some  changes for generation of the “Sequence of Octets to be

Signed” (SOS) in the draft on pg. 15. This change would modify the order of

information within the SOS as well as the order of attributes within the

“Secure_Path” Segment listed on pg. 8.

For your convenience I attached this email as pdf document as well.

NONE of the changes has any impact on the information that is put on the wire

in regards to adding or removing data. The only on the wire change is the

ordering of the attributes within the Secure_Path Segment.

As we are all aware, the most expensive operation within the BGPSEC protocol is

the crypto operation, especially the Path verification.

With the proposed modification of the SOS, implementers will be able to utilize

more efficient and higher performing software mechanisms to validate the

complete chain of signatures in an update. The current form makes this more

difficult.

Our request does remove some data from the previous SOS structure, changes the

order of the remaining attributes within the SOS and includes the re-ordering

of one data segment on the wire, which will facilitate the SOS generation.

1) Request for re-ordering the Secure_Path segment

The first request deals with modifying the order of the Secure_Path segment.

This modification will become more obvious later on when we explain our request

for changes in the structure of “Sequence of Octets to be Signed” (SOS) on

pg. 15.

This is also the only change that has an affect on the data on the “wire” but

again only regarding the order itself, NOT the content.

The current format as it is shown on pg. 8 is as follows:

+-------------------------------+

| AS Number  (4 octets)         |

+-------------------------------+

| pCount     (1 octet)          |

+-------------------------------+

| Flags      (1 octet)          |

+-------------------------------+

We request to move the “AS Number” field to the end of the signature segment.

This results in the following structure:

+-------------------------------+

| pCount     (1 octet)          |

+-------------------------------+

| Flags      (1 octet)          |

+-------------------------------+

| AS Number  (4 octets)         |

+-------------------------------+

The reason for this minor change becomes more clear when we explain our request

for modifying the SOS structure. But as a little preview for where we want to

go with this, consider the following:

Having a set of Secure_Path segments, the last field of the following segment

equals the “Target AS” needed in the SOS structure. But this becomes more

obvious later on.

2) Modifying the SOS structure”

The current structure as it is presented on pg. 15 of draft-14 is as follows:

+-------------------------------+

| Target AS Number              |

+-------------------------------+

| AS Number                     |

+-------------------------------+

| pCount                        |

+-------------------------------+

| Flags                         |

+-------------------------------+

| Previous Secure_Path          |

+-------------------------------+

| Previous Signature_Block      |

+-------------------------------+

| AFI                           |

+-------------------------------+

| SAFI                          |

+-------------------------------+

| NLRI                          |

+-------------------------------+

This structure is very inefficient for signature validation because for each

signature validation the structure needs to be newly regenerated.

One major change in version-14 compared to the preceding drafts is the

inclusion of all previous signatures to the SOS structure. In the previous

draft only the directly preceding signature was part of the SOS. Version-14

introduces an additional overhead of approximately 91-93 bytes (69-71 for

signature + 20 SKI + 2 signature length) or ~92 extra bytes per Signature.

This means that verifying a 10 hop path, the following additional overhead for

signatures must be added to each SOS in comparison to draft 13:

(assumed 92 bytes on average per signature)

SOS overhead 10 signatures: +828 bytes

SOS overhead  9 signatures: +736 bytes

SOS overhead  8 signatures: +644 bytes

SOS overhead  7 signatures: +552 bytes

SOS overhead  6 signatures: +460 bytes

SOS overhead  5 signatures: +368 bytes

SOS overhead  4 signatures: +276 bytes

SOS overhead  3 signatures: +184 bytes

SOS overhead  2 signatures: + 92 bytes

For sequential verification only the maximum memory overhead comes into place

because each consecutive verification will have an SOS size less then the

previous one.

For parallel verification though each verification itself requires the

necessary memory overhead to the SOS which will end up with:

Cumulative overhead for a 10 hop path: 4,140 bytes

And this is only the additional memory consumption added with the signatures.

On top of that comes the prefix information {AFI, SAFI, NLRI}   -> (5...21

bytes), Path information {AS, pCount, Flags} -> 6 bytes each, and 1 byte for

algo ID.

Depending where the data is located during the hash generation (e.g. L2 cache)

the additional memory accesses could further hinder performance and negatively

affect convergence time.

Furthermore, the newly proposed (version-14 draft) SOS includes Secure_Path

Length and Signature_Block Length, both of which are overwritten at each hop.

This imposes the additional burden of regenerating these length fields for the

SOS corresponding to each signature verification. This again means that each

parallel working thread is required to generate its own SOS for signature

validation (see earlier discussion). Hence, it is not desirable to include

these length fields in the SOS at the sender. Removing these will not create a

security risk.

The idea is to generate an SOS that can be re-used so that it only has to be

generated once and then can be utilized without any modification for all

signature verifications within an update – regardless if sequential or parallel

processing is used.

The proposed modification will result in the following SOS structure:

For simplification we combine the signature and path segments shown below into

a combined segment (in the SOS):

+----------------------------+

| SKI                  (n-1) |\

+----------------------------+ \

| Signarture Length    (n-1) |--- Signature Segment   (n-1)

+----------------------------+ /

| Signature            (n-1) |/

+----------------------------+

| pCount               (n)   |\

+----------------------------+ \

| Flags                (n)   |--- Secure_Path Segment (n)

+----------------------------+ /

| AS Number            (n)   |/

+----------------------------+

The simplification in imploded form looks as follows:

+----------------------------+

| Signature Segment    (n-1) |

+----------------------------+

| Secure_Path Segment  (n)   |

+----------------------------+

Proposed SOS Structure: (See example on next page for n=3)

+---------------------------------------+

| Target AS Number                      |

+---------------------------------------+\

| Signature Segment          (n-1)      | \

+---------------------------------------+ |

| Secure_Path Segment        (n)        | |

+---------------------------------------+ \

...                                        > For n Hops

+---------------------------------------+ /

| Signature Segment          (1 origin) | |

+---------------------------------------+ |

| Secure_Path Segment        (2)        | /

+---------------------------------------+/

| Secure_Path Segment        (1 origin) |

+---------------------------------------+

| Algorithm Suite Identifier            |

+---------------------------------------+

| AFI                                   |

+---------------------------------------+

| SAFI                                  |

+---------------------------------------+

| NLRI                                  |

+---------------------------------------+

This structure allows the generation of one single SOS that can be accessed

simultaneously by multiple threads (one for each signature verification).

With this structure an update containing 10 Signatures contains the same

overhead of +828 bytes but here it does not need to be re-generated for each

signature validation. Independent of whether the validation is performed

sequential or parallel, the overhead remains the same and will NOT grow to an

extra 4,140 bytes as outlined earlier. This will result in a net saving of

+3,312 bytes for a path with 10 signatures in addition to the time saved

generating the SOS for each validation separately.

Example for generation and processing the new proposed SOS structure for a

signed path from AS1 to AS4:

AS1—AS2—AS3-AS4

           +----------------------+

SOS 3----->| AS 4                 |   <- (Target AS for signature 3)

         | +----------------------+

         | | Signature_Segment (2)|

         | +----------------------+

         | | pCount            (3)| \

         | +----------------------+  \

         | | Flags             (3)| --- Secure_Path Segment (3)

         | +----------------------+  /

SOS 2----+>| AS 3              (3)| / <- (Target AS for signature 2)

       | | +----------------------+

       | | | Signature_Segment (1)|

       | | +----------------------+

       | | | pCount            (2)| \

       | | +----------------------+  \

       | | | Flags             (2)| --- Secure_Path Segment (2)

       | | +----------------------+  /

SOS 1--+-+>| AS 2              (2)| / <- (Target AS for signature 1)

     | | | +----------------------+

     | | | | pCount            (1)| \

     | | | +----------------------+  \

     | | | | Flags             (1)| --- Secure_Path Segment (origin)

     | | | +----------------------+  /

     | | | | AS 1              (1)| /

     | | | +----------------------+

     | | | | Algorithm Suite ID   |

     | | | +----------------------+

     | | | | AFI                  |

     | | | +----------------------+

     | | | | SAFI                 |

     | | | +----------------------+

     | | | | NLRI                 |

END  +-+-+>+----------------------+

As one can clearly observe the receiver needs only to generate one single

SOS and can utilize it for validation of all previous signatures without

the need to regenerate the SOS at each step.

Better even, the new SOS allows:

 - sequential validation processing without the need to regenerate the

   SOS data for each validation process; just use pointer arithmetic to

   specify start of the structure

 - parallel validation processing using the same memory location.

Thanks,

Oliver Borchert (NIST) & Michael Baer (PARSONS)

---

From: Sean Turner <[email-masked]>
Date: Tue, 23 Feb 2016 22:07:45 -0500

Oliver & Michael,

I see that the Algorithm Suite Identifier is now included just once, which saves one byte per signature segment, and that’s great, but how’s this new structure going to work if there’s an an algorithm transition?  How will you support indicating the “old” and “new” algorithm?

spt

> On Feb 10, 2016, at 15:05, Borchert, Oliver <[email-masked]> wrote:
> 
> Hello Matt,
> 
> <BGPSEC-Draft14-ChangeRequest.pdf>_______________________________________________
> sidr mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/sidr

---

From: "Borchert, Oliver" <[email-masked]>
Date: Wed, 24 Feb 2016 16:19:02 +0000

Sean,

The change relates to the "Sequence of Octets to be Signed" (SOS), not the signature blocks on the wire. 
For validation and signing, one needs to generate a separate SOS per algorithm / signature block 
which is the same as it always was - nothing changed here.
The resulting signature (while signing) will be added to the appropriate signature block,
and algorithm transfers are still dealt with in the same manner as before.
I hope that helps.

Oliver

---

From: Michael Baer <[email-masked]>
Date: Wed, 24 Feb 2016 08:28:29 -0800

>>>>> On Tue, 23 Feb 2016 22:07:45 -0500, Sean Turner <[email-masked]> said:

    Sean> Oliver & Michael,
    Sean> I see that the Algorithm Suite Identifier is now included just once,
    Sean> which saves one byte per signature segment, and that’s great, but
    Sean> how’s this new structure going to work if there’s an an algorithm
    Sean> transition?  How will you support indicating the “old” and “new”
    Sean> algorithm?
    Sean> spt

I'm afraid that I'm not understanding the problem.  Except for the
reordering of data in the Secure_Path segments, the bits on the wire
haven't changed in the proposal.  The algorithm suite ID is still in the
signature_block header.  In draft 14, the algorithm suite ID is included
as part of the entire signature_block in the sequence of octets to be
signed (SOS) for each signature.  The algo suite ID is also include in
the SOS of each signature in the current proposal.  I believe that the
only information not signed over in the proposed SOS that was signed in
draft 14's SOS (although not in previous drafts) is the Signature_Block
length and the Secure_Path length.  I don't think there would be any
change in algorithm suite transition.

-Mike

    >> The current format as it is shown on pg. 8 is as follows:

    Sean> _______________________________________________
    Sean> sidr mailing list
    Sean> [email-masked]
    Sean> https://www.ietf.org/mailman/listinfo/sidr

-- 
Michael Baer
[email-masked]
Senior Software Engineer
Parsons Global Shared Services, Cyber Security Division
C: 530.902.3131

---

From: Sean Turner <[email-masked]>
Date: Wed, 24 Feb 2016 19:55:34 -0500

Right - so after re-reading this I see it now.

spt

> On Feb 24, 2016, at 11:19, Borchert, Oliver <[email-masked]> wrote:
> 
> Sean,
>