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

From: David Benjamin <[email-masked]>
Date: Mon, 29 Jul 2019 20:15:44 -0400

Hi all,

I’ve just uploaded a pair of drafts relating to signatures in TLS 1.3.
https://tools.ietf.org/html/draft-davidben-tls13-pkcs1-00
https://tools.ietf.org/html/draft-davidben-tls-batch-signing-00

The first introduces optional legacy codepoints for PKCS#1 v1.5 signatures
with client certificates. This is unfortunate, but I think we should do it.
On the Chrome side, we’ve encountered some headaches with the TLS 1.3 PSS
requirement which are unique to client certificates. The document describes
the motivations in detail.

The second describes a batch signing mechanism for TLS using Merkle trees.
It allows TLS clients and servers to better handle signing load. I think it
could be beneficial for a number of DoS and remote key scenarios.

Thoughts?

David

---

From: David Benjamin <[email-masked]>
Date: Tue, 30 Jul 2019 15:09:01 -0400

Oops. draft-davidben-tls-batch-signing-00 cites
draft-davidben-http2-tls13-00. That should be
draft-davidben-tls13-pkcs1-00. (The XML file took a really long time to be
created, so I manually tried to recreate it based on another file and
forgot to update one of the fields.) I'll fix this in -01.

---

From: Ben Schwartz <[email-masked]>
Date: Tue, 30 Jul 2019 23:54:30 -0400

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?

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.

On Tue, Jul 30, 2019 at 3:09 PM David Benjamin <[email-masked]>
wrote:

> forgot to update one of the fields..) I'll fix this in -01.
>
>> The first introduces optional legacy codepoints for PKCS#1 v1.5
>> signatures with client certificates. This is unfortunate, but I think we
>> should do it. On the Chrome side, we’ve encountered some headaches with the
>> TLS 1.3 PSS requirement which are unique to client certificates. The
>> document describes the motivations in detail.
>>
>> The second describes a batch signing mechanism for TLS using Merkle
>> trees. It allows TLS clients and servers to better handle signing load. I
>> think it could be beneficial for a number of DoS and remote key scenarios.
>>
>> Thoughts?
>>
>> David
>>
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

From: "Martin Thomson" <[email-masked]>
Date: Wed, 31 Jul 2019 13:59:29 +1000

On Wed, Jul 31, 2019, at 13:54, Ben Schwartz wrote:
> 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 

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.

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

---

From: David Benjamin <[email-masked]>
Date: Wed, 31 Jul 2019 00:11:54 -0400

On Tue, Jul 30, 2019 at 11:59 PM Martin Thomson <[email-masked]> wrote:

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

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

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.

David

---

From: Andrey Jivsov <[email-masked]>
Date: Tue, 30 Jul 2019 23:36:23 -0700

Regarding PKCS 1.5 in TLS 1.3, please also see slide 4 for a year 2015
version of the same motivation
https://www.ietf.org/proceedings/94/slides/slides-94-tls-4.pdf .

On 7/29/19 5:15 PM, David Benjamin wrote:
> should do it. On the Chrome side, we’ve encountered some headaches with
> the TLS 1.3 PSS requirement which are unique to client certificates. The
> trees. It allows TLS clients and servers to better handle signing load.
> I think it could be beneficial for a number of DoS and remote key scenarios.
> 
> Thoughts?
> 
> David
>

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 31 Jul 2019 10:35:00 +0300

On Mon, Jul 29, 2019 at 08:15:44PM -0400, David Benjamin wrote:
> Hi all,
> 
> I’ve just uploaded a pair of drafts relating to signatures in TLS 1..3.

Why is the context string same for clients and servers? The base TLS
1.3 signatures use different context strings for client and server.

What is the hash length of SHAKE256 in Ed448_batch? 512 bits (64
octets) required to saturate the collision resistance?

"to a random byte of string of" in section 3.1, should that be
"to a random byte string of"?

-Ilari

---

From: Thom Wiggers <[email-masked]>
Date: Wed, 31 Jul 2019 09:42:09 +0200

Hi David,

I've found some small textual issues (I'm looking at the PDF version):

In section 3.1 in step 1 (on PDF page 4):

"element 2*i+1 to a random byte of string of Hash.length bytes."

This sentence is slightly puzzling. A random bytestring?

Section 4.2, first paragraph, last sentence:

"so batch signing inherits preserves separation"

This sentence contains two verbs.

It looks like an interesting proposition, which could also be interesting
in the context of some of the post-quantum signing algorithms.

Cheers,

Thom

---

From: Ben Schwartz <[email-masked]>
Date: Wed, 31 Jul 2019 08:01:28 -0400

On Wed, Jul 31, 2019 at 12:12 AM David Benjamin <[email-masked]>
wrote:

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

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

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

David

---

From: David Benjamin <[email-masked]>
Date: Wed, 31 Jul 2019 13:17:03 -0400

On Wed, Jul 31, 2019 at 3:35 AM Ilari Liusvaara <[email-masked]>
wrote:

> trees.

I don't think it's necessary here. The existing separation between client
and server in the base TLS 1.3 signatures is preserved here because the
input messages include their respective context strings. And if we do TLS
1.4 with its own context string, that'll get picked up too.

> octets) required to saturate the collision resistance?

Ah, right. Yeah, let's say 512 bits / 64 bytes. I'll incorporate that into
the next version of the draft.

> "to a random byte string of"?

Oops, thanks! Fixed in local copy.

David

---

From: David Benjamin <[email-masked]>
Date: Wed, 31 Jul 2019 13:22:28 -0400

Thanks! I've applied those fixes to my local copy. They fixes will be in
the -01 revision.

> This sentence contains two verbs.

I also apparently never finished that sentence. Oops. :-) In my local copy,
this paragraph now reads:

Signatures made by the same key in different contexts should be separated to
avoid potential cross-protocol attacks. Inputs to the batch signing
algorithm
include any existing context strings, such as TLS 1.3's distinct client and
server labels or new labels that may be allocated by future versions of TLS.
By signing over those labels, batch signing preserves separation between
those
inputs.

> Op di 30 jul. 2019 om 02:16 schreef David Benjamin <[email-masked]
> >:
>
>> Hi all,
>>

---

From: David Benjamin <[email-masked]>
Date: Wed, 31 Jul 2019 13:40:33 -0400

On Wed, Jul 31, 2019 at 8:01 AM Ben Schwartz <[email-masked]> wrote:

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

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

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

---

From: Ben Schwartz <[email-masked]>
Date: Wed, 31 Jul 2019 14:26:41 -0400

On Wed, Jul 31, 2019 at 1:40 PM David Benjamin <[email-masked]>
wrote:

> Added to the intro "A server under load could, for instance,
> preferentially serve batch-capable clients as part of its DoS strategy.".
>
>
>>> 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
>> 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.
>>
>

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.

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