Tags: algebra
Rating: 5.0
I really do not understand what this is about, but my cousin told me that once he managed to got a flag out of this. I was able to copy from my cousin's shell parts of his interactions with the server. You can find them in interaction1.txt and interaction2.txt. Unfortunately, they are incomplete.
nooombers.challenges.ooo 8765
Files: interaction1.txt f6aeae3c35be2f8a2d098d076e4bf7ac9f5ece24ddc88c9e7fb43016e049b89a interaction2.txt 6fd5facfefdbd20b82d651520edf56713ef585bad1b78788db06c4208d2da321
Solved by: Srdnlen
We are presented with two files and a service.
The files interaction1.txt and interaction2.txt contain two separate conversations with the server. Let's start looking at interaction1.txt, while also working with the service.
Since everything is in chinese and seems to talk about fish, we tried to replace each symbol or string of symbols with an identifier. It seems like every conversation begins with a triple chinese symbol that we'll call >. After the initial >>>, the service gives us 11 other chinese symbols, followed by another >. It then waits for an input.
Each connection we make has different symbols, so it looks like the characters are in some way randomized, even though they are the same throughout a single connection.
If we give in input anything that's not one of the first 10 symbols (we'll call the first ten 0-9, and the eleventh -), it closes the connection. Depending on the picked option, the services asks us for 0, 1, 2 or 3 inputs, and then spits out a list of chinese strings.
Let's take one part of interaction1 as an example:
>>>
0
1
2
3
4
5
6
7
8
9
-
> 0
0 A
Here the server asks us which action we want to perform, we chose 0. The server spits out symbol 0 followed by a long string of chinese symbols "鱷鳘鰬鰛鳘鰑鳌鲯鳗鲳鱃鰢鲣鲴鲌鰊鲤鲜鰩鰽鱡鱒鳮鳖鰹鱖鳃鱘鰑鰊鰄鰆鱉鳼鱨鳢鱑鲀鲒鳆鰢鲔鰕鳤鳾鲳鲜鲉鱚鳞鲑鱔鳽鱄鳪鲥鰻鳲鲷鲉鱍鲚鲻鱲鰩鲜鰨鰶鰛鱪鱔鱭鳹鳤鳘鲻鱬鲈鲼鲭鲨鳨鱎鳯鳕鰷鲓鰣鲺鲜鳖鱻鱌鰫鱶鲓鰴鳶鳙鱽鳰鲼鲒鲵鱜鱸鰄鱒鰻鱱鲊鳧鲔鰢鰛鰲鳛鲵鲯鱤鰺鰮鱷鰐鱠鲓鲯鲷鲯鲙鳥鱝鰸鰚鱈鲒鲲鱱鳣鰂鳇鲫鳃鳾" (which we'll call A).
>>>
0
1
2
3
4
5
6
7
8
9
-
> 1
> A
1 A B C
We then try to use option 1, giving it as a parameter the string given by option 0 (A). It returns symbol 1 followed by our input, and then two strings, B and C. String B seems to be some sort of separator between input and output since it's present in option 1 2 3 4, but we'll see later that that is not the case.
Let's look at one last operation
>>>
0
1
2
3
4
5
6
7
8
9
-
> 3
> A
> C
3 A C B D
Here the user asks for option 3, and gives it two inputs: A and C (these are of course the same A and C as the earlier example, since they are both part of one big interaction with the server).
The server then answers with 3 A C B D: the option we asked, our two inputs, a "separator", and an output D.
After a bunch of operations, the server seems to give us a warning Too much! Disabling one option..., and disables option 9.
Let's now look at interaction2.txt.
>>>
0
1
2
3
4
5
6
7
8
9
-
> 9
> A
> B
2 B C D
4 E D C F
4 A D C G
6 H F I J
6 K G I L
5 J L I M
0 N
1 N C O
3 M N C P
3 P O C A
9 E A B A
Correct signature! This is the flag:
The user asks for option 9, and gives it two inputs "A" and "B" (of course these are different strings than the A and B of interaction1, since every interaction changes symbols and symbol strings).
The server spits out a bunch of lines, each resembling the outputs of various operations in interaction1.txt. So it seems like option 9 performs a bunch of operations on our inputs:
2 B C D: option 2 on input B returning string D4 E D C F: option 4 on inputs E and D returning string F9 E A B A: maybe option 9 on inputs E, A and B returning A?.This last line is interesting because it seems to have "A" as an output and as an input.
We try connecting to the server and asking it to use option 9.
>>>
0
1
2
3
4
5
6
7
8
9
-
> 9
> A
> B
2 B C D
4 E D C F
4 A D C G
6 H F I J
6 K G I L
5 J L I M
0 N
1 N C O
3 M N C P
3 P O C Q
9 E A B Q
Here the server returns us with 9 E A B Q, and doesn't give us the flag. We hypothesize that the server wants some A and B such that "9 E A B A". But what do these options do? Let's go back to interaction1.txt
0
1
2
3
4
5
6
7
8
9
-
> 3
> A
> C
3 A C B D
>>>
0
1
2
3
4
5
6
7
8
9
-
> 3
> D
> F
3 D F B F
Let's look at these two interactions with the server that use option 3. In the first block, the user performs option 3 with input A and C, and the servers gives back output D. In the second block, the user performs option 3 with input D and F, and the server gives back F, the second input.
Why did 3 give back a new string in one case, and one of the input in the other? Maybe D is some kind of identity element and this is all some kind of algebra? Let's find out.
We built a wrapper in python to facilitate working with the server, since copying and pasting strings of chinese isn't much fun.
We can call the function op(OPERATIONNUMBER, PARAMETERS), which will return the last string of chinese the server writes (what we think is the operation output).
This way we can easily combine operations with calls like a = op(0) and op(3, a, op(1, a)). The wrapper also tells us when it encounter as an output something it has seen before, for example if we wrote
op(3, b, op(3, op(1, a), a))
our script will return
0() = a
0() = b
1(a) = c
3(1(a), a) = d
3(b, 3(1(a), a)) = b
!!! 3(b, 3(1(a), a)) = b <-> 0() = b
telling us that op(3, b, op(3, op(1, a), a)) is equal to b itself
Next chapter lists all our findings
This operation seems to always give one number out of 7 random numbers
This operation acts like the additive inversion (with op3 being the addition), probably modulo N
<img src="https://render.githubusercontent.com/render/math?math=-((-a) %2b a) = -0 = 0"> <span style="color:red">[!]</span> mentions operation 3 (operation and identity element)
# 131aa = 31aa : -((-a)+a) = -0 = 0
assert op(1, op(3, op(1, a), a)) == op(3, op(1, a), a)
<img src="https://render.githubusercontent.com/render/math?math=-(-a) = a">
# 11a = a : -(-a) = a
assert op(1, op(1, a)) == a
This operation acts like the multiplicative inversion (with op4 being the multiplication), probably modulo N
<img src="https://render.githubusercontent.com/render/math?math=1/(a*(1/a)) = 1/1 = 1"> <span style="color:red">[!]</span> mentions operation 4 (operation and identity element)
# 242aa = 42aa : 1/(a*(1/a)) = 1/1 = 1
assert op(2, op(4, op(2, a), a)) == op(4, op(2, a), a)
<img src="https://render.githubusercontent.com/render/math?math=1/(1/a) = a">
# 22a = a : 1/(1/a) = a
assert op(2, op(2, a)) == a
<img src="https://render.githubusercontent.com/render/math?math=1/0 = 0"> <span style="color:red">[!]</span> mentions operation 3 (operation and identity element)
# 231aa = 31aa : 1/((-a)+a)) = 1/0 = 0
assert op(2, op(3, op(1, a), a)) == op(3, op(1, a), a)
This operation acts like the addition, probably modulo N
<img src="https://render.githubusercontent.com/render/math?math=a %2b b = b %2b a">
# 3ab = 3ba : (a + b) = (b + a)
assert op(3, a, b) == op(3, b, a)
<img src="https://render.githubusercontent.com/render/math?math=a %2b (b%2bc) = (a%2bb) %2b c">
# 3a3bc = 33abc = 3abc : a + (b + c) = (a + b) + c
assert op(3, a, op(3, b, c)) == op(3, op(3, a, b), c)
<img src="https://render.githubusercontent.com/render/math?math=b %2b ((-a)%2ba) = b %2b 0 = b">
# 3b31aa = b : b + ((-a) + a) = b + 0 = b
assert op(3, b, op(3, op(1, a), a)) == b
# together with other permutations (because of commutativity)
<img src="https://render.githubusercontent.com/render/math?math=(-a) %2b (a %2b b) = b">
# 31a3ab = b : (-a) + (a + b) = b
assert op(3, op(1, a), op(3, a, b)) == b
# together with other permutations (because of commutativity)
This operation acts like the multiplication, probably modulo N
<img src="https://render.githubusercontent.com/render/math?math=a * b = b * a">
# 4ab = 4ba : ab = ba
assert op(4, a, b) == op(4, b, a)
<img src="https://render.githubusercontent.com/render/math?math=a * (bc) = (ab) * c">
# 4a4bc = 44abc = 4abc : a*(b*c) = (a*b)*c
assert op(4, a, op(4, b, c)) == op(4, op(4, a, b), c)
<img src="https://render.githubusercontent.com/render/math?math=b * (1/a * a) = b * 1 = b">
# 4b42aa = b : b * (1/a * a) = b * 1 = b
assert op(4, b, op(4, op(2, a), a)) == b
# together with other permutations (because of commutativity)
<img src="https://render.githubusercontent.com/render/math?math=b * (1/a\times a) = b * @ = b">, <img src="https://render.githubusercontent.com/render/math?math=(@ \ne 1)"> <span style="color:red">[!]</span> mentions operation 5 (operation and identity element)
# 4b52aa = b : b * (1/a × a) = b
assert op(4, b, op(5, op(2, a), a)) == b
# together with other permutations (because of commutativity)
<img src="https://render.githubusercontent.com/render/math?math=1/a * (a * b) = b">
# 42a4ab = b : 1/a * (a * b) = 1 * b = b
assert op(4, op(2, a), op(4, a, b)) == b
# together with other permutations (because of commutativity)
<img src="https://render.githubusercontent.com/render/math?math=a * (b %2b (-b)) = a * 0 = 0">
# 5a3b1b = 3b1b : a * (b + (-b)) = a*0 = 0
assert op(4, a, op(3, b, op(1, b))) == op(3, b, op(1, b))
# together with other permutations (because of commutativity)
<img src="https://render.githubusercontent.com/render/math?math=a(b%2bc) = ab %2b a*c">
# 4a3bc == 34ab4ac : a * (b + c) = ab + ac
assert op(4, a, op(3, b, c)) == op(3, op(4, a, b), op(4, a, c))
<img src="https://render.githubusercontent.com/render/math?math=1%2b1%2b1%2b1 = (1%2b1) * (1%2b1)">
# 1 + 1 + 1 + 1 = 4 = (1 + 1) * (1 + 1)
n1 = op(4, op(2, a), a)
assert op(3, n1, op(3, n1, op(3, n1, n1))) == op(4, op(3, n1, n1), op(3, n1, n1))
<img src="https://render.githubusercontent.com/render/math?math=a * 2 = a %2b a">
# a * 2 = a + a
assert op(4, a, n2) == op(3, a, a)
Earlier, we said that when we called operation 1, 2, 3, and 4, the output looks like
INPUTS SEPARATOR OUTPUT, where separator is some string that looks like any other "number". After finding out that these operations are probably in modulo, we hypothesized thatSEPARATORis not actually a separator, but the modulo of operation. This seems to be correct since <img src="https://render.githubusercontent.com/render/math?math=0 %2b N = 0">, but we didn't investigate much further.
This was a weird one, this operations acts like op4, except it doesn't in some cases. It gives back the exact same results for small numbers (obtained adding 1, the identity element of op3, a bunch of times), but with numbers given by op0 it acts differently (probably because they are really big).
It seems like this is multiplication with some other modulo or maybe with no modulo. It probably just has a bigger modulo since we couldn't make it overflow or anything like that.
This would explain why <img src="https://render.githubusercontent.com/render/math?math=1/a*(a\times b)=b"> (using * everything goes back to modulo N), while <img src="https://render.githubusercontent.com/render/math?math=1/a\times (a\times b)\ne b"> (1/a is a different number than the inverse of a with respect to op5, since they have a different modulo).
Some other things we didn't write here point in this direction too, like <img src="https://render.githubusercontent.com/render/math?math=1* (a\times b) = 1* (a * b)"> even though <img src="https://render.githubusercontent.com/render/math?math=(a\times b) \ne (a * b)">.
<img src="https://render.githubusercontent.com/render/math?math=a\times b = b\times a">
# 5ab = 5ba : a × b = b × a
assert op(5, a, b) == op(5, b, a)
<img src="https://render.githubusercontent.com/render/math?math=a\times (b\times c) = (a\times b)\times c">
# 5a5bc = 55abc = 5abc : a × (b × c) = (a × b) × c
assert op(5, a, op(5, b, c)) == op(5, op(5, a, b), c)
<img src="https://render.githubusercontent.com/render/math?math=b\times 1 = b">
# 5b4a2a = b : b × (a*1/a) = b × 1 = b
assert op(5, b, op(4, a, op(2, a))) == b
# together with other permutations (because of commutativity)
<img src="https://render.githubusercontent.com/render/math?math=b\times 0 = 0">
5b3a1a = 3a1a : b × (a+(-a)) = b × 0 = 0
assert op(5, b, op(3, a, op(1, a))) == op(3, a, op(1, a))
# together with other permutations (because of commutativity)
<img src="https://render.githubusercontent.com/render/math?math=1/a * (a\times b) = b">
# 42a5ab = b : 1/a * (a × b) = b
assert op(4, op(2, a), op(5, a, b)) == b
# together with other permutations (because of commutativity)
<img src="https://render.githubusercontent.com/render/math?math=1/a\times (a\times b) \ne b">
# 52a5ab != b : 1/a × a × b != b
assert op(5, op(2, a), op(5, a, b)) != b
<img src="https://render.githubusercontent.com/render/math?math=@ * @ = 1">
# 452aa52aa = 42aa : (1/a × a) * (1/a × a) = @ * @ = 1
assert op(4, op(5, op(2, a), a), op(5, op(2, a), a)) == op(4, op(2, a), a)
<img src="https://render.githubusercontent.com/render/math?math=1/@ = 1">
# 252aa = 42aa : 1/(1/a × a) = 1/@ = 1
assert op(2, op(5, op(2, a), a)) == op(4, op(2, a), a)
<img src="https://render.githubusercontent.com/render/math?math=-@ = -1">
# 152aa = 142aa : -(1/a × a) = -@ != -1 = -(1/a * a)
assert op(1, op(5, op(2, a), a)) == op(1, op(4, op(2, a), a))
<img src="https://render.githubusercontent.com/render/math?math=@ \ne 1">
# 52aa != 42aa : (1/a × a) = @ != 1 = (1/a * a)
assert op(5, op(2, a), a) != op(4, op(2, a), a)
This operation acts like exponentiation with no modulo or with the same modulo as op5. It behaves well with op5, exponentiation rules work with it, while they often don't work with op4 (unless we're using small numbers)
<img src="https://render.githubusercontent.com/render/math?math=a^b \ne b^a">
#6ab != 6ba : a ! b != b ! a
assert op(6, a, b) != op(6, b, a)
<img src="https://render.githubusercontent.com/render/math?math=a^{(b^c)} \ne (a^b)^c">
# 6a6bc != 66abc : a ! (b ! c) != (a ! b) ! c
assert op(6, a, op(6, b, c)) != op(6, op(6, a, b), c)
<img src="https://render.githubusercontent.com/render/math?math=x^1 = x">
# 6b42aa = b : b ! (1/a * a) = b ! 1 = b
assert op(6, b, op(4, op(2, a), a)) == b
<img src="https://render.githubusercontent.com/render/math?math=1^x = 1">
# 642aab = 42aa : (1/a * a) ! b = 1 ! b = 1
assert op(6, op(4, op(2, a), a), b) == op(4, op(2, a), a)
<img src="https://render.githubusercontent.com/render/math?math=0^x = 0">
# 631aab = 31aa : ((-a) + a) ! b = 0 ! b = 0
assert op(6, op(3, op(1, a), a), b) == op(3, op(1, a), a)
<img src="https://render.githubusercontent.com/render/math?math=x^0 = 1">
# 6a31aa = 42aa : a ! ((-a) + a) = a ! 0 = 1 = (1/a * a)
assert op(6, b, op(3, op(1, a), a)) == op(4, op(2, a), a)
<img src="https://render.githubusercontent.com/render/math?math=3^2 = 3*3">
<img src="https://render.githubusercontent.com/render/math?math=a^2 \ne a*a">
<img src="https://render.githubusercontent.com/render/math?math=a^2 = a\times a">
# 3 ^ 2 = 3 * 3
assert op(6, n3, n2) == op(4, n3, n3)
# a ^ 2 != a * a
assert op(6, b, n2) != op(4, b, b)
# a ^ 2 = a × a
assert op(6, b, n2) != op(4, b, b)
<img src="https://render.githubusercontent.com/render/math?math=(2^3)^4 = 2^{(3*4)}">
<img src="https://render.githubusercontent.com/render/math?math=(a^b)^c \ne a^{bc}">
<img src="https://render.githubusercontent.com/render/math?math=(a^b)^c = a^{(b\times c)}">
# (2 ^ 3) ^ 4 = 2 ^ (3*4)
assert op(6, op(6, n2, n3), n4) == op(6, n2, op(4, n3, n4))
# (a ^ b) ^ c != a ^ (b*c)
assert op(6, op(6, a, b), c) != op(6, a, op(4, b, c))
# (a ^ b) ^ c = a ^ (b × c)
assert op(6, op(6, a, b), c) == op(6, a, op(5, b, c))
<img src="https://render.githubusercontent.com/render/math?math=a^{-1} \ne 1/a">
# a ^ -1 != 1/a
assert op(6, a, op(1, n1)) != op(2, a)
<img src="https://render.githubusercontent.com/render/math?math=a^b\times a^c \ne a^{(b %2b c)}">
# a^b × a^c != a^(b + c)
assert op(5, op(6, a, b), op(6, a, c)) != op(6, a, op(5, b, c))
<img src="https://render.githubusercontent.com/render/math?math=a^c\times b^c = (a\times b)^c">
# a^c × b^c = (a × b)^c
assert op(5, op(6, a, c), op(6, b, c)) == op(6, op(5, a, b), c)
OP5 and OP6 also have a "separator", but it's different from the separator of 1 2 3 4. This reinforces the theory that op5 and op6 are also in modulo, but with a different modulo, which is given in every op5 and op6 output.
We don't know much about op7, it asks for one input, and performs some operations of which we don't know the operands (we only know the operators).
This operator does exactly what 9 does, but it has 3 inputs: A B C, as opposed to 2 (one of the 3 inputs of op8 corresponds to one of the constants of op9). It then does the same operations as op9, but with some numbers permuted:
(A,B,C)[op9] = (B,C,A)[op8].
Here is where the magic happens, as we said earlier, op9 does a bunch of operations on two inputs A and B, and then gives a result Q. If Q == A then it also gives us the flag.
>>>
0
1
2
3
4
5
6
7
8
9
-
> 9
> A
> B
2 B (modN) 2B
4 C 2B (modN) 4C2B
4 A 2B (modN) 4A2B
6 D 4C2B (modM) 6D4C2B
6 E 4A2B (modM) 6E4A2B
5 6D4C2B 6E4A2B (modM) 56D4C2B6E4A2B
0 F
1 F = 1F
3 56D4C2B6E4A2B F (modN) 356D4C2B6E4A2BF
3 356D4C2B6E4A2BF 1F (modN) A
9 C A B A
Our goal is to find A and B for the equation
A = 3356D4C2B6E4A2BF1F(prefix notation), or, using the symbols we defined earlier:<img src="https://render.githubusercontent.com/render/math?math=D \wedge (C * 1/B) \times E \wedge (A*1/B) %2b F %2b (-F) = A">
We can rewrite this (because of associativity of + and because -F is the inverse of F) as
<img src="https://render.githubusercontent.com/render/math?math=D \wedge (C * 1/B) \times E \wedge (A*1/B) = A">
Now, we can rewrite this (thanks to the property of the exponentiation) as
<img src="https://render.githubusercontent.com/render/math?math=(D \wedge C) \wedge (1/B) \times (E \wedge A) \wedge (1/B) = A">
This pass might seem wrong because the operator * is used inside the exponent, and not the operator ×. However, because in the original equation, we add and subtract F, the result is modulo <img src="https://render.githubusercontent.com/render/math?math=N">, so everything should work properly. Next, thanks to another property of exponentiation, we can rewrite as
<img src="https://render.githubusercontent.com/render/math?math=(D \wedge C \times E \wedge A) \wedge (1/B) = A">
At this point, we can either continue trying to solve the equation for A or B, or try some numbers. We lost quite some time thinking that maybe we should find the modulo of op6, and we tried some strategies, but we realized that the modulo changed every time, and that it was also probably not the correct way to solve the challenge. So, we tried some numbers.
Since <img src="https://render.githubusercontent.com/render/math?math=1/0 = 0">, and <img src="https://render.githubusercontent.com/render/math?math=x^0 = 1">, forcing <img src="https://render.githubusercontent.com/render/math?math=B=0"> makes the <img src="https://render.githubusercontent.com/render/math?math=\text{LHS} = 1">. We can now force <img src="https://render.githubusercontent.com/render/math?math=A = 1">, which makes the <img src="https://render.githubusercontent.com/render/math?math=\text{RHS} = 1">, and the equation is solved.
Now that we solved the equation, we can just do
a = op(0)
n0 = op(3, a, op(1, a))
n1 = op(4, a, op(2, a))
op(9, n1, n0)
And the server returns us the flag: OOO{D0Y0uUnd3rstandWh4tANumberIs?}
