Challenge Name:
addiplikation
Category:
Crypto
Challenge Description:
Kryptonissen har fundet på en ny non-deterministisk hashfunktion - et skiftende hash må jo være *endnu* sværere at cracke end et statisk!
We’re given a Python script, which loads flag.txt (which is obviously unavailable to us). The scripts shows us exactly which characters the flag consists of:
assert all(c in "NC3{_abcdefghijklmnopqrstuvwxyz}" for c in flag)
This severely limits the possible variations of the flag (which is lucky, because we’re going to brute force it).
The script then loops over each character in the flag, and either multiplicate or add each characters decimal value (eg. A = 97) to a total. Finally, the total is returned.
We’re also given a server that can be called with Netcat - it returns a “random” number, generated by the script, based on the correct flag.txt. Example return values:
9506572611482756233049013176272744937202351313392
1728935373303241485036230803522717940674312950741740000
285974934246601765900156051069395912031772061840390835000
356342271713358890750844138753006091931162500
95565309707797259465780386468212183952173182063580000
336733060874377604448327060091515363322637818518560939805
Approach
The main weakness of the “crypto” algorithm, is that it’s reversible.
As an example, lets say the flag is ab.
The possible values from calling the script would be:
a*0+b: 98
a+b: 195
a*b: 9506
With a very small flag and sample set, getting the correct flag is actually pretty hard. The only viable results would be b, ab or ba.
But with a longer string and enough result data (i could call the endpoint as many times as I wanted), it’s possible to reverse-engineer the flag.
How I solved it
* For each result from Netcat (i used about 25.000 pre-saved):
* For each viable character in the flag (given in the challenge).
* Modulo the character with the result, if the result was 0, add one to that characters value in a dict.
* Once done, compare all characters, and select the one that has the highest value.
The character with the highest value, is the most likely candidate to be part of the flag, since every single result that ended in a multiplication, will have modulo == 0 on that characters value. There will be a lot of “false” results too, but statistically, the flag character will always be the highest.
With a character found, its time to clean up the results and prepare for the next character in the flag:
* For each result
* If modulo == 0: divide the result with the previous found characters decimal value
* Else: minus it
The point here, is that the calculation for each character, will always be either an addition or a multiplication. Since we “know” (if our highest valued character was correct), the correct value, we can either divide or subtract the number, to work our way one character back.
Running the above in a script, gives us the following output, after checking the most likely character for the first time:
[('}', 254), ('s', 126), ('d', 103), ('h', 59), ('x', 32), ('t', 32), ('i', 22), ('_', 21), ('a', 19), ('N', 17), ('p', 16), ('n', 14), ('m', 14), ('C', 12), ('b', 10), ('u', 7), ('3', 6), ('r', 6), ('j', 6), ('q', 6), ('c', 6), ('y', 5), ('k', 5), ('g', 4), ('z', 4), ('e', 4), ('v', 4), ('f', 3), ('l', 3), ('w', 3), ('{', 2), ('o', 1)]
So } was the most likely character found - which makes sense, since we know the flag consists of NC3{*}.
There’s a lot of false characters that could modulo == 0, but our correct character is over double the value of the next candidate.
Printing all the most likely candidate characters gives us:
Most likely character: }
Most likely character: s
Most likely character: h
Most likely character: t
Most likely character: a
Most likely character: m
Most likely character: _
Most likely character: k
Most likely character: c
Most likely character: i
Most likely character: u
Most likely character: q
Most likely character: _
Most likely character: s
Most likely character: k
Most likely character: e
Most likely character: s
Most likely character: _
Most likely character: r
Most likely character: e
Most likely character: _
Most likely character: e
Most likely character: r
Most likely character: t
Most likely character: _
Most likely character: e
Most likely character: g
Most likely character: n
Most likely character: a
Most likely character: g
Most likely character: _
Most likely character: o
Most likely character: t
Most likely character: _
Most likely character: r
Most likely character: e
Most likely character: _
Most likely character: n
Most likely character: e
Most likely character: _
Most likely character: s
Most likely character: u
Most likely character: l
Most likely character: p
Most likely character: _
Most likely character: n
Most likely character: e
Most likely character: {
Most likely character: 3
Most likely character: C
Most likely character: N
All that’s left to do is join the flag to a string and reverse it (since we’ve been working in reverse).
Flag
NC3{en_plus_en_er_to_gange_tre_er_seks_quick_maths}
Reflections and Learnings
Math is fun! But basic math doesn’t make for a very good cryptography algorithm :(