암호 뉴비의 암호 깨는 대회 출전기

컴퓨터과학 • 2020년 10월 31일

2020 암호분석경진대회에 참가하였고, 고등부 2등으로 장려상을 수상하였다.

Screenshot_2020-09-25--------SEC------------

아직도 어떻게 상받았는지 이해가 안간다.

암호분석경진대회가 유명하지는 않은 대회이기 때문에 간단하게 설명하자면, 취약점을 발견하여 암호화 키를 얻거나 평문을 얻는 등 암호를 해독하는 등의 문제를 푸는 대회라고 할 수 있다. 이 대회는 일반부와 고등부로 나뉘어 있는데, 일반부와 고등부가 공통으로 해결해야 하는 3문제가 있고, 일반부는 2문제를 더 해결해야 한다. 나는 3문제 중 2문제를 해결하였고, 여기에 내가 문제를 분석하고 해결하려고 시도한 과정을 중점적으로 설명하려고 한다. 문제가 무엇인지 궁금하다면, 암호분석경진대회 사이트에서 문제들을 다운로드하면 된다.

대회 총평

제목에서도 알 수 있지만, 나는 암호에 대해서 거의 아무것도 모르는[1] "뉴비" 상태로 대회에 참가하였다. 이러한 이유로 문제를 풀기 위해 여러 가지를 검색하고 책을 읽으면서 배우면서 얻는 것이 많았다고 생각한다. 또, 2019년에도 이 대회에 참가하려고 했는데, 2020년과 2019년 대회의 문제 난이도 차이는 엄청나다는 느낌을 얻었다. 2019년 대회의 경우 첫 번째 고전 암호 문제는 XOR 한번만 하면 끝났고, 두 번째 암호구현 문제는 지금과 비슷하고, 세 번째 문제는 관련해서 조금만 찾아보면 나오는 유명한 취약점을 이용하면 되기 때문이다.

1번: 힐 암호에 대한 COA (Ciphertext Only Attack)

첫 번째 문제는 힐 암호화된 텍스트가 주어졌을 때, 암호화키와 평문을 구하는 문제이다. 힐 암호화는 행렬 곱을 이용하는 암호인데, 암호화와 복호화가 일종의 선형 변환이다. 암호화/복호화 과정을 설명하기 위해 다음과 같은 문장을 암호화한다고 해 보자. 문장은 대소문자 구분 없는 알파벳으로만 이루어져야 한다.

IHATECLASSICCIPHER

이때, 이 글자들에 대해 A를 0, B를 1, ... Z를 25로 바꿔서 모든 성분이 \(\mathbb{Z}_{26}\)에 속하는 벡터를 만들 수 있다.

\[(8, 7, 0, 19, 4, 2, 11, 0, 18, 18, 8, 2, 2, 8, 15, 7, 4, 17)\]

암호화를 위해서는 \(\mathbb{Z}_{26}\)에서 정의되었고 역행렬이 존재하는[2] \(N\)-by-\(N\) 정사각행렬이 하나 필요하다. 이때 \(N\)은 암호화를 할 때의 블록 크기이다. 힐 암호는 블록 단위로 암호화/복호화를 수행하므로, 블록 크기 \(N\)은 평문 길이의 약수여야 한다. 여기서는 다음과 같은 3 by 3 행렬을 이용할 것이다.

\[\begin{pmatrix}6 & 24 & 1\\ 13 & 16 & 10\\ 20 & 17 & 15\end{pmatrix}\]

이제, 원래의 암호문을 3블록 단위로 쪼개서 행렬곱을 하면 된다.[3] 첫 번째 블록은 앞의 벡터에서 첫 3개 성분을 취한 것이고, 알파벳으로는 "IHA"이다.

\[(8, 7, 0)\begin{pmatrix}6 & 24 & 1\\ 13 & 16 & 10\\ 20 & 17 & 15\end{pmatrix}=(9, 18, 0)\]

암호화 결과 \((9, 18, 0)\)이 나오고, 알파벳으로 나타내면 "JSA"이다. 이렇게 평문을 한 블록씩 블록씩 반복하여 행렬 곱으로 암호화를 하면 다음과 같은 암호문을 얻을 수 있다.

JSAYILKYVSWYAPVSBQ

복호화를 할 때에도 암호화와 거의 비슷하지만, 다른 점은 곱하는 행렬이 암호화를 할 때 사용했던 것의 역행렬이여야 한다는 것이다. 첫 번째 블록에 대해 예를 들자면, 다음과 같이 곱하여 결과를 얻을 수 있을 것이다.

\[(9, 18, 0)\begin{pmatrix}8 & 5 & 10\\ 21 & 8 & 21\\ 21 & 12 & 8\end{pmatrix}=(8, 7, 0)\]

문제에서 요구하는 것은 힐 암호화 방식으로 암호화된 주어진 암호문에서 평문을 얻는 것이다. 문제에서 준 암호문은 다음과 같다.

HRDKHUBHAAMAEQMTMZSHGBAKFUBHAASYRXUNKYUAATQCTLUTOGEWVAJGVEIIYTKIOTQRXXQVSQLISVVOCNGCUXPKPIUBOHTVKCFKWNJSEZYSSUTUOESIXKAPVFXNZHAOQTLCGYJVAEHLNNKEESQMKSHKKDFCNZSRHRDKHSDKFXVPTGMKRUPZBIKEVNYEKXMFXKFYMWYUDZDENEWNKDAOUXGPCXZDLCSNFGCMCSNUAOJDBLQTAHEWYZCHQJYKSNUWOKQKONZGOKDXGUXKEMWQMCFGUEAVKHDIIATCHVTGYMGKJMLNPCNAYKMIRWEETIYQKELEGLQOVKISFNUDAJQIQYBXQTMZSHGBAKFZRCNWRSODAFKKXWGAZGDBIUDDHCUDFRFOVSZXADSHYSGLTQBMNEMKDCFSOZSRDYLIHIAXCMGMFEIDNZKOVJEOIEFNWWQEDRLZYZIZXADSHYSGLJYFWDUAKSIOGOZOXWYPBUFEPNBIRJUJNDZJJYMURKNCIKPWLRMRIAGVSXTYNIWPROHLDHQOMBEKZURQCLQOVKISFNUAFQBHGPCLHZTPJVPXIZKLQSNVKIJAEITTNVSVWNFYVATDEMKDCTGIHKZTVGZYXTYQEDBACFMNCAHRDKHSDKFXZXXGMJOSLPSZBMOILMMWRALAFFMNXXDYFBIYQVVOHSWKGBIRJGTBYQLKIJAEQBTAXGFGAVUIJADHQKLFWRJXYFVIGGQZNBHSUIYOZALSKIABLWQNXNXKOAJAIKHXODXWORVDOGBMHOPLQJZALQJZALIKTKLENZHQAVYUEUFEVLUXHGOWNMGWXUIAHGQOMNCKFQLIPBNKVWDLNGMJCOBFKIGBYWPAHMMPQLUTOGECXITZVVAJEOIDCNWMFNLOBGQXCYFWQFWVXWRKWYGBFHJVLBAWBOUQEKHZHSZZIZARYITDCLQFPGBTJMQVSQLIHPEJONCYMZWTVJVZOBOMOHPSXMPUKVAGXIPOQUQUQBCKXZJSZAHEWYHAEMKOJCCCFBEUKVNCAWANSNXISVVOWHQGQFBGWKQEGBIFRGIZUJQWIMFANTGBHWGVAGXIPOQUQTTRMWDHDGRFENKYPZVCLNQAUBTZSRYGVGOWSVROENABMZTOHZRQFUEVPLLIODEYRYLUTOGPYAFHJFIVOSFMPBSHLEKWYWJYTFYETAZQCRFTFHOMACOQVTWKLKYMGIMQDSYNWMFNIEITWMBVVWANBQFVUSKZOTLCCWABAGHWZBZHRDKHDTUOMUUUGQICHNUUQFJYUCQUO

암호문이 참 길다. 이와 같이 암호문만 갖고 평문과 키를 얻어야 하는 공격 모델에 대해서는 평문에 대한 정보가 어느 정도 있어야 성공적인 공격이 가능하다. 여기에서는 평문이 의미가 있는 영어 문장이라는 가정을 하였다. 이러한 가정이 있다면, 복호화 키를 시도해 보면서 문장이 얼마나 '의미 있는지'를 나타내는 지표가 최대화되는 것을 답이라고 할 수 있을 것이다. 여기에서는 얼마나 '의미 있는지'를 계산하는 지표로 IC(Index of Coincidence)를 사용하였다. IC는 텍스트로 어떤 숫자를 계산하는 것인데, 다음과 같은 수식으로 계산한다.

\[IC(P)=\displaystyle\sum_i \hat{f}_i f_i\]

여기에서 \(f_i\)는 텍스트의 \(i\)번째 알파벳의 비율이고, \(\hat{f}_i\)는 \(i\)번째 알파벳이 일반적인 텍스트에서 차지하는 비율이다. 수식으로만 보면 이해하기 어려울 수 있는데, 다음과 같이 코드로 보면 이해가 더 빠를 것이다.[4]

monogram_prob = np.array([
    0.082, 0.015, 0.028, 0.043, 0.127, 0.022, 0.020, 0.061,
    0.070, 0.002, 0.008, 0.040, 0.024, 0.067, 0.075, 0.019,
    0.001, 0.060, 0.063, 0.091, 0.028, 0.010, 0.023, 0.001,
    0.020, 0.001
])

def normalized_freq(text):
    counter = Counter(text)
    result = np.zeros((26,))
    for i in range(26):
        if i not in counter:
            continue
        result[i] = counter[i]
    return result / len(text)

def index_of_coincidence(text):
    return sum(normalized_freq(text) * monogram_prob)

monogram_prob은 앞서 설명한 \(\hat{f}_i\)를 나타낸다고 할 수 있고, normalized_freq는 텍스트를 입력 받아서 정규화된 빈도수를 계산한다.[5] index_of_coincidence는 IC값을 계산하는 함수이고, 간단하게 numpy의 브로드캐스팅 연산을 이용하였다.

무식하게 모두 시도해본다면, 답을 구하는 데에 필요한 연산량과 시간은 블록 크기에 따라 바뀐다. 이 암호문의 길이는 1285글자이므로, \(1285=5\times257\)이기 때문에 블록 크기는 5 또는 257이다. 행복회로를 32768번 돌린 후, 나는 블록 크기가 5라는 결론을 내렸다. 만약 블록 크기가 \(d\)일 때 무식하게 모든 경우의 수를 계산해서 행렬을 구한다면, \(d^3 26^{d^2}\)번의 계산을 해야 할 것이다. 최종적으로 내가 이 문제를 풀기 위해 사용한 알고리즘이 대략 \(d26^d\)번의 계산을 하는데, 계산을 완료할 때까지 구글 클라우드에서 무료로 제공하는 f1-micro 인스턴스에서 약 5시간이 걸렸다. 대충 계산해 보았을 때, 무식한 알고리즘을 이용한다면 약 150일이 필요하다. 대회 문제가 6월에 공지되었고, 8월 말이 제출 기한이라는 것을 생각하면, 대회 문제가 공지되자마자 코드를 작성해서 실행시킨다고 해도 기한 안에는 답이 나오지 않을 것이다.[6] 효율적인 알고리즘이 필요한 것이다.

우선, 평문에서 \(d\)글자씩 건너뛰어서 알파벳 분포를 계산해도 원래 평문과 비슷하다는 생각을 할 수 있다. 다시 말해, 모든 행렬에 대해 최대 IC값을 주는 조합을 찾는 것이 아니라, 행렬의 열벡터를 모두 시도해서 가장 높은 IC값을 주는 \(d\)개를 찾으면 될 것이다. 이 경우 알고리즘의 시간 복잡도를 \(O(d^3 26^{d^2})\)에서 \(O(d^3 26^d)\)로 줄일 수 있다. 또한, 약간의 변환을 거치면 여기에서 시간 복잡도를 더욱 개선할 수 있다. 이 부분은 상당히 지엽적인 이야기이므로 '더 읽을거리'에 링크한 논문을 참고하자.

이러한 방법을 사용하여 구현한 코드를 5시간동안 구글 클라우드의 f1-micro 인스턴스에서 실행한 결과, 다음과 같은 키 행렬을 얻었다.[7]

\[\begin{pmatrix}3 & 17 & 12 & 9 & 18 \\ 19 & 24 & 18 & 7 & 12 \\ 11 & 13 & 4 & 12 & 6 \\ 2 & 11 & 9 & 20 & 16 \\ 3 & 21 & 0 & 13 & 23 \end{pmatrix}\]

또한, 평문은 다음과 같다.

cryptanalysisisthestudyofanalyxinginformationsystemsinthestudyofanalyzinginformationsystemsinordertostudythehiddenaspectsofthesystemscryptanalysisisusedtobreachcryptographicsecuritysystemsandgainaccesstothecontentsofencryptedmessagesevenifthecryptographickeyisunknowninadditiontomathematicalanalysisofcryptographicalgorithmscryptanalysisincludesthestudyofsidechannelattacksthatdonottargetweaknessesinthecryptographicalgorithmsthemselvesbutinsteadexploitweaknessesintheirweakimplementationeventhoughthegoalhasbeenthesamethemethodsandtechniquesofcryptanalysishavechangeddrasticallythroughthehistoryofcryptographyadaptingtoincreasingcryptographiccomplexityrangingfromthepenandpapermethodsofthepastthroughmachineslikethebritishbombesandbolossuscomputersatbletchleyparkinworldwartwotothemathematicallyadvancedcomputerizedschemesofthepresentmethodsforbreakingmoderncryptosystemsofteninvolvesolvingcarefullyconstructedproblemsinpuremathematicsthebestknownbeingintegerfactorizationgivensomeencrypteddatathegoalofthecryptanalystistogainasmuchinformationaspossibleabouttheoriginalunencrypteddatatisusefultoconsidertwoaspectsofachievingthisthefirstisbreakingthesystemthatisdiscoveringhowtheenciphermentprocessworksthesecondissolvingthekeythatisuniqueforaparticularencryptedmessageorgroupofmessage

2번: 암호 최적화

이 문제의 경우에는 아두이노에서 동작하는 "ARX 암호"의 암호화 코드를 주고 이를 최적화하는 것이었다. 원래 코드를 실행해 보면 벤치마크에서 3909ms가 걸린다고 나온다. 원본 코드에서 주목할 만한 부분은 고정된 횟수만큼 실행되는 반복문이다. key_gen 함수와 enc 함수에서 ROUND_NUM번 반복하는 for문을 볼 수 있다.

보안 취약점 Spectre의 설명에서도 언급한 적 있지만, CPU는 if나 for과 같은 분기에서 큰 성능 타격을 입는다. 분기는 기본적으로 CPU가 코드의 실행 경로를 예측하기 힘들게 만들기 때문이다. 따라서 여기에서는 loop unrolling이라는 방법을 사용하여 이 루프들을 걷어내고, 루프가 돌아가는 횟수만큼 하드코딩했다. 쉽게 말하면, 다음과 같은 코드가 있을 때

for i in range(10):
    func(i)

다음과 같이 고친 것이다.[8]

func(0)
func(1)
...
func(9)

이러한 방법으로 최적화를 거치면 1600ms대로 실행시간을 최적화할 수 있다. 수상자 중에서는 500ms대까지(!) 최적화한 팀도 있었는데, 이들은 loop unrolling뿐만 아니라 비트 연산을 최적화하여 경우에 따라 더 적은 사이클로 계산할 수 있는 코드 경로를 따라가게 했다고 한다.

3번: 블록 암호와 패딩 오라클 (못품)

3번 문제는 풀지 못했지만, 어떤 문제이고 어떻게 접근을 시도했는지만 알아보자. 3번 문제는 ARIA-128이라는 블록 암호를 통해 패딩이 맞는지 검증하는 코드를 DLL 파일 형태로 제공한다. 패딩은 블록 암호화에서 암호문의 길이를 블록 크기에 맞도록 하기 위해 맨 뒤에 채워 넣는 값이다. 블록 암호화는 이름이 말하는 것처럼 평문을 크기가 정해진 블록 크기만큼 잘라서 블록 단위로 암호화한다. 따라서 암호문이 블록 크기의 배수가 아니면 암호화를 할 수 없기 때문에 길이를 맞추기 위해 패딩을 넣는 것이다.

이 DLL 파일은 Themida라는 실행 파일 보호 도구로 보호[9]가 걸려 있기 때문에 거의 블랙박스라고 보아도 무방하다. 문제는 암호문이 주어졌을 때, 이 암호문에 대응되는 평문을 찾는 것이다. 이렇게 암호문의 패딩을 검증하는 코드가 주어지고 평문을 알아내는 공격 모델을 패딩 오라클 공격 모델이라고 한다.

패딩 오라클 공격을 적용하는 방법은 블록 암호가 어떻게 사용되는지를 정하는 블록 암호화 운영모드에 따라 다르다. 이 문제에서는 PCBC 암호화 모드로 암호화가 진행되었다는 사실까지만 알게 되고 더 이상 진행하지 못했다.

주최측에 문제의 풀이 방법에 대해 질문을 했었는데, 주최측의 풀이를 간단히 요약하면, PCBC는 IV에 어떤 값을 XOR했을 때 XOR한 값을 뒤쪽 블록으로 전파한다는 점을 이용하였다. IV의 마지막 비이트에 0x01부터 0xff까지 XOR을 수행하여 패딩 오라클에서 복호화한 평문의 마지막 바이트를 0x80으로 만드는 값을 찾고, 이 값에 0x80을 XOR하여 평문의 마지막 바이트를 찾고, 이를 다른 바이트들에 대해서도 반복하여 전체 평문을 얻는 것이었다.

더 읽을거리

P.S. 내년에 이 대회 같이 나갈 파티원 1분 구합니다[10]

  1. 암호에 대해 아는 것은 암호가 무엇인지, AES나 RSA가 존재한다는 사실 정도밖에 없었다. ↩︎

  2. 역행렬이 존재하지 않으면 복호화가 불가능하다. ↩︎

  3. 행렬곱도 당연히 \(\mathbb{Z}_{26}\)에서 이루어져야 한다. ↩︎

  4. numpy에 대해 좀 안다면 이 코드가 엄청나게 비효율적이라는 것을 눈치챘을 것이다. Counter 객체를 만들어서 다시 numpy 배열에 접근하는 연산은 성능이 좋게 나올 수 없다. ↩︎

  5. 수학에서 보통 정규화되었다는 것은 합이나 크기가 1이라는 것을 의미한다. 여기에서 정규화된 빈도수는 텍스트의 알파벳 빈도수를 센 다음, 이들의 합이 1이 되도록 나눈 것을 의미한다. ↩︎

  6. 물론 이 알고리즘은 embarrassingly parallel하므로, 돈을 쏟아부어서 코어 개수를 많이 가지는 인스턴스 여러 개를 빌리면 기한 안에도 답을 낼 수 있을 것이다. 이제는 문제가 되는 것이 시간이 아니라 돈인데, 이 경우 172,594.77원을 지출해야 한다. 계산을 하고 의외로 놀랐는데, 이 대회의 가장 낮은 상의 상금이 100만원이므로 이득을 볼 수는 있기는 하다. ↩︎

  7. 사실 깃허브에 있는 코드를 실행하면 이 행렬과는 약간 다른 행렬이 나오고, 복호화한 평문도 각 블록마다 글자의 위치가 바뀌어 있다. 이는 알고리즘이 행렬의 열 단위로 계산하기 때문에 일어나는 현상이고, 해결하기 위해서는 눈대중으로 열을 재배치하거나 bigram frequency를 이용하여 가장 IC값이 높은 열의 순서를 계산하는 코드를 작성하면 된다. ↩︎

  8. 깃허브에서 제출한 코드를 보면 enc 함수에서는 완전히 unrolling을 안한 것을 볼 수 있다. 성능 테스트 결과 for 루프 전체를 unrolling 하는것보다 내부의 if 문만 걷어내는 것이 더 성능이 좋았기 때문에 이렇게 했다. 아무래도 -O3 컴파일러 옵션이 들어가서 그럴 것이라고 생각했는데 다른 참가자에 따르면 아두이노 IDE가 어차피 #pragma를 무시해서 상관 없다고 한다. 역시 컴파일러는 똑똑하다. ↩︎

  9. 암호학보다 리버싱을 먼저 배운 사람으로서 리버싱을 시도해 보았지만 Themida는 너무나도 강력했다. 사실 리버싱도 암호학만큼이나 뉴비 수준이라 당연한 것일지도 모르겠다. ↩︎

  10. 혼자 나가서 상관 있을지는 모르겠지만 수상자는 동일한 팀 구성으로 나갈 수 없기도 하고, 팀으로 참가하는 것을 전제로 출제한 문제들을 혼자 푸는 것이 마냥 쉽지는 않았다. 무튼 관심 있다면 카카오톡으로 연락 바란다. 아마 1명 이하가 연락할 것으로 예상한다. ↩︎

손량

하나고등학교 10기

추천 게시물

No results for your search, please try with something else.

Great! You've successfully subscribed.
Great! Next, complete checkout for full access.
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.