Subject: [DNSOP] DNSSEC threshold signatures idea

From: Mukund Sivaraman <[email-masked]>
Date: Thu, 6 Sep 2018 21:42:52 +0530

During a coversation about the Yeti project, Davey Song brought up an
idea about using threshold signatures within DNSSEC. While he talked
about it primarily for the root zone within the context of having
multiple signers for it, I'm curious to know what operators think about
the concept for other zones, and if there's any interest in having a
working implementation.

DNSKEY RRs contain public keys. Corresponding secret keys are managed by
signing entities in various ways:

* It may be for a low-risk zone and a human may leave the key on the
  nameserver itself

* The key may be held by some number of trustworthy staff offline and
  when signing is required, one of them signs the zone and returns the
  signed zone

* It may be managed by an automated system under the control of one or
  more people

* It may be held in a locked computer system which may be accessed when
  multiple trustworthy "keepers" are present

* There may be schemes like this:
  https://www.icann.org/news/blog/the-problem-with-the-seven-keys

In many of these cases, it may be possible for one rogue person to sign
records against the wish of the rest of the trustworthy group appointed
by a zone owner. Even though it's unlikely, it's possible to do so
because the control over secret key material may be available to one
person, even if it is wrapped in multiple layers.

The concept of threshold crypto is that there is a public DNSKEY, for
which the secret key is not available in a single form where it can be
reconstructed. Instead, N members of a group have some key material each
respectively, and any M (< N) members of the group may work together to
prepare RRSIGs by using their respective key materials individually, and
collaborating to generate the signatures.

It may be possible for such a scheme to be compatible with existing
DNSSEC algorithms. Is there any operator interest in this?

		Mukund

---

From: Hugo Salgado-Hernández <[email-masked]>
Date: Thu, 6 Sep 2018 14:34:12 -0300

Hi Mukund.
I talked about this to Davey in Montreal. There's an implementation
in github[1] and presentations in OARC[2] and ICANN[3].

I'm not sure if its being used right now in a live zone, but certainly
in labs and testing. There's been some interests with academic
institutions, but don't think they're ready yet.

We've been trying to focus this technology as a "poor-man" HSM, as
having similar security features without buying an expensive HW.
But I think the root and similar high-value zones will benefit for
having an split of the private key AND the fact of not needing a
"root key ceremony" to sign, because you can sign remotely with
each piece of the private key, and transmit the "signature pieces"
to a central place.

Hugo

[1] https://github.com/niclabs/docker/tree/master/tchsm
[2] <https://indico.dns-oarc.net/getFile.py/access?contribId=22&sessionId=3&resId=1&materialId=slides&confId=20>
[3] <http://buenosaires48.icann.org/en/schedule/wed-dnssec/presentation-dnssec-cryptographic-20nov13-en>

On 21:42 06/09, Mukund Sivaraman wrote:
> _______________________________________________
> DNSOP mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/dnsop
>

---

From: Mukund Sivaraman <[email-masked]>
Date: Thu, 6 Sep 2018 23:19:26 +0530

> in github[1] and presentations in OARC[2] and ICANN[3].

Aha so you're the original source :)

> [3] <http://buenosaires48.icann.org/en/schedule/wed-dnssec/presentation-dnssec-cryptographic-20nov13-en>

So this's implemented as a PKCS 11 provider.. interesting. In my mind I
was thinking along the lines of updates to dnssec-keygen +
dnssec-signzone + intermediate RRSIG representation using new RR type +
zone transfers to share intermediate effects.

		Mukund

---

From: Steve Crocker <[email-masked]>
Date: Thu, 6 Sep 2018 14:14:44 -0400

I've been thinking about a version of this problem for several years.
Attached are a short paper and presentation on the topic of a tamperproof
root zone update system.  The ideas are also applicable to other levels in
the DNS tree.

In parallel, there is work on open source hardware crypto that can easily
be extended to include this functionality.

There are some important governance and process details alluded to but not
fleshed out in the paper.  Happy to discuss with anyone interested.

Steve

On Thu, Sep 6, 2018 at 1:34 PM, Hugo Salgado-Hernández <[email-masked]>
wrote:

> [2] <https://indico.dns-oarc.net/getFile.py/access?contribId=
> 22&sessionId=3&resId=1&materialId=slides&confId=20>
> [3] <http://buenosaires48.icann.org/en/schedule/wed-dnssec/
> presentation-dnssec-cryptographic-20nov13-en>
>
>

---

From: Hugo Salgado-Hernández <[email-masked]>
Date: Thu, 6 Sep 2018 16:02:57 -0300

> zone transfers to share intermediate effects.

In our implementation you'll need a central "orchestrator" who
creates the first key and split the private pieces to each
signing node. This same orchestrator later send signature
requests to each node, collect the signature pieces and
defines the "consensus" of M/N. Finally, there's an PKCS11
interface between this orchestrator and the zone signing
policy machinery (OpenDNSSEC in our setup).

Hugo

---

From: Steve Crocker <[email-masked]>
Date: Thu, 6 Sep 2018 15:08:28 -0400

How do you prevent compromise of the central service?

Steve

---

From: Hugo Salgado-Hernández <[email-masked]>
Date: Thu, 6 Sep 2018 16:22:09 -0300

> How do you prevent compromise of the central service?

For the initial setup a physical ceremony is necessary,
to check there's no extra subkeys and for secure transmision
of them. But afterwards there's no need. Each node can check
the final signature validates with the public key (just like
a normal signature), and the plain data should be public
(DNSKEY rrset).

In this same first ceremony you can also share simmetric
keys for the secure transmission of data and signature
pieces.

The system is fault-tolerant as a subset of nodes can fail
and the signing process can be completed, and you can
detect faked sub-signatures.

Hugo

---

From: Steve Crocker <[email-masked]>
Date: Thu, 6 Sep 2018 15:25:14 -0400

Let me flag a key point.  You said this scheme will *detect* faked
signatures.  If you want to *prevent* faked signatures, you need additional
structure.

Steve

---

From: Michael StJohns <[email-masked]>
Date: Thu, 6 Sep 2018 15:52:36 -0400

> How do you prevent compromise of the central service?

The "Dealer" is only doing confidential processing during the key 
generation phase.   Once that's done, you can do a wipe.   The 
subsequent signature operations are all distributed.  The combine 
operation is public.

Let's pause here for a moment though.   Shoup came up with a threshold 
system that worked this way - but only for RSA signatures.   I actually 
built (and still have) the tools to do a N of K distributed DNSSEC 
signing process using his scheme.

> /**
>  * A key Dealer for an RSA-based (k,l) Threshold Signature Scheme<p>
>  * Portions Copyright (c) 2004 Nominum, Inc.<p>
>  * Substantially modified from Steve Weis' original to enable
>  * real (e.g. compatible with the JCA/JCE) RSA signatures.
>  *
>  * @author Steve Weis <[email-masked]>
>  * @author Mike StJohns
>  * @see "Practical Threshold Signatures,
>  * Victor Shoup ([email-masked]), IBM Research Paper RZ3121, 4/30/99"
>  */

  Specifically the scheme generates K shares of a private key and 
distributes them.  The share holders generate partial signatures across 
the same identical data and publish those partial signatures.   
Publicly, anyone who wants can take those N of those partial signatures 
and form a normal RSA signature. (which can be verified using normal RSA 
signature/verification primitives).

AFAICT, there isn't an ECDSA system that has the same characteristics.

Lately, I've been thinking about a non-math based threshold system.

1. Assume you can program a policy wrapper around key material on an HSM 
(e.g. javacard scheme for example) - then
    a) Have K people generate key pairs and send the public keys of the 
key pairs to the HSM owner.  These represent the K keys of key share 
holders set H.
    b) generate a key pair providing H as an input and with the 
following policy
            the private key will sign data IF and ONLY IF it first sees 
N different valid signatures over the same data by the members of set H.
2) Signing manager generates and publishes the "to be signed" data
3) After public concurrence, the members of set H sign the data and 
publish their signatures.
4) After verification of sufficient valid signatures by the H keys, the 
HSM manager presents those signatures (and their related public keys as 
in index) to the HSM and retrieves and publishes the final signatre.

This is trivial to implement on a javacard and there are a few HSM 
vendors that are now providing support for scripting key policies that 
are much richer than PKCS11 can express.

PS - the RSA scheme is pretty neat in that it's invertible.  E.g. I can 
encrypt something using the public key, and then require N share holders 
to decrypt it.

Mike

>
> Steve
>
>
> On Thu, Sep 6, 2018 at 3:02 PM, Hugo Salgado-Hernández 
> <[email-masked] <mailto:[email-masked]>> wrote:
>
>     <https://github.com/niclabs/docker/tree/master/tchsm>
>     > > [2]
>     <https://indico.dns-oarc.net/getFile.py/access?contribId=22&sessionId=3&resId=1&materialId=slides&confId=20
>     <https://indico.dns-oarc.net/getFile.py/access?contribId=22&sessionId=3&resId=1&materialId=slides&confId=20>>
>     > > [3]
>     <http://buenosaires48.icann.org/en/schedule/wed-dnssec/presentation-dnssec-cryptographic-20nov13-en
>     <http://buenosaires48.icann.org/en/schedule/wed-dnssec/presentation-dnssec-cryptographic-20nov13-en>>
>     >
>     [email-masked] <mailto:[email-masked]>
>     <https://www.ietf.org/mailman/listinfo/dnsop>
>
>
>
>

---

From: Hugo Salgado-Hernández <[email-masked]>
Date: Thu, 6 Sep 2018 16:52:56 -0300

> signatures.  If you want to *prevent* faked signatures, you need additional

The orchestrator can detect faked signature pieces when is
merging them, before going live. So for this definition of
"prevent" should be sufficient. If you're referring to
prevent the orchestrator with faking the resulting signature,
I think we're gonna fail preventing but only reacting after
detecting it alive.

Hugo

---

From: Steve Crocker <[email-masked]>
Date: Thu, 6 Sep 2018 15:54:30 -0400

My focus is on preventing the orchestrator from faking the signatures.

Steve

Sent from my iPhone

> On Sep 6, 2018, at 3:52 PM, Hugo Salgado-Hernández <[email-masked]> wrote:
>

---

From: Davey Song(宋林健) <[email-masked]>
Date: Fri, 7 Sep 2018 12:51:06 +0800

Hi Mukund，

Thank you for proposing here for comments and discussion. I would like to
share more background on this if people are interested. 

Actually I was inspired by several sources. One is the Multisignature
(https://en.bitcoin.it/wiki/Multisignature ) concept from Bitcoin which help
to reduce the risk of wallet keys be stolen.

One is from Yeti work we are doing where Hugo gave me some ideas. In Yeti
testbed, we try to implement the concept of "Share Zone Control" proposed by
PVM in ICANN ITI report. We firstly constructed the root system with 3
signers (3ZSK and 1 KSK) . We would like improve this system with more
fault-tolerant property and less dependency on a central entity. There is a
post I put in Yeti blog (https://goo.gl/7i4NxB ). 

When I survey on this, I learnt some concept of threshold signature
algorithms in the crypto academic field, like BLS , Boldyreva and PBC
(Pairing based crypto). But I'm not a crypto guys . I'm just looking for
mature and reliable crypto tool to fit my case, then we can test and try it
in existing testbed. Maybe people on this mailing list can help.

Best regares,
Davey

> -----邮件原件-----
> 发件人: DNSOP [mailto:[email-masked]] 代表 Mukund Sivaraman
> 发送时间: 2018年9月7日 0:13
> 收件人: [email-masked]; [email-masked]
> 主题: [DNSOP] DNSSEC threshold signatures idea
> 
> During a coversation about the Yeti project, Davey Song brought up an idea
> about using threshold signatures within DNSSEC. While he talked about it
> primarily for the root zone within the context of having multiple signers
for it,
> I'm curious to know what operators think about the concept for other
zones,
> and if there's any interest in having a working implementation.
> 
records
> against the wish of the rest of the trustworthy group appointed by a zone
> owner. Even though it's unlikely, it's possible to do so because the
control over
> secret key material may be available to one person, even if it is wrapped
in
> multiple layers.
which the
> secret key is not available in a single form where it can be
reconstructed.
> Instead, N members of a group have some key material each respectively,
and
> any M (< N) members of the group may work together to prepare RRSIGs by
> using their respective key materials individually, and collaborating to
generate
> the signatures.
> 
> It may be possible for such a scheme to be compatible with existing DNSSEC
> algorithms. Is there any operator interest in this?
> 
> 		Mukund
>

---

From: Davey Song(宋林健) <[email-masked]>
Date: Fri, 7 Sep 2018 15:23:34 +0800

I also ask the same question and look for solutions. I do find a statement from a paper (The Honey Badger of BFT Protocols@ CCS 2016) that " if an trusted party is unavailable, then a distributed key generation protocol could be used instead (c.f., Boldyreva [11])."

[11] A. Boldyreva. Threshold signatures, multisignatures and blind
signatures based on the gap-diffie-hellman-group signature
scheme. In Public key cryptographyâA˘TPKC 2003 ˇ , pages
31–46. Springer, 2002

I have no experience on Boldyreva protocol though, but it seems possible without a central service if all participants follow a certain common rule or algorithm.

Davey
> -----邮件原件-----
> 发件人: DNSOP [mailto:[email-masked]] 代表 Hugo Salgado-Herná
> ndez
> 发送时间: 2018年9月7日 3:22
> 收件人: Steve Crocker
> 抄送: dnsop; Mukund Sivaraman; [email-masked]
> 主题: Re: [DNSOP] DNSSEC threshold signatures idea
> 
> For the initial setup a physical ceremony is necessary, to check there's no extra
> subkeys and for secure transmision of them. But afterwards there's no need.
> Each node can check the final signature validates with the public key (just like a
> normal signature), and the plain data should be public (DNSKEY rrset).
> 
> In this same first ceremony you can also share simmetric keys for the secure
> transmission of data and signature pieces.
> 
> The system is fault-tolerant as a subset of nodes can fail and the signing
> process can be completed, and you can detect faked sub-signatures.
> 
> Hugo
> 
> > Steve
> >
> >
> > <[email-masked]>
> > > > > I talked about this to Davey in Montreal. There's an
> > > > > implementation in github[1] and presentations in OARC[2] and
> ICANN[3].
> > > >
> > > > > I'm not sure if its being used right now in a live zone, but
> > > > > certainly in labs and testing. There's been some interests with
> > > > > academic institutions, but don't think they're ready yet.
> > > > >
> > > > > We've been trying to focus this technology as a "poor-man" HSM,
> > > > > as having similar security features without buying an expensive HW.
> > > > > But I think the root and similar high-value zones will benefit
> > > > > for having an split of the private key AND the fact of not
> > > > > needing a "root key ceremony" to sign, because you can sign
> > > > > remotely with each piece of the private key, and transmit the "signature
> pieces"
> > > > > to a central place.
> > > > >
> > > > > Hugo
> > > > >
> > > > So this's implemented as a PKCS 11 provider.. interesting. In my
> > > > mind I was thinking along the lines of updates to dnssec-keygen +
> > > > dnssec-signzone + intermediate RRSIG representation using new RR
> > > > type + zone transfers to share intermediate effects.
> > >
> > > creates the first key and split the private pieces to each signing
> > > node. This same orchestrator later send signature requests to each
> > > node, collect the signature pieces and defines the "consensus" of
> > > M/N. Finally, there's an PKCS11 interface between this orchestrator
> > > and the zone signing policy machinery (OpenDNSSEC in our setup).
> > >
> > > Hugo
> > >
> > >

---

From: william manning <[email-masked]>
Date: Fri, 7 Sep 2018 02:45:35 -0700

Great stuff Steve.  John Gilmore and I talked about the use of byzantine
quorum systems for key management at ISOC in 1998. And Olaf Kolkman, Johan
Ihren and I proposed such a system in 2005 as an alternative to what became
RFC 5011.  I built a DNS system that used these ideas for DNS key
management as part of my thesis work in 2013.   If there is interest I'd be
happy to join a conversation.

http://www.cs.cornell.edu/courses/cs5414/2017fa/papers/bquorum-dc.pdf

/Wm

On Thu, Sep 6, 2018 at 11:14 AM, Steve Crocker <[email-masked]> wrote:

> fleshed out in the paper..  Happy to discuss with anyone interested.
>
> Steve
>
>
>> [2] <https://indico.dns-oarc.net/getFile.py/access?contribId=22&
>> sessionId=3&resId=1&materialId=slides&confId=20>

---

From: Warren Kumari <[email-masked]>
Date: Fri, 7 Sep 2018 14:37:39 -0400

> be extended to include this functionality.
Yup. Two of my concerns are:

1: the HSM has to have a bunch more complexity / content awareness than is
usual - most HSMs simply take a blob and sign it / store keys. This will
require the HSM to have much more understanding of the content, and
understand who the "owner" of each RR is, NSEC / NSEC3 , etc. This logic
all needs to live inside the security envelope, not in the system driving
it. Any "interesting" new resource record types will require updating of
the secure logic. This will be largely a one-off bit of code, and will
require careful code review of the initial, and any new code (and based
upon the amount of review of https://github.com/iana-org/dnssec-keytools
I'm not sure the community has the time / desire). Any scewup by the HSM
makes 1: that TLD or 2: the entire zone unavailable.

2: Based upon things like https://ianix.com/pub/dnssec-outages.html, it is
clear that even TLD operators sometimes manage to shoot themselves in the
foot. Yes, the majority of these are expirations, but it is clear that
people will mess this up. The root KSK is well protected, with people being
really careful, but even that has some risk - multiply that by the number
of TLDs (or opted in TLDs) and the risks multiply. This means that you
really really need a fast, reliable way to regain access in the event of an
Oops... and now you have what looks awfully like a backdoor.

> fleshed out in the paper..  Happy to discuss with anyone interested.

Thank you, happy to discuss further, but the above concerns are why I think
(at least at the beginning) why something similar to Certificate
Transparency but for the root zone is much safer - yes, it provides
deterrence through transparency instead of inviolate crypro protection -
but this same reason prevents a minor mistake turning into a major outage.

This is a summary of a document from back in ~2015 (before the PTI
transition, and so the terminology / focus is historic):
------------------------
*Sunlight is the best disinfectant.*

Currently, the entity that generates the root zone has full control over
the contents. While this is not a new issue or concern, it is being brought
to the public eye because of the IANA transition. To ensure that that
entity doesn’t abuse the power/privilege, or make incorrect or unauthorized
changes, we propose the following.

Transparency and accountability are both fundamental to the safe and
successful management of IANA, regardless of under whose management IANA
sits. To that end, we propose a publicly verifiable, published audit trail
for any and all changes to the root zone. No invisible/unaudited changes
will be able to be made to the root zone by any party. The entity
generating the root zone has full control over what ends up in the file; in
order to ensure that there are no abuses of this power, any and all changes
to the root zone would require a full audit trail.

To implement this technically, each TLD operator will cryptographically
sign and publicly publish any requested updates to their entries in the
root zone. No changes will be made to the root zone without accompanying
signatures. The entity generating the root zone will validate all
signatures before making the changes. Because all of this will be public,
auditors will be able to see from whom the request originated, how it was
validated, and when it was implemented. This is a general case/solution;
emergency backup procedures will also be in place as needed (i.e., if a
country loses its signing key).

So, if the ‘example’ TLD wanted to update its nameservers, it would
generate a change request (format to be discussed later) and digitally sign
the request. It would then publicly publish this change request. The IANA
Functions Operator would then validate the change request for technical
accuracy, and publically sign the change request to confirm that it is
technically correct. The root zone maintainer will validate that the change
request is correctly signed by both the requester and the IANA functions
operator, and will then make that change in the root zone.

Note that this solution does not prevent malfeasance by the IANA functions
operator, or the root zone maintainer; but as all changes are published
with cryptographic signatures, auditors can validate this.

There will also need to be solutions in place to deal with loss of keys by
the TLD operator, and the IANA. The TLD operator can roll to a new key by
signing it with their old one, which invalidates the old key.
-----------------------

Somewhere I still have the full document, a proposed encoding, a modified
Certificate Transparency log which will accept arbitrary text blobs (and an
extension to allow templates in certificates), client software, etc.

W

>> [2] <
>> https://indico.dns-oarc.net/getFile.py/access?contribId=22&sessionId=3&resId=1&materialId=slides&confId=20
>> >
>> [3] <
>> http://buenosaires48.icann.org/en/schedule/wed-dnssec/presentation-dnssec-cryptographic-20nov13-en
>> >
>>
>>

-- 
I don't think the execution is relevant when it was obviously a bad idea in
the first place.
This is like putting rabid weasels in your pants, and later expressing
regret at having chosen those particular rabid weasels and that pair of
pants.
   ---maf