Subject: [Trans] STHExtension expression

From: Daniel Kahn Gillmor <[email-masked]>
Date: Tue, 26 Apr 2016 15:13:40 -0400

in rfc6962-bis-14, both the TreeHeadDataV2 (section 5.7) and
SignedTreeHeadDataV2 (section 5.8) structures have an SthExtensions
member.  The SignedTreeHeadDataV2 structure itself contains a
digitally-signed struct "signature" that contains a TransItem
merkle_tree_head which is constrained to be a TreeHeadDataV2.

  https://tools.ietf.org/html/draft-ietf-trans-rfc6962-bis-14

I'm assuming that the the implication here is that
SignedTreeHeadDataV2.signature.merkel_tree_head is not expected to be
literally included in the bytestream, or else we'd have two copies of
the sth_extensions field in the SignedTreeHeadDataV2, which i don't
think we want.

But the specification of whether SthExtensions are present is unclear.
in the STHv2 description, it says:

       enum {
           reserved(65535)
       } SthExtensionType;

       struct {
           SthExtensionType sth_extension_type;
           opaque sth_extension_data<0..2^16-1>;
       } SthExtension;

       struct {
           LogID log_id;
           uint64 timestamp;
           uint64 tree_size;
           NodeHash root_hash;
           SthExtension sth_extensions<0..2^16-1>;
           digitally-signed struct {
               TransItem merkle_tree_head;
           } signature;
       } SignedTreeHeadDataV2;

 [...]

   "sth_extensions" is a vector of 0 or more STH extensions.  This
   vector MUST NOT include more than one extension with the same
   "sth_extension_type".  The extensions in the vector MUST be ordered
   by the value of the "sth_extension_type" field, smallest value first.
   If an implementation sees an extension that it does not understand,
   it SHOULD ignore that extension.  Furthermore, an implementation MAY
   choose to ignore any extension(s) that it does understand.

This is not an "opaque" data type, so there is no indicator of the
number of extensions available in the bytestream.

Consider the case of zero extensions:

 log_id
 timestamp
 tree_size
 root_hash
 signature

and the case of one extension:

 log_id
 timestamp
 tree_size
 root_hash
 extension_0
 signature

if the start of the signature was mistakable for the start of an
SthExtension, then there is a potential for ambiguity.

This concatenated array representation is used in TreeHeadDataV2, as
well as in TLS 1.2 for client and server Extensions (a list of TLV
extensions at the tail of the Hello handshake message), and for
Certificate messages (a distinct and independent Certificate handshake
message).  But those uses have the advantage of an external frame
indicating the overall length of the repeated datatype.

I see four possible resolutions, none of which are that great; i'd be
happy with a better proposal:

(a) explicitly indicate the number of extensions to expect:

index ef69039..0b09171 100644
--- a/rfc6962-bis.xml
+++ b/rfc6962-bis.xml
@@ -654,6 +654,7 @@ d0 d1   d2 d3           d0 d1   d2 d3  d4 d5</artwork>
         uint64 timestamp;
         uint64 tree_size;
         NodeHash root_hash;
+        uint8 extension_count;
         SthExtension sth_extensions&lt;0..2^16-1&gt;;
         digitally-signed struct {
             TransItem merkle_tree_head;

(b) If the size of the signature is guaranteed to be known or computable
    in advance, move the extensions to follow the signature, so that
    they're delimited by the size and framing of the STHv2 itself:

--- a/rfc6962-bis.xml
+++ b/rfc6962-bis.xml
@@ -654,10 +654,10 @@ d0 d1   d2 d3           d0 d1   d2 d3  d4 d5</artwork>
         uint64 timestamp;
         uint64 tree_size;
         NodeHash root_hash;
-        SthExtension sth_extensions&lt;0..2^16-1&gt;;
         digitally-signed struct {
             TransItem merkle_tree_head;
         } signature;
+        SthExtension sth_extensions&lt;0..2^16-1&gt;;
     } SignedTreeHeadDataV2;</artwork>
         </figure>
         <t>

(c) If the size of the signature is guaranteed to be known or computable
    in advance, provide guidance on determining the signatures in a
    reverse scan:

--- a/rfc6962-bis.xml
+++ b/rfc6962-bis.xml
@@ -682,6 +682,12 @@ d0 d1   d2 d3           d0 d1   d2 d3  d4 d5</artwork>
           <spanx style="verb">sth_extensions</spanx> is a vector of 0 or more STH extensions. This vector MUST NOT include more than one extension with the same <spanx style="verb">sth_extension_type</spanx>. The extensions in the vector MUST be ordered by the value of the <spanx style="verb">sth_extension_type</spanx> field, smallest value first. If an implementation sees an extension that it does not understand, it SHOULD ignore that extension. Furthermore, an implementation MAY choose to ignore any extension(s) that it does understand.
         </t>
         <t>
+          To determine the size of the <spanx
+          style="verb">sth_extensions</spanx> field, subtract the
+          expected size of the <spanx style="verb">signature</spanx>
+          field from the size of the SignedTreeHeadDataV2 object.
+        </t>
+        <t>
           <spanx style="verb">merkle_tree_head</spanx> is a <spanx style="verb">TransItem</spanx> structure that MUST be of type <spanx style="verb">tree_head_v2</spanx> (see <xref target="tree_head"/>).
         </t>
       </section>

(d) treat the signature as a very special-cased extension:

--- a/rfc6962-bis.xml
+++ b/rfc6962-bis.xml
@@ -628,7 +628,7 @@ d0 d1   d2 d3           d0 d1   d2 d3  d4 d5</artwork>
           <spanx style="verb">root_hash</spanx> is the root of the Merkle Hash Tree.
         </t>
         <t>
-          <spanx style="verb">sth_extensions</spanx> matches the STH extensions of the corresponding STH.
+          <spanx style="verb">sth_extensions</spanx> matches the STH extensions of the corresponding STH, with the "signature" extension removed.
         </t>
       </section>
       <section title="Signed Tree Head (STH)" anchor="STH">
@@ -641,7 +641,7 @@ d0 d1   d2 d3           d0 d1   d2 d3  d4 d5</artwork>
           </preamble>
           <artwork>
     enum {
-        reserved(65535)
+        signature(65535)
     } SthExtensionType;
 
     struct {
@@ -655,9 +655,6 @@ d0 d1   d2 d3           d0 d1   d2 d3  d4 d5</artwork>
         uint64 tree_size;
         NodeHash root_hash;
         SthExtension sth_extensions&lt;0..2^16-1&gt;;
-        digitally-signed struct {
-            TransItem merkle_tree_head;
-        } signature;
     } SignedTreeHeadDataV2;</artwork>
         </figure>
         <t>
@@ -682,6 +679,15 @@ d0 d1   d2 d3           d0 d1   d2 d3  d4 d5</artwork>
           <spanx style="verb">sth_extensions</spanx> is a vector of 0 or more STH extensions. This vector MUST NOT include more than one extension with the same <spanx style="verb">sth_extension_type</spanx>. The extensions in the vector MUST be ordered by the value of the <spanx style="verb">sth_extension_type</spanx> field, smallest value first. If an implementation sees an extension that it does not understand, it SHOULD ignore that extension. Furthermore, an implementation MAY choose to ignore any extension(s) that it does understand.
         </t>
         <t>
+          The extension of type "signature" is special, in that it
+          contains a signature made by the log as defined in <xref
+          target="signature_algorithms"/>, and it is omitted from the
+          data being signed.  The <spanx
+          style=verb">sth_extensions</spanx> field of a
+          SignedTreeHeadDataV2 MUST contain a "signature" extension as
+          the last extension.
+        </t>
+        <t>
           <spanx style="verb">merkle_tree_head</spanx> is a <spanx style="verb">TransItem</spanx> structure that MUST be of type <spanx style="verb">tree_head_v2</spanx> (see <xref target="tree_head"/>).
         </t>
       </section>

Any suggestions on how to resolve this?

    --dkg

---

From: Rob Stradling <[email-masked]>
Date: Tue, 26 Apr 2016 21:01:00 +0100

sth_extensions is a variable-length vector (see 
https://tools.ietf.org/html/rfc5246#section-4.3).  "<0..2^16-1>" means 
that the first two bytes of the encoding of this field are the length of 
its value.  In the case of zero extensions, these two bytes will be: 
0x00 0x00.

There's no ambiguity AFAICT.

Does this resolve your concern?

On 26/04/16 20:13, Daniel Kahn Gillmor wrote:
> _______________________________________________
> Trans mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/trans
>

-- 
Rob Stradling
Senior Research & Development Scientist
COMODO - Creating Trust Online