• Goal: offline signing of NXDOMAIN responses
• Sort owner names in canonical order
• NSEC: sign proof of non-existence

ftp   IN  NSEC   mail

• New requirement: hide names
• NSEC3: hash names before sorting

3a45  IN  NSEC3  78a1

• “There is no name with \(\text{3a45} < h(\text{name}) < \text{78a1}\)”
• 31 top-level domains use NSEC, 81 use NSEC3

def nsec3(name, iterations, salt):
    digest = hashlib.sha1(name + salt).digest()
    for i in xrange(0, iterations): # for(i=0; i < iterations; i++)
        digest = hashlib.sha1(digest + salt).digest()
    return digest

• name: label-encoded FQDN (RFC 1035 Section 3.1)
• foo.example.org. = \x03foo\x07example\x03org\x00
• iterations: SHA-1 operations – 1
• 0 iterations = 1 SHA-1 operation
• 10 iterations = 11 SHA-1 operations
• salt: any binary blob 0–255 bytes
• hexadecimal presentation format

• Name+Salt ≤ 55 bytes will fit into one SHA-1 block
• Each SHA-1 block increases the hashing work
• Maximum: 255 bytes name + 255 bytes salt + padding ⇨ 9 blocks
• Hash value is 20 bytes (32 bytes encoded as Base32hex)
• No known pre-image attacks on SHA-1
• collision attacks not relevant for common NSEC3 usage

• Crawl NSEC3 hashes implemented
• Break NSEC3 hashes
• Brute-force attack implemented
• Markov chains implemented
• Dictionary attack work in progress
• Rainbow tables no plans
  (won't work once everybody starts changing the salt regularly)

1. Calculate hash value of random name
2. Check whether hash value falls into known NSEC3 range
• If yes, go back to step 1 and try again
3. Send query to server, receive NXDOMAIN and new NSEC3 range
4. Repeat until NSEC3 chain is complete

• Download \(n\) NSEC3 ranges with \(n\) online queries
• For large zones, finding the last NSEC3 ranges can take a while
• We send one query to a zone at a time
• Host: crawler.vs.uni-duisburg-essen.de.
• IPv4: 134.91.78.159 IPv6: 2001:638:501:8efc::159

1. Enumerate all names up to a certain length
• aaa, aab, aac, aad, ..., aa8, aa9, aba, abc, ...
2. Hash name
3. Check if hash is in known-hash array
• Efficient approach: binary search with \(O \left ( log(n) \right )\)
• Challenge on GPU, global memory access is slow
• Bloom filter before binary search for probabilistic test: 300% speedup

• Limited feasiblity
• 9 characters: ~1 week
• 10 characters: ~37 weeks

• General idea: characters in natural languages follow hidden markov models
• Probability of a certain character in a word depends on its predecessors
• Example for the English language: 'th', 'he', 'in' and 'er' are very common
• Use a data set to calculate character transition probabilities
• Names from brute-force attack for example
• Advantage: TLD-specific probabilities are considered
• Use efficient algorithm which enumerates highly probable names
• Ported Simon Marechal's John the Ripper Markov patch to OpenCL
• Not exhaustive: omits improbable names

• Written in Python and OpenCL
• OpenCL runs on CPU or GPU
• AMD/ATI graphics card: runs best
• NVIDIA graphics card: runs decently
• CPU with AMD APP SDK: runs
• http://dnssec.vs.uni-due.de/nsec3

svn co https://www.vs.uni-due.de/svn/dnssec/nsec3breaker/trunk

(install dnspython, numpy and pyopencl, see HOWTO.txt)

python nsec3breaker.py -o         # Desktop GPU: set also -c 0.01
python client.py -r someusername  # register at server
python client.py -j               # fetch and compute jobs

• Brute-force attack performance
• Radeon HD 7970: 1800 MHash/s
  (360 €)
• Radeon HD 6970: 550 MHash/s
  (200 €)
• 4 cores (out of 12) Intel Xeon X5650 2,67 GHz: 17 MHash/s
• Number of crawled hashes so far: 5,6 M
• Top 3: ch. (1,46 M), cz. (1,03 M), nl. (1,45 M)
• Number of broken names so far: 1,6 M
• Top 3: ch. (481 k), cz. (428 k), nl. (390 k)

• Finish dictionary attack
• create dictionary from PTR reverse lookups
• Automatic scheduling
• crawl unknown zones
• distributed breaking of unknown hashes
• Goal: full copy of all DNSSEC zones
• for monitoring and further research
• Join the distributed computing project
• http://dnssec.vs.uni-due.de/nsec3
• Question to you: publish zone data?