Utility function for decoding an InclusionProof structure

RESOLVED FIXED in Firefox 57

Status

()

defect
RESOLVED FIXED
2 years ago
2 years ago

People

(Reporter: arroway, Assigned: arroway)

Tracking

(Blocks 1 bug)

unspecified
Firefox 57
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox57 fixed)

Details

Attachments

(3 attachments)

Decode an InclusionProof object from a reader in CTSerialization.cpp:

1. Define a class ct::InclusionProof that represents the proof
2. Parse the InclusionProofDataV2 and produce a ct::InclusionProof object

The struct of InclusionProofDatav2 is: 
struct {
    LogID log_id;
    uint64 tree_size;
    uint64 leaf_index;
    NodeHash inclusion_path<1..2^16-1>;
} InclusionProofDataV2;

We define an InclusionProof object as:
struct InclusionProof {
    Buffer logId;
    uint64_t treeSize;
    uint64_t leafIndex;
    Vector<Buffer, 32> inclusionPath;
};
Assignee: nobody → stephouillon
Blocks: 1341398
Comment on attachment 8842505 [details]
Bug 1343202 - Utility function for decoding an InclusionProof structure;

https://reviewboard.mozilla.org/r/116316/#review118354

Overall, this is on the right track.  Just need to clean up a few small things.

::: security/certverifier/CTInclusionProof.h:16
(Diff revision 2)
> +#include "pkix/Input.h"
> +#include "pkix/Result.h"
> +
> +namespace mozilla { namespace ct {
> +
> +typedef Vector<uint8_t> Buffer;

We shouldn't duplicate this code (and the comparison operators) between this file and `SignedCertificateTimestamp.h`.  Please find some way to define this once and include it both places.

::: security/certverifier/CTInclusionProof.h:40
(Diff revision 2)
> +  pkix::Result Verify(const Buffer& leaf, const Buffer& head) const;
> +
> +  Buffer logId;
> +  uint64_t treeSize;
> +  uint64_t leafIndex;
> +  Vector<Buffer, 32> inclusionPath;

Just to confirm my understanding: The `32` here is an initial capacity, and if the vector needs to grow beyond that, it will?

Also, please make the `32` a constant, e.g., `kInitialPathLengthCapacity`.

::: security/certverifier/CTSerialization.h:69
(Diff revision 2)
>    SignedCertificateTimestamp& output);
>  
>  // Encodes a list of SCTs (|scts|) to |output|.
>  pkix::Result EncodeSCTList(const Vector<pkix::Input>& scts, Buffer& output);
>  
> +// Or should input be InclusionProofDataV2 there?

Make this comment descriptive, like the ones above.

With regard to the question: Obviously, `input` should not be; it should be `pkix::Reader` (i.e., it's right as-is).  `output` should be whatever inclusion proof type we have, so right now `InclusionProof` is right.  I would support changing `InclusionProof` to `InclusionProofDataV2`, though, to align with the spec.

::: security/certverifier/CTSerialization.cpp:50
(Diff revision 2)
>  // Length of sha256RootHash buffer of SignedTreeHead
>  static const size_t kSthRootHashLength = 32;
>  
> +// Members of a Inclusion Proof struct
> +static const size_t kLogIdPrefixLengthBytes = 1;
> +static const size_t kProofTreeSizeLength = 8;

Nit: No need to say `Proof` here since it's not elsewhere.

::: security/certverifier/CTSerialization.cpp:573
(Diff revision 2)
> +  uint8_t i = 0;
> +
> +  Result rv = ReadVariableBytes<kLogIdPrefixLengthBytes>(reader, logId);
> +  if (rv != Success) {
> +    return rv;
> +  }

If `rv` were an `nsResult`, you could use `NS_ENSURE_SUCCESS` to make this a little less verbose.  Maybe keeler could advise on whether there's an equivalent here?  Or whether this whole idea is bad?

::: security/certverifier/CTSerialization.cpp:605
(Diff revision 2)
> +
> +    rv = InputToBuffer(hash, inclusionPath[i]);
> +    if (rv != Success) {
> +      return rv;
> +    }
> +    i++;

It would be better to have this as a `for` loop, so that all the relevant logic is together:

```
for (int i = 0; !reader.AtEnd(); i++) {...}
```

::: security/certverifier/tests/gtest/CTSerializationTest.cpp:290
(Diff revision 2)
> +  InclusionProof ipr;
> +  ASSERT_EQ(Success, DecodeInclusionProof(encodedProofReader, ipr));
> +  EXPECT_EQ(expectedLogId, ipr.logId);
> +  EXPECT_EQ(expectedTreeSize, ipr.treeSize);
> +  EXPECT_EQ(expectedLeafIndex, ipr.leafIndex);
> +  EXPECT_EQ(GetTestNodeHash0(), ipr.inclusionPath[0]);

Be sure to check that you have the right number of elements in the inclusion path.

::: security/certverifier/tests/gtest/CTTestUtils.h:48
(Diff revision 2)
> +// Returns the binary representation of a test serialized InclusionProof.
> +Buffer GetTestInclusionProof();
> +Buffer GetTestInclusionProofInvalidHashSize();
> +Buffer GetTestInclusionProofInvalidHash();
> +
> +// Returns the binary representation of a test serialized node hash from an

Nit: "node hashes"

::: security/certverifier/tests/gtest/CTTestUtils.cpp:411
(Diff revision 2)
>  {
>    return HexToBytes(kTestSignedCertificateTimestamp);
>  }
>  
> +// Merkle tree generated for data: 0x00, 0x01, 0x02, deadbeef
> +const char kTestInclusionProof[] =

Let's follow the structure of the file and put the data above the `GetX()` functions.  Also, please indent these to match the other examples.  I think it's fine to leave the elements split out, but I might combine the lenghts of the log ID and the node hashes with their contents on one line.

::: security/certverifier/tests/gtest/CTTestUtils.cpp:445
(Diff revision 2)
> +"02" // length of logId
> +"0000" // logId
> +"0000000000000004" // treesize
> +"0000000000000002" // leafindex
> +"0042" // inclusion path length
> +"20" // oversized

No, that's correct :)
Attachment #8842505 - Flags: review?(rlb) → review-
Comment on attachment 8842505 [details]
Bug 1343202 - Utility function for decoding an InclusionProof structure;

https://reviewboard.mozilla.org/r/116316/#review118444

Yep, this is the right idea. Just some nits and a few things to address.

::: security/certverifier/CTInclusionProof.h:18
(Diff revision 2)
> +
> +namespace mozilla { namespace ct {
> +
> +typedef Vector<uint8_t> Buffer;
> +
> +/* Represents a Merkle inclusion proof for purposes of serialization,

style nit: let's use //-style comments (or at least have the leading * at each line to indicate that it's still a comment)

::: security/certverifier/CTInclusionProof.h:35
(Diff revision 2)
> +        } InclusionProofDataV2;
> +*/
> +
> +struct InclusionProof
> +{
> +  pkix::Result Verify(const Buffer& leaf, const Buffer& head) const;

This isn't implemented yet, right? Let's just not declare it until it is.

::: security/certverifier/CTInclusionProof.h:50
(Diff revision 2)
> +namespace mozilla {
> +
> +// Comparison operators are placed under mozilla namespace since
> +// mozilla::ct::Buffer is actually mozilla::Vector.
> +bool operator==(const ct::Buffer& a, const ct::Buffer& b);
> +bool operator!=(const ct::Buffer& a, const ct::Buffer& b);

Similarly with these - let's not declare these until they're implemented.

::: security/certverifier/CTSerialization.h:15
(Diff revision 2)
>  #include "mozilla/Vector.h"
>  #include "pkix/Input.h"
>  #include "pkix/Result.h"
>  #include "SignedCertificateTimestamp.h"
>  #include "SignedTreeHead.h"
> +#include "CTInclusionProof.h"

nit: keep these sorted please

::: security/certverifier/CTSerialization.cpp:562
(Diff revision 2)
> +Result
> +DecodeInclusionProof(pkix::Reader& reader, InclusionProof& output)
> +{
> +  InclusionProof result;
> +
> +  Input logId;

Let's declare these where they're used (this isn't C).

::: security/certverifier/CTSerialization.cpp:575
(Diff revision 2)
> +  Result rv = ReadVariableBytes<kLogIdPrefixLengthBytes>(reader, logId);
> +  if (rv != Success) {
> +    return rv;
> +  }
> +
> +  rv = ReadUint<kProofTreeSizeLength>(reader, treeSize);

Any particular reason not to read directly into result.treeSize? (Same idea with leafIndex)

::: security/certverifier/CTSerialization.cpp:585
(Diff revision 2)
> +  rv = ReadUint<kLeafIndexLength>(reader, leafIndex);
> +  if (rv != Success) {
> +    return rv;
> +  }
> +
> +  rv = ReadFixedBytes(kInclusionPathLengthBytes, reader, pathSize);

Seems like we never validate pathSize, which we should do (and add some tests for).

::: security/certverifier/CTSerialization.cpp:601
(Diff revision 2)
> +
> +    if (!inclusionPath.append(Move(Buffer()))) {
> +      return pkix::Result::FATAL_ERROR_NO_MEMORY;
> +    }
> +
> +    rv = InputToBuffer(hash, inclusionPath[i]);

I would switch the order of the inclusionPath.append and InputToBuffer operations.

::: security/certverifier/CTSerialization.cpp:605
(Diff revision 2)
> +
> +    rv = InputToBuffer(hash, inclusionPath[i]);
> +    if (rv != Success) {
> +      return rv;
> +    }
> +    i++;

Actually, it looks like after switching the append/InputTobuffer, i isn't even necessary and you can keep this as while loop.

::: security/certverifier/tests/gtest/CTTestUtils.cpp:439
(Diff revision 2)
> +"30" // oversized
> +"48c90c8ae24688d6bef5d48a30c2cc8b6754335a8db21793cc0a8e3bed321729" // node hash 0
> +"20" // node hash size
> +"a20bf9a7cc2dc8a08f5f415a71b19f6ac427bab54d24eec868b5d3103449953a"; // node hash 1
> +
> +const char kTestInclusionProofInvalidHash[] =

A couple more testcase ideas:
* other missing or invalid-sized fields? (logId, treesize, leafindex, etc.)
* is an inclusion proof with an inclusion path length of 0 valid?
Attachment #8842505 - Flags: review?(dkeeler) → review-
Comment on attachment 8842505 [details]
Bug 1343202 - Utility function for decoding an InclusionProof structure;

https://reviewboard.mozilla.org/r/116316/#review118354

> If `rv` were an `nsResult`, you could use `NS_ENSURE_SUCCESS` to make this a little less verbose.  Maybe keeler could advise on whether there's an equivalent here?  Or whether this whole idea is bad?

(Harumph. reviewboard ate my original reply.)
NS_ENSURE_SUCCESS is a bit controversial. One reason to not use it is it hides a return. In this case, since Input/Reader and the rest of this code all use Result (and since there's not an equivalent macro), let's just stick with how it is.
Thanks!
I addressed most comments, below are some more detailed answers to some of them:

(In reply to Richard Barnes [:rbarnes] from comment #3)
> 
> ::: security/certverifier/CTInclusionProof.h:40
> (Diff revision 2)
> > +  pkix::Result Verify(const Buffer& leaf, const Buffer& head) const;
> > +
> > +  Buffer logId;
> > +  uint64_t treeSize;
> > +  uint64_t leafIndex;
> > +  Vector<Buffer, 32> inclusionPath;
> 
> Just to confirm my understanding: The `32` here is an initial capacity, and
> if the vector needs to grow beyond that, it will?

yes, each time their is a new hash needed to be added, we append a Buffer to the inclusionPath Vector.


> 
> ::: security/certverifier/CTSerialization.cpp:50
> (Diff revision 2)
> >  // Length of sha256RootHash buffer of SignedTreeHead
> >  static const size_t kSthRootHashLength = 32;
> >  
> > +// Members of a Inclusion Proof struct
> > +static const size_t kLogIdPrefixLengthBytes = 1;
> > +static const size_t kProofTreeSizeLength = 8;
> 
> Nit: No need to say `Proof` here since it's not elsewhere.

Actually, there is already a kTreeSizeLength just above (look for "Members of digitally-signed struct of a STH"), so I figured out it was better to have two separate variables even if they have the same value right now.




(In reply to David Keeler [:keeler] (use needinfo?) from comment #4)

> 
> ::: security/certverifier/CTSerialization.cpp:585
> (Diff revision 2)
> > +  rv = ReadUint<kLeafIndexLength>(reader, leafIndex);
> > +  if (rv != Success) {
> > +    return rv;
> > +  }
> > +
> > +  rv = ReadFixedBytes(kInclusionPathLengthBytes, reader, pathSize);
> 
> Seems like we never validate pathSize, which we should do (and add some
> tests for).

So I modified the code to get a new reader of the size of the inclusion proof, and deleted this pathSize variable I wasn't using ayway.

> 
> ::: security/certverifier/CTSerialization.cpp:601
> (Diff revision 2)
> > +
> > +    if (!inclusionPath.append(Move(Buffer()))) {
> > +      return pkix::Result::FATAL_ERROR_NO_MEMORY;
> > +    }
> > +
> > +    rv = InputToBuffer(hash, inclusionPath[i]);
> 
> I would switch the order of the inclusionPath.append and InputToBuffer
> operations.

The thing is if I don't make the append before, I don't have the memory allocated in the Buffer to move the hash, and the code fails.
Am I missing something there?

> 
> ::: security/certverifier/CTSerialization.cpp:605
> (Diff revision 2)
> > +
> > +    rv = InputToBuffer(hash, inclusionPath[i]);
> > +    if (rv != Success) {
> > +      return rv;
> > +    }
> > +    i++;
> 
> Actually, it looks like after switching the append/InputTobuffer, i isn't
> even necessary and you can keep this as while loop.

I didn't modified it for this new submission, apart from making it a for loop as richard suggested, because of my question above.

> 
> ::: security/certverifier/tests/gtest/CTTestUtils.cpp:439
> (Diff revision 2)
> > +"30" // oversized
> > +"48c90c8ae24688d6bef5d48a30c2cc8b6754335a8db21793cc0a8e3bed321729" // node hash 0
> > +"20" // node hash size
> > +"a20bf9a7cc2dc8a08f5f415a71b19f6ac427bab54d24eec868b5d3103449953a"; // node hash 1
> > +
> > +const char kTestInclusionProofInvalidHash[] =
> 
> A couple more testcase ideas:
> * other missing or invalid-sized fields? (logId, treesize, leafindex, etc.)
> * is an inclusion proof with an inclusion path length of 0 valid?

Done, but I didn't test every case you suggest because it looks redundant since it relies on the same functions used with the Reader.
I'll add them if I'm missing something there, though.
Comment on attachment 8842505 [details]
Bug 1343202 - Utility function for decoding an InclusionProof structure;

https://reviewboard.mozilla.org/r/116316/#review118836

Looking good. I think the main issue now is reorganizing the bad input tests (see comment).

::: security/certverifier/CTInclusionProof.h:16
(Diff revision 3)
> +#include "pkix/Input.h"
> +#include "pkix/Result.h"
> +
> +namespace mozilla { namespace ct {
> +
> +typedef Vector<uint8_t> Buffer;

Let's just re-order the commits so we don't even have to have this in the first place.

::: security/certverifier/CTSerialization.cpp:587
(Diff revision 3)
> +  }
> +
> +  Reader pathReader(pathInput);
> +  Vector<Buffer, 32> inclusionPath;
> +
> +  for(int i=0; !pathReader.AtEnd(); i++) {

This seems to work for me:

    while (!pathReader.AtEnd()) {
      Input hash;
      rv = ReadVariableBytes<kNodeHashPrefixLengthBytes>(pathReader, hash);
      if (rv != Success) {
        return rv;
      }

      Buffer hashBuffer;
      rv = InputToBuffer(hash, hashBuffer);
      if (rv != Success) {
        return rv;
      }

      if (!inclusionPath.append(Move(hashBuffer))) {
        return pkix::Result::FATAL_ERROR_NO_MEMORY;
      }
    }

::: security/certverifier/CTSerialization.cpp:605
(Diff revision 3)
> +      return rv;
> +    }
> +
> +  }
> +
> +  rv = InputToBuffer(logId, result.logId);

Might make sense to put this just after reading logId, but not a big deal.

::: security/certverifier/tests/gtest/CTSerializationTest.cpp:279
(Diff revision 3)
> +  const uint64_t expectedLeafIndex = 2;
> +  const uint64_t expectedInclusionPathElements = 2;
> +
> +  const uint8_t EXPECTED_LOGID[] = { 0x00, 0x00 };
> +  Buffer expectedLogId;
> +  MOZ_RELEASE_ASSERT(expectedLogId.append(EXPECTED_LOGID, 2));

nit: maybe mozilla::ArrayLength(EXPECTED_LOGID) or sizeof(EXPECTED_LOGID)

::: security/certverifier/tests/gtest/CTSerializationTest.cpp:307
(Diff revision 3)
> +  ASSERT_EQ(Result::ERROR_BAD_DER, DecodeInclusionProof(encodedProofReader, ipr));
> +
> +  encodedProof.clear();
> +
> +  encodedProof = GetTestInclusionProofInvalidHash();
> +  encodedProofInput.Init(InputForBuffer(encodedProof));

This is my mistake for not noticing it before, but Input is designed to not be re-used in this way (remember to always check the return values when using these APIs). I recommend restructuring this TEST_F to be a parameterized test (TEST_P). Here's a good example if you're not already familiar with that: https://dxr.mozilla.org/mozilla-central/rev/b23d6277acca34a4b1be9a4c24efd3b999e47ec3/security/pkix/test/gtest/pkixcert_extension_tests.cpp#228

::: security/certverifier/tests/gtest/CTTestUtils.cpp:26
(Diff revision 3)
>  #include "pkix/Result.h"
>  #include "pkixcheck.h"
>  #include "pkixutil.h"
>  #include "SignedCertificateTimestamp.h"
>  #include "SignedTreeHead.h"
> +#include "CTInclusionProof.h"

nit: keep sorted

::: security/certverifier/tests/gtest/CTTestUtils.cpp:383
(Diff revision 3)
> +  "020000"
> +  "00000000000000041234" // treesize
> +  "0000000000000002" // leafindex
> +  "0000"
> +  "2048c90c8ae24688d6bef5d48a30c2cc8b6754335a8db21793cc0a8e3bed321729" // node hash 0
> +  "20a20bf9a7cc2dc8a08f5f415a71b19f6ac427bab54d24eec868b5d3103449953a"; // node hash 1

nit: I don't think the two hashes are relevant to this test-case (as in, you should be able to omit them)
Attachment #8842505 - Flags: review?(dkeeler) → review-
Comment on attachment 8843409 [details]
Bug 1343202 - Move Buffer definition into its own file;

https://reviewboard.mozilla.org/r/117156/#review118856

r=me with the commits reordered so this is first.
Attachment #8843409 - Flags: review?(dkeeler) → review+
Comment on attachment 8843409 [details]
Bug 1343202 - Move Buffer definition into its own file;

https://reviewboard.mozilla.org/r/117156/#review119622

The code looks fine to me.  I just wonder if this is the right place, or if we can find something more elegant.

Nathan (choosing an mfbt peer at random): Would it make sense to fold these operators in as a special case in `Vector.h`?
Attachment #8843409 - Flags: review?(rlb) → review+
Flags: needinfo?(nfroyd)
Comment on attachment 8842505 [details]
Bug 1343202 - Utility function for decoding an InclusionProof structure;

https://reviewboard.mozilla.org/r/116316/#review119624

Clearing review flag pending responses to keeler's review

::: security/certverifier/CTInclusionProof.h:31
(Diff revision 3)
> +//         LogID log_id;
> +//         uint64 tree_size;
> +//         uint64 leaf_index;
> +//         NodeHash inclusion_path<1..2^16-1>;
> +//     } InclusionProofDataV2;
> +//

Nit: Extra comment line

::: security/certverifier/CTInclusionProof.h:33
(Diff revision 3)
> +//         uint64 leaf_index;
> +//         NodeHash inclusion_path<1..2^16-1>;
> +//     } InclusionProofDataV2;
> +//
> +
> +const uint64_t kInitialPathLengthCapacity = 32;

Nit: Does this value need to be exposed to consumers of this struct?
Attachment #8842505 - Flags: review?(rlb)
(In reply to Richard Barnes [:rbarnes] from comment #11)
> Comment on attachment 8843409 [details]
> Bug 1343202 - Move Buffer definition into its own file;
> 
> https://reviewboard.mozilla.org/r/117156/#review119622
> 
> The code looks fine to me.  I just wonder if this is the right place, or if
> we can find something more elegant.
> 
> Nathan (choosing an mfbt peer at random): Would it make sense to fold these
> operators in as a special case in `Vector.h`?

I thought I remembered us *not* having operator== for Vector for some reason, but I can't find the particular discussion that I'm (mis)remembering.

It would make sense, probably adding a static equal() method to VectorImpl and its POD specialization:

https://dxr.mozilla.org/mozilla-central/source/mfbt/Vector.h#56

and then adding an operator== method to Vector itself or operator== function overloads.

I would be OK with filing a followup bug for that in Core::MFBT, though; it's not crucial that we fix it here, and filing the separate bug would give more people the ability to weigh in.
Flags: needinfo?(nfroyd)
Back on working on this patch.
I started to re-implement how the tests for the FailsDecodingInvalidInclusionProof testcases, changing the TEST_F to a TEST_P function.

So far I got something like what is shown in the attached CTSerialization.cpp file. It is not compiling in the current state because of the call to GetTestInclusionProofInvalidHashSize() to fill in the static const ProofInputTestcase structure (PROOFINPUT_TESTCASES). The role of this function is to get hexadecimal test data as bytes. One solution would be to put directly in the CTSerialization.cpp the data as bytes, but it's not very elegant. 

What other functions seem to do is using the Setup() function: GetTestInclusionProofInvalidHashSize() (and similar functions for the tests) would be called in the SetUp() function, in a similar way to https://dxr.mozilla.org/mozilla-central/source/security/certverifier/tests/gtest/CTObjectsExtractorTest.cpp#26

What do you think, would that be acceptable?

With ckerschb, we're also willing to move all the code related to Binary Transparency in separate a folder/files, if that's fine with you.
Flags: needinfo?(dkeeler)
The test reorganization is looking like a good approach. I think unfortunately the input test data does have to be static, although maybe there's a way to define the test cases in a static, human-readable way that we can then convert to the binary input on the fly, if that answers your question.
Flags: needinfo?(dkeeler)
Changes done:
* I fixed the code according to the comments from the previous reviews
* I updated the tests
* I moved code related to Binary Transparency in their own file (BTVerifier.* and BTSerializationTest.cpp)
* and I created CTUtils.cpp and CTUtils.h and moved their some utility code used for deserialization in both BTVerifier.cpp and CTSerialization.cpp.
Comment on attachment 8842505 [details]
Bug 1343202 - Utility function for decoding an InclusionProof structure;

https://reviewboard.mozilla.org/r/116316/#review171308

Cool - this is looking good. I guess top-level comments would be:
a) there seems to be some redundant code in CTUtils.cpp / CTUtils.h - we should de-duplicate that
b) let's try to preserve repository history as much as possible with `hg mv`/`hg cp` where appropriate
c) this is minor, but keep an eye out for #includes that aren't actually necessary
I also made some suggestions for additional tests and other items that should be addressed.

::: security/certverifier/BTInclusionProof.h:1
(Diff revision 4)
> +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */

This is CTInclusionProof.h, right? Let's either `hg mv` it or modify the previous changeset to call it BTInclusionProof.h from the beginning.

::: security/certverifier/BTInclusionProof.h:13
(Diff revision 4)
> +#define BTInclusionProof_h
> +
> +#include "Buffer.h"
> +#include "mozilla/Vector.h"
> +#include "pkix/Input.h"
> +#include "pkix/Result.h"

nit: not a big deal, but I don't think Input.h or Result.h are used in this file.

::: security/certverifier/BTVerifier.h:11
(Diff revision 4)
> +
> +#ifndef BTVerifier_h
> +#define BTVerifier_h
> +
> +#include "BTInclusionProof.h"
> +#include "mozilla/Vector.h"

nit: same kind of thing - it doesn't look like Vector.h is used in this file.

::: security/certverifier/BTVerifier.h:18
(Diff revision 4)
> +#include "pkix/Result.h"
> +
> +namespace mozilla { namespace ct {
> +
> +// Decodes an Inclusion Proof (InclusionProofDataV2 as defined in RFC 6962-bis).
> +pkix::Result DecodeInclusionProof(pkix::Reader& input,

Is this intended to consume the entirety of the input or no? (either way, we should probably document it, and if yes, we need to check that we're at the end in the implementation)

::: security/certverifier/CTSerialization.cpp:18
(Diff revision 4)
>  
>  typedef mozilla::pkix::Result Result;
>  
>  // Note: length is always specified in bytes.
>  // Signed Certificate Timestamp (SCT) Version length
> -static const size_t kVersionLength = 1;
> +//static const size_t kVersionLength = 1;

nit: these should be removed rather than commented out

::: security/certverifier/CTSerialization.cpp
(Diff revision 4)
>  enum class SignatureType {
>    CertificateTimestamp = 0,
>    TreeHash = 1,
>  };
>  
> -// Reads a TLS-encoded variable length unsigned integer from |in|.

For moving a large chunk of code like this, I think it might be helpful to `hg cp` this file and then remove this chunk from the original and everything else from the copy (that way, we preserve history a bit).

::: security/certverifier/CTUtils.cpp:1
(Diff revision 4)
> +/* -*- Mode: C++; tab-width: 6; indent-tabs-mode: nil; c-basic-offset: 2 -*- */

Is this largely a copy of CTUtils.h? This seems unnecessary.

::: security/certverifier/tests/gtest/BTSerializationTest.cpp:10
(Diff revision 4)
> + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
> +
> +#include "BTVerifier.h"
> +#include "CTTestUtils.h"
> +#include "gtest/gtest.h"
> +#include "mozilla/Move.h"

Is Move used in this file?

::: security/certverifier/tests/gtest/BTSerializationTest.cpp:46
(Diff revision 4)
> +{
> +  const uint64_t expectedTreeSize = 4;
> +  const uint64_t expectedLeafIndex = 2;
> +  const uint64_t expectedInclusionPathElements = 2;
> +
> +  const uint8_t EXPECTED_LOGID[] = { 0x00, 0x00 };

Hmmm - having '00 00' as the log id seems like we could miss bugs where the parsed log id is uninitialized and defaults to 0. Let's have a non-zero test id?

::: security/certverifier/tests/gtest/BTSerializationTest.cpp:107
(Diff revision 4)
> +  Input encodedProofInput = InputForBuffer(mTestInclusionProofPathLengthTooLarge);
> +  Reader encodedProofReader(encodedProofInput);
> +  InclusionProofDataV2 ipr;
> +
> +  ASSERT_EQ(Result::ERROR_BAD_DER, DecodeInclusionProof(encodedProofReader, ipr));
> +}

I'm not seeing a TEST_F that uses the InvalidHashSize or InvalidHash test-cases.

::: security/certverifier/tests/gtest/CTTestUtils.cpp:330
(Diff revision 4)
>    "e6ce65c1e51b47bf7c8950f80bccd57168567954ed35b0ce9346065a5eae"
>    "5bf95d41da8e27cee9eeac688f4bd343f9c2888327abd8b9f68dcb1e3050"
>    "041d31bda8e2dd6d39b3664de5ce0870f5fc7e6a00d6ed00528458d953d2"
>    "37586d73";
>  
> +// Merkle tree generated for data: 0x00, 0x01, 0x02, deadbeef

Would it be possible to briefly describe how the tree is generated given this data? Or maybe a pointer to documentation on it?

::: security/certverifier/tests/gtest/CTTestUtils.cpp:345
(Diff revision 4)
> +  "48c90c8ae24688d6bef5d48a30c2cc8b6754335a8db21793cc0a8e3bed321729";
> +
> +const char kTestNodeHash1[] =
> +  "a20bf9a7cc2dc8a08f5f415a71b19f6ac427bab54d24eec868b5d3103449953a";
> +
> +const char kTestInclusionProofRandom[] = "12345678";

I'm not sure "Random" is the best description of this. Maybe "UnrelatedData" or "UnexpectedData" or "NonInclusionProofData" or something"?

::: security/certverifier/tests/gtest/CTTestUtils.cpp:388
(Diff revision 4)
> +  "2048c90c8ae24688d6bef5d48a30c2cc8b6754335a8db21793cc0a8e3bed321729" // node hash 0
> +  "20a20bf9a7cc2dc8a08f5f415a71b19f6ac427bab54d24eec868b5d3103449953a"; // node hash 1
> +
> +const char kTestInclusionProofPathLengthTooLarge[] =
> +  "020000"
> +  "0000000000000004" // treesize

Might be good to have some testcases with outlandish values for treesize and leafindex.
Attachment #8842505 - Flags: review?(dkeeler) → review-
Comment on attachment 8842505 [details]
Bug 1343202 - Utility function for decoding an InclusionProof structure;

https://reviewboard.mozilla.org/r/116316/#review171660

Steph, I only took a quick look since I am a little short on time right now. It seems David provided some good feedback. Once you have incorporated his suggestions I'll take a closer look. Overall that already looks pretty good to me. Thanks for working on this!

::: security/certverifier/BTVerifier.cpp:61
(Diff revision 4)
> +  if (pathInput.GetLength() < 1) {
> +    return pkix::Result::ERROR_BAD_DER;
> +  }
> +
> +  Reader pathReader(pathInput);
> +  Vector<Buffer, 32> inclusionPath;

nit: can we replace the hardcoded 32 with kInitialPathLengthCapacity? Is that the same?

::: security/certverifier/CTUtils.h:29
(Diff revision 4)
> +
> +typedef mozilla::pkix::Result Result;
> +
> +// Note: length is always specified in bytes.
> +// Signed Certificate Timestamp (SCT) Version length
> +//static const size_t kVersionLength = 1;

nit: please remove if not needed.

::: security/certverifier/CTUtils.h:61
(Diff revision 4)
> +// Performs overflow sanity checks and calls UncheckedReadUint.
> +template <size_t length, typename T>
> +static inline Result
> +ReadUint(Reader& in, T& out)
> +{
> +  uint64_t value;

nit: please initialize to 0

::: security/certverifier/CTUtils.cpp:18
(Diff revision 4)
> +typedef mozilla::pkix::Result Result;
> +
> +// Note: length is always specified in bytes.
> +// Signed Certificate Timestamp (SCT) Version length
> +//static const size_t kVersionLength = 1;
> +static const size_t kVersionLength = 1;

nit: please remove if not needed
Attachment #8842505 - Flags: review?(ckerschb)
I addressed your comments, apart from one I'm not sure about:
 
(In reply to David Keeler [:keeler] (use needinfo?) from comment #19)
> ::: security/certverifier/BTVerifier.h:18
> (Diff revision 4)
> > +#include "pkix/Result.h"
> > +
> > +namespace mozilla { namespace ct {
> > +
> > +// Decodes an Inclusion Proof (InclusionProofDataV2 as defined in RFC 6962-bis).
> > +pkix::Result DecodeInclusionProof(pkix::Reader& input,
> 
> Is this intended to consume the entirety of the input or no? (either way, we
> should probably document it, and if yes, we need to check that we're at the
> end in the implementation)
> 

The inclusion proof will be read from an xml file, from a specific field. So I would say yes, the function is intended to consume the entirety of the input. I've looked at the other decoding functions, in CTSerialization.cpp mainly, but haven't found an example of how we can check we're at the end (something like checking the reader doesn't have any other data we can read from I guess?).
Comment on attachment 8842505 [details]
Bug 1343202 - Utility function for decoding an InclusionProof structure;

https://reviewboard.mozilla.org/r/116316/#review173636

Right - to check that a Result's input has been completely consumed (and that there isn't extra data), use `reader.AtEnd()` (see the second comment).
Also, I'm sorry, but my previous advice on `CTUtils.h` was actually a step in the wrong direction, and I'm going to ask you to undo a bit of the work that's gone into this patch. Basically, I think we should make that file as small as possible - see the 3rd comment.
Other than that, this is almost ready to go with just some minor other comments.

::: security/certverifier/BTInclusionProof.h:1
(Diff revision 5)
> +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */

Looks like this is still missing the `hg mv` from the previous changeset's CTInclusionProof.h (right now these two changesets create two nearly identical files BTInclusionProof.h and CTInclusionProof.h, which seems unnecessary).

::: security/certverifier/BTVerifier.cpp:97
(Diff revision 5)
> +  }
> +
> +  result.inclusionPath = Move(inclusionPath);
> +
> +  output = Move(result);
> +  return Success;

To check that we've consumed all the input for reader, just use `reader.AtEnd()` (it returns a bool, so that'll have to be converted to a Result.

::: security/certverifier/CTUtils.h:1
(Diff revision 5)
>  /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */

Hmmm - I probably should have thought more about this file in earlier reviews. My main question is, why is it necessary? From my reading, it provides `ReadUint` and `ReadVariableBytes` for `BTVerifier.cpp`. However, there is a lot more code in `CTUtils.h` than just these implementations. Furthermore, there's a nontrivial amount of *code* in `CTUtils.h`, rather than just declarations. I think it would be best to minimize the API exposed in `CTUtils.h` as much as possible. It looks like we can trim it to just the declarations of `ReadVariableBytes` and `ReadUint`.

::: security/certverifier/moz.build:18
(Diff revision 5)
> +    'BTVerifier.h',
>      'Buffer.h',
>      'CertVerifier.h',
>      'CTLog.h',
>      'CTPolicyEnforcer.h',
> +    'CTUtils.h',

This doesn't seem to be necessary to export.

::: security/certverifier/tests/gtest/BTSerializationTest.cpp:78
(Diff revision 5)
> +  ASSERT_EQ(Result::ERROR_BAD_DER, DecodeInclusionProof(encodedProofReader, ipr));
> +}
> +
> +TEST_F(BTSerializationTest, FailsDecodingInvalidHashSize)
> +{
> +  Input encodedProofInput = InputForBuffer(mTestInclusionProofInvalidHashSize);

Still missing a test for InvalidHash.

::: security/certverifier/tests/gtest/CTTestUtils.cpp:340
(Diff revision 5)
> +// Hash (also called 'Merkle Tree head') for that tree.
> +// This follows the structure defined in RFC 6962-bis.
> +//
> +// https://tools.ietf.org/html/draft-ietf-trans-rfc6962-bis-24#section-2.1
> +
> +const char kTestInclusionProof[] =

We should probably add a testcase for "extra data after the proof"
Attachment #8842505 - Flags: review?(dkeeler) → review-
Comment on attachment 8842505 [details]
Bug 1343202 - Utility function for decoding an InclusionProof structure;

https://reviewboard.mozilla.org/r/116316/#review174580

As discussed over IRC, let's first incorporate Keelers suggestions and then I'll have a look - clearing r? until then - thanks!
Attachment #8842505 - Flags: review?(ckerschb)
Sorry for the mess with CTInclusionProof.h, I didn't check I was introducing it in the first commit and had only made the change in the second one. 
Anyway, here are the changes for this patch:
* I added a condition to test whether the entirety of the input is consumed after we read the inclusionPath.
* I added a test for an InvalidHash, and one for an input with a valid inclusion proof with extra data.
* I made the changes for CTUtils.h : now, this file only declares the ReadUint and ReadVariableBytes functions (and the code for the function body stays in CTSerialization.cpp), and it is not exported in moz.build
Comment on attachment 8842505 [details]
Bug 1343202 - Utility function for decoding an InclusionProof structure;

https://reviewboard.mozilla.org/r/116316/#review174978

Great! I think this is ready to go. I just noted a few style nits.

::: security/certverifier/CTSerialization.cpp:76
(Diff revision 6)
>    return Success;
>  }
>  
>  // Performs overflow sanity checks and calls UncheckedReadUint.
>  template <size_t length, typename T>
> -static inline Result
> +Result ReadUint(Reader& in, T& out)

nit: return value on its own line

::: security/certverifier/CTSerialization.cpp:101
(Diff revision 6)
>  
>  // Reads a length-prefixed variable amount of bytes from |in|, updating |out|
>  // on success. |prefixLength| indicates the number of bytes needed to represent
>  // the length.
>  template <size_t prefixLength>
> -static inline Result
> +Result ReadVariableBytes(Reader& in, Input& out)

nit: same here

::: security/certverifier/CTUtils.h:20
(Diff revision 6)
> +// Reads a TLS-encoded variable length unsigned integer from |in|.
> +// The integer is expected to be in big-endian order, which is used by TLS.
> +// Note: checks if the output parameter overflows while reading.
> +// |length| indicates the size (in bytes) of the serialized integer.
> +template <size_t length, typename T>
> +pkix::Result

For declarations, I think these are short enough to have the return value and function name/parameters on the same line.
Attachment #8842505 - Flags: review?(dkeeler) → review+
Nits fixed!
Comment on attachment 8842505 [details]
Bug 1343202 - Utility function for decoding an InclusionProof structure;

https://reviewboard.mozilla.org/r/116316/#review175294

that looks great and ended up being a way smaller and cleaner patch in the end, thanks. r=ckerschb
Attachment #8842505 - Flags: review?(ckerschb) → review+
Tests on try looks ok (failures don't seem related to this bug) https://treeherder.mozilla.org/#/jobs?repo=try&revision=3b90bc944ee4dbb95a4e3aabda688994b5916e85&selectedJob=124136201, so flagging for checkin-needed.
Autoland can't push this until all pending issues are marked as resolved in MozReview.
Keywords: checkin-needed
Stephanie, can you mark those as resolved. I guess there is nothing missing, right?
Flags: needinfo?(stephouillon)
I marked the issues as resolved, I didn't know it needed to be done for each diff revision.
Flags: needinfo?(stephouillon)
Pushed by ryanvm@gmail.com:
https://hg.mozilla.org/integration/autoland/rev/8192716611b6
Move Buffer definition into its own file; r=keeler,rbarnes
https://hg.mozilla.org/integration/autoland/rev/ee4c6aa368ff
Utility function for decoding an InclusionProof structure; r=ckerschb,keeler
Keywords: checkin-needed
https://hg.mozilla.org/mozilla-central/rev/8192716611b6
https://hg.mozilla.org/mozilla-central/rev/ee4c6aa368ff
Status: NEW → RESOLVED
Closed: 2 years ago
Resolution: --- → FIXED
Target Milestone: --- → Firefox 57
You need to log in before you can comment on or make changes to this bug.