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

"Borchert, Oliver" <oliver.borchert@nist.gov> Wed, 10 February 2016 20:05 UTC

Return-Path: <oliver.borchert@nist.gov>
X-Original-To: sidr@ietfa.amsl.com
Delivered-To: sidr@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 1C92D1ACEA7 for <sidr@ietfa.amsl.com>; Wed, 10 Feb 2016 12:05:41 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.799
X-Spam-Level:
X-Spam-Status: No, score=0.799 tagged_above=-999 required=5 tests=[BAYES_50=0.8, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id EPzVGOlF-NBe for <sidr@ietfa.amsl.com>; Wed, 10 Feb 2016 12:05:35 -0800 (PST)
Received: from gcc01-CY1-obe.outbound.protection.outlook.com (mail-cy1gcc01on0134.outbound.protection.outlook.com [23.103.200.134]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 5FC711B2F3E for <sidr@ietf.org>; Wed, 10 Feb 2016 12:05:35 -0800 (PST)
Received: from BN3PR09MB0355.namprd09.prod.outlook.com (10.160.115.152) by BN3PR09MB0355.namprd09.prod.outlook.com (10.160.115.152) with Microsoft SMTP Server (TLS) id 15.1.403.16; Wed, 10 Feb 2016 20:05:31 +0000
Received: from BN3PR09MB0355.namprd09.prod.outlook.com ([10.160.115.152]) by BN3PR09MB0355.namprd09.prod.outlook.com ([10.160.115.152]) with mapi id 15.01.0403.017; Wed, 10 Feb 2016 20:05:31 +0000
From: "Borchert, Oliver" <oliver.borchert@nist.gov>
To: Matthew Lepinski <mlepinski@ncf.edu>
Thread-Topic: Modifiation request: draft-ietf-sidr-bgpsec-protocol-14
Thread-Index: AQHRZD5kpFCefHUu10mm0B3o1UytGQ==
Date: Wed, 10 Feb 2016 20:05:31 +0000
Message-ID: <ECE5A848-2A1D-43F7-A303-A76442572693@nist.gov>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
user-agent: Microsoft-MacOutlook/0.0.0.160109
authentication-results: ncf.edu; dkim=none (message not signed) header.d=none;ncf.edu; dmarc=none action=none header.from=nist.gov;
x-ms-exchange-messagesentrepresentingtype: 1
x-originating-ip: [129.6.108.114]
x-microsoft-exchange-diagnostics: 1; BN3PR09MB0355; 5:/hcHkAPB3cmcK3BrLEt8/LtO416dP3chThV+I3gZ5wZHg5RgVo6rV7tt3UMpOS4TmGOrMaDKEdbdPGWuL20N46sSBIkNNTqPksu3p+6rYiiD/hMxrwx7Djqo9tOpI2z4/S6XU5rC7gHhWgmSQeco+Q==; 24:y/1PR2r7OrvumjrPywx38vJgy/sOZ5Q0w75HfiT1FWIwG3yxisAX/cQPEUNGw9JtZ2ljIZLkCoWo9ZPvxKxRwcQZxTA8wkigB+Rfj60mrXI=
x-microsoft-antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:BN3PR09MB0355;
x-ms-office365-filtering-correlation-id: af3819ab-e816-4d7b-5f76-08d332558759
x-microsoft-antispam-prvs: <BN3PR09MB0355375431F906702A1B9E1698D70@BN3PR09MB0355.namprd09.prod.outlook.com>
x-exchange-antispam-report-test: UriScan:;
x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(102415293)(102615271)(601004)(2401047)(5005006)(8121501046)(10201501046)(3002001); SRVR:BN3PR09MB0355; BCL:0; PCL:0; RULEID:; SRVR:BN3PR09MB0355;
x-forefront-prvs: 0848C1A6AA
x-forefront-antispam-report: SFV:NSPM; SFS:(10019020)(979002)(164054003)(92566002)(122556002)(230783001)(19625215002)(50986999)(33656002)(54356999)(86362001)(2171001)(6116002)(1220700001)(102836003)(106116001)(1096002)(3846002)(87936001)(5008740100001)(83716003)(40100003)(5004730100002)(4001350100001)(110136002)(99936001)(16236675004)(5001960100002)(229853001)(3660700001)(66066001)(77096005)(99286002)(19580395003)(189998001)(2900100001)(83506001)(36756003)(586003)(15187005004)(11100500001)(2906002)(82746002)(3280700002)(4326007)(5002640100001)(5890100001)(10400500002)(104396002)(959014)(569005); DIR:OUT; SFP:1102; SCL:1; SRVR:BN3PR09MB0355; H:BN3PR09MB0355.namprd09.prod.outlook.com; FPR:; SPF:None; MLV:ovrnspm; PTR:InfoNoRecords; LANG:en;
spamdiagnosticoutput: 1:23
spamdiagnosticmetadata: NSPM
Content-Type: multipart/mixed; boundary="_004_ECE5A8482A1D43F7A303A76442572693nistgov_"
MIME-Version: 1.0
X-OriginatorOrg: nist.gov
X-MS-Exchange-CrossTenant-originalarrivaltime: 10 Feb 2016 20:05:31.1418 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 2ab5d82f-d8fa-4797-a93e-054655c61dec
X-MS-Exchange-Transport-CrossTenantHeadersStamped: BN3PR09MB0355
Archived-At: <http://mailarchive.ietf.org/arch/msg/sidr/8B_e4CNxQCUKeZ_AUzsdnn2f5MU>
Cc: sidr list <sidr@ietf.org>, Michael Baer <baerm@tislabs.com>
Subject: [sidr] Modifiation request: draft-ietf-sidr-bgpsec-protocol-14
X-BeenThere: sidr@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Secure Interdomain Routing <sidr.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/sidr>, <mailto:sidr-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/sidr/>
List-Post: <mailto:sidr@ietf.org>
List-Help: <mailto:sidr-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/sidr>, <mailto:sidr-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 10 Feb 2016 20:05:41 -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)