Is this the first ever practically-deployed use of a threshold scheme?

[D. K. Smetters]

Jonathan Katz wrote:
> On Sat, 31 Jul 2010, Jakob Schlyter wrote:
> 
>> On 31 jul 2010, at 08.44, Peter Gutmann wrote:
>>
>>> Apparently the DNS root key is protected by what sounds like a 
>>> five-of-seven
>>> threshold scheme, but the description is a bit unclear.  Does anyone 
>>> know
>>> more?
>>
>> The DNS root key is stored in HSMs. The key backups (maintained by 
>> ICANN) are encrypted with a storage master key (SMK), created inside 
>> the HSM and then split among 7 people (aka "Recovery Key Share 
>> Holders"). To recover the SMK in case of all 4 HSMs going bad, 5 of 7 
>> key shares are required. (https://www.iana.org/dnssec/icann-dps.txt 
>> section 5.2.4)
>>
>> According to the FIPS 140-2 Security Policy of the HSM, an AEP Keyper, 
>> the M-of-N key split is done using a La Grange interpolating Polynomial.
>>
>>
>> I'd be happy to answer any additional questions,
>>
>>     jakob (part of the team who designed and implemented this)
> 
> This is "just" Shamir secret sharing, not "real" threshold cryptography. 
> (In a threshold cryptosystem, the shares would be used in a protocol to 
> perform the desired cryptographic operation [e.g., signing] without ever 
> reconstructing the real secret.) Has real threshold cryptography never 
> been used anywhere?

CertCo (RIP) built a Certification Authority software product that used 
"real" threshold cryptography. Key shares for a k of n scheme (where k 
and n were chosen at key split time) were stored in hardware crypto 
tokens, and signatures were generated by having k tokens generate 
partial signatures and then combining them into a "regular" RSA sig. The 
system was deployed as the SET root CA for some time; we did try to sell 
it as a regular software product, but (corporate) political issues made 
that somewhat challenging. I honestly don't remember whether it was 
deployed by anyone else for anything other than SET, but it may be that 
one of the (many) other CertCo alumni on this list might.

The original CertCo CA software used pretty simple threshold crypto (I 
can provide paper refs for the particular schemes we used if anyone 
really wants them), but by the time I left we had worked on verifiable 
schemes (where you can verify the partial sigs independently), 
proactivization (re-sharing to change k or n, or remove bad players), 
and so on. The deployed system did not implement distributed key 
generation, which had just appeared in the literature at that time -- 
the key was generated on one token, and then split; the key generation 
token was then intended to be destroyed.

Although the system was designed to be used in a globally distributed 
fashion, with automated systems for sending work (things to sign) to 
sites holding key shares (where each signing request was signed by an RA 
to authorize it), and then collecting and recombining the partial sigs, 
it turned out to be way too hard to use that way. I don't know if it was 
ever deployed in a truly geographically distributed configuration, 
rather than having all the shares (except for backups) kept at one site. 
(And as a result, I started working on usability of security :-).

Shortly after the last CertCo CA, Victor Shoup published a new threshold 
RSA scheme that made them much simpler to incorporate into deployable 
systems; building a system that uses "real" threshold crypto would be 
pretty easy these days if one wanted to. If nothing else, it's a great 
example for cryptographers of how small changes in the algebraic 
formulation of something can have large impact on how easy it is to 
build into systems.

--Diana Smetters

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com