[saag] Side channel resistance, threshold signatures, etc.

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

As promised, I wrote up the use of threshold schemes for key agreement, key
generation and signature:

https://www.ietf.org/id/draft-hallambaker-threshold-00.html
https://www.ietf.org/id/draft-hallambaker-threshold-sigs-00.html


The signature scheme proposed is a threshold scheme, not an aggregate
signature. It is not possible to use the scheme as specified to sign
documents using arbitrary sets of pre-existing keys. As with 'true' proxy
re-encryption, this is a cryptographic capability that imposes significant
demands (i.e. requires pairing) but does not provide compelling additional
benefit.

I think it is clear that notwithstanding the work on new public key systems
that are threshold friendly (e.g. BLS), there is great value in extracting
the maximum capability from our existing algorithms.

The same algorithms will of course apply to other curves besides the CFRG
ones. But if we are going to move forward with ECC, best to put all the
wood behind the same arrow.

One other point is that the first paper could be used to address the NIST
objection to the deterministic RFC8032 signature scheme (which I endorse).
It is my understanding that the Kocher side channel blinding patent expired
last year and so it is now possible for all applications, including open
source, to use key splitting against a random number and combination of the
results to effect a degree of side channel resistance. It is my personal
view that this should be employed for Montgomery curves as well because I
do not believe the ladder is as 'constant' as people imagine.

What I am trying to work towards here is the specification of a common
cryptographic core that could be implemented at the hardware level on mid
range CPUs and above to defeat the use of the SPECTRE class hardware
attacks and to permit binding of cryptographic material to a specific host
without exposing the users to compromise during manufacture (or
manufacturers of being accused of the compromise).

The basic idea is that the CPU has a single private key 'x' embedded during
manufacture such that it cannot be extracted. Applications can get the
public key X which is fixed for all the users on the machine. The built in
key may be used in two different ways. In either case, the application
generates its own key pair {Y, y}. It may then decide to perform all
private key operations itself and combine the results or pass y to the
coprocessor to be added to the result.

The two operations the CPU module will perform would be limited to:

1) given a point P, return x.P
2) given a scalar k, generate a random value 0 < r < L and return {r.P, r +
x.k}

The smaller the requirements, the more likely it is we can get what we
need. So it might well be that a hardware module only supported the Edwards
or the Montgomery curves and applications were required to use the
isomorphisms to map from one to the other.


Two decades after I first attended my first (and last) 'Trusted Computing'
WG meeting, deployment of the original TPM model is no closer. I suspect
that a great deal of the opposition to TPMs was cleverly orchestrated to
discourage proliferation of effective strong cryptography (the $250
million/yr on BULLRUN obviously went somewhere). But regardless, the
achilles heel of that scheme was and is the need for a physical token (SIM
card / TPM) to effect device portability.

The threshold models I have developed allow those restrictions to be
avoided. Alice can deploy keys to all her devices that allow them to
encrypt, authenticate and sign and retain the ability to recover data from
a broken machine, port data between her machines etc. without the need for
the crypto processor to be on a pluggable daughter board.

The only real limitations of this model come from conflicting requirements.
I cannot design a key recovery system that only works when the 'good guys'
are using it.