TRX CTF 2025 - sudo-kurl
by Luca Padalino (padawan)
Challenge README:
The year is 3000 AD. The Pax Romana extends to the stars, but peace has been shattered. Xenomorph invaders challenge the might of the New Roman Empire. A letter arrives from the Senate, sealed with the golden eagle of Rome. It reads:
“Darius Caesar, the stars burn with conflict. The alien invaders are unlike anything we’ve faced before—ruthless, cunning, and relentless. They strike at our borders, threatening to unravel the Pax Galactica and reduce the New Roman Empire to ashes. Our legions are strong, but strength alone will not win this war. You must outthink, outmaneuver, and outlast them. The fate of humanity hangs by a thread, and only your brilliance can secure our future. Will you rise to the challenge and lead us to victory, or shall Rome fall to the void?”
Overview
There was only a binary file (chall) attached to this challenge. The output of the file command was:
chall: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=ae4c7f64246b2a03dd90a3ee5c2a76ea4826aa0b, for GNU/Linux 3.2.0, not stripped
We also executed pwn checksec chall to discover enabled mitigations:
Arch: amd64-64-little
RELRO: Full RELRO
Stack: Canary found
NX: NX enabled
PIE: PIE enabled
SHSTK: Enabled
IBT: Enabled
Stripped: No
After enabling execution permissions (chmod +x chall), the following splash text appears:
Welcome, Darius Caesar.
The Senate has entrusted you with the fate of the New Roman Empire.
Our legions await your orders, and the alien menace encroaches upon our borders.
Caesar, the legions await your command. Specify the sector where our forces should deploy.
Row [1-25] (-1 to check win):
The user is prompted to insert a row index, then a column index, then a value to be stored in that cell. By repeatedly entering 1, the program exits, showing the following message:
Welcome, Darius Caesar.
The Senate has entrusted you with the fate of the New Roman Empire.
Our legions await your orders, and the alien menace encroaches upon our borders.
Caesar, the legions await your command. Specify the sector where our forces should deploy.
Row [1-25] (-1 to check win): 1
Column [1-25]: 1
Troups [1-25]: 1
A miscalculation, Darius. The aliens exploit our weaknesses.
It is also possible to check for victory by typing -1 in the console when the row index is asked. The output is the following:
Welcome, Darius Caesar.
The Senate has entrusted you with the fate of the New Roman Empire.
Our legions await your orders, and the alien menace encroaches upon our borders.
Caesar, the legions await your command. Specify the sector where our forces should deploy.
Row [1-25] (-1 to check win): -1
The legions have fallen, and the Senate lies in ruins. The alien horde swarms across the galaxy, extinguishing the light of the New Roman Empire. Your name, once shouted in triumph, is now whispered in despair. The dream of eternal Rome ends here, Dominus. But remember—history is not kind to the vanquished. The stars, once ours, now belong to the void. Hail, fallen Caesar.
At first glance, it was unclear when and how the flag could be read. Likewise, the logic behind the row indices, column indices, and the specific cell value triggering either program termination or flag access was also unclear—it’s time to dive into the code!
Approach
To decompile and disassemble the code, we used Ghidra. From the very beginning, we noticed that the challenge was written in C++ and has the following functions. For each of those, we provide the decompiled code and a high-level description.
Functions
main()
int main(void) {
ostream *this;
this = std::operator<<((ostream *)std::cout,
"Welcome, Darius Caesar. \nThe Senate has entrusted you with the fate of th e New Roman Empire. \nOur legions await your orders, and the alien menace e ncroaches upon our borders.\n"
);
std::ostream::operator<<(this,std::endl<>);
play();
return 0;
}
This is the first function called after the initialization phase. After printing a welcome message, it calls the play() function.
play()
void play(void) {
bool checkBoardValidity;
char checkWinResult;
ostream *stdoutStream;
long in_FS_OFFSET;
string finalFlag [32];
vector computedFlag [32];
string tempFlag [40];
long canary;
canary = *(long *)(in_FS_OFFSET + 0x28);
do {
checkBoardValidity = isValid((vector *)board);
if (!checkBoardValidity) {
stdoutStream = std::operator<<((ostream *)std::cout, "A miscalculation, Darius. The aliens exploit our weaknesses.");
std::ostream::operator<<(stdoutStream,std::endl<>);
goto LAB_CANARY_CHECK;
}
checkBoardValidity = askInput((vector *)board);
} while (checkBoardValidity);
checkWinResult = checkWin((vector *)board);
if (checkWinResult == '\0') {
stdoutStream = std::operator<<((ostream *)std::cout,&FALLEN_LEGIONS_MESSAGE);
std::ostream::operator<<(stdoutStream,std::endl<>);
} else {
stdoutStream = std::operator<<((ostream *)std::cout, "\nVictory is ours, Darius! \nThe alien forces have been routed, and their stronghold burns under the New Roman banner. \nThe Sena te declares you \'Imperator Invictus\'!");
std::ostream::operator<<(stdoutStream,std::endl<>);
getFlag[abi:cxx11](computedFlag);
std::operator+((char *)tempFlag,(string *)&FLAG_HEADER);
std::operator+(finalFlag,(char *)tempFlag);
std::string::~string(tempFlag);
std::string::~string((string *)computedFlag);
stdoutStream = std::operator<<((ostream *)std::cout,finalFlag);
std::ostream::operator<<(stdoutStream,std::endl<>);
std::string::~string(finalFlag);
}
LAB_CANARY_CHECK:
if (canary != *(long *)(in_FS_OFFSET + 0x28)) {
__stack_chk_fail();
}
return;
}
This is the main function of the challenge. At the beginning, there is a loop where the board is validated using isValid(board). If the board is valid, the program requests input from the user via askInput(board). This loop continues until the user explicitly requests a verification by entering -1. Once the loop exits, the program checks for a win condition using checkWin(board). If the player loses, a defeat message is displayed. Otherwise, the program retrieves and prints the secret flag using getFlag(computedFlag). Additionally, the code includes stack canary protection (__stack_chk_fail()) to guard against buffer overflow exploits.
isValid(*board)
bool isValid(vector *boardPtr) {
int iVar1;
vector<> *beginRowPtr;
vector<> *beginRowPtr_1;
int *colVecIndex;
vector local_DL_606;
vector *var1;
undefined1 finalOutcome;
long in_FS_OFFSET;
undefined1 cellVec [16];
int rowIndex;
int colIndex;
int i;
int j;
int local_a8;
int local_a4;
long cellVec_2;
undefined8 cellVec_1;
long mask_1;
int cell_3;
undefined1 rowPtr [3] [16];
allocator<bool> long_2 [40];
long canary;
bool check;
canary = *(long *)(in_FS_OFFSET + 0x28);
for (rowIndex = 0; rowIndex < 25; rowIndex = rowIndex + 1) {
std::allocator<bool>::allocator();
mask_1 = mask_1 & 0xffffffffffffff00;
std::vector<>::vector((ulong)rowPtr,(bool *)26,(allocator *)&mask_1);
std::allocator<bool>::~allocator(long_2);
std::allocator<bool>::allocator();
cellVec_2 = cellVec_2 & 0xffffffffffffff00;
std::vector<>::vector((ulong)long_2,(bool *)26,(allocator *)&cellVec_2);
std::allocator<bool>::~allocator((allocator<bool> *)&mask_1);
for (colIndex = 0; colIndex < 25; colIndex = colIndex + 1) {
beginRowPtr = (vector<> *)std::vector<>::operator[]((vector<> *)boardPtr,(long)rowIndex);
colVecIndex = (int *)std::vector<>::operator[](beginRowPtr,(long)colIndex);
if (*colVecIndex < 1) {
LAB_CHECK_FALSE:
check = false;
}
else {
beginRowPtr_1 = (vector<> *)std::vector<>::operator[]((vector<> *)boardPtr,(long)rowIndex);
colVecIndex = (int *)std::vector<>::operator[](beginRowPtr_1,(long)colIndex);
cellVec = std::vector<>::operator[]((vector<> *)rowPtr,(long)*colVecIndex);
_cell_3 = cellVec._8_8_;
mask_1 = cellVec._0_8_;
check = std::_Bit_reference::operator.cast.to.bool((_Bit_reference *)&mask_1);
if (!check) goto LAB_CHECK_FALSE;
check = true;
}
if (check) {
finalOutcome = 0;
check = false;
goto LAB_001028c0;
}
beginRowPtr_1 = (vector<> *)std::vector<>::operator[]((vector<> *)boardPtr,(long)colIndex);
colVecIndex = (int *)std::vector<>::operator[](beginRowPtr_1,(long)rowIndex);
if (*colVecIndex < 1) {
LAB_CHECK_KO:
check = false;
}
else {
beginRowPtr_1 = (vector<> *)std::vector<>::operator[]((vector<> *)boardPtr,(long)colIndex);
colVecIndex = (int *)std::vector<>::operator[](beginRowPtr_1,(long)rowIndex);
cellVec = std::vector<>::operator[]((vector<> *)long_2,(long)*colVecIndex);
_cell_3 = cellVec._8_8_;
mask_1 = cellVec._0_8_;
check = std::_Bit_reference::operator.cast.to.bool((_Bit_reference *)&mask_1);
if (!check) goto LAB_CHECK_KO;
check = true;
}
if (check) {
finalOutcome = 0;
check = false;
goto LAB_001028c0;
}
beginRowPtr_1 = (vector<> *)std::vector<>::operator[]((vector<> *)boardPtr,(long)rowIndex);
colVecIndex = (int *)std::vector<>::operator[](beginRowPtr_1,(long)colIndex);
cellVec = std::vector<>::operator[]((vector<> *)rowPtr,(long)*colVecIndex);
cellVec_1 = cellVec._8_8_;
cellVec_2 = cellVec._0_8_;
std::_Bit_reference::operator=((_Bit_reference *)&cellVec_2,true);
beginRowPtr_1 = (vector<> *)std::vector<>::operator[]((vector<> *)boardPtr,(long)colIndex);
colVecIndex = (int *)std::vector<>::operator[](beginRowPtr_1,(long)rowIndex);
cellVec = std::vector<>::operator[]((vector<> *)long_2,(long)*colVecIndex);
_cell_3 = cellVec._8_8_;
mask_1 = cellVec._0_8_;
std::_Bit_reference::operator=((_Bit_reference *)&mask_1,true);
}
check = true;
LAB_001028c0:
std::vector<>::~vector((vector<> *)long_2);
std::vector<>::~vector((vector<> *)rowPtr);
if (!check) goto LAB_EXIT_FUNCTION;
}
for (i = 0; i < 25; i = i + 5) {
for (j = 0; j < 25; j = j + 5) {
std::allocator<bool>::allocator();
mask_1 = mask_1 & 0xffffffffffffff00;
std::vector<>::vector((ulong)long_2,(bool *)0x1a,(allocator *)&mask_1);
std::allocator<bool>::~allocator((allocator<bool> *)rowPtr);
for (local_a8 = 0; local_a8 < 5; local_a8 = local_a8 + 1) {
for (local_a4 = 0; local_a4 < 5; local_a4 = local_a4 + 1) {
beginRowPtr_1 = (vector<> *)std::vector<>::operator[]((vector<> *)boardPtr,(long)(local_a8 + i));
colVecIndex = (int *)std::vector<>::operator[](beginRowPtr_1,(long)(local_a4 + j));
iVar1 = *colVecIndex;
if (iVar1 < 1) {
LAB_00102a0a:
check = false;
} else {
cellVec = std::vector<>::operator[]((vector<> *)long_2,(long)iVar1);
rowPtr[0] = cellVec;
check = std::_Bit_reference::operator.cast.to.bool((_Bit_reference *)rowPtr);
if (!check) goto LAB_00102a0a;
check = true;
}
if (check) {
finalOutcome = 0;
check = false;
goto LAB_CHECK_OK;
}
cellVec = std::vector<>::operator[]((vector<> *)long_2,(long)iVar1);
rowPtr[0] = cellVec;
std::_Bit_reference::operator=((_Bit_reference *)rowPtr,true);
}
}
check = true;
LAB_CHECK_OK:
std::vector<>::~vector((vector<> *)long_2);
if (!check) goto LAB_EXIT_FUNCTION;
}
}
finalOutcome = 1;
LAB_EXIT_FUNCTION:
if (canary != *(long *)(in_FS_OFFSET + 0x28)) {
__stack_chk_fail();
}
return (bool)finalOutcome;
}
The syntax of this disassembled function is particularly ugly. Of course, we asked to ChatGPT their thoughts on the code, and this was their response:
💡 Essentially, this function should check for the board’s validity, operating on rows, columns, and sub-grids (likely 5x5, given the use of
0x19and 5 in the loops). The verification approach is that of Sudoku, as the pun in the challenge title suggests. For each of row, column, and subgrid, it verifies that each number is not duplicated; otherwise, it returns an error code that leads to the program closing.
askInput(*board)
bool askInput(vector *boardPtr) {
bool outcome;
ostream *stdoutStream;
vector<> *rowPtr;
int *colPtr;
long in_FS_OFFSET;
int rowIndex;
int colIndex;
int troupsNo;
long canary;
canary = *(long *)(in_FS_OFFSET + 0x28);
stdoutStream = std::operator<<((ostream *)std::cout,
"Caesar, the legions await your command. Specify the sector where o ur forces should deploy."
);
std::ostream::operator<<(stdoutStream,std::endl<>);
std::operator<<((ostream *)std::cout,"Row [1-25] (-1 to check win): ");
std::istream::operator>>((istream *)std::cin,&rowIndex);
if (rowIndex == -1) {
outcome = false;
} else {
std::operator<<((ostream *)std::cout,"Column [1-25]: ");
std::istream::operator>>((istream *)std::cin,&colIndex);
std::operator<<((ostream *)std::cout,"Troups [1-25]: ");
std::istream::operator>>((istream *)std::cin,&troupsNo);
if ((((rowIndex < 1) || (0x19 < rowIndex)) || (colIndex < 1)) || (0x19 < colIndex)) {
stdoutStream = std::operator<<((ostream *)std::cout,
"You attempted to reinforce Saturn, but its fragile alliance wi th Mars has shattered. Their combined fury annihilated our forc es. This misstep will be recorded as a dark chapter in Roman hi story."
);
std::ostream::operator<<(stdoutStream,std::endl<>);
outcome = true;
}
else if ((troupsNo < 1) || (25 < troupsNo)) {
stdoutStream = std::operator<<((ostream *)std::cout,
"Your decision to deploy all our troops into what appeared to b e a strategic stronghold was a trap. The aliens detonated a bom b, and our legions were obliterated. The stars grow dimmer with our loss."
);
std::ostream::operator<<(stdoutStream,std::endl<>);
outcome = true;
}
else {
rowPtr = (vector<> *)std::vector<>::operator[]((vector<> *)boardPtr,(long)(rowIndex + -1));
colPtr = (int *)std::vector<>::operator[](rowPtr,(long)(colIndex + -1));
if (*colPtr == 0) {
rowPtr = (vector<> *)std::vector<>::operator[]((vector<> *)boardPtr,(long)(rowIndex + -1));
colPtr = (int *)std::vector<>::operator[](rowPtr,(long)(colIndex + -1));
*colPtr = troupsNo;
outcome = true;
} else {
stdoutStream = std::operator<<((ostream *)std::cout,
"The battlefield is overrun with alien forces, Dominus. There \'s no room for additional troops, and your efforts have led to chaos within the ranks."
);
std::ostream::operator<<(stdoutStream,std::endl<>);
outcome = false;
}
}
}
if (canary != *(long *)(in_FS_OFFSET + 0x28)) {
__stack_chk_fail();
}
return outcome;
}
This function prompts the user to specify the row index, column index, and the number of troops to deploy. It validates whether the entered indices fall within the range of 1-25. For the row index, the value -1 is also accepted, in which case the function returns control to the play() function to continue its execution.
🔦 This function provides insight into the structure of the board, which appears to be a 25x25 grid.
checkWin(*board)
bool checkWin(vector *boardPtr) {
bool isBoardValid;
vector<> *this;
int *cellValue;
long in_FS_OFFSET;
__normal_iterator boardVecBegin;
__normal_iterator boardVecEnd;
__normal_iterator rowVecBegin;
__normal_iterator rowVecEnd;
long canaryStr;
canaryStr = *(long *)(in_FS_OFFSET + 0x28);
_boardVecBegin = std::vector<>::begin((vector<> *)boardPtr);
_boardVecEnd = std::vector<>::end((vector<> *)boardPtr);
do {
isBoardValid = operator!=(&boardVecBegin,&boardVecEnd);
if (!isBoardValid) {
isBoardValid = isValid(boardPtr);
LAB_CANARY_CHECK:
if (canaryStr != *(long *)(in_FS_OFFSET + 0x28)) {
__stack_chk_fail();
}
return isBoardValid;
}
this = (vector<> *)__normal_iterator<>::operator*((__normal_iterator<> *)&boardVecBegin);
_rowVecBegin = std::vector<>::begin(this);
_rowVecEnd = std::vector<>::end(this);
while(true) {
isBoardValid = operator!=(&rowVecBegin,&rowVecEnd);
if (!isBoardValid) break;
cellValue = (int *)__normal_iterator<>::operator*((__normal_iterator<> *)&rowVecBegin);
if (*cellValue == 0) {
isBoardValid = false;
goto LAB_CANARY_CHECK;
}
__normal_iterator<>::operator++((__normal_iterator<> *)&rowVecBegin);
}
__normal_iterator<>::operator++((__normal_iterator<> *)&boardVecBegin);
} while( true );
}
This function checks whether the board is valid by calling the
isValid(*board)function, and it ensures there are no cells with a value of0. It provides additional information beyond what is discussed in theisValid(*board)description.
getFlag(*board)
vector *getFlag[abi:cxx11](vector *boardPtr) {
__normal_iterator aVecIterator;
bool compareVecs;
undefined8 beginAVec_2;
double *pdVar1;
vector *vectorToMultiply;
long in_FS_OFFSET;
double dVar2;
undefined8 endAVec;
undefined8 local_d8;
ulong aVec;
vector<> *local_c8;
double local_c0;
vector<> local_b8 [32];
vector<> local_98 [32];
vector matrixToMultiply [32];
allocator<double> vecToAllocate [32];
undefined8 beginAVec [3];
long canary;
undefined8 aVecIterator_2;
ulong aVec_1;
canary = *(long *)(in_FS_OFFSET + 0x28);
aVec = std::vector<>::size((vector<> *)A);
aVec = aVec >> 1;
std::allocator<double>::allocator();
aVec_1 = aVec;
beginAVec[0] = std::vector<>::begin((vector<> *)A);
aVecIterator_2 = __normal_iterator<>::operator+((__normal_iterator<> *)beginAVec,aVec_1);
beginAVec_2 = std::vector<>::begin((vector<> *)A);
std::vector<>::vector<>(local_b8,beginAVec_2,aVecIterator_2,vecToAllocate);
std::allocator<double>::~allocator(vecToAllocate);
std::allocator<double>::allocator();
aVecIterator_2 = std::vector<>::end((vector<> *)A);
aVec_1 = aVec;
beginAVec[0] = std::vector<>::begin((vector<> *)A);
beginAVec_2 = __normal_iterator<>::operator+((__normal_iterator<> *)beginAVec,aVec_1);
std::vector<>::vector<>(local_98,beginAVec_2,aVecIterator_2,vecToAllocate);
std::allocator<double>::~allocator(vecToAllocate);
matrixVectorMultiply(matrixToMultiply,vectorToMultiply);
matrixVectorMultiply((vector *)vecToAllocate,vectorToMultiply);
std::vector<>::vector((vector<> *)beginAVec,matrixToMultiply);
aVecIterator_2 = std::vector<>::end((vector<> *)vecToAllocate);
beginAVec_2 = std::vector<>::begin((vector<> *)vecToAllocate);
endAVec = std::vector<>::end((vector<> *)beginAVec);
__normal_iterator<>::__normal_iterator<double*>((__normal_iterator<> *)&local_d8,(__normal_iterator *)&endAVec);
std::vector<>::insert<>((vector<> *)beginAVec,local_d8,beginAVec_2,aVecIterator_2);
std::string::string((string *)boardPtr);
local_c8 = (vector<> *)beginAVec;
endAVec = std::vector<>::begin(local_c8);
local_d8 = std::vector<>::end(local_c8);
while( true ) {
compareVecs = operator!=((__normal_iterator *)&endAVec,(__normal_iterator *)&local_d8);
if (!compareVecs) break;
pdVar1 = (double *)__normal_iterator<>::operator*((__normal_iterator<> *)&endAVec);
local_c0 = *pdVar1;
dVar2 = round(local_c0);
std::string::operator+=((string *)boardPtr,(char)(int)dVar2);
__normal_iterator<>::operator++((__normal_iterator<> *)&endAVec);
}
std::vector<>::~vector((vector<> *)beginAVec);
std::vector<>::~vector((vector<> *)vecToAllocate);
std::vector<>::~vector((vector<> *)matrixToMultiply);
std::vector<>::~vector(local_98);
std::vector<>::~vector(local_b8);
if (canary != *(long *)(in_FS_OFFSET + 0x28)) {
__stack_chk_fail();
}
return boardPtr;
}
This function takes a two-dimensional vector (A) and the current state of the board to compute the flag. It divides the vector A into two segments and performs matrix-vector multiplications using the matrixVectorMultiply(matrix, vector) function on each segment. The results of these multiplications are combined, and the resulting elements are converted into characters by rounding the doubles to integers. These characters are then concatenated to form a string.
The resulting string corresponds to the content of the flag. This string is appended to the prefix TRX{} and returned as the final flag. The flag’s value depends on the final state of the board and the vector A.
The getFlag() function is triggered only upon a win condition. When called, it processes the board and vector A to construct the flag, which is then printed in the play() function.
matrixVectorMultiply(*matrix, *vector)
vector * matrixVectorMultiply(vector *matrix,vector *vector) {
ulong vectorSize;
vector<> *matrixRowPtr;
int *matrixCellPtr;
double *vectorCellPtr;
vector<> *vector_2;
long in_FS_OFFSET;
allocator tempAllocator;
double zeroValue;
ulong i;
ulong j;
long canary;
int cellValue;
double tempProdResult;
canary = *(long *)(in_FS_OFFSET + 0x28);
std::allocator<double>::allocator();
zeroValue = 0.0;
vectorSize = std::vector<>::size((vector<> *)vector);
std::vector<>::vector((vector<> *)matrix,vectorSize,&zeroValue,&tempAllocator);
std::allocator<double>::~allocator((allocator<double> *)&tempAllocator);
i = 0;
while(true) {
vectorSize = std::vector<>::size((vector<> *)vector);
if (vectorSize <= i) break;
j = 0;
while( true ) {
vectorSize = std::vector<>::size(vector_2);
if (vectorSize <= j) break;
matrixRowPtr = (vector<> *)std::vector<>::operator[]((vector<> *)vector,i);
matrixCellPtr = (int *)std::vector<>::operator[](matrixRowPtr,j);
cellValue = *matrixCellPtr;
vectorCellPtr = (double *)std::vector<>::operator[](vector_2,j);
tempProdResult = *vectorCellPtr;
vectorCellPtr = (double *)std::vector<>::operator[]((vector<> *)matrix,i);
*vectorCellPtr = *vectorCellPtr + tempProdResult * (double)cellValue;
j = j + 1;
}
i = i + 1;
}
if (canary != *(long *)(in_FS_OFFSET + 0x28)) {
__stack_chk_fail();
}
return matrix;
}
This function multiplies the board by a vector A, producing a 25-element vector of doubles. It’s used in getFlag() to compute the flag characters.
displayBoard(*board)
void displayBoard(vector *boardPtr) {
bool checkBoardEnd;
int *boardCellPtr;
ostream *boardCellValue;
long in_FS_OFFSET;
undefined8 beginBoard;
undefined8 endBoard;
undefined8 beginBoardColumn;
undefined8 endBoardColumn;
vector<> *boardVec;
vector<> *beginBoardRow;
vector<> *boardRow;
long canary;
canary = *(long *)(in_FS_OFFSET + 0x28);
boardVec = (vector<> *)boardPtr;
beginBoard = std::vector<>::begin((vector<> *)boardPtr);
endBoard = std::vector<>::end(boardVec);
while( true ) {
checkBoardEnd = operator!=((__normal_iterator *)&beginBoard,(__normal_iterator *)&endBoard);
if (!checkBoardEnd) break;
beginBoardRow = (vector<> *)__normal_iterator<>::operator*((__normal_iterator<> *)&beginBoard);
boardRow = beginBoardRow;
beginBoardColumn = std::vector<>::begin(beginBoardRow);
endBoardColumn = std::vector<>::end(boardRow);
while( true ) {
checkBoardEnd = operator!=((__normal_iterator *)&beginBoardColumn,(__normal_iterator *)&endBoardColumn);
if (!checkBoardEnd) break;
boardCellPtr = (int *)__normal_iterator<>::operator*((__normal_iterator<> *)&beginBoardColumn);
if (*boardCellPtr == 0) {
std::operator<<((ostream *)std::cout,". ");
} else {
boardCellValue = (ostream *)std::ostream::operator<<((ostream *)std::cout,*boardCellPtr);
std::operator<<(boardCellValue," ");
}
__normal_iterator<>::operator++((__normal_iterator<> *)&beginBoardColumn);
}
std::ostream::operator<<((ostream *)std::cout,std::endl<>);
__normal_iterator<>::operator++((__normal_iterator<> *)&beginBoard);
}
if (canary != *(long *)(in_FS_OFFSET + 0x28)) {
__stack_chk_fail();
}
return;
}
This function shows the content of the board on screen, printing one row in each line, and separating the columns with a space and replacing a 0 with a ”.”.
. . . 21 . 11 . . 3 24 9 20 23 . 7 22 . 5 18 . 15 2 16 13 .
24 4 . 20 15 . . 5 . 16 2 25 22 . 17 6 21 . 14 . 8 10 1 19 18
. . 10 . 5 . 21 19 22 . 3 13 1 16 . 15 4 7 23 24 12 . 14 . .
. . 13 6 12 14 4 1 . . 24 18 19 5 . . 17 . . . 7 22 . 9 21
. 23 19 7 . . 6 . . 20 15 4 . 21 . . . . 16 10 24 3 . 17 5
12 15 21 . . . 16 6 18 5 7 . 17 3 9 14 . 4 24 22 13 . . . .
14 10 11 2 24 1 25 22 20 . . 23 6 19 . 13 5 8 12 . 17 . 7 15 9
. . . . 1 24 . 3 15 10 20 8 5 . 25 9 16 19 21 . 2 6 . 12 14
. . 5 . 3 . 23 14 8 . . 2 15 . 12 . 7 1 17 6 22 21 4 . 19
13 . . 4 20 . . . 17 . 11 16 . . 22 . 10 18 15 23 . 25 8 1 3
20 25 7 22 . 23 . 10 1 . . . . 13 4 21 . 6 19 . 3 9 15 8 .
1 24 . . . 4 . 20 13 . 8 . 3 . 19 16 2 12 9 5 . 14 10 25 22
. . . . . . . 9 24 . 25 6 . 2 16 4 8 10 . 17 18 7 21 . 1
. 8 . 10 14 16 3 25 6 . . 7 18 9 11 . 13 . 20 . 19 24 5 . 17
17 3 . 15 9 5 . . 11 . . 21 . . 23 7 . 22 . . 20 13 12 4 6
15 . 20 11 21 10 . . 5 22 16 . . 8 3 24 . 13 2 19 . . . . .
. 13 8 . 19 17 . . . . . 12 7 24 6 . 15 23 22 4 14 5 9 . .
9 1 23 14 4 . 24 . 7 8 19 . 2 . 13 17 3 20 5 . . 15 . 16 10
10 . 2 12 . 13 18 15 . . 17 5 . 20 21 8 1 16 . 7 . 19 . 11 .
7 5 17 24 16 20 2 11 19 3 23 . 4 15 1 18 14 . 10 . . 8 13 21 12
. 20 9 . 7 15 22 17 10 . 12 19 . . 24 25 . 14 4 8 16 18 2 . .
19 2 24 8 . . 20 7 4 . . . 9 . 15 5 . 21 11 16 1 . . 14 25
. . 25 1 . 8 5 23 14 6 4 17 16 . 2 . 20 . 13 9 10 12 24 7 15
. . 14 . . . . . . 2 6 10 13 . 5 12 . 24 . . 9 11 . 3 8
6 . 15 . 13 . . 24 . 9 1 . 8 25 . 10 18 17 . 2 . 4 19 . 23
Considerations
After a first analysis of the functions, we reflected on the following points:
- The
displayBoardfunction was not called by any other function, but could have been useful for getting the ongoing status of the board. - By inspecting the contents of the variables
boardandA(both used bygetFlag) in Ghidra, we noticed that they were all initialized to0. Since the flag is computed based on both theboardand vectorA, and the user can only control the board’s values, vectorAmust have been initialized with non-zero values at some point. - The board verification mechanism resembled the logic used to validate a Sudoku puzzle. During the first test, the board validation immediately failed after entering the number
1in the first row and first column. Understanding how the board validation process works, one possible explanation for this behavior is that the board itself had already been initialized.
Our Solution
We concentrate on point 1, as it can give us more insight into the others. Among the functions, there is one that appears to initialize values, but it is quite lengthy and obscure (__static_initialization_and_destruction_0(1,0xffff), called by GLOBAL_sub_I_board, which in turn is called by __frame_dummy_init_array_entry).
If only there were a way to debug the binary easily, either by modifying the control flow or dumping entire memory regions…
Here comes libdebug to the rescue! This library allows us to interact with the binary in a more straightforward way, by setting breakpoints, reading and writing memory, and controlling the execution flow.
from libdebug import debugger
# let's debug the chall binary...
d = debugger("./chall")
# ... using the pipe interaction
pipe = d.run()
# let's try to see whether it is possible not to call the isValid function, but the displayBoard one...
# first of all, place a hardware breakpoint in play()+38 using a binary-relative addressing
bp = d.breakpoint(f"play()+{str(hex(38))}", file="binary", hardware=True)
while not d.dead:
# continue the execution waiting for the breakpoint to be reached
d.cont()
d.wait()
if bp.hit_on(d.threads[0]):
d.step()
print("Hit on play+38!")
# let's change the next instruction pointer to the one of the displayBoard function...
d.regs.rip = d.maps[0].base + 0x2469
# the board should be printed after the initial welcome message...
pipe.recvline(numlines=4)
# let's create a mono-dimensional array reading all the lines, removing useless spaces, and splitting values by ' '
initial_board = pipe.recvline(25).decode().strip().split(" ")
# if the value is uninitialized, there is a "." we can replace with a placeholder value (e.g. 0, in our case)
initial_board = [int(x) if x != "." else 0 for x in initial_board]
print("\n".join(" ".join(map(str, initial_board[i*25:(i+1)*25])) for i in range(25)))
Here is the board! And here is explained the error encountered after entering the number 1 in the first row, first column… There was already a 1 in the twelfth row, first column.
But are we sure that the values of A and board remain constant across different executions? Fortunately, yes!
Therefore we can rely on their consistency to solve the challenge effectively. To retrieve the flag, we just need to manipulate the board such that the matrix-vector multiplication in getFlag produces the desired result. This involves carefully placing values on the board while adhering to the constraints enforced by isValid and checkWin. In short, we need to solve the Sudoku puzzle…
This is the second part of the script. After libdebug is used to force the binary to display the board, we parse the cells and run the Z3 solver to solve the Sudoku puzzle. Once the board is solved, we send the values to the binary and retrieve the flag.
# solve the sudoku using z3
from z3 import *
BOARD_SIZE = 25
BOARD_STEP = 5
s = Solver()
# create the board
board = [[Int(f"board_{i}_{j}") for i in range(25)] for j in range(25)]
# add constraints
for i in range(BOARD_SIZE):
for j in range(25):
# 1) all the numbers must be between 1 and 25
s.add(board[i][j] >= 1, board[i][j] <= 25)
# 2) if the number is already given, it must be the same
if initial_board[i*25+j] != 0:
s.add(board[i][j] == initial_board[i*25+j])
# 3) all the numbers in the row must be different
s.add(Distinct(board[i]))
# 4) all the numbers in the column must be different
s.add(Distinct([board[j][i] for j in range(BOARD_SIZE)]))
# 5) all the numbers in the 5x5 blocks must be different
for i in range(0, BOARD_SIZE, BOARD_STEP):
for j in range(0, BOARD_SIZE, BOARD_STEP):
block = [board[i+k][j+l] for k in range(BOARD_STEP) for l in range(BOARD_STEP)]
s.add(Distinct(block))
# check if the board is solvable
if s.check() == sat:
m = s.model()
# solve the game after having re-run the challenge...
pipe = d.run()
d.cont()
pipe.recvuntil("deploy.\n")
for i in range(BOARD_SIZE):
for j in range(BOARD_SIZE):
# ...avoiding inserting yet initilized numbers
if initial_board[i*25+j] == 0:
pipe.recvuntil(": ")
pipe.sendline(f"{i+1}")
pipe.recvuntil(": ")
pipe.sendline(f"{j+1}")
pipe.recvuntil(": ")
pipe.sendline(str(m[board[i][j]]))
print(f"Row {i+1} - Col {j+1}: {m[board[i][j]]}")
pipe.recvuntil(": ")
pipe.sendline(f"-1")
# the flag should appear there... :D
print(pipe.recvline().decode())
print(pipe.recvline().decode())
print(pipe.recvline().decode())
print(pipe.recvline().decode())
print(pipe.recvline().decode())
else:
print("No solution found")
d.kill()
Flag: TRX{H0w_0ft3n_d0_y0u_th1nk_4b0ut_th3_R0m4n_3mp1r3?!?:D}