zer0ptsCTF 2023 - mimikyu Writeup

문제 바이너리와 두 개의 라이브러리 파일을 준다.

strip 되지 않았다.

 

 

mimikyu main 을 보자

일단 flag 길이가 40자인 것은 알 수 있다.

 

ResolveModuleFunction 일부:

매개변수로 받은 값이 해시값이고, 해시값을 통해 특정 라이브러리의 특정 함수를 호출하는 것을 알 수 있다.

 

LoadLibrary 후 ResolveModuleFunction 에 라이브러리와 해시값을 넘겨 원하는 함수를 호출하는 것을 유추할 수 있다.

실제로 call 하는 곳에 브포 걸고 확인하면 라이브러리 내의 함수를 호출한다.

첫 ResolveModuleFunction 호출은 gmpz_init 임을 알 수 있다. (r10)

브포걸고 계속 continue 해서 호출되는 함수들을 확인한다.

srand 로 시드 설정해주고, gmpz 변수 3개를 설정해준다.

 

rand() 로 얻은 값을 cap 함수에 gmpz 변수와 함께 넘겨준다.

 

cap 함수:

cap 함수를 보면 search.h 의 hcreate, hsearch 를 사용하는데 찾아보니 hash 관리해주는 라이브러리이다.

hcreate(size) : size 를 hash table 의 max size로 설정

hsearch(item, mode)

item { key , value } : 검색할 값

mode : FIND / ENTER

FIND : 없으면 null

ENTER : 없으면 add. 만약 max size 넘어가면 null

 

위 코드에선 ENTER 모드를 사용한다. 즉 매개변수로 받은 random 값을 hcreate 에 넘겨서 size를 설정하고, 

ENTER mode 로 계속 add 하여 max size 로 인해 null 을 반환할 때까지 gmpz 변수 값을 1씩 증가시킨다.

 

그래서 처음엔 100 을 넣으면 gmpz 변수 값이 100 이 될 거라 생각했는데 약간의 오차가 존재했고, 그 이유는 아직도 모르겠다.

 

암튼 쭉 뽑아보면 아래와 같다.

 

다시 돌아와 정연산 코드를 짜보면

 

이걸 어떻게 역연산하는지 머리가 안 굴러갔는데, c = x^a (mod b) 에서 x를 구할 수 있는 경우는 a b 가 소수라든지 특별한 값이어야 한다. 그래서 확인해봤더니

 

다 소수가 나왔다. 아마 hcreate table 의 특별한 규칙이 있나보다.

암튼 소수임을 안 상황에서, n 이 세 소수의 곱인 RSA 임을 알 수 있따.

 

d 를 구해주고 c ^ d mod n 으로 복호화할 수 잇다.

 

Flag : zer0pts{L00k_th3_1nt3rn4l_0f_l1br4r13s!}