네트워크 보안 - 기본 개념 Summary

1. Security Requirements

   Confidentiality

   Data Integrity

   Availability

   User Authentication

   Non-repudiation

2. Details of Theory of Secure Communication

   1. Condition of Perfect Secrecy

   • P(M|C) = P(C|M)P(M) / P(C)

     P(M|C) = prob. of message M given C intercepted

     P(C|M) = prob. of cipher text C generated by M

     P(M) = prob. of M being selected

     P(C) = prob. of obtaining C

   • Necessary and Sufficient Condition for Perfect Secrecy for all C and all M

     P(M|C) = P(M)

     P(C|M) = P(C)

     → C, M is totally not related.

   1. Shannon Entropy

   • Message Entropy

     Amount of information produced when a message is chosen

      

   • Key Entropy

     Amount of information produced when a key is chosen

      

   The amount of uncertainty introduced into the system cannot be greater than than the key uncertainty.

   Message information can be perfectly concealed if the key uncertainty is at least the message uncertainty.

   log n : occurs when all messages are equally probable

   1. Equivocation

   Conditional entropies of the key K and message M

    

   H(K, N|C) is a non-increasing function of N

   → It is theoretically easier to determine the key as more cipher text is intercepted.

   1. Mutual Information

   I(M|C) represent the amount of information revealed about M given C

   I(K|C) represent the amount of information revealed about K given C

   "New Information Revealed Knowing Something"

   = "Uncertainty" - "Uncertainty after Knowing Something"

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

   Perfect Secrecy Condition

   (1) I(M|C) = 0 → H(M) = H(M|C)

   (2) H(M) ≤ H(K)

   If H(K) is small, Cryptanalyst can obtain a lot of info about the plaintext.

   Longer Message = Lower Entropy

   1. Redundancy

   2. Unicity Distance

   The length of an original cipher text needed to break the cipher by reducing the number of spurious keys to zero.

    

   • Unicity Distance of DES

     H(K) = 56bit, D = 3.2bit/letter

     N = H(K) / D = 56 / 3.2 = 17.5 letters

3. Complexity Theory

• Polynomial Time Problem (P)

  If a problem can be solved in polynomial time, it is not considered cryptographically strong.

• Non-Deterministic Polynomial (NP)

  Solvable in polynomial time on a non-deterministic machine

  Example : Knapsack problem, discrete logarithm problem, integer factorization problem

• PSPACE

  Some problems can be solved with polynomial space but not polynomial time

  Harder than NP Problem

1. Multiplicative Inverse Modulo

1. using Extended Euclidean Algorithm

2. Euler Totient Function

• 𝝋(𝒏) = (p-1)(q-1)

  p, q is prime number

Ex. 𝝋(10) = 𝝋(2 x 5) = (2-1)(5-1) = 4

1. Fermat's Little Theorem

 

where p is prime and gcd(a, p) = 1.

i.e a, p are relatively prime

1. Euler's Theorem

 

1. Chinese Remainder Theorem

• If n is composite with factors

  n = d1 x d2 x ... x dt

• and di's are pairwise relatively prime there exists a common solution x such that

  (x mod di) = xi for i = 1, 2, ... , t

   

5. IPSec Protocols

1. IPSec Provides the following:

• Data origin authentication
• Data content confidentiality
• Connectionless data integrity
• Anti-Replay Protection
• Limited traffic flow confidentiality

1. IPSec Protocols

• Authentication Header (AH)

  Data Authentication, Connectionless Data Integrity 제공

  Anti-Replay Protection, Non-Repudiation

  (중요) Confidentiality를 제공하지 않는다.

• Encapsulating Security Payload (ESP)

  Proof of Data origin, Data Integrity

  Anti-Replay Protection

  Data Confidentiality and Limited traffic flow confidentiality

• Modes of Operation : Transport Mode, Tunnel Mode

1. Transport Mode

Usage : Protect Upper Layer Protocols

Communication Endpoints must be cryptographic endpoints

IP 패킷의 Payload를 보호하는 모드로써 IP의 상위 프로토콜 데이터를 보호하는 모드이다.

IP Packet의 Payload만 IPsec으로 캡슐화하고 IP Header는 그대로 유지하므로 네트워크 상 패킷 전송에 문제가 발생하지 않는다.

IP Header를 보호하지 않으므로 Traffic Flow가 분석될 수 있다.

 

보호 구간

일반적으로 End-Point 구간의 IP Packet 보호를 위해 사용한다.

1. Tunnel Mode

Usage : Protect Entire IP Datagram

IP 패킷 전체를 IPSec으로 캡슐화하여 IP Header를 식별할 수 없기 때문에 네트워크 상 패킷 전송이 불가능하다. 따라서 전송 구간 주소 정보를 담은 New IP Header를 추가한다.

 

1. IPSec Protocols (Modes)

• Transport Mode with AH (Authentication Header)
• Tunnel Mode with AH (Authentication Header)
• Transport Mode with ESP (Encapsulating Security Payload)
• Tunnel Mode with ESP (Encapsulating Security Payload)

1. AH (Authentication Header) Format

 

Next Header (8 bits)

Identifies the type of header immediately following this head

Payload Length(8 bits)

Length of Authentication Header in 32-bit words

Reserved (16 bits)

For future use.

Security Parameter Index (SPI) 32 bits

identifies a security association

Sequence Number 32 bits

A monotonically increasing counter value (Anti-Replay Protection)

Authentication Data (Variable) ICV(Integrity Check value) or MAC(Message Authentication Code)

1. ESP (Encapsulating Security Payload)

• Provides

  Confidentiality (AH do not provides)

  Authentication

  Limited Traffic Flow Confidentiality (in tunnel mode only)

  Anti-Replay Protection

1. ESP Transport Mode

IP Payload와 ESP Trailer를 암호화하고 암호화된 데이터와 ESP Header를 인증한다.

 

1. ESP Tunnel Mode

Original IP Packet 전체와 ESP Trailer를 암호화하고 암호화된 데이터와 ESP 헤더를 인증한다.

 

ESP 헤더는 암호화가 되지 않으며 ESP 트레일러는 보통 암호화된다.

1. ESP Header Format

 

Security Parameters Index (32 bits)

• Identifies Security Association

Sequence Number (32 bits)

• Anti-Replay Protection
• A monotonically increasing counter value, same as in AH

Payload Data (Variable)

Padding (0-255 bytes)

• For encryption and others

Pad Length (8 bits)

• Indicating the number of pad bytes

Next Header (8 bits)

• Identifies the type of data contained in the payload data field by identifying the first header in that payload.

Authentication Data (Variable)

• ICV computed over the ESP

(Cheat Sheet) IPSec Summary

1. IPSec Packet Send/Receive Architecture

11-1) 송신 절차

• 전송할 패킷에 대하여 SPD 검색

• SPD 에 일치하는 Entry가 없으면 패킷을 폐기하고 있으면 첫 번째 Entry의 정책에 따라 처리

  • Discard : 패킷 삭제
  • ByPass : 패킷 송신
  • Protect : 보안 연관 데이터베이스를 검색

• SAD에 일치하는 Entry가 있으면 IPSec 처리를 수행한 후 전송하며 없으면 IKE (Internet Key Exchange) 과정을 수행하여 SA(Security Association)를 생성하는 과정을 수행

  11-2) 수신 절차

• IP Protocol의 protocol 필드를 조사하여 보호되지 않는 IP 패킷인지 IPSec (AH/ESP) 패킷인지 확인

• 보호되지 않는 IP Packet이라면 SPD를 검색하여 첫 번째 일치하는 엔트리가 Bypass이면 상위계층으로 전달, Discard면 패킷을 삭제한다.

• IPSec Packet이라면 SAD를 검색하여 일치하는 Entry가 없으면 패킷을 삭제하고 있으면 IPSec 처리를 수행한 후 상위 계층으로 전달한다.

1. Benefits of Using IPSec

• IPSec can be transparent to end users
• No need to train users on security mechanism
• Provide security for individual application
• applied to only one specified application

6. SSL (Secure Socket Layer)

Transport Layer Security Service

Uses TCP to provide a reliable end-to-end service

 

1. SSL Record Protocol : Services

• Message Integrity

  MAC (Message Authentication Code) with shared secret key

  Similar to HMAC but with different padding

• Confidentiality

  Symmetric Encryption with shared secret key defined by Handshake Protocol

  Message Compressed before encryption

  → Why? (시험에 나올 수 있음)

  → Encryption after compression strengthens the encryption, since compression reduces redundancy in the message.

1. SSL Record Protocol : Operation

• Data Fragmentation
• After Compression Insert MAC (Message Authentication Code)
• Encryption
• Append Record Header in front of the encrypted data

1. SSL Handshake Protocol

 

1. SSL Change Cipher Spec Protocol

• Updating the cipher suite in use
• A single message causes pending state to become current

1. SSL Alert Protocol

• Warning : Connection or security may be unstable
• Fatal : Connection or security may be compromised, or an unrecoverable error has occurred

1. TLS Minor difference to SSL

• HMAC for MAC
• Additional Alert Codes
• Record Format Version Number

7. Firewall

1) What is a Firewall

Isolates organization's internal net allowing some packets to pass, blocking others

2) What can Firewall do

• Define Single Choke point
• IP Spoofing, Routing Attack에 대한 방어
• Penetration에 대한 immune (면역이 있어야 한다)

3) What cannot Firewall do

• Firewall를 Bypass하는 공격은 못 막는다.
• Internal Thread는 못 막는다.
• 바이러스에 감염된 파일이나 프로그램의 전송을 못 막는다.

4) Stateful Packet Filtering vs. Stateless Packet Filtering (매우 중요)

• Stateful Packet Filter

  Track status of every TCP Connection

  Augmented ACL : indicate check connection

  Modern Method

• Stateless Packet Filter

  Admit packets that "make no sense", even though no TCP Connection established.

  OLD, Not used usually

1. Intruders

1. **(Cheat Sheet)**Classes of Intruders

• Masquerader : Individual who is not authorized to use the computer (Outsider)
• Misfeasor : Legitimate user who accessed unauthorized data, programs, or resources (Insider)
• Clandestine User : An individual who seizes supervisory control of the system and uses this control to evade auditing and access controls or to suppress audit collection (either)

1. IDS (Intrusion Detection System)

1) Rule-based Detection

• Anomaly Detection (previous usage patterns)
• Penetration Identification (suspicious behavior)
• False Positive(오탐률) 낮음

2) Statistical Anomaly Detection

• Threshold
• Profile Based
• False Positive(오탐률) 높음

10. Honeypots

Decoy systems to lure potential attackers to...

공격자를 유인한다.

1. Virus - Self-replicating code (자가복제), attach itself to a program

2. Worm - Replicating but not infecting program (does not attach itself to a program)

• used by hackers to create zombie pc etc.
• Morris Worm (1988) - Targeted Unix System

1. Kerberos Authentication Protocol

1. Kerberos Version 4

• Problem

  • Lifetime of the ticket-granting ticket (TGT)

    • Too Short → Repeatedly asked for password

    • Too Long → Greater opportunity to replay

      Adversary can steal the ticket and use it before the expiration

• Authentication Dialogue

   

1. Kerberos: Realms, Multiple Kerberos

• A Kerberos Realm
  • Clients, Kerberos Server, App. Server
  • Share same Kerberos database
• Server Database Contains
  • User ID + Hashed Passwords
  • Shared Secret Key with each app. server
• Inter-Realm Authentication
  • Kerberos servers share a secret key

1. Kerberos Version 5

• Improvements over version 4

(Cheat Sheet) Improvements over v4

14. PGP (Pretty Good Privacy)

1) PGP: Services

• Security Requirements : Non-Repudiation, Authentication, Confidentiality
• Compression: ZIP
• Compatibility

2) PGP 기밀성과 인증 과정

• 송신자가 메시지를 생성한다
• Hash Function을 통해 M의 해시 값을 생성하고 송신자의 개인키로 RSA를 이용하여 암호화
• 암호화된 값을 M에 덧붙이고 ZIP 압축
• 세션키를 이용해 압축된 메시지를 암호화(1)
• 수신자의 공개키를 이용해 세션키를 암호화(2)
• (1)과 (2)의 메시지를 결합하여 수신자에게 전송
• 수신자는 메시지를 받으면 암호화된 키 부분과 암호화된 메시지 부분을 분리
• 수신자는 자신의 개인키를 이용해 암호화된 세션키를 복호화
• 세션키를 이용해 암호화된 메시지를 복호화
• 메시지의 ZIP 압축을 푼다.
• 전자 서명 부분을 분리하여 송신자의 공개키로 복호화 (3)
• Hash Function을 통해 메시지 부분의 해시 값을 얻는다. (4)
• (3)과 (4)를 비교하여 동일하면 메시지가 인증된다.

1. PGP : Email Compression

• Why Compress : Reduce size, Reduce Redundancy
• Placement of Compression : 압축을 하고 암호화를 하면 보안효과가 커진다.

15. Secret Sharing

1) Threshold Scheme

• Definition

  (t, n) t ≤ n

  t명의 participant들이 secret을 결정할 수 있다.

  t명보다 적은 수의 participant들은 secret을 얻을 수 없다.

1. (n, n) - Threshold Scheme

• Given : Secret (binary string s of w bits)

• Compute Shares (s1, ..., Sn):

   

• Distribute Si to Pi

• Recover the Secret

   

1. (2, n) - Threshold Scheme

• Linear Function (일차 함수)
• 함수의 그래프와 x값 0에 대한 y축 값을 구할 수 있다.

1. (3, n) - Threshold Scheme

• 이차 함수
• 3 점을 지나는 삼각함수의 식을 만들고 그린 후 x 좌표 0에 해당하는 y 값을 구할 수 있다.

1. (t, n) - Threshold Scheme

• (t -1) degree polynomial 식을 구할 수 있다. (t-1 차 함수)

1. Blakley's Scheme

• 2개의 선이 만나면 한 점이 생긴다. (Two nonparallel lines)
• 3개의 평면이 만나면 한 점이 생긴다. (Three nonparallel planes)

1. Shamir's (t, n) - Threshold Scheme

Example. Multi-Level Structure

(President has 3 shares, prime minister has 2, other have 1)

By using a (3, n)-threshold scheme

Secret can be recovered by

(1) The president, or

(2) The prime minister and another minister, or

(3) Any three ministers

1. ElGamal (n, n)-Threshold Scheme

 

1. EIGamal (t, n)-Threshold Scheme

10) Secret Sharing Using CRT

Q. Is the secret sharing scheme using CRT a (4, 4) - threshold scheme?

A. No. (Not good Scheme)

Because, each share gives information of the secret.

search space를 줄이기 때문이다.

(2019. 12. 17. 깜지 시작 부분)

1. Millionaire Problem 백만장자 문제

“Alice and Bob are two millionaires who want to find out which is richer without revealing the precise amount of their wealth"

Answer : ?

12) Solving Millionaire Problem

Alice가 3을 가지고 있고 Bob이 6을 가지고 있다고 가정해보자.

A = {A1, A2, ...} B = {B1, B2, ...}

Public c1, c2, c3, ..., c7, c8

Initialization

• Alice establishes the RSA public key (n, e) and keeps private key d
• Two public sets A and B are available to both parties.

Step 1.

Compute and publish c1, c2, ..., c8

 

Step 2.

Bob computes and sends u to Alice.

 

Step 3.

Alice computes and sends back v to Bob

 

Step 4.

Recover B6

 

13) Socialist Millionaire Problem

Alice와 Bob이 서로 같은 값을 가지고 있는데 이를 드러내지 않고 같다는 것을 알아내고 싶을 경우에 사용

Step 1. g2, g3

 

Step 2. Share P, Q

 

Step 3. Verify

 

1. DES Block = 64 bits, Key = 56 bits

Generating Keys : Initial Key Permutation, Key round scheduling

Steps : Initial Permutation (IP), 16 rounds of Feistel Cipher, Final Permutation (IP^-1)

• Expansion (E-Box)
• Key mixing (XOR)
• Substitution (S-Box) - Confusion
• Permutation (P-Box) - Diffusion

1. Cracking DES

• Differential Cryptanalysis - Chosen Plaintext Attack
• Linear Cryptanalysis - Known Plaintext Attack

1. AES

• Stage 1. SubBytes
• Stage 2. ShiftRows
• Stage 3. MixColumns
• Stage 4. AddRoundKey

Q. Why is AES stronger than DES?

Longer encryption key and block sizes in AES

DES : Balanced Feistel Structure

AES uses substitution-permutation steps (good running time)

DES : 56 bit / AES : 128 / 192 / 256 bits

1. RSA

Disadvantages of Symmetric Cryptography

n = 1000

(1000 * 999) / 2 = 499500 키의 관리가 매우 어려워진다.

1. RSA Cryptosystem

p and q are large primes

n = pq

𝝋(n) = (p - 1)(q - 1)

e is an integer, 1 < e < 𝝋(n), gcd(e, 𝝋(n)) = 1

d is an integer, 1 < d < 𝝋(n), ed = 1(mod 𝝋(n))

public key = (n, e)

private key = (n, d)

 

1. The difference value |p - q| should be large

2. guard your 𝝋(n)

3. The padding is required in RSA

The receiver cannot identify the recovered mr is correct or not.

1. RSA Digital Signature

 

Why is the hash function used?

• To reduce size
• To improve security

19. Diffie-Hellman Key Exchange

 

g^xy mod p → Shared Secret Key

1. Preventing the Man-in-the-Middle Attack

• User Authentication prior to the key exchange
• Station-to-Station protocol

1. ElGamal Public Key System

1. Limitation of RSA: Slow Decryption

public key가 작으면 private key d는 커야 한다.

RSA is Not-Semantic Secure under Chosen Plaintext Attack

1. EIGamal Cryptosystem

 

1. Encryption and Decryption

• Encryption

Generate public key Y using (g, x) : Y = g^x mod p

chosen random number : k (1, p - 1)

K = Y^k mod p

Encrypt Message M

C = (C1, C2)

C1 = g^k mod p, C2 = M X K mod p

• Decryption

Compute K using the private key x on C1

C1^x = K mod p

M = C2 / (K mod p)

1. ElGamal Cryptosystem is Semantic Secure under Chosen Plaintext Attack

2. Padding is required

With the padding, the receiver can detect whether the message has been modified during the transmission.

1. How to encrypt a long message

Block 단위로 나눠서 암호화를 한다. 각 Block은 각기 다른 랜덤 넘버를 사용한다.

Each block should use different random number k.

Why? M이 찾아지면 다른 M도 찾아지고 Key가 필요 없어진다.

1. Elliptic Curve Cryptography

• Public Key Encryption
• Based on : Elliptic Curve Theory, Discrete Logarithm Problem

1. Elliptic Curve

• Given any two points on the curve, the line drawn through them intersect the curve at exactly one point (dot operation)
• We can repeat the dot operation n times to arrive at a final point.
• Finding n when only knowing the final point is HARD.

1. Security of ECC depends on...

• Ability to compute a point multiplication
• Inability to compute the multiplicand (n) - how many times operation given the original base point.
• Private Key : n, Public Key : based point dotted after n times.

1. Elliptic Curve Implementation Issue

• Usually a prime number is chosen as the maximum. → Prime Elliptic Curve

1. Elliptic Curve Cryptography (ECC)

 

a, b : Two coefficient which defines the shape of the curve

p : Prime number which define the max (boundary)

G : generator coordinate(base point) which defines the start of the curve

n : order of point G (스칼라 곱을 통해 얻어진 각각 다른 점들의 개수)

#E : number of points of the elliptic curve

h : cofactor of the curve (h = #E / n)

1. Point Doubling (2P = P + P)

 

1. Scalar Point Multiplication : Double and Add Algorithm

example)

151(10) = 10010111(2)

151 = 2^7P + 2^4P + 2^2P + 2^1P + 2^0P

Double 2P = 2^2P

Double 2^2P = 2^3P

...

Double 2^6P = 2^7P

Double할 수록 2를 곱하는 것과 같으므로 7번 Double 연산을 수행한 후 다 더하면 된다.

1. ECC vs. RSA

• ECC는 보내야 할 데이터의 양이 줄어든다. (light weight)
• ECC는 Discrete Logarithm 문제 기반으로 동일 길이의 키를 기준으로 RSA보다 Challenge 하기가 훨씬 더 어렵다.
• 양자 컴퓨터에 의해 NP문제를 빠르게 해결할 수 있는 효율적인 알고리즘의 존재 때문에 RSA보다 해독하기 힘들다.

1. Blind Signature

• Q : How to verify the message without publically revealing the message content?
• A : Blind Signature
• Message is blinded before it is signed.
  • Then it can be publicly verify the original unblinded message.
  • Blinding Factor + Public key signature (RSA, DSA)

1. Architectrue

 

1. Blind Signature

• (1) [Message] : the blinded message

• (2) Signature on [Message] : the blind signature

• (3) Signature on Message : to be obtained after unblinding

• Unlinkability : It is intractable for the signer to link (3) to (2). Should NOT be linked.

1. Blind Signature : RSA

RSA : Public Key (n, e) , Private Key (d)

Signing : s = H(m)^d mod n ← Original Signature

Verifying : H(m) = s^e mod n

• Blind Signature Generation : (r = "blinding factor")

   

1. E-Cash → Untraceability

• Bank cannot trace an e-cash to the withdrawing protocol

1. The database will unlimitedly grow.

→ Keep tracking the cash.