When analyzing a new botnet, I tend to focus heavily on the network messages. After all, they are the glue that holds the botnet together. So one of the first things I did, when working on our new analysis of the Ozdok/Mega-D botnet, was to look at the messages and discover that they were encrypted. Of course this is not unusual, and after deciding the encryption was not something simple, I went to the bot code to see what was being used.
It soon developed that the encryption used was DES (Data Encryption Standard), in ECB mode. The cryptographic functions used are in the Microsoft Windows standard ADVAPI32 library. Clearly this should not be vulnerable to cryptanalysis or a brute force attack, not in the time available for anti-virus scanning. It was easy to find the key, which can be seen in the disassembled code below.
00408DE4 C645 EC 61 MOV BYTE PTR SS:[EBP-14],61 ; key 'a' 00408DE8 C645 ED 62 MOV BYTE PTR SS:[EBP-13],62 ; 'b' 00408DEC C645 EE 63 MOV BYTE PTR SS:[EBP-12],63 ; 'c' 00408DF0 C645 EF 64 MOV BYTE PTR SS:[EBP-11],64 ; 'd' 00408DF4 C645 F0 65 MOV BYTE PTR SS:[EBP-10],65 ; 'e' 00408DF8 C645 F1 66 MOV BYTE PTR SS:[EBP-F],66 ; 'f' 00408DFC C645 F2 67 MOV BYTE PTR SS:[EBP-E],67 ; 'g' 00408E00 C645 F3 68 MOV BYTE PTR SS:[EBP-D],68 ; 'h' ** So the **key was "abcdefgh", really nothing more than a lower case text password. Maybe the botnet herder was not too worried about security and expected to change the key frequently, but this did seem a little weak.
This made me wonder how weak this key really is. The only practical approach would be a brute force attack, where we try all the keys to see which one works. The DES key is 56 bits long, meaning there are 256 possible keys (2 to the 56th power), or in decimal numbers **256 = 72,057,594,037,927,935**, that is 72 million billion keys.
But if only lower case letters are used, as they are in the bot, the number of keys to try is only 268 = 208,827,064,576**. And it gets worse. DES only uses 56 bits for the key, and the 8 letters have 8 x 8 = 64 bits, so there are 8 bits too many. The official way to fix this is to drop the lowest bit from each letter, so that "b" (01100010) and "c" (01100011) both become 01100010. This means if we try "b", we don't need to try "c" because it is the same. The key "abcdefgh" is the same as "abbddffg", and the real number of lower case letter keys to try is 148 = 1,475,789,056**. Not impossible millions of billions, but just a billion and a half.
How much time would it take to search that many keys? One way to get a rough idea is to decrypt a large file and see how long it takes. A 800,000,000 byte file has 100,000,000 eight byte blocks, and takes that many DES operations to decrypt. This should give some idea of the time needed to test 100,000,000 keys. Running this test with mcrypt on an Intel Core2 Quad Q8400 (R) at 2.66 ghz, results in a decryption time of less than 70 seconds, about 1.4 million keys per second. For 1,475,789,056 keys that would be 1033 seconds or about 17 minutes.
If digits and lower case letters are allowed, there are 198 = 16,983,563,041** keys, and the search time would be 11,888 seconds or 198 minutes. Include upper case letters and there are 338 = 1,406,408,618,241** keys, and the time goes up to 984,486 seconds or 273 hours. To search all of the 72,057,594,037,927,935 possible keys at this rate would require 50,440,315,827 seconds, or about 1599 years.
The search times would certainly be far shorter with software written specially for this purpose and a more powerful computer. Even better times could be achieved with a hardware DES processor, especially if several were run in parallel. In the test 1.4 million decryptions were done per second, but some dedicated chips claim to process as many as 30 million DES decryptions per second.
So for the lower case letter key found in Ozdok, we are almost at the point where the key can be searched quickly enough for antivirus purposes. For keys with a wider range of values the times become too great, at least for the present time.
Part of the problem here derives from a basic weakness in the setting of encryption keys. Users typically will be asked to enter the key, so it can only include ordinary text bytes. The range of key values is seriously limited by this. DES aggravates the problem by folding text characters together, further reducing the real world key space. It is possible to process the password into a better key, but that does not help much if the algorithm used for this is known, and normally it cannot be kept secret. One practical way to reduce the problem is to employ an encryption system with a longer key, but only a fraction of the larger key space will be used.
In any case we can certainly learn something from these calculations. Keys and passwords with a limited range of characters are not just unsafe, they can actually compromise an otherwise secure system.
To find out more about the Ozdok/Mega-D botnet and its hidden messages, take a look at the new analysis.