resolved: add basic DNSSEC support

This adds most basic operation for doing DNSSEC validation on the
client side. However, it does not actually add the verification logic to
the resolver. Specifically, this patch only includes:

- Verifying DNSKEY RRs against a DS RRs
- Verifying RRSets against a combination of RRSIG and DNSKEY RRs
- Matching up RRSIG RRs and DNSKEY RRs
- Matching up RR keys and RRSIG RRs
- Calculating the DNSSEC key tag from a DNSKEY RR

All currently used DNSSEC combinations of SHA and RSA are implemented. Support
for MD5 hashing and DSA or EC cyphers are not. MD5 and DSA are probably
obsolete, and shouldn't be added. EC should probably be added
eventually, if it actually is deployed on the Internet.

6 files changed, 927 insertions, 7 deletions

diff --git a/Makefile.am b/Makefile.am
index cecd139e4f..29c7f322ea 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -5136,12 +5136,13 @@ polkitpolicy_in_files += \
 	src/import/org.freedesktop.import1.policy.in
 
 EXTRA_DIST += \
-	units/systemd-importd.service.in \
-	src/resolve/resolved.conf.in
+	units/systemd-importd.service.in
 
 
 # ------------------------------------------------------------------------------
 if ENABLE_RESOLVED
+if HAVE_GCRYPT
+
 systemd_resolved_SOURCES = \
 	src/resolve/resolved.c \
 	src/resolve/resolved-manager.c \
@@ -5181,6 +5182,8 @@ systemd_resolved_SOURCES = \
 	src/resolve/resolved-dns-zone.c \
 	src/resolve/resolved-dns-stream.h \
 	src/resolve/resolved-dns-stream.c \
+	src/resolve/resolved-dns-dnssec.h \
+	src/resolve/resolved-dns-dnssec.c \
 	src/resolve/dns-type.c \
 	src/resolve/dns-type.h
 
@@ -5226,9 +5229,6 @@ GENERAL_ALIASES += \
 nodist_pkgsysconf_DATA += \
 	src/resolve/resolved.conf
 
-tests += \
-	test-dns-domain
-
 libnss_resolve_la_SOURCES = \
 	src/nss-resolve/nss-resolve.sym \
 	src/nss-resolve/nss-resolve.c
@@ -5272,10 +5272,34 @@ systemd_resolve_host_LDADD = \
 rootlibexec_PROGRAMS += \
 	systemd-resolve-host
 
+tests += \
+	test-dns-domain \
+	test-dnssec
+
+test_dnssec_SOURCES = \
+	src/resolve/test-dnssec.c \
+	src/resolve/resolved-dns-packet.c \
+	src/resolve/resolved-dns-packet.h \
+	src/resolve/resolved-dns-rr.c \
+	src/resolve/resolved-dns-rr.h \
+	src/resolve/resolved-dns-answer.c \
+	src/resolve/resolved-dns-answer.h \
+	src/resolve/resolved-dns-question.c \
+	src/resolve/resolved-dns-question.h \
+	src/resolve/resolved-dns-dnssec.c \
+	src/resolve/resolved-dns-dnssec.h \
+	src/resolve/dns-type.c \
+	src/resolve/dns-type.h
+
+test_dnssec_LDADD = \
+	libshared.la
+
+endif
 endif
 
 EXTRA_DIST += \
-	units/systemd-resolved.service.m4.in
+	units/systemd-resolved.service.m4.in \
+	src/resolve/resolved.conf.in
 
 # ------------------------------------------------------------------------------
 if ENABLE_NETWORKD
diff --git a/src/resolve/resolved-dns-cache.h b/src/resolve/resolved-dns-cache.h
index 164435b4fb..561d31ad99 100644
--- a/src/resolve/resolved-dns-cache.h
+++ b/src/resolve/resolved-dns-cache.h
@@ -21,7 +21,6 @@
   along with systemd; If not, see <http://www.gnu.org/licenses/>.
 ***/
 
-
 #include "hashmap.h"
 #include "list.h"
 #include "prioq.h"
diff --git a/src/resolve/resolved-dns-dnssec.c b/src/resolve/resolved-dns-dnssec.c
new file mode 100644
index 0000000000..ad28d8adef
--- /dev/null
+++ b/src/resolve/resolved-dns-dnssec.c
@@ -0,0 +1,629 @@
+/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
+
+/***
+  This file is part of systemd.
+
+  Copyright 2015 Lennart Poettering
+
+  systemd is free software; you can redistribute it and/or modify it
+  under the terms of the GNU Lesser General Public License as published by
+  the Free Software Foundation; either version 2.1 of the License, or
+  (at your option) any later version.
+
+  systemd is distributed in the hope that it will be useful, but
+  WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+  Lesser General Public License for more details.
+
+  You should have received a copy of the GNU Lesser General Public License
+  along with systemd; If not, see <http://www.gnu.org/licenses/>.
+***/
+
+#include <gcrypt.h>
+
+#include "alloc-util.h"
+#include "dns-domain.h"
+#include "resolved-dns-dnssec.h"
+#include "resolved-dns-packet.h"
+
+/* Open question:
+ *
+ * How does the DNSSEC canonical form of a hostname with a label
+ * containing a dot look like, the way DNS-SD does it?
+ *
+ * */
+
+#define VERIFY_RRS_MAX 256
+#define MAX_KEY_SIZE (32*1024)
+
+/*
+ * The DNSSEC Chain of trust:
+ *
+ *            Normal RRs are protected via RRSIG RRs in combination with DNSKEY RRs, all in the same zone
+ *            DNSKEY RRs are either protected like normal RRs, or via a DS from a zone "higher" up the tree
+ *            DS RRs are protected like normal RRs
+ *
+ * Example chain:
+ *            Normal RR → RRSIG/DNSKEY+ → DS → RRSIG/DNSKEY+ → DS → ... → DS → RRSIG/DNSKEY+ → DS
+ */
+
+static bool dnssec_algorithm_supported(int algorithm) {
+        return IN_SET(algorithm, DNSSEC_ALGORITHM_RSASHA1, DNSSEC_ALGORITHM_RSASHA256, DNSSEC_ALGORITHM_RSASHA512);
+}
+
+static bool dnssec_digest_supported(int digest) {
+        return IN_SET(digest, DNSSEC_DIGEST_SHA1, DNSSEC_DIGEST_SHA256);
+}
+
+uint16_t dnssec_keytag(DnsResourceRecord *dnskey) {
+        const uint8_t *p;
+        uint32_t sum;
+        size_t i;
+
+        /* The algorithm from RFC 4034, Appendix B. */
+
+        assert(dnskey);
+        assert(dnskey->key->type == DNS_TYPE_DNSKEY);
+
+        sum = (uint32_t) dnskey->dnskey.flags +
+                ((((uint32_t) dnskey->dnskey.protocol) << 8) + (uint32_t) dnskey->dnskey.algorithm);
+
+        p = dnskey->dnskey.key;
+
+        for (i = 0; i < dnskey->dnskey.key_size; i++)
+                sum += (i & 1) == 0 ? (uint32_t) p[i] << 8 : (uint32_t) p[i];
+
+        sum += (sum >> 16) & UINT32_C(0xFFFF);
+
+        return sum & UINT32_C(0xFFFF);
+}
+
+static int rr_compare(const void *a, const void *b) {
+        DnsResourceRecord **x = (DnsResourceRecord**) a, **y = (DnsResourceRecord**) b;
+        size_t m;
+        int r;
+
+        /* Let's order the RRs according to RFC 4034, Section 6.3 */
+
+        assert(x);
+        assert(*x);
+        assert((*x)->wire_format);
+        assert(y);
+        assert(*y);
+        assert((*y)->wire_format);
+
+        m = MIN((*x)->wire_format_size, (*y)->wire_format_size);
+
+        r = memcmp((*x)->wire_format, (*y)->wire_format, m);
+        if (r != 0)
+                return r;
+
+        if ((*x)->wire_format_size < (*y)->wire_format_size)
+                return -1;
+        else if ((*x)->wire_format_size > (*y)->wire_format_size)
+                return 1;
+
+        return 0;
+}
+
+static int dnssec_rsa_verify(
+                const char *hash_algorithm,
+                const void *signature, size_t signature_size,
+                const void *data, size_t data_size,
+                const void *exponent, size_t exponent_size,
+                const void *modulus, size_t modulus_size) {
+
+        gcry_sexp_t public_key_sexp = NULL, data_sexp = NULL, signature_sexp = NULL;
+        gcry_mpi_t n = NULL, e = NULL, s = NULL;
+        gcry_error_t ge;
+        int r;
+
+        assert(hash_algorithm);
+
+        ge = gcry_mpi_scan(&s, GCRYMPI_FMT_USG, signature, signature_size, NULL);
+        if (ge != 0) {
+                r = -EIO;
+                goto finish;
+        }
+
+        ge = gcry_mpi_scan(&e, GCRYMPI_FMT_USG, exponent, exponent_size, NULL);
+        if (ge != 0) {
+                r = -EIO;
+                goto finish;
+        }
+
+        ge = gcry_mpi_scan(&n, GCRYMPI_FMT_USG, modulus, modulus_size, NULL);
+        if (ge != 0) {
+                r = -EIO;
+                goto finish;
+        }
+
+        ge = gcry_sexp_build(&signature_sexp,
+                             NULL,
+                             "(sig-val (rsa (s %m)))",
+                             s);
+
+        if (ge != 0) {
+                r = -EIO;
+                goto finish;
+        }
+
+        ge = gcry_sexp_build(&data_sexp,
+                             NULL,
+                             "(data (flags pkcs1) (hash %s %b))",
+                             hash_algorithm,
+                             (int) data_size,
+                             data);
+        if (ge != 0) {
+                r = -EIO;
+                goto finish;
+        }
+
+        ge = gcry_sexp_build(&public_key_sexp,
+                             NULL,
+                             "(public-key (rsa (n %m) (e %m)))",
+                             n,
+                             e);
+        if (ge != 0) {
+                r = -EIO;
+                goto finish;
+        }
+
+        ge = gcry_pk_verify(signature_sexp, data_sexp, public_key_sexp);
+        if (ge == GPG_ERR_BAD_SIGNATURE)
+                r = 0;
+        else if (ge != 0)
+                r = -EIO;
+        else
+                r = 1;
+
+finish:
+        if (e)
+                gcry_mpi_release(e);
+        if (n)
+                gcry_mpi_release(n);
+        if (s)
+                gcry_mpi_release(s);
+
+        if (public_key_sexp)
+                gcry_sexp_release(public_key_sexp);
+        if (signature_sexp)
+                gcry_sexp_release(signature_sexp);
+        if (data_sexp)
+                gcry_sexp_release(data_sexp);
+
+        return r;
+}
+
+static void md_add_uint8(gcry_md_hd_t md, uint8_t v) {
+        gcry_md_write(md, &v, sizeof(v));
+}
+
+static void md_add_uint16(gcry_md_hd_t md, uint16_t v) {
+        v = htobe16(v);
+        gcry_md_write(md, &v, sizeof(v));
+}
+
+static void md_add_uint32(gcry_md_hd_t md, uint32_t v) {
+        v = htobe32(v);
+        gcry_md_write(md, &v, sizeof(v));
+}
+
+int dnssec_verify_rrset(DnsAnswer *a, DnsResourceKey *key, DnsResourceRecord *rrsig, DnsResourceRecord *dnskey) {
+        uint8_t wire_format_name[DNS_WIRE_FOMAT_HOSTNAME_MAX];
+        size_t exponent_size, modulus_size, hash_size;
+        void *exponent, *modulus, *hash;
+        DnsResourceRecord **list, *rr;
+        gcry_md_hd_t md = NULL;
+        size_t k, n = 0;
+        int r;
+
+        assert(key);
+        assert(rrsig);
+        assert(dnskey);
+
+        /* Verifies the the RRSet matching the specified "key" in "a",
+         * using the signature "rrsig" and the key "dnskey". It's
+         * assumed the RRSIG and DNSKEY match. */
+
+        if (!dnssec_algorithm_supported(rrsig->rrsig.algorithm))
+                return -EOPNOTSUPP;
+
+        if (a->n_rrs > VERIFY_RRS_MAX)
+                return -E2BIG;
+
+        /* Collect all relevant RRs in a single array, so that we can look at the RRset */
+        list = newa(DnsResourceRecord *, a->n_rrs);
+
+        DNS_ANSWER_FOREACH(rr, a) {
+                r = dns_resource_key_equal(key, rr->key);
+                if (r < 0)
+                        return r;
+                if (r == 0)
+                        continue;
+
+                /* We need the wire format for ordering, and digest calculation */
+                r = dns_resource_record_to_wire_format(rr, true);
+                if (r < 0)
+                        return r;
+
+                list[n++] = rr;
+        }
+
+        if (n <= 0)
+                return -ENODATA;
+
+        /* Bring the RRs into canonical order */
+        qsort_safe(list, n, sizeof(DnsResourceRecord), rr_compare);
+
+        /* OK, the RRs are now in canonical order. Let's calculate the digest */
+        switch (rrsig->rrsig.algorithm) {
+
+        case DNSSEC_ALGORITHM_RSASHA1:
+                gcry_md_open(&md, GCRY_MD_SHA1, 0);
+                hash_size = 20;
+                break;
+
+        case DNSSEC_ALGORITHM_RSASHA256:
+                gcry_md_open(&md, GCRY_MD_SHA256, 0);
+                hash_size = 32;
+                break;
+
+        case DNSSEC_ALGORITHM_RSASHA512:
+                gcry_md_open(&md, GCRY_MD_SHA512, 0);
+                hash_size = 64;
+                break;
+
+        default:
+                assert_not_reached("Unknown digest");
+        }
+
+        if (!md)
+                return -EIO;
+
+        md_add_uint16(md, rrsig->rrsig.type_covered);
+        md_add_uint8(md, rrsig->rrsig.algorithm);
+        md_add_uint8(md, rrsig->rrsig.labels);
+        md_add_uint32(md, rrsig->rrsig.original_ttl);
+        md_add_uint32(md, rrsig->rrsig.expiration);
+        md_add_uint32(md, rrsig->rrsig.inception);
+        md_add_uint16(md, rrsig->rrsig.key_tag);
+
+        r = dns_name_to_wire_format(rrsig->rrsig.signer, wire_format_name, sizeof(wire_format_name), true);
+        if (r < 0)
+                goto finish;
+        gcry_md_write(md, wire_format_name, r);
+
+        for (k = 0; k < n; k++) {
+                size_t l;
+                rr = list[k];
+
+                r = dns_name_to_wire_format(DNS_RESOURCE_KEY_NAME(rr->key), wire_format_name, sizeof(wire_format_name), true);
+                if (r < 0)
+                        goto finish;
+                gcry_md_write(md, wire_format_name, r);
+
+                md_add_uint16(md, rr->key->type);
+                md_add_uint16(md, rr->key->class);
+                md_add_uint32(md, rrsig->rrsig.original_ttl);
+
+                assert(rr->wire_format_rdata_offset <= rr->wire_format_size);
+                l = rr->wire_format_size - rr->wire_format_rdata_offset;
+                assert(l <= 0xFFFF);
+
+                md_add_uint16(md, (uint16_t) l);
+                gcry_md_write(md, (uint8_t*) rr->wire_format + rr->wire_format_rdata_offset, l);
+        }
+
+        hash = gcry_md_read(md, 0);
+        if (!hash) {
+                r = -EIO;
+                goto finish;
+        }
+
+        if (*(uint8_t*) dnskey->dnskey.key == 0) {
+                /* exponent is > 255 bytes long */
+
+                exponent = (uint8_t*) dnskey->dnskey.key + 3;
+                exponent_size =
+                        ((size_t) (((uint8_t*) dnskey->dnskey.key)[0]) << 8) |
+                        ((size_t) ((uint8_t*) dnskey->dnskey.key)[1]);
+
+                if (exponent_size < 256) {
+                        r = -EINVAL;
+                        goto finish;
+                }
+
+                if (3 + exponent_size >= dnskey->dnskey.key_size) {
+                        r = -EINVAL;
+                        goto finish;
+                }
+
+                modulus = (uint8_t*) dnskey->dnskey.key + 3 + exponent_size;
+                modulus_size = dnskey->dnskey.key_size - 3 - exponent_size;
+
+        } else {
+                /* exponent is <= 255 bytes long */
+
+                exponent = (uint8_t*) dnskey->dnskey.key + 1;
+                exponent_size = (size_t) ((uint8_t*) dnskey->dnskey.key)[0];
+
+                if (exponent_size <= 0) {
+                        r = -EINVAL;
+                        goto finish;
+                }
+
+                if (1 + exponent_size >= dnskey->dnskey.key_size) {
+                        r = -EINVAL;
+                        goto finish;
+                }
+
+                modulus = (uint8_t*) dnskey->dnskey.key + 1 + exponent_size;
+                modulus_size = dnskey->dnskey.key_size - 1 - exponent_size;
+        }
+
+        r = dnssec_rsa_verify(
+                        gcry_md_algo_name(gcry_md_get_algo(md)),
+                        rrsig->rrsig.signature, rrsig->rrsig.signature_size,
+                        hash, hash_size,
+                        exponent, exponent_size,
+                        modulus, modulus_size);
+        if (r < 0)
+                goto finish;
+
+        r = r ? DNSSEC_VERIFIED : DNSSEC_INVALID;
+
+finish:
+        gcry_md_close(md);
+        return r;
+}
+
+int dnssec_rrsig_match_dnskey(DnsResourceRecord *rrsig, DnsResourceRecord *dnskey) {
+
+        assert(rrsig);
+        assert(dnskey);
+
+        /* Checks if the specified DNSKEY RR matches the key used for
+         * the signature in the specified RRSIG RR */
+
+        if (rrsig->key->type != DNS_TYPE_RRSIG)
+                return -EINVAL;
+
+        if (dnskey->key->type != DNS_TYPE_DNSKEY)
+                return 0;
+        if (dnskey->key->class != rrsig->key->class)
+                return 0;
+        if ((dnskey->dnskey.flags & DNSKEY_FLAG_ZONE_KEY) == 0)
+                return 0;
+        if (dnskey->dnskey.protocol != 3)
+                return 0;
+        if (dnskey->dnskey.algorithm != rrsig->rrsig.algorithm)
+                return 0;
+
+        if (dnssec_keytag(dnskey) != rrsig->rrsig.key_tag)
+                return 0;
+
+        return dns_name_equal(DNS_RESOURCE_KEY_NAME(dnskey->key), DNS_RESOURCE_KEY_NAME(rrsig->key));
+}
+
+int dnssec_key_match_rrsig(DnsResourceKey *key, DnsResourceRecord *rrsig) {
+        assert(key);
+        assert(rrsig);
+
+        /* Checks if the specified RRSIG RR protects the RRSet of the specified RR key. */
+
+        if (rrsig->key->type != DNS_TYPE_RRSIG)
+                return 0;
+        if (rrsig->key->class != key->class)
+                return 0;
+        if (rrsig->rrsig.type_covered != key->type)
+                return 0;
+
+        return dns_name_equal(DNS_RESOURCE_KEY_NAME(rrsig->key), DNS_RESOURCE_KEY_NAME(key));
+}
+
+int dnssec_verify_rrset_search(DnsAnswer *a, DnsResourceKey *key, DnsAnswer *validated_dnskeys) {
+        bool found_rrsig = false, found_dnskey = false;
+        DnsResourceRecord *rrsig;
+        int r;
+
+        assert(key);
+
+        /* Verifies all RRs from "a" that match the key "key", against DNSKEY RRs in "validated_dnskeys" */
+
+        if (!a || a->n_rrs <= 0)
+                return -ENODATA;
+
+        /* Iterate through each RRSIG RR. */
+        DNS_ANSWER_FOREACH(rrsig, a) {
+                DnsResourceRecord *dnskey;
+
+                r = dnssec_key_match_rrsig(key, rrsig);
+                if (r < 0)
+                        return r;
+                if (r == 0)
+                        continue;
+
+                found_rrsig = true;
+
+                DNS_ANSWER_FOREACH(dnskey, validated_dnskeys) {
+
+                        r = dnssec_rrsig_match_dnskey(rrsig, dnskey);
+                        if (r < 0)
+                                return r;
+                        if (r == 0)
+                                continue;
+
+                        found_dnskey = true;
+
+                        /* Yay, we found a matching RRSIG with a matching
+                         * DNSKEY, awesome. Now let's verify all entries of
+                         * the RRSet against the RRSIG and DNSKEY
+                         * combination. */
+
+                        r = dnssec_verify_rrset(a, key, rrsig, dnskey);
+                        if (r < 0 && r != EOPNOTSUPP)
+                                return r;
+                        if (r == DNSSEC_VERIFIED)
+                                return DNSSEC_VERIFIED;
+
+                        /* If the signature is invalid, or done using
+                           an unsupported algorithm, let's try another
+                           key and/or signature. After all they
+                           key_tags and stuff are not unique, and
+                           might be shared by multiple keys. */
+                }
+        }
+
+        if (found_dnskey)
+                return DNSSEC_INVALID;
+
+        if (found_rrsig)
+                return DNSSEC_MISSING_KEY;
+
+        return DNSSEC_NO_SIGNATURE;
+}
+
+int dnssec_canonicalize(const char *n, char *buffer, size_t buffer_max) {
+        _cleanup_free_ char *s = NULL;
+        size_t c = 0;
+        int r;
+
+        /* Converts the specified hostname into DNSSEC canonicalized
+         * form. */
+
+        if (buffer_max < 2)
+                return -ENOBUFS;
+
+        for (;;) {
+                size_t i;
+
+                r = dns_label_unescape(&n, buffer, buffer_max);
+                if (r < 0)
+                        return r;
+                if (r == 0)
+                        break;
+                if (r > 0) {
+                        int k;
+
+                        /* DNSSEC validation is always done on the ASCII version of the label */
+                        k = dns_label_apply_idna(buffer, r, buffer, buffer_max);
+                        if (k < 0)
+                                return k;
+                        if (k > 0)
+                                r = k;
+                }
+
+                if (buffer_max < (size_t) r + 2)
+                        return -ENOBUFS;
+
+                /* The DNSSEC canonical form is not clear on what to
+                 * do with dots appearing in labels, the way DNS-SD
+                 * does it. Refuse it for now. */
+
+                if (memchr(buffer, '.', r))
+                        return -EINVAL;
+
+                for (i = 0; i < (size_t) r; i ++) {
+                        if (buffer[i] >= 'A' && buffer[i] <= 'Z')
+                                buffer[i] = buffer[i] - 'A' + 'a';
+                }
+
+                buffer[r] = '.';
+
+                buffer += r + 1;
+                c += r + 1;
+
+                buffer_max -= r + 1;
+        }
+
+        if (c <= 0) {
+                /* Not even a single label: this is the root domain name */
+
+                assert(buffer_max > 2);
+                buffer[0] = '.';
+                buffer[1] = 0;
+
+                return 1;
+        }
+
+        return (int) c;
+}
+
+int dnssec_verify_dnskey(DnsResourceRecord *dnskey, DnsResourceRecord *ds) {
+        gcry_md_hd_t md = NULL;
+        char owner_name[DNSSEC_CANONICAL_HOSTNAME_MAX];
+        void *result;
+        int r;
+
+        assert(dnskey);
+        assert(ds);
+
+        /* Implements DNSKEY verification by a DS, according to RFC 4035, section 5.2 */
+
+        if (dnskey->key->type != DNS_TYPE_DNSKEY)
+                return -EINVAL;
+        if (ds->key->type != DNS_TYPE_DS)
+                return -EINVAL;
+        if ((dnskey->dnskey.flags & DNSKEY_FLAG_ZONE_KEY) == 0)
+                return -EKEYREJECTED;
+        if (dnskey->dnskey.protocol != 3)
+                return -EKEYREJECTED;
+
+        if (!dnssec_algorithm_supported(dnskey->dnskey.algorithm))
+                return -EOPNOTSUPP;
+        if (!dnssec_digest_supported(ds->ds.digest_type))
+                return -EOPNOTSUPP;
+
+        if (dnskey->dnskey.algorithm != ds->ds.algorithm)
+                return 0;
+        if (dnssec_keytag(dnskey) != ds->ds.key_tag)
+                return 0;
+
+        switch (ds->ds.digest_type) {
+
+        case DNSSEC_DIGEST_SHA1:
+
+                if (ds->ds.digest_size != 20)
+                        return 0;
+
+                gcry_md_open(&md, GCRY_MD_SHA1, 0);
+                break;
+
+        case DNSSEC_DIGEST_SHA256:
+
+                if (ds->ds.digest_size != 32)
+                        return 0;
+
+                gcry_md_open(&md, GCRY_MD_SHA256, 0);
+                break;
+
+        default:
+                assert_not_reached("Unknown digest");
+        }
+
+        if (!md)
+                return -EIO;
+
+        r = dnssec_canonicalize(DNS_RESOURCE_KEY_NAME(dnskey->key), owner_name, sizeof(owner_name));
+        if (r < 0)
+                goto finish;
+
+        gcry_md_write(md, owner_name, r);
+        md_add_uint16(md, dnskey->dnskey.flags);
+        md_add_uint8(md, dnskey->dnskey.protocol);
+        md_add_uint8(md, dnskey->dnskey.algorithm);
+        gcry_md_write(md, dnskey->dnskey.key, dnskey->dnskey.key_size);
+
+        result = gcry_md_read(md, 0);
+        if (!result) {
+                r = -EIO;
+                goto finish;
+        }
+
+        r = memcmp(result, ds->ds.digest, ds->ds.digest_size) != 0;
+
+finish:
+        gcry_md_close(md);
+        return r;
+}
diff --git a/src/resolve/resolved-dns-dnssec.h b/src/resolve/resolved-dns-dnssec.h
new file mode 100644
index 0000000000..56f0aec437
--- /dev/null
+++ b/src/resolve/resolved-dns-dnssec.h
@@ -0,0 +1,48 @@
+/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
+
+#pragma once
+
+/***
+  This file is part of systemd.
+
+  Copyright 2015 Lennart Poettering
+
+  systemd is free software; you can redistribute it and/or modify it
+  under the terms of the GNU Lesser General Public License as published by
+  the Free Software Foundation; either version 2.1 of the License, or
+  (at your option) any later version.
+
+  systemd is distributed in the hope that it will be useful, but
+  WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+  Lesser General Public License for more details.
+
+  You should have received a copy of the GNU Lesser General Public License
+  along with systemd; If not, see <http://www.gnu.org/licenses/>.
+***/
+
+#include "dns-domain.h"
+#include "resolved-dns-answer.h"
+#include "resolved-dns-rr.h"
+
+enum {
+        DNSSEC_VERIFIED,
+        DNSSEC_INVALID,
+        DNSSEC_NO_SIGNATURE,
+        DNSSEC_MISSING_KEY,
+};
+
+
+#define DNSSEC_CANONICAL_HOSTNAME_MAX (DNS_HOSTNAME_MAX + 2)
+
+int dnssec_rrsig_match_dnskey(DnsResourceRecord *rrsig, DnsResourceRecord *dnskey);
+int dnssec_key_match_rrsig(DnsResourceKey *key, DnsResourceRecord *rrsig);
+
+int dnssec_verify_rrset(DnsAnswer *answer, DnsResourceKey *key, DnsResourceRecord *rrsig, DnsResourceRecord *dnskey);
+int dnssec_verify_rrset_search(DnsAnswer *a, DnsResourceKey *key, DnsAnswer *validated_dnskeys);
+
+int dnssec_verify_dnskey(DnsResourceRecord *dnskey, DnsResourceRecord *ds);
+
+uint16_t dnssec_keytag(DnsResourceRecord *dnskey);
+
+int dnssec_canonicalize(const char *n, char *buffer, size_t buffer_max);
diff --git a/src/resolve/test-dnssec.c b/src/resolve/test-dnssec.c
new file mode 100644
index 0000000000..8cab025426
--- /dev/null
+++ b/src/resolve/test-dnssec.c
@@ -0,0 +1,217 @@
+/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
+
+/***
+  This file is part of systemd.
+
+  Copyright 2015 Lennart Poettering
+
+  systemd is free software; you can redistribute it and/or modify it
+  under the terms of the GNU Lesser General Public License as published by
+  the Free Software Foundation; either version 2.1 of the License, or
+  (at your option) any later version.
+
+  systemd is distributed in the hope that it will be useful, but
+  WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+  Lesser General Public License for more details.
+
+  You should have received a copy of the GNU Lesser General Public License
+  along with systemd; If not, see <http://www.gnu.org/licenses/>.
+***/
+
+#include <arpa/inet.h>
+#include <netinet/in.h>
+#include <sys/socket.h>
+
+#include "alloc-util.h"
+#include "resolved-dns-dnssec.h"
+#include "resolved-dns-packet.h"
+#include "resolved-dns-rr.h"
+#include "string-util.h"
+
+static void test_dnssec_verify_rrset(void) {
+
+        static const uint8_t signature_blob[] = {
+                0x7f, 0x79, 0xdd, 0x5e, 0x89, 0x79, 0x18, 0xd0, 0x34, 0x86, 0x8c, 0x72, 0x77, 0x75, 0x48, 0x4d,
+                0xc3, 0x7d, 0x38, 0x04, 0xab, 0xcd, 0x9e, 0x4c, 0x82, 0xb0, 0x92, 0xca, 0xe9, 0x66, 0xe9, 0x6e,
+                0x47, 0xc7, 0x68, 0x8c, 0x94, 0xf6, 0x69, 0xcb, 0x75, 0x94, 0xe6, 0x30, 0xa6, 0xfb, 0x68, 0x64,
+                0x96, 0x1a, 0x84, 0xe1, 0xdc, 0x16, 0x4c, 0x83, 0x6c, 0x44, 0xf2, 0x74, 0x4d, 0x74, 0x79, 0x8f,
+                0xf3, 0xf4, 0x63, 0x0d, 0xef, 0x5a, 0xe7, 0xe2, 0xfd, 0xf2, 0x2b, 0x38, 0x7c, 0x28, 0x96, 0x9d,
+                0xb6, 0xcd, 0x5c, 0x3b, 0x57, 0xe2, 0x24, 0x78, 0x65, 0xd0, 0x9e, 0x77, 0x83, 0x09, 0x6c, 0xff,
+                0x3d, 0x52, 0x3f, 0x6e, 0xd1, 0xed, 0x2e, 0xf9, 0xee, 0x8e, 0xa6, 0xbe, 0x9a, 0xa8, 0x87, 0x76,
+                0xd8, 0x77, 0xcc, 0x96, 0xa0, 0x98, 0xa1, 0xd1, 0x68, 0x09, 0x43, 0xcf, 0x56, 0xd9, 0xd1, 0x66,
+        };
+
+        static const uint8_t dnskey_blob[] = {
+                0x03, 0x01, 0x00, 0x01, 0x9b, 0x49, 0x9b, 0xc1, 0xf9, 0x9a, 0xe0, 0x4e, 0xcf, 0xcb, 0x14, 0x45,
+                0x2e, 0xc9, 0xf9, 0x74, 0xa7, 0x18, 0xb5, 0xf3, 0xde, 0x39, 0x49, 0xdf, 0x63, 0x33, 0x97, 0x52,
+                0xe0, 0x8e, 0xac, 0x50, 0x30, 0x8e, 0x09, 0xd5, 0x24, 0x3d, 0x26, 0xa4, 0x49, 0x37, 0x2b, 0xb0,
+                0x6b, 0x1b, 0xdf, 0xde, 0x85, 0x83, 0xcb, 0x22, 0x4e, 0x60, 0x0a, 0x91, 0x1a, 0x1f, 0xc5, 0x40,
+                0xb1, 0xc3, 0x15, 0xc1, 0x54, 0x77, 0x86, 0x65, 0x53, 0xec, 0x10, 0x90, 0x0c, 0x91, 0x00, 0x5e,
+                0x15, 0xdc, 0x08, 0x02, 0x4c, 0x8c, 0x0d, 0xc0, 0xac, 0x6e, 0xc4, 0x3e, 0x1b, 0x80, 0x19, 0xe4,
+                0xf7, 0x5f, 0x77, 0x51, 0x06, 0x87, 0x61, 0xde, 0xa2, 0x18, 0x0f, 0x40, 0x8b, 0x79, 0x72, 0xfa,
+                0x8d, 0x1a, 0x44, 0x47, 0x0d, 0x8e, 0x3a, 0x2d, 0xc7, 0x39, 0xbf, 0x56, 0x28, 0x97, 0xd9, 0x20,
+                0x4f, 0x00, 0x51, 0x3b,
+        };
+
+        _cleanup_(dns_resource_record_unrefp) DnsResourceRecord *a = NULL, *rrsig = NULL, *dnskey = NULL;
+        _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL;
+        _cleanup_free_ char *x = NULL, *y = NULL, *z = NULL;
+
+        a = dns_resource_record_new_full(DNS_CLASS_IN, DNS_TYPE_A, "nAsA.gov");
+        assert_se(a);
+
+        a->a.in_addr.s_addr = inet_addr("52.0.14.116");
+
+        assert_se(dns_resource_record_to_string(a, &x) >= 0);
+        log_info("A: %s", x);
+
+        rrsig = dns_resource_record_new_full(DNS_CLASS_IN, DNS_TYPE_RRSIG, "NaSa.GOV.");
+        assert_se(rrsig);
+
+        rrsig->rrsig.type_covered = DNS_TYPE_A;
+        rrsig->rrsig.algorithm = DNSSEC_ALGORITHM_RSASHA256;
+        rrsig->rrsig.labels = 2;
+        rrsig->rrsig.original_ttl = 600;
+        rrsig->rrsig.expiration = 0x5683135c;
+        rrsig->rrsig.inception = 0x565b7da8;
+        rrsig->rrsig.key_tag = 63876;
+        rrsig->rrsig.signer = strdup("Nasa.Gov.");
+        assert_se(rrsig->rrsig.signer);
+        rrsig->rrsig.signature_size = sizeof(signature_blob);
+        rrsig->rrsig.signature = memdup(signature_blob, rrsig->rrsig.signature_size);
+        assert_se(rrsig->rrsig.signature);
+
+        assert_se(dns_resource_record_to_string(rrsig, &y) >= 0);
+        log_info("RRSIG: %s", y);
+
+        dnskey = dns_resource_record_new_full(DNS_CLASS_IN, DNS_TYPE_DNSKEY, "nASA.gOV");
+        assert_se(dnskey);
+
+        dnskey->dnskey.flags = 256;
+        dnskey->dnskey.protocol = 3;
+        dnskey->dnskey.algorithm = DNSSEC_ALGORITHM_RSASHA256;
+        dnskey->dnskey.key_size = sizeof(dnskey_blob);
+        dnskey->dnskey.key = memdup(dnskey_blob, sizeof(dnskey_blob));
+        assert_se(dnskey->dnskey.key);
+
+        assert_se(dns_resource_record_to_string(dnskey, &z) >= 0);
+        log_info("DNSKEY: %s", z);
+        log_info("DNSKEY keytag: %u", dnssec_keytag(dnskey));
+
+        assert_se(dnssec_key_match_rrsig(a->key, rrsig) > 0);
+        assert_se(dnssec_rrsig_match_dnskey(rrsig, dnskey) > 0);
+
+        answer = dns_answer_new(1);
+        assert_se(answer);
+        assert_se(dns_answer_add(answer, a, 0) >= 0);
+
+        assert_se(dnssec_verify_rrset(answer, a->key, rrsig, dnskey) == DNSSEC_VERIFIED);
+}
+
+static void test_dnssec_verify_dns_key(void) {
+
+        static const uint8_t ds1_fprint[] = {
+                0x46, 0x8B, 0xC8, 0xDD, 0xC7, 0xE8, 0x27, 0x03, 0x40, 0xBB, 0x8A, 0x1F, 0x3B, 0x2E, 0x45, 0x9D,
+                0x80, 0x67, 0x14, 0x01,
+        };
+        static const uint8_t ds2_fprint[] = {
+                0x8A, 0xEE, 0x80, 0x47, 0x05, 0x5F, 0x83, 0xD1, 0x48, 0xBA, 0x8F, 0xF6, 0xDD, 0xA7, 0x60, 0xCE,
+                0x94, 0xF7, 0xC7, 0x5E, 0x52, 0x4C, 0xF2, 0xE9, 0x50, 0xB9, 0x2E, 0xCB, 0xEF, 0x96, 0xB9, 0x98,
+        };
+        static const uint8_t dnskey_blob[] = {
+                0x03, 0x01, 0x00, 0x01, 0xa8, 0x12, 0xda, 0x4f, 0xd2, 0x7d, 0x54, 0x14, 0x0e, 0xcc, 0x5b, 0x5e,
+                0x45, 0x9c, 0x96, 0x98, 0xc0, 0xc0, 0x85, 0x81, 0xb1, 0x47, 0x8c, 0x7d, 0xe8, 0x39, 0x50, 0xcc,
+                0xc5, 0xd0, 0xf2, 0x00, 0x81, 0x67, 0x79, 0xf6, 0xcc, 0x9d, 0xad, 0x6c, 0xbb, 0x7b, 0x6f, 0x48,
+                0x97, 0x15, 0x1c, 0xfd, 0x0b, 0xfe, 0xd3, 0xd7, 0x7d, 0x9f, 0x81, 0x26, 0xd3, 0xc5, 0x65, 0x49,
+                0xcf, 0x46, 0x62, 0xb0, 0x55, 0x6e, 0x47, 0xc7, 0x30, 0xef, 0x51, 0xfb, 0x3e, 0xc6, 0xef, 0xde,
+                0x27, 0x3f, 0xfa, 0x57, 0x2d, 0xa7, 0x1d, 0x80, 0x46, 0x9a, 0x5f, 0x14, 0xb3, 0xb0, 0x2c, 0xbe,
+                0x72, 0xca, 0xdf, 0xb2, 0xff, 0x36, 0x5b, 0x4f, 0xec, 0x58, 0x8e, 0x8d, 0x01, 0xe9, 0xa9, 0xdf,
+                0xb5, 0x60, 0xad, 0x52, 0x4d, 0xfc, 0xa9, 0x3e, 0x8d, 0x35, 0x95, 0xb3, 0x4e, 0x0f, 0xca, 0x45,
+                0x1b, 0xf7, 0xef, 0x3a, 0x88, 0x25, 0x08, 0xc7, 0x4e, 0x06, 0xc1, 0x62, 0x1a, 0xce, 0xd8, 0x77,
+                0xbd, 0x02, 0x65, 0xf8, 0x49, 0xfb, 0xce, 0xf6, 0xa8, 0x09, 0xfc, 0xde, 0xb2, 0x09, 0x9d, 0x39,
+                0xf8, 0x63, 0x9c, 0x32, 0x42, 0x7c, 0xa0, 0x30, 0x86, 0x72, 0x7a, 0x4a, 0xc6, 0xd4, 0xb3, 0x2d,
+                0x24, 0xef, 0x96, 0x3f, 0xc2, 0xda, 0xd3, 0xf2, 0x15, 0x6f, 0xda, 0x65, 0x4b, 0x81, 0x28, 0x68,
+                0xf4, 0xfe, 0x3e, 0x71, 0x4f, 0x50, 0x96, 0x72, 0x58, 0xa1, 0x89, 0xdd, 0x01, 0x61, 0x39, 0x39,
+                0xc6, 0x76, 0xa4, 0xda, 0x02, 0x70, 0x3d, 0xc0, 0xdc, 0x8d, 0x70, 0x72, 0x04, 0x90, 0x79, 0xd4,
+                0xec, 0x65, 0xcf, 0x49, 0x35, 0x25, 0x3a, 0x14, 0x1a, 0x45, 0x20, 0xeb, 0x31, 0xaf, 0x92, 0xba,
+                0x20, 0xd3, 0xcd, 0xa7, 0x13, 0x44, 0xdc, 0xcf, 0xf0, 0x27, 0x34, 0xb9, 0xe7, 0x24, 0x6f, 0x73,
+                0xe7, 0xea, 0x77, 0x03,
+        };
+
+        _cleanup_(dns_resource_record_unrefp) DnsResourceRecord *dnskey = NULL, *ds1 = NULL, *ds2 = NULL;
+        _cleanup_free_ char *a = NULL, *b = NULL, *c = NULL;
+
+        /* The two DS RRs in effect for nasa.gov on 2015-12-01. */
+        ds1 = dns_resource_record_new_full(DNS_CLASS_IN, DNS_TYPE_DS, "nasa.gov");
+        assert_se(ds1);
+
+        ds1->ds.key_tag = 47857;
+        ds1->ds.algorithm = DNSSEC_ALGORITHM_RSASHA256;
+        ds1->ds.digest_type = DNSSEC_DIGEST_SHA1;
+        ds1->ds.digest_size = sizeof(ds1_fprint);
+        ds1->ds.digest = memdup(ds1_fprint, ds1->ds.digest_size);
+        assert_se(ds1->ds.digest);
+
+        assert_se(dns_resource_record_to_string(ds1, &a) >= 0);
+        log_info("DS1: %s", a);
+
+        ds2 = dns_resource_record_new_full(DNS_CLASS_IN, DNS_TYPE_DS, "NASA.GOV");
+        assert_se(ds2);
+
+        ds2->ds.key_tag = 47857;
+        ds2->ds.algorithm = DNSSEC_ALGORITHM_RSASHA256;
+        ds2->ds.digest_type = DNSSEC_DIGEST_SHA256;
+        ds2->ds.digest_size = sizeof(ds2_fprint);
+        ds2->ds.digest = memdup(ds2_fprint, ds2->ds.digest_size);
+        assert_se(ds2->ds.digest);
+
+        assert_se(dns_resource_record_to_string(ds2, &b) >= 0);
+        log_info("DS2: %s", b);
+
+        dnskey = dns_resource_record_new_full(DNS_CLASS_IN, DNS_TYPE_DNSKEY, "nasa.GOV");
+        assert_se(dnskey);
+
+        dnskey->dnskey.flags = 257;
+        dnskey->dnskey.protocol = 3;
+        dnskey->dnskey.algorithm = DNSSEC_ALGORITHM_RSASHA256;
+        dnskey->dnskey.key_size = sizeof(dnskey_blob);
+        dnskey->dnskey.key = memdup(dnskey_blob, sizeof(dnskey_blob));
+        assert_se(dnskey->dnskey.key);
+
+        assert_se(dns_resource_record_to_string(dnskey, &c) >= 0);
+        log_info("DNSKEY: %s", c);
+        log_info("DNSKEY keytag: %u", dnssec_keytag(dnskey));
+
+        assert_se(dnssec_verify_dnskey(dnskey, ds1) > 0);
+        assert_se(dnssec_verify_dnskey(dnskey, ds2) > 0);
+}
+
+static void test_dnssec_canonicalize_one(const char *original, const char *canonical, int r) {
+        char canonicalized[DNSSEC_CANONICAL_HOSTNAME_MAX];
+
+        assert_se(dnssec_canonicalize(original, canonicalized, sizeof(canonicalized)) == r);
+        if (r < 0)
+                return;
+
+        assert_se(streq(canonicalized, canonical));
+}
+
+static void test_dnssec_canonicalize(void) {
+        test_dnssec_canonicalize_one("", ".", 1);
+        test_dnssec_canonicalize_one(".", ".", 1);
+        test_dnssec_canonicalize_one("foo", "foo.", 4);
+        test_dnssec_canonicalize_one("foo.", "foo.", 4);
+        test_dnssec_canonicalize_one("FOO.", "foo.", 4);
+        test_dnssec_canonicalize_one("FOO.bar.", "foo.bar.", 8);
+        test_dnssec_canonicalize_one("FOO..bar.", NULL, -EINVAL);
+}
+
+int main(int argc, char*argv[]) {
+
+        test_dnssec_canonicalize();
+        test_dnssec_verify_dns_key();
+        test_dnssec_verify_rrset();
+
+        return 0;
+}
diff --git a/src/shared/dns-domain.h b/src/shared/dns-domain.h
index 17dab1da18..e48d8c6b9d 100644
--- a/src/shared/dns-domain.h
+++ b/src/shared/dns-domain.h
@@ -34,6 +34,9 @@
 /* Maximum length of a full hostname, consisting of a series of unescaped labels, and no trailing dot or NUL byte */
 #define DNS_HOSTNAME_MAX 253
 
+/* Maximum length of a full hostname, on the wire, including the final NUL byte */
+#define DNS_WIRE_FOMAT_HOSTNAME_MAX 255
+
 int dns_label_unescape(const char **name, char *dest, size_t sz);
 int dns_label_unescape_suffix(const char *name, const char **label_end, char *dest, size_t sz);
 int dns_label_escape(const char *p, size_t l, char *dest, size_t sz);