This year is the second time I participate in the International Students’ Olympiad in Cryptography. The game is over, but the official results still not announced so I am not sure my solution is correct or not. However, I want to write how i found the solution. I will focus on the way to solution, not focus on algorithm because I am a noob. Please correct me if I am wrong in math (and English also, my English skill is very terrible)
This year I solved 4 challenges (maybe, because the result is pending). The solutions are following:
Problem 10: PIN code
We have 2 notes for this challenge:
- The picture below the task is not linked with the task and was used only for decorative purposes. So, there is no any PIN codes or digits related to the problem.
- A PIN code is an ARBITRARY number of ARBITRARY length (not 4).
I tried to choose some random value P then calculate the S i realize that most of them are 27, i was so surprised. However, there is something missing at the first time i read the challenge, i read more carefully and i found that the number P is an arbitrary number consisting of a few pairwise different digits in ascending order. Tried again with these numbers, the calculated S only had 1 value: 27. At this time, i knew the answer for this challenge but i didn’t know why. With a pen and a paper, i had my explanation:
Assume P is a number with 5 digits: P = abcde. We have A = 999*P = 1000*P – P
The solution of the numbers P satisfied this challenge’s condition will be as same as this one, but i was so lazy to write it generalize so i stopped here and insisted that my teammate (@cothan) help me to do it, hehe. He said that this challenge seem to be a secondary students’ test. Right, it was so easy, maybe it was used to encourage players.
Problem 5: A music lover
There are 2 remarks for this challenge:
- You should invent a way how to apply one code to another.
- Some arithmetic operations can also be used.
When i was doing this challenge, i didn’t know where i should begin. Too much thing in one picture:
- The morse code at the top
- The table with a lots numbers and letters
- & symbol
- A string with 11 letters
but in the description, they said that there are only 2 secret codes we need to know. I tried a lots of way. At the begining, i misunderstood that & operator is one of arithmetic operations, it wasted me a lots of time. I found that the morse string and the other string have same length (11). I was sure that 2 strings were belonged 2 secret codes Alex had used. And how about the table, still unknown. Trying to map these 2 strings with the table, i found that the letter O in the second string didn’t appear in the table so the table must be map with the morse string. After decoding the morse string i had STNEKMIHWAY.
However, i hadn’t known that a letter should be map with a number following or all of numbers following jet. If you don’t know which way to the destination, go all the way possible.
I tried to calculate sum of these numbers first, i get a list of numbers:
[4, 7, 5, 25, 25, 10, 4, 3, 5, 0, 6]
then add these numbers with the remain string i got EDVARDGRIEG
No meaning, i tried other way, just used a number following the letter in the table, i got a list:
[3, 1, 2, 8, 9, 2, 2, 3, 5, 0, 3]
this time i got DXSJBVERIED, seem to be better.
I thought that this string should be DISCOVERIED but it was wrong at 3 letters. I tried again, more carefully, but the result didn’t change. I tried some other similar way, still no hope. I wondered if the challenge correct or not. After discussing with my teammates, finally, one of my teammates (@quandoan a.k.a. qd) realized that EDVARDGRIEG is name of composer and pianist, lollllllllllllllllllllllllllllllllllllll. It is so sad when you find the secret but you dont know it is a secret then you waste the time for the wrong ways. F*ck my life! F*ck my knowledge about music. F*ck my “google search” skill. I hope that there is someone who doesn’t realize that like me, hoho.
Finally i knew that the & symbol was used to seperated 2 secret codes, lol. How noob i am.
Problem 8: Scientists
This challenge made me guess a lots. I tried anything possible, i searched for the biographies of those scientist. I thought about their year of birth, nationality, institution, school, award and honors, field, nobel prizes,….bla bla bla… .After wasting tons of time, i realized that i forgot 1 important thing: use brain. Fresh my mind and return to the beginning, read the description as careful as possible and i found something. I asked myself:
Why called set of paramaters? How many paramaters in a set? Why the secret was devided into 3 parts? Why a part was encrypted 3 times? One time is enough,… Too much questions so i can’t remember all of them. Just focus on some question above.
- Why the secret was devided into 3 parts? The parts of plaintext was encrypted with a 48-bits cryptosystem? We need 3 times encrypt the plaintexts with same parameters to attack this cryptosystem?…
- Why a part was encrypted 3 times? We need 3 ciphertexts of 1 plaintext with different parameters to attack this cryptosystem? This question make me remember to an attack on RSA cryptosystem that i did many times before. New hope.
Checked these scientists’ information again. I looked for some primes. Begin with the year of birth:
Charles Darwin : 1809 –> not prime
Tried with concatenation of the birthday:
Charles Darwin : 1221809 –> not prime
How about full birthday with the format DDMMYYYY
Charles Darwin: 12021809 –> prime
Michael Faraday: 22091791 –> prime
Werner Heisenberg: 5121901 –> prime
Johannes Kepler: 27121571 –> prime
Hans Christian Orsted: 14081777 –> prime
Mikhail Lomonosov: 19111711 –> prime
So magical, the light was right here. It couldn’t be a coincidence. I guessed that is RSA cryptosystem and the attack is using CRT to compute the plaintext which encrypted with small public exponent (e = 3). Check again for the sureness:
This meaned 3 divided phi(n) so i couldn’t compute the plaintext even if when i know phi(n) unless using CRT. No more doubt, almost reached the solution. The last thing to do was recover the plaintext with this such attack.
I also surprised when i did it, lol, so magical.
Conclusion:
The plaintext was PUTSTHEMINDINORDER
The property is: Birthday of them with format DDMMYYYY is a prime.
The cryptosystem is RSA, the attack is CRT with small public exp. (e = 3)
The whole sentence is: Mathematics should be studied if only for that it puts the mind in order
Problem 2: TwinPeaks
This challenge is so complicated for me. It make me waste a lots of papers, maybe a quarter of my notebook :'(. Wrote down, wrong, threw, repeated.
Note for the following sh!t i write:
- a, b, c, d is the original 32-bits words (plaintext)
- a’, b’, c’, d’ is the final 32-bits words (ciphertext)
+operator is the coordinatewise sum modulo 2 which is as same as XOR operator
Applied tranformation as same as step 3 in the description:
a’ = a + c + S(c + d)
b’ = a + b + d + S(c + d)
c’ = a + c + d
d’ = b + d + S(c + d)
Did this tranformation 6 times i got the final result (other tranformations are not necessary so i will not write here):
a’ = d + X1 + X2 + X4 + X5 + X6 (1)
b’ = c + X1 + X2 + X5 + X6 (2)
c’ = b + X3 + X4 (3)
d’ = a + X2 + X3 + X4 + X6 (4)
with:
- X1 = S(c + d) (5)
- X2 = S(a + b + c + X1) (6)
- X3 = S(a + b + X2) (7)
- X4 = S(b + c + d + X3) (8)
- X5 = S(c + d + X4) (9)
- X6 = S(a + b + c + X1 + X5) (10)
Combined (1), (2) i got:
a’ + b’ = c + X1 + X2 + X4 + X5 + X6 + d + X1 + X2 + X5 + X6
= c + d + X4 (11)
==> X4 = a’ + b’ + c + d
Combined (1), (2), (3) i got:
a’ + b’ + c’ = b + c + d + X3 (12)
==> X3 = a’ + b’ + c’ + b + c + d
Combined (3), (4) i got:
c’ + d’ = a + b + X2 + X6 (13)
This challenge provided a link for testing the encrypt function, but it no longer available. At first, i tried with 128 bits 0 which is 00000000000000000000000000000000 in hexadecimal notation. The server returned 9EB684838EFA7E766FFAA1B6804583D4
Rewrite the fomula:
X1 = S(0)
X2 = S(X1)
X3 = S(X2) = a’ + b’ + c’
X4 = S(X3) = a’ + b’
X5 = S(X4)
X6 = S(X1 + X5)
I knew a’, b’, c’ after encypting 128-bits 0 so i could know X3 (input of function S) and X4 (output of function S). But i couldn’t control this input.
Called this X3 is XXX, i had
XXX = a’ + b’ + c’
= 0x9EB68483 + 0x8EFA7E76 + 0x6FFAA1B6
= 0x7fb65b43
I tried some way to control the input of S function. I spent long time to found out: if i input 4 32-bits words with format:
a = b != 0
c = d = 0
i could control the input of S function. Rewrite the formula:
X1 = S(0)
X2 = S(X1)
X3 = S(X2) = a’ + b’ + c’
X4 = S(b + X3) = a’ + b’
X5 = S(X4)
X6 = S(X1 + X5)
Noticed that this time the value of X3 equal to S(S(S(0))). It is as same as the value of XXX above. I knew this value, i could control the value of b so i could control the input of S function and got the output of arbitrary input (oracle).
At this time, i had an oracle, the remaining problem was how can i recover the plaintext within only ciphertext and an oracle.
Backed to the generalized fomula, tried to do something with these fomula.
Combined (8), (12), i got that:
X3 = S(a’ + b’ + c’)
Similar with (9), (11):
X4 = S(a’ + b’)
(2), (3), (4) ==> b’ + c’ + d’ = a + b + c + X1 + X5 (14)
(10), (14) ==> X6 = S(b’ + c’ + d’)
(6), (14) ==> X2 = S(b’ + c’ + d’ + X5)
(5), (11) ==> X1 = S(a’ + b’ + X4)
(7), (13) ==> X3 = S(c’ + d’ + X6)
I had an oracle, i had a way to calculate all value (X1, X2, X3, X4, X5, X6), Uh, i had a solution.
Tried to recover the plaintext of the ciphertext 59A0D027D032B394A0A47A9ED19C98A8. To compute X4, i need the output of function S with the input equal a’ + b’ (0x59A0D027 + 0xD032B394 = 0x899263b3). So i added this wanted input with XXX to get b value:
b = 0x899263b3 + 0x7fb65b43
= 0xf62438f0
then i encrypted f62438f0f62438f00000000000000000. The output could be used to calculate X4. The others were the same.
When i had all values of (X1, X2, X3, X4, X5, X6), it was very easy to compute the plaintext:
a = d’ + X2 + X3 + X4 + X6
b = c’ + X3 + X4
c = b’ + X1 + X2 + X5 + X6
d = a’ + X1 + X2 + X4 + X5 + X6
The plaintext was: 43abeccaa53cb953f35239e79cc900ee
Conclusion
That’s all. My team solved 2 another problems but my teammates did it so i don’t write it here. I only write what i did.
Thanks for the great challenges, i learned a lots . I haven’t tried hard like i did last week for a long time. I hope my boss can’t see this blog because i did those challenge almost the time at the office 😀 😀
I will participate nsucrypto 2018 for sure! 😀
bomotodo 