Cryptography(2) - Stream cipher & Block cipher

• Random generators – stream ciphers
  연속적 input → 연속적 out
• Random permutations – block ciphers
  고정 input ←(keyed-invertible function)→ 고정 output

Random bit generation

Computing environment(library)에서 random값 생성 → seed값을 기반으로하기 때문에 특정 분포를 가진다.

 

⇒ Randomness sources (High resolution/noise/time)

혼자서는 unbiased random bit이지만 Hash function을 사용하여 accumulated entropy를 이용하는 것이 좋다!

• Hardware random bit generators (noise)
• Linux의 /dev/random device driver - pseudo random bit stream generator(entropy pool)
• User behaviour timing (key strokes, mouse 움직임)
• Hardware response times (timing - disk drives)
• noise from converter / network packet timing

Stream Cipher Example : RC4

일정 규칙에 따라 stream bit 생성 → Keystream bytes를 one-time pad처럼 사용한다.

• Lookup table → (0~255)까지 byte값들의 permutation 포함
• Key를 이용해 permutation 초기화 → 각 step마다 (현재 lookup table의 원소들 교환) & (table로부터 keystream byte 선택)
• 각 step마다 byte 생성

• S[] = lookup table 구성, permutation state vector
• key[] = N bytes

keystreambyte가 암호화에 사용

for i = 0 to 255
    S[i] = i
    K[i] = key[i (**mod** N)]
next i

j = 0
for i = 0 to 255
        j = (j + S[i] + K[i]) mod 256
        swap(S[i], S[j])
next i

i = j = 0

// swap & keystream byte 선택
i = (i + 1) mod 256
j = (j + S[i]) mod 256
swap(S[i], S[j])
t = (S[i] + S[j]) mod 256
keystreamByte = S

---

Block Ciphers

오늘날 대부분의 Block 암호화에 사용

→ bit-block 알파벳(2의 64/128승)을 사용한 key-dependent permutations

• Confusion
• Key-Ciphertext 간의 상관관계를 되도록 복잡하게 한다.
• Diffusion
• Plaintext-Ciphertext 간의 통계적 연관성을 제거한다.

 

< Block Ciphers에 대한 attack >

• known plaintext attack : 평문, 암호문 동시에 알고 있다.
  decoder → enciphered broadcast signal과 비교
• chosen plaintext attack : 암호화가 가능한 경우, 많은 평문들을 암호문으로 만들 수 있다.
• chosen ciphertext attack : 복호화가 가능한 경우, 많은 암호문들을 평문으로 만들 수 있다.
  권한 있는 사용자가 logout, 허용된 작업하는 동안 hacker의 일시적 접속
• related key attack : Hacker가 타겟 K와 연관된 key들에 답할 수 있는 query 생성

DES (Data Encryption Standard)

1970년대 최초의 Block 암호화 기술, Key 기반. (64-bit ⇒ 64-bit 블록)

특정 함수가 반복되는 Feistel Cipher

• 64-bit block length & 56-bit key length (치명적)
  • 64-bit block plaintext를 32-bit씩 나눠 L, R로 쪼갠 후 L에만 XOR연산 + 함수 적용
• block cipher가 16 rounds 반복
• (subkey) 각 round마다 48-bit key 사용

Security는 “S-boxes”에 의존하며, 각각의 S-boxes는 6-bit ⇒ 4-bit 매핑

3DES (Triple DES)

오늘날 56-bit DES key는 너무 작아 Exhaustive key search에 취약하지만, 옛날 시스템과의 호환성은 유지하고 싶다. → 보안성 & 호환성

- 112-bit key 사용

- 2개의 Key(각각 56-bit)를 사용해 encrypt/decrypt

• Encrypt : E-D-E
• Decrypt : D-E-D

▶ 만약 1개의 Key를 사용하면? : Backward compatible

 

▶ 만약 1개의 Key로 2번 암호화?

같은 key로 2번 암호화 → 56-bit Key 1개인 것과 다르지 않다.

2DES (Double DES)

2개의 key로 1번씩 암호화하지 않는 이유?

▶ Known plaintext attack : “Meet-in-the-Middle”

 

$C = E_{k2}(E_{k1}(P))$ 에서 K2로 양변을 Decrypt

→ $D_{k2}(C) = E_{k1}(P)$

→ (양변이 같아지는 지점 찾는데 걸리는 시간) = $2^{56}+2^{56}+\alpha$

 

112-bit임에도 훨씬 적은 시간으로 Key를 구할 수 있다.

AES (Advanced Encryption Standard)

DES 대체 → Block cipher가 반복되지만, Feistel Cipher는 아니다!

(ex. Rijndael Algorithm)

• Block size : 128-bits
• Key-length : 128 / 192 / 256 (Block size와 무관)
• Rounds : 10~14 (Key-length에 의존)
  • DES는 16 rounds & L과 R로 쪼개서 반만 함수 통한 encrypt
  • AES는 매 Round마다 전체 bit들을 전부 encrypt
  • 각 Round마다 4개의 함수 사용 (3 “layers”)
    • SubBytes (non-linear) : 변환표로 byte 단위 치환
    • ShiftRows(linear-mixing) : 행 단위 shift
    • MixColumns(non-linear) : 열 단위 mix
    • AddRoundKey(key addition)

< 다른 Symmetric Block Ciphers >

IDEA / Blowfish / RC6 / SEED

Multiple Blocks’ Operation의 Mode

multiple block 암호화 방법 고려사항

=> 새로운 key가 각 block마다 필요한가? / 각 block을 독립적으로 암호화? / 이전 block에 의존하는 chain 구조 / Partial blocks 처리

• ECB (Electronic CodeBook) : 각 block을 독립적으로 encrypt
• CBC (Cipher Block Chaining) : 앞뒤 block 간 의존성(chain), 대량 암호화 어려움
• CTR (Counter)
• CFB (Cipher FeedBack)
• OFB (Output FeedBack)
• GCM (Galois Counter Mode) : 병렬화, (암호화+인증) 한번에

ECB (Electronic CodeBook)

동일한 Key값 → 각 Block을 독립적으로 암호화

가장 단순 : Message를 (n-bit_ block들로 나눠서 cipher encryption function 개별적 적용 ($n$ = cipher의 block size)

• (한계) 같은 Plaintext는 같은 Ciphertext를 만든다! (같은 Key값 & 분포)
  • 또한 Cut & Paste가 가능하다는 단점 (Alice’s uncompressed image)
• Block cipher로 pseudo-random값을 넣어서 해결할 수도 있다!

CBC (Cipher Block Chaining)

이전 Ciphertext와 현재 Plaintext의 XOR 연산 → 랜덤 초기 벡터(IV)로 전체 Ciphertext 랜덤화

• ECB의 한계 극복 : 같은 Plaintext는 다른 Ciphertext Blocks를 만든다!
• 에러들로부터 자동 복구가 가능하다.
• (한계) Cut & Paste가 여전히 가능하지만 더 복잡하다 → garble 초래
  → Message의 무결성을 확보하지 못한다.

MAC (Message Authentication Code)

(암호화 + MAC값) 같이 전송 → 수신자가 송신자와 같은 key값으로 복호화하여 비교

Hash 연산 통해 Message의 무결성 확보!

• Key를 알고 있는 사람만 생성&증명 가능 - secure
• 초기 vector 고정

CTR (Counter Mode)

암호화를 통해 pseudo-random bit stream 얻고, 다른 blocks들의 sequence를 생성하기 쉽다.

• 장점 : 병렬 처리가 가능하여 대량 암호화가 가능하다! (fast random access decryption이 필요할 때 용이)

($O$는 offset - nonce, random값)

CFB (Cipher FeedBack) v/s OFB (Output FeedBack)

언제 암호화하여 전달하냐의 차이

plaintext는 pseudo-random bit stream generator의 출력과 XOR 연산

GCM (Galois Counter Mode)

AEAD (Authenticated Encryption with Associated Data)

• AE = (암호화: Integrity + 인증: Authentication )
• 암호화와 인증이 독립적 수행

CBC는 confidentiality&integrity를 보호할 때 bulk encryption에 효율적 X

 

⇒ (기본 원리)

• counter mode를 변형하여 encryption
• ciphertext를 Galois field(GF)의 다항식의 계수로서 사용하여 authentication tag 계산 → integrity

⇒ (장점) parllelizable → High-throughput encryption/decryption