04. Theory of Secure Communication

학습개요

-Model of Secure System

-Theory of Secrecy Systems

  · Condition for perfect secrecy

  · Shannon Entropy

  · Equivocation

  · Perfect Secrecy

  · Redundancy

  · Unicity Distance

-Complexity Theory

Digital Signature Susceptibility

<MD5에서의 Hash값>

MD5:128비트 암호화 해시 함수

susceptibility: 민감성

 

Hash 동작 : m→ f(m)(=H(m))

 

m'≠m이면 f(m')≠f(m) 이어야한다.

m'≠m인데 f(m')≠f(m)이면 attacker가 m'으로 f(m)에 접근할 수 있기때문에 보안이 취약해진다.

 

문제해결

① MD5를 더 많은 bit로 사용

② 동일한 hash를 가진 두 개의 사기성 문서를 발견하면 정보를 얻지 못하므로 해시함수의 결과값은 충분히 커야한다.

≫ 더 큰 hash를 사용하여 collision이 발생하지 않도록 해야한다.

≫ 더 많은 bit를 사용한다.

 

Model of Secure System

M → E(M,K) → C → D(C,K) → M

(이 때 secrecy를 위해 Key를 사용하며 secure channel을 통해 전달한다.)

 

Shannon Theory

secrecy problem은 noisy-channel problem과 유사하다.

redundancy: 그것이 없어도 전체 정보의 본질적인 뜻이 변하지 않는 정보. 즉, 필요없는 정보

 

Noisy Channel에서 redundancy를 통해 original message를 recover하듯, 해독 과정에서 암호화된 Cipher(Message+Noise)에서 Noise를 제거하여 M을 찾아내는 것이 서로 유사하다.

 

Priori and Posterior Probabilities

사전확률과 사후확률

사전확률 P_i로 모든 K 중에서 K_i를 선택하고, 사전확률 Q_j로 모든 M 중에서 M_j를 선택하여 M은 Cipher text로 변환된다.

C_l=E(M_j,K_i)

 

attacker는 C_l만 볼 수 있으며 가능한 M_j와 K_i의 사후확률을 계산한다.

 

Condition for Perfect Secrecy

  사후확률(posteriori probability)은 attacker의 knowlege를 나타낸다.

  P(M|C) : C가 주어졌을 때 M을 찾을 확률

 

P(M|C)=P(M)이 되는 것이 가장 바람직하다. attacker가 C를 통해 아무정보도 얻지 못한다는 뜻이므로.

 

∴Perfect Secrecy를 위한 조건

① P(M|C) = P(M)

② P(C|M) = P(C)

 

  perfect system이란 다수의 C와 M이 존재할 때 M을 C로 변환하는 적어도 하나의 key가 있는 상태를 말한다. attacker의 입장에서 guessing이 불가능하고 모두 같은 확률이 되도록 해야한다.

 

Shannon Entropy

  Entropy: 불확실성

 Shannon Entropy: random 변수의 예측 불가능성을 측정한 것.

이 때, b는 bit의 경우 2, digit의 경우 10이 된다. 즉, 가능한 경우의 수이다.

예측이 어려울수록 불확실해지므로 Entropy가 크다고 한다. (Entropy가 클수록 좋음)

 

ex) 동전 던지기

H일 확률 : 1/2

T일 확률 : 1/2

 

만약 Coin이 Biased Coin일 경우 H와 T의 확률이 같지 않아 엔트로피 값을 통해 예측가능해진다.

 

<Shannon Entropy의 종류>

① Message Entropy

메시지가 선택됐을 때 얻는 정보의 양

 

② Key Entropy

Key가 선택됐을 때 얻는 정보의 양

≫ Key Entropy≥Message Entropy일 때 메시지 정보가 완벽히 은폐된다.

 

Equivocation

equivocation: 모호성

conditional entropies of the key K and message M

앞서 알아본 Entropy 공식에 조건이 추가되었다. ~일 확률이 아닌, ~일때 ~일 확률로 계산한 Entropy이다.

cipher text의 길이가 길수록 uncertainty가 줄어든다. 즉, 예측하기 쉬워진다.

 

<Perfect Secrecy>
I(M|C) : C가 주어졌을 때 M에 대해 새롭게 알려지는 정보량

I(K|C) : C가 주어졌을 때 K에 대해 새롭게 알려지는 정보량

 

C가 주어짐으로써 새로 알게된 정보 = Uncertainty - C를 알고 난 뒤의 Uncertainty

I(M|C) = H(M)-H(M|C)

이 때 I(M|C)=0이 되는 것이 가장 이상적이다.

∴H(M)=H(M|C)가 되어야한다.

≫ C가 uncertainty of message를 낮추지 않는다.

 

또한, H(K)≥H(M)이어야한다. 즉, Key bits 수가 Message bits 수보다 같거나 많아야한다.

유도:

H(M|C)≤ H((M,K)|C) = H(H|C)+H(M|(C,K))

이 때, H(M|(C,K))=0이므로

 

H(M|C)≤ H(H|C)≤H(K)

H(M|C)=H(M)

∴H(M)≤H(K)

 

결론 - Perfect secrecy를 위한 조건

① I(M|C)=0, H(M)=H(M|C)

② H(K)≥H(M)

 

Intercepted Ciphertext

H(M|C₁,C₂,...,C_n+1)에서 C의 개수가 많아질수록(=정보가 더 많을수록) entropy가 감소한다.

 

Redundancy

redundancy: 그것이 없어도 본질적인 뜻이 정하지 않는 정보. 즉, 무의미한 정보

D=R-r

R: Absolute Rate of the language, 조합가능한 모든 경우의 bit 수(entropy)

ex) cat, cta, act...

r: Rate of the language, 실제 사용하는 조합의 entropy

ex) cat

 

R-r의 결과는 사용하지 않는 무의미한 단어가 된다.

 

Spurious Key Decipherment

spurious: 거짓된

 

C=E(M,K)이고 C를 생산하는 또 다른 K가 존재할때 spurious key decipherment가 발생한다.

C=E(M,K)=E(M',K')일 때 발생한다.

2H(K)-1개의 spurious key decipherment가 존재한다.

 

Unicity Distance

무차별 대입 공격에서 가능한 spurious key의 수를 0으로 줄임으로써 암호를 해독하는데 필요한 원래 암호 텍스트의 길이

F:number of false solutions

q:false solution을 생산할 확률

F=(2^H(K)-1)q≒2^H(K)-DN

log₂F=H(K)-DN

 

Length of Ciphertext가 커질수록 Number of False Solutions이 작아진다.

 

F 값을 0으로 두어 암호를 해독하는데 필요한 원래 암호 텍스트의 길이를 계산할 수 있다.

0=H(K)-DN

H(K)=DN

 

N=H(K)/D=Entropy/Redundancy

 

위 식에서 다음과 같은 관계를 발견할 수 있다.

Entropy↑ : Unicity Distance↑

Redundancy↓ : Unicity Distance↑

 

Unicity Distance 계산 예

8bits per letter이므로

17.5×8bits=140bit=2blocks