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.


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

Original writeup (https://www.sigflag.at/blog/2019/writeup-newbiectf2019-bimilcode/).