I. The Challenge

The Honeynet Project challange for June 2000 reads:

II. Analyzis

The first step in breaking an unknown encryption is to determine the nature of the encrypted information, including its possible purpose and language. In some cases they will be fairly obvious, but often an educated guess will be the best we can get.

We are presented with an encrypted file, 532 bytes long. This file is a part of a blackhat security toolkit. The file is not big enough to be a binary or an archive. We will base our encryption analysis on the assumption that the file contains text. It could be source code, passwords or names of irc channels for eggdropping.

A good introduction to cryptanalysis is the Department of the Army Field Manual No 34-40-2, Basic Cryptanalysis. It covers monoalphabetic and polyalphabetic substitution ciphers and provides algorithms and techniques for breaking them.

The encryption algorithm is unknown. If the encryption is strong (Blowfish, Rijndael, RC4 or any of the other AES candidates) we won't be able to break with it a single 532 bytes message. Let's ignore these algorithms for now.

Another option is DES, which is used in the default implementation of crypt() on Unix, as well as countless other software projects. It would make sense for the blackhat to use this algorithm because of its simplicity, relative strength and publicly available source code. However, DES is a block cipher and operates on 64-bit blocks. The file size is 532, which is not a multiple of 4. The file can not be encrypted with DES, unless the algorithm was modified or the file has extra padding. Since we want to explore the simple cases first, we'll leave DES for later.

Another very common "encryption", utilized by countless Windows programs is the so called XOR-encryption. The XOR logic function has the interesting property that if A xor B = C, then C xor B = A. If A is the plaintext and B is the key, C will be the encrypted data. Xoring C with the key B will give us back the plaintext A. In 1942 Shanon proved that if the key is trully random and as long as the message the encryption can not be broken. Unfortunately in this case transmitting the key becomes as hard as transmitting the original message which makes this type of encryption usable only in limited cases.

Most programs using XOR encryption use a short key repeatedly, xoring all data with it. This reuse of the key makes them vulnerable to some very simple statistical attacks. The coincidence test can immediately determine the length of the key. Then we can shift the encrypted data by k bytes (where k is the length of the key) and XOR it with itself. Frequency analysis can be used on the resulting data to efficiently brute-force the encryption. (see question 8.2 in the sci.crypt FAQ: How do I break a Vigenere (repeated-key) cipher?)

We'll assume that the file is XOR encrypted and we'll try to break that. A very nice tool for this task is the xor-analyse package by Marvin <marvin@nss.nu> It contains the following programs:

• xor-enc encrypts data
• xor-dec decrypts data
• xor-analyse finds the key by using statistical analysis
• freq  generates frequency distribution data

II. Breaking the XOR encryption

Running freq over somefile gives us a very interesting frequency distribution - there are only 45 characters used and the frequency distribution is very uneven. This is very similar to the statistics that we get for text or source code. This is a clear indication that the encryption is weak. Strong encryption algorithms like DES and Blowfish produce data that looks almost random.

For an interesting article about using randomness visualization for encryption analysis take a look at http://www.quantdec.com/encryption.htm.

Let's run the xor-analyse tool and they try to decrypt the file.

$ ./xor-analyze -v ../somefile ./freq/english.freq 
xor-analyze version 0.1 by marvin (marvin@nss.nu)
Counting coincidences... 20 / 20
Key length is probably 4
Key length Coincidents Bytes Coincidents (in percent)
1 23 / 532 = 4.32 %
2 17 / 532 = 3.20 %
3 17 / 532 = 3.20 %
4 51 / 532 = 9.59 % (winner)
5 31 / 532 = 5.83 %
6 30 / 532 = 5.64 %
7 45 / 532 = 8.46 %
8 24 / 532 = 4.51 %
9 23 / 532 = 4.32 %
10 29 / 532 = 5.45 %
11 41 / 532 = 7.71 %
12 21 / 532 = 3.95 %
13 31 / 532 = 5.83 %
14 15 / 532 = 2.82 %
15 28 / 532 = 5.26 %
16 27 / 532 = 5.08 %
17 24 / 532 = 4.51 %
18 17 / 532 = 3.20 %
19 25 / 532 = 4.70 %
20 29 / 532 = 5.45 %
Probable key: "uyyz"
$ ./xor-dec uyyz somefile somefile.out

Unfortunately this is not the correct key. Somefile.out does not contain anything meaningful. Running xor-analyze with different frequency tables also does not help.

IV. The magical NOT instruction

Let's take a look at the encrypted file again. Notice that all the bytes in the file are > 128. This means that their 8th bit is always 1. The plaintext (which we believe to be source code) consists of alpha-numerical 7bit ASCII characters which all have 0 as their 8-th bit. Xoring the plaintext bit '0' with the encrypted bit '1' will give us the key bit.

0 XOR 1 = 1

All bytes in the key must have 1 as their high bit. The key must contain only high ASCII characters. While it is possible to use high ASCII characters for the key, this would create too much inconvenience if the key has to be entered with a keyboard. This doesn't make sense.

We must be missing something.

The encryption can not be pure XOR if we assume that the key is alphanumeric. May be the blackhat is trying to obfuscate the algorithm by doing additional operations on the output? May be the blackhat is just flipping the 8th bit after the XOR operation? Let's convert all data in a file to 7bit ASCII by reseting the 8-th bit of each byte and try xor-analyze again.

$ ./7bit < somefile > somefile.7bit
$ ./xor-analyze somefile.7bit ./freq/english.freq
xor-analyze version 0.1 by marvin (marvin@nss.nu)
Counting coincidences... 20 / 20
Key length is probably 4
Probable key: "yyya"
$ ./xor-dec yyya somefile.7bit somefile.out

No progress here.

Let's try something else. May be the algorithm flips all bits after the XOR, not only the 8-th bit. This scheme might be called XOR+NOT.

Negating all bytes in the file gives us an unexpected result - the plaintext. There is no key and no XOR encryption. The encrypted data is just the 1's complement of the plaintext. We can decrypt the file using the following perl one-liner:

perl -e 'while (<>) { print ~$_; }' < somefile

V. The decrypted file

[file]
find=/dev/pts/01/bin/find
du=/dev/pts/01/bin/du
ls=/dev/pts/01/bin/ls
file_filters=01,lblibps.so,sn.l,prom,cleaner,dos,uconf.inv,psbnc,lpacct,USER


[ps]
ps=/dev/pts/01/bin/psr
ps_filters=lpq,lpsched,sh1t,psr,sshd2,lpset,lpacct,bnclp,lpsys
lsof_filters=lp,uconf.inv,psniff,psr,:13000,:25000,:6668,:6667,/dev/pts/01,sn.l,prom,lsof,psbnc


[netstat]
netstat=/dev/pts/01/bin/netstat
net_filters=47018,6668


[login]
su_loc=/dev/pts/01/bin/su
ping=/dev/pts/01/bin/ping
passwd=/dev/pts/01/bin/passwd
shell=/bin/sh


su_pass=l33th4x0r

The file looks like a configuration file for a rootkit. The rootkit replaces find, du, ls, ps, lsof, su, ping and passwd with trojanized versions. The original files are copied to /dev/pts/01/bin. The trojanized utilities execute the original programs and filter their output, removing traces of the rootkit's presence. The file_filters, ps_filters, lsof_filters and net_filters specify the files, processes and ports to be hidden.

The password for getting root access through the trojanized version of su is l33th4x0r.

VI. The rootkit

Searching for su_pass and other strings from this file gives us a few hits on Google. One of them is a message in the SecurityFocus-Sun mailing list (http://archives.neohapsis.com/archives/sf/sun/2001-q2/0088.html)

When I noticed our backups weren't working right, I started to investigate. 
One of the startup scripts called the /usr/bin/ps command, and I noticed the 
file size of ps was off compared to some of our other machines running 
solaris 8. I did a 'strings ps' and found this: 


  /dev/pts/01/uconf.inv 
  [file] 
  find 
  file_filters 
  [ps] 
  ps_filters 
  [netstat] 
  netstat 
  net_filters 
  [login] 
  su_pass 
  su_loc 
  ping 
  passwd 
  shell 
  /dev/pts/01/bin/psr 
  lp,uconf.inv,psniff,psr 
  tw33dl3 
  /bin/sh 


A 'strings ps' I'm guessing should normally return something like this on 
solaris 8: 


  SUNW_OST_OSCMD 
  %s: cannot find the ISA list 
  %s: getexecname() failed 
  %s: malloc(%d) failed 
  %s: execve("%s") failed 
  %s: cannot find/execute "%s" in ISA subdirectories 

There was a README in the directory which states: 

  This is: SunOS Rootkit v2.5 (C) 1997-2001 Tragedy/Dor 
  If you find this file, most likely your host has been hacked by a user 
  of this rootkit. If you want information about this tool, removal instructions 
  or such, please email bert.smith@mbox.bol.bg 
  The author takes NO RESPONSIBILITY for anyone who misuses this tool. 

  Please quote the following version number in any emails.. if the rootkit wasnt 
  installed the version will be in a file named "iver" 

  17645914 

There are quite a few shellscripts and solaris binary replacements in the 
/dev/pts/01 directory. There were also 5 or 6 other machines with this 
directory as well. I tried aksing around and doing some research on the web 
and came back with practically nothing. Does anyone have any suggestions? 

Regards, 
--
Christopher Wong
Florida Atlantic University
chris@fau.edu

This looks like our rootkit. According to the README it was written by Tragedy/Dor <bert.smith@mbox.bol.bg> I send an email to this address and Dor was kind enough to send me the binaries of his rootkit - k.tar.gz. I have not analyzed the rootkit in depth, since this is not the objective of Scan 16, but I looked at the installation script. It writes out the configuration to a temporary file and then obfuscates it with a crypt program, included in the rootkit. By disassembling the crypt binary with IDA Pro I found out that it simply reads the file, NOTs every byte and writes it out. My cryptanalysis appears to be correct.

VII. Conclusion

The configuration file is encrypted in an attempt to hide its contents in case the /dev/pts/01/bin directory is discovered. An inexperienced system administrator might be less suspicious if the file is not in plaintext and assume that if he doesn't understand it, it belongs there. An experienced system administrator knows that these files shouldn't be there and will immediately recognize the rootkit as such.

I learned a few important lessons from this challange: 1) A scary looking encryption scheme is not neceserilly secure. 2) Sometimes things are much simpler than they look. 3) Never underestimate the power of Google.

It took me about 8 hours to decrypt the file, most of which I spend reading introductory cryptography texts on the web and looking for a pirated OCR-ed copy of Applied Cryptoraphy.

The actual work was no more than 4 hours.

-rw-r----- 1 solar eclipse 532 Jun 5 17:09 somefile
-rw-r--r-- 1 solar eclipse 532 Jun 5 23:27 somefile.7bits
-rw-r--r-- 1 solar eclipse 532 Jun 6 01:22 somefile.not

Writing this text took me 3 hours.