Rating:
# Rucksack (RevCrypt 200)
> Find the value that encoded gives "B75B63369A52F5F30CFE5E642" to open the flag archive.
https://dctf.def.camp/quals-2016/rucksack.tar.gz
The binary given in challenge was simple windows dialog window. It was performing some interesting calculations on given number, and returning the result.
Interesting part of the algorithm looked like this after decompilation:
```c
dword_401368 = 0;
dword_401364 = 0;
dword_401360 = 0;
dword_40135C = 0;
do
{
v14 = dword_401354 & 1;
dword_401354 = (unsigned int)dword_401354 >> 1;
v15 = __RCR__(dword_401358, v14);
v14 = __CFRCR__(dword_401358, v14);
dword_401358 = v15;
if ( v14 )
{
v16 = v12[2];
v14 = __CFADD__(v16, dword_40135C);
dword_40135C += v16;
v17 = v12[1];
v18 = v14;
v14 = __CFADD__(v14, dword_401360) | __CFADD__(v17, v14 + dword_401360);
dword_401360 += v17 + v18;
v19 = v14;
v14 = __CFADD__(v14, dword_401364) | __CFADD__(*v12, v14 + dword_401364);
dword_401364 += *v12 + v19;
dword_401368 += v14;
}
v12 += 3;
--v13;
}
while ( v13 );
```
But it turned out to be really simple algorithm, after reverse engineering it:
```python
def hack(input):
dw = 0
for i in range(64):
carry = input & 1
input >>= 1
if carry:
dw += data[i]
return dw
```
Where `data` stands for big static array filled with big numbers:
```python
data = [
58692287682224938532079129932L, 54124250491778978820692485381L,
7277220015820983195773562608L, 22332383050669823978020089761L,
16967063558604003742849514894L, 62355997480269765615210626760L,
5170363880013545458168089364L, 14258428081357094750634713280L,
36287775811261632958539463292L, 64158589039078535932527740088L,
4957165945420369897339450045L, 48887024134310311336003185458L,
18793329531325217943998377262L, 34849054916999515597115226753L,
34004947907188645530085195162L, 34292499970059354752786233092L,
7465958787690007484635596453L, 54523540218652065182276201159L,
57000747039828947704764319534L, 50575388677892232980068371694L,
3702058161015823872166782237L, 3349829679265481129755048986L,
28405544429942218214723074100L, 36495788164044649888936432337L,
48544464129042978733031529923L, 60050271447609162325797432216L,
17009291688635671258136540844L, 32243452400131210275321820528L,
19435400185697379146087163973L, 18958695960561396891652356392L,
31046838278903521493393091567L, 22039804766852830688395024152L,
57057512556148595984239556858L, 60234203621762490899836532853L,
17520024899042505063126260369L, 47991875009003147708419421093L,
2490616484966554508753587547L, 2899153068397613767531906868L,
52497993703425658528041503014L, 52472487311532478269420426577L,
40482174126297668775911754500L, 16911496622935987625595000117L,
46693438934980177103776837991L, 1284890835773525386783112485L,
54477823291266207382876225082L, 61740894964814382664396357499L,
46647309100226523278177395127L, 16502561642567509404189158915L,
19004498941637468189390997034L, 9828916790346848731369187336L,
35425036974884801641584840823L, 31415726379765125631239673685L,
17972704773815859985638190557L, 9936946611209044418233820319L,
36798963351701498896151091569L, 13848431692126270671326713024L,
3198504385930460160976160781L, 16499536430449755854269030517L,
57509243300349206773820711938L, 43866494813937969559452082306L,
54036517188127062281695050584L, 27536442945835183874395339046L,
27752811040789181632791691991L, 55343638437809942929901949018L
]
```
So this challenge is equivalent to solving subset sum problem (which is NP Complete, but good solvers exist in practice).
We implemented simple solved in SAGE, and after a while it printed a solution:
```
[0, 0, 7277220015820983195773562608, 22332383050669823978020089761, 0,
62355997480269765615210626760, 0, 0, 0, 0, 0, 48887024134310311336003185458,
18793329531325217943998377262, 34849054916999515597115226753, 0, 0,
7465958787690007484635596453, 54523540218652065182276201159, 0, 0,
3702058161015823872166782237, 3349829679265481129755048986,
28405544429942218214723074100, 36495788164044649888936432337, 0,
60050271447609162325797432216, 0, 0, 0, 0, 0, 22039804766852830688395024152,
57057512556148595984239556858, 60234203621762490899836532853,
17520024899042505063126260369, 0, 0, 0, 0, 0, 40482174126297668775911754500, 0,
0, 1284890835773525386783112485, 54477823291266207382876225082,
61740894964814382664396357499, 0, 16502561642567509404189158915,
19004498941637468189390997034, 0, 35425036974884801641584840823, 0,
17972704773815859985638190557, 0, 0, 0, 0, 16499536430449755854269030517, 0,
43866494813937969559452082306, 0, 0, 0, 55343638437809942929901949018]
```
After that we recovered good input, and decrypted 7z file given in challenge:
