A long time ago I discovered (or likely, rediscovered) a trick to rapidly determine the number of DNSSEC secured delegations in a zone. I thought this was rather clever.
A few years later, I finally had a need to learn about the magic of HyperLogLog (as championed by my friend and Open-Xchange coworker Neil Cook). And behold, I found that my DNSSEC trick and HyperLogLog were mostly the same thing!
Before we go on, I want to thank Peter van Dijk for running tests that showed that it wasn’t the .NL zone that was wrong, but my understanding of HyperLogLog!
What is HyperLogLog?
The challenge: determine how many unique entries you have in a list with billions of entries. You need this for example if you have user cookies of site visitors, and you want to know how many unique visitors there were in a day. This is a common problem in the advertising industry.
The naive way is to sort all cookies and count how many are unique. This may require terabytes of memory though, even if we only store hashes of the cookies, for example. It might also take you more than 24 hours to study the traffic of one day!
A very special trick called HyperLogLog can give a very good estimate of the number of unique things in your list… using 1280 bytes of memory.
So how does it work?
A lot of fine words are written on HyperLogLog, and this is justified. It is a magic thing, and some maths is involved to prove that it actually works. But conceptually it is not that difficult.
Here goes. Let’s say that we have around 20 entries in our list, of which 10 are unique. Let’s also say we have a fast non-cryptographic 32-bit hash function that emits one of roughly 4.3 billion values for each entry, and we plot these hashes on a bar. We’d find the hashes of our 20 entries are distributed randomly:
So what is the average distance between the hashes if we have N unique entries? Given sufficient entries, we can be sure that this is very close to 232/N. In other words, if we know the average distance between two hashes, we know the number of unique entries.
This insight is not particularly helpful though – to know this average distance, we still have to keep track of where all the hashes are, and there might be billions. This doesn’t really solve our problem – we still need 232/8 bytes of memory for a bitmap of all hashes.
This, however, is where statistics come to our rescue. It turns out we don’t need to know the distance between two actual hashes. We simply need to pick a point and see how close the closest hash is. Conventionally, this point is at 0.
In other words, the lowest hash value on its own gives us information about the number of unique values in a list.
In the bar above, if we find the first hash at around 430 million (±232/10), this tells us it is likely there are around 10 unique entries in our list.
In this way, we only have to keep track of the lowest hash we have ever seen, and we know the number of unique entries. Neat eh?
So why does this work? Intuitively, you can see that if you have only a few unique hashes, it is pretty unlikely one of them is close to the chosen point of 0:
But if we have a ton of points, it is far more likely that a lower hash will appear:
Now – there is a pretty large element of chance in this estimate, so actual HyperLogLog doesn’t look at just one hash value, but at many of them. If you expect up to one billion unique values, one could split up the 232 hash space in 2048 subspaces, and only keep track of the lowest hash value in each of them.
It also turns out that for this to work, we don’t even need to store the actual lowest hash we find – it suffices to store the leading number of zeroes in binary representation. In other words, for the 2048 subspaces example above, if we have two hashes with binary presentations:
- 10000101111 01101001011100010101
- 11111101001 00010110000100010101
This is what this would look like, where we actually only store the last column:
| Bin (11 bits) | Lowest hash (21 bits) | Leading zeroes |
| … | … | … |
| 10000101111 | 01101001011100010101 | 1 |
| 11111101001 | 00010110000100010101 | 3 |
| … | … | … |
To get the number of unique entries, determine the harmonic mean of all those lowest hash values, and out comes a pretty precise estimate (±2%) of how many unique values there are in your list.
In this configuration, the whole HyperLogLog structure requires five bits of storage for each of the 2048 bins (enough to store the maximum of 32 — log2(2048) = 21 leading zeros), for a total of 1280 bytes. To keep track of up to a billion unique entries!
Note: This is not quite the entire story. The HLL paper contains correction factors that make all this slightly more complicated, but also more correct. Work by Google and the ETH Zurich [PDF 534 KB] offers even more precision.
Relation to DNSSEC and NSEC3
So what does all this have to do with DNSSEC?
DNSSEC signs DNS answers cryptographically. A problem is that if DNS needs to say ‘no such record’, it says this with an empty answer. So the question ‘What is the IPv6 address of www.horselesscarriage.com’ gets the answer ” to signify there is no IPv6 address. And sadly, we can’t usefully sign an empty string – since that would give a universally valid ‘no such record’ answer that could be replayed to make any domain disappear. Sad!
The initial DNSSEC solution for this problem was to sign the interval between non-existent domain names. So for example, a query for ‘www.nosuchdomain123.nl’ to the .NL servers might get as an answer ‘nothing known between nosuchdomain.nl and nosuchdomain321.nl’. And this could be signed without the risk of replay attacks being used to silence domains that did exist. Clever.
However, it was quickly pointed out that such ranges of ’empty space’ inherently also document which domain names actually DO exist. In other words, the full content of a DNSSEC-signed zone would be available for enumeration. Many European operators did not want this.
So, of course, the DNSSEC community resorted to what always saves us: a hash, more precisely a salted and iterated hash. This did not really solve the problem since it is quite easy to calculate billions of hashes and ‘walk a zone’ anyhow, but this is what we ended up with (for now).
So what does all of this have to do with HyperLogLog? Let us send a query to my favorite zone, the Dutch .NL Top Level Domain:
$ dig +dnssec +norecurs www.nosuchdomain234.nl @ns1.dns.nl
;; ->>HEADER<<- opcode: QUERY, status: NXDOMAIN, id: 58311
;; QUESTION SECTION:
;www.nosuchdomain234.nl. IN A
;; AUTHORITY SECTION:
nl. IN SOA ns1.dns.nl. hostmaster.domain-registry.nl. 2017012321 3600 600 2419200 600
qauju5pk2k5krcucblgr1l6mkvqfifbd.nl. IN NSEC3 1 1 5 A1..B1 QAUK0QHQ5P430LN1A171K6VUKGHR1UFB NS SOA TXT RRSIG DNSKEY NSEC3PARAM
a4hm8068md36206d7ga8tjin9oi4bmo8.nl. IN NSEC3 1 1 5 A1..B1 A4HNAJIO9T91U4NVVLK3RG2LHF2HGQQK NS DS RRSIG
bqhhp9r6o9uifoi974teka9hithd9tdo.nl. IN NSEC3 1 1 5 A1..B1 BQHIVE08OU9VP6JM5MM6BR0LF1TDJMT0 NS DS RRSIG
This answer tells us that ‘nosuchdomain234.nl’ doesn’t exist, and then goes on to prove that by providing three ‘NSEC3’ ranges of hashes that do not have DNSSEC data.
If we zoom in to one of these:
bqhhp9r6o9uifoi974teka9hithd9tdo IN NSEC3 1 1 5 A1.B1 BQHIVE08OU9VP6JM5MM6BR0LF1TDJMT0 NS DS RRSIG
This tells us the salt of the hash (A10222AECD6609B1), some other DNSSEC parameters, but most importantly: between base-32 encoded values bqhhp9r6o9uifoi974teka9hithd9tdo and BQHIVE08OU9VP6JM5MM6BR0LF1TDJMT0, there is nothing signed.
Note that these values are hashes, and they are therefore distributed randomly over the available hash space. And the distance between the hashes is, as with HyperLogLog, telling for the number of unique names in there.
To perform the HLL algorithm, we calculate the distance between the hashes, and determine the number of leading zeroes of this number.
In this specific case, if we look at the first 64 bits in hex, this gets us:
5ea32f b808c793f c — 5ea31ca766c27d27 = 1310a20516d5
In binary, this difference is:
0000000000000000000100110001000010100010000001010001011
0110101010000000000000000000100110001000010100010000001
010001011011010101
Or, 20 leading zeroes. For reasons explained in the HyperLogLog paper, we can add 1 to that, leading to an estimate of the .NL zone size of 2121, which is 2.09 million. At the time of measurement, the actual number was 2.57 million. Not bad!
Experimentally, if thousands of NSEC3 hash values are considered, their distances quickly provide an estimate of the number of DNSSEC delegation in the .NL zone that turns out to be accurate to 1%.
dnssecmeasure tool
To perform this calculation, clone the ‘dnssecmeasure’ branch of PowerDNS from https://github.com/ahupowerdns/pdns.git and run:
$ ./dnssecmeasure nl 4096
Will send 4096 queries to: nl1.dnsnode.net sns-pb.isc.org ns-nl.nic.fr
ns3.dns.nl ns1.dns.nl ns2.dns.nl ns4.dns.nl ns5.dns.nl
194.146.106.42 2001:67c:1010:10::53 2a00:d78:0:102:193:176:144:5
213.154.241.85 95.142.99.212 2001:7b8:606::85 193.176.144.5
2a00:1188:5::212 194.0.28.53 2001:678:2c:0:194:0:28:53
2001:610:0:800d::10 194.171.17.10 192.5.4.1 2001:660:3005:1::1:2
192.93.0.4 2001:500:2e::1
Poisson size 2.55888e+06
This tool opens a TCP/IP connection to each of the IPv4 and IPv6 addresses that host a zone. It then sends random questions to all these connections until it has received the requested number of answers (4096 by default).
It then divides the the totally available hash length (2160 bits currently) by the average ‘width’ of the NSEC3 records. Given that the NSEC3 hash lengths are likely Poisson distributed, this is a very robust estimator of the total amount of signed names in a zone.
Most zones can be measured this way in under a second.
NOTE: Does not yet support NSEC signed zones!
Determining number of signed delegations by eye
As a party trick, this estimation can be performed by eye – if a zone typically has three to four overlapping first characters in NSEC3 hashes, this corresponds to at least 15 to 20 bits of overlap (because of base32). Add 1 and you can quickly state a zone likely has ‘in the order of a million signed delegations’.
To further impress your friends, see how often you spot four overlapping base32 digits and round up accordingly for more precision.
Original post appeared on Bert Hubert’s blog ds9a.
Burt Hubert is a software developer and founder of PowerDNS
The views expressed by the authors of this blog are their own and do not necessarily reflect the views of APNIC. Please note a Code of Conduct applies to this blog.