###### tags: TSGCTF2021
# TSG CTF 2021 B??e64 Author's Writeupauthor: [@m1kit](https://twitter.com/m1kit)
## Problem Overview
- The server generates a 32 chars-length secret string encoded 8 times with base64.- You can know arbitrarily 124 chars among the 344 chars-length encoded message.- You need to guess the original secret 8 times consecutively.
## Hint
- Hint 1: In a single Base64 encoding, 6 bits of data become 8 bits. Thus there is some redundancy. Can you find redundant parts of some encoded secrets?- Hint 2: Assume you have enough information to restore the original message, can you write a brute-force algorithm to restore the original message from a masked base64 string?  - Hint 3: To get a good mask, you need to think of heuristic algorithms and/or entropy.
!! Solution below !!
↓
↓
↓
↓
↓
↓
## Solution### Find one possible original message from the masked messageLet's think about brute-forcing the original message from the masked message.
If you fix the first $n$ characters of the original message, the first $\left\lfloor \frac{4}{3}\left\lfloor \frac{4}{3}\left\lfloor \frac{4}{3}\left\lfloor \frac{4}{3}\left\lfloor \frac{4}{3}\left\lfloor \frac{4}{3}\left\lfloor \frac{4}{3}\left\lfloor \frac{4n}{3} \right\rfloor\right\rfloor\right\rfloor\right\rfloor\right\rfloor\right\rfloor\right\rfloor\right\rfloor$ characters of the encoded message are fixed as well.
So, you can try:- change the first character until the first encoded character matches, - change the second character until the first two encoded characters match, - change the third character until the first 22 encoded characters match,- and so on...
If it does not match, you will need to go back to the previous character.
```python=def almost_eq(seq, pat):  return all(s == p or p == '*' for s, p in zip(seq, pat))
def solve(s, n=32, charset=CHARSET):  assert len(s) == len(enc(' ' * n))
  dr = []  for i in range(n):    b = i + 1    for _ in range(8):      b = b * 8 // 6    dr.append(b)  dr[-1] = len(s)
  cur = 0  res = [0] * n  while cur < n:    m = ''.join(charset[x] for x in res)    c = enc(m)    if almost_eq(c[:dr[cur]], s[:dr[cur]]):      cur += 1    else:      res[cur] += 1      rc = cur      while res[rc] == len(charset):        res[rc] = 0        rc -= 1        res[rc] += 1  return ''.join(charset[x] for x in res)```
By this solver, you can quickly find the  lexicographically smallest possible original message. Similarly, you can find the lexicographically largest one.
Let's call the masked message is *unique* if the  lexicographically smallest one and the lexicographically largest one are identical.
### Construct a good maskI understand there are various approaches to do this. Let me introduce one of them.
I randomly sampled 1000 original messages and encoded them all, and calculated entropy for each character position in encoded messages. Clearly, we want to know a character position with high entropy.
I removed characters from low-entropy ones as long as it keeps *uniqueness* which we defined above. To determine *uniqueness*, I randomly sampled 32 messages.
By doing this I got this mask:```*******??**?***?***???***?*??****??**??**?**?*?**???***?***?*??***?**?**?****?*?**???**?**?**?*?***???*?*****?*???***??***?**?*?*?**?**?**?**?*?***?**??***?*?*?***?***?*?***?*??**??***?****?*?****?*?????****??**?*****??****?**?****???*??**??****??*?***??*?****?*?*??***??*****?*?**?****?**???***?**?**??******???**??***?*?**********************```With this mask we can guess 95% of messages correctly, which is sufficient for this problem.
BTW, do you notice there are only 122 `?`s in this mask?Yes, I increased number of allowed `?`s by two before the competition.
## AppendixThe flag was, `TSGCTF{Ba5e6A_has_a_f1xp0int}`.
I should have written it as "fixpoints", since there are some.
One fixpoint I know is, "".Clearly, an empty string is a fixpoint for `base64` operation.
Also, we have a fixpoint with infinity length string, starting with "Vm0wd2Qy".
```❯ echo Vm0wd2Qy | base64Vm0wd2QyUXkK
❯ echo Vm0wd2QyUXkK | base64Vm0wd2QyUXlVWGtLCg==```
In this problem, after 8 times encoding, the first part of the encoded string converges to this fixpoint, so the entropy of the first part is low.This is why first a few chars are useless when you create a mask.