MIDTERM 정리

1. Introduction

What is computer security?

CIA Triad

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

 

Accountability, Availability

책임추적성은 자신의 행위에 대해 차후에 책임을 질 수 있는 개인들까지 시스템에서 수행하는 활동을 추적할 수 있는 속성을 말한다.

 

Why these attacks can succeed?

SW나 컴퓨터 시스템에 버그가 있거나, 유저가 실수하거나, 기술적인 요소(폰 노이만 구조, 안전하지 않은 프로그래밍 언어, 복잡한 SW, 보안성 강화의 어려움, Usability)들에 의해 성공할 수 있다.

 

Security is

• Not Absolute
  상대적인 것이다.
• Secondary
  물리 세계에서 발생하는 보안 이슈는 해결할 수 없다.
• Interesting
  사람에 의해 흥미로운 공격이 발생한다.
  Information security는 attack, defense 관점에서 독립적인 영역이다.
  Benefit / Cost의 trade-off이다.
  기술적인 문제 외에도, 사람의 문제로 공격이 발생할 수 있다.
• Challenging
  Defense는 attack보다 어렵다.

 

Terms

• Adversary
• Attack
• Countermeasure
• Risk
• Security Policy
• System resource
• Threat
• Vulnerability

 

 

2. Crypto

Shift cipher

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

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

 

Substitution cipher

Mono-alphabetical substitution

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

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

 

Poly-alphabetical substitution

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를 적용하기 어렵다.

 

다음의 공격에 의해서 break될 수 있다.

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 길이를 찾지 못하는 단점이 있다.

 

 

3. Security Principals

Adversarial models for ciphers

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

 

Kerckhoffs's principle

내부 system 정보가 public이어도 보안이 가능해야 한다. Key는 비밀이다.

 

Shannon's maxim

공격자가 key 제외 모든 정보를 알아도 보안이 가능해야 한다.

 

 

4. Crypto

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되면 안된다는 제약이 있다.

 

Shannon security (= Perfect security)

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$ ]

 

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는 사용하지 않음

 

Brute-force attack / Randomness

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$

 

이를 방지하기 위해 Key에 randomness를 추가하여 사용한다.

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

 

Computational security

Computationally bounded, small probability

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

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

 

$(t, \epsilon)$-secure

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

 

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

 

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

 

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

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

 

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

 

 

5. Crypto

Block ciphers

• 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}$

 

DES

Data Encryption Standard

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

DES의 구조

 

AES

Advanced Encryption Standard

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

 

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가 존재한다.

 

Encryption modes

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가 가능하다.

 

Hash function

one-way, weak collision resistent, strong collision resistent

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'을 구분할 수 없음

 

attack on hash function

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이 쉽게 발생할 수 있다는 것을 알 수 있다.

 

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

 

Merkle-Damgard Construction

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이 구현된다.

 

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은 현재 없다.

 

 

6. Crypto

Public Key Encription

Diffie-Hellman Key Aggrement Protocol

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

 

Secret key를 share하는 방법이다.

 

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 Gamel

• 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

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를 권장한다.

 

Digital signature

Non-repudiation

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

 

 

7. Authentication

Password

Attacks

Password를 유추해서 공격하는 방법이다. 다음의 요소에 의하여 성공이 결정된다.

Average # of guesses	Easiness to check validity
how long? symbols? how is it created?	PW 저장 방식 PW 확인 방식 Limitation on trying PW

 

Password entropy, Usability

Password의 복잡도를 측정하는 방법이다. Entrophy는 bit를 이용해서 계산한다. 평균적으로 password entrophy의 절반 정도의 시도는 이루어저야 공격에 성공한다. 일반적으로 사람은 충분한 password entrophy를 가지지 못한다. Usability 때문이다.

 

NIST에 따른 일반적인 password entrophy는 다음과 같다.

Char의 category를 고려하지 않은 PW entrophy이다.

 

Better Password Entrophy

PW entrophy를 높이기 위해서는 다음의 방법이 있다.

• Different category of characters
• Orders
• State-of-art : Markov Chain
  Markov chain으로 unpredictable한 PW를 만들 수 있다.

 

PW를 다른 order로 시도하는 공격 등의 fundamental challenge들은 여전히 존재한다. 그렇기에 PW entrophy를 높이는 작업은 중요하다.

 

*Example of weak PW

Default passwords password

 

Dictionary words Apple

 

Words with simple obfuscation p@ssword

 

Double words appleapple

 

Keyboard row sequences qwer, 1234, asdfg

 

Well known numeric # 112, 911, 119

 

Identifiers 1999/03/03

 

Anything personally related to an individual

 

Avoid Weak Passwords

• Long passphrase
• Randomly generate PW (일반적으로는 적절하지 않음)
• Check the quality of user PW
  • Dictionary attack 등을 시도해서 바꾸라고 알려주기
• Give user suggestion / guidelines

 

Balancing : PW entrophy, Usability

• Random PW는 user가 기억하기 어렵기 때문에 often bad하다. 
• PW expiration, PW trial limitation 등이 구현되어 있다면 Guessing PW도 괜찮을 수 있다.

Usability 때문에 발생하는 문제이다. 적절한 선택이 필요하다.

 

Storing password, UNIX

PW를 저장하는 과정에서 Old UNIX에서 발생했던 문제점이 있다.

• H(password) -> /etc/passwd
• World readable
• Bruteforce attack으로 broken

 

이에 Modern UNIX에서는 password salt를 이용해서 이를 방지하였다.

 

Password salt

Modern UNIX는 password를 /etc/password와 /etc/shadow에 저장한다. 기존의 문제를 해결하기 위하여 /etc/shadow는 root만 읽을 수 있게 되었다.

• [r, H(password, r)] -> /etc/shadow
  r : random vector and public

 

사용함으로써 얻게 되는 장점은 다음과 같다.

• Dictionary attack이 어려워진다.
• Single account 공격 cost는 유지된다.
• 2 user가 같은 password를 사용해도 다른 값으로 보인다.

 

Mechanism to defend Dictionary attack & Guessing attack

Multiple failed attempts가 이루어지면 account를 disable하면 된다. Account를 복구하고 싶다면 추가적인 authentication을 수행하도록 구성한다.

 

Login spoofing

가짜 login window를 제작하여 이용자가 ID, PW를 입력하면 그 내용을 가져가는 방법이다.

 

-> Trusted Path로 방지할 수 있다.

Real web과의 연결을 보장하며, non-maskable interrupt이 발생하면 데이터가 spoofed 되는 것을 방지해주는 internet connection이다.

 

Key logging

키보드 입력을 tracking하는 방법이다. Insecure client side에서 발생하는 문제이다.

• SW-based
  Keystroke events, Grab web forms, Analyze HTTP packets
• HW-based
  Connector, Wireless sniffers, Acoustic-based

Anti-spyware, network monitor 등에 의해서 방어할 수 있지만, 일단 system이 감염된다면 해결하기 어려워진다.

 

One time password

Insecure channel에서 비밀번호를 이용하는 방법이다.

 

Lamport ; hash chain

다음의 순서로 진행된다.

• One-time setup
  User가 s, h(), t를 선택해서 server에 전송한다.
  ex) $h^{1000}(s)$
  Server는 이 값을 저장한다.

 

• Authentication
  User는 $h^{999}(s)$ 값을 보낸다.
  Server는 $h(h^{999}(s))==h^{1000}(s)$ 검증한다.
  Server는 다음 authentication을 위해 $h^{999}(s)$ 값을 저장한다.

 

Challenge-response protocol

Server가 user에게 challenge를 전송하면, user는 secret key를 통해서 암호화한 값을 server에 response한다. Challenge는 일회성 난수로 생성되며 매번 다른 값으로 설정된다. 이를 위해서 server와 user는 shared secret key를 가진다.

 

공격자는 response를 스니핑하더라도 다시 사용할 수 없다. 이미 사용된 일회성 값이기 때문이다.

 

Challenge-Response protocols based on symmetic key crypto

Unilateral authentication		Mutual authentication
timestamp-based	nounce-based	nounce-based
A to B : $MAC_k(t_A, s)$	B to A : $r_B$ A to B : $MAC_k(r_B, s)$	B to A : $r_B$ A to B : $r_A$, $MAC_k(r_A, r_B, s)$ B to A : $MAC_k(r_b, r_A)$

 

 

8. OS security and Access control

OS security

Memory protection

Memory access를 control한다. 핵심은 하나의 process가 다른 process의 memory를 access 하지 못하는 것이다. 이를 위해서는 OS와 process가 다른 priviledge를 가져야 한다.

 

CPU modes

Kenel mode라고도 한다. OS의 권한을 의미하며, 자원과 process의 state를 제약 없이 사용 및 조작할 수 있다.

• Execute any instruction
• Access any memory loaction
• Access MMU(memory management unit)
• ...

 

System calls

User mode에서 kernel mode 수준의 작업이 필요한 경우, system call을 사용하여 작업을 해결할 수 있다. System call의 과정은 다음과 같이 진행된다.

System call 과정

1. User mode에서 special CPU inst.를 수행한다. Interrupt이라고도 한다.
   (syscall, 0x80, ...)
2. Store user state & change state form user to kernel
3. Do kernel work
4. Restore user state & return user mode

 

Access control matrix, Principals, subjects, objects

Subject가 Object에 어떤 Right를 가지는 지 정리한 표이다.

• Subject
  Object에 접근하는 entity
• Principal
  Unit of access control and authoriazation
  User account의 보안 수준이라고 보면 된다.
• Object
  Files, Directories, Memory segments 등
  Subject도 object가 될 수 있다. ex) kill

 

Basic concepts of UNIX access control  ; Users, Groups, Files, Processes

• User는 uid를 가진다.
  UID 0 : root
• Subject는 process이다.
• Object는 file이다.
• Group은 principal이 될 수 있다.

 

User는 system에 의해서 여러 principal을 가질 수 있다. 이는 accountability를 보장한다.

 

Permissions

Permission bit ; File

rwx가 있다.

• r : read 가능
• w : write 가능
• x : execute 가능

 

Permission bit ; Directory

File에서와 비슷하지만 조금 다르다.

• r : Directory 내 file name을 보여준다.
• x : Directory 접근이 가능하며, 내부 file을 실행할 수 있다.
• w+x : create, delete, rename이 가능하다.

path에 있는 모든 directory의 permission bit가 x여야 원하는 file에 접근할 수 있다. 

 

ex) Directory r-- 이면?

file name 확인 가능, file 실행은 불가능

 

ex) Directory --x 이면?

file name 확인 불가능, file 실행은 가능

 

ex) access directory/file ?

read : /d1 /d2 /f1

• d1 : --x
• d2 : --x
• f1 : r--

 

write : /d1 /d2 /f1

• d1 : --x
• d2 : --x
• f1 : -wx

 

delete : /d1 /d2 /f1

• d1 : --x
• d2 : -wx
• f1 : 

 

rename : /d1 /d2 /f1

• d1 : --x
• d2 : -wx
• f1 : 

 

suid, sgid, sticky bits

• suid
  set euid, file 소유자의 권한을 줄 수 있다.
• sgid
• sticky
  owner만 directory delete/modify 가능하다.

 

Process user ID model

Principal을 쉽게 관리하기 위하여 process ID를 사용한다. Process는 3개의 user ID와 3개의 group ID를 가진다.

ruid real user ID	process의 owner이다.
euid effective user ID	실제로 접근을 control할 때, 확인하는 ID이다.
suid saved user ID	일시적인 권한 drop을 위해 ruid를 저장한다.
rgid, egid, sgid	group에 대해 같은 id이다.

 

*Process creation과 execution시 어떤 priviledge를 사용할까?

사용가능 후보는 file의 owner와 process의 owner가 있다. 상황에 따라 다르게 설정된다.

• Process → fork()
  부모 process의 uid를 상속한다.
• Process → exec()
  file의 suid가 설정되면, file의 owner의 uid를 euid, suid로 사용한다.
  (suid, set user id)
  그렇지 않으면, process의 uid를 사용한다.

 

suid(sgid) bit의 필요성과 문제점

몇 operation이 user id=0을 요구하기 때문에 필요하다. 또한 file level access control은 충분히 잘 동작하지 않는다. System integrity는 누가 wirte할 수 있는지 관리하는 것 보다는 어떻게 write 되었는 지가 더 중요하기 때문이다.

 

일반적으로 suid = root를 요구한다. 하지만 이는 Least priviledge를 위반하게 된다. 또한 attack의 가능성이 있다. 따라서 이를 관리하기 위하여 euid, effective user id가 사용된다.

 

Changing effective user ID

영구적인 priviledge drop과 일시적인 priviledge drop이 있다. 이에 따라 다르게 설정된다.

• Drop priviledge permanently
  setuid(ruid) = euid
  saveuid(ruid) = suid
• Drop priviledge temporarily
  setuid(ruid) = euid
  saveuid(0, root) = suid
  

 

What happens during Logging In

User가 로그인해서 비밀번호를 변경하는 과정이다.

ruid는 변하지 않는다. Priviledge 변화에는 euid와 suid의 값이 변함을 알 수 있다.

 

 

9. Security Principals

Psychological Acceptability

Negative Authorization?

"특정 group의 member는 접근할 수 없다"

구현할 수 있지만 권장하지 않는다. 관리에 용이하지 않기 때문이다.

 

Complete mediation

모든 access의 authority를 검증한다. 이 과정에서 access control은 외부에 의해서 변하지 않아야 한다.

 

*violated

• OS kernel 감염처럼 Protection scheme이 올바르게 작동하지 않는 경우
• Access control이 bypassed 당하는 경우 (file system 없이 disk 접근 등)

 

Fail-safe defaults

Default configuration : No access allowed

 

어떤 상황에서 access에 permission을 줄 지 결정하는 것이 더 올바른 보안 방법이다. Whitelist나 Fire wall는 대표적인 fail-safe default이다.

 

*violated

Guest account의 high priviledge

 

Least privilege

System의 모든 program과 user는 least priviledge를 가지고 operate한다. 이렇게 함으로써, accident나 error에서 발생하는 피해를 줄일 수 있다.

 

 

10. Secure communication

Symmetric Key aggrement

Needham-Schroeder Shared-key protocol

TTP의 역할을 최소화하고 A와 B 사이의 key 공유를 하는 방법이다.

• Party : A, B, TTP
• Setup :
  $k_{A, T}$ for A, TTP
  $k_{B, T}$ for B, TTP
• Goal :
  Mutual entity authentication이 목표이다.
  (Key establishment)
  이 과정에서 TTP의 역할은 최소화한다.
  (가령 T는 stateless이다.)
• Method
  A→T : $ID_A$, $ID_B$, $N_1$
              A의 아이디, B의 아이디, 임시값1(random)
  T→A : $Ek_{A,T}[N_1 || ID_B || k_{A,B} || Ek_{B,T}[k_{A,B} || ID_A]]$
              $k_{A,B}$ : A와 B 사이의 session key
  A→B : $Ek_{B,T}[k_{A,B} || A]$
  B→A : $Ek_{A,B}[N_2]$
              $N_2$ : 임시값2
  A→B : $Ek_{A,B}[N_2 - 1]$

 

Attacks on Needham-Schroeder

Old session key 탈취에 매우 취약하다. 공격자는 이 값을 reuse해서 fresh처럼 B에게 전송하면, A인척 할 수 있다. 방법은 3번째부터 수행하면 된다.

 

C→B : $Ek_{B,T}[k || A]$

B→C : $Ek_{A, B}[N_B]$

C→B : $Ek_{A, B}[N_B -1]$

 

B의 입장에서는 A와 대화하고 있는 것처럼 느끼게 된다. 이를 방지하기 위해서 N은 random으로 생성한다. 이렇게 하면, $N_B$를 받는 A의 경우, $N_B$ history와 비교해서 fresh하면 B를 믿으면 된다. 대표적으로는 timestamp를 이용한다.

 

Kerberos

MIT에서 개발한 Network authentication protocol이다.

• Needham-Schroeder protocol 기반이다.
• Authentication과 Secure communication을 제공해준다.
• Symmetic cryptography이다.

 

Needham-Schroeder에서의 문제점은 새로운 서비를 이용할 때마다 $k_{A,T}$를 사용하는 것이다. Kerberos는 TTP를 AS, TGS로 분리함으로써 이를 해결한다.

 

그 전에 간단하게 용어를 살피고 간다.

• AS : authentication server
• SS : service server
• TGS : ticket granting server
• TGT : ticket granting ticket

 

Kerberos의 통신 성립 과정은 다음과 같다.

Kerberos의 클라이언트가 서비스를 이용하기 위한 통신 과정이다.

클라이언트는 long-term shared secret key를 이용해서 AS에 인증하고 TGT를 받는다. 클라이언트는 TGT로 TGS에 인증하여 SS 접근에 필요한 ticket을 받는다.

 

Kerberos protocol

구체적으로는 다음과 같다.

 

*로그인하는 경우

클라이언트는 AS로부터 TGT를 받는다.

 

*서비스를 사용할 때마다 한번씩

클라이언트는 TGS로부터 SS ticket을 받는다.

 

*서비스 session마다 한번식

세션마다 서비스와 클라이언트는 인증을 해야한다. 클라이언트는 SS ticket으로 서비스를 사용할 수 있다.

 

Kerberos drawback

• TGS에 대한 의존도가 높다.
  = Single point of failure
• Tight clock synchronization에 의존한다.
• 주로 Organazation 내부에서 유용하다.

 

+$\alpha$ : Kerberos v4의 경우 DES 하나만 사용하고 IP 주소만 사용하는 등의 단점이 있었지만, v5로 넘어오면서 해결되었다.

 

Public Key certificate

X.509

인증서의 형식을 정의하는 X.500의 인증 프레임워크가 X.509이다.

• Public Key Infrastructure, PKI 프레임워크
• Public Key와 ID 정보가 인증서에 포함된다.
• 인증서는 CA에 의해서 발행된다.
• 주로 SSL, IPSec, SET에 쓰인다.

 

CA

인증서는 CA의 서명이 있어야 신뢰가능하다. 그런데 CA가 모든 인증서를 관리하는 것은 현실적으로 불가능하다. 따라서 계층구조적 관리가 들어간다.

 

계층 구조의 CA

User1과 User4가 서로 인증하려고 하면,

• User1 : root CA 가지고 있음
  User4 → User1 : CA<<CA3>>, CA3<<User4 public key>>
  (CA에서 발행한 CA3 인증서는 CA<<CA3>>라고 표현한다.)
• User1 : 가지고 있는 CA로 CA<<CA3>> 인증서 검증
              CA<<CA3>>에서 CA3 추출
              추출한 CA3로 CA3<<User4>> 인증서 검증
              CA3<<User4 ID>>에서 User4의 public key 추출

 

How to obtain a certificate

2가지 방법이 있다.

• Self-signed certificate
  (unlikely to be accepted by others)
• CA vendors에게 인증서 받기
  과정은 다음과 같다.
  • Generate private key
  • Generate Certificate Signing Request, CSR
  • Send CSR to CA
  • CA sends signed certificate to requestor

 

Authenticated Diffie-Hellman

DH도 인증서와 함께 사용할 수 있다.

 

SSL/TLS

Secure Socket Layer, SSL이라는 이름이었던 Web security를 위한 protocol이다. 데이터 전송 시에 평문이 아니라 암호문을 전송한다. 개인정보 보호에 따라서 SSL은 필수로 사용된다.

 

SSL은 크게 Session과 Connection으로 나뉜다.

• Session : 두 서버의 관계
• Connection : 연결 방법

 

보안 세션은 Handshake protocol에 의해 생성된다.

• Public key cryptography를 이용해 shared secret key를 생성한다.
• 서버에서 클라이언트 인증을 위해 signed certification을 사용한다.

Record Layer도 존재한다.

• 데이터는 negotiated key, encryption function에 의해 전송된다.

Handshake 과정이다.

 

Usage of SSL/TLS

TLS는 Application layer와 Transport layer 사이에 위치한다. HTTP, SMTP 등을 보호한다.

사용 예시는 다음과 같다.

• Public key와 인증서를 이용해 서버를 인증할 수 있다.
• Client와 Server는 cipher suite를 협상해서 결정한다.
  • Key exchange algorithm ; RSA, Diffie-Hellman, ...
  • Encryption algorithm ; RC4, DES, AES, ...
  • MAC algorithm ; HMAC-MD5, HMC-SHA1, ...

 

Real world problem

• Heartbeated SW bug in OpenSSL
• SSL 인증서 validation 오류
• Non-random private key in RSA, n=pq
  (종종 같은 prime으로 생성됨)
• Pre-computation으로 TLS에서 Diffie-Hellman을 break할 수 있다.

 

HTTPS

Indicator를 통해서 TLS가 동작하고 있는 것을 확인할 수 있다. Phishing attack 등을 방지할 수 있다.

 

하지만 여전히 security 문제는 존재한다.

• 일반 사람들은 잘 모름
• 일반 사람들은 잘 확인 안함
• 브라우저가 취약한 경우, 이상한 indicator로 바뀜
• 저장된 인증서의 권한 정보가 변하는 경우

 

 

11. Web security

Web browser

브라우저의 request에 네트워크는 reply로 반응한다.

Reply에는 response page 뿐만 아니라, code도 포함될 수 있다. Attack에 사용될 여지는 충분하다.

 

Browser as OS

유저는 여러 웹 사이트를 방문하게 된다. 브라우저는 여러 domain에서 web page를 불러오게 된다. 이 과정에서 untrusted entity의 program을 실행하게 되는데, 이런 code는 위험성이 높다. 또한 이런 domain으로부터 생성 및 유지되는 쿠키도 공격에 사용될 여지가 충분하다.

 

브라우저는 다음의 대안을 사용하고 있다.

 

→ 브라우저는 sandbox(제한)로 스크립트가 local resource에 접근하지 못하도록 막는다.

→ 브라우저는 security policy를 사용한다.

     브라우저가 유지하는 resource의 관리 및 보호, untrusted script간의 separation이 가능해진다.

 

Cookie

Website가 name-value pair를 생성해서 브라우저에게 전달하면, 브라우저는 해당 정보를 컴퓨터에 저장한다. 저장된 정보를 쿠키라고 하며, 브라우저는 매 request마다 쿠키를 함께 보내, 자신을 인증한다. 자신을 인증한다는 것은 자신의 상태(인증된 상태)를 쿠키게 저장한다는 것을 의미하기도 한다.

 

HTTP : stateless

Cookie : state

 

쿠키 정보에는 여러 정보가 포함되며, 다소 민감한 정보도 포함된다. 대신 인증과정이나 상태가 유지됨으로 편리성이 증가한다. 구체적으로 포함되는 정보는 다음과 같다.

• Name : session_token
• Content : "abasdjklxcnv09i3qrjdfklms..."
• Domain : .dgist.ac.kr
• Path : /
• Send For : Any type of connection
• Expires : Mon, Sep 08, 2043 7:23:14 PM

 

쿠키는 보통 authentication, tracking, maintaining special information of user를 위해 사용된다. 민감한 정보가 포함되지만, 쿠키는 오직 쿠키를 생성한 website만 읽을 수 있다.

 

Web authentication via Cookies

HTTP는 stateless로 로그인 기록을 저장할 수 없지만, 쿠키를 사용하면 가능하다. 과정은 다음과 같다.

• 유저가 성공적으로 인증되면 서버는 authenticator를 생성하여 쿠키로 사용한다.
  (ex. access token)
• 클라이언트는 쿠키를 위조할 수 없다.
• 브라우저는 매 request마다 쿠키를 함께 보낸다.
• 서버는 쿠키를 보고 사용자를 인증한다.

 

A typical session with Cookies

클라이언트는 쿠키를 위조할 수 없으며 쿠키는 장기간이나 세션 단위로 유지된다. 어떻게 위조가 안되고 tamper-proof하게 만들 수 있을까?

 

이후 내용이 위 질문에 대한 답이다.

• Cross Site Scripting
• Cross Site Request Forgery
• SQL Injection

 

Sandbox

Separating / Limitating running program

 

Program이 요구하는 resource를 명확하게 파악하고 그 외 resource의 접근은 제한한다. 다음의 방법으로 구현이 가능하다.

• OS-level virtualization
• VIrtual Machine monitor
• Java applets

 

Same Origin Policy

브라우저의 가장 기초적인 security model이다. 다른 origin에서 받은 스크립트나 resource를 격리시키는 정책이다.

 

ex) digist.ac.kr의 스크립트는 kaist.ac.kr resource에 접근하지 못한다.

 

쉽게 말해, Origin이 security principal이 된다. Origin의 구성요소는 다음과 같다.

• Scheme (protocol)
• Host (domain)
• Port

 

3가지가 모두 같아야 SOP를 만족한다. 같은 SOP에서는 다음의 작업이 가능하다.

• 브라우저 윈도우 조작
• XmlHttpRequest로 URL 요청 가능
• frame 조작
• document 조작
• cookie 조작

 

Problems with SOP

• 일부 오래된 브라우저에서는 잘 동작하지 않는다.
• 웹 페이지가 unrelated하지만, SOP에 의해 서로 접근이 가능한 경우 문제가 된다.
  • naver.com/account/
  • naver.com/other account/
• Usability 측면 ; cross-origin resource 공유가 필요하지만, SOP에 의해 제한된다.

 

Cross-Site Scripting, XSS

스크립트를 이용해 공격하는 방법이다. 일부 application은 유저의 input을 web page의 part로서 사용하기 때문에 가능한 공격이다. 공격과정은 다음과 같다.

• Web page 내부 스크립트가 브라우저에 의해 실행
• 스크립트로 쿠키 접근이 가능
  → 개인정보 유출
• 스크립트로 DOM object 조작 가능
  → 유저가 보는 화면 조작(링크 변경)

 

XSS on Blog

댓글로 공격을 수행한다.

• 공격자가 malicious comment를 스크립트 형식으로 작성하여 댓글 작성
  (local authentication 인증서를 읽고 이를 공격자에게 보내는 코드)
• Blog post를 보는 사람은 local authentication 쿠키를 가지고 있을 수 있음
• 브라우저는 악성코드를 확인하지만, 종종 실패함
• 브라우저에 버그가 있으면, 공격 성공

 

Effect of XSS attack

공격자가 임의의 스크립트를 실행할 수 있게 된다. 

• DOM object 조작
  링크 바꾸기
  form으로 pw를 치면, 사이트로 연결해줌(pw 탈취)
• Other user 감염
  Domain 감염 → 접속하는 user 감염

 

XSS attack ; MySpace.com

유저는 HTML을 포스팅할 수 있었다. 대신 MySpace에서는 <script>, <body>, <a href=javascript://>, onclick을 포함하지 않아야 HTML 포스팅을 할 수 있다.

 

그러나 공격자들은 CSS tag에 javascript 코드를 포함시켜 XSS 공격을 수행하였다.

<div style="background:url('javascript: alert(1)')"/>

 

대표적으로 Samy worm 공격이 수행되었다. MySpace 페이지에 접속하면 Samy를 친구로 추가하는 공격이었다. Samy는 24시간 내 수백만의 친구가 생겼다.(오?)

 

PHP, avoiding XSS bugs

Input을 확인하는 것은 어려운 일이다. HTML에 스크립트를 삽입하는 방법은 매우 다양하기 때문이다. 대신 PHP는 유저로부터 input을 preprocessing하는 방법으로 확인한다.

 

PHP, Hypertext Preprocessor : htmlspercialchars(string)

• &   → &amp;
• "    → &quat;
• '    → &#039;
• <   → &lt;
• >   → &gt;   

 

htmlspercialchars("<a herf='test'>TEST<a>")

→ &lt;a href=&#039...

 

ASP.NET, avoiding XSS bugs

• PHP처럼 Server.HtmlEncode(string) 함수를 이용해 HTML을 인코딩한다.
• validateRequest를 통해서 HTML을 확인한다.
  • POST에 <script>가 있으면 동작을 안한다.
  • Hardcoded list의 패턴을 참고해 검사한다.
  • Disabled 가능하다.
    <%@ Page validateRequest="false" %>

 

Cross Site Request Forgery, CSRF

One click attack, Session riding으로도 알려져 있다.

 

Authentication에 session cookie만 사용하는 web applciation을 타깃으로 공격한다. 공격자는 유저의 쿠키 정보를 가지고 다른 웹 어플리케이션에 유저의 인증으로 명령어를 전송하는 공격이다.

 

이 공격이 가능한 이유는 브라우저가 도메인 X에 의해 설정된 쿠키를 도메인 X로 보내지는 요청에 첨부하기 때문이다. 예를 들어서, X 사이트에서 Instagram으로 redirect해주는 경우, 이미 로그인 되어 있으면, 브라우저가 쿠키를 함께 보내준다.

 

CSRF

공격 예시를 들어보자면 다음과 같다.

• 유저가 Youtube에 로그인하고 로그아웃하는 것을 까먹는다.
• Session 쿠키가 브라우저에 남아있는다. 다른 웹 사이트에 방문하는 경우, 다음처럼 보내진다.
  
  <from name=F action=https://www.youtube.com/name.php method=POST>
     <input type=hidden name=email value=name@gmail.com> ...
  <script> document.F.submit(); </script>
  
  
• Malicious 웹 페이지는 유튜브에 HTTP request를 보낸다.
• 브라우저는 session 쿠키를 함께 보내준다.
• 유튜브는 request를 수행해준다.

 

브라우저는 누가 request를 보내는지 알 방도가 없다.

 

Prevention

서버 측면에서, 유저 측면에서 예방할 수 있다.

Server side	User side
Cookie랑 hidden value로 같이 authentication 수행하기  - hidden value는 예측 불가능, user-specific  - 위조하기 위해서는 hidden value를 예측해야 함 Cookie를 포함하기 위해서는 POST request의 body가 필요함  - 브라우저는 자동으로 쿠키를 보내지 않음  - Malicious는 쿠키를 추가해야 함  - 하지만 malicious는 SOP에 의해서 body에 접근할 수 없음	로그아웃 하기 Request에 session 쿠키를 선택적으로 보내기  - script code에 의한 request에는 쿠키를 보내지 않기