For an update on how I got it smaller, check:
http://blogs.securiteam.com/index.php/archives/690

Hi everyone,

As I promised to get the tiny.exe less than 400 bytes, I sat last night and did it. Now with a new record size of 384 bytes and still supposed to run on all Windows versions.

You can find my original blog post with further technical details on this challenge here:
http://blogs.securiteam.com/index.php/archives/675

Here’s a snippet of the conversation between me and a good friend.
This is one of the ways to develop new tricks for code crunching:

…
…
Arkon: The problem with that URLDownloadToFileA is that it creates another thread,
Arkon: and that thread never terminates for some unknown reason to me.
Arkon: So I HAD to call ExitProcess and finish it, otherwise my process will hang.
Arkon: But now what I’m going to do is raising a silent exception
Matthew: Just blow away the SEH chain and trigger an INT3.
Arkon: It will eliminate the string “ExitProcess” and the GetProcAddress code for it as well.
Matthew:
MOV FS:[0], 0xFFFFFFFF
INT3
Matthew: BAM! Instant process death…
Arkon: This is too long.
Matthew:
PUSH 0
POP FS:[0]
Arkon: Nah
Matthew: XOR ESP, ESP might also do the trick
Arkon: LOL!!!
Matthew:
XOR ESP, ESP
PUSH EAX
Arkon:
XCHG EAX, ESP
PUSH 0
Arkon: Wait I’m stupid, push 0 is 2 bytes long.
Arkon:
XCHG EAX, ESP
PUSH EAX
Arkon: 2 bytes ExitProcess OMFG
Matthew: You’re a maniac

Thanks to my idea and to Matthew Murphy, I got the new .EXE size to merely 384 bytes.
It seems to be 99% usage of all spared room in the file…
If you even dare looking at this .EXE, you are crazier than me,
well – I wrote it, but you will have to understand it.
This is only one trick, there are way more undocumented tricks to explore and to learn from!

Check it out here:
http://ragestorm.net/tiny/tiny.exe

Gil Dabah
arkon@ragestorm.net