Block Cipher Operation - ECB/CBC/CFB/OFB/CTR

* DES(Data Encryption Standard) 설명 - 참고

 

 

Double DES

• Encryption을 2번 하자!
• C = E($K_2$, E($K_1$, P))
• P = D($K_1$, D($K_2$, C)) 

 

Q: key 56 bits가 두 개니까 공격하려면 112 bits를 다 돌려봐야 하니 안전하겠지?

A: Nope! 그 정도는 아냐 -> Meet-in-the Middle Attack

 

 

 

 

 

 

 

 

 

 

Meet-in-the Middle Attack

• Meet-in-the middle: 타협하다
•  Observation
  • C = E($K_2$, E($K_1$, P))
  • P = D($K_1$, D($K_2$, C)) 
  • X = E($K_1$, P) = D($K_2$, C)
• 공격자가 (p, c) 쌍을 알게된 경우를 가정해보자.
  • key를 알기 위해서는 112 bits를 모두 다 대입해봐야 하나?
  • Nope! 반으로 나눠서 찾을 수 있다!

• 찾는 방법:
  • [p -> E($K_1$) -> x]에 하나의 key($K_1$)에 대한 가능한 값들(56 bits)을 대입해서 x들을 추출해 낸다.
  • 반대로도 [c -> D($K_2$) -> x]에 ($K_2$)에 대한 가능한 값들을 대입해서 x'를 추출해 낸다.
  • 그 후, 각각 정렬한다(x끼리, x'끼리)
  • 같은 x를 찾았다면, 그 x를 출력하게 한 key값이 각각 $K_1$, $K_2$가 된다.
• 즉, [$2^56$*2 + 정렬시간*2] 시간 복잡도로 key값을 찾을 수 있다. -> 별로 안전하지 않다.
• 하지만 모든 x 값을 다 기록하기에는 메모리가 부족하다.
  • 해결책: 일부 x, x' 값들만 뽑아서 저장한 후 찾는다.
  • 정확도는 떨어지게 되지만, 속도를 향상시킬 수 있고, 메모리 문제를 해결할 수 있다.

 

 

Triple-DES with Two-key

• 그렇다면 위에서 설명한 meet-in-the-middle attack에 대응하기 위해 이번에는 DES를 3번 돌려보자!
• meet-in-the-middle attack의 공격의 cost를 $2^{112}$로 올릴 수 있다.
• 168 bits 길이의 key가 필요하다.

• Q: Encryption 중간에 Decryption이 끼어있는 이유는?
  • Backward compatible(하위 호환성) 때문이다.
  • $K_2$ 자리에 $K_1$을 넣으면 decryption 결과 원래 Plaintext가 나오게 된다. 결과적으로 single DES가 된다.
  • 즉, 알고리즘을 크게 바꾸지 않고 하위 버전과 호환되게 할 수 있다.

• Triple DES는 single DES에 비해 안전성은 높지만, 연산량이 많아 속도가 느리다.

 

 

Modes of Operation

• 암호 알고리즘의 효과를 향상시키거나 애플리케이션에 적용하기 위한 기법이다.
• 모든 Block Cipher에 똑같이 적용할 수 있다. (Triple DES, AES 등)
• Block Cipher는 plaintext를 block 단위로 나눠서 변환하는 암호화 방법을 말한다.
• 5가지 모드
  • ECB / CBC / CFB / OFB / CTR

 

 

1. ECB(Electronic CodeBook) Mode

• 작동 방식:
  • 각각의 plaintext block을 따로 encryption한 후, 결과물들을 합친다.
• 단점:
  • 같은 key를 사용해서 encryption을 하기 때문에, 같은 문자는 항상 같은 문자로 변환되게 된다.
  • 이로 인해 통계적으로 분석할 수 있게 된다. -> 안전하지 않음
  • Pre-processing 불가
    
    • Pre-processing은 어려운 작업을 미리 해놓는 것을 말한다.
    • ECB에서 어려운 작업은 Encryption 연산 부분인데, 이 부분은 plaintext가 들어오기 전에 작업을 할 수 없으므로 pre-processing은 불가능하다.
• 장점:
  • 각 block간 연산이 독립적으로 일어나기 때문에, 병렬로 작업할 수 있다.

 

 

2. CBC(Cipher Block Chaining) Mode

 

• 작동 방식: 
  • 첫 번째 plaintext block($P_1$)을 encryption하고, 그 결과물을 다음 plaintext block($P_2$)와 XOR한 것을 입력으로 넣는다.
  • 첫 번째 encryption을 진행할 때는, IV(Initial Vector)로 따로 입력을 넣어준다.
• 이 방식의 경우 Error Propagation이 발생한다.
  • 에러가 전파된다는 뜻이다. 위 단계 중, 어떠한 오류로 plaintext($P_i$)의 bits의 일부가 바뀐다면 그 결과($C_i$)는 큰 차이가 나게 되고, 그 결과가 다음 단계의 입력으로 들어가면서 에러가 확산된다.
  • 이러한 특성은 단점일 수도 있지만, 장점으로써도 작동한다. 
• 장점:
  • Integrity(무결성)과 Authentication(인증)을 제공할 수 있다.
  • 이렇게 메시지의 무결성과 인증을 제공하는 것을 MAC(Message Auth. Conf.)라고 한다.
• 단점:
  • 직전 block의 연산이 끝나야 다음 block의 연산을 수행할 수 있다.
    • 특히, encryption하는 연산은 복잡하기 때문에 오래 걸릴 수 있는데, 그동안 다른 block들은 기다리기만 해야 한다.
  • Pre-processing과 병렬 처리 불가능

 

 

MAC

• 목표: Integrity(무결성)과 Authentication(인증)을 제공하는 것
• 작동 방식:
  • 수신자가 {$P_1$, $P_2$, ..., $P_n$, $C_n$}을 수신한다.
  • 입력받은 plaintext blocks($P_1$ ~ $P_n$)로 똑같이 Encryption을 수행해 본다.
    • 수신자도 송신자와 같은 key를 가짐
  • 이때, 수신받은 $C_n$과, 직접 encryption을 수행해본 결과가 동일하다면 무결성을 보장할 수 있다.
    • 송신자가 보낼 때, 일부 데이터에 오류가 생겼거나, 공격을 받아 데이터가 변경되지 않았음을 보장
  • 또한, 결과가 동일하다는 것은, 수신자가 동일한 key를 가지고 있다는 것으로 authentication을 할 수 있다.
• Q: 무결성을 보장하려면 간단하게 parity bit를 쓰면 되는 게 아닌가?
  • parity bit는 아무나 만들 수 있다. 공격자가 데이터를 변조시키고, 그에 맞게 parity bit도 변조하면 수신자는 데이터의 이상을 파악할 수 없다.
  • 또한 parity bit로는 authentication이 불가능하다. 이 부분이 parity bit와 MAC의 차이이다.

 

 

 

<복습>

• 아래 사진을 보면서 간단하게 Stream Cipher와 Block Cipher에 대해 복습해보자.
• Stream Cipher
  • Decryption은 Encryption의 순방향으로 작동됨.
  • XOR로 작업이 이루어지기 때문
• Block Cipher
  • Decryption을 하려면, Encryption에서 이뤄진 연산들을 역으로 거슬러 올라가야 한다.
• 자세한 설명 - 참고

 

 

3. CFB(Cipher FeedBack) Mode

• CBC와 비슷해 보이지만 이건 Stream mode이다. 
  • Decryption이 순방향으로 이루어진다.
• 장점:
  • Error propagation 됨 -> MAC 제공
• 단점:
  • CBC와 마찬가지로 직전 아웃풋이 나와야지만 다음 block이 수행될 수 있다.
  • Pre-processing과 병렬 처리 불가

 

 

4. OFB(Output FeedBack) Mode

• CBC나 CFB와 달리 해당 block의 연산이 완전히 끝나기 전(encrpytion 함수만 지난 후), 그때까지의 결과를 다음 block의 입력으로 미리 넣어준다.
• 어떤 plaintext가 변조되어도 다른 block에 영향을 주지 않는다 -> No error propagation
  • 즉, MAC으로 사용할 수 없다.
• 장점:
  • Preprocessing이 가능하다.
    • Encryption 연산이 어려운 연산 부분인데, plaintext가 들어오는 것과 상관없이 미리 다 처리해 놓을 수 있다.
• 단점:
  • 병렬로 작업 불가.
    • 아직 직전 block의 작업이 어느 정도 끝나야 다음 block을 처리할 수 있으므로

 

 

5. CTR(Counter) Mode

• ECB와 비슷하게 보이지만, 여기에는 counter라는 특성이 있다.
• 여기서 counter는 우리가 생각하는 '숫자 세는 것'이 맞다.
  • 즉, 각 block에 counter를 1, 2, 3 이런 식으로 줌으로써 counter끼리 연관관계를 주는 것이다.
• 장점:
  • 같은 문자여도 상황에 따라 다른 문자로 변환된다. -> counter 역할
  • 병렬로 작업이 가능하다
    • 어떠한 결과가 인풋으로 들어오는 것이 아니라 독립적으로 작동하기 때문
    • 랜덤 하게 접근 가능하다. 3번째 block부터 작업할 수 있음.
  • Pre-processing도 가능하다.

 

 

 

ECB를 제외한 mode들

비교해 보자!

 

 

5가지의 모드들을 비교해보자.

	Block vs Stream	Same Output	Error Propagation	Pre-processing	Parallel Process
ECB	Block	O	X	X	O
CBC	Block	X	O	X	X
CFB	Stream	X	O	X	X
OFB	Stream	X	X	O	X
CTR	Stream	X	X	O	O

• Q: 가장 좋은 mode가 무엇일까?
  • A: CTR!!!
  • 이유:
    • 같은 문자가 상황에 따라 다르게 변화하고
    • Error propagation은 장단점이 있으니 패스하고
    • Pre-processing 가능하고
    • 병렬로 작업이 가능
• 참고:
  • CBC, CFB 둘 다 MAC으로 쓸 수 있지만, 주로 CBC를 사용한다.
  • CBC는 MAC으로써 Integrity와 Authentication을 제공할 때 사용한다.
  • CTR은 긴 길이의 암호문을 만들 때, confidentiality(기밀성)을 제공한다.
  • CTR with CBC-MAC(CCM): 기밀성, 무결성, 인증을 모두 다 제공한다.

 

 

 

 

 

 

 

 

출처:

- [Cryptography and Network Security: Principles and Practices]