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

[Matthew Lepinski <[e-mail]>]

I haven't seen any objections to this change on the list.

I suspect that the benefits from this change are modest. However, I am
happy to see us make a couple of small changes that will make things a bit
easier for implementers.

I have made the changes Oliver suggested in the next version of the
document.

I just need to roll in a few last editorial suggestions and then I will
toss the new version into the draft repository.

Thanks again to Oliver for providing this feedback.

- Matt Lepinski

On Wed, Feb 24, 2016 at 7:55 PM, Sean Turner <[e-mail]> wrote:

> Right - so after re-reading this I see it now.
>
> spt
>
> > On Feb 24, 2016, at 11:19, Borchert, Oliver <[e-mail]>
> wrote:
> >
> > 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
> >
> >
> >
> >
> >
> >
> > On 2/23/16, 10:07 PM, "Sean Turner" <[e-mail]> wrote:
> >
> >> 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 <[e-mail]>
> wrote:
> >>>
> >>> 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)
> >>>
> >>>
> >>>
> <BGPSEC-Draft14-ChangeRequest.pdf>_______________________________________________
> >>> sidr mailing list
> >>> [e-mail]
> >>> https://www.ietf.org/mailman/listinfo/sidr
> >>
>
> _______________________________________________
> sidr mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/sidr
>