This is a post that was of great use to me written by injx on funender, it seems they are no longer hosting it however. Re-uploading for archival purposes.

Introduction

This article will attempt to explain why certain angles have to be used when strafe-jumping, and why strafe-jumping is necessary in the first place. It is aimed at those who already have a practical knowledge of strafe-jumping, and wish to know more about what is really going on. Although this article is based on Quake 3, the theory may be applied to many games, especially those based on Quake engines.

If you enjoyed this article, you may be interested in its sequel, Circle-Jump Theory COMING SOON

Firstly, you should know that there is one important difference between standing on a surface and being airborne, that is a surface has friction. Therefore if you are in contact with a surface and you stop providing movement (i.e. release all keys) then the frictional force will decelerate your movement to zero. In the air there is no friction, and so as long as you are not in contact with another object, when you release all keys your speed will remain constant.

In-game, a player has control of two key things: their orientation, and the movement keys being pressed. The movement keys can provide acceleration; the combination of movement keys, and the orientation of the player, determines which direction the player wishes this acceleration to be applied in.

For example, by holding Forwards and Right Strafe, the player’s acceleration vector, a, looks like this:

It is this acceleration, provided by the movement keys, which gives the player a change in velocity, which ultimately changes his position.

However, the Quake 3 engine tries to limit your ‘speed’ to 320ups by the server variable g_speed. The engine doesn’t allow you to accelerate past this 320ups in any one direction. Indeed, if you are travelling through the air at 320ups (or greater) and you hold the Forwards key (while facing the direction of travel) nothing will happen, because the engine is enforcing this limit, whether you are running or flying. So you have to use strafe-jumping to accelerate past 320ups.

Before I go any further, I will remind you of the following definitions:

• _Vector = A quantity which has both a size and direction.
• Velocity = A vector consisting of speed and direction of speed.
• Acceleration = The rate of change of velocity with time. Therefore it is also a vector. The acceleration accounts for both the change in speed, and change in direction of the velocity._

So let’s look at what happens when you are strafe-jumping. In all techniques, you need to be in the air at all times to avoid the friction caused by surfaces. This is the reason why players repeatedly jump, and this repeated jumping is known as bunny-hopping.

The first example technique is of standard single-beat strafing.

There are two air ‘modes’ involved in single-beat strafing, one being a mirror image of the other. In both modes, the player is orientated at an angle to the direction of travel. We shall call this angle theta, θ. At the same time, the player is holding Forwards and either Left Strafe for the left mode, or Right Strafe for the right mode. This results in the following situation.

The black arrow is the velocity vector, which illustrates the direction in which the player is currently moving.
The blue arrow is the orientation of the player (the direction in which you are looking).
The red arrow is the acceleration vector.

To perform the technique, the player quickly switches between modes (called an ‘air-change’) and continues alternating in this fashion by air-changing at (usually) regular intervals, usually in time with a jump.

Now keeping this in mind, let’s look at the other distinctive strafing technique: half-beat strafing. You will see that half-beat strafing is actually the same thing as single-beat strafing, it’s just another way to perform it.

Like single-beat, there are two air modes in half-beat. For lack of better terms, I shall name them ‘first mode’ and ‘second mode’.

The first mode is exactly the same as the ‘left mode’ from single-beat. The second mode appears a little strange at first. In this mode, the player is again orientated to the left of the direction of travel, by a small angle, which I have named angle lambda, λ. At the same time, the player is holding Right Strafe only.

Now if you look back at the single-beat diagrams and compare them with these half-beat diagrams, you can see that the acceleration vectors (red arrows) are exactly the same in both techniques! There is a red arrow to the left in both the strafing techniques followed by one to the right. Plus, these acceleration vectors are all at the same angle to the velocity (use your imagination if necessary).

Indeed, it’s possible to strafe in a number of ways, by using any combination of keys-presses and orientations in order to apply acceleration vectors in the way illustrated above. They are all equivalent, although some are more difficult to humanly perform than others.

Now let’s look at why this angle between our velocity and acceleration is significant. We already know that the engine won’t allow a player to gain speed in the direction of travel using the movement keys. However, we CAN gain speed in another direction, as long as our velocity’s component is less than 320ups in that specific direction.

So when we try to apply an acceleration at some angle to the velocity, we will be allowed to accelerate provided that the component of our current velocity in the proposed direction is less than 320ups. Mathematically, this is as follows.

Let’s call this angle between our velocity and acceleration angle delta, δ.

The component of the velocity in the direction of the acceleration is given by

.

This can be thought of as the projection of the velocity onto the direction of a.

As described above, the condition for acceleration to be allowed is

.

Note that when is negative, this means you are applying an acceleration in a direction at more than 90º to the velocity, which means you are effectively opposing your current velocity, a braking effect*.

The size of the acceleration applied, a, is a constant, independent of the angle at which it is applied (in the allowed region). This is defined by the engine in the same way that jump velocity and friction (etc.) are defined. However there is one special case which is an exception to this rule. If your is less than 320 but still very close to 320, applying the usual constant acceleration for a single frame would be enough to take you over 320ups in that direction. This is something the engine checks for, and if the situation exists, the applied acceleration will be only enough to take you up to the 320ups limit (so it would be ), and not beyond. However, the range of angle delta at which this situation exists is very small.

The acceleration causes a change in the total velocity, which is made up of a change in speed and a change in direction (remember that velocity is a vector). Although the amount of acceleration, a, is a constant, the direction that it is applied in dictates how much of this acceleration goes into changing the speed, and how much goes into changing the direction. In strafe-jumping it is the change in speed that we are interested in maximising, in an increasing fashion.

The way to achieve this maximum increase in speed is by applying the acceleration so its direction is as close to that of the velocity as possible, i.e. so the angle delta is as small as possible. This will mean that more of the acceleration goes into increasing our speed, and less goes into affecting the direction. The limiting condition gives a minimum angle delta of

.

However in order to gain the full acceleration, a, we need the angle to be a bit larger, so we avoid the special case mentioned above. Therefore the optimal angle is the smallest angle at which we receive the full acceleration, a, which is given by

.

As you can see, this optimal angle is dependent on the speed, v. This means that the optimal angle increases as you speed up, tending towards 90º at infinity.

Now that we know how acceleration is applied, we can look at the effect it has on the velocity, and the new velocity that results.

This acceleration, a, causes the current velocity, v, to change and produces a resultant velocity, r. We can use basic trigonometry to calculate the size and change in direction of the resultant velocity. The change in direction also illustrates why strafe-jumping can cause the player to ‘drift’ to one side if the strafing is not consistent.

The results of these calculations are here for the mathematically-gifted; however it’s not necessary to understand the following. From now on I shall use the parameter s to refer to the value of g_speed. First let’s look at the resultant speed after one frame. Note that there are three regions where acceleration is applied differently and hence the resultant speed is given by the following piecewise function.

The acceleration per frame, a, is defined (for air) by the engine as

,

where T is the frame-time in seconds. So for a constant 125fps framerate and standard g_speed of 320, then ups per frame.

The best way to interpret this is graphically. Here is a graph of the speed gained in a single frame, as a function of the applied angle delta.

Although this graph looks triangular, the two curves are not actually straight lines, but as you can see, for all intents and purposes they can be thought of as straight lines. Also note that the spacing between the minimum and optimal delta angles has been exaggerated in the graph, and so the increase in speed drops off very quickly as angle delta is decreased from its optimal value.

This makes it highly important to ensure that any applied angle delta is not too small. It’s not so bad if the angle is a little larger than optimal, but if it is smaller than optimal, the consequences are much greater. Also remember that both the minimum and optimal angles are velocity-dependent, so they both move closer to 90º (and closer to each other) as the velocity increases. During normal strafe-jumping these two angles are separated by less than 0.3°, so you can imagine how steep that part of the graph above really looks. There is, therefore, a very fine line between an optimal and zero speed increase.

If we apply an optimal angle delta, we get a resultant velocity of

,

which we can use to graph the maximum increase in speed per frame:

This graph illustrates how you cannot increase your speed as much at high velocites as you can at lower velocities.

Now we shall look at the change in direction. Let angle phi-one, φ₁, be the change in direction due to one frame of acceleration, at our optimal delta angle.

When strafing, the direction in which you are travelling is always changing. However, you cannot see the direction that your velocity is pointing in, and it’s difficult to guess accurately just by looking, so it can be very difficult to apply the optimal angle delta unaided.

It is much more useful to know the angle that we must apply relative to the overall direction in which we are trying to move in, e.g. from the beginning of a strafe pad lane to the end. I shall refer to this direction as the ‘direction of overall motion’.

To do this, we need to consider how much our velocity direction changes from one bunny-hop to the next. Let angle phi, φ, be the total change in direction caused by strafing between air-changes.

If we analyse the change in direction per frame, we see that not only is it small, but it also doesn’t change much over the period between air-changes, provided that the velocity is greater than about 600ups. This is useful to us, since 600ups is roughly the boundary between the end of a circle-jump, and the beginning of strafe-jumping. This is also the reason why the technique used for circle-jumps needs to be different to strafe-jumping.

We can use this to gain an expression for the change in direction between air-changes.

Phi is the change in direction between air-changes. N is the number of frames between air-changes. is the average change in direction per frame. [Using standard gravity (800) and 125fps, there are about 88 air-frames between bunny-hops.]

Therefore we can take this change in direction into account, and specify the strafing angles relative to the fixed direction of overall motion, rather than giving them relative to the velocity direction, which is always changing.

First let’s define angle alpha, α, as the angle between the direction of overall motion and the optimal acceleration direction, at an air-change.

Then we can go on to apply this to the different strafing techniques.

The first strafing angle I shall call angle epsilon, ε. This is the angle that is used to implement an optimal angle theta, used in single-beat strafing and for the ‘first mode’ of half-beat. (Here the orange arrow is the direction of overall motion)

Angle epsilon is thus,

.

If we look at the graph of angle epsilon, we can see that the angle increases as we speed up.

The other strafing angle I shall call angle kappa, κ. This is the angle that is used to implement an optimal angle lambda, used for the ‘second mode’ of half-beat.

Angle kappa is thus,

Looking at the graph of angle kappa, we can see that angle kappa becomes smaller as we speed up, and is smaller in general than angle epsilon.

In short, the strafing angle for single-beat (epsilon) begins at about 22º and increases. It’s about 33º at 1000ups. The half-beat angle (kappa) begins at about 23º and decreases. It’s about 12º at 1000ups.

* There is a small angle by which angle delta can exceed 90º and still result in a speed increase. The maximum angle delta is given by

.

This is the boundary between a speed increase and a speed decrease.

This semester at RPI I’m taking the class “Modern Binary Exploitation”. This post will detail how I reversed and cracked the rpisec_nuke binary.

Understanding rpisec_nuke

Running the binary shows us 3 options, KEY 1, KEY 2, and KEY 3

KEY 1 is seemingly the most simple, it asks us for a launch key, and then tries to authenticate with that.

KEY 2 looks more complicated, it askes us for an ‘AES-128 CRYPTO KEY’, a data length, and the data to encrypt.

KEY 3 is presumably to be the most complicated. it starts by asking us to confirm the launch session, which is found at the top of the banner, then it gives us a challenge and asks for a response.

Unlocking KEY 1

After some time in IDA I found a fantastically simple bug that lets us get through all the authentication steps. If I input null bytes then it stops reading with length 0, with this the strncomp passes since all of the ( zero ) characters were matches.

Unlocking KEY 2 and determining PRNG

After spending a bunch of time in IDA looking through two, I couldn’t find the vuln. I gave up and went to key three. The first thing I noticed is that if you fail the launch session on the first time you open three it frees that struct on the WOPR. In GDB I could see that going back into two after this occurance causes it to allocate the struct right on top of where three’s free’d one was. If I enter in garbage on two and then go back to three the challenge that I see will contain the password for two xor’d with random integers.

The first step here was to figure out the prng seed. It was easy to find using IDA that it was seeded with the current time, and since in key three they give us the time of access we can use this as a reference point. If I just enter new lines during key two then when I get the key three, the first line of the challenge after uxoring should be

0a00000000000000000000000000000000

I wrote a loop to keep trying times lesser than the time output in key three until it was able to unxor to this value. Once I had this I knew the prng seed and could take advantage of any random numbers in the program. I also used this seed to unxor key two which gave me the password in plain text :) Entering this key in unlocks the level.

key2 = 4e96e75bd2912e31f3234f6828a4a897

Unlocking KEY 3

At this point I can guess random numbers. I spent some time looking at what the challenge actually does: Each time you open key three it xors the challenge with random numbers, then xors the diagonal 4 bytes at a time with 4 bytes of the password. when it checks your challenge it does the same thing agian. since I already can undo the random number xor, figuring out the password was as simple as unxoring the random numbers.

key3 =
90357303000000000000000000000000
00000000412ef8220000000000000000
0000000000000000cd10e79800000000
000000000000000000000000760491a6

To unlock the level I simple xor the challenge with the next 16 random numbers and also with the block above.

Programming Nuke86

The first thing I see when pressing the almighty 4 is a prompt asking me for the targetting code. After I give my input nuke86 tells me the checksum and then fails. The first thing to do is to figure out how to pass this step. In IDA I see that the checksum is compared against the xor of all three key flags which represent whether or not you have unlocked that key.

checksum = 0xCAC380CD ^ 0xBADC0DED ^ 0xACC3D489
checksum = 0xDCDC59A9

Also in the compute_checksum function I see that the checksum is just the composite of my input xor’d 4 bytes at a time. I played around with my input until I was able to get it to match 0xDCDC59A9 This showed me “PROGRAMMING COMPLETE”. When I then type launch it shows me mission failed shutting down, etc. Now it’s time to really learn how to program this thing.

In IDA launch_nuke reveals the “programming language” used by nuke86. Here’s a mapping of the instructions:

R = Reprogram Nuke
D = Compare to DOOM and DISARM, if DOOM then detonate, if DISARM, then disarm.
E = Compare to END, end the program.
I = Increment the "program pointer"
O = Output the "Targetting status code" which is relative to where the "program pointer" is
S = Set the character at the "program pointer" to the next character

With this it’s very easy to write a program to detonate on general doom, just use S and I to write it in, then type DOOM to blow it up

The exploit was pretty trivial to find, if I just keep typing I, then the “program pointer” goes way overboard and gives me write access to the function pointers in the struct namely the detonate_nuke pointer. So I can just I until I’m there, then put in my rop chain and DOOM to detonate. I tested this using strace to see if I can set the real program pointer to 0x41414141 and I was successful.

Since I already have a pointer to the WOPR I can just use that to point to where /bin/sh is input within the nuke86 program, and all I have to do is put in my rop chain after I do all my offsetting with I. I did not actually do the rop chain but I have a high suspicion that it will be the same execve setup that we’ve done many times.

My Auth Program can be found here: auth.py

My Key2 && Key3 inital finders can be found here: keys.py

This semester at RPI I’m taking the class “Modern Binary Exploitation”. This post will detail how I reversed and cracked the tw33tchainz binary.

Understanding tw33tchainz

When we run tw33tchainz the first thing we are presented with is some art and a prompt for our username, and salt. upon entering these values we are given a generated password.

afterwards we are given a menu with 4 options, labelled 1, 2, 4, and 5. the option labelled ‘3’ is missing. Naturally I entered into the prompt 3, then I was asked to enter a password, my guess was incorrect.

Option 1 lets us enter a tweet which gets stored somewhere, and is appended to the penguin’s beak the next time the menu is output to our term.

Option 2 lets us view all of our previous tweets.

Option 4 simply prints out the ascii art that’s on top of the menu. ( looks like a mallet smashing a sombrero, or maybe a bird? nah… )

Option 5 quits the program.

Digging deeper

I decided a good first step would be to map out all the functions defined in the binary, I did this through the use of gdb

project1@warzone:/levels/project1$ echo "disas main" | gdbpeda tw33tchainz | grep "call" | grep -v "@plt"
   0x08048e7f <+155>:	call   0x8048fac <print_banner>
   0x08048e84 <+160>:	call   0x804886c <gen_pass>
   0x08048e89 <+165>:	call   0x8048923 <gen_user>
   0x08048eb4 <+208>:	call   0x8048fac <print_banner>
   0x08048eb9 <+213>:	call   0x8048a34 <print_menu>
   0x08048f27 <+323>:	call   0x8048c0e <do_tweet>
   0x08048f2e <+330>:	call   0x8048bcd <view_chainz>
   0x08048f35 <+337>:	call   0x8048d40 <maybe_admin>
   0x08048f48 <+356>:	call   0x8048fac <print_banner>
   0x08048f4f <+363>:	call   0x8048fc1 <print_exit>

I then ran the same command for each function in the output.

a quick checksec shows us that RELRO isn’t full, therefore we can overwrite to the GOT.

CANARY    : disabled
FORTIFY   : disabled
NX        : disabled
PIE       : disabled
RELRO     : Partial

From here I wanted to see if there were any vulnerable printf statements that would let me make arbitrary memory writes.

I was looking for printfs that touched user input, in the entire program there are only two locations where these reside: print_menu, and view_chainz. I started by going through each printf statement in print_menu and surely enough there is printf which takes the previous tweet and uses it as the first argument, a cardinal sin.

Unfortunately the block of code containing the vulnerable printf looks like this:

0x08048a84 <+80>:	movzx  eax,BYTE PTR ds:0x804c0a8
0x08048a8b <+87>:	test   al,al
0x08048a8d <+89>:	je     0x8048ab4 <print_menu+128>
0x08048a8f <+91>:	mov    DWORD PTR [esp],0x8049143
0x08048a96 <+98>:	call   0x80485d0 <printf@plt>
0x08048a9b <+103>:	lea    eax,[ebp-0x19]
0x08048a9e <+106>:	mov    DWORD PTR [esp],eax
0x08048aa1 <+109>:	call   0x80485d0 <printf@plt>

the first three lines there check to see if you are admin. If 0x804c0a8 is 0 then you are not admin, if either of the bottom 2 bytes are non-zero then you are considered an admin.

the vulnerable printf cannot be reached unless we’re set to admin. So the next step is to figure out what the correct password for option 3 is.

taking a look at the gen_pass function I see that it simply reads 16 bytes from /dev/urandom, these 16 random bytes are the password required for option 3.

gen_user does the following

1. memset the salt with 16 bytes of 0xba
2. memset the user with 16 bytes of 0xcc
3. read 16 bytes into user
4. read 16 bytes into salt
5. call the hash function

hash then creates the generated password like so

1. byte wise addition between the salt and the secret password
2. xors that new value with the user

then later down in gen_user it calls print_pass which outputs the generated password as hex.

in print_pass

0x08048851 <+52>:	mov    DWORD PTR [esp],0x8049070
0x08048858 <+59>:	call   0x80485d0 <printf@plt>

value at 0x08049070

0x08049070 : 25 30 38 78 25 30 38 78 25 30 38 78 25 30 38 78   %08x%08x%08x%08x

given this, with a carefully chosen user and salt, we can easily recover the secret pass from the generated pass that we are given.

I chose to use 15 of 0x01 for the user and 15 of 0xff for the salt, I’m using 15 instead of 16 because in gdb I saw that fgets adds a null terminator as the 16th byte in each.

with these values I know that when we’re adding the secret password to 0xff the value will overflow and be 1 less than the original value.

afterwards when we xor this with the value 0x01 that will turn even numbers odd, one greater than the original value, and odd numbers even, one less than the original value.

for example if the secret byte was 0x55, when that’s added to 0xff we end up with the value 0x54, which then turns back into 0x55 after we xor it with 0x01.

further if the secret byte was 0x56, when that’s added to 0xff we end up with the value 0x55, which turns into 0x54 after we xor it with 0x01.

this means that in our generated password, we simply add 2 to the even bytes, and leave the odd bytes unchanged. except for the last byte, which was null. The last byte remains unchanged from the secret password.

I wrote a python script which takes the generated password as a command line argument and returns the secret password.

decode_pass.py

Success!, now that we’re admin we have a menu option labelled 6, and more importantly, access to the vulnerable printf statement in print_menu

since tweets are limited to 16 characters, the format string for the exploit must be this length.

in gdb I noticed that the stack is actually misalighned by 1 byte so the first character of the format string will be used to realign it.

tweet="A"

This means we have 15 bytes remaining for an arbitrary write.

First thing’s first, we need the address to write to, this will consume 4 more bytes which leaves us 11 bytes for %x and %n to actually write the value.

With 11 bytes there is simply not enough room for enough %x tokens to get to the address on the stack, which means I’ll have to use direct parameter access. with all the required characters our tweet format looks like this

tweet="A....%???x%#$hhn"

…. will be the address

The only thing left is to determine what values to substitute for ???, and which parameter # will be.

looking at the stack I can see that # has to be 8.

when doing some test writes in gdb I can see that whatever value I put in for ??? will be written to memory as 5 higher than the original value which means I just simply subtract 5 from the value I want to write and then the correct value will be written. This works unless the value I want to write is less than 5 since I can’t write a negative number of bytes. To mediate this I simply add 256 to every value which lets it overflow cleanly into the correct value.

The final anatomy of a malicious tweet which writes the value 0x10 to the location 0x43434343 looks like this.

tweet="ACCCC%267x%8$hhn"

Now it’s just a matter of finding a location to write my shellcode, then writing it, overwriting exit to point to that location ( Thanks RELRO! ) and cat’ing the password :)

I used the execve(“/bin/sh”) shellcode found here

and formatted it to be more easily readable by my final script: binsh.hex

I wrote a python script to create the format string given the address to write to, the tweet number, and the value to write: get_tweet.py

and my final driver to input all this to the program, and cat the password is written in bash: driver.sh

Results

$ ./driver.sh
...
...
Enter Choice: m0_tw33ts_m0_ch4inz_n0_m0n3y

If you use urxvt and ssh chances are you’ve ran into the same issue as I have:

$ clear
'rxvt-unicode-256color': unknown terminal type.

As it turns out, it’s quite easy to fix. All you have to do is copy over your local terminfo to the server which is giving you the problem.

create the terminfo folders on user@remotehost:

mkdir -p ~/.terminfo/r/

copy over the terminal profile ( urxvt in my case ):

scp /usr/share/terminfo/r/rxvt-unicode-256color user@remotehost:.terminfo/r/

All new ssh sessions will support the terminal profile you added :)