【국가암호공모전】 (II-A 분야) 문제 03 (2016)

국가암호공모전 (II-A 분야) 문제 03 (2016)

 

추천글 : 【암호론】 암호론 목차

---

1. 문제 [본문]

2. 풀이 [본문]

---

 

1. 문제 [목차]

개발자 X씨는 패스워드를 기반으로 파일을 암호화하는 암호모듈을 받아 제품을 개발하였다. 이때 패스워드 기반 암호화 모듈은 [표 1]과 같이 동작한다.

 

 

그러나 이후 패스워드 정책이 5자리에서 7자리로 변경되었다. 개발자 X씨는 쉽게 패치하기 위해 기존 암호모듈을 그대로 사용하여 다음과 같이 단계를 수정하였다.

 

공격자 Y씨는 패스워드 전수조사를 통하여 파일 복호화를 시도한다. 이때 공격자 Y씨가 [표 2]의 단계 2에 대하여 획득한 정보를 정리하면 다음과 같다.

 

정확히 7자리인 패스워드 각 자리를 {P1, P2, P3, P4, P5, P6, P7}이라 정의하자.

 

(1) P1, P2, P3, P4, P5 중 한 자리에 P6을 연산하여 새로운 값을 생성함

(예) P1 + P6 → P1 (새로운 P1은 0 ~ 255 사이의 값이 될 수 있음)

 

(2) P1, P2, P3, P4, P5 중 한 자리에 P7을 연산하여 새로운 값을 생성함

(예) P2 + P7 → P2 (새로운 P2는 0 ~ 255 사이의 값이 될 수 있음)

 

(3) 만약 (1)에서 P1이 사용되었으면, (2)에서는 P2, P3, P4, P5 중 하나가 선택됨

 

(4) 이항연산은 {+, -, *, /, %, ^, &, |, <<, >>} 중 하나를 선택하였음

 

※ 기존 5자리 패스워드를 모두 검증하는데 소요되는 시간은 대략 9시간이 필요함

: CPU(I7 3770K 3.5 GHz 기준)

: 하나의 패스워드를 검증하는데 소요되는 시간 = 약 0.0000044초 

: 전체 소요시간 = (95⁵가지) * (0.0000044초) = 34,046초 = 대략 9시간 

 

※ 7자리 패스워드를 모두 검증하는데 소요되는 시간은 대략 85,352시간이 필요함

: 전체 소요시간 = (95⁷가지) * (0.0000044초) = 307,768,410초 = 대략 85,352시간 

 

 

 

문제 A. 정확히 7자리인 패스워드를 입력하면 블록암호 키를 생성해주는 툴(PBKDF2.exe)을 이용하여 [표 2]의 (단계 2)를 알아내고, 그 과정을 설명하시오. (패스워드 문자세트는 [표 3] 참조, PBKDF2.exe은 [표 2]의 단계 1 ~ 단계 5를 수행함)

 

문제 B. 블록암호 키 "b9fcea0c9b252f9bfe04682d752c843a"에 대응하는 [표 3]의 문자세트로 이루어진 7자리 패스워드와 동치 패스워드를 하나 찾으시오. (블록암호 키는 [표 2]의 단계 5에서 얻어진 결과이며, 5자리 문자열(0 ~ 255)을 입력받아 해당 블록암호 키에 대응하는 패스워드를 찾는 툴(PWsearch.exe)을 이용하시오)

 

2016 국가암호공모전 (Ⅱ-A) 분야 문제 03 문제.pdf

다운로드

Q1.zip

다운로드

Q2.zip

다운로드

 

 

2. 풀이 [목차] 

문제는 굉장히 단순하다. 왜냐하면 [표 2]의 3번 문자열이 같으면 생성 암호가 같아서다. 그런데 [표 2]의 3번 문자열을 생성하는 방법이 주어져 있다. 따라서 10개의 이항연산과 P6, P7이 상호작용하는 위치에 따라 경우를 총 50 × 50 가지만 고려하면 된다. 그런데 P6와 P7이 독립적이므로 각각 50가지씩 고려한다. (단, 50이란 수는 이항연산의 종류 10과 상호작용 위치의 개수 5를 곱한 값이다.)

 

About P6.

우선 '+'일 것이라 가정하고, 다음 케이스를 조사한다.

 

0000010, 1000000, 0100000, 0010000, 0001000, 0000100

 

그 뒤 MasterKey를 조사하자 1번과 5번만 같았다. 그래서 P6와 P4가 상호작용한다고 결론지을 수 있다. 그런데 상호작용의 종류가 반드시 '+'일 것이라고는 장담할 수 없다. 따라서 다음을 조사해 본다.

 

0000000, 0000010, 0001000, 0001010

 

그 뒤 MasterKey를 조사하자 2번, 3번, 4번만 같았다. 따라서 상호작용의 종류는 '|'이다.

 

 

About P7. 

우선 '+'일 것이라 가정하고, 다음 케이스를 조사한다.

 

0000001, 1000000, 0100000, 0010000, 0001000, 0000100

 

그 뒤 MasterKey를 조사하자 1번과 3번만 같았다. 그래서 P7과 P2가 상호작용한다고 결론지을 수 있다. 그런데 상호작용의 종류가 반드시 '+'일 것이라고는 장담할 수 없다. 따라서 다음을 조사해 본다.

 

0000000, 0000001, 0100000, 0100001, 0000002

 

그 뒤 MasterKey를 조사하자 2번과 3번만 같았다. 위 표에 따르면 2번과 3번만 같고, 1번, 4번은 따로 노는 경우는 '+'와 '^', '*' 뿐이다. 그런데 5번이 4번과 다르고(≠ '+'), 1번과 4번이 다르므로(≠ '^') 상호작용은 '*'이다.

 

그런데 경우에 따라 상호작용의 종류 및 위치가 다를 수 있지 않을까. 이에 몇 차례 검증을 해 보았으며, 잠정적으로 그렇지 않다고 결론 내렸다. 우선 가능한 P2, P4의 값의 후보는 첨부된 코드를 통해 구할 수 있다. 그러면 P1 ~ P5 모두 95가지가 된다. 따라서 소요시간은 다음과 같다.

 

 

해 볼만 하다. 실제로 PWsearch.exe를 실행시킨 결과 %당 약 800초가 소요됐다. 35% 완료된 직후 찾아낸 마스터키는 다음과 같았다. (중간에 계산실수가 있어서 계산 과정이 원래와 다소 다를 수 있다.)

 

● 찾아낸 단계2의 문자열(16진수값): 435577656d
● 마스터키: b9fcea0c9b252f9bfe04682d752c843a 

 

따라 5 bytes 문자열은 'CUwem'이다. 그러므로 가령 다음과 같은 7 bytes 문자열이 가능하다:

 

'CWweme3' 

 

입력: 2016.08.14 12:58