2020 암호경진대회 3번 문제 풀이

출처 : cryptocontest.kr/

Home - SEC연구소 | 암호분석경진대회

해당 문제를 풀기 위해서는 library 등이 압축된 파일이 필요하지만 용량 문제로 인해 업로드하지 않았습니다. 압축파일은 위 SEC연구소 홈페이지를 통해 다운받으시면 됩니다.

 

3번은 블록암호 복호화 문제입니다.

(제가 아닌 다른 팀원이 푼 문제였습니다. 1번을 풀고 있었는데 하루만에 풀어와서 놀랐던 기억이 나네요 ㅎㅎ)

우선 문제에서 주어진 블록 암호는 ARIA-128입니다. ARIA-128은 KISA에서 만든 대한민국 표준 블록 암호 알고리즘입니다. 암호화 과정은 문제에 나온 것을 인용하면 다음과 같습니다.

평문 P를 q개의 블록으로 나누어 루프를 돌며 enc과 IV를 이용해 xor 연산을 주로 이루진 암호화를 합니다.

해당 문제는 복호화만이 필요하기 때문에 ARIA-128의 암호화 과정을 따로 적지 않겠습니다.

(나중에 여유가 된다면 따로 올리겠습니다.)

 

1. 문제 접근

 

블록 암호의 공격 방법은 다양합니다. brute-force와 같이 모든 경우에 대해 공격할 수도 있고, 오라클 패딩과 같이 패딩을 이용할 수도 있습니다. 또한 DPA, CPA 등 물리적 특성을 이용하여 공격을 할 수도 있습니다. (CPA는 4번 문제입니다.)그 외에도 다양한 공격 방법이 있습니다.

우선 오라클 패딩 공격 (oracle padding attack)을 사용해야하는 문제입니다. 문제에서 오라클 패딩이라고 따로 나와있지 않지만 문제를 잘 읽어보면 힌트를 얻을 수 있습니다.

"다음 첨부된 라이브러리 파일은 제시된 블록암호 운영모드에 대한 복호화를 수행한 후 평문에 적용된 패딩 패턴을 검사하는 API를 포함하고 있다. 해당 API를 사용하면 입력된 암호문에 대해 복호화된 결과에 대한 패딩 형식이 올 바른지에 대한 판별 결과를 얻을 수 있다."

라는 내용을 통해 오라클 패딩 문제임을 알 수 있습니다. ( 회사 oracle 아닙니다 ㅎㅎ)

 

오라클 패딩 공격이란, 암호문을 어떤 복호화 시스템에 적용하였을 때 패딩이 올바른지를 판단하는 오라클을 이용하여 복호화하는 것입니다. 올바른지 유무를 판단하는 API는 첨부파일에 주어져있습니다. 

 

이제 주어진 API를 활용하여 문제를 풀어봅시다.

 

2. 문제 풀이

 

오라클 패딩 공격을 사용해야하는 것만 깨달으면 쉬운 문제입니다. (물론 1번이 제일 쉬운 것 같습니다.)

문제에 주어진 암호문을 16byte 씩 자르면 총 29개의 블록으로 이루어집니다. 처음 IV 또한 주어져있습니다.

패딩 과정은 다음과 같습니다. 

n번째 암호문을 $C_n$, 복호화 결과를 $M_n$이라고 합시다. 첫 블록에서 $P_0$=$M_0$ ^ IV이고

첫 블록이 암호화가 진행되었고 맨 끝 자리가 패딩 되었다고 가정하면, IV[15] ^ $M_0$[15] = 0x80 입니다.

이제 IV[15] 값이 올바른지를 주어진 API를 사용하여 확인합니다. 이 때 0x00 ~ 0xFF 까지 256번 전수조사를 시행하면 됩니다. 그 중 올바르게 패딩된 결과만 출력하면 IV[15]=0x82가 됩니다. 이를 통해 $M_0$[15]=0x02 임을 알 수 있습니다. 

이제 맨 끝 자리가 아닌 끝에서 두번째 자리가 패딩이 되었다고 가정합시다. 패딩 방식이 처음에만 0x80을 패딩하고 나머지는 0x00을 패딩하므로 위에서 구한 0x02를 IV[15]=0x02로 세팅 후 IV[14]값에 대해 위와 마찬가지로 0x00 ~ 0xFF 에 대해 전수조사를 합니다. 이를 통해 똑같이 올바른 패딩 값인지 아닌지 판단할 수 있습니다.

이 과정을 계속 반복하면 $M_0$의 16byte 값을 구할 수 있고, IV와 xor 연산을 이용해 평문 $P_0$를 얻을 수 있습니다.

 

이 과정 이후 주어진 IV 가 아닌 이전 블록과 암호문의 xor 결과, 즉 $P_0$ ^ $C_0$, $P_1$ ^ $C_1$, ... 를 IV 대신 이용하면 됩니다.

이를 통해 $P_0$, $P_1$, ..., $P_{28}$ 의 결과를 얻을 수 있고 $P_{28}$ 블록을 찍어보시면 올바르게 패딩이 됨을 알 수 있습니다. 모든 P를 구했으므로 ASCII 코드를 이용해 영어로 변환하면 됩니다.

 

정답은 다음과 같습니다.

Recommendations for preventing novel coronavirus infection

1. Wash your hands with soap and running water.

2. Cover your mouth with your sleeve when coughing!

3. If you experience respiratory symptoms such as cough, must wear a mask.

4. Inform medical staffs of your travel history when visiting selected clinics.

5. Consult with your local public health center or call ‘1339’ or ‘Are a Code+120’ if you are suspicious of contract an infectious disease.

저는 오라클 패딩이란 것도 친구에게 설명을 들어서 바로 알았고, 친구의 문제 풀이 코드 또한 받아 큰 무리가 없었지만 처음 이 문제를 그냥 읽으면 조금 어려울 수도 있을 것 같습니다. 하지만 3번 문제 또한 고등부와 공통 문제로 주어졌고, padding attack에 대해 조금만 공부하시면 금방 해결하실 수 있을 것입니다. 소스코드는 친구가 짠 거라 따로 올리지는 않고 제가 수정 후 github에 올리겠습니다. 문제 해결에 필요한 API 또한 제공되고, 설명을 그대로 따라 가시면 API를 금방 사용하실 수 있습니다.

 

정답 내용은 코로나 방역 수칙에 관련 된 내용입니다. 코로나가 11월인 지금까지도 계속 이어져 내년에도 온라인 수업이 이어질 지 모르겠네요. 교수님 말씀으로는 아마 내년에도 1학기는 온라인으로 수업을 많이 할 것 같다고 하시고 저 또한 그렇게 생각합니다. 아무쪼록 여러분 모두 코로나 조심하시길 바랍니다.