---
tags: crypto, ctf
---
# Crypto CTF 2020 - Amsterdam
* 会場(今も鯖が生きている): <https://cryp.toc.tf/>
* これまでに解いた問題: https://hackmd.io/@Xornet/BkemeSAhU
## Writeup
### Outline
秘密のパラメータn, kが与えられ、nをデクリメントしながら、kと組み合わせ(combination)を取ったものと平文を比べていく。
もし平文の方が大きかったら暗号化配列に1を追加し、平文からその組み合わせを引く、ついでにkもデクリメントする。そうでなかったら0を追加する(正確には元々0で埋め尽くされた配列があるので単に1に変えるか何も変えないかの違いである)。
この配列をビット列の2進数表記とみなして整数にする。これを2で割るのを繰り返しながら同時に4の剰余を取った余りで決定される3進数表記された暗号文を作る。
その暗号文が与えられるのでこの操作を逆にたどり、n, kを特定して暗号文作成プロセスを再現する。
### Source
問題のソースコードは次の通り、そこまで長くないので貼る(若干コメントを加えている)
```python=
#!/usr/bin/env python3
from Crypto.Util.number import *
from functools import reduce
import operator
from secret import flag, n, k
# combination (n C k)
def comb(n, k):
if k > n :
return 0
k = min(k, n - k)
u = reduce(operator.mul, range(n, n - k, -1), 1) # n! // (n-k)!!
d = reduce(operator.mul, range(1, k + 1), 1) # k!
return u // d
def encrypt(msg, n, k):
msg = bytes_to_long(msg.encode('utf-8'))
if msg >= comb(n, k):
return -1
m = ['1'] + ['0' for i in range(n - 1)]
for i in range(1, n + 1):
if msg >= comb(n - i, k):
m[i-1]= '1'
msg -= comb(n - i, k)
k -= 1
m = int(''.join(m), 2)
i, z = 0, [0 for i in range(n - 1)]
c = 0
while (m > 0):
if m % 4 == 1:
c += 3 ** i
m -= 1
elif m % 4 == 3:
c += 2 * 3 ** i
m += 1
m //= 2
i += 1
return c
enc = encrypt(flag, n, k)
print('enc =', enc)
```
(tab文字でインデントしてるせいで`comb`関数コピペしたら動かなくて困った)
`comb`関数から見ていく。こいつは`n! // (n-k)!! // k!`を計算して返す、つまり ${}_n \mathrm{C} _k$ を返す。
続いて`encrypt`関数内だが、秘密になっている`n, k`のcombinationを取っている箇所が多い。ひとまず長さがnで先頭以外全部0の配列`m`が21行目で作られている。
続いて`range(1, n+1)`の範囲で`i`を回し、もし`msg >= comb(n - i, k)`であれば`m[i-1]`を`"1"`に変更する。そして`msg`から`comb(n-i, k)`を引いている。
これはビットの配列なのでくっつけて2進表記とみなして`m`に再代入している。
ここまでが暗号化の第1パートで次が第2パートになる。
続いて`m`を4で割った余りによって対応する操作が`m`が正の間だけ行われる。
もし余りが1なら暗号文(初期値0)に`3**i`を足している。なお`i`はwhileループの回数(初期値0)である。ついでに`m`をデクリメントしている。
余りが3なら暗号文に`2*3**i`を足している。ついでに`m`をインクリメントしている。
これらの場合もそうでない場合も`m`はかならず2で割られる。
こうして足された暗号文が最終的に出力される。
では、この手順を逆に辿って平文を導出することを目指す。
### `m`の逆算
暗号文`c`の逆算は`m`の剰余によって決まった。ここのコードを見ると`x*3**i`が`c`に足されており、`x`は次のようになっている(疑似matchコード)。
```
x = match (m % 4) {
1 => 1,
3 => 2,
_ => 0,
}
```
`i`はループ毎に1増えるため、`c`の最終結果を3進数で展開すれば各ループで`x`が何であったかが判明する。
また、同じく`m`を4で割ったときの余りに対応して`m`も変化するため、導出した`x`を逆にたどれば`m`の逆算も出来る。
また`m`は元々ビットの配列だったので、2進数表現に直せばそちらも手に入る。以後はこの配列を`m`とする。
### `n, k`の特定
次の復号手順を経る為に`m`から`n, k`を特定する。`n`は`m`の要素数なので簡単に求めることが出来る。ということで`k`を求めるだけだが、その前に`comb`の性質を幾つか挙げる。
1. `comb(n, n) = 1`
2. `comb(n, k) = 0 (n < k)`
3. `comb(n, k) = 1 (k <= 0)`
いずれも`comb`の定義から導出出来る。
ここで上の手順を経た`m`を表示すると次のようになる。
```
['1', '0', '0', ...
(snip)
'1', '0', '0', '0', '0', '1', '0', '0', '0', '0', '0']
```
末尾に`"0"`が続いていることがわかる。暗号化時に`m`を生成する時、`"1"`になる条件は`msg >= comb(n - i, k)`であった。ここで`i`は`range(1, n+1)`のイテレータで回っている事を鑑みると、最後は`i = n`になる。ということは`msg >= comb(0, k)`になる。
`m`の最後は`"0"`なのでこの条件は`False`であることから`msg < comb(0, k)`になる。
さて、`msg`が減るのは先程の条件だったが、`msg >= comb(n, k)`時に`msg -= comb(n, k)`となるので`msg`が負になることはあり得ない。よって最後のループでは`0 <= msg < comb(0, k)`が成立する。
この不等式と先程挙げた3つの性質のうち、2より`k > 0`であることはあり得ない。よって`k <= 0`となる。性質3より`0 <= msg < 1`が成り立つので`msg = 0`である。
`msg`が減算される時の条件に戻るとこの時`m[i-1] = "1"`になるので`msg`がどこで0になったかが判明する(ついでに`k`もデクリメントされる)。
ここで`k`が最終的に負になるかどうかを考える。もし、負になる場合、`msg -= comb(n-i, k)`は`msg -= 1`となる。そして次のような表が得られる。
|`k`|`comb(n-i, k)`|constraints|
----|----|----|
|1|`n-i`|`msg >= n-i`|
|0|1|`msg >= 1`|
|-1|1|`msg >= 1`|
|...|||
もし`k=1`の時の`msg`の減算で`msg = 0`とならなければ、その後0になるまで1が引かれ続ける事になる。したがって、`m[i-1] = "1"`の操作が2回以上連続して終わるはずである。
ところが`m`の終端を見るとそんなことは無い、よって`k=1`で無事に`msg = 0`になったことになる(同時に`k`も減算されて0になる)。
これ以後、`msg >= comb(n-i, k)`の条件は`0 >= 1`となるので常に偽である。すなわち`k, msg`は0のままだし、`msg[i-1]`も`"0"`から更新されない。
ということで`m`中の`"1"`の数を数えればそれが`k`に一致する...と言いたいところなのだが、最初の`"1"`に関しては元からそうなので`msg, k`の減算が発生したのかどうかはわからない。
冒頭の`msg >= comb(n, k)`時に`return -1`というコードに到達していないことと、それ以降もしばらく`msg >= comb(n-i, k)`を満たしていないことから`msg >= comb(n-1, k)`も満たさないだろうという仮定をして`"1"`の数より1小さい量を`k`とした。
`n, k`の両者を求めた(正確には仮定だが)のであとはこれを逆向きに辿って`msg`を復元する。`msg >= comb(n-i, k)`なら`m[i] = "1"`をして`msg -= comb(n-i, k)`もするので`m[i] = "1"`だったら平文(初期値0)に`comb(n-i, k)`を足すだけである。
これを`long_to_bytes`でバイト列にしたらフラグを含んだものが表示された。
## Code
```python=
from Crypto.Util.number import *
from functools import reduce
import operator
from xlog import XLog
logger = XLog("EXPLOIT")
# combination (n C k)
def comb(n, k):
if k > n:
return 0
k = min(k, n - k)
u = reduce(operator.mul, range(n, n - k, -1), 1) # n! // (n-k)!!
d = reduce(operator.mul, range(1, k + 1), 1) # k!
return u // d
def recalc_c(m):
c = 0
i = 0
while m > 0:
if m % 4 == 1:
c += 3 ** i
m -= 1
elif m % 4 == 3:
c += 2 * 3 ** i
m += 1
m //= 2
i += 1
return c
if __name__ == '__main__':
enc = 5550332817876280162274999855997378479609235817133438293571677699650886802393479724923012712512679874728166741238894341948016359931375508700911359897203801700186950730629587624939700035031277025534500760060328480444149259318830785583493
enc_org = enc
# mの逆算
cs = []
while enc > 0:
cs.append(enc % 3)
enc //= 3
s = 0
for i, c in enumerate(cs):
s += (3**i) * c
assert s == enc_org
m = 0
for c in reversed(cs):
m *= 2
if c == 1:
m += 1
elif c== 2:
m -= 1
assert recalc_c(m) == enc_org
m = list(bin(m)[2:])
n = len(m)
k = sum(x == "1" for x in m) - 1
print(m)
print(n)
print(k)
msg = 0
for i in range(1, n+1):
if m[i-1] == "1" and i != 1:
msg += comb(n-i, k)
k -= 1
print(long_to_bytes(msg))
```
## Flag
当日は出ていませんが、問題サーバーもバリデータも生きていたのでやりました
`CCTF{With_Re3p3ct_for_Sch4lkwijk_dec3nt_Encoding!}`
スクリプトを走らせた結果はこちら
```python=
$ xplt
['1', '0', '0', '0', '0', '0', '1', '0', '1', '0', '0', '0', '0', '0', '1', '1', '1', '1', '0', '1', '1', '1', '1', '0', '0', '0', '0', '0', '1', '1', '0', '0', '1', '0', '1', '1', '0', '0', '1', '0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '0', '1', '1', '1', '1', '0', '0', '1', '1', '1', '0', '1', '0', '1', '1', '1', '1', '1', '0', '1', '0', '0', '1', '1', '0', '1', '0', '0', '0', '0', '0', '1', '1', '1', '0', '1', '0', '1', '1', '1', '0', '0', '0', '1', '0', '1', '1', '0', '0', '0', '0', '0', '0', '1', '0', '1', '1', '1', '0', '1', '0', '0', '1', '0', '0', '1', '1', '0', '0', '0', '0', '1', '1', '0', '1', '0', '0', '0', '1', '1', '1', '1', '1', '0', '1', '0', '0', '0', '0', '0', '1', '1', '0', '1', '0', '1', '0', '1', '1', '1', '1', '1', '0', '0', '0', '0', '0', '0', '1', '0', '0', '0', '0', '0', '0', '0', '1', '1', '0', '0', '0', '0', '0', '1', '0', '0', '0', '1', '1', '0', '0', '1', '0', '1', '0', '1', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '0', '1', '1', '0', '1', '1', '1', '1', '1', '0', '0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '1', '0', '1', '0', '0', '1', '1', '0', '0', '0', '0', '1', '1', '1', '0', '0', '0', '0', '1', '1', '0', '1', '0', '1', '0', '1', '0', '1', '0', '1', '1', '1', '0', '0', '0', '0', '1', '0', '0', '1', '1', '1', '1', '0', '0', '1', '0', '0', '0', '0', '1', '0', '0', '0', '1', '0', '1', '1', '0', '0', '0', '0', '1', '0', '1', '1', '1', '1', '1', '1', '0', '1', '0', '0', '1', '0', '1', '0', '1', '0', '1', '0', '1', '0', '0', '0', '0', '0', '1', '1', '0', '1', '0', '1', '0', '1', '0', '0', '1', '0', '0', '1', '0', '0', '0', '0', '1', '1', '0', '1', '0', '1', '0', '0', '0', '1', '0', '0', '0', '0', '0', '1', '1', '1', '0', '1', '0', '1', '1', '1', '0', '0', '0', '0', '0', '1', '1', '0', '1', '1', '0', '1', '1', '1', '1', '0', '1', '1', '1', '0', '0', '1', '0', '0', '1', '1', '0', '0', '0', '0', '1', '0', '1', '1', '1', '0', '1', '0', '0', '1', '0', '1', '1', '1', '0', '0', '0', '1', '1', '0', '1', '1', '0', '0', '1', '1', '1', '0', '1', '0', '0', '1', '0', '0', '0', '0', '0', '0', '1', '1', '0', '0', '0', '1', '0', '0', '0', '0', '0', '0', '0', '1', '0', '1', '0', '0', '0', '0', '0', '0', '1', '1', '0', '0', '0', '0', '0', '0', '0', '1', '1', '0', '0', '0', '0', '1', '0', '1', '0', '1', '1', '1', '1', '0', '0', '1', '0', '1', '1', '1', '1', '1', '1', '1', '1', '0', '0', '0', '0', '1', '0', '0', '0', '0', '1', '0', '0', '0', '0', '0']
493
217
b'..:: CCTF{With_Re3p3ct_for_Sch4lkwijk_dec3nt_Encoding!} ::..'
```
## 感想
`k`は負にならないだろうというGuessをして無事に解けましたがせっかくなので証明を与えました、この証明が1番大変でしたが面白かったです。
あと最後の`n-i`を`n-1`とTypoして無限に時間を溶かした(30分ぐらい)上にこのTypoはよくやるので気をつけたいです。
Sign in with Wallet
Connect another wallet