[Cryptography] 5. Block Cipher mode of Operation

 앞서 공부했던 기본적인 Block Cipher은, 아래와 같은 구조를 가지고 있었다.

아래와 같이 가장 기본적이고 단순한 Block Cipher 구조를 Electronic Codebook 이라고도 한다.

 

Electronic Code Book

Cryptosystem의 5개 튜플 (M,C,K,E,D) 에서 message인 m이 직접 E(Encryption function)로 k(secret key) 암호화되어서 c(cipher text) 를 만들어 내었다. Message가 미리 설정한 블록단위로 끊어져서 Encrypt 되기에, Block Cipher이라고 불렀다는 것을 명심하자. 위 방법을 사용하면, 동일한 Plaintext message 블럭은 반드시 동일한 Ciphertext code블럭으로 암호화 된다. 따라서, 위 방법은 여러개의 블럭을 암호화하여 통신하기에는 적합하지 않은 방법이다. 해커가 여러개의 (m,c) 를 받아놓고 (Ciphertext only attack) 보면 대충 뜻을 짐작할 수도 있기 때문이다.

예를들어, English Character Frequency analysis를 해보면 e가 약 11%, a가 9% 정도 등장한다는 통계를 사용하면, transposition이나 simple substitution cipher은 샤논에 의하면 28개의 텍스트만 해커가 가로채면 이론적으로 암호를 뚫을수 있다는 것이다.

 그래서 보통 Key 전달 같은 Single Block Transmission에 위 방법을 사용한다. 

 

◉ One Key Stream Cipher 

 

Stream Cipher은, 위의 ECB 모드에서 message가 한 차례 시간에따라 바뀌는 난수와 연산된 뒤에, Encrypt Function에 들어가는 구조를 가진다. 즉 데이터의 흐름(Stream)을 순차적으로 암호화하는 암호화 기법이다. 

 

기존 Cryptosystem 5개 튜플에서 Time-variant parameter u 가 추가되었다. 

따라서, One key stream cipher 의 cryptosystem은 6개 튜플 시스템이다 (M,C,K,E,D,u) 

 

u는, cryptosystem 내 시간에 따라 변화하는 파라미터로, 메모리에 저장되어 시간에따라 바뀌는 값이다.

 

[Shift Register]

 u는 Shift Register 라는 하드웨어에서 연산이 되는데, 굉장히 로직이 간단하다.

Shift register은 튜플 (n,t,b) 로 표기하고,

n : 메모리 셀의 개수,

t : Shift count 1회 마다 shift 되는 cell의 개수

b : 각 cell의 메모리 비트 크기   

 

예를 들어, 아래 구조는 (12,3,1) Shift Register이다.

(12,3,1) Shift Register

◉ Cipher Block Chaining

 

Cipher Block Chaining 모드에서는, 각 Plaintext message들이, Encryption function에서 암호화 되기 전에, 이전 블럭의 Ciphertext와 XOR연산 된다. 

 

XOR연산을 위해, 이전 블럭의 Ciphertext을 Shift Register에 저장하는데, 각 블럭의 암호화 연산이 끝나면, 결과물인 ciphertext를 다음 블럭의 암호화를 위해 shift register에 넣어 저장한다. 

 

이 방법을 사용하면, Plaintext m1과 m2의 내용이 같더라도, c1과 c2의 내용은 무조건 다를수 밖에 없다. // 하지만 같은 문자열을 계속보내면 똑같을듯??? -> 질문하자

 

Cipher block chaining

 

1. Shift register에 Initial vector값을 부여, message와 XOR연산 한다.

 

2. 결과물을 Encrypt 하고, message에 대응하는 Ciphertext를 만들어낸다.

 

3. 만들어낸 ciphertext는 다음 message 블럭의 연산을 위해, shift register에 저장되고, 레지스터는 블럭크기만큼 shift 된다. 

 

CBC mode Formula

 

위 수식 양변에 Dk 연산을 하면, Decryption 식도 쉽게 유도할 수 있다.

 

◉ Cipher Feedback

 

Cipher Feedback은, Secret Key 와 

shift register의 크기가 n이라고 할때, 

t (1<=t<=n) 는, 매 카운트마다 shift register가 shift되는 비트 수이자, message 블럭의 크기이다. (n은 레지스터 크기)

 

직관적으로 이해할 수 있는데, 앞에 CBC처럼, 이전 블럭의 Cipher text가 Shift register에 들어가는데, Plain text와 XOR하는 것이 아니라, 직접 secret key k 와 함께 Ek의 input이 된다. 

 

Ek 의 output은 shift register의 크기가 n이므로 당연히 크기가 n 일텐데, message 블럭 과 연산하기 위해서 앞 t비트 만 선택된 후, 나머지는 버려진다. 

 

message 와 위 연산의 결과물은 XOR연산을 통해서 새로운 Ciphertext로 유도된다.

 

Cipher Feedback

 Decrypt progress는 위의 화살표를 거꾸로하면 된다. 초기 c0를 해독할때는 Initial vector의 값을 사용하고, 그 이후부터는 c0를 받는 순간, shift register에 보관하여 연산하면 된다.

 

 만약 t=1 이면 1비트 블럭마다 암호화를 진행하는것이기 때문에 security 는 좋아진다, 하지만 연산 자체의 횟수가 엄청 많아지기때문에, 연산 성능 측면에서 떨어진다.

 

 반대로 t=n(레지스터 크기)이면, 적은횟수의 연산만을 필요로 하기때문에 성능은 좋아지지만 security는 떨어지게된다. 

 

또한 암호화가 앞 블록에 의존하기 때문에 병렬연산이 안된다. 

 

 

☞ Cipher Feedback 예제 

 

 Q . Consider the 8-bit CFB mode of DES, where n = 64 and t = 8. If a bit error occurs in the transmission of a ciphertext character (i.e., a block of one byte), how far does the error propagate in the decrypted plaintext characters? Justify your answer.

 

=> shift register의 크기가 64bit, Plaintext를 8bit단위로 암호화한다. 8bit=1byte이므로, ciphertext character 하나가(c) 오염된 것이다.

첫 값 c0를 decrypt할때는 Initial vector의 값이 Shift register에 들어있지만, 그 이후의 stream cipher에는 c0이 레지스터에 들어가서, IV를 c0의크기(8비트) 만큼 왼쪽으로 shift한다. 따라서, 이 경우, 하나의 ciphertext는 총 8번의 연산동안 shift register에 잔류한다. 그래서 우리는 오류난 ciphertext 이후 8개의 ciphertext를 decrypt하는데에 error가 생김을 쉽게 이해할 수 있다.

 

 

 

 

 

◉ Output Feedback

 

위 Cipher Feedback 과 비슷하지만, 레지스터에 들어가는 값이 다를 뿐이다.

 

Encrypt function의 output이 Shift register에 들어가기 때문에, output feedback 이라고 부른다. 

 

Cipher Feedback 모드는, 이전 블록의 ciphertext가 그대로 shift register에 저장되었기에, self synchromization 이 가능했지만, 여기서는 synchronization 문제에 취약하다. 

 

따라서 성능은 Cipher Feedback 과 비슷하다. 하지만 보안은, Output feedback이 조금 더 취약하다. // 보충하기 위키피디아 참고

 

Output Feedback

Output Feedback mode 의 문제점으로, plaintext가 쉽게 변할수 있다는 문제가 있는데, 이는 Digital Signature로 문제를 보완할 수 있다.

또한 Cipher text feedback 과 마찬가지로 병렬연산이 안된다. (앞 블록에 의존하기 때문에)

 

◉ Counter Mode

 

Counter mode는 CTR이라고도 하며, 매 카운트 마다 counter로 카운팅, 카운트가 최대값을 넘어 가면 다시 0부터 시작하는 cyclic counting 하드웨어를 implement 한다.

 

Counter mode encryption

1. Cyclic Counter에 기본값(Initialize Vector)을 부여, 각 블럭 암호화 시행마다 카운트값을 1 증가시킨다.

 

2. Secret Key k 와 카운터를 Ek로 Encrypt한다. 

 

3. Message 인 Plaintext 와 Encrypt function의 결과물을 XOR연산해서 Cipher Text 로 만들어낸다. 

 

 

 

◉ Combining Block Ciphers

 

 실생활에서는 위에서 설명한 서로 다른 Block Cipher 기법들을 보안성 향상을 위해 중첩을 한다. 예를들어, DES 기법은 AES기법으로 이미 대체되어 사라진지 오래지만, DES기법을 3번 중첩한 T-DES는 아직도 많이 사용되고 있다.

 

Combining Block Ciphers