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

Ben Schwartz <bemasc@google.com> Wed, 31 July 2019 18:26 UTC

Return-Path: <bemasc@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 E55B81206CC for <tls@ietfa.amsl.com>; Wed, 31 Jul 2019 11:26:59 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -17.5
X-Spam-Level:
X-Spam-Status: No, score=-17.5 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_MED=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, ENV_AND_HDR_SPF_MATCH=-0.5, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, USER_IN_DEF_DKIM_WL=-7.5, USER_IN_DEF_SPF_WL=-7.5] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=google.com
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 E-csre-1zWm8 for <tls@ietfa.amsl.com>; Wed, 31 Jul 2019 11:26:57 -0700 (PDT)
Received: from mail-io1-xd34.google.com (mail-io1-xd34.google.com [IPv6:2607:f8b0:4864:20::d34]) (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 395F31206C5 for <tls@ietf.org>; Wed, 31 Jul 2019 11:26:57 -0700 (PDT)
Received: by mail-io1-xd34.google.com with SMTP id k20so138400962ios.10 for <tls@ietf.org>; Wed, 31 Jul 2019 11:26:57 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=Jujx+wAKCMT/a0PmYQputNV36pRgWoCLaC6nXx2HGXM=; b=eQ1zx+HXkdwADxJScJoxG52C11o2FWBCXJw6xyyPkRgXKjfXuDXs5PY36sg+tN5/O6 52czEZavNxSnudlr/S0Ngg2CRuTfJX9KdB5cfpWwoZbnG9QQSjdiYBVYgrxXtqogzCFo hdSh/YYFYmtUanzH6togv3HcBW0P3nXJLyNAmcqF0Xi+pBBAR506rUHnJW3PkpMDXx/v +jLtPBojJB0pskgAOTjlhGBbzBUCBIoZ303NogBtavzsa7cxs1o/eX1QCffp/VRK6iVE dVoZkgzHJ2CMUeAIQICG8pw3ix/k0q0n5T4Obaz9LWRtn3Gv4rSYYiNCXXczENIQfB3v IbwA==
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=Jujx+wAKCMT/a0PmYQputNV36pRgWoCLaC6nXx2HGXM=; b=HItFy2++TYUDtc6Fhw488QyTwHlekyXtjY5vDgMTAsZ3RAjhXHZXpG3H9onIJRIAkx yfjIyd+acittj1MWLUkfBkbgIt8meCp2rl/d3Dx1ReJcuUG1GYzITkxVi2bAOEU8MoiG iuGQmS7dTQ9kpAd107xrcSmTt1Z4JN1Pamls9QdBoMp4IqrMoTeL6fiFOv4Kta0kebE8 kqitZcrykB2Cpwp39tZj9vBTirT+grxRcPeYH2ypaK8ipxv+TnLxviPm5hedqrqjGJ3C G8d/7CWDUG77JIK8LXTW1tYjaGYZG0IDOvk0HIRuJOjB4T6mlf1OHstxoH7gHvcMK3xt ud9A==
X-Gm-Message-State: APjAAAXc5uogCm9TxtpVIQA9K3mnQZ5Xix2yqK/ap91w//ox7VIZXY/w qFtFy5XjZ0QuGa2KeJArrG4GNs3C+30OsjUMIHVAXw==
X-Google-Smtp-Source: APXvYqxt5b6GsbE+Z3NkJU1l5Ra89Y1BHYyQGvd3IV508kTPzoifGAKsixm3z8MhMqemQCGYrDQQ3NMBA/aySGyB6AE=
X-Received: by 2002:a02:cc8e:: with SMTP id s14mr39050391jap.142.1564597614878; Wed, 31 Jul 2019 11:26:54 -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> <CAF8qwaC7rocngd0+VRm9nziwYQkMSDn0zmVS6Dvzb+Amo53tDw@mail.gmail.com>
In-Reply-To: <CAF8qwaC7rocngd0+VRm9nziwYQkMSDn0zmVS6Dvzb+Amo53tDw@mail.gmail.com>
From: Ben Schwartz <bemasc@google.com>
Date: Wed, 31 Jul 2019 14:26:41 -0400
Message-ID: <CAHbrMsDfKYy-H=AQmYohUwcsSpgL1vZ7d1XQoNXJtbZw8eaU+g@mail.gmail.com>
To: David Benjamin <davidben@chromium.org>
Cc: Martin Thomson <mt@lowentropy.net>, "<tls@ietf.org>" <tls@ietf.org>
Content-Type: multipart/signed; protocol="application/pkcs7-signature"; micalg=sha-256; boundary="00000000000029204f058efe4587"
Archived-At: <https://mailarchive.ietf.org/arch/msg/tls/dtFOQnyS12NOvmmKiuJASwxcAbU>
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 18:27:04 -0000

On Wed, Jul 31, 2019 at 1:40 PM David Benjamin <davidben@chromium.org>;
wrote:

> 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?
>

Yes, I was thinking about a signer who builds the tree incrementally while
waiting for the "RSA unit" to signal that it is ready.  Building the tree
at signing time prevents hashes and signatures from running in parallel.

That said, I think your construction is actually fine for this purpose.  I
misinterpreted your diagram to indicate that rows >=1 should have full
power-of-2 size.  The text makes clear that this is not the intention.

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.
>