스트림 암호에서 공격자는 m1 x 또는 m2를 알고 있다면 어떻게 m1 m2를 얻을 수 있습니까?

Question

스트림 암호 c = m xor G (k)에서 알 수 있습니다. 키를 한번 이상 사용 된 경우에, 공격자는 얻을 수

• C1 = M1을 배타적 G (k)는
는
• C2 = m2의 XOR G (k)는

은 다음 그는 C1의 XOR 알고 c2 = m1 x 또는 G (k) x 또는 m2 x 또는 G (k) = m1 x 또는 m2.

(m1 xor m2)에 대한 지식으로 공격자는 어떻게 m1 m2를 알 수 있습니까?

Answer 1

당신이 말한대로 : c1 xor c2 = m1 xor m2 k가 동일하면.

이 방정식에서 다른 것을 복구하려면 m1 또는 m2를 알아야합니다.

현실적으로 m1 또는 m2는 G(k)과 같은 의사 랜덤 문자열이 아닙니다. 예측 가능하거나 쉽게 콘텐츠를 추측 할 수 있습니다. 예를 들어, m1과 m2는 영어 문장이거나 m1과 m2는 둘 다 일부 프로토콜의 헤더입니다.

Answer 2

아주 간단한 예를 들어 보겠습니다. 메시지는 1 비트이며, 독립적으로 다음 배포에서 선택한다고 가정

P(m1=1, m2=1) = .36 
P(m1=1, m2=0) = P(m1=0, m2=1) = .24 
P(m1=0, m2=0) = .16 

그런 다음, x = m1 xor m2을 고려

P(m=0) = .4 
P(m=1) = .6 

다음, 우리는 두 개의 메시지 m1 및 m2의 공동 분포를 계산할 수 있습니다. 우리는이 : x=0, 우리는 우리의 초기 60 %/40 %를 조정하면, 즉

P(m1=1|x=0) = P(x=0|m1=1) * P(m1=1)/P(x=0) = .6 * .6/.52 = 9/13 (.692) 
P(m1=0|x=0) = P(x=0|m1=0) * P(m1=0)/P(x=0) = .4 * .4/.52 = 4/13 (.308) 

P(m1=1|x=1) = P(x=1|m1=1) * P(m1=1)/P(x=1) = .4 * .6/.48 = .5 
P(m1=0|x=1) = P(x=1|m1=0) * P(m1=0)/P(x=1) = .6 * .4/.48 = .5 

:

P(x=0) = P(m1=1, m2=1) + P(m1=0, m2=0) = .52 
P(x=1) = .48 

P(x=0|m1=1) = P(m2=1) = 0.6 
P(x=0|m1=0) = P(m2=0) = 0.4 
P(x=1|m1=1) = P(m2=0) = 0.4 
P(x=1|m1=0) = P(m2=1) = 0.6 

따라서, 우리는 베이 즈 정리를 사용하여 x을 제공 m1의 사후 분포를 계산할 수 있습니다 메시지가 1 인 확률이 더 높다고 추정합니다. x=1 인 경우 초기 추정치를 조정하여 두 메시지가 모두 동일하다고 판단합니다. 두 경우 모두 새로운 추정치가 처음 60 %/40 % 추정치보다 낫습니다.

평문은 무엇인지 확실하게 말할 수있는 정보가 충분하지 않지만 일부 정보는 얻었습니다 (키를 한 번만 사용하면 발생하지 않음).

초기 분포가 50 %/50 % 인 경우 조건부 확률은 여전히 ​​50 %/50 %로 나오므로 초기 분포가 왜곡된다는 사실이 중요합니다. 더 많은 메시지가 안다면

동일한 기술

또한, 예를 들어 사용될 수있다 : 우리는 독립적 인 다수의 메시지, 따라서 x 변수의 수가 많은 경우

x1 = m1 xor m2 
x2 = m1 xor m3 

P(m1=1|x1=0, x2=0) = P(x1=0, x2=0|m1=1) * P(m1=1)/P(x1=0, x2=0) = (.6 * .6) * .6/.28 = 27/35 (.771) 

우리는 말할 수 x은 아마도 0 및 1 중 하나를 약 60 %의 시간과 다른 하나는 약 40 %의 시간 중 하나를 취할 것입니다.x이 0을 선호하면 m1=1이고 그 반대의 경우도 마찬가지입니다.

영문 텍스트의 경우 간단한 방법은 영문 메일 빈도 표를 초기 배포로 사용하고 각 문자에이 방법을 적용하는 것입니다. 그러나 더 복잡한 영어 적용 모델이 있습니다. 예를 들어, 각 문자가 앞의 문자 (즉, 마르코프 체인)에 따라 다른 도수 분포를 갖는 영어 모델을 취할 수 있습니다. 이러한 조건부 확률을 사용하여 단일 문자 방법을 반복함으로써 마르코프 체인에서 표본을 추출하여 가능성있는 평문을 발견 할 수 있습니다. 또는 조금 더 노력하면서이 모델에서 가장 가능성있는 메시지 목록을 계산할 수 있습니다 (단, 각 단계에서 가장 가능성이있는 편지를 취하는 것이 '탐욕 스럽다'는 메시지가 전체적으로 가장 가능성이있는 메시지는 아님).