At first glance, the challenge binary just accepts some inputs and then, quits.
Nothing but good, plain rev 😎. Tools used: IDA, unicorn and capstone.
Decompilation
Initial rough decompilation with IDA, incl. initial understanding of the variables:
#include <unicorn/unicorn.h>
unsigned int ARM_CODE[2048] = {
0x43E2405D, 0xCBFAEF17, 0xD808F4F1, 0x65FEAF15, 0x02338CC9, 0x4273FAA9, 0x05665ACC, 0x385237FA,
...
0x9C0A2E68, 0x29FDBEC0, 0x0F7A16CC, 0x60A1078A, 0xABF8888E, 0xD3231E84, 0xCC111460, 0x5033DFE4
};
uc_engine *engines[9]; // Only 8 are used.
unsigned long unused_8x8_1[8] = {
0x00000000000061a0, 0x00000000000061a8,
0x00000000000061b0, 0x00000000000061b8,
0x00000000000061c0, 0x00000000000061c8,
0x00000000000061d0, 0x00000000000061c8
};
unsigned long unused_8x8_2[8];
unsigned long offsets_by8[8] = { 0, 8, 16, 24, 32, 40, 48, 56 };
void RunProgram(unsigned long program_id) {
int y = 13, x = 37;
uc_engine *engine = engines[program_id];
do {
unsigned int code = ARM_CODE[256 * program_id + 128 + (y & 0x7F)] ^ ARM_CODE[256 * program_id + (x & 0x7F)];
if ( uc_mem_write(engine, 0, code, 4) || (unsigned int)uc_emu_start(engine, 0, 4, 0, 1) )
exit(0);
x += 13; y += 37;
} while ( x != 1701 );
}
void main(int argc, char **argv, char **envp) {
unsigned long uc; // rdi MAPDST
unsigned long inputs[9];
// All the SSE stuff effectively initializes unused_8x8_1 with offsets from unused_8x8_2
// ... which doesn't seem used anyway.
__m128i tmp128 = _mm_unpacklo_epi64((__m128i)(unsigned unsigned long)unused_8x8_2, (__m128i)(unsigned unsigned long)unused_8x8_2);
*(__m128i *)unused_8x8_1 = _mm_add_epi64(_mm_load_si128((const __m128i *)offsets_by8), tmp128);
*(__m128i *)&unused_8x8_1[2] = _mm_add_epi64(_mm_load_si128((const __m128i *)&offsets_by8[2]), tmp128);
*(__m128i *)&unused_8x8_1[4] = _mm_add_epi64(_mm_load_si128((const __m128i *)&offsets_by8[4]), tmp128);
*(__m128i *)&unused_8x8_1[6] = _mm_add_epi64(tmp128, *(__m128i *)&offsets_by8[6]);
unsigned long *engines_end = &engines[8];
// Initialize 8 Unicorn engines and map 1k RAM for each
unsigned long *engine = engines;
do {
if ( (unsigned int)uc_open(UC_ARCH_ARM64, UC_MODE_LITTLE_ENDIAN, engine) )
exit(0);
uc = *engine++;
uc_mem_map(uc, 0, 1024, UC_PROT_ALL);
} while ( engine != engines_end );
// Read 8 64-bit decimal numbers into inputs[] (and copy to vars[])
unsigned long *input = inputs;
unsigned long **var = vars;
do {
unsigned long *inp = input++;
scanf(&fmt_lu, inp);
*var++ = (unsigned long *)*(input - 1);
} while ( input != &inputs[8] );
// Main loop, repeats 31 times
int j = 31;
do {
var = vars;
engine = engines;
// Initialize X0 in all engines with respective var[]
do {
uc = *engine;
unsigned long **val = var;
++engine;
++var;
uc_reg_write(uc, UC_ARM64_REG_X0, val);
} while ( engine != engines_end );
// Run program on all the engines
for ( int i = 0; i != 8; RunProgram(i) )
++i;
// Pull the result (X0) from each engine back into vars[] - but at position offset by 1
engine = engines;
int y = 7;
do {
uc = *engine++;
int pos = y++ & 7;
uc_reg_read(uc, UC_ARM64_REG_X0, &vars[pos]);
} while ( engine != engines_end );
--j;
} while ( j );
// Calculate logical OR of all the vars[]
__m128i diff = _mm_or_si128(
_mm_or_si128(_mm_or_si128(_mm_load_si128((const __m128i *)&vars[4]), *(__m128i *)&vars[2]), *(__m128i *)vars),
*(__m128i *)&vars[6]);
long diff_exists = _mm_or_si128(diff, _mm_srli_si128(diff, 8)).m128i_u64[0];
// Shutdown all engines
engine = engines;
do {
uc = *engine++;
uc_close(uc);
} while ( engine != engines_end );
// If all vars[] got reduced to 0, the initial inputs were correct
if ( !diff_exists ) {
printf("Congrats! You can use the flag FCSC{");
input = inputs;
do {
printf("%016lx", *input++);
} while ( input != &inputs[8] );
puts("} to validate the challenge.");
}
}
So, what we see here:
- Read 8 64-bit numbers into
vars - Run 31 iterations of a loop where each of the
varsis processed by simulated ARM64 code and written back (with a position shift) - If, at the end, all 8
varsare zero, the initial inputs were correct.
The ARM_CODE[] array has eight, 256-element blocks, each element being a 4-byte ARM64 instruction.
However, the instructions are spread across the block, with two separate strides of 13 and 37 (all that modulo 128).
All this can be simplified as:
void RunProgram(int program_id) {
for (int y=13, x=37; x!=(128*13+37); y+=37, x+=13) {
// Pull the opcode from a garbled location in ARM_CODE
unsigned int code = ARM_CODE[256 * program_id + (x & 0x7F)] ^
ARM_CODE[256 * program_id + 128 + (y & 0x7F)];
uc_mem_write(engines[program_id], 0, code, 4); // Write 4 bytes at 0
uc_emu_start(engines[program_id], 0, 4, 0, 1); // Run 1 instruction from 0 (or until 4)
}
}
void main() {
unsigned long inputs[8];
// Open the engines
for (i=0; i<8; i++) {
uc_open(UC_ARCH_ARM64, UC_MODE_LITTLE_ENDIAN, &engines[i]);
uc_mem_map(engines[i], 0, 1024, UC_PROT_ALL);
}
// Read initial values into vars[] and inputs[]
for (i=0; i<8; i++) {
scanf("%lu", &inputs[i]);
vars[i] = inputs[i];
}
// Main loop
for (j=31; j>0; j--) {
// Write current vars[] into X0 in each engine
for (i=0; i<8; i++)
uc_reg_write(engines[i], UC_ARM_REG_X0, &vars[i]);
// Execute each engine's program
for (i=0; i<8; i++)
RunProgram(i);
// Pull the values back into vars, but with offset of -1
for (i=0; i<8; i++)
uc_reg_read(engines[i], UC_ARM_REG_X0, &vars[(i+7)&7]);
}
// Bail out if any vars is non-zero
for (res=0,i=0; i<8; i++)
if (vars[i]) return;
// Otherwise, print the flag as a concat of (correct) inputs
puts("Congrats! You can use the flag FCSC{");
for (i=0; i<0; i++)
printf("%016lx", inputs[i]);
puts("} to validate the challenge.");
}
The ARM code
Let’s decrypt these ARM shellcodes. We will use exactly the same stride logic as RunProgram() above:
ARM_CODE = [
0x43E2405D, 0xCBFAEF17, 0xD808F4F1, 0x65FEAF15, 0x02338CC9, 0x4273FAA9, 0x05665ACC, 0x385237FA,
...
0x9C0A2E68, 0x29FDBEC0, 0x0F7A16CC, 0x60A1078A, 0xABF8888E, 0xD3231E84, 0xCC111460, 0x5033DFE4,
]
for program_id in range(8):
code = b''
y = 13
for x in range(37, 37+128*13, 13):
code += (ARM_CODE[256*program_id+(x & 0x7F)] ^ ARM_CODE[256*program_id+128+(y & 0x7F)]).to_bytes(4, 'little')
y += 37
print(str(program_id)+":"+code.hex())
Result:
0:210001cae2618fd22314c2ca82279bd223ecc2cae27f8fd22380c2ca02ab80d2233cc2cac28991d22304c2cae2838fd2231cc2ca823586d223e0c2caa20399d223f4c2cac2cc8bd22348c2cac2f899d223ccc2ca228497d2230cc2ca425e90d22318c2ca227d8bd22338c2ca221893d22378c2ca02bf9fd22328c2ca62fb9fd22368c2caa2aa9dd223c0c2ca223f83d223b8c2caa2139ed223a8c2ca22e191d223d8c2caa24a9ad223b4c2ca02338cd223f0c2ca021193d223f8c2ca627992d2238cc2cae26281d22324c2ca028080d22134c2cae20480d22100c2ca02f182d22160c2ca423387d221dcc2ca420080d221a4c2ca82c084d22198c2ca007c019b210001ca62459ad22334c2ca820283d223b4c2ca626a80d223ecc2ca228388d22380c2ca02038bd22318c2cac21782d223c0c2ca62bd8dd223d4c2ca828b97d22314c2cae26a87d2233cc2cac24a92d22344c2cae26886d223bcc2cae2b09bd223a4c2ca825383d22398c2ca42bf97d22350c2cac24485d22390c2cac2aa98d223e0c2cac22e9ad2232cc2cae2f686d22394c2ca623e9fd22378c2caa2a095d2230cc2ca426c94d22338c2ca820080d22164c2ca02049ad2219cc2cac26583d223f0c2ca228587d22348c2ca424d80d22340c2ca024380d22120c2cae2a690d22154c2ca02008ad221ccc2ca02c082d221dcc2ca02a58fd221f8c2ca0000018b
1:210001ca024697d223d8c2ca22119ad2237cc2ca220492d223fcc2ca62c49bd22324c2ca420b94d2238cc2ca428483d22390c2caa25c90d22360c2caa2728ed223b4c2cac21991d22368c2ca82ac8cd2233cc2cae21f8bd223acc2ca627386d22398c2caa2e99bd22384c2cae2e88dd22358c2cac27797d223ecc2ca428788d22304c2ca223995d22334c2ca22819fd22320c2ca023080d221ccc2ca021192d2234cc2ca42b785d22340c2ca02389cd22314c2ca220080d22148c2ca822c81d22144c2caa2609ed223f4c2ca220080d221a8c2ca02809fd22188c2ca025287d2230cc2ca02c08ad221f0c2ca021d9ed221a4c2ca627683d22110c2ca007c019b210001cae2c292d22380c2ca02269ed223a0c2caa29b8ed223b4c2cac2ff93d22348c2caa27393d2239cc2cac2348bd223f0c2cae20694d22338c2ca02fa9fd22364c2ca621a99d22300c2ca022d8ed22324c2ca82a982d223a4c2ca02289ed2238cc2ca62dc97d22370c2ca225794d223e8c2cae20f9ad22388c2ca422590d22368c2ca82c19fd223bcc2ca22f38cd22398c2ca225f92d223ecc2ca02e89bd22314c2cae2899ed22378c2ca020082d221f8c2ca02d380d221c4c2caa21883d22358c2ca022088d22108c2ca429481d2233cc2ca020088d22128c2cac2e784d22194c2cae2f49fd22344c2ca229980d2215cc2ca420188d22130c2ca0000018b
2:210001cac22c9ed223e4c2caa25e8bd223acc2cae2f59dd223a4c2ca42da91d22364c2caa27e88d22310c2ca02e697d223c8c2ca02b295d22340c2cae2ac9dd223bcc2cac2999ad223e8c2ca826095d223a0c2cae2f49bd2238cc2ca020088d221d4c2cac2b886d22314c2ca823888d223f8c2ca220080d22198c2cae27785d2237cc2ca426c92d223ecc2ca62008ad223f0c2ca625787d22344c2caa2868fd223fcc2caa23597d2231cc2caa2438ed22308c2ca82ef8bd22338c2ca220080d22118c2ca02b581d22388c2ca02f289d221dcc2cac2a281d22360c2ca829399d2210cc2ca62ea86d22380c2caa2b483d22194c2cae2fc9ed22158c2ca007c019b210001ca220984d223c8c2ca02ee8cd22394c2ca023d8bd22314c2ca42bb85d22358c2ca62929cd223a4c2ca62fe90d223e4c2ca82f38fd22344c2cac2a480d223acc2ca62808cd223f4c2ca22ca81d223b8c2ca42409cd223c4c2ca82c18fd2239cc2ca027182d223d4c2ca42b880d223bcc2ca627b97d22378c2ca22df86d223d0c2ca024090d22304c2ca42bf9fd223c0c2cac24791d223ecc2caa2cb86d22324c2ca421a87d22388c2caa27282d2238cc2ca426491d22320c2cae27889d22368c2ca02009dd2212cc2ca026080d221b4c2ca22ee8fd223dcc2ca223a9fd223e0c2ca022089d22140c2caa2bd94d2217cc2ca82e39fd221e8c2ca0000018b
3:210001ca626285d223d8c2caa23f84d22354c2ca62ad98d22398c2ca22d883d22390c2cae28692d223c8c2ca020898d223bcc2cac27f91d22368c2ca022b8dd22370c2ca221b9dd2238cc2ca22368fd223f0c2ca82259dd223a8c2ca02b998d22388c2ca22399cd2234cc2ca22668cd22304c2cae2ed95d22374c2cae2dc92d223d0c2cac2dc92d22344c2caa29896d22318c2ca228585d223ccc2cae2259fd22330c2ca623689d22340c2cac2009ed22358c2ca022080d221e8c2cae28597d2239cc2cac2ba93d22324c2cae2e99ed223a0c2ca02c09cd22114c2ca227882d221b8c2ca62a58ed22384c2ca02ee84d2217cc2ca82289cd2213cc2ca007c019b210001ca022993d22390c2cae26081d22398c2caa25384d22314c2ca021b80d22350c2cac27086d223f0c2ca62599bd223ccc2ca42e286d2234cc2ca026598d22348c2cac23d88d22374c2caa2e490d223e8c2ca22248fd223f8c2ca822b98d22394c2ca220e9dd22384c2ca22b885d22360c2ca828987d223d0c2ca82e88dd22320c2cae25984d223c8c2caa2d28fd223bcc2ca628491d22340c2ca62ed9ed22318c2ca020085d2216cc2cae27391d223b8c2ca62969fd22380c2ca22779fd223e4c2ca820183d2232cc2ca825084d223c0c2ca820380d221a0c2ca020c80d22108c2ca42b692d221d8c2caa25392d2218cc2ca427c9fd22134c2ca0000018b
4:210001cac2118ed2232cc2cac2a883d22398c2ca22bd9bd22304c2ca62b28fd223c8c2ca42028cd22358c2ca625890d2231cc2ca82618ad2239cc2caa2fb9dd22370c2ca427c8ed223dcc2caa2f680d22348c2ca02679dd22328c2ca623992d2238cc2ca42018ad223e4c2ca62f697d22324c2ca426093d223a8c2ca620884d223f4c2ca226790d2237cc2ca42be90d22380c2ca029791d223f0c2ca02259cd2235cc2cac20880d22138c2ca822491d22394c2ca629e9ad223bcc2ca620080d22114c2caa2da9ad223b4c2cae2b799d223a4c2ca029f80d221a0c2cae2ec9bd223e0c2ca82e589d221d4c2caa2e981d2210cc2ca02c49fd22174c2ca007c019b210001ca625584d223b8c2cae27289d22308c2ca428683d22320c2ca427382d223c4c2ca220884d22390c2ca425982d22310c2ca825792d223c8c2ca420d88d2233cc2cae22c88d22328c2ca822b9fd22314c2cac22490d22348c2ca42b08dd22368c2caa20598d2234cc2ca02d798d22378c2ca82c28fd22384c2ca028083d22194c2ca820099d223f0c2ca22f883d223c0c2ca020090d221acc2ca82408cd22344c2caa28792d223d0c2cae20b8fd22358c2caa22f9ad223ccc2ca020780d2210cc2ca620080d22160c2ca020090d221b0c2ca020087d22140c2cae2e395d223e4c2ca020895d221bcc2ca82629dd221e8c2cae2909dd22154c2ca0000018b
5:210001ca42908fd22314c2ca224b98d22360c2caa28787d22300c2ca82d888d223f8c2ca82d49ed2230cc2ca224e89d223d8c2ca22ab97d223bcc2caa2bf9bd22370c2ca22e09cd22304c2caa20597d22398c2ca826198d2235cc2ca02539ed223c8c2ca221d9ed22328c2ca026897d22320c2ca42c380d223b0c2ca021991d22330c2ca82a79ed22340c2caa2bc8ad223acc2cac24b83d223a4c2ca828f9ad223f4c2ca42d18fd22324c2ca020082d22180c2ca42fc95d223c4c2ca220080d2214cc2ca02ac8ad22190c2ca820080d221f0c2ca02008fd221c0c2ca02009cd221d4c2ca420481d221e0c2ca028081d2212cc2ca62419bd22148c2ca007c019b210001ca42278ed223d8c2ca42948fd223dcc2ca22139ad22304c2ca82b98bd2237cc2ca22488ad2238cc2ca82fe84d22364c2ca22c886d223e8c2caa2e980d22328c2ca624289d223fcc2ca021394d223e0c2ca62099ed22398c2ca02b980d22370c2ca82b894d22318c2cae21797d223f8c2cae2a091d223d4c2ca42f78ed223f4c2ca02b79dd22330c2ca62878dd223b4c2ca229f87d2239cc2cac23a8dd223c4c2ca62a88ad2234cc2ca226893d22350c2cac2f798d22324c2ca62619fd22334c2ca826b92d22388c2caa20b80d22168c2cac21c8ed2230cc2ca62a48fd22140c2ca020880d221ccc2ca620691d22100c2ca82228ad221b0c2ca0000018b
6:210001cae28c8fd22348c2ca62cd81d223f8c2cae2e08fd2237cc2ca029f90d223e4c2ca82f88cd22324c2caa28c85d22394c2ca824f99d2231cc2ca621f90d22388c2caa2be8dd223ecc2cac26194d22370c2cae2fc8ad22308c2caa2ef9cd2235cc2ca829099d223f4c2ca02d187d223c8c2caa2158ed2236cc2ca82d782d223c4c2caa2769ed22378c2cac2548ed2238cc2ca62f79dd2234cc2caa21d9dd22330c2caa25684d2233cc2ca021e9ad22300c2cae26c89d22334c2caa22884d2230cc2ca020085d22140c2ca020180d221b8c2ca020081d221f0c2cac27a83d22380c2ca228d85d22154c2ca42a987d22104c2ca425b82d2219cc2ca007c019b210001cac2399fd22348c2ca022083d223ccc2ca62c291d22324c2ca22e494d22364c2ca62028cd2230cc2ca02e28ad22338c2caa22c93d22304c2caa2b79bd223ecc2cac2849ed22340c2ca82029ed223f8c2ca62b19dd2239cc2ca420191d22368c2ca82d19dd22350c2ca62da81d22354c2ca82c284d22310c2caa27290d22378c2caa26192d223dcc2cae20c80d223b4c2ca021080d22144c2cac22889d22308c2ca227090d22388c2caa2179dd223c0c2cac2c59ad223f0c2ca22de85d22318c2ca82c68dd223b8c2ca028f8dd2216cc2cac2bb80d22114c2caa2a794d223a8c2ca421182d221e8c2ca420180d221b0c2ca42919ad221a0c2ca0000018b
7:210001caa2d18ad223bcc2ca42548dd22370c2ca82f581d223ccc2ca822d9ed223f0c2ca82f09ed223a8c2caa2f387d223f8c2ca22738dd223b4c2cac2ac87d223ecc2ca627b88d22340c2cac2858ed22310c2ca220b89d223dcc2ca42c480d2237cc2ca824a98d22378c2ca82ff8bd223e0c2ca82b194d22328c2cae2ee82d223d0c2ca423e82d223b0c2caa23198d223acc2caa29295d22338c2cac26194d22384c2cae28f94d22324c2cac26a97d2238cc2ca02d38ed223b8c2ca021080d221e4c2caa22e99d2234cc2ca22619ed22314c2ca827980d22134c2ca020580d221c4c2ca82eb92d22108c2ca02b491d2216cc2ca62569fd221a0c2ca007c019b210001ca821284d22354c2ca22cd8bd22310c2cae22b9ad223b4c2ca42038ed223e8c2ca224183d22314c2cae2ee93d22330c2cac25b93d223ecc2ca821882d22300c2cae2189dd2230cc2ca02a38ad22374c2cae2ea91d223e4c2caa2909dd223c0c2ca625398d22340c2ca22ab88d22320c2caa2239fd22398c2ca42c28fd223c4c2cac2c684d223b0c2ca82c196d22384c2ca021f97d22348c2cae25297d22388c2caa2b285d22344c2cac2399fd22368c2ca020082d22160c2ca829188d223f0c2caa2379ed223b8c2caa28889d2239cc2cac20d80d221ccc2cac2d981d221a8c2ca021086d22108c2cae2a58ed22178c2ca22e99cd2212cc2ca0000018b
All these bytecodes are very similar, not just in hex, but also when looking at them with ShellStorm disassembler: #0, #1, #2, #3, #4, #5, #6, #7. All the “programs” are down to:
0x0000000000000000: eor x1, x1, x1
0x0000000000000004: movz x2, #xxxx
0x0000000000000008: eor x3, x1, x2, ror #xx
0x000000000000000c: movz x2, #xxxx
0x0000000000000010: eor x3, x1, x2, ror #xx
(...)
0x00000000000000f4: movz x2, #xxxx
0x00000000000000f8: eor x1, x1, x2, ror #xx
0x00000000000000fc: mul x0, x0, x1
0x0000000000000100: eor x1, x1, x1
0x0000000000000104: movz x2, #xxxx
0x0000000000000108: eor x3, x1, x2, ror #xx
0x000000000000010c: movz x2, #xxxx
0x0000000000000110: eor x3, x1, x2, ror #xx
(...)
0x00000000000001ec: movz x2, #xxxx
0x00000000000001f0: eor x1, x1, x2, ror #xx
0x00000000000001f4: movz x2, #xxxx
0x00000000000001f8: eor x1, x1, x2, ror #xx
0x00000000000001fc: add x0, x0, x1
- (remember,
X0is our input, passed to simulated CPU) - Do a bunch of loads and XORs on fixed values, using
X1,X2,X3. Result will be inX1- and it will be always the same. - Multiply
X0byX1 - Do another round of loads and XORs, storing final result in
X1 - Add
X1toX0(and it is the final result)
So, each of these Unicorn engines is simply calculating X0 = X0 * factor1 + factor2.
What are these factors? We can use Capstone / Unicorn, to parse and execute the instructions, stopping right after
respective mul / add, and writing down the X1 value:
import unicorn
import unicorn.arm64_const
import capstone
for num in range(8):
y = 13
cs = capstone.Cs(capstone.CS_ARCH_ARM64, capstone.CS_MODE_ARM)
uc = unicorn.Uc(unicorn.UC_ARCH_ARM64, unicorn.UC_MODE_ARM)
uc.mem_map(0, 2048)
uc.reg_write(unicorn.arm64_const.UC_ARM64_REG_X0, 0) # Just testing with consistent X0
for x in range(37, 37+128*13, 13):
code = (ARM_CODE[256*num+(x & 0x7F)] ^ ARM_CODE[256*num+128+(y & 0x7F)]).to_bytes(4, 'little')
for ins in cs.disasm(code, 0):
pass # Just get the first instruction
uc.mem_write(0, code)
uc.emu_start(0, 4)
if ins.mnemonic == 'mul' and ins.op_str.startswith('x0'):
num_mul = uc.reg_read(unicorn.arm64_const.UC_ARM64_REG_X1)
elif ins.mnemonic == 'add' and ins.op_str.startswith('x0'):
num_add = uc.reg_read(unicorn.arm64_const.UC_ARM64_REG_X1)
y += 37
print("{0:d} : X0 = X0 * 0x{1:08x} + 0x{2:08x}".format(num, num_mul, num_add))
Result:
0 : X0 = X0 * 0x2017889811733427 + 0x1c29bba04a2df4a2
1 : X0 = X0 * 0x34b27f78747561bb + 0xa99339f34c5054
2 : X0 = X0 * 0x87df9ced2e9f3993 + 0x49014bda183fc71d
3 : X0 = X0 * 0xc2884ee04f044731 + 0xdf151253be56c81f
4 : X0 = X0 * 0xb91ff104fa7961e9 + 0x3f643bf950bac507
5 : X0 = X0 * 0xb682f5567f082241 + 0x7d23174511488833
6 : X0 = X0 * 0x29634825b4209ea5 + 0xf04d8fd48aa422ae
7 : X0 = X0 * 0x1e71b4fab31465d7 + 0xe931d4bfb38dcc3c
Rewriting all that in simple Python
With all this information we can write a much simpler functional equivalent of the whole initial program:
FACTORS = [
0x2017889811733427, 0x1c29bba04a2df4a2,
0x34b27f78747561bb, 0x00a99339f34c5054,
0x87df9ced2e9f3993, 0x49014bda183fc71d,
0xc2884ee04f044731, 0xdf151253be56c81f,
0xb91ff104fa7961e9, 0x3f643bf950bac507,
0xb682f5567f082241, 0x7d23174511488833,
0x29634825b4209ea5, 0xf04d8fd48aa422ae,
0x1e71b4fab31465d7, 0xe931d4bfb38dcc3c,
]
vars = inputs = [int(input()) for i in range(8)]
for j in range(31):
tmp = [(vars[i]*FACTORS[i*2]+FACTORS[i*2+1])&0xFFFFFFFFFFFFFFFF for i in range(8)]
vars = tmp[1:] + tmp[:1]
if sum(vars)==0:
print("Congrats! You can use the flag FCSC{", end="")
for i in range(8):
print(hex(inputs[i])[2:], end="")
print("} to validate the challenge.")
Finally reversing it
The only thing left is to find the initial value of inputs that will result in the final vars being all 0.
- The pattern of updating
varsisvar = var * x + y - So, naive way of reversing that would be
var = (var - y) // x - But, that would lose nuance of 64-bit multiplication.
What we can do instead is to multiply by modular inverse:
var = (var-y) * pow(x, -1, 1<<64).
This has one strong assumption that all the multiplication factors have a modular inverse. They do 😁
With that, we need to replace the vars initialization above with:
vars = 8 * [0]
for j in range(31):
tmp = vars[-1:] + vars[:-1]
for i in range(8):
vars[i] = (((tmp[i]-FACTORS[i*2+1]))*pow(FACTORS[i*2], -1, 1<<64))&0xFFFFFFFFFFFFFFFF
inputs = vars
print("Correct inputs:", inputs)
… and the challenge will solve itself 😀
Correct inputs: [13680672352284224804, 8294549406814182013, 10417456484546671247, 5217063809825069383, 16594513019748566915, 11098971089058666910, 1846450735050454444, 1845426182176457746]
Congrats! You can use the flag FCSC{bddb83056668ad24731c28bd35161a7d90923d7a887e728f4866bbe4d32b5947e64b8dab82b547839a0777668fac199e199fe9291df0f5ac199c4555cfd54412} to validate the challenge.
(that can be confirmed by entering these inputs in the original binary)