1   13 September, 2020
  2
  3My submissions for r2wars 2020
  4
  5If I learnt one thing, it's that ARM is the future
  6
  7   [1]r2wars is a [2]CoreWar-like game thar runs within the radare2
  8   [3]ESIL virtual machine. In short, you have two programs running in a
  9   shared memory space (1kb), with the goal of killing the other and
 10   surviving as long as possible. r2wars was conducted as a part of
 11   [4]r2con2020.
 12
 13day 1
 14
 15   My first submission was an incredibly simple "bomber". All it does is
 16   write code to a location, jump there, and continue executing the same
 17   thing over and over.
 18mov eax, 0xfeebfeeb; just some bad jumps
 19mov ebx, eax
 20mov ecx, eax
 21mov edx, eax
 22mov ebp, eax
 23mov edi, eax
 24mov esp, 0x3fc
 25mov esi, 0x3fd
 26mov [esi], 0xe6ff60
 27jmp esi
 28
 29   Specifically, it writes 0xe6ff60, which is
 30pushal
 31jmp esi
 32
 33   effectively looping over and over. pushal is a very interesting x86
 34   instruction, that pushes all the registers and decrements the stack
 35   pointer esp by how many ever bytes were pushed. Nifty, especially if
 36   you're looking for high throughput (to bomb the address space). Here,
 37   it starts bombing from 0x3fc - 0x000 (and below, because there's no
 38   bounds checking in place), and ends up killing itself, since writing
 39   outside of the arena (0x000 - 0x400) is illegal.
 40
 41   Ultimately, this bot placed 7th out of 9 contestants -- an
 42   underwhelming outcome. I had to fix this.
 43
 44   day 1
 45
 46day 2
 47
 48   I sat for a second and recollected the different reasons for my bot
 49   getting killed, and the one that occurred the most was my bot
 50   insta-dying to bad instructions being written from 0x400 -- i.e. from
 51   near where I'm positioned. Nearly all competing bots write from bottom
 52   up, because pushal decrements the stack pointer. So the obvious
 53   solution was to reposition my initial payload way above, at 0x000. And
 54   of course, it goes without saying that this assumes everyone's using
 55   pushal (they are).
 56mov eax, 0xffffffff
 57mov ecx, eax
 58mov edx, eax
 59mov ebx, eax
 60mov ebp, eax
 61mov esi, eax
 62
 63check:
 64    mov edi, 0x000
 65    cmp [edi], 0
 66    jne planb
 67    mov esp, 0x400
 68    inc edi
 69    mov [edi], 0xe7ff6060; pushal, jmp edi
 70    jmp edi
 71
 72planb:
 73    mov edi, 0x3fb
 74    mov [edi], 0xe7ff6060
 75    mov esp, 0x3fa
 76    jmp edi
 77
 78   I also added a (pretty redundant) check to see if the stuff at edi was
 79   0, since the entire arena is initially 0x0. My reasoning, albeit
 80   flawed, was that if it wasn't 0, then it was unsafe to go there. In
 81   hindsight, it would've been safer, since it's already been written over
 82   by somebody. In any case, planb never got executed because of what I'd
 83   mentioned earlier -- everyone writes from 0x400. Or anywhere above
 84   0x000, for that matter. So I'm relatively safer than I was in day 1.
 85
 86   These changes paid off, though. I placed 4th on day 2, out of 13
 87   contestants! This screenshot was taken on my phone as I was eating
 88   dinner.
 89
 90   day 2
 91
 92   All wasn't well though -- I still lost 4 matches, for the reasons
 93   below:
 94    1. I'd get snuffed out before my bomb wave from 0x400 would reach the
 95       opponent.
 96    2. I'd end up bombing myself without hitting anyone on the way up.
 97
 98day 3
 99
100   I needed to add some checks to prevent killing myself in the process of
101   bombing.
102mov eax, 0xffffffff
103mov ecx, eax
104mov edx, eax
105mov ebx, eax
106mov ebp, eax
107mov esi, eax
108
109mov edi, 0x000
110mov esp, 0x400
111mov [edi], 0x20fc8360
112mov [edi+4], 0xff600374
113mov [edi+8], 0x0400bce7
114mov [edi+12], 0xe7ff0000
115jmp edi
116
117   If you noticed, the initial payload I'm writing to the address at edi
118   is a bit more complex this time -- let's break it down.
1190x20fc8360
1200xff600374
1210x0400bce7
1220xe7ff0000
123
124   This translates to:
12560                pushal
12683 FC 20          cmp    esp, 0x20
12774 03             je     9
12860                pushal
129FF E7             jmp    edi
130BC 04 00 00 00    mov    esp, 0x400; <- 0x9
131FF E7             jmp    edi
132
133   I check if the stack pointer is 0x20 (decrements from 0x400 due to
134   pushal); if yes, reset to 0x400, else continue looping. This prevented
135   me from writing myself over, and also resets bombing from 0x400 --
136   better chance of hitting someone we missed in our first wave.
137
138   Sounds good? That's what I thought too. Day 3 had a bunch of new bot
139   submissions (and some updated submissions), and a lot of them checked
140   0x000 for existence of a bot, effectively recking me. I placed 8th out
141   of 14 contestants, with 7 wins and 6 losses. Tough day.
142
143   day 3
144
145day 4: the finals
146
147   I spent a lot of time refactoring my bot. I tried all kinds of things,
148   even reworked it to be entirely mobile using the pushal + jmp esp
149   trick, but I just wasn't satisfied. In the end, I decided to address
150   the problem in the simplest way possible. You're checking 0x000? Okay,
151   I'll reposition my initial payload to 0xd.
152
153   And this surprisingly tiny change landed me in 4th place out of 15
154   contestants, which was way better than I'd anticipated! The top spots
155   were all claimed by ARM, and naturally so -- they had a potential
156   throughput of 64 bytes per cycle thanks to stmia, compared to x86's 32
157   bytes. Pretty neat!
158
159   day 4
160
161links and references
162
163     * [5]Anisse's r2wars 2019 post
164     * [6]Emile's intro to r2wars
165     * [7]How not to suck at r2wars
166     * [8]r2wars: Shall we play a game?
167     * [9]Shell Storm's online (dis)assembler
168     * [10]radare2
169     * [11]r2wars game engine
170     * [12]Anisse's bot workspace
171     * [13]My bot dev workspace
172     * [14]r2con YouTube
173
174closing thoughts
175
176   This was my first ever r2wars, and it was an incredible experience. Who
177   woulda thunk staring at colored boxes on the screen would be so much
178   fun?! So much so that my parents walked over to see what all the fuss
179   was about. Shoutout to [15]Abel and [16]pancake for taking the time out
180   to work on this, and especially Abel for dealing with all the last
181   minute updates and bot submissions!
182
183   All things said, mine was still the best x86 bot -- so that's a win. ;)
184
185References
186
187   1. https://github.com/radareorg/r2wars
188   2. http://corewars.org/
189   3. https://radare.gitbooks.io/radare2book/content/disassembling/esil.html
190   4. https://rada.re/con/2020
191   5. https://anisse.astier.eu/r2wars-2019.html
192   6. https://www.tildeho.me/r2wars/
193   7. https://bananamafia.dev/post/r2wars-2019/
194   8. https://ackcent.com/r2wars-shall-we-play-a-game/
195   9. http://shell-storm.org/online/Online-Assembler-and-Disassembler
196  10. https://github.com/radareorg/radare2
197  11. https://github.com/radareorg/r2wars
198  12. https://github.com/anisse/r2warsbots
199  13. https://github.com/icyphox/r2wars-bots
200  14. https://www.youtube.com/channel/UCZo6gyBPj6Vgg8u2dfIhY4Q
201  15. https://twitter.com/sanguinawer
202  16. https://twitter.com/trufae