[Keytrans] Re: [EXTERNAL] Re: New Version Notification for draft-keytrans-mcmillion-protocol-01.txt

"Esha Ghosh (SHE/HER)" <Esha.Ghosh@microsoft.com> Mon, 11 November 2024 19:25 UTC

From: "Esha Ghosh (SHE/HER)" <Esha.Ghosh@microsoft.com>
To: Brendan McMillion <brendanmcmillion@gmail.com>
Thread-Topic: [EXTERNAL] [Keytrans] Re: New Version Notification for draft-keytrans-mcmillion-protocol-01.txt
Thread-Index: AQHbHez1xbikquhwEkGABbO9vrOVJrKfpg/AgBLvpwCAAAuomA==
Date: Mon, 11 Nov 2024 19:25:51 +0000
Message-ID: <CY5PR21MB3588469EBF6C7C759E0098108B582@CY5PR21MB3588.namprd21.prod.outlook.com>
References: <172887577824.782988.12440844536930810184@dt-datatracker-78dc5ccf94-w8wgc> <CAJTd26+m7pCHd4JO85ANJnXaDr6xofnTu+XuHkZOLe3_h9nvYg@mail.gmail.com> <DM6PR21MB1338CE3D9036B4125F2077C28B542@DM6PR21MB1338.namprd21.prod.outlook.com> <CAJTd26+9-fUAXNxUdS8t0mhYUa0qH8YoxtxBBGoiy2ACcpSGOQ@mail.gmail.com>
In-Reply-To: <CAJTd26+9-fUAXNxUdS8t0mhYUa0qH8YoxtxBBGoiy2ACcpSGOQ@mail.gmail.com>
Accept-Language: en-US
Content-Language: en-US
msip_labels: MSIP_Label_f42aa342-8706-4288-bd11-ebb85995028c_Enabled=True;MSIP_Label_f42aa342-8706-4288-bd11-ebb85995028c_SiteId=72f988bf-86f1-41af-91ab-2d7cd011db47;MSIP_Label_f42aa342-8706-4288-bd11-ebb85995028c_SetDate=2024-11-11T19:25:53.227Z;MSIP_Label_f42aa342-8706-4288-bd11-ebb85995028c_Name=General;MSIP_Label_f42aa342-8706-4288-bd11-ebb85995028c_ContentBits=0;MSIP_Label_f42aa342-8706-4288-bd11-ebb85995028c_Method=Standard;
authentication-results: dkim=none (message not signed) header.d=none;dmarc=none action=none header.from=microsoft.com;
x-ms-publictraffictype: Email
x-ms-traffictypediagnostic: CY5PR21MB3588:EE_|CY5PR21MB3519:EE_
x-ms-office365-filtering-correlation-id: 2443e52b-346c-4fcf-1eda-08dd0286a753
x-ms-exchange-senderadcheck: 1
x-ms-exchange-antispam-relay: 0
x-microsoft-antispam: BCL:0;ARA:13230040|366016|376014|10070799003|4022899009|1800799024|8096899003|38070700018;
x-microsoft-antispam-message-info: 2Z+lgG33E2YX7erIURTAD+fKEmIIaGOPu5qcW+GaZRNTgzN5NvjE40bwSQ+zRuFCjbQNxbBld3bQ/FciUaRYal3xFCwEuYs3QBxL85kKW8KGOzhSNdljwo5FP/P7UGinKwRn3kNWOq30XnI7SZYq+MmUlfCDNPMslh0ewYYsT6uveQ65ai+8RI45Mva8eCVqoGBIMDr9mMmB8YhKu1/7EE4w7YIADBleto1WNycfijd03/LB7nrPBd4UPZ6PsQYU05pe72C1xtMLebSCIfp38VjjxdnfyZ9b9On0TsEJXw5Z0K1AwthG987ntu3RtrdlQYWBtCDBbByUXF1vi1+kT/wMa9LIqlCSdN1Wuz+ajBK/AnS9fTDXRvt6wDVjsRasFrV/ABx9qbOX/xxev9gyoDjttWyRptKQCe6YejQAJQkjuzamx4UALwuqJqNh/024H7rTRs8FrqGZA293TYGV4XZhG5E4rCV+TufYrIakWx51gp6zvQdF7UaF3aoF+7pXvhSFaSwNdXdLcurEYv4d5XXIUIDGSBWuLH0EEB3rVwKCalhhwe4tb/KcHt17+uV6Rhtg0WptWDdVseupngxZTYTt9+3Pw1IandKxL9pX41aEGcNEc+ewdilpYTcSsFqKGDlGnfCCXf2Ycrhy0/ujUlTbR2gD0Rk8jpR+6RM2I7F8I1mcqSVcFVxm1ZJMHttrpmYNyi7e+MkESuIazuIvJsiq6NqDRfwL+Y4O5U05BvaiWnpSGLT0OnioO4uCxP0JTmkiZbYbwdqsS2vtoFnLcqCEYR1F+EBTFwpRlEub81YXTlk3SFXxOlWShKTOdQ6UN3y7lWP7lFptU+q+w1HoRY1zVDHzAVVifaDvp5HXUF5+W9wt/RHBaDj8yaObutPzGhisAmMS9+WEMf30awmC1CXnF7iT98Z5RhWF7c/htr1Vr0t+Uv9N9DBqWGGcOx6T1WQIgju4boJDS/e1UkpqaFvLLF/37spUf6tcAsd4dDTR+KuRVHqg+shECxyHRTD1h1ps5+uoY27rXjW2T89jQojj/s6sYsNquFCBF1DjICt57TCVuMxtz2wkWqkj8Ze2N2/120tTc8k3qBtASdmsAyoUlDHEKQlZcgOgHYRYPSKXfiZ99BdDQpVQoT4qFrGCa2CJzisLaNYqFJ9AvLhd3XFX+6PcicR0fkxHFeT61cGEn5Pe5/AkHuGBHvH8fojpXFYiWLh2olx2un5h3zWXjH4Jx3KPi/5Im3Qg6wTXr5W7kp2StX+zeWL8yMSzOyDWBN+Dpry2N+gK4745D+ALk//xLlPJ6acshixrjeS/lvsCjYLOIAYtDDpUpMBcJyBRJMDHAf1Z8TrZU52yE5YpK/09bBSIheXbuoaWfeb2Moz6zZOYMoyT6R6HjPkiBfW+
x-forefront-antispam-report: CIP:255.255.255.255;CTRY:;LANG:en;SCL:1;SRV:;IPV:NLI;SFV:NSPM;H:CY5PR21MB3588.namprd21.prod.outlook.com;PTR:;CAT:NONE;SFS:(13230040)(366016)(376014)(10070799003)(4022899009)(1800799024)(8096899003)(38070700018);DIR:OUT;SFP:1102;
x-ms-exchange-antispam-messagedata-chunkcount: 1
x-ms-exchange-antispam-messagedata-0: AHVJ3ottZZ/RC+YYY3ebbF7BeDS4jm1BA9cqkUgtCLd7+mHoDmHmFTLWQEtRLKe8ESrCJCe+r5PwmVJ5LAEHf92GxeuOT44bRwvDpoGO3slWgdNvGOeN4CkNWs3lX2JVr5vdhW24KYJSrY/jXSnY8ws5u1gqITlIij4xh6vvLZ6fV3EFKljXsal069NWXLjWAabR6Kr5Wo4+Sm+VIk8HsEIcvif2nJ0dyC5qlqfQoENo82yJ3SkYQu0MHJ2fhPV+wkvU1kDATFQk58tN6VsfTSqMsIW5GW46Yb8Lk6kEMd9WiYWPjnyRjNTRkBIeQ02Ed9omSHknJRmPG0Iw2Oiq3CTe/QVOiEABNuiCZzGpg9PnpiPpWDeRkceiFiU6DpnXWwuni9yCUyqakBU1uTMW5nREo7rPSgC5ZCC3Lg2oXvzIZ0ZqmQqdGoNXrQyem8U9CeZVyTKE8BG0Linng5tFh/V+kkT6NykunkYanzNWcv4xIyfB9NpiHbtQDGz3jzqr29ZumIvesY1QcROExp2sxcVknkk87v/K0hCP4X+uMdAe+ESP2XjAWrKyQopGg1alhBxVH+xySUxgOk2P0VUKd0LZy4oRYshda4RGemBf1WzvMT7nLBYsh0Yu99kLV/7M0mOGKDuBJFp9FYnvW0MNwddsZ7cEFnkaEvFhlsvmr/k+kj7CVVAhOmJ8LRK6cG8NnM7iAT94uR2o2zUe8K3fGOn38buM1IH2lnoEt7/zsE4mKI/NfmUA1nsrus9vNfSrXhPYLrZpsCTmA8ZhytNR26DUH4hJgTQ9DrSUj396FaUT3WDNSesj885N9MpQ+6Ac1E4q5/EQU92GAoQCiBb1yJKR3db7X+yAe0yCZpXr8CCSLmzmLtCwkOtkLyqCFkdslQ2aJ/sWwjCbazurP9zs/9vwMm9g9IvWkUgkGNBTTjT7LNMkJ9SapsyT8KZqkS/NfHjH26aXDuTK1cCMXxcHNLEflBcT769XC0mSoPp2ENLPDMLMunVLRSO8Kq5ymGH2TjPWPmlHALWSg9+tvjmkOTBgZ7Af7PrpfIaKlESzEvCpMd2QEkY8rgCNfCErYXqZOs/LwX/wgUbDhyHvHBBFr5rTzCabpOxvZE7w7dDW6c4/DeKeMnLDenlBAkHQOINx1Pkc+z+PoCg9FTPaik4DtWXNgJQN0CLeCuaKmbIL3mwDalNjrM111CVVYuLYTDB6PYT9BR0F1AH1QjAIeTZbsNfFzHbPO9y0OwrBrnNS4O9XOlCmHPNb79pXDTEvjah4oa13pShM9SP5l0CksEGuSUT7pgrn+3Kk6tSW2G0c2o0AjVSQCdtoQc/Va1uK8hDONL+qXprMJhmp2D0TfqIkptpAUrodz8e82kc55CnTS2tr3vS9nBF8ETFv19YXXe1OW4fMjMZrhdda5oGCZJb4YzPpcBhke6mlBtbihr6EMyWcxkrNvcHk8eonkQS8j9axjvHaTNlYSeLEvhvOYurJ5Cz4EFj7CcwHp4Hw41KcyUY+QjnZFbt20gYqz315A9QsnjNd5ICfCKKwn6FqAnpAMJ/uGqivJKGbj9mUJV69DfrSsSqDL4Yrxy8tKbX1PZ31KHaU3+cKgil0eIA6z/F3+zUF96LfUKH3IrMmrSnrggJMKiJMYzvEEGoERlw9jV7l
Content-Type: multipart/alternative; boundary="_000_CY5PR21MB3588469EBF6C7C759E0098108B582CY5PR21MB3588namp_"
MIME-Version: 1.0
X-OriginatorOrg: microsoft.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: CY5PR21MB3588.namprd21.prod.outlook.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 2443e52b-346c-4fcf-1eda-08dd0286a753
X-MS-Exchange-CrossTenant-originalarrivaltime: 11 Nov 2024 19:25:51.2172 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 72f988bf-86f1-41af-91ab-2d7cd011db47
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: 5SxSBE155NUq0Dm9PljByfrZ2fXW8A3Ql8lhokf0gkl5npEZKHUdoSP1oaEwZuYKzHIGydpAUm71ZXU/52jXEQ==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: CY5PR21MB3519
Message-ID-Hash: WVGQSPQFVC5QNQZO6EN7HVLLK3LTT46L
X-Message-ID-Hash: WVGQSPQFVC5QNQZO6EN7HVLLK3LTT46L
X-MailFrom: Esha.Ghosh@microsoft.com
X-Mailman-Rule-Misses: dmarc-mitigation; no-senders; approved; emergency; loop; banned-address; member-moderation; nonmember-moderation; administrivia; implicit-dest; max-recipients; max-size; news-moderation; no-subject; digests; suspicious-header
CC: "keytrans@ietf.org" <keytrans@ietf.org>
X-Mailman-Version: 3.3.9rc6
Precedence: list
Subject: [Keytrans] Re: [EXTERNAL] Re: New Version Notification for draft-keytrans-mcmillion-protocol-01.txt
List-Id: Key Transparency <keytrans.ietf.org>
Archived-At: <https://mailarchive.ietf.org/arch/msg/keytrans/YfpQ3hgWq7Du34grF5W9chEhg1c>
List-Archive: <https://mailarchive.ietf.org/arch/browse/keytrans>
List-Help: <mailto:keytrans-request@ietf.org?subject=help>
List-Owner: <mailto:keytrans-owner@ietf.org>
List-Post: <mailto:keytrans@ietf.org>
List-Subscribe: <mailto:keytrans-join@ietf.org>
List-Unsubscribe: <mailto:keytrans-leave@ietf.org>

Thanks, Brendan! Please see my response inline.

________________________________
From: Brendan McMillion <brendanmcmillion@gmail.com>
Sent: Monday, November 11, 2024 10:37 AM
To: Esha Ghosh (SHE/HER) <Esha.Ghosh@microsoft.com>
Cc: keytrans@ietf.org <keytrans@ietf.org>
Subject: Re: [EXTERNAL] [Keytrans] Re: New Version Notification for draft-keytrans-mcmillion-protocol-01.txt

Hi Esha, thank you for writing this up! Responses inline,

On Wed, Oct 30, 2024 at 10:31 AM Esha Ghosh (SHE/HER) <Esha.Ghosh@microsoft.com<mailto:Esha.Ghosh@microsoft.com>> wrote:
Thanks a lot Brendan and Felix for working on the protocol draft! I am reading through the draft and I have a couple of questions/comments.


  1.  Section 8.3.2. Proofs for Third-Party Auditing:
     *   The client Search and Lookup protocols don’t appear to be specified in this section. Can they be added in?
     *   I think one major advantage that the third party auditing mode provides over client monitoring mode, is that, the client devices do not need to maintain persistent state between verifications for the security of the system to hold. By client state, I mean the state that the client devices need to store for eventual detection of malicious behavior (such as version numbers for all your contact's keys). Note that, this is different from the human user remembering roughly when they may have updated their own keys in order to detect fake updates. From reading this section, I could not follow if the Search and Lookup algorithms envisioned in this mode operates without requiring persistent client state. Note that the current key transparency deployments (WhatsApp, protonKT) are in this mode and does not require persistent client state for verification. It would be great if the draft support such Search and Lookup algorithms too.


Yes, the intention is to add both of these in the future, potentially with more working group discussion. There's a decent amount of other content missing from the document right now too, as adoption is only the start of the writing process.

That sound good!


  1.  Changing the Tree structure:
     *
In the talk Brendan mentioned moving to a different tree structure which will require rebalancing operation at each update, while keeping the VRF at the leaf labels for privacy. Given that having a VRF at the leaves already makes the current Prefix Trees probabilistically balanced, is the only advantage of picking a different tree over a Prefix Tree is when there is no privacy requirement?
     *
I also wanted to note a difference between Left-Balanced Red Black Tree (LLRBT) and Prefix Tree (PT). PT's are history independent data structure whereas LLRBTs are not. This means, the shape of the tree  and the root are independent of the sequence in which the labels are inserted in PT, but it's not in LLRBTs. I do not think lack of history independence causes any privacy issues, but it can help with some storage optimizations.

The purpose of using a self-balancing tree would be to support use-cases where there is no VRF. Many use-cases don't need a VRF (and in fact, strongly oppose having a VRF) because the content of the log isn't as privacy-sensitive as e2ee messaging. The things I have in mind here are certificate transparency, binary transparency, etc.

I see. Are you proposing to make the draft more general? Can the use cases be explicitly added in the draft then?


  1.  Citations: The draft currently only cites [Merkle^2] for the combined tree approach and is missing a few important citations. It would be great if those can be included.
     *   The idea of using a VRF on the username was first introduced in CONIKS, which the current draft is using.
     *   The idea of using VRF on username||version number to get privacy was introduces in SEEMless, which the current draft is using.
     *   The current Prefix Tree construction in the current draft is identical to the Prefix Tree in OPTIKS.

I don't think RFCs are generally required to reference sources as thoroughly as papers, but I'm happy to add them if you think they're useful background.

Yes, it would be great if you could please add them.

Thanks,
Esha


________________________________
From: Brendan McMillion <brendanmcmillion@gmail.com<mailto:brendanmcmillion@gmail.com>>
Sent: Sunday, October 13, 2024 8:55 PM
To: keytrans@ietf.org<mailto:keytrans@ietf.org> <keytrans@ietf.org<mailto:keytrans@ietf.org>>
Subject: [EXTERNAL] [Keytrans] Re: New Version Notification for draft-keytrans-mcmillion-protocol-01.txt

Hello keytrans@

Felix and I would like to share a new version of the protocol draft
we've been writing in advance of the interim meeting on Oct 22. To
summarize the main changes:

- The term "search key" was changed to "label" throughout the entire
document, to address persistent confusion between "key" as in "search
key" and "key" as in "cryptographic key".
- Support was added for "abridged" proofs when there's a third-party
auditor/manager. These proofs skip some steps that are unnecessary
with third-party auditing to save space.
- The commitment to each change is now stored in a leaf of the prefix
tree, instead of a leaf of the log tree. This was done to allow
"pre-loading", where the log's first entry bulk imports all of a
previous log's contents. Although as a side effect, it allows bulk
changes in any epoch.

We hope to discuss adoption at the meeting, so please let us know any
thoughts. Thanks!


On Sun, Oct 13, 2024 at 8:16 PM <internet-drafts@ietf.org<mailto:internet-drafts@ietf.org>> wrote:
>
> A new version of Internet-Draft draft-keytrans-mcmillion-protocol-01.txt has
> been successfully submitted by Brendan McMillion and posted to the
> IETF repository.
>
> Name:     draft-keytrans-mcmillion-protocol
> Revision: 01
> Title:    Key Transparency Protocol
> Date:     2024-10-14
> Group:    Individual Submission
> Pages:    34
> URL:      https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.ietf.org%2Farchive%2Fid%2Fdraft-keytrans-mcmillion-protocol-01.txt&data=05%7C02%7CEsha.Ghosh%40microsoft.com%7Cc8621fd1151f4dd0f60608dcec0416ad%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C638644749512833129%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata=ae%2Bjyk0sPdX9Reaiw6KnqQ%2Bcm8ALVChG0IayVppE6jM%3D&reserved=0<https://www.ietf.org/archive/id/draft-keytrans-mcmillion-protocol-01.txt>
> Status:   https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdatatracker.ietf.org%2Fdoc%2Fdraft-keytrans-mcmillion-protocol%2F&data=05%7C02%7CEsha.Ghosh%40microsoft.com%7Cc8621fd1151f4dd0f60608dcec0416ad%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C638644749512854309%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata=f5ind%2Bq9nTgoOQKTFlneHfhoh5MdNRTkZHZUIhPzTOM%3D&reserved=0<https://datatracker.ietf.org/doc/draft-keytrans-mcmillion-protocol/>
> HTML:     https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.ietf.org%2Farchive%2Fid%2Fdraft-keytrans-mcmillion-protocol-01.html&data=05%7C02%7CEsha.Ghosh%40microsoft.com%7Cc8621fd1151f4dd0f60608dcec0416ad%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C638644749512868960%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata=pTkgqd0MufkwJUm23xmCP%2FMr1gsA7n3Hfqa0rMJPSRA%3D&reserved=0<https://www.ietf.org/archive/id/draft-keytrans-mcmillion-protocol-01.html>
> HTMLized: https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdatatracker.ietf.org%2Fdoc%2Fhtml%2Fdraft-keytrans-mcmillion-protocol&data=05%7C02%7CEsha.Ghosh%40microsoft.com%7Cc8621fd1151f4dd0f60608dcec0416ad%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C638644749512882972%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata=5waEdFkIsf3X1LmNU%2BNDQeETkcZ%2BDYsSzujMB%2BOkHxQ%3D&reserved=0<https://datatracker.ietf.org/doc/html/draft-keytrans-mcmillion-protocol>
> Diff:     https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fauthor-tools.ietf.org%2Fiddiff%3Furl2%3Ddraft-keytrans-mcmillion-protocol-01&data=05%7C02%7CEsha.Ghosh%40microsoft.com%7Cc8621fd1151f4dd0f60608dcec0416ad%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C638644749512897049%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata=kznEBZUrZ7r%2F8gF5Tck4DmYEEi42mrZk380eU1ap2lg%3D&reserved=0<https://author-tools.ietf.org/iddiff?url2=draft-keytrans-mcmillion-protocol-01>
>
> Abstract:
>
>    While there are several established protocols for end-to-end
>    encryption, relatively little attention has been given to securely
>    distributing the end-user public keys for such encryption.  As a
>    result, these protocols are often still vulnerable to eavesdropping
>    by active attackers.  Key Transparency is a protocol for distributing
>    sensitive cryptographic information, such as public keys, in a way
>    that reliably either prevents interference or detects that it
>    occurred in a timely manner.
>
>
>
> The IETF Secretariat
>
>

--
Keytrans mailing list -- keytrans@ietf.org<mailto:keytrans@ietf.org>
To unsubscribe send an email to keytrans-leave@ietf.org<mailto:keytrans-leave@ietf.org>

[Keytrans] Re: New Version Notification for draft… Brendan McMillion
[Keytrans] Re: [EXTERNAL] Re: New Version Notific… Esha Ghosh (SHE/HER)
[Keytrans] Re: [EXTERNAL] Re: New Version Notific… Brendan McMillion
[Keytrans] Re: [EXTERNAL] Re: New Version Notific… Esha Ghosh (SHE/HER)