Computer Journal

April 8-10, 2015
Permalink
keystream_dupe-0.6.tgz [sig]
keystream_dupe-0.5.tgz [sig]
keystream_dupe-0.4.tgz [sig]
keystream_dupe-0.3.tgz [sig]
keystream_dupe-0.2.tgz [sig]
keystream_dupe-0.1.tgz [sig]

In this very basic cryptography exercise, I have written a simple test of the quality of a cipher. For RC4 and stream ciphers, we can encrypt \x00\x00\x00\x00 to get the first four bytes of the keystream. I do this for the first 1048576 keys (assuming big endian and 64-bit keys) with RC4. Then I find out how many random keys I have to try before I find the same first four keystream bytes. I do this 1024 times. The data shows that this is around 4 million keys.

For block ciphers like AES, we have to do it slightly differently, but the concept is the exact same. I encrypt "GET / HTTP/1.1\r\n" which happens to be 16 bytes, the exactly correct size to fit in a single block of AES plaintext. I store the first four bytes of the ciphertext for the first 1048576 keys (same assumption as above but 128-bit keys). Then I do the same with random keys and I compare the first four bytes of the ciphertext against the first four bytes of the 1048576 partial ciphertexts. I find out how many random keys I have to try before I find the same first four ciphertext bytes. I do this 1024 times. The data shows that this is around 3 million keys. As you can clearly see, this is far smaller than RC4 (which is known to be vulnerable to many attacks).

To test whether the problem is in AES or RC4, I used my system's random number generator (Linux /dev/urandom) to generate random bytes of keystream and tested how many attempts it would take to collide 1024 times. It took on the order of 4 million. This proves that the issue is either in AES or in RC4 and my system's random number generator. Since my system's random number generator is as good a source of entropy as I have, I must conclude that there is no issue with RC4 and that there is an issue with AES.

Oct 25, 2014 - Jan 25, 2015

By the way we're not any geeks, we hack into NASA
-- Dual Core "All The Things"

DNSSEC has an interesting design flaw where it was designed around precomputation of all data. The keys are held offline so they cannot be seized in a compromise of the server. This presents a problem because the non-existence of a domain cannot be easily precomputed (Does abcdefg1234567.yourdomain.com exist? No, abcdefg1234567.yourdomain.com doesn't exist. If the response was "No" an attacker could replay that response on a domain that did exist. If the response was not signed, an attacker could generate their own No responses. If the server didn't respond, the resolver would have to wait until a timeout occurred which could take a minute depending on the implementation). To solve this problem, they created NXT records and then after that they created NSEC records. Almost no servers use NXT, but it's easy enough to parse those. NSEC records list the two nearest matches in the database to the requested record. Hackers found that this results in name enumeration and they wrote tools to use that. Dan J. Bernstein describes this attack on his page: DNS database espionage [1]. In response, Dan Kaminsky's DNSSEC proxy Phreebird dynamically generates NSEC3 responses that do not divulge any information. This research shows that no TLDs currently use Phreebird. What can you get out of NSEC and NSEC3 records? Every subdomain of nasa.gov? See below. Every subdomain of .br? Every subdomain of hpc.mil? Every subdomain of paypal.com? It turns out that there are millions of domains that can be enumerated with NSEC3 and NSEC walkers. That is exactly what I have done. ldns-walk allows enumeration of NSEC records and a patch to nsec3walker is available above. A bug in ldns-walk causes an endless while loop for some domains, a workaround has been made available until a fix is found.

All of these methods and attacks are 5 years old. What's the deal? Since 2009, the government of the United States and many other NICs have mandated the use of DNSSEC on many servers or simply signed all domains below their TLD. Adoption of DNSSEC has increased by orders of magnitude. In fact, nsec3walker is unable to collect all of .com in a single attempt, as one might expect. Patches are necessary to get nsec3walker to collect com NSEC3 records because it has no salt (nsec3walker was designed to assume that a salt was required). As more and more hashes are added, it becomes exponentially slower looking for hashes that fall between two hashes. For example, try finding a domain name that hashes between 00000000aaaaaaaaaaaaaaaaaaaaaaaa and 00000000bbbbbbbbbbbbbbbbbbbbbbbb. The odds of you finding a hash between those two are approximately 2⁴⁴:1. That means it will take trillions of hashes to find such a hash. This is the basis for the proof of work that has been very popular in programming since its use in Bitcoin (and before that, HashCash [2]).

The entirety of com was only 396191 domains, which means that only nameservers that have opted-in to DNSSEC are possible to enumerate. However, this shows that systems that opt-in to DNSSEC are uncovered by hash cracking, giving users a clear reason not to use DNSSEC. Furthermore, the results that come from NSEC walking show that if a nameserver chooses to use DNSSEC, NSEC3 costs people who wish to enumerate NSEC3 cpu time. Targeted attacks are much more effective against NSEC3 than generic attacks because an attacker can add a word to the cracking practically for free. For example testing the three domains:
microsofta.com
microsoftb.com
microsoftc.com
against all hashes in com is as easy as hashing the three domains:
a.com
b.com
c.com
This makes it possible to guarantee that none of the hashes are name + letter * 7 because given only 37 valid characters in domain names, there are only 95 billion unique name + letter * 7 combinations. It takes minutes to crack all possible values. Similarly, letter * 7 + name and letter * 4 + name + letter * 3 take the same amount of time. The entire wordlist from AI3 that are valid domain names is only 3678794 words long. This means that we can crack word + word + name, name + word + word, and word + name + word for 13.5 trillion SHA1 hashes (assuming that the domain uses a single iteration like com does). This takes weeks on a CPU but less time on a GPU. I spent a month and a half doing exactly this with the first 8000 words from the AI3 wordlist as well as brute force, with incredible success. I was able to crack 226346 of the 396932 com hashes found (57%). By using brute force, I was guaranteed to find all short domain names which leaves only long domain names for Markov chain cracking and passphrase cracking. As I said before, the AI3 wordlist is very effective against weak passphrases. Therefore we can only expect long or complex domains to remain. While you may reject the notion that over 43% of domain names that use DNSSEC are long and complex enough to make cracking difficult, I recommend trying oclHashcat against these NSEC3 hashes to verify my findings.

Jan 31, 2015

JavRE-0.2 [sig]
JavRE-0.1.1 [sig]
Git repository: git clone https://www.altsci.com/repo/javre.git
JavRE project page

Reverse Engineering is an interesting and useful task which allows a person to gain knowledge about the software they use or that other people use. This basic tutorial for those who have had trouble getting started shows the methods on a file for which we have source code. It's a linux binary which is part of foo2zjs, an open source printer driver for HP printers. Like many Linux drivers, foo2zjs is made up of simple command-line executables which follow the Unix philosophy, do one thing and do it well. Of course there are exceptions to this, but the program we're reversing today was picked by me because it's important and small. Isn't that a nice combination? How small is /bin/usb_printerid? It's 8.4kB not stripped, 6.2kB stripped when compiled 64-bit. It is very similar in size to the simple 13 line program if2, which is 7.9kB unstripped, 6.1kB stripped. So what does usb_printerid do? Let's assume that we didn't have a name. Let's call it black for a few minutes.

Since black came from an untrusted source and was not signed by the author anyway, we consider it untrustworthy. Even if it came from a trusted source, we couldn't verify it, so we have to explicitly not trust it. How do we run something without trusting it? The Android model for running untrusted apps is to give the app a user and don't give that user access to the rest of the system. How difficult is that? Very difficult. For one, the kernel needs to not have any exploitable local root vulnerabilities. For two, no suid executables available to the user can have local code execution vulnerabilities before they drop privileges. Let's try to do that. You might think it's easiest to just run a virtual machine. Feel free to do that. I am going to recommend a different method similar to Android's security model. There are other ways to run code without trusting it, but they trade privacy for security. If you have root access on your local system, you can create a new user. Let's name that user oooooo after the program we're going to be running, black. Shadow has a program called useradd which I'll be using. If you're familiar with adding users, I'll leave it up to you.

Oct 10, 2010 10:43 am

No files officially released yet. See below.

Firmware hacking is an impressively difficult yet rewarding task. Most people are afraid of it because it depends on reversing binaries for embedded architectures that do not have good tools. Many tools that do exist are expensive and have a high learning curve even for experts in the field. Firmware hacking is actually a fun and simple process if you know what you're looking for. Projects for cell phones, video game consoles, and calculators are often out of the league of amateurs until the initial work is done. After the system has been successfully hacked, the code (if made available as open source) can be modified by anyone to improve the software.