Re: [Cfrg] Adoption of threshold drafts by RG

[Phillip Hallam-Baker <[e-mail]>]

I think this is starting to get into discussion of the drafts rather than
the decision for the WG to move forward on the work. Which I would also
like to see happen. I am indifferent as to whose draft is used as the basis
for the signature part. My goal is to get a scheme I can use.


As far as the use cases go, I am starting to see the basis for the Drijvers
attack. Your use of the term 'concurrency' is a little confusing to me. I
am a protocol guy, not a cryptographer. What is the information that you
are assuming is shared between a set of 'concurrent' signatures?

However I am not convinced that an HSM can perform the attack from the
information made available to it. When implemented as a CPU co-processor,
the HSM will only ever see the R contribution value from the other party
and the message. The HSM never sees the final signature or the other
contributions, nor does it get to choose the message. This is not the case
for a threshold signature service however. That will see the final
signature.

For the CPU co-processor case, offering less than FIPS-140 level security
might well be acceptable. The key concern is preventing leakage of the
co-processor key. The possibility that a malicious co-processor could
perform an active attack on the application key is less of a concern. It is
hard to see how that sort of thing can be easily hidden in the microcode.

>From my point of view, the critical thing for a threshold signature service
is to enable a single request/response pattern to service a single API call
to 'sign'. But I can offload a pre-commitment phase as is being done in
FROST.


To be more specific about my particular use case. Alice (@alice) creates a
Mesh profile which she will initially use with the service example.com and
later with example.net (but only one at a time). Connecting a device to her
Mesh requires the creation of a Mesh Activation record and connection
record for the device. These must be signed under an administrator key
declared in the User profile. Alice may connect multiple administrator
devices to her Mesh. She is also likely to lose one of them at some point.
So the ability to split the threshold signature across the administrator
device and a threshold service is really desirable but neither essential
nor is it currently implemented.

The quorum criteria here is going to be that Alice must use an
administrator device and one of the services. The services must not be able
to collude and create a signature on their own. This is achieved by first
splitting the private key into two parts, giving one of them to the device
and performing a Shamir secret share n=3, t=2 on the other.

If use of threshold signatures is limited to the specific task of device
connection, the service can compute a pre-commitment every time it receives
a device connection request. But it would be nice if this could be made
more general.




On Tue, Sep 29, 2020 at 4:21 PM Chelsea Komlo <[e-mail]> wrote:

> Hi Phillip,
>
>
> Here is a summary of how the Drivers attack [1] can be performed, and the
> implications for schemes that are insecure.
>
>
> Let the threshold be t=2, and assume one signer is malicious. Let the
> number of victim's commitments that the attacker can learn *before*
> selecting their own commitment be k >= 2 (such as by opening many
> simultaneous signing connections).
>
>
> After performing O(k*b*2^{1/lg(k)}) local computations (where b is the
> bitlength of the order of the group), the adversary can compute a valid
> forged signature. They do so by first completing the k signing executions,
> sending the victim k messages to sign of the adversary's choosing, along
> with their own commitments. From the victim's responses, the adversary can
> derive a partial forged signature for the victim over a message that the
> victim has never seen. The adversary then simply provides their own partial
> signature to complete what is a valid forged joint signature.
>
>
> For a scheme defined over a group order of bitlength 256, an adversary
> that is allowed to make up to 3 concurrent signing operations reduces the
> security of the scheme to ~95 bits of security. Allowing up to 7 concurrent
> signing operations reduces the security to 75 bits, etc.
>
>
> With that said, even if you did integrate a FROST-like approach into your
> scheme, after a quick look, there are parts of your design that remain
> insecure. For example, the stateless computation of the final share [2]
> would remain insecure against the Drijvers attack as the final signer is
> not required to commit to their nonce before seeing all other signers'
> commitments.
>
>
> We would however like schemes that are designed for specific use cases to
> build upon FROST as needed. Because of the interest here and as expressed
> previously on this list, I would like to ask the chairs to consider moving
> our draft for FROST [3] forward.
>
>
> Chelsea
>
>
> [1] https://eprint.iacr.org/2018/417.pdf
> [2]
> https://tools.ietf.org/id/draft-hallambaker-threshold-sigs-04.html#section-3.3
> [3] https://www.ietf.org/id/draft-komlo-frost-00.txt
>
>