Re: [TLS] Drafts for batch signing and PKCS#1 v1.5

David Benjamin <davidben@chromium.org> Wed, 31 July 2019 17:40 UTC

Return-Path: <davidben@google.com>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 8A6491201ED for <tls@ietfa.amsl.com>; Wed, 31 Jul 2019 10:40:52 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -9.251
X-Spam-Level:
X-Spam-Status: No, score=-9.251 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HEADER_FROM_DIFFERENT_DOMAINS=0.249, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, USER_IN_DEF_SPF_WL=-7.5] autolearn=no autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=chromium.org
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 oR1OJl1DzYJe for <tls@ietfa.amsl.com>; Wed, 31 Jul 2019 10:40:51 -0700 (PDT)
Received: from mail-qt1-x835.google.com (mail-qt1-x835.google.com [IPv6:2607:f8b0:4864:20::835]) (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 DCC3912015C for <tls@ietf.org>; Wed, 31 Jul 2019 10:40:50 -0700 (PDT)
Received: by mail-qt1-x835.google.com with SMTP id y26so67429196qto.4 for <tls@ietf.org>; Wed, 31 Jul 2019 10:40:50 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=chromium.org; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=O4ClpOV1BzjA7cQmTwcjBxKdIrH4di+wYtZNpUMBl8U=; b=QBTbaNnPWvKqaKmvTgD0wVUm016FpNmRHn4AwRdy0F1srKpCrcEF2LAdTnGtFdolhZ 3IBPGfsH43YJzsG0HyKdqk0XgdQ1wdDRQ6s232+n7j+SzExbwe+P8IPpIDoQrWle4pjF qKuQe+aHnvakKK7ZsqgZkhGIu4Sn28BoEBSqM=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=O4ClpOV1BzjA7cQmTwcjBxKdIrH4di+wYtZNpUMBl8U=; b=W67qu2+9xNLjk1X65jfR2WVxD1agGU2lVeUddDY2aCv+wUou+lhocmHZt5f2ZKPYu/ Nwx0bS83FYHPBpJT/gF1irw1GwDr0OloHWRfUccXAWN0N+juCTrS5sRn/GpTrkZ8gK5Q e2ibxyeqx6L1vIqDwKWVMU6L8ZakXa0gfAMnwDopd2x/B+Gs/wbcqrAwPNZwczsIapSA ZM/pCP9eCKgb77Wn1+qBMWdylDgVcGyX5CFQax8cIhSFJAVg0Ga85ApXMxDlRPAiOHOQ OxHf1VBGTPXx1R309Y3k0cJuO+ugQEtHb1K6taug3u5MSHejhJO9azyo0297dTCmEAv9 Q7XQ==
X-Gm-Message-State: APjAAAXRZPg73t1zfG5JL9SGUN16xMj3j29hWXvn6nA363eThEMobaZG WJuRvttsGFr5MVOsTqQGsCOFeeSex/yBjM9Qn0lf
X-Google-Smtp-Source: APXvYqxq6ndVK+07F/i+oEMQXVRoJi7kWWND0tN4LA/u545DDNqegcnjdtlE6ETPJG1d7Qi0Mwh3p46LQwPBjt/ajXs=
X-Received: by 2002:a0c:b786:: with SMTP id l6mr89168339qve.148.1564594849670; Wed, 31 Jul 2019 10:40:49 -0700 (PDT)
MIME-Version: 1.0
References: <CAF8qwaDxRhGXc522Rf4C-8OcGM4Mm08Xca4KNNpHcT=4Va89aA@mail.gmail.com> <CAF8qwaD=5B9AXkGziwHZ-=LGH-n6fW0KQ9cQfZ2DWhpjDujhEQ@mail.gmail.com> <CAHbrMsCBvZz7j5uH-gKfDrxc4ub=btZh7RyxNZmaADXZEEFJ+A@mail.gmail.com> <19909dab-34bf-442e-9e67-9aef459d472c@www.fastmail.com> <CAF8qwaA1ckZEQmEgcevHVSPVPLfUb-4iVvOb=J9kd=EL=Ckvqw@mail.gmail.com> <CAHbrMsAV0gOSxVKTozO3D813gpHpaOSJWG2vJJuS9VXdKL9ysQ@mail.gmail.com>
In-Reply-To: <CAHbrMsAV0gOSxVKTozO3D813gpHpaOSJWG2vJJuS9VXdKL9ysQ@mail.gmail.com>
From: David Benjamin <davidben@chromium.org>
Date: Wed, 31 Jul 2019 13:40:33 -0400
Message-ID: <CAF8qwaC7rocngd0+VRm9nziwYQkMSDn0zmVS6Dvzb+Amo53tDw@mail.gmail.com>
To: Ben Schwartz <bemasc@google.com>
Cc: Martin Thomson <mt@lowentropy.net>, "<tls@ietf.org>" <tls@ietf.org>
Content-Type: multipart/alternative; boundary="0000000000003bab79058efda073"
Archived-At: <https://mailarchive.ietf.org/arch/msg/tls/NtxBc9ZuyUC7YfwaxKikf1DzDy8>
Subject: Re: [TLS] Drafts for batch signing and PKCS#1 v1.5
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/tls/>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 31 Jul 2019 17:40:52 -0000

On Wed, Jul 31, 2019 at 8:01 AM Ben Schwartz <bemasc@google.com>; wrote:

>
>
> On Wed, Jul 31, 2019 at 12:12 AM David Benjamin <davidben@chromium.org>;
> wrote:
>
>> On Tue, Jul 30, 2019 at 11:59 PM Martin Thomson <mt@lowentropy.net>;
>> wrote:
>>
>>> On Wed, Jul 31, 2019, at 13:54, Ben Schwartz wrote:
>>> > The batch signing idea is very cool. I'm not entirely sure I
>>> understand
>>> > the intended use case, though. The intro suggests that this motivated
>>> > by DoS defense, but presumably an attacker who controls their own TLS
>>> > client stack could simply omit support for these signature schemes. Do
>>> > you envision a future where servers can safely omit support for all
>>> the
>>> > non-batch signature schemes? Or are you thinking of attackers who
>>> don't
>>> > control the TLS client stack?
>>>
>>> The usual trick when under duress is to attempt to process some
>>> requests, and lowering the cost of handling those requests enables higher
>>> tolerance to attack and better continuity of service.  A server might
>>> choose not to serve clients that don't offer batching if it is stressed.
>>>
>>
>> Yup. The signing cost of a batch-capable client is effectively zero. (I
>> expect it's already common to preferentially serve ECDSA-capable clients
>> when under load.) Also, if many clients implement this, serving load under
>> normal operation goes down, which is also valuable..
>>
>
> OK.  I think it would be good to clarify the motivation in the intro.
> (For me, defending against DDoS attackers who don't control the TLS client
> stack is also a compelling use case.)
>

Added to the intro "A server under load could, for instance, preferentially
serve batch-capable clients as part of its DoS strategy.".


> > Minor question: in the tree diagrams, m2 goes to t04. Is there any
>>> > reason it couldn't go directly to t12? That would seem more natural to
>>> > me.
>>>
>>> The blinding process is explained in Section 4.3.
>>>
>>
>> I think Ben is asking why the tree doesn't put m2 a level higher (like CT
>> does), instead of adding the padding nodes. That would work too. I chose
>> this one because I found it more straightforward, and it doesn't
>> particularly matter. Also it's what Roughtime did and I cribbed the
>> construction from Roughtime. :-)
>>
>
> OK, thanks for the explanation.  My main reason to favor the CT-style tree
> structure is that it avoids load spikes.  In this structure, incrementally
> processing message mk requires k hashes when k is a power of 2, as opposed
> to O(1) hashes for each message in a CT-style tree.
>

I'm not sure I understand the concern. In both constructions, the cost of
processing N messages is O(N) total hashes, one signature, and then O(lg N)
copies of the hash per message. I'm envisioning the signer just queues up
hashed inputs and then builds the tree at signing time. Were you thinking
some other pattern?

Complete trees are nice because they can be stored in a single contiguous
buffer, and the tree construction itself is just a couple of
straightforward loops.


> In principle, the signer could pick any tree strategy as long as it
>> produced valid paths for each message. But I think it's probably better for
>> the draft to be opinionated, rather than risk implementers mess things up.
>>
>
> A SHOULD-strength recommendation for a particular approach seems fine, but
> I think sophisticated implementers might want to use different structures
> depending on their needs.
>

Flexibility is the enemy of security. ECDSA and EdDSA's verification
algorithms will accept manner of nonce generation strategies, but that
doesn't mean all of them are fine. I don't think there are enough valuable
variations in this space to justify the flexibility.