2. Cryptography

Cryptography의 특징

Encryption	randomized 같은 key에 대해서 plaintext는 여러 ciphertext가 나올 수 있다.
Decryption	deterministic 같은 key에 대해서 ciphertext의 plaintext는 하나이다.
One-to-many	plaintext space < ciphertext space

 

 

Computational Security

Perfect secrecy는 현실적으로 달성하기 어렵다. 그래서 우리는 2 relaxation을 적용한다.

1. Efficient adveraries (유한한 공격 수행)
2. Small probability to break

 

 

Concrete Approach

$(t, \epsilon)$-secure

$t$: 공격 투자 시간, $\epsilon$: 공격 성공 확률

 

Example) n-bit key에 대해서는 $(t,  t / 2^n)$-secure이 성립하게 된다.

 

가령 n=128, $t$=$2^{60}$이라면 $\epsilon$=$2^{-68}$이 된다. 매우 작은 성공 확률임을 알 수 있다.

 

 

The Asymptotic Approach

Crypto system이 polynomial time에 동작하면서 매우 작은 확률로 break되면 efficient하다고 평가한다.

 

 

Semantic Security

Ciphertext만으로 plaintext를 유추(구분)하기 어렵다.

 

 

IND-CPA

Indistinguishable under Chosen Plaintext Attack

 

IND-CPA 상황에 대한 그림이다.

앞서 Perfect secrecy가 plaintext가 ciphertext가 될 확률은 ${1 \over n}$을 의미한다고 공부했다. IND-CPA도 비슷한 의미이다. Bounded computational resource에 대해서, 공격자는 C를 보고 P를 구분하지 못해야 하는 것을 의미한다.

 

 

CPA secure (aka IND-CPA security)

$P[adversary$    $win] = {1 \over 2} + negl(n)$

IND-CPA 실험에서 공격자가 승리할 확률은 ${1 \over 2}$보다 약간 큰 확률이다. 계산 자원이 풍부하다면, 이길 수 있는 확률이 조금 증가하기 때문이다.

 

 

Computational Security

만약 cipher가 computational security만 가지고 있다면, bruteforce attack에 의하여 break될 수 있다. 이를 방지하기 위하여 Information Theoretic Security를 가정한다. 다시 말해, breaking security는 solving problem이며, problem은 풀기 어려운 문제인 것이다. 이 개념에서 modern cryptography가 시작된다.

 

 

---

 

Block cipher

• n : block size
• s : key size
• P : $(0, 1)^n$
• C : $(0, 1)^n$
• K : $(0, 1)^s$
• Encryption : KxP = C, $E_k$: permutation on ${0, 1}^n$
• Decryption : KxC = P, $D_k$:$E_{k}^{-1}$

 

 

Why Block cipher?

Defeating Frequency Analysis	Unit of transformation 크게하기
One-time pad Stream cipher	Block cipher

 

 

DES

Data Encryption Standard

• HW에 특화된 구조이다.
• Block size : 64-bit
• Key size : 56-bit
• 16 rounds of permutation
• Insecure now (vulnerable to bruteforce attack)

DES의 구조

 

 

Attacking block cipher

Known plaintext attack : plaintext-cipertext pair 알고 있는 상황을 가정한다.

• Exhaustive key search
• Dictionary attack
• Differential cryptoanalysis, linear cryptoanalysis
• Side channel attack (ex. cache memory)

DES's vulnerability는 key size가 작다는 것이다.

 

 

Chosen-plaintext Dictionary attack against block cipher

공격 과정은 다음과 같이 진행된다.

1. 모든 가능한 $k$에 대해서 $(k, E_k[0])$ 생성 및 dictionary에 저장
   • key 길이만큼 걸림
2. 새로운 $k_{new}$에 대해서 $E_{k_{new}}[0]$ 생성
3. Dictionary와 비교
   • ciphertext 길이만큼 걸림

Dictionary attack은 space<->time 간의 trade-off가 존재한다.

 

 

AES

Advanced Encryption Standard

• HW, SW에 특화해서 제작되었다.
• Block size : 128-bit
• Key size : 128, 192, 256 bits
• 현재까지 발견된 약점은 없다.
• 구현하는 과정에서 vulnerability가 발견되었다. (timing attack)

 

 

Encryption mode

Block cipher는 하나의 block을 encrypt하는 방법이다. 따라서 arbitrarily long message를 위한 encrypt 방법이 필요하다. IND-CPA를 요구한다. 종류는 대표적으로 3가지 방법이 있다.

• ECB
• CBC
• CTR

 

ECB

Electronic Code Block

• Message를 block size에 맞춰서 분리한다.
• Block 하나씩 암호화하는 방식
• Encryption : $c = E_k [x]$
• Decryption : $x = D_k [c]$

Diterministic하기 때문에 다음의 특징을 가지고 있다.

• same data block -> same ciphertext (vulnerability; pattern이 들킬 수 있다.)
• same key, same message -> same ciphertext

 

 

CBC

Cipher Block Chaining

DES encryption mode

CBC encryption mode

• Random IV(initial vector)를 사용
• $Input_{next}$가 $Output_{prev}$에 영향을 받는다.
• Encryption : $c_1 = E_k [M_1 \oplus c_0]$
• Decryption : $M_1 = c_0 \oplus D_k(c_1)$

CBC는 다음의 특징을 가진다.

• Randomized encryption
  • 반복되는 같은 message가 다른 ciphertext를 가짐
• 이전 block에 영향을 받음
• IV는 random이고 Integrity를 요구함 (Confidentiality는 필요없음)

 

단점으로는 하나의 block이 re-encrypt되면 모든 block을 다시 encrypt해야 한다는 점이 있다.

 

 

CTR

Counter Mode

Stream cipher를 이용한다.

CTR encryption mode

• Block간의 독립이다.
• Encryption : $c_1 = M_1 \oplus E_k [IV+1]$
• Decryption : $M_1 = c_1 \oplus D_k [IV+1]$

CTR의 특징은 다음과 같다.

• Block cipher로 stream cipher가 가능하다.
• Randomized encryption
• Block 간의 독립이기 때문에 random access가 가능하다.
  • Block 순서에 상관없이 Encrypt나 Decrypt가 가능하다.

 

 

---

 

Data Integrity & Source Authentication

Encryption만으로는 data의 수정을 막을 수 없다. 현재 대부분의 방식이 수정이 가능한 형태이다. 이에 따라 message가 변하지 않았음(=Integrity)을 보장하는 수단이 필요하다. 대표적인 대안으로는 Hash function을 이용하는 방법이 있다.

 

 

Hash function

Hash function's space

Hash 함수는 임의의 길이를 가지는 message를 n-bit output으로 바꿔주는 함수이다. Mod 연산을 통해 이를 수행할 수 있다.

 

Example) Input $mod$ $2^{32}$,  then $2^{32}$는 output space.

 

보안 요구 사항을 충족하는 Cryptographic hash function을 이용해서 message integrity를 보장한다.

 

 

Using Hash functions for message integrity

Method 1

Authentic channel로 $H(M)$을 보내서, public으로 온 M의 hash value와 값을 비교하여 일치하면 Integrity가 보장되었다고 본다. 그러나 이 방법은 Insecure하다. Hash collision이 발생할 수 있기 때문이다. 이는 만약 공격자가 같은 Hash를 가지는 M'을 찾는다면, receiver 입장에서는 Integrity가 보장되지 않음을 의미한다.

 

 

Security requirement for Cryptographic Hash functions

Preimage resistant	2-nd preimage resistant	Collision resistant
one-wayness	weak collision resistant	strong collision resistant
y를 보고 x를 찾을 수 없음	x를 보고 h(x)=h(x')인 x'을 찾을 수 없음	h(x)=h(x')인 x와 x'을 구분할 수 없음

 

 

Cryptography Hash Function의 사용 예시

• Software Integrity
• Time-stamping
• Authenticating logs
• Coverd letter
  • message authentication
  • one-time passwords
  • digital signature

 

 

Bruteforce attack on Hash function (Attacking one-wayness)

h:X→Y와 y가 주어졌을 때, h(x)=y를 만족하는 x 찾기

for q iterations:
	pick random x
    
    if h(x)==y then return x
    else iterate
return failed

 

Average case에 대한 공격 성공 확률을 구해보면 다음과 같다.

$P = \epsilon = 1 - (1 - {1 \over |Y|})^q = {q \over |Y|}$

$|Y|$: output space

$Y=2^m$일 때, $\epsilon = 0.5$이려면, $q=2^{m-1}$이다.

 

 

Bruteforce attack on Hash function (Attacking collision resistance  )

h:X→Y가 주어졌을 때, h(x)=h(x')을 만족하는 x, x' 찾기

for q iterations:
	pick random set X0 of q values in X
    
    for x in X0:
    	h(x) -> store
    
    for h(x1), h(x2) in store:
    	if h(x1) == h(x2) then return WIN
return FAIL

 

마찬가지로 average case에 대한 공격 성공 확률을 구해보면 다음과 같다.

$\epsilon = 1- ( 1 - {1 \over |Y|})^{q(q-1) \over 2}$

 

$|Y|=2^m$이면 $q=2^{{n \over 2}}$여야 P=0.5가 된다.

 

이와 같은 공격을 Birthday attack이라고도 한다. Birthday paradox란 생일이 같은 사람이 존재할 확률이 집단의 규모가 100명만 되어도 매우 높음을 의미하며, 이를 통해서 우리는 hash collision이 쉽게 발생할 수 있다는 것을 알 수 있다.

 

인원수가 증가할 수록 생일이 같은 사람이 있을 확률은 증가한다.

 

 

Well known Hash functions

• MD5 : output 128 bits, completely broken.
• SHA1 : output 160 bits
  • Insecure : collision attack ($2^{80}$안에 collision 찾기 가능)
  • Secure : one-wayness
• SHA2 : output 224, 256, 384, 512 bits
• SHA3

 

 

Merkle-Damgard Construction for Hash functions

MD5, SHA1, SHA2가 사용하고 있다.

Merkle-Damgard hash function

구조는 다음과 같이 진행된다.

1. Message divided into fixed size blocks and padded
2. " f  "(compression function)을 통해서 CBC를 수행한다.
3. One-way compression function 덕분에 collision resistant Hash function이 구현된다.

 

 

Hash output의 length의 의미

" The weakest link principle "

 

System에서 가장 약한 부분이 system의 보안 수준이다. Birthday attack과 같은 hash collision을 찾는 공격때문에, 일반적인 hash output의 length는 block cipher의 2배이다.

• Length of hash output = block cipher * 2
  • SHA-224 = 112 bits triple-DES
  • SHA-256, SHA-384, SHA-512 = (128, 192, 256) in AES

이는 만약 작은 hash output이 필요하다면, collision resistant는 포기하고 one-wayness만을 보장해야 함을 의미한다.

 

 

Limitation of using Hash for Authentication

• Authentic channel이 필요함

Hash output이 pulbic이면 위조가 가능해지기 때문에 authentic channel이 필요하지만, 실제로는 이런 채널을 준비하는 것이 쉬운 일이 아니다.

 

Solution으로는 여러개의 Hash function을 사용하는 것이다. 어떤 hash function을 사용할 것인지는 key를 통해서 결정한다.

 

 

Hash Family

(X, Y, K, H)

• X : possible message 모음
• Y : finite output
• K : key space
• H : hash function space

간단하게 H: K×X → Y 라고 생각할 수 있다.

 

 

Message Authentication Code, MAC

$MAC_k(K, M) = H_k(M)$

 

Reciver와 Sender는 key를 공유한다. Sender가 M과 $H_k(M)$을 보내면 Receiver는 M을 보고 $H_k(M)$을 구해서 받은 값과 같은지 비교를 통해 message를 검증한다. 그림으로 표현하면 다음과 같다.

 

 

 

Security Requirement for MAC

Existential Forgery under Chosen Plaintext Attack, EF-CPA의 조건을 만족해야 한다. EF-CPA 요구 사항은 다음과 같이 진행된다. 

1. Challenger가 random k 선택
2. 공격자는 plaintext $M_1$, $M_2$, ..., $M_n$ 중 $M_j$ 선택하여 $t_j=MAC_k(k, M_j)$를 얻는다.
3. 공격자는 M'에 대한 t'을 얻는다.
4. $M_j != M'$인데 $t=t'$이면 공격자의 승리이다.

즉 EF-CPA란 공격자가 기존의 M과 같은 MAC value를 가지는 새로운 M'을 생성할 수 없어야 함을 의미한다.

 

 

MAC with hash function

• h : one-way hash function (ex. SHA2)
• MAC(k||M) = h(k||M)

이러한 방법은 h가 Merkle-Damgard construction을 사용한다면 Insecure하다. 공격과정은 다음과 같다.

1. 공격자가 M과 h(k||M)=t 를 얻음
2. M' = M || Pad(M) || X 라고 가정
   t' = h(k||M')을 얻음
3. t' = h(k||M') = f(MAC(k, M), X) = t
   위 식을 통해서 MAC이 같은 M과 M'을 찾을 수 있음

 

Key length가 중요하며, Key는 여러번 사용되어야 한다.

 

 

HMAC, MAC from Cryptographic Hash function

$HMAC_k[M] = h[(k^+ \oplus opad) || h[(k^+ \oplus ipad) || M]]$

 

• $k^+$ : Padded key with 0 bit. Size is a input block size of hash f(=B).
• ipad : 0x36 repeated B times
• opad : 0x5c repeated B times

간단하게 표현하면 다음과 같다. Hash가 nested function으로 두번 사용된 것이다.

 

$HMAC_k[M] = h(K || h(K||M))$

 

 

HMAC security

Secure hash function 이용시 practical attack은 현재 없다.

 

 

---

Review of Symmetric Cryptography

Confidentiality	Stream cipher (PRNG)
	Block cipher (CBC, CTR)
Integrity	Cryptographic hash function
	Message Authentication Code
Limitations	Sender와 Receiver의 key 공유   Authentic channel 필요   사전 관계가 없으면 불가능   n party > n key 필요

 

---

 

Public key encryption

Party마다 ($k$, $k^{-1}$)을 가진다. 

• $k$ : encryption key, public
• $k^{-1}$ : decryption key, private

$k$를 보고 $k^{-1}$ 추론하는 것은 어려운 일이다. 암호화와 복호화 과정에서 다른 key를 사용하기 때문에 Asymmetric crypto system이라고도 부른다.

 

 

Public key encryption Algorithm

Computation Infeasible을 이용하는 것이다. 대표적으로는 Modular arithmetic number theory나 Elliptic curves 등이 있다. 대표적인 알고리즘과 이것이 사용하는 문제는 다음과 같다.

• Diffie-Hellman Key agreement protocol : hardness of modular arithmetic
• El Gamal : hardness of solving discrete logarithm
• RSA : hardness of factoring large numbers into primes

 

 

Modular Arithmetic : Generator

• $Z^*_p = {0, 1, ..., p-1}$ where GCD(n, p) = 1 for all n
• g : generator of $Z^*_p$, $g^k$ mod $p=Z^*_p$ for all k

예를 들자면, $Z^*_4$의 g는 3이다.

• k=1, 3 mod 4 = 3
• k=2, 9 mod 4 = 1
• ...

 

 

Diffie-Hellman Key agreement protocol

Public key encryption system은 아니다. 하지만 A와 B가 public channel에서 secret share를 가능하게 만들어 주는 방법이다. 과정은 다음과 같다.

 

Secret key를 share하는 방법이다.

 

 

Diffie-Hellman example

p = 11, g = 2 (public values)일 때 가능한 table은 다음과 같다.

 

$Z_{11}^*, g=2$

A는 4, B는 3을 선택했다면, 다음의 과정이 진행된다.

 

 

 

Security of DH ; 3 hard problems

Discrete-Log problem, DLG

<g, h, p> given, $g^a = h$ mod $p$인 a 구하기

Computational Diffie-Hellman problem, CDH

<g, p, $g^a$ mod $p$, $g^b$ mod $p$> given, $g^{ab}$ mod $p$ 구하기

Decision Diffie-Hellman problem, DDH

<$g^a$, $g^b$, $g^c$> given, <$g^a$, $g^b$, $g^{ab}$> 구분하기 IND-CPA 적용

DLG를 풀면, CDH를 해결할 수 있다.

CDH를 풀면, DDH를 해결할 수 있다.

 

Assumption

They are hard to solve. (DLG, CDH, DDH)

* DDH는 large P에 대해서 풀기 어렵다. (at least 1024-bit)

 

 

El Gamal encryption

• Public : <g, p, h= $g^a$ mod $p$>
• Private key : only decryption
• Encryption :
  • random b 선택
  • C = [$g^b$ mod $p$, $g^{ab}$×M mod $p$]
    $g^{ab}$는 DH protocol로 생성, M을 숨겨주는 역할을 담당한다.
• Decryption :
  • C = [$c_1$, $c_2$]
  • ($c_1^a$ mod $p$)×M mod $p$ = $c_2$
    $c_1^a$ mod $p$ = $x$
    $x$×$z$ mod $p=1$ → $z = x^{-1}$ mod $p$
    $z$를 구하면 M을 구할 수 있다.
    
    M = $c_2$×$z$ mod $p$

CDH assumption은 M이 완벽하게 recover되지 않음을 보장해준다.

IND-CPA를 위해서는 DDH assumption이 필요하다.

 

 

RSA  algorithm

The difficulty of factoring large composite numbers에 기반하여 만들어진 알고리즘이다. 

• Public : (e, N)
• Private : d
• Encryption : $C=M^e$ mod $N$
• Decryption : $C^d$ mod $N$ = $M^{ed}$ mod $N$ = M

 

Private key를 생성하는 과정은 다음과 같다.

1. Large prime number p, q 선택
2. N = pq, $\phi(N)$ = (p-1)(q-1)
3. GCD(e, $\phi(N)$) = 1, 1<e<$\phi(N)$인 e 선택
4. ed mod $\phi(N)$ = 1, 1<d<$\phi(N)$인 d 선택

 

e와 N이 공개이기 때문에, 누구나 M을 암호화할 수 있다. 그러나 복호화 과정은 d가 있는 사람만 가능하다.

 

RSA example

Let p = 3, q = 5

1. N = 3*5 = 15, $\phi(N)$ = 2*4 = 8
2. GCD(e, $\phi(N)$) = 1 = GCD(e, 8)
   let e = 3
3. M = 10
4. ed mod $\phi(N)$ = 1 = 3d mod 8
   따라서 d=3
5. Encryption :
   $M^e$ mod $N$ = $10^3$ mod 15 = 10
6. Decryption :
   $C^d$ mod $N$ = $10^3$ mod 15 = 10

 

*GCD 계산

GCD(17, 40) = ?

• 40 = 17*2 + 6
• 17 = 6*2 + 5
• 6 = 5*1 + 1
• 5 = 1*5 + 0, 1 = GCD(17, 40)

 

 

Security of RSA

Factoring problem

Given N=pq, p와 q 찾기

Finding RSA Private key

Given (N, e), ed mod $\phi(N)$ = 1을 만족하는 d 계산하기   - (d, e)가 주어졌을 때, N의 인수를 찾는 랜덤 알고리즘은 존재함  - 여러 user간에 modulus N을 공유할 수 없음

RSA problem

Given (N, e) and C, C = $M^e$ mod N을 만족하는 M 계산하기  - N이 인수분해가 가능하다면 풀 수 있음

 

 

RSA security & Factoring

• Security가 difficulty of factoring N에 의존한다.
  • Factor N → $\phi(N)$ 계산 → (e, N)으로 d 구할 수 있음
  • ed mod $\phi(N)$=1을 만족하는 (e, d)를 앎 → Factor N
• N의 길이도 중요하다.
  • 2009년 768-bit N이 인수분해됨(2년 걸림)
• RSA en(de)cryption 속도는 key length의 2배이다.
• 현재는 최소 1024-bit를 권장한다.

 

 

Real world Usage of Public Key encryption

Symmetic key를 암호화해서 사용하기도 한다,

• [$K^e$ mod n, AES-CBC$_k$(M)]

 

혹은 random padding을 통해서 M을 암호화하기도 한다.

• (M||r)$^e$ mod n,  where r : random value

 

---

Digital Signature

MAC에는 여러 한계가 존재한다. 비밀 키를 공유하지 않는 사용자는 이를 사용할 수 없으며, Non-repudiation이 불가능하다. A가 B에게 MAC을 전송했음에도, 나중에 A가 이를 부인할 경우 증명할 수 있는 방법이 없다. 이에 따라 Digital signature가 제안된다. 다음의 특징을 가지고 있다.

• 제 3자에 대한 Authentication
• Non-repudiation
• Data integrity

하나의 party가 signature를 생성하면, 다른 parties에서 증명할 수 있다. Digital signature에는 2가지 구조가 있다.

• Signing algorithm
  Message, Private Key → Signature 
• Verification algorithms
  Signature, Public Key → Message

주로 Hash function을 사용한다. Public key encryption은 성능 이슈가 있어서 message 전체를 암호화하기 보다는 hash value를 암호화하기 때문이다. 이 때, hash function은 strong collision resistant이다.

 

 

RSA signature

• Public : (e, N)  → Signature verification
  $S^e$ mod $n$ = h(M)
• Private : d → Signature generation
  S = $h(M)^d$ mod n

 

---

The Big Picture

	Secret Key	Public Key
Secrecy / Confidentiality	Stream cipher Block cipher Encryption modes	RSA El Gamel
Authenticity / Integrity	Message Authentication Code	Digital Signature