VIRUS BULLETIN www.virusbtn.com
MALWARE ANALYSIS
is large enough to hold the virus body. The file cannot be
MAKING A HASH OF THINGS
infected by any of the first three variants if the section is
Peter Ferrie
too small.
Microsoft, USA
HASH COOKIES
File format tricks abound in ELF files. One of these was
described in last month s issue of Virus Bulletin (see VB,
At this point, the .A and .B variants check if the file is
July 2009, p.4). In that trick, a particular section of the file
infected already. The infection marker for the .A variant is
was overwritten by virus code. A variation of that technique
the number of hash buckets being set to one. This is a legal
is described here.
value, but it effectively disables the hashing mechanism.
The infection marker for the .B variant is the first byte in the
hash section being a  push instruction.
MISPLACED TRUST
The hash table exists to improve the performance of
In contrast to the  Caveat virus, which overwrites the
locating symbols. Instead of searching linearly through
 .note.ABI-tag section of ELF files, the  Hasher virus
the symbol table, the hash table allows the searching to be
(so-named by its author) is interested in the  .hash section.
achieved using perhaps only a few comparisons. The hash
The virus begins by searching for files within the current
table consists of an array of buckets, which is a collection
directory. When a file is found, the virus attempts to open
of pointers whose number ideally corresponds to the
and map it. If the mapping process fails, the virus closes the
number of unique hashes in the symbol table. However,
file without attempting to unmap anything.
the number can be made arbitrarily smaller than that, which
saves space.
However, the virus is very trusting of the contents of the file.
The first three variants of the virus all assume that the file is
To find a symbol, its hash value is calculated (the hashing
in ELF format without verifying this fact. A field inside the
algorithm is published in the file format specification), and
supposed ELF header is used, without checking that the file
the bucket is indexed by using the hash value modulo the
is large enough to support the field s presence. A sufficiently
number of buckets. A bucket is simply a starting point for
small file will cause the code to crash. A truncated ELF file,
searching within a particular chain. The number of chains
or a file with a sufficiently large value in the e_shnum field,
corresponds exactly to the number of symbols in the file. If
among other things, will also cause the virus to crash, since
either a bucket entry or a chain entry of zero is encountered,
the code contains no bounds checking of any kind. The .D
then the symbol does not exist in the file. In the most
variant of the virus requires that a file is at least 1,024 bytes
extreme case, the number of buckets can be set to one, in
long, but this is insufficient to avoid crashes when pointers
which case the entire chain might be searched for a match,
reach outside of the file.
as for the case where no hash table exists at all.
THE MAKER S MARK
A HOLE IN THE BUCKET
The virus is interested in ELF files for the Intel x86-based
The .A variant of the virus disables the lookup by setting
CPU. At this point the .C and .D variants of the virus check
the number of buckets to one, and the number of chains
whether the file is infected already, while the .A and .B
and the first bucket entry to zero. This corresponds to a
variants perform this check later. The infection marker
single empty bucket, and thus no symbols. The virus code is
for the .C and .D variants is the last byte of the e_ident
appended immediately after the end of this new hash table,
field being set to 1. This has the effect of inoculating the
since the table is no longer usable. As a result of the change,
file against a number of other viruses, since a marker in
symbol lookup no longer works for an infected file, but the
this location is quite common. The .C and .D variants set
file remains executable as before. The entrypoint of the file
this value in the file immediately. This has the effect of
is altered to point directly to the virus code.
preventing the files from being examined again, in case an
The .B variant of the virus alters the characteristics of the
error occurs while infecting them. In addition, the .D variant
Section Header Table entry, by replacing the SHT_HASH
requires that the ABI is either for Linux or is not specified.
entry with a SHT_NULL entry. As a result of the change, the
For each such file that is found, the virus searches within hash table seems no longer to exist in the file, and thus the
the Section Header Table entries for the SHT_HASH entire table becomes available for the virus. The virus code
entry. If the SHT_HASH entry is found, then with the is placed over the top of the hash table, and the entrypoint of
exception of the .D variant, the virus checks if the section the file is altered to point directly to the virus code.
4 AUGUST 2009
VIRUS BULLETIN www.virusbtn.com
Header Table entries. The second and following sections, up
STASH THE HASH
to and including the hash table section, have their memory
The .C variant of the virus requires that the size of the .hash
and file offsets increased by 32 bytes. The contents of those
section is large enough to hold both the number of chains
sections are also moved down in the file by 32 bytes. An
and the virus body. This would be a rare occurrence, but the
implicit assumption exists here, which is that the section
virus author included the technique for completeness. If the
is legally movable. This is not the case for code and data
section is large enough, then the virus reduces the number
sections, since they might contain direct references to each
of buckets by the size of the virus body in dwords. There is
other which would also need to be adjusted. Thus, if the
a bug in this code, which is that the virus forgets to include
hash table appears after code or data sections, then the
room for at least one bucket. The new bucket number is
resulting infected file will no longer run.
checked against a value that is less than zero, but it should be
checked against a value that is less than one. (Interestingly, Next, the .D variant of the virus examines the Program
the virus author included an overview document which Header Table. Another assumption is made here, which
describes the technique, and the document included an is that the Program Header Table exists. If the Program
algorithm written in C which contains the correct check. It Header Table does not exist, then the .D variant will crash.
seems that the bug was introduced when the virus author If any entry in the Program Header Table corresponds to
ported the algorithm to assembly language.) As a result, the one of the moved sections, then the .D variant will increase
number of buckets can be reduced to zero, in which case a the entry s memory and file offset by 32 bytes. Also, if any
divide-by-zero error will occur when the virus is building entry in the dynamic segment corresponds to one of the
the new bucket list. Given that a  bucket list is also a list of moved sections, then the .D variant will increase the entry s
things to do before the end of one s life, this bug is rather memory offset by 32 bytes.
appropriate. If the list is empty, the process dies.
If the list is valid, then the virus erases the existing hash
PHaT CODING
table entirely, and creates a new one in its place. The number
of chains remains the same, but the placement of the chains After making the appropriate adjustments to the Program
is altered according to the new number of buckets. For each Header Table, the .D variant of the virus examines the
symbol, the hash value is created, and the corresponding Program Header Table again. The lowest non-zero virtual
bucket entry (the hash value modulo the number of buckets, address of all of the entries, and the last PT_LOAD entry,
as described above) is examined. If the entry is empty, then is saved for later. If the PT_PHDR entry is seen, then the
the hash value becomes the bucket value. If the bucket .D variant increases its memory and file size by 32 bytes.
value exists already, then the chain is walked until the end is Once all of the Program Header Table entries have been
found, after which the hash value is appended to the chain. examined, the .D variant of the virus moves all of the
Once the bucket list has been created, the virus body is sections after the last PT_LOAD entry down in the file by
appended to the hash table, and the entrypoint of the file is 32 bytes. The .D variant then inserts a new PT_LOAD entry
altered to point directly to the virus code. into the newly created gap, whose file offset begins at the
current end of the file. The virtual address of the entry is set
to two pages below the previously lowest virtual address,
KICK THE BUCKET
taking into account the amount by which the file exceeds a
The .D variant of the virus searches the Section Header multiple of four kilobytes. Two pages are required for the
Table for the SHT_HASH and SHT_DYNAMIC entries. virus code, because even though the virus code is less than
Both of them must exist in order for the virus to infect the four kilobytes long, the new size of the file might exceed
file. The .D variant also requires that there are at least nine another multiple of four kilobytes, resulting in the virus
buckets in the hash table. The reason for this is because the code extending beyond the boundary of one page. The
.D variant intends to reduce the size of the hash table by entrypoint of the file is altered to point directly to the virus
32 bytes (which corresponds to eight buckets) and because code, and then the virus code is appended to the file.
at least one bucket must exist (as described above). If the
hash table contains at least nine buckets, then the .D variant
CONCLUSION
reduces the number of buckets by eight, and then erases and
rebuilds the hash table in the same way as for the .C variant.
The addition of a new section header is an interesting
The size of the hash table is then reduced by 32 bytes in the
technique, since it has long been thought that files are
Section Header Table.
packed too tightly for space to be found. While not ground
Once the hash table modifications have been made, the .D breaking in any way, this virus does show that one should
variant of the virus makes further adjustments to the Section be careful about received wisdom.
AUGUST 2009 5