상관 공격

이 글의 어조나 문체는 위키백과에서 사용되는 백과사전적 어조를 반영하지 못할 수도 있다. 제안사항은 위키피디아의 더 나은 기사 작성 안내서를 참조하십시오. (2008년 10월) (이 템플리트 메시지를 제거하는 방법과 시기 알아보기)

암호학에서 상관 공격은 부울 함수를 사용하여 여러 선형 피드백 시프트 레지스터(이 글의 나머지 부분에 대해 LFSR이라고 함)의 출력을 결합하여 키스트림이 생성되는 스트림 암호를 해독하기 위한 알려진 일반 텍스트 공격의 한 종류다. 상관 공격은 부울 함수의 빈약한 선택에서 발생하는 통계적 약점을 이용한다 – 상관 공격을 피하는 함수를 선택할 수 있기 때문에 이러한 유형의 암호는 본질적으로 불안정하지 않다. 이러한 유형의 스트림 암호를 설계할 때 상관 관계 공격에 대한 민감성을 고려하는 것이 필수적이다.^{[citation needed]}

설명

상관 공격은 키스트림 발생기에 있는 하나의 개별 LFSR의 출력 상태와 모든 LFSR의 출력 상태를 결합한 부울 함수의 출력 사이에 유의미한 상관관계가 있을 때 가능하다. 키스트림에 대한 부분적 지식(둘이 함께 XORED되어 있기 때문에 일반 텍스트에 대한 부분적 지식에서 쉽게 파생됨)과 결합되어 공격자는 개별 LFSR과 시스템의 나머지 부분에 대해 키를 개별적으로 분쇄할 수 있다. 예를 들어, 만약keystream 발생기 4명 8비트 LFSRs은 keystream를 생산하고 하나를 등록하는 부울 함수 결과에 상관성이 있는 결합하여 28+224의 총 공격 복잡성에 대해, 우리가 외면할 수 없는 힘이 처음으로 나머지 3.전체 s에 이성이 없는 부대 공격을 시작하는 비용에 비해시스템(복잡성³² 2)은 256 미만의 공격력 절약 요인을 나타내며, 이는 상당한 수준이다. 만약 두 번째 레지스터가 기능과 상관관계가 있다면, 우리는 이 과정을 반복해서 공격⁸ 복잡성을 2 + 2⁸ + 2로¹⁶ 떨어뜨려 65028이하의 노력절감률을 얻을 수 있다. 이런 의미에서 상관관계 공격은 알고리즘을 분할하여 정복하는 것으로 간주할 수 있다.

예

Geffe 생성기 중단

Consider the case of the Geffe generator, which consists of three LFSRs: LFSR-1, LFSR-2 and LFSR-3. If we denote the outputs of these registers by ${\displaystyle x_{1}}$, ${\displaystyle x_{2}}$ and ${\displaystyle x_{3}}$, respectively, then the Boolean function that combines the three registers to provide the generator output is given by ${\displaystyle F(x_{1},x_{2},x_{3})=(x_{1}\wedge x_{2})\oplus (\neg x_{1}\wedge x_{3})}$ (i.e. (${\displaystyle x_{1}}$ AND ${\displaystyle x_{2}}$) XOR (NOT ${\displaystyle x_{1}}$ AND ${\displaystyle {x\mathrm{}}_{}}$ $3{\displaystyle {}_{}}$ ${\$ 3개의 레지스터 출력에는 2³ = 8개의 가능한 값이 있으며, 각 레지스터에 대한 이 결합 함수의 값은 아래 표와 같다.

부울 함수 출력 표

${\displaystyle x_{1}.$	${\displaystyle x_{2}}:$	${\displaystyle x_{3}}$	${\displaystyle F(x_{1},x_{2},x_{3}}}}$
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

세 번째 레지스터인 x 3 ${\$의 출력을 고려하십시오$.$ The table above shows that of the 8 possible outputs of ${\displaystyle x_{3}}$, 6 are equal to the corresponding value of the generator output, ${\displaystyle F(x_{1},x_{2},x_{3})}$. In 75% of all possible cases, ${\displaystyle x_{3}=F(x_{1},x$$_{2},x_{3}}}$. 따라서 우리는 LFSR-3가 발전기와 상관관계가 있다고 말한다. 이것은 우리가 다음과 같이 이용할 수 있는 약점이다.

Suppose we intercept the ciphertext ${\displaystyle c_{1},c_{2},c_{3},\ldots ,c_{n}}$ of a plaintext ${\displaystyle p_{1},p_{2},p_{3},\ldots }$ which has been encrypted by a stream cipher using a Geffe generator as its keystream generator, i.e. ${\displaystyle c_i=p_{}}$${\displaystyle c_{i}=p_{i}\oplus F(x_{1i},x_{2i},x_{3i})}$ for ${\displaystyle i=1,2,3,\ldots ,n}$, where ${\displaystyle x_{1i}}$ is the output of LFSR-1 at time ${\displaystyle i}$, etc. 우리가 일반 텍스트의 일부를 알고 있다고 가정하자. 예를 들어, $우리$는 p${\displaystyle {}_{}{1\mathrm{}}_{}}$, ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$,${\displaystyle {}_{}}$p ${\displaystyle {3\mathrm{}}_{}\dots ,}$ p ${\displaystyle {32}_{}}$ ${\$ 즉 일반 텍스트의 첫 32비트(텍스트의 4 ASCII 문자에 대응)를 알고 있다. 예를 들어, 일반 텍스트가 유효한 XML 파일이라는 것을 알고 있다면 처음 4개의 ASCII 문자는 "<xml"이어야 한다는 것을 알 수 있다. 마찬가지로, 많은 파일 형식이나 네트워크 프로토콜은 쉽게 추측할 수 있는 표준 헤더나 바닥글을 가지고 있다. Given the intercepted ${\displaystyle c_{1},c_{2},c_{3},\ldots ,c_{32}}$ and our known/guessed ${\displaystyle p_{1},p_{2},p_{3},\ldots ,p_{32}}$, we may easily find ${\displaystyle F(x_{1i},x_{2i},x_{3i})}$$$ $i{\displaystyle }$= ${\displaystyle 1}$,${\displaystyle 2}$,${\displaystyle 3}$,${\displaystyle }$… ${\displaystyle 32}$ ${\displaystyle i=1,2,3,\ldots,32}$을(를) XOR로 함께 표시한다$$. 우리는 이제 발전기 출력의 32비트를 연속적으로 알게 되었다.

이제 우리는 LFSR-3(Kerckhoffs의 원칙에 부합하는 가정인 LFSR-3의 태핑된 비트를 알고 있다고 가정할 때)에 대해 가능한 키(초기 값)의 공간을 무차별적으로 검색하기 시작할 수 있다. 키 스페이스에 주어진 키에 대해, 우리는 LFSR-3의 첫 32비트를 신속하게 생성하여 이를 전체 발전기 출력의 복구된 32비트와 비교할 수 있다. 앞서 LFSR-3의 출력과 제너레이터의 출력 사이에 75%의 상관관계가 있다는 것을 확인했기 때문에, LFSR-3의 키를 정확하게 추측했다면, LFSR-3 출력의 처음 32비트 중 약 24비트가 제너레이터 출력의 해당 비트와 일치한다는 것을 알고 있다. 만약 우리가 잘못 추측했다면, 이 두 시퀀스의 처음 32비트 중 대략 절반, 즉 16비트가 일치할 것으로 예상해야 한다. 따라서 우리는 LFSR-1 및 LFSR-2의 키와 독립적으로 LFSR-3의 키를 복구할 수 있다. 이 단계에서 우리는 3개의 LFSR의 시스템을 단일 LFSR과 2개의 LFSR의 시스템을 강제하는 문제에 강제하는 문제를 줄였다. 여기서 절약되는 노력의 양은 LFSR의 길이에 따라 달라진다. 현실적인 가치에 있어서, 그것은 매우 실질적인 절약이며, 맹수 공격을 매우 실용적으로 만들 수 있다.

위의 표에서 $x{\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$}도$$ 8번 중 6번 제너레이터 출력에 동의하며, ${\displaystyle {다시\mathrm{}}_{}}$ x 2 ${\$}와$$ 제너레이터 출력 사이의 상관 관계가 75%인 것을 관찰하십시오. LFSR-1과 LFSR-3의 키와는 별개로 LFSR-2에 대한 흉포 공격을 시작할 수 있으며, LFSR-1만 파손되지 않은 채로 남겨둘 수 있다. 따라서 우리는 완전히 독립적인 3개의 LFSR을 제동하는데 필요한 만큼의 노력으로 게페 발생기를 파괴할 수 있다. 즉, 게페 발생기는 매우 약한 발전기로서 스트림 암호 키스트림을 생성하는데 절대 사용되어서는 안 된다.

${\displaystyle {위}_{}}$의 표에서 볼 때 $x{\displaystyle {}_{}}$ 1 ${\$1}은(는) 8번 중 4번 생성기 출력과 일치한다는$$ 점을 유의하십시오(상관률 50%). 우리는 이것을 다른 것들과 독립적으로 LFSR-1을 강제하는 데 사용할 수 없다. 올바른 키는 발전기 출력에 50%의 시간 동안 동의하는 출력을 산출하지만 평균적으로 부정확한 키를 산출한다. 이는 보안 관점에서 이상적인 상황을 나타낸다. 결합 함수 $F{\displaystyle ({x\mathrm{}}_{}}$ 1,${\displaystyle {}_{}{x\mathrm{}}_{}}$ ${\displaystyle {}_{}}$, ${\displaystyle {}_{}{3\mathrm{}}_{}}$ ) ${\displaystyle F(x_{1},x_{2},x_{3}}$를 선택하여 각 변수와 결합 함수의 출력 간의 상관 관계가 가능한 50%에 근접하도록 해야$$ 한다. 실제로 기간 길이와 같은 다른 설계 기준을 희생하지 않고 이를 달성하는 기능을 찾기가 어려울 수 있으므로 절충이 필요할 수 있다.

공격의 통계적 성격을 명확히 함

위의 예는 상관관계 공격의 이면에 있는 비교적 단순한 개념을 잘 보여주고 있지만, 그것은 아마도 개별 LFSR의 짐승 같은 강제력이 어떻게 진행되는지에 대한 설명을 단순화시킬 수 있다. 우리는 키가 잘못 추측되면 LFSR 출력이 생성기 출력과 대략 50% 일치한다는 진술을 한다. 왜냐하면 주어진 길이의 두 개의 무작위 비트 시퀀스를 주어진다면, 특정 비트에서의 시퀀스 간 합치 확률은 0.5이기 때문이다. 단, 개별적인 부정확한 키는 발전기 출력에 정확히 50%보다 더 자주 또는 더 적게 동의하는 LFSR 출력을 생성할 수 있다. 이것은 발전기와의 상관관계가 특별히 강하지 않은 LFSR의 경우에 특히 두드러진다. 작은 상관관계의 경우, 잘못 추측된 키가 발전기 출력의 원하는 비트 수와 일치하는 LFSR 출력으로 이어질 가능성은 분명히 없다. 따라서 우리는 그 LFSR에 대한 키를 독특하고 확실하게 찾을 수 없을지도 모른다. 비록 이것이 여전히 암호의 보안을 심각하게 침해하고 있지만, 우리는 대신 가능한 많은 열쇠를 찾을 수 있을 것이다. 만약 우리가 예를 들어, 1메가바이트의 알려진 일반 텍스트가 있다면, 상황은 실질적으로 다를 것이다. 키가 잘못되면 발전기 출력의 512 킬로바이트 이상에 동의하는 LFSR 출력이 생성될 수 있지만, 정확히 추측된 키처럼 발전기 출력의 768 킬로바이트에 해당하는 출력은 생성되지 않을 수 있다. 일반적으로 개별 레지스터와 제너레이터 출력 사이의 상관관계가 약할수록 높은 신뢰도로 레지스터의 키를 찾으려면 더 잘 알려진 일반 텍스트가 필요하다. 확률 이론의 배경을 가진 독자들은 이 주장을 공식화하는 방법을 쉽게 알 수 있어야 하며 이항 분포를 사용하여 주어진 상관관계에 필요한 알려진 일반 텍스트의 길이에 대한 추정치를 얻을 수 있어야 한다.

상위 상관 계수

정의

Geffe 발생기에 대한 예시 공격에서 이용된 상관관계는 첫 번째 순서 상관관계의 예로서 발전기 출력의 값과 개별 LFSR 사이의 상관관계다. 이것들 외에도 더 높은 순서의 상관관계를 정의할 수 있다. 예를 들어, 주어진 부울함수가 자신이 결합한 개별 레지스터와 강한 상관관계가 없지만, 두 레지스터의 부울함수 사이에 유의미한 상관관계가 존재할 수 있다($예{\displaystyle {}_{}}$: x ${\displaystyle {1\mathrm{}}_{}{2\mathrm{}}_{}}$ x$$2 {\$displaystyle x_{1$}\$oplus x_$2}}). 이것은 두 번째 순서 co의 예일 것이다.호언장담 우리는 세 번째 순서 상관관계 등을 명백하게 정의할 수 있다.

고차 상관계 공격은 단일 주문 상관관계 공격보다 더 강력할 수 있지만, 이 효과는 "수익 제한법"의 적용을 받는다. 아래 표는 8개의 8비트 LFSR로 구성된 키스트림 발생기에 대한 다양한 공격에 대한 계산 비용을 하나의 부울 함수로 결합한 척도를 보여준다. 비용 계산을 이해하는 것은 비교적 간단하다. 합계의 가장 왼쪽 항은 상관 발전기의 키 공간 크기를 나타내고 오른쪽 항은 나머지 발전기의 키 공간 크기를 나타낸다.

제너레이터 공격력

공략	노력(키스페이스 크기)
폭력	${\displaystyle 2^{8\filename 8}=184467440737095516}$
단일 1차 상관 관계 공격	${\displaystyle 2^{8}+2^{7\f8}=57594037928192}$
단일 2차 상관 관계 공격	${\displaystyle 2^{2\filename 8}+2^{6\filename 8}=281474976776192}$
단일 3차 순서 상관 관계 공격	${\displaystyle 2^{3\message 8}+2^{5\message 8}=1099528404992}$
단일 4차 순서 상관 관계 공격	${\displaystyle 2^{4\message 8}+2^{4\message 8}=8589934592}$
단일 5차 순서 상관 관계 공격	${\displaystyle 2^{5\message 8}+2^{3\message 8}=1099528404992}$
단일 6번째 순서 상관 관계 공격	${\displaystyle 2^{6\filename 8}+2^{2\filename 8}=281474976776192}$
단일 7차 순서 상관 관계 공격	${\displaystyle 2^{7\put 8}+2^{8}=72057594037928192}$

고차 상관관계는 더 강력한 공격으로 이어지지만, 기능에 대한 인수의 수에 따라 제너레이터 출력에 대해 상관할 수 있는 사용 가능한 부울 함수의 공간이 증가하기 때문에 그것들 또한 찾기가 더 어렵다.

용어.

n 변수의$$ Boolean $함수{\displaystyle }$ F${\displaystyle ({x\mathrm{}}_{}}$1${\displaystyle }$,${\displaystyle }$… , x${\displaystyle {}_{}{n}_{}}$) {\$displaystyle F(x_{1},\ldots$ ,$x_{$n}}는 함수 출력과 해당 입력의 m의 Boolean 함수 사이에 유의한 상관관계가 존재하지 않는 경우 일부 정수 m에 대해 "m-th 순서 상관성 면역" 또는 "m-th 순서 상관성"을 갖는다고 한다. 예를 들어, 첫 번째 순서 또는 두 번째 순서 상관관계는 없지만 세 번째 순서 상관관계가 있는 부울 함수는 두 번째 순서 상관관계 내성을 나타낸다. 분명히 상관성 내성이 높으면 키스트림 발생기에서 사용하기 더 적합한 기능을 만들 수 있다(이것만 고려할 필요는 없지만).

지젠탈러는 n 변수의 대수적 정도 d d의 부울함수의 상관관계 내성 m이 m + d n n을 만족한다는 것을 보여주었다. 이는 특정 입력 변수 집합에 대해, 높은 대수적 정도가 가능한 최대 상관관계 내성을 제한한다는 것을 의미한다. 또한, 기능이 균형을 이루면 m m n - 1이다.^[1]

n개의 변수의 함수가 n번째 순서 상관 관계 면역인 것은 불가능하다는 것이다. 이는 입력 함수의 XOR의 조합으로 Reed-Muller 기준을 사용하여 이러한 함수를 작성할 수 있다는 사실에서도 나타난다.

암호 설계 의미

스트림 암호의 보안에 대한 상관 관계 공격의 영향이 극심할 수 있으므로, 스트림 암호에서 상호관계의 사용을 결정하기 전에 후보 부울 조합 함수의 내성을 시험하는 것이 필수적이라고 간주해야 한다. 단, 높은 상관성 내성은 부울 함수가 키스트림 발생기에 사용하기에 적합하기 위해 필요하지만 충분하지 않은 조건이라는 점에 유의해야 한다. 예를 들어, 함수의 균형 여부, 즉 가능한 모든 입력을 고려할 때 0만큼의 1을 출력하는지 또는 대략적으로 출력하는지 등 고려해야 할 다른 문제가 있다.

특정 크기의 부울 함수를 쉽게 생성하기 위한 방법에 대한 연구가 수행되었으며, 적어도 어느 정도의 특정 상관성 내성이 보장된다. 이 연구는 상관 면역 부울 기능과 오류 수정 코드 사이의 연관성을 밝혀냈다.^[2]

이 구간은 확장이 필요하다. 추가하면 도움이 된다. (2008년 10월)

참고 항목

• 암호학의 주제

참조

• 브루스 슈나이어 응용 암호화: 프로토콜, 알고리즘 및 소스 코드(C, Second Edition). 1996년 존 와일리 & 선즈 주식회사. ISBN0-471-12845-7. 섹션 16.4의 페이지 382: LFSR을 사용하여 암호 스트림

외부 링크

• 부울함수의 온라인 데이터베이스는 방문자가 상관 내성을 포함한 여러 가지 방법으로 부울 인자 데이터베이스를 검색할 수 있도록 한다.