## 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:
```text==================================================This is BiMilCodeI'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 sampleof such a connection looks like this:
```text==================================================This is BiMilCodeI'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 : 1111111183 58 56 39 45 83 64 4e you have 2 chance left.Input : 2222111184 59 57 3a 45 83 64 4e you have 1 chance left.Input : 3322110085 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][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][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][caesar_cipher]. Because the substitution differs for every input character, it is a polyalphabetic substitution like employed in the [Vigenère cipher][vigenere_cipher].
## Basic idea
1. input at least n characters as encoded bytes present2. read the encoded message and calculate offsets, assuming an ASCII encoding of the characters3. 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:
```python#!/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 anythingprint(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
```text==================================================This is BiMilCodeI'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 : 111111118d 4c 3e 8f 8d 77 91 3c you have 2 chance left.Input : 0Oh really? come on ! : __<)?S&aYou did it!KorNewbie{Nace_I_believed_it}```
[substitution_cipher]:      https://en.wikipedia.org/wiki/Substitution_cipher[polyalphabetic_cipher]:    https://en.wikipedia.org/wiki/Polyalphabetic_cipher[vigenere_cipher]:          https://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher[caesar_cipher]:            https://en.wikipedia.org/wiki/Caesar_cipher