divN

$ cat foo.c
long long div(long long x) {
return x / N;
}
$ gcc -DN=$N -c -O2 foo.c
$ objdump -d foo.o

foo.o: file format elf64-x86-64

Disassembly of section .text:

0000000000000000
:
0: 48 89 f8 mov %rdi,%rax
3: 48 ba 01 0d 1a 82 9a movabs $0x49ea309a821a0d01,%rdx
a: 30 ea 49
d: 48 c1 ff 3f sar $0x3f,%rdi
11: 48 f7 ea imul %rdx
14: 48 c1 fa 30 sar $0x30,%rdx
18: 48 89 d0 mov %rdx,%rax
1b: 48 29 f8 sub %rdi,%rax
1e: c3 retq

$ echo “HarekazeCTF{$N}” > /dev/null
(Rev, 100 points)

foo.c を N=$N と定義したうえで、最適化してコンパイルした(-O2)もののアセンブリを読み解いて、$Nの値を探る問題。

アセンブラの記法は、%があることから判断してAT&T。つまり、movだったら左から右に移動している。

mov %rdi,%rax で、引数としてわたってきた %rdi が %rax にコピーされる。
movabs $0x49ea309a821a0d01,%rdx で、%rdx(データレジスタ)に ‭5326122949484875009‬ が入る。
sar $0x3f,%rdi で、%rdiには最上位1bitが最下位1bitとなり、それ以外はもともとの最上位1bitと同じになる。
imul %rdx で、%raxの値（つまり、引数で渡されたx）と%rdxの値を乗算したものの、上位を%rdxに、下位を%raxに格納する。
sar $0x30,%rdx で、%rdxの上位16bitが下位16bitとなり、上位48bitは最上位のbitと同じになる。
mov %rdx,%rax で、%rdxを%raxにコピーする。
sub %rdi,%rax で、%raxから%rdiを引いた値を%raxに格納する。

‭Nを求めるには、
‭(2**112) // ‭5326122949484875009‬ +1
をする。
（+1がなんで必要か正直分かってない。。）

関数の戻り値は rax で戻す。
引数はrdi, rsi, rdx, rcx, r8, r9の順でセットされる。（http://inaz2.hatenablog.com/entry/2014/07/04/001851）
long long型は64bit以上の整数を表現することができる。

fight

import random
import base64
import key

def xor(msg, key):
    return bytes([ch1^ch2 for ch1, ch2 in zip(msg, key)])

def gcd(x, y):
  while y != 0:
    r = x % y
    x = y
    y = r
  return x

def gen_seed(n):
  seed = 0
  for k in range(1,n):
    if gcd(k,n)==1:
      seed += 1
  return seed

s = 1
for p in b"Enjoy_HarekazeCTF!!":
  s *= p
seed = gen_seed(s)
random.seed(str(seed).rstrip("0"))

flag = key.FLAG
key = bytes([random.randint(0,255) for _ in flag])

enc = xor(flag, key)
print(base64.b64encode(enc).decode('utf-8')) #7XDZk9F4ZI5WpcFOfej3Dbau3yc1kxUgqmRCPMkzgyYFGjsRJF9aMaLHyDU=

いろいろ暗号化したものをBASE64エンコードしたら、
7XDZk9F4ZI5WpcFOfej3Dbau3yc1kxUgqmRCPMkzgyYFGjsRJF9aMaLHyDU=
になる。
そのひとつ前で enc = xor(flag, key)とあり、暗号化されたビット配列は、flagとkeyの排他的論理和であることが分かる。
そのため、既知である暗号化されたbit配列と、keyの排他的論理和を取れば、flagが分かる。

与えられたソースコードを少しいじって、keyを出そうと試みた。


import random
import base64

def xor(msg, key):
    return bytes([ch1^ch2 for ch1, ch2 in zip(msg, key)])

def gcd(x, y):
  while y != 0:
    r = x % y
    x = y
    y = r
  return x

def gen_seed(n):
  seed = 0
  for k in range(1,n):
    if gcd(k,n)==1:
      seed += 1
  return seed

s = 1
for p in b"Enjoy_HarekazeCTF!!":
  s *= p
# print(s)
seed = gen_seed(s)
random.seed(str(seed).rstrip("0"))
print(seed)
key = bytes([random.randint(0,255) for _ in range(45)])

print(key)

しかし、gen_seedに渡す引数が
4529255040439033800342855653030016000
と膨大であるため、for文を素直に回していたら間に合わない。

gen_seed でやっていることは、
1~4529255040439033800342855653030015999
のうち、
4529255040439033800342855653030016000
との最大公約数が1である数の個数を返している。

4529255040439033800342855653030016000
を素因数分解すると以下のよう

import sympy

print(sympy.factorint(4529255040439033800342855653030016000))

{2: 10, 3: 8, 5: 3, 7: 2, 11: 5, 19: 2, 23: 1, 37: 1, 53: 1, 61: 1, 67: 1, 97: 2, 101: 2, 107: 1}

包除原理を用いて、
4529255040439033800342855653030016000
と互いに素であるものの数を数える。
https://ja.wikipedia.org/wiki/%E5%8C%85%E9%99%A4%E5%8E%9F%E7%90%86

import itertools
import functools
import operator
import random
import base64

base64_ans = "7XDZk9F4ZI5WpcFOfej3Dbau3yc1kxUgqmRCPMkzgyYFGjsRJF9aMaLHyDU="
# print(base64.b64decode(base64_ans))

# 最後のBASE64化された文字列のビット配列
enc_flag_bit_array = ""
for tmp in base64.b64decode(base64_ans):
    enc_flag_bit_array += bin(tmp)[2:].zfill(8)

# 最終的な暗号化されたフラグのビット文字列
# print(enc_flag)

import sympy

# Sはランダム関数の種を生成する際に使う数
S = 4529255040439033800342855653030016000

factors = sympy.factorint(S)

# 包除原理を用いて解く
prime_factors_list = [p for p, _ in factors.items()]
# print(prime_factors_list)

# for tup in itertools.combinations(prime_factors_list,2):
#     print(tup)

# Sと互いに素にならない数の個数
not_tagainiso = 0

for i in range(1, len(prime_factors_list) + 1):
    for tup in itertools.combinations(prime_factors_list, i):
        if i & 1:
            not_tagainiso += S // functools.reduce(operator.mul, tup)
        else:
            not_tagainiso -= S // functools.reduce(operator.mul, tup)
seed = S - not_tagainiso
random.seed(str(seed).rstrip("0"))
key = bytes([random.randint(0, 255) for _ in range(45)])

key_bit_array = ""
for i in key:
    key_bit_array += bin(i)[2:].zfill(8)

ans_bit_array = ""
for e, k in zip(enc_flag_bit_array, key_bit_array):
    ans_bit_array += str(int(e) ^ int(k))

ans = ""
for j in range(0, len(enc_flag_bit_array), 8):
    ans += chr(int(ans_bit_array[j:j + 8], 2))

print(ans)

HarekazeCTF{3ul3rrrrrrrrr_t0000000t1nt!!!!!}