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

[David Benjamin <[e-mail]>]

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?

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.