Output Feedback Mode (OFB)

1. 핵심 아이디어:

Keystream Generator필기 최상단에 "idea: use the block cipher as a keystream generator"라고 적혀 있습니다. 이것이 OFB 모드의 정체성입니다.

• 이전 모드(ECB, CBC): 평문($x_i$)이 직접 AES 같은 암호화 모듈($e$) 안으로 들어갔습니다.
• OFB 모드: 평문($x_i$)은 암호화 모듈에 들어가지 않습니다. 대신, 암호화 모듈($e$)은 키($K$)와 초기화 벡터($IV$)를 사용해 무작위해 보이는 비트열(Keystream, $s_i$)을 끊임없이 만들어내는 난수 발생기 역할만 합니다.
• 암호화/복호화:
  
  이렇게 만들어진 키 스트림($s_i$)을 평문($x_i$)과 단순히 XOR($\oplus$) 연산하여 암호문($y_i$)을 만듭니다. 복호화할 때도 똑같은 키 스트림을 만들어 암호문에 다시 XOR 연산하면 원래 평문이 튀어나옵니다.

2. 동작 구조 (피드백 루프)

다이어그램을 보면 'Output Feedback'이라는 이름이 왜 붙었는지 알 수 있습니다.

• 초기 상태 ($i=1$): 첫 번째 키 스트림 $s_1$은 초기화 벡터 $IV$를 암호화($e$)하여 만듭니다.$s_1 = e_K(IV)$

• 피드백 ($i \ge 2$): 두 번째부터는 방금 전 출력된 결과값($s_{i-1}$)을 다시 입력으로 집어넣어(Feedback) 다음 결과값($s_i$)을 만듭니다.$s_i = e_K(s_{i-1})$

3. 필기 하단의 핵심 질문 분석

교수님께서 던지신 두 가지 질문은 OFB 모드의 본질을 꿰뚫는 아주 좋은 시험 문제 후보입니다.

① Why NOT $e^{-1}$?

(왜 복호화할 때 역함수 $e^{-1}$를 쓰지 않는가?)필기의 오른쪽 복호화(Decryption) 다이어그램을 보면, 암호화 모듈의 기호가 $e^{-1}$(복호화)가 아니라 빨간색 밑줄이 쳐진 $e$(암호화) 그대로인 것을 볼 수 있습니다.

• 이유: 수신자의 목적은 '암호문 $y_i$를 암호화 모듈에 넣어 푸는 것'이 아닙니다.
• 송신자가 평문과 섞었던 그 '키 스트림($s_i$)'을 똑같이 재현해 내는 것이 목적입니다.송신자가 키 스트림을 만들 때 $e$를 썼으므로, 수신자도 똑같이 $e$를 써야 동일한 난수열($s_1, s_2, \dots$)이 만들어집니다. 그렇게 만든 $s_i$를 받은 암호문 $y_i$와 XOR만 하면 원래 평문이 나옵니다 ($y_i \oplus s_i = x_i \oplus s_i \oplus s_i = x_i$).
• 하드웨어적 장점: 이것은 엄청난 장점입니다! AES 복호화 코어(Decryption logic)를 아예 하드웨어로 구현할 필요가 없습니다. 암호화 모듈 하나만 올려두면 암호화와 복호화를 모두 수행할 수 있어 칩 면적(Area)을 크게 절약할 수 있습니다.

② $s_i$ Repeated?

(키 스트림 $s_i$는 반복되는가?)
출력값이 다시 입력으로 들어가는 유한한 크기(예: AES는 128비트)의 시스템이므로, 언젠가는 이전에 나왔던 값이 다시 나올 수밖에 없습니다.

• 위험성: 만약 스트림 암호에서 키 스트림($s_i$)의 패턴이 반복된다면, 이는 보안상 심각한 재앙(Two-time pad attack)입니다. 공격자가 패턴을 유추해 암호를 깰 수 있습니다.
• 실제 상황: 다행히 128비트 블록 암호를 사용할 경우, 수학적으로 이 사이클이 반복되기까지 걸리는 주기(Period)는 평균적으로 $2^{64}$ 블록 정도로 천문학적으로 깁니다. 따라서 한 번의 통신 세션에서 키 스트림이 반복될 확률은 사실상 0에 가깝습니다. 단, 메시지를 보낼 때마다 무조건 새로운 IV를 사용해야 한다는 전제 조건이 붙습니다.

Double Encryption(2DES)

이중 암호화

1. 도입 배경 (Motivation)

문제점: 과거의 표준이었던 DES 암호 알고리즘은 키(Key)의 길이가 56-bit로 너무 짧았습니다. 필기 상단에 $2^{56}$이라고 적혀 있듯이 무차별 대입(Brute-force)을 하기에 경우의 수가 너무 적었습니다. 필기 우측 하단에 안전성의 최소 기준선처럼 적혀 있는 $2^{80}$에 비하면 턱없이 부족하여, 컴퓨터 성능 발달로 인해 뚫릴 위험이 컸습니다.

2. 이중 암호화의 아이디어 (Double Encrypt)

• 해결책의 착각: 사람들은 아주 단순한 아이디어를 냈습니다. 암호화 모듈($e$)을 두 번 이어 붙여서, 왼쪽 키($K_L$, 56-bit)로 한 번 암호화하고, 오른쪽 키($K_R$, 56-bit)로 한 번 더 암호화하자는 것이었습니다.
• 기대 효과: 이렇게 하면 키 공간(Key space)의 크기가 $|K_L| \cdot |K_R|$이 되어, $2^{56} \cdot 2^{56} = 2^{112}$ 비트 수준의 보안성을 가질 것이라 예상했습니다. $2^{112}$는 $2^{80}$보다 훨씬 크기($\gg$) 때문에 무차별 대입 공격(Brute-force Attack)의 복잡도를 완벽하게 방어할 수 있을 것이라고 생각한 것이죠.

3. 치명적인 약점 발견

(Can we find a better attack?)교수님께서 가운데 그려두신 빨간색 점선과 핑크색 화살표(Left $\rightarrow$, $\leftarrow$ Right)가 바로 이 착각을 부수는 '중간자 공격'의 핵심 원리입니다.해커가 어떤 평문($x_i$)과 그에 해당하는 최종 암호문($y_i$) 한 쌍을 알고 있다고 가정해 봅시다

• 왼쪽에서 접근 (search for $K_L$): 핑크색 화살표처럼, 해커는 평문 $x_i$를 $2^{56}$개의 모든 가능한 $K_L$을 이용해 한 번씩 암호화해 본 뒤, 그 결과들을 메모리(표)에 싹 다 저장합니다. (이때 연산량은 $2^{56}$ 입니다.)
• 오른쪽에서 접근 (search for $K_R$): 반대편 핑크색 화살표처럼, 최종 암호문 $y_i$를 $2^{56}$개의 모든 가능한 $K_R$을 이용해 이번에는 역방향으로 복호화해 봅니다.
• 중간에서 만나기: 오른쪽에서 복호화하며 나온 값이, 아까 왼쪽에서 암호화해 저장해둔 표의 값과 중간(빨간색 점선)에서 일치하는지 찾습니다. 일치하는 순간의 $K_L$과 $K_R$ 쌍이 바로 정답 키가 됩니다!

4. 최종 결론

이 공격법을 사용하면 두 키를 동시에 찾는 것(곱하기)이 아니라, 각각 따로따로(separately) 찾아서 합치게 됩니다.

• 필기 하단의 수식처럼 전체 복잡도는 $2^{56} \text{ (왼쪽 탐색)} + 2^{56} \text{ (오른쪽 탐색)} = 2 \cdot 2^{56} = 2^{57}$ 이 됩니다.
• 결국 이중 암호화는 연산을 두 번이나 수행하게 만들었음에도, 전체 보안성은 고작 1비트($2^{56} \rightarrow 2^{57}$) 증가하는 데 그쳤습니다. 필기 마지막에 노란색 형광펜 쳐진 것처럼 $2^{57}$은 여전히 안전 기준선인 $2^{80}$보다 한참 작아서($\ll$) 실효성이 없다는 뼈아픈 결론이 나옵니다.

Meet in the Middle Attack

해커(Man)가 평문 $x_1$과 그에 대응하는 최종 암호문 $y_1$ 한 쌍을 몰래 확보했다고 가정했을 때, 공격은 다음과 같이 진행됩니다.

Phase I:

왼쪽 탐색 및 중간값 저장 (Left Side)이 단계는 무식하게 모든 경우의 수를 다 해보면서 거대한 '컨닝 페이퍼(표)'를 만드는 과정입니다.

1. 암호화 연산: 해커는 알고 있는 평문 $x_1$을 $2^{56}$개의 모든 가능한 왼쪽 키 $K_{L,i}$ ($i$는 $0$부터 $2^{56}-1$까지)를 이용해 암호화 모듈($e$)에 통과시킵니다.
   $e_{K_{L,i}}(x_1) = Z_{L,i}$

2. 저장 (Store): 이때 암호화되어 나온 결과들, 즉 중간값(intermediate value)인 $Z_{L,i}$를 사용했던 키 $K_{L,i}$와 짝지어서 메모리에 전부 저장합니다. 필기 상단 가운데에 그려진 빨간색 표가 바로 이것입니다.

3. 복잡도 (Complexity): 이 단계를 수행하기 위해서는 $2^{56}$번의 암호화 연산(encryptions) 시간과, 그 결과들을 담아둘 $2^{56}$개의 엄청난 저장 공간(storage locations)이 필요합니다.

Phase II:

오른쪽 탐색 및 충돌 확인 (Right Side)표가 완성되었으니, 이제 반대쪽 끝에서 거꾸로 추적해 들어옵니다.

1. 복호화 연산: 이번에는 최종 암호문 $y_1$을 $2^{56}$개의 모든 가능한 오른쪽 키 $K_{R,j}$를 사용하여 역으로 복호화($e^{-1}$)합니다.

$Z_{R,j} = e^{-1}_{K_{R,j}}(y_1)$

2. 충돌/매칭 확인 (Check for matching/collision): $Z_{R,j}$를 하나 계산할 때마다, 앞서 Phase I에서 만들어둔 거대한 표를 뒤져서 방금 계산한 값과 똑같은 값($Z_{L,i} \stackrel{?}{=} Z_{R,j}$)이 존재하는지 확인합니다.

3. 정답 도출: 만약 표에서 일치하는 값을 찾았다면! 그때 표에 적혀있던 $K_{L,i}$와 방금 사용한 $K_{R,j}$가 바로 이중 암호화 시스템에 사용된 실제 마스터 키 쌍이 됩니다.

이 공격의 핵심은 "시간-메모리 교환(Time-Memory Trade-off)"입니다.원래대로라면 $2^{112}$번을 계산해야 할 엄청난 시간을, $2^{56}$ 크기의 거대한 메모리(표)를 희생하는 대가로 연산 시간을 $2^{57}$ ($2^{56} + 2^{56}$) 수준으로 극단적으로 줄여버린 것입니다.결과적으로 2DES(이중 암호화)는 해커에게 메모리만 충분하다면 보안성이 DES 1번 쓰는 것과 크게 다를 바 없다는 것이 완벽히 증명되었고, 이 때문에 암호화 표준에서 철저히 버려지게 되었습니다.

1. 충돌(Collision) 발견의 의미와 수학적 증명

표에서 $Z_{L,i}$와 $Z_{R,j}$가 일치하는 구간을 찾았다면, 이는 수식으로 다음과 같이 표현됩니다.
$e_{K_{L,i}}(x_1) = e^{-1}_{K_{R,j}}(y_1)$
이 수식을 $x_1$에 대해 정리하면(양변을 $e^{-1}{K{L,i}}$로 복호화하면) 아래와 같이 됩니다.
$x_1 = e^{-1}_{K_{L,i}}[e^{-1}_{K_{R,j}}(y_1)]$
즉, 이 충돌을 일으킨 키 쌍 $(K_{L,i}, K_{R,j})$는 $y_1$을 $x_1$으로 완벽하게 되돌려 놓을 수 있는 '가능성 있는 정답 후보(possible Keys)'가 됩니다. (필기에서 'possible'에 밑줄이 쳐진 이유가 있습니다. 아직 100% 확정은 아니기 때문입니다).

2. 교차 검증:

두 번째 쌍 $(x_2, y_2)$의 필요성필기 중간의 "Note" 부분은 해커가 겪을 수 있는 거짓 양성(False Positive) 문제를 해결하는 방법입니다.

• 문제: 단 하나의 평문-암호문 쌍 $(x_1, y_1)$만 가지고 비교하면, 우연의 일치로 중간값이 같아지는 '가짜 정답 키'가 여러 개 튀어나올 수 있습니다.
• 해결: 이를 걸러내기 위해, 해커는 사전에 확보해 둔 두 번째 평문-암호문 쌍 $(x_2, y_2)$를 꺼내어 방금 찾은 후보 키를 대입해 봅니다.
  $x_2 \stackrel{?}{=} e^{-1}_{K_{L,i}}[e^{-1}_{K_{R,j}}(y_2)]$
  이 두 번째 테스트까지 통과한다면, 우연일 확률이 사실상 0이 되므로 해당 키 쌍이 100% 진짜 마스터 키임을 확신할 수 있습니다.

3. 전체 공격 비용 (Total Complexity) 결산

해커가 이 공격을 수행하기 위해 들인 총비용을 더해봅니다.

• Phase I (왼쪽): $2^{56}$번의 암호화 연산 + $2^{56}$개의 저장 공간(메모리)
• Phase II (오른쪽): 최대 $2^{56}$번의 복호화/암호화 연산
• 총 연산량 (Total): $2^{56} + 2^{56} = 2 \cdot 2^{56} = 2^{57}$ 번의 연산

4. 최종 결론 (The Final Verdict)
   필기 맨 아래, 빨간색 X 표시와 함께 가장 중요한 결론이 적혀 있습니다.

• 이중 암호화(2DES)는 키를 두 번이나 쓰면서 시스템 복잡도를 크게 높였지만, 중간자 공격을 받으면 해킹 연산량이 $2^{112}$가 아닌 고작 $2^{57}$로 뚝 떨어집니다.
• 이 $2^{57}$이라는 숫자는 암호학적으로 안전하다고 여겨지는 최소 마지노선인 $2^{80}$보다 한참 작습니다 ($\ll 2^{80}$).
• 결과적으로 "이중 암호화는 단일 DES보다 아주 약간(marginally) 더 나을 뿐이다"라며 완전히 낙제점을 받게 됩니다.

결국 하드웨어 설계자나 보안 엔지니어 입장에서 2DES는 전력 소모와 칩 면적은 2배로 잡아먹으면서 보안성은 거의 올려주지 못하는 최악의 가성비 알고리즘이었던 것이죠.

Triple Encryption (3DES)

앞서 완벽하게 실패했던 이중 암호화(2DES)의 대안으로 등장한 "삼중 암호화(Triple Encryption, 3DES)"의 보안성을 분석한 내용입니다. 중간자 공격(Meet-in-the-Middle Attack)을 적용했을 때 3DES가 어떻게 살아남는지 아주 잘 보여주고 있습니다.

1. 나이브한 착각 (Naive Expectation)

• 필기 우측 상단을 보면 파란색 글씨로 "Naive = $2^{56} \cdot 2^{56} \cdot 2^{56} = 2^{168}$"이라고 적혀 있고 옆에 노란색 X 표시가 있습니다.
• 사람들은 처음에 56비트 키를 가진 암호화 모듈 3개($K_1, K_2, K_3$)를 연달아 이어 붙이면, 보안성이 $56 + 56 + 56 = 168$비트가 될 것이라고 단순하게(Naive) 생각했습니다.
• 하지만 앞서 2DES를 박살 냈던 중간자 공격을 적용하면 이 예상은 빗나가게 됩니다.

2. 중간자 공격 적용:

어디서 자를 것인가? (다이어그램 분석)필기의 다이어그램에는 암호화 블록($e$) 3개가 직렬로 연결되어 있습니다. 해커가 중간자 공격을 하려면 이 파이프라인을 두 동강 내어 왼쪽과 오른쪽에서 접근해야 하는데, 자를 수 있는 위치가 두 군데 있습니다.

① 파란색 전략 (1번째 블록 / 2, 3번째 블록 사이에서 만나기)

연두색 점선(첫 번째 블록 뒤)을 기준으로 삼는 방법입니다.

• Phase I (왼쪽): $K_1$ 하나만 찾으면 되므로, $2^{56}$번의 연산과 결과를 저장할 $2^{56}$ 크기의 메모리가 필요합니다.
• Phase II (오른쪽): $K_2$와 $K_3$를 동시에 추측하며 역추적해야 하므로, $2^{56} \cdot 2^{56} = 2^{112}$번의 복호화/암호화 연산이 필요합니다.
• 총 연산량 (파란색 수식): $O(2^{56} + 2^{112}) \approx 2^{112}$ 번의 연산이 소요됩니다. (큰 수의 세계에서 $2^{56}$은 $2^{112}$에 비해 먼지 같은 수준이므로 무시됩니다.)

② 빨간색 전략 (1, 2번째 블록 / 3번째 블록 사이에서 만나기)

분홍색 굵은 선(두 번째 블록 뒤)을 기준으로 삼는 방법입니다.

• Phase I (왼쪽): $K_1, K_2$를 조립하며 전진하므로 $2^{56} \cdot 2^{56} = 2^{112}$번의 연산과, 그 엄청난 결과값을 다 담아둘 $2^{112}$ 크기의 메모리(Storage)가 필요합니다.
• Phase II (오른쪽): $K_3$ 하나만 역추적하므로 $2^{56}$번의 연산이 듭니다.
• 총비용 (빨간색 수식): 연산량은 $2^{56} + 2^{112}$로 파란색 전략과 비슷하지만, 요구되는 메모리 공간이 $2^{112}$로 기하급수적으로 커서 현실적으로 실행이 불가능합니다.

3. 최종 결론 (The Verdict on 3DES)

해커 입장에서는 당연히 메모리 소모가 적은 '파란색 전략'을 택하게 됩니다. 이를 바탕으로 도출된 최종 결론이 필기 맨 아래에 적혀 있습니다.

• 3개의 키를 썼으니 168비트의 방어력을 기대했지만, 중간자 공격을 받으면 해커는 $2^{112}$번의 연산만으로 암호를 뚫을 수 있습니다.
• 하지만 2DES 때와는 결론이 다릅니다. 이 $2^{112}$라는 숫자는 안전 기준선인 $2^{80}$보다 훨씬 크기($\ggg$) 때문에, 현대의 컴퓨터로도 뚫는 것이 사실상 불가능합니다.
• 따라서 "3DES는 안전하다(secure)." 그리고 3DES의 "실질적인 키 길이(effective key length)는 168비트가 아니라 112비트이다."라는 암호학계의 중요한 결론이 나옵니다.

결과적으로 2DES는 처참히 실패했지만, 한 번 더 꼬아 만든 3DES는 중간자 공격의 효율을 반감시키며 AES가 등장하기 전까지 훌륭한 금융권/산업계 표준 암호로 활약할 수 있었습니다.이로써 블록 암호의 알고리즘 발전사(DES $\rightarrow$ 2DES $\rightarrow$ 3DES)가 완벽하게 마무리되었네요!

1. 3DES의 실제 동작: EDE 구조와 호환성

필기 최상단의 다이어그램을 보면, 3DES는 단순히 암호화($e$)를 세 번 반복하는 것이 아님을 알 수 있습니다. 암호화($e$) $\rightarrow$ 복호화($e^{-1}$) $\rightarrow$ 암호화($e$) 순서로 동작합니다. 이를 EDE (Encrypt-Decrypt-Encrypt) 구조라고 부릅니다.

• Scenario 1 ($K_1 = K_2$): 만약 첫 번째 키와 두 번째 키를 똑같은 값으로 설정하면 어떻게 될까요? 첫 번째 단계에서 암호화한 것을 두 번째 단계에서 같은 키로 복호화해 버리니 완전히 상쇄(Cancel out)되어 원래 데이터로 돌아옵니다. 결국 세 번째 단계($K_3$) 한 번만 암호화한 것과 동일해집니다. 즉, 3DES 하드웨어 하나만 만들어두면, 키 세팅에 따라 과거의 Single DES 시스템과 100% 하위 호환(Backward Compatibility)이 가능해지는 엄청난 장점이 있습니다.

• Scenario 2 ($K_1 = K_3$): 3개의 키를 전부 다르게 쓰지 않고, 1번과 3번 키를 똑같이 설정하여 2개의 키만 사용해도(112-bit) 여전히 3DES의 보안성을 유지하기에 충분하다(enough)는 의미입니다.

2. 왜 3DES에서 멈출까? (Diminishing Returns)

필기 중간을 보면 4DES, 5DES부터 심지어 1M(백만) DES까지 적어두고 전부 초록색 체크와 빨간색 X 표시를 그어두셨습니다. 이것은 엔지니어링의 '가성비(Trade-off)'를 찌르는 핵심입니다.

• 앞선 분석에서 3DES는 중간자 공격을 받아도 $2^{112}$의 방어력을 가짐을 확인했습니다.
• 이 $2^{112}$라는 숫자는 이미 지구상의 모든 컴퓨터를 동원해도 우주의 나이만큼 걸리는, 현실적으로 "충분히 훌륭한(good enough)" 절대 방어선입니다.
• 따라서 더 안전하게 만들겠다고 암호화 블록을 4개, 5개, 100만 개 이어 붙여봤자 방어력은 무의미하게 과잉될 뿐, 데이터 처리 시간(Latency)과 하드웨어 전력 소모만 기하급수적으로 늘어납니다.
• 결론적으로 3DES가 보안성과 연산 효율성이 교차하는 완벽한 마지노선이었기 때문에 그 이상은 만들지 않았던 것입니다.

3. "왜 거짓 양성(False Positive)이 발생하는가?"

필기 맨 아래 노란 형광펜으로 칠해진 질문("Q = why false positive results?")은 이전 시간에 배웠던 "왜 해커가 키를 교차 검증하기 위해 두 번째 평문-암호문 쌍 $(x_2, y_2)$를 확인해야 하는가?"에 대한 근본적인 이유입니다.

• 이유: 중간자 공격을 할 때, 우리가 암호화하는 데이터 블록(평문)의 크기는 겨우 64비트(경우의 수 $2^{64}$)입니다. 반면 우리가 때려 맞춰야 하는 해킹 키의 경우의 수는 112비트($2^{112}$)로 압도적으로 많습니다.
• 비둘기집 원리: 좁은 64비트 공간에 $2^{112}$개의 결과물을 욱여넣다 보면, 해커가 입력한 가짜 키(Wrong Key) 쌍이 우연의 일치로 우리가 훔친 암호문 $y_1$을 완벽하게 만들어내는 경우(Collision)가 수학적으로 어마어마하게 많이 발생합니다. 이게 바로 거짓 양성(False Positive)입니다.
• 그래서 해커는 중간값이 일치했다고 바로 기뻐하면 안 되고, 반드시 다른 데이터 쌍을 가져와서 "이게 진짜 마스터 키가 맞나?" 하고 한 번 더 테스트해야만 진짜 정답을 걸러낼 수 있습니다.

1. 다트 게임 비유: 핵심 변수 설정

• 다트 판 (Plaintext 및 Ciphertext 공간): 데이터 블록의 크기입니다. 이 예시에서는 크기를 $2^{64}$로 가정합니다. 다트 판 위에 $2^{64}$개의 과녁(점)이 있다고 상상하시면 됩니다.
• 다트의 개수 (Key 공간): 우리가 던질 수 있는 열쇠(Key)의 총개수입니다. 이 예시에서는 총 $2^{80}$개의 다트를 가지고 있다고 가정합니다.
• 목표: 특정 평문 $x_1$을 특정 암호문 $y_1$으로 변환하는 것입니다. 즉, 다트를 던져서 정확히 $y_1$이라는 위치에 명중시키는 게임입니다.

2. Phase I: 거짓 양성(False Positive)의 발생

• 플레이어가 $2^{80}$개의 다트를 모두 던집니다. 다트 판의 공간인 $2^{64}$보다 다트의 개수인 $2^{80}$이 압도적으로 많습니다.
• 다트가 모든 위치에 골고루 꽂힌다고 가정하면, $y_1$이라는 특정 위치 하나에 꽂히는 다트의 개수는 평균적으로 $2^{80} / 2^{64} = 2^{16}$개가 됩니다.
• 즉, $x_1$을 $y_1$으로 만들어내는 열쇠(Key)가 무려 $2^{16}$개나 발견된다는 뜻입니다.
• 하지만 이 중에서 진짜 마스터 키(Real Key)는 단 1개뿐이며, 나머지 $2^{16} - 1$개의 키는 우연히 결과만 같게 나온 거짓 양성(False Positive) 키입니다.

3. Phase II: 교차 검증 (두 번째 쌍의 필요성)

• 이제 손에 남은 $2^{16}$개의 후보 키 중에서 어떤 것이 진짜인지 찾아내야 합니다.
• 이를 위해 두 번째 평문과 암호문 쌍($x_2$, $y_2$)을 가져옵니다. 새로운 목표물 $y_2$가 생긴 것입니다.
• 방금 찾은 $2^{16}$개의 후보 다트만 가지고 다시 $y_2$를 향해 던집니다.
• 진짜 마스터 키라면 당연히 $x_2$를 $y_2$로 완벽하게 변환(명중)시킬 것입니다.
• 반면, 가짜 키가 우연히 또 $y_2$에 명중할 확률은 $2^{16}$ (남은 다트 수) / $2^{64}$ (전체 과녁 수) = $2^{-48}$이 됩니다. 이는 사실상 0에 가까운 확률입니다.
• 결론적으로 두 번째 쌍($x_2$, $y_2$)까지 만족하는 키를 찾았다면, 그것이 100% 진짜 마스터 키임을 확신할 수 있습니다.

Meet-in-the-Middle 공격과 거짓 양성 공식

• 이전 시간에 배운 '다트 게임' 비유를 수학적 공식으로 일반화한 내용입니다.

• 공식: T개의 평문-암호문 쌍(Pairs)이 주어졌을 때, 거짓 양성 키(False Positive Key)가 검증을 통과할 확률 내지 개수는 2^(M - TN) 으로 계산됩니다. (M: 유효 키 길이, N: 블록 크기, T: 쌍의 개수)

• 3DES 예시: 3DES는 유효 키 길이 M = 112 이고, 블록 크기 N = 64 입니다. 두 번째 쌍(T = 2)까지 사용하여 검증한다면, 확률은 2^(112 - (2 * 64)) = 2^(-16) 이 되어 가짜 키를 효과적으로 걸러낼 수 있습니다.