게페 결합기 (Geffe Combiner)

게페 결합기(Geffe Combiner)는 1973년 P. R. Geffe가 제안한 스트림 암호용 키스트림 생성기로, 세 개의 선형 피드백 시프트 레지스터(LFSR)의 출력을 비선형 결합 함수로 섞습니다. 두 LFSR은 데이터 비트를 내고, 세 번째 LFSR은 매 순간 그중 어느 비트를 출력할지 고르는 선택기 역할을 합니다. 각 LFSR보다 예측하기 어려운 수열을 만들려는 설계였지만, 상관 공격에 취약한 것으로 밝혀졌습니다.

배경: LFSR과 결합 생성기

선형 피드백 시프트 레지스터(LFSR)는 매우 빠르고 주기가 긴 수열을 만들지만, 출력이 선형 관계를 따르므로 출력 일부만 알면 나머지를 계산할 수 있습니다. 그래서 여러 LFSR의 출력을 비선형 함수로 묶어 선형성을 깨려는 결합 생성기(combination generator)가 고안되었고, 게페 결합기는 그 초기의 대표적인 예입니다. 생성된 키스트림은 평문과 XOR되어 암호문이 됩니다.

작동 원리

세 LFSR의 같은 시점 출력 비트를 x₁, x₂, x₃라고 하면, 게페 결합기의 출력 z는 다음과 같습니다.

z = (x₁ ∧ x₂) ⊕ (¬x₁ ∧ x₃)

즉 선택기 x₁이 1이면 x₂가, 0이면 x₃가 그대로 출력됩니다. 이 함수는 2:1 멀티플렉서와 같습니다. 세 LFSR의 길이를 서로소인 L₁, L₂, L₃로 잡으면 출력 수열의 주기와 선형 복잡도(L₁L₂ + L₁L₃ + L₃)가 커진다는 점이 설계의 장점으로 여겨졌습니다.

약점: 상관관계

선택된 입력 비트가 그대로 출력되므로 출력이 입력과 상관관계를 유지합니다. 선택기 x₁이 x₂를 고르는 절반의 경우에는 z = x₂이고, 나머지 절반에서도 x₃가 우연히 x₂와 같을 확률이 1/2이므로, 출력 z는 x₂와 약 75%의 확률로 일치합니다. 같은 이유로 z는 x₃와도 약 75% 일치합니다. 반면 선택기 x₁과의 일치 확률은 50%입니다.

상관 공격

1985년 T. Siegenthaler가 제시한 상관 공격은 이 상관관계를 이용합니다. 공격자는 알려진 키스트림 일부를 놓고 LFSR 2의 가능한 초기 상태를 하나씩 시험해, 출력과 약 75% 일치하는 상태를 찾습니다. LFSR 3도 같은 방법으로 따로 찾고, 마지막으로 LFSR 1의 상태를 찾습니다. 그 결과 필요한 탐색량은 세 레지스터 상태 공간의 곱(2^{L₁+L₂+L₃} 수준)에서 각 레지스터를 따로 공격하는 합(2^L₁ + 2^L₂ + 2^L₃ 수준)으로 줄어들어, 결합기의 보안은 개별 LFSR을 하나씩 공격하는 수준으로 떨어집니다.

평가와 쓰임

• 단순성: 구조가 간단해 하드웨어로 쉽게 구현할 수 있습니다.
• 교육적 가치: 결합 함수 설계가 잘못되면 여러 생성기를 써도 약점이 남는다는 점, 즉 결합 함수의 상관 면역성(correlation immunity)이 중요하다는 점을 보여 주는 사례로 암호학 교재에서 다뤄집니다.
• 실사용 비권장: 상관 공격에 취약하므로 오늘날에는 안전한 결합기로 보지 않으며, 실제 통신 보안이나 키 생성 용도로는 권장되지 않습니다.