Basics of XORing
In a recent tutorial, I showed you how to use shikata_ga_nai to change the signature of a payload to evade detection by security devices (firewalls, IDS, etc.) and AV software.
Shikata_ga_nai is an encoding module in Metasploit that XORs the payload through multiple iterations (the number of iterations is up to you), thereby changing the payload's signature. When the payload bypasses the security devices and the AV software, it then reverses the XORing and the payload is executed normally on the victim's system.
From the questions and comments I received on that guide, it became apparent that not all of you are familiar with this concept of XOR. This guide is dedicated to those of you who are not familiar with this common technique in information technology, and as refresher for those who are.
What Is XOR?
XOR stands for eXclusive OR. In logic and in everyday language, an OR can mean that either statement is true or both are true. In other words, the statement will evaluate to true if any of the statements are true. So, if I say, "The sky is cloudy OR the sky is blue," it will evaluate to true if either statement is true or if the sky is blue AND cloudy.
The exclusive OR makes a distinction between these two and means only the case where one of the two statements is true. It is used throughout computing for numerous purposes, including the encryption of the payload using shikata_ga_nai, error checking, and setting parity bits on a RAID, among many other things.
As you know, computers operate with millions of on/off switches. Modern computers uses transistors to operate these on/off switches, but of course, early computers used vacuum tubes and any on/off switch would suffice.
These on/off switches are represented by a single bit that is often represented by an o. That bit can be on or off. If it is off, it is represented with a 0 (zero) and if it is on, it is represented with a 1 (one). Additionally, the 0 represents false and the 1 represents true. It might help you to remember this by thinking of the question, "Is the switch on?" True if it is "on" (1), and false if it "off" (0). Hope that helps.
Boolean algebra is the algebra of statements that evaluate to either true or false. This is useful in computing because we can represent these two states (true or false) by a single bit. When the statement is false, it is represented by a zero (off) and when it is true it is represented by a one (on).
In logic and computing, we often use what are known as truth tables. These truth tables represent all the possible cases and whether they would evaluate to true or false, hence the name "truth tables". In the case of XOR, there are only four possible cases as illustrated below.
Note that whenever the two inputs are the same (00, 11) they evaluate to false. whenever the two inputs are different (10, 01) the XOR evaluates to true. So, to summarize, same is 0 and different is 1.
The XOR cipher is a relatively simple cipher that encrypts the input by using a key that is then XORed against the input to create an output. For example:
One of the advantages of the XOR cipher is that it is simple and fast. In addition, it does not need a separate algorithm to decipher it, as all systems can XOR. This is why it works so well in Metasploit's shikata_ga_nai encoding.
XOR in RAIDS
XOR is used in RAID levels 3–6 for creating parity information. RAID 1 is mirroring the hard drive, which means we need twice as many drives (and cost) to create fault tolerance. On the other hand, parity information is used to make certain that if one drive fails, the original information can be recovered. In this way, the RAID has fault tolerance without a huge additional expense.
For example, a RAID can assure the recovery of bytes 10011100 and 01101100 from two (or more) hard drives by XORing these bytes, resulting in (11110000) and writing it to another drive. In a RAID 3 arrangement, this is a separate drive. In a RAID 5 arrangement, as illustrated above, the parity is interspersed among the drives.
Under this method, if any one of the hard drives are lost, the lost byte can be recreated by XORing bytes from the remaining drives. For instance, if the drive containing 01101100 is lost, 10011100 and 11110000 can be XORed to recover the lost byte.
XOR in Error Checking
XORing is also implemented in CRC, or cyclic redundancy check, a common method in computing to detect whether any accidental errors have entered the data. CRC is used for error checking in TCP, hard drives, cell phones, and nearly every other type of data transmission. Although the mathematics are beyond the scope of this tutorial, suffice to say that at least, in part, CRC uses XOR.
I hope this short tutorial on XOR is helpful and enlightening to my novice hackers, as XOR is used throughout IT and hacking. It is especially important in exploit and payload obfuscation to avoid detection by security devices and AV software.