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

Sean Turner <sean@sn3rd.com> Wed, 24 February 2016 03:07 UTC

Return-Path: <sean@sn3rd.com>
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 D6DA01B4351 for <sidr@ietfa.amsl.com>; Tue, 23 Feb 2016 19:07:51 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.601
X-Spam-Level:
X-Spam-Status: No, score=-0.601 tagged_above=-999 required=5 tests=[BAYES_05=-0.5, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, 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 VT1eMhLN5TFJ for <sidr@ietfa.amsl.com>; Tue, 23 Feb 2016 19:07:49 -0800 (PST)
Received: from mail-yw0-x236.google.com (mail-yw0-x236.google.com [IPv6:2607:f8b0:4002:c05::236]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id DC67E1B4350 for <sidr@ietf.org>; Tue, 23 Feb 2016 19:07:48 -0800 (PST)
Received: by mail-yw0-x236.google.com with SMTP id u200so5130811ywf.0 for <sidr@ietf.org>; Tue, 23 Feb 2016 19:07:48 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sn3rd.com; s=google; h=content-type:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=SfRYNQVjYzBcipTAH5jlae8aTVelqFN411EFAwKfSHs=; b=c5Yt+bNsh31Eku5Nw2cK4YCoppoGgY2k9M/8eV8LVtDqyrLZNVTP8AcvB5e357NdmB FDZDgKHPoNkZ4smZN4QiPLud1fV54PuzT/KkzzXOg7EvS8b8sq6V5Fz9yRt6KnPtzFOh tFV4/40SFlkN2JK8XieIFx/HcVfgYM7998IAU=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:content-type:mime-version:subject:from :in-reply-to:date:cc:content-transfer-encoding:message-id:references :to; bh=SfRYNQVjYzBcipTAH5jlae8aTVelqFN411EFAwKfSHs=; b=IBxX9vdgrIusAU0odC8ZPlNhzuyDhIzCyfeD0f7Lq6GBQt/2TBjAVVfUs5XX1aLSmG VLfj83P6lBtNGFE44aNd0z2CyAsLf4FqqBhthkhYtsc0s1nB6ISDzGcn4cniH330Ts+Q acx5HZ7Yo8crauBtUjsV0uj5CHzMtRLs2QS6QbUPOlfPJFTJq2HRicxsPuN4EKD3IG7w l38jY2oXaIckfjbFvV5c87V35WsBVgdR1Rd9pdl8cA+Ghpnhvqa2qIVWsoadwoCScCf9 XVd1xDpR7YDD2syk4QG/tBCJy/2MEQ0npFLluiGbA1TWHpJWBNuyWTKhFwT7n6y6OyMW HHHg==
X-Gm-Message-State: AG10YORMYg3YtnT0muZKUSuJ9rxTVc+vT6ya7tIpTyWDpc/NDgpa3Dl+rdUqvV6G3O5M0A==
X-Received: by 10.13.236.136 with SMTP id v130mr19150573ywe.308.1456283268140; Tue, 23 Feb 2016 19:07:48 -0800 (PST)
Received: from [172.16.0.112] ([96.231.217.211]) by smtp.gmail.com with ESMTPSA id n82sm753426ywd.53.2016.02.23.19.07.46 (version=TLS1 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Tue, 23 Feb 2016 19:07:47 -0800 (PST)
Content-Type: text/plain; charset="utf-8"
Mime-Version: 1.0 (Mac OS X Mail 9.2 \(3112\))
From: Sean Turner <sean@sn3rd.com>
In-Reply-To: <ECE5A848-2A1D-43F7-A303-A76442572693@nist.gov>
Date: Tue, 23 Feb 2016 22:07:45 -0500
Content-Transfer-Encoding: quoted-printable
Message-Id: <0FCAB5B8-420D-4007-8E91-21712D9CD6A5@sn3rd.com>
References: <ECE5A848-2A1D-43F7-A303-A76442572693@nist.gov>
To: "Borchert, Oliver" <oliver.borchert@nist.gov>, Michael Baer <baerm@tislabs.com>
X-Mailer: Apple Mail (2.3112)
Archived-At: <http://mailarchive.ietf.org/arch/msg/sidr/2eZ36RYD5jdTwzICUipbNDU3zok>
Cc: Matthew Lepinski <mlepinski@ncf.edu>, sidr list <sidr@ietf.org>
Subject: Re: [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, 24 Feb 2016 03:07:52 -0000

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 <oliver.borchert@nist.gov> 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
> sidr@ietf.org
> https://www.ietf.org/mailman/listinfo/sidr