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

[Ben Schwartz <[e-mail]>]

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

> On Wed, Jul 31, 2019 at 8:01 AM Ben Schwartz <[e-mail]> wrote:
>
>>
>>
>> On Wed, Jul 31, 2019 at 12:12 AM David Benjamin <[e-mail]>
>> wrote:
>>
>>> On Tue, Jul 30, 2019 at 11:59 PM Martin Thomson <[e-mail]>
>>> 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.
>