Rating:

# SEC-T CTF 2019 : likeason

**category** : crypto

**points** : 1337

**solves** : 1

## write-up

I didn't solve this challenge during the contest.

This challenge is yet another rsa oracle, but the oracle only give us bin(m).count('1') & 0x1

It can still be solved using the same old technique, LSB Oracle Attack, only a little different

We send message 2 ** (0 * e) * c, 2 ** (1 * e) * c, ... and get the bit count parity of 2 ** 0 * m, 2 ** 1 * m, ...

There are two circumstances:
1. If the bit count parity is change, we are sure that there must be an overflow over n.
2. If the bit count parity is unchange, we know nothing ( just like John Snow )

### First Method

From the LSB Oracle Attack point of view:
1. If the bit count parity is change, L = (L + U) // 2
2. If the bit count parity is unchange, both of L = (L + U) // 2 and U = (L + U) // 2 are possible to happend, we need to try both possibilities.
3. Then we prune the path using the fact that the character set only contains '.-'

### Second Method

From the Bleichenbacher 1998 point of view:

If the bit count parity is change between 2 ** (s - 1) * m, 2 ** s * m, then we have the following condition:


let x = (2 ** (s - 1) * m) % n
0 <= x < n
n <= 2 * x < 2 * n


Simplified a bit, we get:


let k = (2 ** (s - 1) * m - 2 ** (s - 1) * m % n) / n
(k + 1/2) * n / 2 ** (s - 1) <= m < (k + 1) * n / 2 ** (s - 1)
(2 ** (s - 1) * m - n) / n < k <= (2 ** (s - 1) * m - n * 1/2) / n


Try all possible k to get many possible intervals of m, and union all intervals.
Everytime you will reduce the possible range of m, and finally get an interval of size 1 which is flag.
We also can prune out the intervals using the fact that the character set only contains '.-'

The performance of the second method is worth than the first one, maybe due to massive amount of union on intervals?

By the way, I use sage with python3

# other write-ups and resources

Original writeup (https://github.com/OAlienO/CTF/tree/master/2019/SEC-T-CTF/likeason).