ROT Cipher Bruteforcer in Assembly x64
In this text, I will show an implementation I made a couple of years ago in x64 assembly of a ROT Cipher brute forcer — also known as the Caesar Cipher. The code was not made with the intention of being the smallest or most optimized possible. This is just the first way I found to build the program (and I know there are more efficient ways to do it), and writing the text was a “documentation” of the code and part of my learning in assembly. Therefore, do not use the code for academic purposes unless you are sure of what you are doing.
ROT
The ROT (from “rotate”) is one of the oldest and best-known — and simplest — cryptographic algorithms in the world. The algorithm was originally used for the exchange of secret messages between armies during the reign of Julius Caesar, which is where the cipher gets its name.
It is a very simple substitution cipher based on rotating the alphabet by a certain index n, where n ∈ ℕ, n <= 26. Consider the following alphabets:
Let’s consider the following alphabets:
Original: ABCDEFGHIJKLMNOPQRSTUVWXYZ
ROT 0: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Here, the cipher index is 0. In this case, there is no encryption because the cipher alphabet is identical to the original. However, let’s consider the following alphabets with the index being 1:
Original: ABCDEFGHIJKLMNOPQRSTUVWXYZ
ROT 1: BCDEFGHIJKLMNOPQRSTUVWXYZA
Note that now the cipher alphabet has shifted left by one position, so the letter A from the original alphabet is now mapped to the letter B in the cipher alphabet, B is mapped to C, and so on until Z, which is mapped to A, completing the cycle.
Encryption can now be done by remapping all the letters of the text to be encrypted to the corresponding letters in the cipher alphabet. So, if we want to encrypt the word “onion”, we just look for the letter “o” in the original alphabet and note the letter it maps to in the cipher alphabet, and then do the same for the letters “n”, “i” and “o”. In this case, we get “pojpo”.
To decrypt, just do the same thing, but rotate to the right. Or, since the alphabet is cyclic, just do the same thing with the index 26-n, where n is the original index.
ROT13
The most famous use case is ROT13 since rotating by 13 positions takes you to the middle of the alphabet. In this case, to decrypt, you can apply the same algorithm with the same index (13), because 13+13=26 (the number of letters in the alphabet). Thus, the ROT13 function is its own inverse, meaning ROT13(ROT13(x))=x. For example:
ROT13(“good night”) = “tbbq avtug”
ROT13(“tbbq avtug”) = “good night”
It’s clear that ROT has no current cryptographic applications, as there are very few combinations (at most 25), making it extremely easy to test all combinations until we find the one that decrypts the original message. This brute force test, written in assembly, will be presented here.
How the program will work
The aim is to write a command-line program that can receive inputs in two ways: through stdin or via arguments. In the first case, the program will directly receive the string to be tested (e.g., via pipe, as in echo -n tbbq avtug | ./rotbrute). In the second case, the program will receive the name of a file to be opened, and its content will be tested.
We need to create the following routine (shown in pseudo-code), where rotbrute is the main function we will write later.
if(argv.count > 1)
if(file = open(argv[1]))
var content = read(file);
else
exit "Error opening file";
else
if(stdin.length > 0)
var content = stdin;
else
print "Usage: echo -n 'string' | ./rotbrute"
rotbrute(content)Reading the file
The first step is to check if any arguments were passed and, if so, try to read the content of the passed file.
When a program starts, the first thing at the top of the stack is a numeric value containing the number of arguments passed to the program. This value will always be at least 1, as the first item is always the program’s name. We need to check if this value is greater than or equal to 2 to determine if an argument was passed (the name of the file to be opened).
Since this value is at the top of the stack, we can use the pop instruction to move it to a register and use the cmp instruction to check if the value is greater than or equal to 2. If it is, we will jump to the routine that attempts to open the file. Otherwise, we will call the routine that checks if there is input from stdin.
global _start
section .text
_start:
pop rax ; stores the number of arguments
cmp rax, 2 ; compares this number with 2
jge _hasArgument ; if it is >=2, tries to open the file
call _checkStdin ; if not, checks stdin
jmp _begin ; then jumps to _beginNote that if the program doesn’t receive an argument, it will check stdin and then jump to the _begin routine, which hasn’t been defined yet. This routine, as the name suggests, will start the bruteforce process, and when we enter it, we will have already loaded the string to be tested. The pointer to this string will be in rdx, and the number of bytes in the string will be in rax, regardless of whether it was loaded via file reading or stdin. This will be important later.
Since we’ll need to use various system functions, I defined the constants for each syscall at the beginning of the code. You can find the syscall numbers in the file /usr/include/x86_64-linux-gnu/asm/unistd_64.h.
%define READ 0
%define WRITE 1
%define OPEN 2
%define FSTAT 5
%define MMAP 9
%define EXIT 60
%define MREMAP 25Now, we need to create the code that tries to open the file passed as an argument. After the first item on the stack, which is the number of arguments passed, are the actual arguments. Before that, however, let’s create a routine and a macro for opening the file. In the open() syscall, three arguments are passed: the path of the file to be opened, the open flags, and the permissions.
%macro open 3 ;open filepath, flags, perm
push %1 ;filepath
push %2 ;flags(ro)
push %3 ;perm
call _open ;call the open routine
add rsp, 24 ;clear the stack
%endmacro
_open:
push rbp ;create a new stack frame
mov rbp, rsp
mov rax, OPEN
mov rdx, [rbp+16] ;perm
mov rsi, [rbp+24] ;flags
mov rdi, [rbp+32] ;filepath
syscall
leave
ret ;save the result in rdiTo get the first argument, we need to reach rsp+8.
_hasArgument:
mov rax, [rsp+8] ; gets argv[1] from the stack
push rax ; saves it on top of the stack
open rax, 0, 0 ; opens the file with read and write permissions
cmp rax, 0 ; compares the opened file descriptor with 0
jl _notfound ; if it's less than zero, there's an error
push rax ; if not, saves it on the stackThe _notfound routine simply prints an error message and exits the program.
_notfound:
write 1, error, 15
exitLet’s also define the strings for usage instructions and newline in the .data section of the executable.
section .data
usage: db 'Usage: ./rotbrute [filename]', 0
error: db 'File not found', 0
nl: db 0xA, 0After opening the file, we need to allocate memory space to be filled with its content. We will use the mmap syscall, which takes the number of bytes to allocate. To find out the number of bytes to allocate (the size of the opened file), we will use the fstat syscall, which returns file information, including its size. Here are the macros and routines for mmap and fstat:
%macro mmap 2 ;argument: size of the map
push %1 ;address (let the kernel decide)
push %2 ;size
push 0x2 ;prot (PROT_WRITE)
push 33 ;flags (MAP_SHARED|MAP_ANONYMOUS)
push -1 ;fd (ignore)
push 0 ;offset (0, due to MAP_ANONYMOUS)
call _mmap
add rsp, 48 ;clear the stack
%endmacro
%macro filesize 1 ;filesize fd
mov rdi, %1 ;save the file descriptor in rdi
call _filesize
%endmacro
_filesize:
push rbp ;new stack frame
mov rbp, rsp
sub rsp, 192 ;reserved for stat() return
mov rax, FSTAT ;constant with syscall
mov rsi, rsp ;statbuf
syscall
mov rax, [rsp+48] ;file size will be here on the stack
leave
ret
_mmap:
push rbp ;new stack frame
mov rbp, rsp
mov rax, MMAP ;constant with syscall
mov r9, [rbp+16] ;offset
mov r8, [rbp+24] ;fd
mov r10, [rbp+32] ;flags
mov rdx, [rbp+40] ;prot
mov rsi, [rbp+48] ;length
mov rdi, [rbp+54] ;addr
syscall
leave
retNow, we can use the filesize macro and pass the file descriptor of the file whose size we want to know. This file descriptor is already saved in rax, which contains the return from the open() call.
filesize rax ; returns the size of the file
cmp rax, 0 ; compares the size with 0
jz _exit ; exits if the size is 0The _exit routine is very simple; it's just a call to the exit() syscall:
_exit:
mov rax, 60 ; syscall code for exit()
mov rdi, 0 ; exit code
syscallNow we have the file size saved in rax. We can pass this size to our mmap macro to allocate the necessary size in a memory buffer. After this, we can read the file content and save it in this new buffer.
push rax ; saves the file size (k) on the stack
mmap 0, rax ; maps k bytes in memoryThe mmap returns the address where the new buffer was created. With this address (in rax), the file descriptor of the file to be read (on the stack), and the buffer size (file size, also on the stack), we can call the read() function to read the file content into the new buffer:
mov rcx, [rsp] ; file size
mov rbx, [rsp+8] ; file descriptor
mov rdx, rax ; pointer to the created buffer
push rdx ; saves the pointer on the stack
push rdx
read rbx, rax, rcx ; reads the file into the buffer
mov r9, rax ; saves the number of bytes read in r9
pop rdx ; restores the pointer to the bufferAt the end of this segment, rax will contain the number of bytes read (i.e., the file size), and rdx will contain the pointer to the buffer with the file content.
Reading from stdin
We wrote the code that reads the content of a file passed via argument (e.g., ./rotbrute file.txt). Now, we need to write the code that reads stdin passed by the user (e.g., echo -n string | ./rotbrute). At the beginning of the main routine, _start, we already declared a call to the _checkStdin function, which we will write now.
The function will have the following flow (in pseudo-code):
buf = mmap(x); // maps x bytes in memory
r = read(STDIN, buf, x); // reads x bytes from STDIN into this buffer
if(r > 0) // number of bytes read
while(r != 0) { // while there is content to read
buf = mremap(buf, x); // increases the buffer size by x bytes
r = read(STDIN, buf, x); // reads another x bytes into the buffer
}
else
print "Usage: echo -n 'string' | ./rotbrute";In other words, we will create a buffer in memory with a size x and read x bytes from STDIN into this buffer. If the size of the content read is greater than zero, the function remaps the buffer to increase its size and tries to read more content from STDIN until it is empty. Otherwise (i.e., if there is no STDIN), the function prints the usage instructions.
_checkStdin: ; check if len(stdin) > 0
push rbp ; new stack frame
mov rbp, rsp
mmap 0, BUF ; allocate the buffer to receive STDIN
mov r14, rax ; save the buffer address
mov r15, rax ; save again as it will be incremented
push rax ; save the mapped memory address
read 0, rax, BUF ; try to read from STDIN
cmp rax, 0 ; if more than 0 bytes are read
jnz _hasStdin ; then there is STDIN
jmp _usage ; if not, print usageHere, we call the mmap macro and pass BUF as a parameter. This would be the size of the buffer to be allocated. We need to define this constant BUF at the beginning of the code; in this case, it will be 256 bytes (i.e., STDIN will be read in blocks of 256 bytes until it ends).
%define BUF 256After calling mmap, rax will contain the memory address of the new buffer created. We then save this address in two registers, r14 and r15. The second will be altered during the function execution—it will be incremented by 256 bytes to create the new address where the next 256 bytes from stdin should be read. The first will be kept and moved to rdx at the end of the function (remember that at the end of this segment, we need rdx to be the pointer to the buffer containing the content to be tested). This mapped memory address is also saved on the stack to be referenced later.
We then call the read macro to read 256 bytes from stdin into rax, i.e., into the new buffer created with mmap. After calling the read function, the number of bytes read is saved in rax. We then compare rax with 0 to check if something was read. If it is greater than 0, then we have something in stdin and can jump to the _hasStdin routine. If not, then we jump to the routine that prints the usage instructions (_usage).
The _hasStdin routine will start the code responsible for reading stdin in 256-byte increments into the created buffer and increasing the buffer size as needed. To do this, we will use the mremap syscall, which takes the following parameters: the address of the memory to be resized, the old size, the new size, flags, and the new address. For flags, we will provide nothing. For the new address, we will also leave it as 0 so that the address remains the same. Here is the macro and the routine for this function:
%macro mremap 3
push %1 ; old address
push %2 ; old size
push %3 ; new size
push 0 ; flags
push 0 ; new address
call _mremap
add rsp, 40 ; clear the stack
%endmacro
_mremap:
push rbp ; new stack frame
mov rbp, rsp
mov rax, MREMAP ; syscall code
mov r8, [rbp+16] ; old address
mov r10, [rbp+24] ; old size
mov rdx, [rbp+32] ; new size
mov rsi, [rbp+40] ; flags
mov rdi, [rbp+48] ; new address
syscall
leave
retOnce the mremap macro and routine are defined, we can use it in our code. Initially, we will save the initial buffer size (256 bytes) on the stack. This size will be changed in each iteration of the loop, so this first push will act almost like an "initialization vector."
_hasStdin:
push BUF ; save the initial buffer size
_loop: ; read `stdin` every 256 bytes
; and increase the allocated memory size as needed
pop rcx ; old size
pop rax ; mapped memory address
mov rbx, rcx ; save the old size
add rcx, BUF ; new size = old size + BUF (256)
push rcx ; save the new size (will be retrieved later)
mremap rax, rbx, rcx ; remap (increase allocated memory size)Right after the _hasStdin routine, which saves the initial buffer size on the stack, we start the _loop routine, which, as the name indicates, will loop reading stdin until it is empty. Initially, we retrieve the current buffer size from the stack into rcx (which in the first iteration will be 256).
After that, we retrieve the mapped memory address by mmap into rax (which had been saved on the stack after calling this syscall). We then save the current buffer size in rbx and add BUF (256) to rcx, which now has the new size the buffer will have when reallocated. We save this new size in rcx and call our macro mremap rax, rbx, rcx, where the first argument is the old buffer address, the second is the old buffer size, and the third is the new size the buffer will have.
Now we can proceed and read stdin into this new buffer.
pop rcx ; retrieve the current buffer size
push rax ; mapped memory address
push rcx ; current buffer address
add r15, BUF ; increase the location where `stdin` will be read
read 0, r15, BUF ; read 256 bytes from `stdin` to the new buffer locationNote that the first instructions of the loop are pop rcx and pop rax. When the loop resets, it will pop two items from the stack into these registers. Since the mremap syscall will return the mapped memory address in rax, we can save it on the stack along with the current buffer size (which is in rcx) to be retrieved at the beginning of the next loop iteration. That's why we put rax and rcx on the stack in this order. After this, we can read another 256 bytes from stdin to r15+256, i.e., to the beginning of the empty part of the buffer (the part that was just remapped).
Now, we just need to check if the number of bytes read was 0. If it wasn’t, then we go back to the beginning of the loop to increase the buffer size and try to read another 256 bytes. If it was 0, then there are no more data to be read, and we can finish this function. Before finishing, however, we save the buffer size (the total number of bytes read) in rax. Remember that after loading the string to be tested, we need its size in rax and the pointer to it in rdx, as mentioned earlier and done in _hasArgument.
cmp rax, 0 ; compare the number of bytes read with 0
jnz _loop ; if different from 0, go back to the beginning of the loop
mov rax, rbx ; if not, move the final buffer size to `rax`
mov rdx, r14 ; move the start address of the buffer to `rdx`
leave
retPreparing for the brute force
As defined in _start, the program will first read the string to be tested—either by reading a file or by reading from stdin—and then jump to the _begin routine, which will start the brute force process. Initially, we will print the loaded string itself and then start the brute force function. To print this, we will define a macro for the write syscall, which takes three parameters: the file descriptor to which the content will be written, a pointer to the buffer containing the content to be written, and the size of the content to be written. Here is the macro and the routine:
%macro write 3
push %1 ; file descriptor
push %2 ; buffer
push %3 ; buffer size
call _write
add rsp, 24 ; clear the stack
%endmacro
_write:
push rbp
mov rbp, rsp
mov rax, WRITE
mov rdx, [rbp+16] ; buffer size
mov rsi, [rbp+24] ; buffer
mov rdi, [rbp+32] ; file descriptor
syscall
leave
retSince we have the size of the read string in rax and the pointer to it in rdx, we just need to call the write macro passing these registers as parameters and write the content to file descriptor 1, which is stdout, i.e., the terminal output. Additionally, we will save these values (the pointer and the size of the string) on the stack so they can be used within the brute force function.
_begin:
push rax
push rdx
write 1, rdx, rax ; print the passed string
write 1, nl, 1 ; print newline
jmp _bruteforceBruteforce
Now we can finally start writing the function that will bruteforce the passed string and return all 25 possible results of applying the ROT algorithm to it. The function will have roughly the following flow, both for uppercase and lowercase letters (in pseudo-code):
str = 'string read from the file or stdin';
charset = 'abcdefghijklmnopqrstuvxwyz'; // in the code, we will use the corresponding ASCII
i = 0; // start with index 0
while (i < 27) // loop for all 27 combinations
for (j = 0; j <= strlen(str); j++) // for each character in the string
if (str[j] == 'z') // if it is the last one (z)
str[j] = 'a'; // change to the first one (a)
else // if not
str[i] = charset[j + 1]; // add 1
i++; // next indexSo, for each index from 0 to 27, the code will loop through all the characters of the string and add 1 to it, based on the ASCII alphabet. For example, when the code finds the letter h, it adds 1 and returns i; when it finds the letter x, it adds 1 and returns y, and so on. The pseudo-code above is not 100% accurate because, as we will see, there are some other exceptions:
- If the character is
z, it will returna, - If the character is
Z, it will returnA, - If the character is a space or number, print it normally,
With that said, we can start:
_bruteforce:
push rbp ; new stack frame
mov rbp, rsp
mov rax, [rbp+8] ; address with the string to be tested
mov rbx, [rbp+16] ; string size
push rbx ; save the size for later
add rbx, rax ; address of the string + string size = end address
push rax ; will be popped at the end
mov rcx, 1 ; ROT indexAfter creating the new stack frame, we retrieve the string address (which is on the stack) to rax and its size (also on the stack) to rbx. We then add them together and save the result in rbx. This result is the pointer to the end of the string and will be used later to check if we have reached the end of the string.
Now, we need to check the exceptions mentioned. In short, if the current character is z or Z, the return needs to be a or A, respectively. If it is a space or a number, the return will be the space or the number itself.
_checkz:
cmp byte [rax], 0x7A ; check if the current character is 'z' (0x7A)
jnz _checkZ ; if not, check if it is 'Z' (uppercase)
mov byte [rax], 0x60 ; if it is 'z', set it to the char before 'a' (0x60 = `)Note that if the character is z, it will be changed to the character before a in the ASCII table. This happens because we will later add 1 to this character, so in this case, z will be converted to a, and the same goes for the uppercase Z. The checks here are done using the corresponding ASCII code of the character. To find it, just consult the ASCII table and get the hexadecimal value of the character.
The same is done for the uppercase Z:
_checkZ:
cmp byte [rax], 0x5A ; check if the current character is 'Z' (0x5A)
jnz _checkSpace ; if not, check if it is a space
mov byte [rax], 0x40 ; if it is 'Z', set it to the char before 'A' (0x40 = @)Checking if the character is a space:
_checkSpace:
cmp byte [rax], 0x20 ; check if the current character is a space (0x20)
jnz _checkNL ; if not, check if it is a newline
jmp _next ; if it is a space, jump to the nextNow, we need to make these two routines: the one that checks if the character is a newline and the one that jumps to the next character. We will do the latter after making the routines for checking numbers.
_checkNL:
cmp byte [rax], 0xA ; check if the current character is a newline (0xA)
jnz _checkNum0 ; if not, check if it is a number greater than 0
jmp _next ; if it is a newline, jump to the nextNow, the routines that check if the character is a number. In the ASCII table, numbers are between 0x30 and 0x39. So, to validate if the current character is a number, just check if it is in this range ([0x30–0x39]). For this, we will use the instructions jge (jump if greater than or equal to) and jle (jump if lesser than or equal to):
_checkNum0:
cmp byte [rax], 0x30 ; check if the current character is 0x30 (0)
jge _checkNum9 ; if greater than or equal to 0, check if it is <= 9
_checkNum9:
cmp byte [rax], 0x39 ; check if the current character is 0x39 (9)
jle _next ; if less than or equal to 9, jump to the next
add byte [rax], 1 ; if not, add 1 to the character (e.g., a+1 = b)Now we can jump to the next character and check if we have reached the end of the string. Remember that at the beginning of the function, we saved the end address of the string in rbx. Since in each iteration we add 1 to the current address (rax), to loop through all the characters of the string, just compare rax with rbx to know if we have reached the end of the string:
_next:
inc rax ; increment the current position by 1
cmp rax, rbx ; is the current position equal to the end?
jle _checkz ; if not, go back to the beginning of the loopAfter this loop ends, we can print the (de)ciphered string (which is currently at the top of the stack) and check if our index is less than or equal to 25 (and not 26, because the original string has already been printed). If it is, we will go back to _checkz, repeating the loop. If it is greater than 25, then we have looped through all possible indices and can exit the function and the program.
mov rdx, [rsp] ; move the (de)ciphered string to `rdx`
mov r9, [rsp+8] ; filesize
push rax ; saving...
push rcx ; saving...
push rdx ; saving...
write 1, rdx, r9 ; print the (de)ciphered string
write 1, nl, 2 ; print a newline
pop rdx ; restoring...
pop rcx ; restoring...
pop rax ; restoring...Note that we save rax, rcx, and rdx on the stack before calling the write syscalls and restore them afterward. We do this because these registers will be altered after the syscall returns, and we will need them later. They contain, respectively, the current position in the string, the current index, and the string address.
After restoring the values to the registers, we can check if the index is less than or equal to 25, and if it is, increment the index (to go to the next ROT algorithm index) and run the loop again, now with the new string. Otherwise, we jump to the program exit routine.
inc rcx ; increment the index
mov rax, rdx ; `rax` now contains the new (de)ciphered string
cmp rcx, 25 ; compare the current index with 25
jle _checkz ; if index <= 25, repeat the loop (with the new incremented index)
jmp _exit ; if not, we have tested everything; close the program
leave
retFinishing up
Thus, we have finished the code for the ROT cipher brute-forcer. To run it, we need to compile the code and link the executable. We do this as follows:
nasm -felf64 rotbrute.nasm -g -F dwarf
ld rotbrute.o -o rotbruteOnce the executable is generated, we can run it in the two ways we programmed. Note that I used -n with echo to prevent it from adding a newline at the end of the string. If we don't do this, the newline will be duplicated in each iteration of the loop, which is not desirable. (I added bold emphasis just to facilitate viewing the correct result of the brute force):
- Reading the content of a file:
nich0las@0x7359:~$ echo -n "wfujqhlwv lwpl" > file.txt
nich0las@0x7359:~$ ./rotbrute text.txt
wfujqhlwv lwpl
xgvkrimxw mxqm
yhwlsjnyx nyrn
zixmtkozy ozso
ajynulpaz patp
bkzovmqba qbuq
clapwnrcb rcvr
dmbqxosdc sdws
encrypted text *
fodszqufe ufyu
gpetarvgf vgzv
hqfubswhg whaw
irgvctxih xibx
jshwduyji yjcy
ktixevzkj zkdz
lujyfwalk alea
mvkzgxbml bmfb
nwlahycnm cngc
oxmbizdon dohd
pyncjaepo epie
qzodkbfqp fqjf
rapelcgrq grkg
sbqfmdhsr hslh
tcrgneits itmi
udshofjut junj
vetipgkvu kvok2. Reading the content from stdin:
nich0las@0x7359:~$ echo "wfujqhlwv lwpl" | ./rotbrute
wfujqhlwv lwpl
xgvkrimxw mxqm
yhwlsjnyx nyrn
zixmtkozy ozso
ajynulpaz patp
bkzovmqba qbuq
clapwnrcb rcvr
dmbqxosdc sdws
encrypted text *
fodszqufe ufyu
gpetarvgf vgzv
hqfubswhg whaw
irgvctxih xibx
jshwduyji yjcy
ktixevzkj zkdz
lujyfwalk alea
mvkzgxbml bmfb
nwlahycnm cngc
oxmbizdon dohd
pyncjaepo epie
qzodkbfqp fqjf
rapelcgrq grkg
sbqfmdhsr hslh
tcrgneits itmi
udshofjut junj
vetipgkvu kvok