On the security of 2-key triple DES

이 논문은 2019 년 NIST 표준에서 제외되었음에도 여전히 널리 사용되는 2 키 3 회 DES 의 보안성을 재검토하여, 1990 년 이후 처음으로 개선된 공격 기법을 제시하고 기존에 80 비트의 안전성이 있다고 여겨졌던 평가가 더 이상 보수적이지 않으며 키 교체만으로는 안전을 보장할 수 없음을 밝혀, 3 키 버전으로의 긴급한 전환을 촉구합니다.

핵심

1. 배경: 낡은 금고와 새로운 열쇠 (Triple DES란?)

과거 은행이나 신용카드 시스템에서는 데이터를 보호하기 위해 DES라는 암호를 썼습니다. 하지만 이 열쇠 (키) 가 너무 짧아서 해커들이 금방 뚫어버릴 수 있게 되자, 사람들은 "열쇠를 두 번, 세 번 돌려보자"고 생각했습니다.

• 단일 DES: 열쇠를 한 번만 돌림. (이미 뚫림)
• 3-키 3중 DES: 서로 다른 열쇠 3 개를 써서 세 번 잠금. (매우 안전함)
• 2-키 3중 DES: 열쇠 3 개 중 2 개만 써서 (A-B-A 순서로) 세 번 잠금. (가장 많이 쓰였지만, 3 개 버전보다 약함)

지금까지 전문가들은 "2-키 3중 DES 는 80 비트의 안전성을 가진다. 즉, 해커가 뚫으려면 엄청난 시간과 돈이 들 테니 괜찮다"고 믿어왔습니다. 마치 "이 금고는 100 년은 버틸 거야"라고 생각했던 것과 같습니다.

2. 새로운 발견: "여러 개의 금고"를 한 번에 뚫는 법

이 논문은 1990 년에 제안된 해킹 방법 (van Oorschot-Wiener 공격) 을 대폭 업그레이드했습니다. 기존 방법의 문제점은 "해커가 단 하나의 열쇠로 만든 데이터만 모아야 했다"는 것이었습니다. 하지만 현실에서는 은행이 자주 열쇠를 바꾸기 때문에, 같은 열쇠로 만든 데이터가 100 개도 안 나올 수 있어 공격이 불가능하다고 여겨졌습니다.

저자는 이 문제를 해결하는 세 가지 혁신적인 방법을 제시합니다.

① "여러 금고의 열쇠를 한 번에 찾아라" (일반화)

• 비유: 예전에는 해커가 "A 금고의 열쇠"를 찾으려면 A 금고의 열쇠로 잠긴 물건 100 개를 모두 모아야 했습니다. 하지만 저자는 **"A, B, C, D... 여러 금고의 물건들을 섞어서 모아도, 결국 그중 하나라도 열쇠를 찾아내면 된다"**는 사실을 발견했습니다.
• 결과: 은행이 열쇠를 자주 바꿔도 해커는 상관없습니다. 여러 번 바뀐 열쇠로 잠긴 데이터들을 한데 모아 분석하면, 그중 하나라도 뚫릴 확률이 높아집니다.

② "거울 속의 열쇠" (DES 의 보완성)

• 비유: DES 암호에는 신기한 성질이 있습니다. 열쇠를 반대로 뒤집으면 (비트 반전), 암호문도 반대로 뒤집힙니다. 마치 거울에 비친 것처럼요.
• 효과: 해커는 원래 열쇠 하나만 분석하는 게 아니라, 거울에 비친 열쇠까지 동시에 분석할 수 있습니다. 이는 해킹 속도를 2 배로 높여줍니다.

③ "일부만 아는 열쇠" (부분적 평문)

• 비유: 해커가 금고 안의 물건 (평문) 을 100% 다 알 필요는 없습니다. 예를 들어, "PIN 번호만 모르고 나머지는 다 아는" 상황도 가능합니다.
• 효과: 해커는 PIN 번호가 될 수 있는 모든 경우의 수 (0000~9999) 를 대입해 가며 공격합니다. 정보가 조금만 부족해도, 컴퓨터가 그 모든 경우를 빠르게 계산해내기 때문에 공격이 여전히 가능합니다.

3. 결론: "안전하다"는 말은 이제 옛말

이 논문의 핵심 결론은 다음과 같습니다.

1. 80 비트 안전성은 착각입니다: 우리가 믿어왔던 "80 비트의 안전성"은 더 이상 보수적인 추정이 아닙니다. 실제로는 훨씬 더 취약합니다.
2. 열쇠를 자주 바꾸는 것도 해결책이 아닙니다: "열쇠를 자주 바꾸면 해커가 뚫을 수 없다"는 조언은 이제 무의미합니다. 해커는 여러 번 바뀐 열쇠들의 데이터를 섞어서 뚫어내기 때문입니다. 열쇠를 자주 바꾸는 것은 해킹이 성공했을 때 피해를 줄이는 효과만 있을 뿐, 해킹을 막지는 못합니다.
3. 급한 교체 필요: 이 기술은 완전히 망가진 것은 아니지만, 안전 마진 (여유) 이 거의 없습니다. 지금 당장이라도 더 안전한 3-키 3중 DES나 최신 암호인 AES로 교체해야 합니다.

4. 요약: 왜 이 논문이 중요한가?

이 논문은 **"낡은 금고 (2-키 3중 DES) 는 이제 더 이상 안전하지 않다"**는 것을 증명했습니다.

• 과거의 생각: "열쇠를 자주 바꾸면 해커가 뚫을 수 없어. 안심해도 돼."
• 이제의 진실: "해커는 여러 금고의 열쇠를 섞어서 뚫어낼 수 있어. 열쇠를 자주 바꿔도 소용없고, 지금 당장 더 튼튼한 금고 (AES) 로 갈아타야 해."

결국, 이 기술이 여전히 널리 쓰이는 금융 산업 등에서 즉시 대체해야 한다는 강력한 경고가 담긴 논문입니다.

기술 요약

1. 문제 제기 (Problem)

• 배경: 2 키 3 중 DES 는 1990 년대부터 결제 산업 (EMV 등) 에서 표준 알고리즘으로 널리 사용되어 왔습니다. NIST 는 2015 년 이를 폐기했으나, 여전히 많은 시스템에서 사용 중입니다.
• 기존 보안 평가: 업계와 표준 기구 (NIST, ISO/IEC) 는 2 키 3 중 DES 가 80 비트의 보안성을 제공하며, 키를 정기적으로 교체하면 실제 공격이 불가능하다고 평가해 왔습니다.
• 핵심 문제: Chris J. Mitchell 은 이러한 "80 비트 보안성"과 "정기적 키 교체로 인한 안전성"이라는 통념이 더 이상 타당하지 않음을 주장합니다. 기존 공격 기법의 한계를 극복하고, 다양한 시나리오 (다중 키 사용, 부분적 평문 노출 등) 에서 공격이 가능함을 보여줌으로써 안전 마진이 매우 좁아졌음을 지적합니다.

2. 방법론 (Methodology)

저자는 1990 년 van Oorschot 와 Wiener 가 제안한 2 키 3 중 DES 에 대한 기존 공격 기법을 **일반화 (Generalization)**하고 **최적화 (Optimization)**하여 공격 효율성을 극대화했습니다.

A. van Oorschot-Wiener 공격의 일반화 (Section 3)

• 기존 공격: 단일 키로 생성된 $n$개의 (평문, 암호문) 쌍을 필요로 함. 공격자는 $A = E_{K1}(P)$가 성립하는 $A$를 가정하고 $K2$를 브루트포스하며, 성공 확률은 $n/2^{64}$임.
• 개선점: 공격에 사용되는 (평문, 암호문) 쌍이 서로 다른 키로 생성되더라도 공격이 유효함을 증명.
  • 각 키 세트를 라벨 ($s$) 로 구분하여 테이블에 저장.
  • 공격 성공 시 해당 라벨에 해당하는 키만 복원되지만, 이는 다수의 키가 사용되는 환경 (예: 결제 시스템) 에서 치명적인 결과를 초래함.
  • 결과: 키를 정기적으로 교체하는 것은 공격 성공 확률을 낮추지 않으며, 단지 공격 성공 시 피해 범위를 제한할 뿐임.

B. DES 보완성 (Complementation Property) 활용 (Section 4)

• 원리: DES 의 보완성 속성 ($E_K(P) = \overline{E_{\overline{K}}(\overline{P})}$) 을 활용.
• 개선: 하나의 평문/암호문 쌍을 사용하여 동시에 $K$와 $\overline{K}$에 대한 공격을 수행 가능.
• 효과: 공격 속도가 2 배 향상됨 (계산 복잡도에서 $2^{121-t}$에서$2^{120-t}$로 감소).

C. 부분적으로 알려진 평문 활용 (Section 5)

• 시나리오: 결제 시스템의 PIN 블록 (ISO 9564-1) 처럼, 암호문은 알지만 평문의 일부 비트 (예: PIN 4 자리) 만 모르는 경우.
• 개선: 알려진 비트를 고정하고, 미지수 비트에 대한 모든 가능한 조합 ($2^w$개) 을 생성하여 가상의 (평문, 암호문) 쌍을 대량으로 생성.
• 효과: 이러한 "거짓" 쌍을 포함하여 공격 테이블을 확장하더라도, 검증 단계에서 올바른 키만 살아남으므로 공격 복잡도는 크게 증가하지 않음.
  • $n=2^{32}$개의 부분적 평문 쌍이 있으면, 완전한 평문 32 비트 쌍과 유사한 수준의 공격 효율 ($2^{89}$ 연산) 을 달성 가능.

3. 주요 기여 (Key Contributions)

1. 최초의 진전 (1990 년 이후): 25 년간 2 키 3 중 DES 에 대한 주요 암호 분석 진전이 없었으나, 본 논문은 van Oorschot-Wiener 공격을 일반화하여 첫 번째 진전을 이루었습니다.
2. 다중 키 환경 공격 가능성 증명: 키를 자주 교체해도 공격이 무력화되지 않음을 수학적으로 증명하여, "정기적 키 교체"라는 보안 권고의 유효성을 도전했습니다.
3. 실제 적용 시나리오 확장:
   • DES 보완성 활용: 공격 효율을 2 배로 증대.
   • 부분 평문 공격: PIN 블록 등 실제 금융 데이터에서 흔히 발생하는 부분적 정보 노출 상황에서도 공격이 가능함을 보임.
4. ANSI Retail MAC 공격: 해당 공격 기법이 ANSI Retail MAC (CBC-MAC-Y) 에도 적용 가능함을 보여주었으며, 이는 MAC 키 복구 공격의 새로운 위협이 됨.

4. 결과 (Results)

• 계산 복잡도: $n = 2^t$개의 (평문, 암호문) 쌍이 주어졌을 때, 2 키 3 중 DES 를 깨는 데 필요한 계산량은 다음과 같습니다.
  • 기존 van Oorschot-Wiener: $2^{121-t}$
  • 보완성 + 일반화 적용 시: $2^{120-t}$
  • 예시: $n=2^{32}$ (약 40 억 개) 의 데이터가 있다면, 공격 복잡도는 $2^{88}$ DES 연산으로 감소합니다. 이는 과거의 80 비트 보안성 평가보다 훨씬 취약한 수준입니다.
• 저장 공간: $O(2^t)$ 또는 $O(2^{t+w})$ (부분 평문 사용 시) 로, 현대적인 하드웨어로 처리 가능한 수준입니다.
• ANSI MAC: 메시지/MAC 쌍이 다중 키로 생성된 경우에도 공격이 가능하여, 기존 Preneel-van Oorschot 공격보다 더 넓은 적용 범위를 가짐.

5. 의의 및 결론 (Significance & Conclusion)

• 보안 마진의 붕괴: 2 키 3 중 DES 가 제공하는 80 비트 보안성은 "보수적인 (conservative)" 추정이 아니라, 실제 공격 환경에서는 안전 마진이 거의 없는 (slim margin) 상태임을 시사합니다.
• 권고 사항의 무효화: "키를 정기적으로 교체하라"는 조언은 공격 성공 확률을 낮추지 못하므로, 공격의 위험을 근본적으로 해결하지 못합니다.
• 대응 방안:
  • 2 키 3 중 DES 는 즉시 3 키 3 중 DES 또는 AES로 대체되어야 합니다.
  • 특히 AES 는 256 비트 키를 지원하여 양자 컴퓨팅 공격에 대한 대비도 가능하게 합니다.
  • ANSI Retail MAC 의 DES 사용도 위험에 처해 있으므로 재검토가 필요합니다.

요약: 본 논문은 2 키 3 중 DES 가 과거의 평가보다 훨씬 취약하며, 다중 키 환경과 부분적 정보 노출 상황에서도 효율적으로 공격받을 수 있음을 증명함으로써, 해당 알고리즘의 즉각적인 폐기와 현대적 알고리즘 (AES 등) 으로 전환의 시급성을 강조합니다.