1. Cryptography

Computer Security, CIA Triad

Confidentiality	Integrity	Availability
기밀성 인가된 사람만 정보 확인 가능	무결성 정보 부인 방지 및 신뢰성 보장	가용성 정보에 대한 안정적 접근 보장

 

 

Goals of Cryptography

Secure security of communication over insecure medium.

 

암호학이 보장하는 secure communication은 다음과 같다.

Secure communication
Confidentiality	Integrity

 

Insecure medium이 의미하는 바는 공격자가 언제나 존재한다는 것을 의미한다.

Insecure medium
Passive attacker	Active attacker
system에 해를 가하지 않음	system에 해를 가함

 

 

Approaches to secure communication

Steganography	Cryptography
message 존재 여부를 숨김	message 내용을 숨김
Algorithm	Key

 

 

Shift Cipher

• Key space : 26 (A~Z)
• Key : k
• Encryption : +k
• Decryption : -k

간단하게 글자를 key만큼 밀어서 암호화하는 방식이다. Key space가 작기 때문에 bruteforce attack에 취약하다. 이를 통해서 Key space가 커야 좋은 암호화 방식임을 알 수 있다.

 

 

Mono-alphabetic substitution cipher

• Key space : all permutation of A~Z
• Key : ABCDE...XYZ
• Encryption : $\pi (x)$
• Decryption : $\pi^{-1}(y)$

Key space가 26!이기 때문에 bruteforce attack이 불가능하다. Frequency analysis와 같은 방법을 사용해서 공격이 가능하다.

 

 

Frequency analysis

언어마다 자주 사용되는 언어가 있기 때문에, 이 빈도수를 통해서 ciphertext를 추론하는 방법이다. Ciphertext의 자주 반복되는 언어를 the, an 등과 매치하여 plaintext를 얻는다.

 

How to defeat Frequency analysis?

1. Use different substitution
    Frequency를 줄이기 위해 사용한다.
        - Poly-alphabetical substitution ciphers
        - Stream ciphers
2. Use larger block
    단어를 key로 사용한다. Block cipher라고 한다. 
        - DES
        - AES

 

 

Poly-alphabetical substitution cipher

mono에서의 단점은 $\pi(x)$로 결과가 정해지는 것이었다. 이를 방지하기 위하여 substitution을 다양하게 구성한다. 대표적인 방법으로 Vigenere cipher가 있다.

 

 

Vigenere cipher

• Key : word
• Encryption : $(p_{i}+k_i) mod 26$
• Decryption : $(c_{i}-k_i) mod 26$

같은 plaintext여도 다른 ciphertext가 될 수 있다. 따라서 Frequency analysis를 적용하기 어렵다.

 

Vigenere cipher : Cryptoanalysis

1. Find the length of key
   • Kasisky test
   • Index of coincidence
2. Divide the message by the length of key
3. Frequency analysis

Key 길이에 한해서는 여전히 frequency가 유지되고 있기 때문에 가능한 공격이다.

 

 

Kasisky test

Same ciphertext 사이의 길이의 최대 공약수가 key의 길이일 수 있다.

1. Identical segment 찾기
2. Distance 기록
3. Key length 찾기 (GCD)

Key 길이가 plaintext와 같으면 key 길이를 찾지 못하는 단점이 있다.

 

 

One-Time pad

• Key space : $(z_m)^{n}$
• Key : uniformly random string as long as plaintext
• Encryption&Decryption : Shift cipher

Vigenere의 취약점이던 key 길이를 plaintext만큼 늘린 방법이다. 직관적으로는 key가 random이기 때문에 secure하지만, 매우 길기 때문에 practical하지는 않다. 또한 reused되면 안된다는 제약이 있다.

 

 

Stream cipher

One-Time pad의 random key 대신에, pseudo random key를 사용하는 방식이다.

$E_{k}[M]=M \oplus PRNG(k)$

 

*PRNG

pseudo random number generator from seed

같은 seed에서 같은 output이 나온다. (대칭키이므로 중요한 성질)

Unpredictable sequence이다. 다음 bit 추측이 불가능하다.

 

그러나 충분한 길이의 output을 알고 있으면, key recover가 가능하다.

 

*The RC4 stream cipher

• Key space : 40~256 bits
• Output : unbounded
• PRNG은 completely secure하지 않음
  • First part에서 bias가 관측됨, 따라서 first n bit는 사용하지 않음

 

 

Stream cipher : cryptoanalysis

P1와 PRNG(key)의 key stream을 알고 있으면 bruteforce attack을 통해서 P2를 얻을 수 있다.

1. $P1 \oplus k = C1$
2. $P2 \oplus k = C2$
3. $C1 \oplus C2 = P1 \oplus P2$

 

 

Stream cipher : Practice

Key에 randomness를 추가하여 사용한다.

• IV : initial vectors
  • Integrity 필요, Confidentiality 필요없음
  • Key stream 반복하지 않음을 보장
  • 반복되서 사용되면 안됨

 

 

Adversarial Models for cipher

Ciphertext-only	Known plaintext
ciphertext만 알고 있음	plaintext-ciphertext pair만 알고 있음
Chosen plaintext	Chosen ciphertext
message를 encrypt할 수 있음	ciphertext에서 plaintext를 얻을 수 있음

 

 

Security Principles

• Kerckhoffs's principle
  • 내부 system 정보가 public이어도 보안이 가능해야 함(key는 비밀)
• Shannons's maxim
  • 공격자가 key 제외 모든 정보를 알아도 보안이 가능해야 함
• Shannons's security - Perfect secrecy
  • Ciphertext와 plaintext가 독립적이어야 한다.
  • "Key length ≥ plaintext length" 만족해야 가능함.
  • P[ PT=m ∩ CT=c ] = P[ PT=m ] P[ CT=c ]
  • P[ CT=c | PT=$m_1$ ] =P[ CT=c | PT=$m_2$ ]