Subject: Re: [Trans] Spinning a new version draft of draft-ietf-trans-rfc6962-bis

From: "Salz, Rich" <[email-masked]>
Date: Wed, 12 May 2021 18:34:56 +0000

There are still open open issues from Ben Kaduk's DISCUSS ballot, which I listed in https://mailarchive.ietf.org/arch/msg/trans/yFJRli55wJ68EcQy5H97b97t8yY/

One of them requires someone in the WG to confirm.  The other two require more input from Ben.

---

From: Roman Danyliw <[email-masked]>
Date: Wed, 12 May 2021 19:02:57 +0000

Hi Rich!

> -----Original Message-----
> From: Salz, Rich <[email-masked]>
> Sent: Wednesday, May 12, 2021 2:35 PM
> To: Roman Danyliw <[email-masked]>; Trans <[email-masked]>
> Subject: Re: [Trans] Spinning a new version draft of draft-ietf-trans-rfc6962-bis
> 
> There are still open open issues from Ben Kaduk's DISCUSS ballot, which I listed
> in https://mailarchive.ietf.org/arch/msg/trans/yFJRli55wJ68EcQy5H97b97t8yY/
> 

Thanks for the clarification.  I'll restate that that "_almost_ IESG feedback appears addressed".

Roman

---

From: Paul Wouters <[email-masked]>
Date: Wed, 12 May 2021 15:08:59 -0400 (EDT)

> One of them requires someone in the WG to confirm.  The other two require more input from Ben.

The two issues needing input from Ben seem to be thing Ben needs to act
on. So please disregard these from now as there is nothing we can do
there. That leaves only one issue unconfirmed:

 	In 2.1.4.1 “Generating a Consistency Proof”:

 	>   If m <= k, the right subtree entries D[k:n] only exist in the current
 	>   tree.  We prove that the left subtree entries D[0:k] are consistent
 	>   and add a commitment to D[k:n]:
 	>
 	>   SUBPROOF(m, D_n, b) = SUBPROOF(m, D[0:k], b) : MTH(D[k:n])
 	>
 	>This 'b' is always 'false', right?

 	Does “this b” mean the one on the right-hand side of the equal sign?  And if so, does the WG have an answer to the question?

 	I believe this refers to the table in 5.5 “Retrieve Merkle Inclusion Proof, Signed Tree Head and Consistency Proof by Leaf Hash”:

Can one or two people from the WG please clarify this issue so we can cut a new draft and start a WGLC.

Paul

---

From: Rob Stradling <[email-masked]>
Date: Thu, 13 May 2021 15:02:52 +0000

> This 'b' is always 'false', right?

Despite being one of the document authors, I am yet to fully get my head around Section 2 (Cryptographic Components), so yesterday I sought help off-list from several folks who I'm sure have a better grasp of the crypto.  Here's what we came up with (which I believe I now understand and agree with! :-) ):

Short answer:
"PROOF(m, D_n) = SUBPROOF(m, D_n, true)" appears just a few lines above, so no.

Long answer:
No.  The first substitution of "PROOF(m, D_n)" gives you an invocation of SUBPROOF with b=true.  As you recurse down, you may reach a call where all further recursive calls have b=false, but the base case should be b=true.
SUBPROOF is defined in four cases.  b could be either true or false depending on whether and how it was invoked by the third case, fourth case, or the base case from the definition of PROOF.
The SUBPROOF case that Ben's question refers to is for m != n, m <= k, and any b.

________________________________
From: Trans <[email-masked]> on behalf of Paul Wouters <[email-masked]>
Sent: 12 May 2021 20:08
To: Salz, Rich <rsalz=[email-masked]>
Cc: Roman Danyliw <[email-masked]>; Trans <[email-masked]>
Subject: Re: [Trans] Spinning a new version draft of draft-ietf-trans-rfc6962-bis

CAUTION: This email originated from outside of the organization. Do not click links or open attachments unless you recognize the sender and know the content is safe.

On Wed, 12 May 2021, Salz, Rich wrote:

> There are still open open issues from Ben Kaduk's DISCUSS ballot, which I listed in https://nam04.safelinks.protection.outlook.com/?url=https%3A%2F%2Fmailarchive.ietf.org%2Farch%2Fmsg%2Ftrans%2FyFJRli55wJ68EcQy5H97b97t8yY%2F&amp;data=04%7C01%7C%7C1d243dd6e8544642471908d915797540%7C0e9c48946caa465d96604b6968b49fb7%7C0%7C0%7C637564433669991858%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&amp;sdata=BUOYOEvOmgRkppZonghLgulUgUSiD9v6FYZGDCg480I%3D&amp;reserved=0
>

Paul

_______________________________________________
Trans mailing list
[email-masked]
https://nam04.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.ietf.org%2Fmailman%2Flistinfo%2Ftrans&amp;data=04%7C01%7C%7C1d243dd6e8544642471908d915797540%7C0e9c48946caa465d96604b6968b49fb7%7C0%7C0%7C637564433669991858%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&amp;sdata=hqFZywSs%2Fb3LsLjW5cG18pxSjrvdvU0mYzg%2BC8aVvDc%3D&amp;reserved=0

---

From: Benjamin Kaduk <[email-masked]>
Date: Thu, 13 May 2021 08:11:55 -0700

> The SUBPROOF case that Ben's question refers to is for m != n, m <= k, and any b.

Thanks, Rob.

I had tentatively reached a similar conclusion yesterday, but didn't get a
chance to remind myself of what the "D[0:m]" referenced in the definition
of the 'b' parameter was.

For what little it's worth, I think my question originated from a
misreading of the surrounding text:

   SUBPROOF(m, D[m], false) = {MTH(D[m])}

   For m < n, let k be the largest power of two smaller than n.  The
   subproof is then defined recursively.

   If m > k, the left subtree entries D[0:k] are identical in both
   trees.  We prove that the right subtree entries D[k:n] are consistent
   and add a commitment to D[0:k].

   SUBPROOF(m, D_n, b) = SUBPROOF(m - k, D[k:n], false) : MTH(D[0:k])

I suspect I noticed that there was a literal 'false' in the first and last
SUBPROOF lines, and missed the boundary between the "m==n" case (first
SUBPROOF) and the "m < n" case (last two SUBPROOFs, that handle the m<=k
and m>k sub-cases respectively).  If I was thinking that the last two were
both somehow subcases of the first, then it would be natural (but wrong) to
assume that the literal 'false' should be in all three SUBPROOFs.

Sorry to have caused the extra work,

Ben

---

From: Rob Stradling <[email-masked]>
Date: Thu, 13 May 2021 16:20:50 +0000

Hi Ben.  No worries, and thanks for explaining your thinking.  Rich just suggested a minor rewording to make that section slightly clearer (https://github.com/google/certificate-transparency-rfcs/pull/331/files, which I've just merged).

I'll submit a fresh I-D shortly.

________________________________
From: Benjamin Kaduk <[email-masked]>
Sent: 13 May 2021 16:11
To: Rob Stradling <[email-masked]>
Cc: Paul Wouters <[email-masked]>; Salz, Rich <rsalz=[email-masked]>; Roman Danyliw <[email-masked]>; Trans <[email-masked]>
Subject: Re: [Trans] Spinning a new version draft of draft-ietf-trans-rfc6962-bis

On Thu, May 13, 2021 at 03:02:52PM +0000, Rob Stradling wrote:
> On https://nam04.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdatatracker.ietf.org%2Fdoc%2Fdraft-ietf-trans-rfc6962-bis%2Fballot%2F&amp;data=04%7C01%7C%7Ce74dd6de1a3a413e93d808d916217962%7C0e9c48946caa465d96604b6968b49fb7%7C0%7C0%7C637565155298755591%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&amp;sdata=yhtv6tmWNkBjCBms3Mm5Ca%2BENQNvvRiR0GjsAgCKXQ0%3D&amp;reserved=0, Ben Kaduk wrote:

Thanks, Rob.

Ben