{"id":75,"date":"2019-02-09T14:00:20","date_gmt":"2019-02-09T14:00:20","guid":{"rendered":"https:\/\/blog.erbbysam.com\/?p=75"},"modified":"2019-02-09T21:38:11","modified_gmt":"2019-02-09T21:38:11","slug":"dnsgrep","status":"publish","type":"post","link":"https:\/\/blog.erbbysam.com\/index.php\/2019\/02\/09\/dnsgrep\/","title":{"rendered":"DNSGrep — Quickly Searching Large DNS Datasets"},"content":{"rendered":"\n

The Rapid7 Project Sonar<\/a> datasets are amazing resources. They represent scans across the internet, compressed and easy to download. This blog post will focus on two of these datasets:<\/p>\n\n\n\n

https:\/\/opendata.rapid7.com\/sonar.rdns_v2\/<\/a> (rdns)
https:\/\/opendata.rapid7.com\/sonar.fdns_v2\/<\/a> (fdns_a)<\/p>\n\n\n\n

Unfortunately, working with these datasets can be a bit slow as the rdns and fdns_a datasets each contain over 10GB of compressed text. My old workflow for using these datasets was not efficient:<\/p>\n\n\n\n

ubuntu@client:~$ time gunzip -c fdns_a.json.gz | grep \"erbbysam.com\"
{\"timestamp\":\"1535127239\",\"name\":\"blog.erbbysam.com\",\"type\":\"a\",\"value\":\"54.190.33.125\"}
 {\"timestamp\":\"1535133613\",\"name\":\"erbbysam.com\",\"type\":\"a\",\"value\":\"104.154.120.133\"}
 {\"timestamp\":\"1535155246\",\"name\":\"www.erbbysam.com\",\"type\":\"cname\",\"value\":\"erbbysam.com\"}
 real    11m31.393s
 user    12m29.212s
 sys     1m37.672s<\/code><\/pre>\n\n\n\n
I suspected there had to be a faster way of searching these two datasets.<\/p>\n\n\n\n
(TLDR, reverse and sort domains then binary search)<\/p>\n\n\n\n
DNS Structure<\/h2>\n\n\n\n
A defining features of the DNS system is its tree-like structure. Visiting this page, you are three levels below the root domain<\/a>:<\/p>\n\n\n\n
com
com.erbbysam
com.erbbysam.blog<\/pre>\n\n\n\n
The grep query above looks for a domain name tied to the root domain, not an arbitrary string in the file. If we could shape our dataset into a DNS tree, an equivalent lookup would just require a quick traversal of this tree.<\/strong><\/p>\n\n\n\n
Binary Search<\/h2>\n\n\n\n
The task of transforming a large dataset into a tree on disk and traversing this tree can be simplified further using a binary search algorithm<\/a>.<\/p>\n\n\n\n
The first step in using a binary search algorithm is to sort the data. One option, matching for format above, is the form “com.erbbysam.blog”. This would require a slightly more complex DNS reversal algorithm than neccessary. To simplify, reverse each line instead:<\/p>\n\n\n\n
moc.masybbre.golb,521.33.091.4
moc.masybbre,331.021.451.40
moc.masybbre.www,moc.masybbre<\/pre>\n\n\n\n
There are no one-command solutions to sort a dataset that does not fit into memory (that I am aware of). To sort these large files, split the data into sorted chunks and then merge the results together:<\/p>\n\n\n\n
# fetch the fdns_a file\nwget -O fdns_a.gz https:\/\/opendata.rapid7.com\/sonar.fdns_v2\/2019-01-25-1548417890-fdns_a.json.gz\n\n# extract and format our data\ngunzip -c fdns_a.gz | jq -r '.value + \",\"+ .name' | tr '[:upper:]' '[:lower:]' | rev > fdns_a.rev.lowercase.txt\n\n# split the data into chunks to sort\n# via https:\/\/unix.stackexchange.com\/a\/350068 -- split and merge code\nsplit -b100M fdns_a.rev.lowercase.txt fileChunk\n\n# remove the old files\nrm fdns_a.gz\nrm fdns_a.rev.lowercase.txt\n\n# Sort each of the pieces and delete the unsorted one\n# via https:\/\/unix.stackexchange.com\/a\/35472 -- use LC_COLLATE=C to sort ., chars\nfor f in fileChunk*; do LC_COLLATE=C sort \"$f\" > \"$f\".sorted && rm \"$f\"; done\n\n# merge the sorted files with local tmp directory\nmkdir -p sorttmp\nLC_COLLATE=C sort -T sorttmp\/ -muo fdns_a.sort.txt fileChunk*.sorted\n\n# clean up\nrm fileChunk*<\/code><\/pre>\n\n\n\n
More detailed instructions for running this script and the rdns equivalent can be found here:
https:\/\/github.com\/erbbysam\/DNSGrep#run<\/a><\/p>\n\n\n\n
DNSGrep<\/h2>\n\n\n\n
Now we can search the data! To accomplish this, I built a simple golang utility that can be found here:
https:\/\/github.com\/erbbysam\/DNSGrep<\/a><\/p>\n\n\n\n
ubuntu@client:~$ ls -lath fdns_a.sort.txt\n-rw-rw-r-- 1 ubuntu ubuntu 68G Feb  3 09:11 fdns_a.sort.txt\nubuntu@client:~$ time .\/dnsgrep -f fdns_a.sort.txt -i \"erbbysam.com\"\n104.154.120.133,erbbysam.com\n54.190.33.125,blog.erbbysam.com\nerbbysam.com,www.erbbysam.com\n\nreal    0m0.002s\nuser    0m0.000s\nsys    0m0.000s\n<\/code>\n<\/pre>\n\n\n\n
That is significantly faster! <\/p>\n\n\n\n
The algorithm is pretty simple:<\/p>\n\n\n\n
  1. Use a binary search algorithm to seek through the file, looking for a substring match against the query.<\/li>
  2. Once a match is found, the file is scanned backwards in 10KB increments looking for a non-matching substring.<\/li>
  3. Once a non-matching substring is found, the file is scanned forwards until all exact matches are returned.<\/li><\/ol>\n\n\n\n
    PoC<\/h2>\n\n\n\n
    PoC<\/strong> disclaimer<\/strong>: There is no uptime\/performance guarantee of this service and I likely will take this offline at some point in the future. Keep in mind that the datasets here are from a scan on 1\/25\/19 — DNS records may have changed by the time you read this.<\/p>\n\n\n\n
    As these queries are so quick, I set up an AWS EC2 t2.micro instance with a spinning disk (Cold HDD sc1) and hosted a server that allows queries into these datasets:
    https:\/\/github.com\/erbbysam\/DNSGrep\/tree\/master\/experimentalServer<\/a><\/p>\n\n\n\n
    https:\/\/dns.bufferover.run\/dns?q=erbbysam.com<\/a><\/p>\n\n\n\n
    ubuntu@client:~$ curl 'https:\/\/dns.bufferover.run\/dns?q=erbbysam.com' \n{\n\t\"Meta\": {\n\t\t\"Runtime\": \"0.000361 seconds\",\n\t\t\"Errors\": [\n\t\t\t\"rdns error: failed to find exact match via binary search\"\n\t\t],\n\t\t\"FileNames\": [\n\t\t\t\"2019-01-25-1548417890-fdns_a.json.gz\",\n\t\t\t\"2019-01-30-1548868121-rdns.json.gz\"\n\t\t],\n\t\t\"TOS\": \"The source of this data is Rapid7 Labs. Please review the Terms of Service: https:\/\/opendata.rapid7.com\/about\/\"\n\t},\n\t\"FDNS_A\": [\n\t\t\"104.154.120.133,erbbysam.com\",\n\t\t\"54.190.33.125,blog.erbbysam.com\",\n\t\t\"erbbysam.com,www.erbbysam.com\"\n\t],\n\t\"RDNS\": null\n}\n<\/code><\/pre>\n\n\n\n
    Having a bit of fun with this, I queried every North Korean domain name, grepping for the IPs not in North Korean IP space<\/a>:
    https:\/\/dns.bufferover.run\/dns?q=.kp<\/a><\/p>\n\n\n\n
     ubuntu@client:~$ curl 'https:\/\/dns.bufferover.run\/dns?q=.kp' 2> \/dev\/null | grep -v \"\\\"175\\.45\\.17\"\n{\n\t\"Meta\": {\n\t\t\"Runtime\": \"0.000534 seconds\",\n\t\t\"Errors\": null,\n\t\t\"FileNames\": [\n\t\t\t\"2019-01-25-1548417890-fdns_a.json.gz\",\n\t\t\t\"2019-01-30-1548868121-rdns.json.gz\"\n\t\t],\n\t\t\"TOS\": \"The source of this data is Rapid7 Labs. Please review the Terms of Service: https:\/\/opendata.rapid7.com\/about\/\"\n\t},\n\t\"FDNS_A\": [\n\t\t\"175.45.0.178,ns1.portal.net.kp\",\n\t],\n\t\"RDNS\": [\n\t\t\"185.33.146.18,north-korea.kp\",\n\t\t\"66.23.232.124,sverjd.ouie.kp\",\n\t\t\"64.86.226.78,ns2.friend.com.kp\",\n\t\t\"103.120.178.114,dedi.kani28test.kp\",\n\t\t\"198.98.49.51,gfw.kp\",\n\t\t\"185.86.149.212,hey.kp\"\n\t]\n}<\/code><\/pre>\n\n\n\n
    That’s it! Hopefully this was useful! Give it a try: https:\/\/dns.bufferover.run\/dns?q=<hostname>
    <\/p>\n","protected":false},"excerpt":{"rendered":"
    The Rapid7 Project Sonar datasets are amazing resources. They represent scans across the internet, compressed and easy to download. This blog post will focus on two of these datasets: https:\/\/opendata.rapid7.com\/sonar.rdns_v2\/ (rdns)https:\/\/opendata.rapid7.com\/sonar.fdns_v2\/ (fdns_a) Unfortunately, working with these datasets can be a bit slow as the rdns and fdns_a datasets each contain over 10GB of compressed text. … <\/p>\n
    Continue reading “DNSGrep — Quickly Searching Large DNS Datasets”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.erbbysam.com\/index.php\/wp-json\/wp\/v2\/posts\/75"}],"collection":[{"href":"https:\/\/blog.erbbysam.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.erbbysam.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.erbbysam.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.erbbysam.com\/index.php\/wp-json\/wp\/v2\/comments?post=75"}],"version-history":[{"count":46,"href":"https:\/\/blog.erbbysam.com\/index.php\/wp-json\/wp\/v2\/posts\/75\/revisions"}],"predecessor-version":[{"id":125,"href":"https:\/\/blog.erbbysam.com\/index.php\/wp-json\/wp\/v2\/posts\/75\/revisions\/125"}],"wp:attachment":[{"href":"https:\/\/blog.erbbysam.com\/index.php\/wp-json\/wp\/v2\/media?parent=75"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.erbbysam.com\/index.php\/wp-json\/wp\/v2\/categories?post=75"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.erbbysam.com\/index.php\/wp-json\/wp\/v2\/tags?post=75"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}