Rating:
# Tokyo Western 2018: scs7
## Solution
If you want to know the gist of the solution, just look at the quick explanation. The rest of the writeup would simply be my approach in solving this problem. If you need code snippets for some of the parts, it'll be in the github repository.
### Quick Explanation
The encryption used is a mix of a special encoding and substitution cipher using the following steps:
1. m1 = base59encode(m)
2. m2 = substitution_encryption(m1, secret_mapping)
So to decrypt you first have to figure out the mapping used for the substitution cipher and then just reverse the process.
1. m1 = substitution_decrypt(m2, secret_mapping)
2. flag = base59decode(m1)
### Full Explanation
Based on some trial and errors, we can see gain insight from the input and output.
```
message: aaaa
ciphertext: vyCU1b
message: aaab
ciphertext: vyCU1H
message: a
ciphertext: 4R
message:
```
#### It's an encoding
Observe the differences between `aaaa` and `aaab`.
```
aaaa => vyCU1b
aaab => vyCU1H
```
This is a clue that this is either a shift cipher, substitution cipher, or simply some encoding. One clue that can it is an encoding if that _"close"_ characters result to _"close"_ output. Here is an example below, where we see `a`, `b`, and `c` result to ciphertexts all starting with `g`.
```
message: a
ciphertext: gA
message: b
ciphertext: gX
message: c
ciphertext: g1
```
#### It's base59
We enumerate all printable ASCII characters to see if this behavior holds true or if this is a coincidence.
```
message: 0
ciphertext: m
message: 1
ciphertext: z
2message:
ciphertext: 1
3message:
ciphertext: q
message: 4
ciphertext: F
...
message: 9
ciphertext: Z
message: :
ciphertext: 3
message: ;
ciphertext: uG
message: <
ciphertext: uu
...
message: A
ciphertext: uN
message: B
ciphertext: uR
message: C
ciphertext: u7
message: D
ciphertext: uS
```
So here it is clear that it is indeed some encoding. And we observe that it is notable that __starting `;`, the ciphertext is 2 digits__.
```
| character | value |
| --------- | ----- |
| `:` | 58 |
| `;` | 59 |
| `<` | 60 |
```
Since `;` is 59, then this is a clue that this is in base59, since this would be `10` in base59. This is further supported by `<`, value 60, which should be `11` in base59.
We see the mapping
```
| character | value | base59 | ciphertext |
| --------- | ----- | ------ | ---------- |
| `;` | 59 | 10 | uG |
| `<` | 60 | 11 | uu |
```
So this leads us to believe that this is __base59 encoding + substitution cipher__.
#### Finding out the substitution
However, we see that in each run, the substitution is different.
```
message: 9
ciphertext: k
message: :
ciphertext: z
message: ;
ciphertext: AU
message: <
ciphertext: AA
```
To do this, we generate a lot of ciphertext and since we know what the plaintext _(base59 of our message)_ should be, we can figure out what the mapping is.
```
encrypted flag: ZwkbWBK6s1Juy2PPamHctPBy4hCDe5aKKEg2boyQ0UXdXz453nwcnkRd0SQaXnFP
You can encrypt up to 100 messages.
message:
OMPrEcUtniP3tKswwMLLnhCRYbIAMkS7vxycrccg
ciphertext: sjyzwT6TUwUVUZ8Xs0e7jerDy8QQR3jRdcPVedAf5dxrUMqWXkfKq8E
message: vdBPbo7JqcrsQzU8ZzwvdvKOCxFK6wh9LL6ezeYX
ciphertext: xEeEDmYjuLUobQiTnP2NkoV3m8cTJWdKsh4EDd4EgkQNuyWqfWFZYKi
message: Q09UcgkIzd9Nt0BWXrX6wFc1kTrVhJACY0EmJeXc
ciphertext: s1WeVJdKJvGpVvQWZqExHJn61LTj3KiKuDAMP0eKdRpZuQwwJm2nJcW
message: 3QFMcEPpXitmaL05OcTrE0dIBajyAtujbccupUJl
ciphertext: sqnbSkc8K3L50UDGDrHiQsCMpCpPnAgFBbrTmxYX1p8kasngcYJ7VGE
message: NXY3IDTj6eKWvUVTMBLnE0XyjTnh70BtwSK8rXeC
ciphertext: sWfLryrSXGxo3MTBMTqzA3PmmtyR8GvzRTsH7ZBxKYwM6E09mFoer5x
```
And from this information, we know enough to get the flag.
`TWCTF{67ced5346146c105075443add26fd7efd72763dd}`
