Challenge

The challenge description only gives us the command nc prob.vulnerable.kr 20034 which is used to connect to the service. Doing so results in the following greeting:

==================================================
This is BiMilCode
I'll give you a chance to type 3 times.
Good Luck
# if you got it how to solve this problem type 0 .
==================================================
You can encode me? :  89 95 79 2e 53 87 62 51 
Input :

Service analysis

There is an input where we can enter arbitrary text. We have 3 tries before the service closes the connection. A sample of such a connection looks like this:

==================================================
This is BiMilCode
I'll give you a chance to type 3 times.
Good Luck
# if you got it how to solve this problem type 0 .
==================================================
You can encode me? :  89 95 79 2e 53 87 62 51 
Input : 11111111
83 58 56 39 45 83 64 4e 
you have 2 chance left.
Input : 22221111
84 59 57 3a 45 83 64 4e 
you have 1 chance left.
Input : 33221100
85 5a 57 3a 45 83 63 4d 
you have 0 chance left.
Think more about it.

While the challenge is located in the category Misc, it is a cryptographic challenge. Looking at the output shows us that the output is a list of hexadecimal numbers based on the input. We can, therefore, perform a chosen-plaintext attack on the service to reverse the encoded message.

From this example output alone, we can already derive some assumptions:

  • Each character is encoded independently. This can be seen because only the bytes are changed where the input character was changed as well.
  • The key does not change between the tries.
  • It is a character (block) based substitution cipher, which changes the character on a fixed offset. This can be seen because the first character was incremented by one every time, and the resulting byte incremented by one as well. A stream cipher with bitwise xor would not show this behavior.
  • The substitution differs on every input position. This can be seen because the same input character results in different output bytes depending on its position. This suggests a polyalphabetic cipher.

We can reason from those observations, that the challenge likely implements a block-based polyalphabetic substitution cipher, where each block has the size of one character. The subsitution is implemented as a fixed shift of the character, as done in the Caesar cipher. Because the substitution differs for every input character, it is a polyalphabetic substitution like employed in the Vigenère cipher.

Basic idea

  1. input at least n characters as encoded bytes present
  2. read the encoded message and calculate offsets, assuming an ASCII encoding of the characters
  3. apply the position-dependent offset on the encoded bytes to the calculate input

Exploit

Instead of doing it manually, I wrote a simple script to do the chosen-plaintext attack:

#!/usr/bin/env python3

encoded = input(" * Encoded message in hex: ").strip().split(' ')
encoded_bytes = [int(ch, 16) for ch in encoded]

input_str = "1"*len(encoded_bytes)  # can be anything
print(f" * Now send '{input_str}' to the server")

output = input(" * Result from server in hex: ").strip().split(' ')
output_bytes = [int(ch, 16) for ch in output]

offsets = [ord(i) - o  for i, o in zip(list(input_str), output_bytes)]
print(f" * Calculated offsets: {offsets}")

plaintext = [chr(e+o)  for e, o in zip(encoded_bytes, offsets)]
plaintext_str = "".join(plaintext)
print(f" * Plaintext is: {plaintext_str}")

Get the flag

==================================================
This is BiMilCode
I'll give you a chance to type 3 times.
Good Luck
# if you got it how to solve this problem type 0 .
==================================================
You can encode me? :  bb 7a 49 87 9b 99 86 6c 
Input : 11111111
8d 4c 3e 8f 8d 77 91 3c 
you have 2 chance left.
Input : 0
Oh really? come on ! : __<)?S&a
You did it!
KorNewbie{Nace_I_believed_it}