선형 암호 분석

Linear cryptanalysis

암호학에서 선형 암호해석은 암호의 작용에 대한 아핀 근사치를 찾는 것에 기초한 암호해석의 일반적인 형태입니다.블록 암호와 스트림 암호에 대한 공격이 개발되었습니다.선형 암호 분석은 블록 암호에 대해 가장 널리 사용되는 두 가지 공격 중 하나이며, 다른 하나는 차등 암호 분석입니다.

이 발견은 FEAL 암호(Matsui and Yamagishi,[1] 1992년)에 이 기술을 처음 적용한 마쓰이 미쓰루 덕분이다.그 후, 마쓰이는 데이터 암호화 규격(DES)에 대한 공격을 발표하였고, 그 결과 오픈 커뮤니티에서 보고된 암호의 첫 실험적인 암호 분석이 이루어졌습니다(Matsui, 1993; 1994).[2][3]DES에 대한 공격은 일반적으로 실용적이지 않으며, 2개의 알려진 [3]평문이47 필요합니다.

공격에 대해 여러 선형 근사 사용 또는 비선형 표현 포함을 포함하여 다양한 개선 사항이 제안되었으며, 이로 인해 분할 암호 분석이 일반화되었습니다.보통 새로운 암호 설계에서는 선형 암호 해석에 대한 보안 증거가 필요합니다.

개요

선형 암호 분석에는 두 가지 부분이 있습니다.첫 번째는 높은 편향을 갖는 평문, 암호문 및 키 비트와 관련된 선형 방정식을 구성하는 것입니다. 즉, (변수의 모든 가능한 값의 공간에 걸쳐) 보유 확률이 가능한 한 0 또는 1에 가깝습니다.두 번째는 이러한 선형 방정식을 기존의 평문-암호화 쌍과 함께 사용하여 키 비트를 도출하는 것입니다.

선형 방정식 구성 중

선형 암호 해독을 위해 선형 방정식은 배타적 논리합(XOR) 연산과 결합된 이진 변수로 구성된 두 식의 동일성을 나타냅니다.예를 들어, 다음 식은 가상 암호에서 첫 번째와 세 번째 평문 비트의 XOR 합계를 나타내며(블록 암호의 블록과 같이), 첫 번째 암호문 비트는 키의 두 번째 비트와 동일합니다.

이상적인 암호에서는 평문, 암호문 및 키 비트와 관련된 선형 방정식이 1/2 확률로 유지됩니다.선형 암호 해석에서 다루는 방정식은 확률에 따라 다르므로, 더 정확하게 선형 근사라고 합니다.

근사치를 작성하는 순서는 암호마다 다릅니다.가장 기본적인 유형의 블록 암호인 대체-변환 네트워크에서 분석은 주로 암호의 유일한 비선형 부분인 S-박스에 집중된다(즉, S-박스의 연산은 선형 방정식으로 부호화할 수 없다).충분히 작은 S박스의 경우, S박스의 입력 및 출력 비트와 관련된 모든 가능한 선형 방정식을 열거하고, 그 편향을 계산하고, 가장 좋은 것을 선택할 수 있다.S-box의 선형 근사치는 전체 암호에 대한 선형 근사치에 도달하기 위해 순열 및 키 혼합과 같은 암호의 다른 동작과 결합되어야 합니다.누적 보조항목이 이 조합 단계에 유용한 도구입니다.또한 선형 근사치를 반복적으로 개선하는 기법도 있다(Matsui 1994).

키 비트 유도

형태의 선형 근사치를 구했습니다.

그런 다음 알려진 평문-암호 쌍을 사용하여 간단한 알고리즘(Matsui의 알고리즘 2)을 적용하여 근사치와 관련된 키 비트 값을 추측할 수 있다.

우측의 키 비트 값 세트(부분 키)별로 알려진 모든 평문과 암호문 쌍에 대해 근사치가 참인 횟수를 카운트합니다.이 카운트를 T라고 부릅니다.T가 플레인텍스트와 암호문 쌍 수의 절반과 절대적인 차이가 가장 큰 부분 키가 이러한 키비트의 가장 가능성이 높은 값 세트로 지정됩니다.이는 정확한 부분 키가 높은 편중으로 근사치를 유지한다고 가정하기 때문입니다.여기서 치우침의 크기는 확률 자체의 크기와는 대조적으로 중요하다.

이 절차를 다른 선형 근사치를 사용하여 알 수 없는 키비트의 수가 브루트 포스로 공격할 수 있을 정도로 적어질 때까지 키비트의 값을 추측할 수 있습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Matsui, M. & Yamagishi, A. "A new method for known plaintext attack of FEAL cipher". Advances in Cryptology - EUROCRYPT 1992.
  2. ^ Matsui, M. "The first experimental cryptanalysis of the data encryption standard". Advances in Cryptology - CRYPTO 1994.
  3. ^ a b Matsui, M. "Linear cryptanalysis method for DES cipher" (PDF). Advances in Cryptology - EUROCRYPT 1993. Archived from the original (PDF) on 2007-09-26. Retrieved 2007-02-22.

외부 링크