Tags: crypto vinegar
Rating:
## 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 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:
```text
==================================================
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][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 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:
```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 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
```text
==================================================
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}
```
[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
