1 Introduction

The Domain Name System (DNS) [RFC1033, RFC1034], one of the core Internet protocols, performs lookup services and provides a platform for an increasing number of systems and applications. DNS was not designed with security in mind and is alarmingly vulnerable to DNS cache poisoning  [2, 6, 9, 22, 23, 36]. DNS Security extensions (DNSSEC) [RFC4033–RFC4035] was standardized to mitigate cache poisoning using cryptographic techniques. At a high level, DNSSEC enables certification of DNS records in a response such that the machine making the query can verify that it was not tampered with, assuming the DNS operator is trusted. A record is certified using a digital signature scheme, with RSA and ECDSA being the supported algorithms [RFC 5702, RFC 6605]. While RSA is the most commonly used scheme, the need to prevent fragmentation of UDP responses requires the signing keys to be short. ECDSA is the better choice moving forward as it provides the same level of security as RSA but with much smaller signatures. While DNSSEC prevents cache poisoning, this only holds insofar as the operator is trusted. Moreover, DNSSEC additionally requires the operator to manage cryptographic keys. Both these requirements manifest themselves as areas of insecurity in practice.

Centralization of Key Management. DNSSEC burdens the provider with the additional task of generating and managing the keys of their users. Recent work has demonstrated that a large number of domains share the same key  [12]. Sharing the same key across multiple domains makes the DNSSEC provider a lucrative target. If the key of one domain is compromised, several other domains can be compromised as well. Another study  [34] has shown issues with key generation that result in keys with inadequate security.

Centralization of Operation. A second issue that arises from the problem of the DNS operator being in-charge of key management is that the entire operation is centralized. In other words, any guarantee towards integrity of a DNS response to a query is lost if the operator cannot be trusted. This implies that DNSSEC does not prevent attacks from powerful adversaries on the operator, such as nation-state actors. In recent years, several examples of sophisticated attacks on DNS registrars have been observed in Germany  [32], Greece  [14] and Sweden  [30] as part of attacks on DNS infrastructure  [37].

1.1 Threshold Signing

Threshold signatures are a natural candidate to solve the issues outlined above. A threshold signature scheme distributes a signing key to n signers such that any subset of at least t signers can sign a message. Since the signing key is distributed among many signers, it will remain private as long as at least t servers remain uncompromised. Moreover, the threshold signing scheme can be made secure against tampering, i.e., a malicious operator cannot compromise the integrity of a response.

While threshold RSA has previously been studied for fault tolerance in DNSSEC, threshold ECDSA has not been used for DNSSEC in spite of an increased interest in threshold ECDSA in recent years  [18, 19, 21, 27, 28]. All of these recent works motivate the problem of threshold ECDSA in the context of crypto-currencies, a problem that is substantially different from DNSSEC: First, recent work on threshold ECDSA focus on “full threshold”, i.e., privacy of the signing key is maintained when up to \(t=n-1\) signers collaborate. Second, the focus has typically been on “malicious” security, i.e., signers are not assumed to behave according to the signing protocol. However, it is possible to design faster protocols by relaxing some of these security guarantees, e.g., by requiring an honest majority, or assuming that signers do not deviate from the signing protocol. The diverse context in which DNS is used can benefit from solutions that are not limited to a specific threat model.

In the real world application of DNSSEC where multiple operators (e.g., 3) serve a domain, the possibility of only one of them being controlled by an adversary is reasonable as operators are often corporations located in different parts of the world and adhere to different local laws. In such a setting, a “full threshold” protocol may not be necessary, and a protocol that assumes an honest-majority (i.e., with 3 servers this implies none of the servers collude) among the operators can be sufficient. Moreover, DNS operators are bound by legal contracts with their customers and they provide service according to this contract. These legal bounds allow us to consider operators that do not act maliciously since that would be a breach of contract. However, in such a case we will still be interested in protecting keys stored at the operator.

1.2 Contributions

A summary of our contributions:

  • A generic transformation for secure multiparty computation (MPC) protocols over a field \(\mathbb {Z}_{p}\) to protocols over an elliptic group of order p, such as one used in ECDSA.

  • An implementation of this transformation in MP-SPDZ [17] to support threshold signing with ECDSA in many different threat models. We benchmark each instantiation against state-of-the-art protocols for threshold signing and show that they perform comparably.

  • A measurement study to understand the extent to which multiple providers for a given domain is used on the Internet.

  • A prototype of a full implementation, based on our implementation in MP-SPDZ and Knot, as well as experiments showing that threshold signing incurs only a minimal overhead.

1.3 Outline

Section 2 presents a measurement study we performed. We show that a significant number of domains use multiple operators, which allows them to easily use our solution. Section 3 outlines our system and threat model. Section 4 presents our technical contribution as well as our threshold signing protocol. Section 5 shows how we integrate our signing protocol into a well-known DNSSEC application. Section 6 presents a number of different experiments and comparisons to prior work. Section 7 discusses how our work relates to prior works before the conclusion is presented in Sect. 8.

2 Quantifying Multiple Operators

Since the large DDoS attacks on Dyn  [20] and NS1  [5] in 2016, many domains are using more than one operator to increase the redundancy of the zone so that they do not fall victim to another DDoS attack. However, no recent work has measured the number of domains that make use of multiple operators. As we propose to use our multiparty ECDSA protocol for DNSSEC zone signing, we measure the extent to which multiple operators are used on the Internet. We consider a domain to have more than one operator if the DNS name servers of the same domain are hosted by an entirely different DNS operator.

2.1 Data Collection Methodology

If a domain name is configured to be served by three DNS name servers, we check whether it is managed by the same operator. For our purpose, we are interested in nameservers run by different operators and not necessarily name servers placed at different locations. For instance, some domains might use two operators who are geographically located in close proximity to each other; sometimes, even in the same data centre. We are interested in the setting with different operators as they do not trust each other with signing keys and they do not have a business relationship with each other that will allow them to pass on copies of signing keys. Hence, being geographically close does not eliminate the need to run a secure signing protocol. Some domains make use of a single operator which has name servers at different locations. In principle, a multiparty ECDSA protocols can be used in this setting as well because it provides better security than simply storing a copy of the signing key on each name server.

Our measurements were conducted using the Alexa Global Top 1 million listFootnote 1 as the dataset. The list was downloaded on 12 July 2019. We ran scans on the same date on all the domains in the dataset and requested its NS records. For each NS record we also obtain the first associated A record. On obtaining the NS record, we have the list of authoritative name servers. We compare the sub-domains of country code TLDs (ccTLDs), country code second-level domains (ccSLDs) and generic TLDs (gTLDs). E.g., if the two name servers of a domain are dns1.p09.nsone.net. and ns1.p43.dynect.net., then we compare nsone and dynect. However, we do not only compare the SLD names. For instance, if there is a third name server for the same domain at pdns6.ultradns.co.uk., then we compare ultradns with nsone and dynect.

To measure how many domains use multiple operators, we need to know the owners of the authoritative name servers. Though it is possible to obtain this information from the WHOIS database using the A records we collected, the information obtained does not have a consistent schema and is heavily rate limited  [29]. Hence, we use the WHOIS database to only check information for Alexa Top-1k; for the rest of Alexa Top 1 million, we take an approach similar to  [12] and rely on the NS records to indicate the DNS operator. We made manual checks to make sure that subsidiaries of large corporations are not classified as separate operators. (For instance, Chinese online shopping website taobao.com is a subsidiary of the Alibaba group, and we found that one of their name servers is owned by Alibaba and hence, we classified them as the same operator.) Note that large organizations such as Facebook and Google run dedicated networks which provides DNS redundancy. However, as it is run by the same organization, we do not account for them in our list of domains with multiple operators.

2.2 Data Analysis

We classified domains as having a single operator (Only 1), multiple operators (More than 1), no response (NR) and misconfigured (Misconf). An NR classification refers to the case where, during our scans, we did not receive a response with the name server list within a 15-s timeout. Misconf refers to zones which are misconfigured due to mistakes and/or typos. More precisely, we first observed whether we received an A record for the NS record. If we instead receive an error, we then checked the NS record for completeness. If, during this check, we encouter mistakes or typos, the domain is marked as misconfigured. E.g., just ds0. was configured as one of the authoritative name servers for the domain oxfordlearnersdictionaries.com. See Fig. 1 for the result of classifying the Alexa Global Top 1 million, as well as its subsets, in this manner.

Fig. 1.
figure 1

Domains with multiple operators

Full size image

We did not receive a response to our queries from 3, 24, 208, 60775 domains in the Top-100, Top-1k, Top-10k and Top-1m respectively. Although we did not find any misconfigured domains in the Top-1k, we found 13 misconfigured domains in the Top-10k and 2483 domains in Top-1m. We observe that 40% of the domains in Alexa Top-100 have more than one operator while the proportion reduces as we move down the Top-1m list. 20.3%, 9.2% and 3.5% of the domains in the Top-1k, Top-10k and Top-1m have more than one operator for their domain. Hence, we conclude from our measurements that there are thousands of domains that use multiple operators and that can easily plug-in our threshold ECDSA protocols.

3 System and Threat Model

The diversity of the DNS ecosystem should be reflected in our system and threat model. For the system model, we assume a small number of operators that serve a single domain. As seen in the previous section, this setting is common in practice, in particular among popular domains. For the threat models, we take the two issues outlined in the introduction as our starting point. Before we continue, we describe the security properties that we address with our threat model:

  1. 1.

    Key Privacy. This is our baseline. Key privacy states that signing key remains private in the event that a server is compromised. We note that this property is relevant in a number of different contexts. For example, this property states that a signing key isn’t exposed to a system administrator, or to anyone who obtains a decommissioned (but improperly cleaned) server.

  2. 2.

    Operational Integrity. Besides keeping keys secret, we may also want to uphold the integrity of operation. By operational integrity, we mean that only two situations can occur: Either operation proceeds as normal, that is, the right zone is signed, or nothing is signed. In other words, at best, a malicious operator can only disrupt operation, i.e., it performs a denial of service attack but it cannot sign zones with bogus information. Notice that key privacy is subsumed in operational integrity. If it is possible to extract the signing key, then no guarantee about the integrity can be made since a single operator can sign any zone it manages at will.

3.1 System and Communication Model

Intuitively, our system model can be viewed as distributing the task of a single operator among multiple operators. To simplify things, we assume that such a system has either \(n=2\) or \(n=3\) operators who maintain a fixed set of domains. These operators can be distributed in a single location, communicating over a LAN, or they can be distributed globally. Finally, we assume that the servers are sufficiently separated, that is, a compromise of one server does not automatically lead to a compromise of another server.

3.2 Threat Model

We consider an adversary that is capable of compromising a single server. Thus, when \(n=2\), the adversary controls half the servers, and when \(n=3\), the adversary controls a minority (since 2 servers remain honest). We distinguish between the two standard adversarial models from the MPC literature. The first type of adversary, called passive, is characterized by following the prescribed protocol. The second adversary, called active, may behave arbitrarily and not follow the protocol. Notice how these two adversarial types capture our security properties. If we only desire key privacy, then security against a passive adversary suffices. If we want operational integrity as well, then we must also secure ourselves against active adversaries. Indeed, it is exactly against such an adversary that the integrity of operation becomes an issue.

4 Threshold ECDSA

In this section we present a generic transformation of any secure computation protocol over a field \(\mathbb {Z}_{p}\) into a protocol for a group of order p. In particular, this technique enables an efficient method to compute threshold ECDSA signatures.

Fig. 2.
figure 2

The arithmetic black-box functionality.

Full size image

4.1 ECDSA Signing

ECDSA as standardized in  [25] is parametrized by a curve E(K) for a field K. Let \(\mathcal {G}\subseteq E(K)\) be an additive subgroup group of order p with generator G, and let \(\mathbb {Z}_{p}\) denote the field of size p. Given a message M, secret key \(\mathsf {sk}\in \mathbb {Z}_{p}\), signing is performed as follows:

  1. 1.

    Sample \(k \leftarrow \mathbb {Z}_{p}\) at random.

  2. 2.

    Compute \((r_{x},r_{y})=k\cdot G\).

  3. 3.

    Let \(s=k^{-1}(H(M)+\mathsf {sk}\cdot r_{x})\) where H is a hash function mapping messages into elements of \(\mathbb {Z}_{p}\).

  4. 4.

    Output signature \(\sigma =(r_{x},s)\).

4.2 Secure Multiparty Computation

We assume a MPC engine supporting the standard commands of the arithmetic black-box (ABB) functionality as shown in Fig. 2, where the notation \([{a}]\) indicates that the value a is “secret-shared”, i.e., no party has access to it. The security model of a MPC protocol is parametrized by two variables. First, whether the adversary can control at least half, or less than half the parties. The former is called dishonest majority, while the latter is called honest majority. Observe that an honest majority protocol would correspond a setting with \(n=3\) servers, while a dishonest majority protocol means \(n=2\). The second parameter is the corruption model: The two cases considered here—active and passive—correspond to our description in Sect. 3.2.

4.3 Secure Computation on Groups

We present an extension to the ABB that extends its capabilities to secure computation over an arbitrary Abelian group of order p. In some sense, this shows that the actual representation of the algebraic structure used to perform MPC is irrelevant as long as it is possible to perform linear operations. This generalization of arithmetic MPC has also been described independently by  [35], and might have applications in other contexts. In this paper, we use this idea to perform MPC in subgroup \(\mathcal {G}\). This extension comes at no extra cost in terms of communication and a small increase in computation complexity (corresponding to standard operations in the subgroup of the curve).

Consider a protocol implementing the ABB in Fig. 2 and assume that the shares \([{a}]\) are also elements of \(\mathbb {Z}_{p}\). The idea is to let each party map their share of \([{a}]\) to a curve point of order p by locally computing \(A_{i}=a_{i}\cdot G\), where \(a_i\) is party i’s share of a. This mapping, being a homomorphism, preserves linearity and so \(A_{i}\) is a share of \(a\cdot G\) with the same properties as the original \(\mathbb {Z}_{p}\) sharing \([{a}]\). In the following, we write \(\langle {a}\rangle \) to denote a share of \(a\cdot G\), and we add the following two commands to the ABB in Fig. 2:

  • A command \(\langle {a}\rangle \leftarrow \mathsf {Convert}([{a}])\) that converts a representation of the shared value a in \(\mathbb {Z}_{p}\) to a representation of the value \(a\cdot G\) in the group \(\mathcal {G}\).

  • A command \(a\cdot G\leftarrow \mathsf {Open}(\langle {a}\rangle )\) that recovers the secret shared point.

These two commands are sufficient to give us a protocol for secure computation over the group \(\mathcal {G}\). If we consider the sharing \([{a}]\) as a vector with elements from \(\mathbb {Z}_{p}\), we get the following useful properties:

  • Linearity is preserved, i.e., given the shares \(\langle {a}\rangle \), \(\langle {b}\rangle \) and scalars \(x,y\in \mathbb {Z}_{p}\), we can locally compute \(\langle {c}\rangle =x\langle {a}\rangle +y\langle {b}\rangle \).

  • If the \(\mathsf {Open}\) procedure for \([{\cdot }]\) shares relies only on group operations in \(\mathbb {Z}_{p}\), then we can implement \(\mathsf {Open}\) for \(\langle {\cdot }\rangle \) shares by using the corresponding group operations of \(\mathcal {G}\). This property follows from the fact that \(\mathsf {Convert}\) is structure preserving.

  • Secret scalar multiplication by public point is possible by noting that \(\mathsf {Convert}\) defines an action of \(\mathbb {Z}_{p}\) on \(\mathcal {G}\), i.e., \([{a}]\cdot P\) for a \(P\in \mathcal {G}\) is a local operation that results in \(\langle {a\cdot \log _P(G)}\rangle \). Note that opening this share will result in \(a\cdot P\).

  • Finally, given \([{x}]\) and \(\langle {y}\rangle \) (and a multiplication tuple \([{a}],[{b}],[{c}]\)) it is possible to compute \(\langle {xy}\rangle \) using a slight tweak on Beaver’s technique as follows: (1) \(e=\mathsf {Open}([{a}]+[{x}])\), (2) \(D=\mathsf {Open}(\mathsf {Convert}([{b}])+\langle {y}\rangle )\), (3) \(\langle {xy}\rangle =\mathsf {Convert}([{c}])+e\langle {y}\rangle +[{x}]D-eD\). Note that this property is not required for our application but could be of independent interest.

The properties of \(\mathsf {Convert}\) and \(\mathsf {Open}\), as well as the functionality of the underlying ABB (which provide secure computation over \(\mathbb {Z}_{p}\)) is enough to give us a protocol for secure computation over \(\mathcal {G}\). This extended ABB (which we will call ABB+) is shown in Fig. 3.

Fig. 3.
figure 3

ABB from Fig. 2 extended to support computation over elliptic curves.

Full size image

4.4 Active Security Using SPDZ Like MACs

The previous section showed that one can easily extend a protocol of \(\mathbb {Z}_{p}\) with functionality for secure computation over a subgroup of \(\mathcal {G}\subseteq E(K)\) of order p. A natural question to ask is whether the active security guarantees of the \(\mathbb {Z}_{p}\) protocol extend to the \(\mathcal {G}\) protocol. We answer this question in the affirmative by showing that the MAC scheme of SPDZ  [16] can be used to provide authentication of shares in \(\mathcal {G}\) (i.e., \(\langle {\cdot }\rangle \) shares) as well.

SPDZ Recap. We recall the SPDZ protocol and its security using the description from [15]. In SPDZ a value \(a\in \mathbb {Z}_{p}\) is shared as

$$ [{a}]=((a_{1},\dots ,a_{N}),(\gamma (a)_{i},\dots ,\gamma (a)_{N})), $$

where party i holds the pair \((a_{i},\gamma (a)_{i})\), and where \(a=\sum _{i}a_{i}\) and \(\alpha \cdot a = \gamma (a)=\sum _{i}\gamma (a)_{i}\). The value \(\alpha \in \mathbb {Z}_{p}\) is a global MAC key which is secret shared using a different scheme, \(\llbracket {\alpha }\rrbracket \). (The details of this are not important for the following discussion; it suffices to say that each party has a share \(\alpha _i\), such that \(\sum _i \alpha _i =\alpha \), as well as other information to make this sharing secure) The global MAC key is unknown to all parties and provide a notion of authentication of the shares.

We recap here the opening phase of the SPDZ protocol for a single value, i.e., the part where the parties check if the output was computed correctlyFootnote 2:

  1. 1.

    Each \(P_{i}\) has input \(\alpha _{i}\), their share of the global MAC key, and \(\gamma (a)_{i}\), their share of the MAC on a partially opened value aFootnote 3.

  2. 2.

    Each \(P_{i}\) computes \(\sigma _{i}=\gamma _{i}(a)-\alpha _{i}a\) and broadcasts a commitment \(\mathsf {com}(\sigma _{i})\).

  3. 3.

    All parties open \(\mathsf {com}(\sigma _{i})\), compute \(\mathsf {chk}=\sum _{i}\sigma _{i}\) and abort if \(\mathsf {chk}\ne 0\).

Suppose \(a'=a + \epsilon \), i.e., the adversary adds an error \(\epsilon \ne 0\) during the partial opening. If, in addition, the adversary lies about its MAC in Step 2 of SPDZ opening phase and let \(\varDelta \) denote this error, then the adversary is successful if \(\varDelta =\sum _{i}\sigma _{i}\). In this case, we have

$$ \varDelta = \sum _{i=1}^{n}\sigma _{i} = \sum _{i=1}^{n}\gamma _{i}(a) - \alpha _{i}a = \alpha \epsilon . $$

Since \(\epsilon =(a-a')\ne 0\), then \(\alpha =\varDelta \epsilon ^{-1}\) which happens with probability at most 1/p due to the random choice of \(\alpha \).

SPDZ-Like Computation Over an Elliptic Curve. In the remainder of this section, we will use the shorthand notation \(\mathsf {cv}(a)=\mathsf {Convert}(a)\) interchangeably for convenience. Consider the most natural modification possible to obtain a notion of a SPDZ-sharing \(\langle {\cdot }\rangle \) over \(\mathcal {G}\), from a SPDZ-sharing \([{\cdot }]\) over \(\mathbb {Z}_{p}\), by applying \(\mathsf {cv}\) to all local shares. We define \(\langle {a}\rangle \) as the vector

$$ \langle {a}\rangle = ((\mathsf {cv}(a_{i}),\dots ,\mathsf {cv}(a_{N})), (\mathsf {cv}({\gamma (a)_{i}}), \dots , \mathsf {cv}({\gamma (a)_{N}}))), $$

where \(P_{i}\) holds \((\mathsf {cv}(a_{1}), \mathsf {cv}(\gamma (a)_{i}))\). Observe that the linearity of \(\mathsf {cv}\) implies that \(\sum _{i}(\mathsf {cv}(a_{i}))=\mathsf {cv}(\sum _{i}a_i)=\mathsf {cv}(a)\), which makes the above a valid sharing of \(\mathsf {cv}(a)\). In addition, the semantics of the MAC is preserved since

$$ \sum _{i}\mathsf {cv}(\gamma (a)_{i}) = \mathsf {cv}(\sum _{i}\gamma (a)_{i}) = \mathsf {cv}(\alpha \cdot a). $$

Therefore, we can use the same \(\llbracket {\alpha }\rrbracket \) to authenticate the \(\mathsf {Convert}\)ed share as well. More precisely, we consider a modified opening procedure that works as follows:Footnote 4

  1. 1.

    Let \(\alpha _{i}\) be the share of the key held by \(P_{i}\), and \(\varGamma _i=\mathsf {cv}(\gamma (a)_{i})\) be the shares of the MAC on \(A=\mathsf {cv}(a)\).

  2. 2.

    Each \(P_{i}\) computes \(\Sigma _{i}=\varGamma _{i}-\alpha _{i}A\) and broadcasts a commitment \(\mathsf {com}(\Sigma _{i})\).

  3. 3.

    Open \(\mathsf {com}(\Sigma _{i})\), compute \(\mathsf {chk}=\Sigma _{1}+\cdots +\Sigma _{N}\) and abort if \(\mathsf {chk}\ne 0\).

It follows that, due to the linearity of the group operations, if the adversary opens \(A'\ne A\), then the check only passes with probability 1/p. In a nutshell, we are taking a secure linear MAC procedure, and raising all the MACs and values in the exponent. Since the SPDZ MACs are information theoretic secure, the security of the “MAC in the exponent” can be reduced to the security of the regular MAC (as the reduction can run in unbounded time and retrieve the original MAC).

4.5 Multiparty ECDSA Protocol Using the ABB+

We recall the protocol of Gennaro and Goldfeder  [21] and show that it can be computed by our extended arithmetic black box functionality. The main issue with computing ECDSA signatures securely is calculating \(k^{-1}\) such that it does not reveal information about k. However, the inversion trick by Bar-Ilan and Beaver  [3] can be used here: Suppose each party has a share of two random values \(\gamma \), k, and their product, i.e., \([{\gamma }]\), \([{k}]\), \([{\delta }]\) where \(\delta =\gamma \cdot k\). The parties can then open \(\delta \) and use it locally to compute their share of \([{k^{-1}}]=\delta ^{-1}[{\gamma }]\). Thus the price to pay for the inversion (which is the most expensive part of every threshold ECDSA protocol) is essentially just generating a random multiplication triple using \(\mathsf {RandMul}\), and using \(\mathsf {Convert}\) to compute the value \(R=\mathsf {Open}(\mathsf {Convert}([{k}]))\). The other value we need is a sharing of \(\mathsf {sk}/k\). Given \([{k^{-1}}]\) it is possible to compute \([{\mathsf {sk}/k}]\) very efficiently by performing a single secure multiplication.

The full protocol using the ABB+ now follows: We consider a setting with a number of servers \(\mathcal {S}=\{S_{1},\dots ,S_{N}\}\) and a number of users \(\mathcal {U}=\{U_{1},\dots ,U_{\ell }\}\). Our protocol has 4 phases: Key generation in which a random secret key is generated using \([{\mathsf {sk}}]=\mathsf {Rand}()\), and then converted into the public key by running \(\mathsf {pk}=\mathsf {Open}(\mathsf {Convert}([{\mathsf {sk}}]))\). (Alternatively, users can pick their own keys and input them to the servers in \(\mathcal {S}\)). Next up are two preprocessing phases: One phase is independent of the users and the messages to be signed, and serves to generate the values [\(k^{-1}\)] and \(\langle {k}\rangle \) that are required for generating any signature; the other phase depends on the user and computes \([{\mathsf {sk}_{j}/k}]\), where \(\mathsf {sk}_{j}\) is the signing key of user \(U_{j}\). Finally, generating a signature using the output of the preprocessing and the user’s signing key is just a matter of performing a linear computation followed by an opening. We show the details of the full protocol in Fig. 4.

Fig. 4.
figure 4

Protocol with preprocessing computing threshold ECDSA signatures using our extended ABB.

Full size image

Security Analysis. Security of the protocol in Fig. 4 follows directly from the security of the underlying ABB scheme, and from an assumption that ECDSA is a secure signature scheme (this assumption has also been used in  [18] and  [19]).

5 Multiparty Zone Signing System

In this section, we describe the integration of our threshold ECDSA implementation in a DNS name server before describing the important operations. We implement several variants of our threshold ECDSA protocol on top of MP-SPDZ [17] and have used Crypto++ as the library for computation over elliptic curves. We integrate MP-SPDZ with DNS administrative name servers. For DNS name server software, we use Knot DNS  [26] as it has the possibility to perform automated key management and it comes with extensive documentation. For the setting where the registrar is the DNS operator, we propose that registrars interact with other registrars in the zone signing protocol. We describe the multi-operator setting in this section and, where necessary, we note the difference if the operators are also the registrar.

5.1 Setup

In our DNSSEC signing system, each operator serves a name server, runs a threshold ECDSA module and has two key stores: one to store the keys for particular zones and another to store the key material associated with other operators. We consider three name servers operated by independent DNS operators, all of which support ECDSA with SHA256 message digest. We do not change the operation of Knot DNS apart from the parts involved in DNSSEC key generation, key rollover and zone signing. Communication between the name server and the threshold ECDSA module is performed using a message queue.

5.2 Key Generation/Rollover

In the key generation/rollover phase, when new keys need to be generated, each operator generates a signing key sharing \([{\mathsf {sk}_{j}}]\) for the zone and runs the key generation as shown in Fig. 4. At the end of this phase, the public key is added to DNSKEY record of the zone at all the operators and the signing key share \([{\mathsf {sk}_{j}}]\) is stored in the keystore for the zones. In addition, a tag that indicates the DNS operators associated with this signing key share is stored. E.g., Operator A would store a tag T(B, C) along with the key shares associated with Operator B and Operator C. This makes it easy for the threshold ECDSA module to contact the corresponding DNS operators during the signature generation phase. Note that the key generation for ZSK and KSK is the same except that in the case of KSK, the domain owner generates the DS record and sends it to the registrar, who then submits it to the registry. When the registrar is one of the DNS operators of the zone, then the registrar can directly submit the DS record.

5.3 Zone Signing

As shown in Fig. 4, our signing protocol has three phases: the first is independent of the zone to be signed, while the second is independent of the RRset, but dependent on the zone to be signed. Each of the three phases involve three steps that are shown in Fig. 5. In Step 1, the threshold ECDSA module receives the input for the phase from the name server and the tag from the key store. In Step 2, the MPC protocol for the phase is run between the threshold ECDSA module of the three operators. In Step 3, the output of the preprocessing phases are sent to the key store (Step 3p) while the output of the signing phase, RRSIG, is sent to the name server to store in the zone file (Step 3s). We note that the threshold ECDSA module runs in the background and periodically polls the name server so that it is always available to sign.

Fig. 5.
figure 5

Zone signing

Full size image

Implication for DNS Operators. In our system, the DNS operators do not need to be online any more than they already are in existing systems. DNS operators in existing systems remain online to respond to DNS queries. Many DNS operators sign DNS responses on-the-fly and, hence, they are already equipped with signing systems that are online. In our system they will not only respond to DNS queries, they will also run MPC with other registrar/operators to create RRSIG. Our threshold ECDSA protocols have an overhead—both in terms of communication and computation—that depends on the concrete threat and system model. We discuss the overheads as part of our benchmarks in Sect. 6. It is also worth noting that the operators need not rely on secure hardware to store their user’s keys anymore, which may bring down both the cost and complexity for a DNS operator.

Implication for DNS Resolvers. Proper functioning of the DNSSEC ecosystem requires both the signing and the validation to work. Deploying changes at DNS resolvers is extremely hard as numerous resolver software need to be changed. Fortunately, no change is required at the validating resolver to use our solution. Every time the domain is queried at the authoritative name server, the signatures for the zone need to be verified at the resolvers for the chain of trust to be established. Though three operators are involved in the signing process, the signature can be verified with the same DNSKEY, irrespective of the operator which initiated the signing process. If the DNS resolver obtains the DNSKEY records from Operator A and stores it in the cache, then it will be able to authenticate a response from Operator B for the same domain, as the two operators have the same DNSKEY for the zone. The resolver will be able to verify the chain of trust irrespective of the operator responded to the query.

6 Evaluation

In this section we report on several benchmarks of our protocol and compare with prior work of both signature generation and key generation times. We implement six varieties of our protocol (thus supporting different system and threat models) in MP-SDPZ  [17]. For \(n=3\) we have Rep3, Shamir (passive security) and Mal. Rep3 and Mal. Shamir (active security). We remark that only the Shamir protocols support \(n>3\). For \(n=2\), we use MASCOT and MASCOT– (MASCOT minus) where the latter is a heuristic optimization of the former. Many of these protocols have asymmetric communication patterns and thus we report the maximum execution time, instead of the average. All experiments were run on AWS c5.2xlarge instances in three settings: LAN, continental WAN and worldwide WAN. The maximum RTT between any two servers in these settings are 0.08 ms, 17 ms and 240 ms, respectively.

6.1 MASCOT– Optimizations

Our MASCOT– protocol is obtained by making a number of function specific optimizations to MASCOT  [24]. Threshold signatures are a special case of MPC where the correctness of the output can trivially be determined by observing the output itself (by verifying the signature). This is a well known trick which has previously been used to optimize many threshold ECDSA protocols in the literature. We can similarly optimize our protocol by using an “optimistic” version of the \(\mathsf {Open}\) command when running Step 3 of the Signing subroutine in Fig. 4.

SPDZ Opening. We save a round of communication during opening as we do not need to check correctness of the MACs. Omitting this attack permits the adversary to make an additive attack, which may result in an invalid signature, but does not leak anything about the secret key.

Beaver Multiplication. Suppose the adversary can perform an additive attack during multiplication. That is, \(x+a+\epsilon _{1}\) and \(y+b+\epsilon _{2}\) for independent \(\epsilon _{1}\) and \(\epsilon _{2}\). A multiplication becomes

$$ (x + a + \epsilon _1) \cdot (y + b + \epsilon _2) - (x + a + \epsilon _1) \cdot b - (y + b + \epsilon _2) \cdot a + ab = xy + \epsilon _1 y + \epsilon _2 x + \epsilon _1 \epsilon _2. $$

This permits a selective failure attack (e.g., \(\epsilon _{2}=0\), \(\epsilon _{1}\ne 0\) then the multiplication is correct if and only if \(y=0\)). However, multiplications are only used on \(k^{-1}\) and \(\mathsf {sk}\), both of which are of high entropy.

6.2 Comparison with Prior Work

We present a comparison of our protocols with two industry protocols from Unbound [38] and KZen [31], as well as the two-party protocol of Doerner et al.  [18] (DKLS) in Table 1. The numbers reported for our protocols correspond to running all three phases in Fig. 4. We see that MASCOT– performs as well as the fastest prior protocol in DKLS, with the same security guarantees, in the LAN setting. However, with more servers, some of our protocols perform better in the LAN setting. In our two WAN settings, DKLS outperforms our protocols, a fact we attribute to the fact that DKLS requires only 2 messages (1 round of communication) whereas our fastest protocol (Rep3) requires 3. Interestingly, the simplicity of our key generation protocol is very apparent, and in all cases (except MASCOT–) key generation is faster than signing.

6.3 Key Generation

We also benchmark the key generation phase as that is typically the more expensive phase in prior works (e.g.,  [21, 28]). With our approach, generating a shared key amounts to running any protocol for generating a secret shared field element \([{\mathsf {sk}}]\), followed by opening the result of \(\mathsf {Convert}{[{\mathsf {sk}}]}\). Timings for key generation is shown in Table 2. For our honest majority protocol (\(n=3\)) generating a secret key requires only 1 or 2 rounds of communication. MASCOT and MASCOT– is slightly different in that the opening procedure is more costly. Finally, notice that MASCOT– and MASCOT perform the same. Indeed, the heuristics used to obtain MASCOT– cannot be used when generating keys.

6.4 Amortizing Signing

Finally, we analyze the cost of signing when amortization is applied, something that no prior work has considered.Footnote 5 Table 3 shows how many signing tuples each protocol can generate per second. The signing times reported in this table correspond to computing a signature when amortization is taken into account. A signing tuple corresponds to the output of the user dependent preprocessing phase in Fig. 4. We note that, for almost all protocols, amortized signing corresponds essentially to a single round of communication.

Table 1. Comparison with prior work. Numbers for our protocols are obtained by taking the mean over the maximum execution time over many runs.
Full size table
Table 2. Breakdown of key generation benchmarks into the time it takes to generate the \([{\mathsf {sk}}]\) sharing, and the time it takes to run \(\mathsf {Open}({\mathsf {Convert}({[{\mathsf {sk}}]})})\). Times are the maximum time that each step takes.
Full size table

6.5 Overhead for Operators

The storage overhead can be derived from the sizes of a share for a given protocol. For Mal. Rep3, MASCOT and Rep3 each share consists of two \(\mathbb {Z}_{p}\) elements, while for the rest a share is a single element. Thus, for the former three the overhead for storing the signing keys is doubled. A signing tuple consists of two \(\mathbb {Z}_{p}\) shares and one \(\mathcal {G}\) share. For example, Rep3 needs to store roughly \(2\cdot 4\cdot 32\) bytes per signature, assuming a 256-bit prime. Communication per party is between 177 and 354 bytes, depending on the protocol (this number was derived at experimentally).

7 Related Works

DNSSEC Deployment and Measurement. DNSSEC deployment heavily relies on DNS operators and registrars. Prior works have found issues such as reuse of signing keys by DNS operators for multiple domainsFootnote 6  [12] and sharing of RSA modulus among multiple domains  [34]. After the DDoS attacks of 2016, the impact of the attacks and the number of customers of DyN and NS1 that added another operator was measured  [1]. However, only the domains that use DyN and NS1 were measured while we measure the use of multiple operators, not restricting our measurements to managed DNS providers.

Table 3. Throughput in signing tuples per second as well as signing time when amortization is taken into account.
Full size table

Privacy in DNS. Though DNSSEC provides data integrity, it does not provide confidentiality. “Range queries”  [39] and private information retrieval  [40] have been proposed as a solution to hide queries. Recently, the Internet Engineering Task Force (IETF) has considered privacy issues in DNS and DNSSEC  [7, 8] and proposed DNS-over-TLS [RFC8310] and DNS-over-HTTPS [RFC8484]. While privacy of DNS queries has been considered, we address the issue of privacy of DNSSEC keys.

Threshold ECDSA. Protocols for computing ECDSA signatures in a threshold manner has seen a resurgence lately due to their relevance to crypto-currencies. Doerner et al. have developed threshold ECDSA protocols for both 2-parties [18] and multiple parties [19]. Another recent protocol for dishonest majority is due to Lindell [27]. Even more recently, Castagnos et al. developed a threshold ECDSA protocol from Hash Proof Systems [11].

Threshold Signatures for DNSSEC. Threshold RSA signatures for DNSSEC have been considered in the past. [10] proposed a distributed DNS to avoid single point of failure, which provides fault tolerance and security in the presence of corrupted servers. [13] emulate a HSM at an authoritative name server and they report timings on a LAN which range from tens to hundreds of milliseconds on commodity hardware. Both used RSA threshold signature scheme of [33].

8 Conclusion

Deployment of DNSSEC is still an open problem. Current practices force the domain owners to “outsource” management of their DNSSEC keys to the operators, and trust them not to abuse that knowledge. We replace that trust with distributed mechanism that generates DNSSEC keys and signatures.

Our mechanism is based on a simple but powerful transformation that can be applied to a large class of protocols for secure computation over \(\mathbb {Z}_{p}\) to obtain protocols for secure computation over an elliptic curve group. We demonstrated the appeal of such a transformation by obtaining several very efficient protocols for threshold ECDSA. Our protocols work in the preprocessing model, which allows us to obtain schemes for computing 100s to 1000s of signatures per second.

Our measurements demonstrate that multi-operator solutions for name servers and for domains are popular in the Internet. Finally, motivated by the aforementioned measurements, we show that our protocols provide an efficient solution to existing issues in DNSSEC. In particular, we demonstrate a system that allows multiple distinct operators to digitally sign zone (as required in DNSSEC) at essentially no cost compared to regular single-operator DNSSEC.