[SECCON 2017] Vigenere3d writeup

문제는 다음과 같습니다. 

import sys
def _l(idx, s):
    return s[idx:] + s[:idx]
 
def main(p, k1, k2):
    s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefghijklmnopqrstuvwxyz_{}"
    t = [[_l((i + j) % len(s), s) for j in range(len(s))] for i in range(len(s))]
    i1 = 0
    i2 = 0
    c = ""
    for a in p:
        c += t[s.find(a)][s.find(k1[i1])][s.find(k2[i2])]
        i1 = (i1 + 1) % len(k1)
        i2 = (i2 + 1) % len(k2)
    return c
 
print main(sys.argv[1], sys.argv[2], sys.argv[2][::-1])
 
-------------
 
$ python Vigenere3d.py SECCON{**********************} **************
POR4dnyTLHBfwbxAAZhe}}ocZR3Cxcftw9

암호문을 만드는 과정을 간단하게 설명하자면, 

먼저 주어진 문자열 s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefghijklmnopqrstuvwxyz_{}" 을 이용해서 다음과 같은 테이블 t 를 만듭니다.

이런 식으로 테이블을 만들고 난 뒤, 평문 글자가 문자열 s에 있는 인덱스 값과 우리가 모르는 Key가 문자열 s에 있는 인덱스 값을 이용해서 암호문을 만드네요.

테이블에서 한 가지 발견할 수 있는 특징은, [[_l((i + j) % len(s), s) for j in range(len(s))] for i in range(len(s))]

이 곳에서 i + j 를 이용하기 때문에, 점점 한 칸씩 밀려서 a+b 의 값이 같다면, t[n][a][b]의 값도 같다는 점입니다. 예시를 들어본다면 다음과 같겠습니다.

위와 같은 특징 덕분에, 우리에게는 t[s.find(a)][s.find(k1[i1])][s.find(k2[i2])] 암호문을 만드는 이 부분에서 s.find(k1[i1]) + s.find(k2[i2]) 값이 중요한 것을 알 수 있습니다. 그런데 k2는 k1을 거꾸로 뒤집은 것이므로 s.find(k1) + s.find(k2) 는 중간을 중심으로 좌우대칭입니다. 그림으로 표현하면 다음과 같습니다.

ex)

s.find(k1) : 1 7 4 8 6 2 4 8 6 2 4 8 6 2

s.find(k2) : 2 6 8 4 2 6 8 4 2 6 8 4 7 1

----------------------------------------------------

s.find(k1) + s.find(k2) : 3 13 12 12 8 8 12 12 8 8 12 12 13 3

따라서 s.find(k1) + s.find(k2)의 7자를 알 수 있다면, 정확한 암호 키 없이도 암호문을 해독할 수 있을 겁니다.

공교롭게도 평문 앞 7글자 SECCON{ 에 해당하는 암호문 POR4dny를 알기 때문에 s.find(k1) + s.find(k2) 를 알 수 있습니다.

def _l(idx, s):
    return s[idx:] + s[:idx]
 
def estimate_key(known_plaintext, ciphertext):
    s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefghijklmnopqrstuvwxyz_{}"
    t = [[_l((i + j) % len(s), s) for j in range(len(s))] for i in range(len(s))]
    fakeKey = ""
    for i in range(0,7):
        for k1 in range(65):
            for k2 in range(65):
                if t[s.find(known_plaintext[i])][k1][k2] == ciphertext[i]:
                    if k1 == 64:
                        #print "{} {}\n".format(k1+k2,i)
                        fakeKey+=s[(k1+k2)%65]
    fakeKey = fakeKey + fakeKey[::-1] 
    print fakeKey    
    return fakeKey
 
def restore_plain_test (fakeKey, ciphertext):
    s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefghijklmnopqrstuvwxyz_{}"
    t = [[_l((i + j) % len(s), s) for j in range(len(s))] for i in range(len(s))]
    plain_text=""
    count=0
    for p in ciphertext:
        for i in range(65):
            if p == t[i][0][s.find(fakeKey[count])]:
                #print "{} ".format(i)
                plain_text += s[i]
                count=(count+1)%14
                break
               
    print plain_text
 
 
known_plaintext = "SECCON{"
ciphertext = "POR4dnyTLHBfwbxAAZhe}}ocZR3Cxcftw9"
fakeKey = estimate_key(known_plaintext,ciphertext)
restore_plain_test(fakeKey,ciphertext)
 

위와 같이 코드를 짜보면 다음과 같은 결과를 얻을 수 있네요.

SECCON{Welc0me_to_SECCON_CTF_2017}