copyright 2008 암호알고리즘 (INS301) 강의노트 03 대칭암호알고리즘 : 암호화모드 한국기술교육대학교인터넷미디어공학부
교육목표 대칭암호알고리즘에대한이해 암호화모드 채우기에대한이해 암호문훔침기법 스트림암호방식에대한이해 2/37
대칭암호알고리즘 크게블록암호방식과스트림암호방식으로분류됨. 블록암호방식 : 메시지를일정한크기로나누어각블록을암호화하는방식 스트림암호방식 : 한번에한비트또는한바이트를암호화하는방식 블록암호방식에서같은평문블록은항상같은암호문블록으로암호화된다. 극복방안으로암호화모드 (cryptographic mode) 등장 스트림암호방식에서각바이트또는비트는암호화될때마다항상다른바이트또는비트로암호화된다. ( 영구적인것은아님 ) 암호화모드는일반적으로암호알고리즘, 피드백 (feedback), 단순연산으로구성된다. 요구사항. 암호화모드를도입하여도기존알고리즘의성능에큰영향을주어서는안된다. 피드백 : 한블록을독립적으로암호화하지않고, 다른블록이나다른블록의암호화한결과를활용하는것을말한다. 3/37
암호화모드 암호화모드의특성은다음에의해결정된다. 암호화된암호문에서두암호문블록을바꾼경우에복호화결과 암호화하기전에한평문블록에오류가발생하였을때그것의파급효과암호화한후에한암호문블록에오류가발생하였을때그것의파급효과암호화모드사용에따른보안문제의유무 4/37
ECB(Electronic CodeBook) 모드 ( 계속 ) 피드백을사용하지않는모드 암호화 : C i = E K (P i ) 복호화 : P i = D K (C i ) P i C i P i 64비트평문 64비트암호문 64비트평문 E k D k 키 K 키 K 5/37
ECB(Electronic CodeBook) 모드 암호화된메시지의블록들의위치를바꾸면복호화된평문메시지의블록위치들도동일하게바뀌게됨 P 1 P 2 P 3 P 4 C 1 C 2 C 3 C 4 C 1 C 3 C 2 C 4 P 1 P 3 P 2 P 4 오류확산 : 암호화된메시지의한블록의오류는그블록의복호화에만영향을줌 P 1 P 2 P 3 P 4 C 1 C 2 C 3 C 4 C 1 C 2 C' C 4 P 1 P 2? P 4 동일한평문은항상같은암호문으로암호화된다. 비고. 결정적암호알고리즘 (deterministic i ti encryption) 6/37
채우기 평문메시지의크기가정확하게블록크기의배수가아닌경우에필요 채우기 (padding): 완전하지않은마지막블록끝에규칙적인일련의비트 ( 예 : 모두 0, 모두 1) 를추가하여완전한블록을만드는것 요구사항 복호화한사용자는채워진부분을정확하게제거할수있어야한다. 위요구사항을충족시키는두가지방법 방법 1. 암호문과별도로원평문의크기를전달 방법 2. 채우기를한부분에채운부분을제거할수있는요소를포함 7/37
채우기 계속 일반적인채우기방법 P n : 평문의마지막블록 (k 바이트 ) 블록크기 : 8 바이트 8-k = 0 실제평문 8 P n P n+1 채우기가적용된평문 8-k 1 평문의크기가정확하게블록크기의배수이어도채우기를하여야한다. 5 P n 8/37
채우기 계속 PKCS #5, PKCS #7, RFC3369 에정의된방법 8-k = 0 08 08 08 08 08 08 08 P n P n+1 8-k 1 05 05 05 05 05 08 P n 채우기를해야하는모든부분을채워야하는바이트수의값으로채운다. 마지막바이트의값이 1과 8 사이의수인지검사한후에그수만큼앞의바이트들도동일한수로채워져있는지검사한다음에제거한다. 일반적인채우기방법이나이방법모두모든메시지를항상채우기를하여야한다. 문제점. 암호문이평문보다항상크다. 9/37
암호문훔침기법 암호문훔침기법 (ciphertext stealing): 바로전암호문블록이용하여채우기를하는방식장점. 암호화된메시지의크기와평문의크기가같아진다. P n-1 P n C' C n-1 C n C' E K E K D K D K C n C' C n-1 P n C' P n-1 EK ( Pn 1 ) Cn C E ( P C ) = C K n n 1 D K ( C ) = P C D ( C C ) = P = K n 1 n K n n 1 10/37
CBC(Cipher Block Chaining) 모드 같은평문블록들도서로다른암호문블록으로암호화된다. P 1 P 2 C 1 C 2 IV 0 XOR E K D K D K E K IV 0 C 1 C 2 P 1 P 2 C E P C = i K( i i 1 ) P i = D K ( C i ) C i 1 C i 는 C i-1 를계산한후에계산할수있다. 하지만 C i 의복호화는독립적으로계산할수있다. 11/37
CBC 모드 계속 C 0 : 초기화벡터 (IV, Initalization Vector) C1 = EK( P1 IV) = EK( P1 C0) P1 = D ( K C ) 1 IV = P1 C0 C0 보통랜덤블록을사용함 같은메시지를다시암호화하면결과가다르다. 비고. 확률적암호알고리즘 (probabilistic encryption) 초기벡터의비밀성을유지할필요는없다. C i : P i 와 P i 앞에있는모든평문블록들에의해결정된다. 암호문블록들의위치를변경하면올바르게복호화되지않는다. P 1 P 2 P 3 P 4 P 5 C 0 C 1 C 2 C 3 C 4 C 5 C 0 C 1 C 3 C 2 C 4 P 2 = D ( K C ) 3 C1 = P3 C2 C1 =? P 3 = D ( K C ) 2 C3 = P2 C1 C3 =? C 5 P 1??? P 5 1 P 4 = D ( K C )? 4 C2 = P4 C3 C2 = P = D ( ) K C C = P C C = P 5 5 4 5 4 4 5 12/37
CBC 모드 계속 채우기 일반적인방법이나끝문자표시방법을사용할수있음 암호문훔침기법 Cn C = EK( P n 1 Cn 2) Pn C = DK( Cn ) { C 0} 1 n Cn 1 = EK({ Pn 0} { Cn C }) Pn 1 = DK( Cn C ) Cn 2 0 으로채우기 암호문훔칩기법을사용하지않고채우기를하면암호문의길이는평문보다최대두블록 ( 초기벡터때문 ) 이커짐. 13/37
CBC 모드 계속 오류확산 (error propagation) 암호화하기전에 P i 에오류가발생하면 C i 에영향을줄뿐만아니라 C i 이후모든암호문블록에영향을준다. 마지막블록을 MAC(Message Authentication Code) 으로사용할수있음 P 1 P 2 P 3 P 4 C 0 C 1 C 2 C 3 C 4 P 5 C 5 C = E K( P C ) EK ( P C ) = C C = E ( P C ) E ( P C ) = C 2 2 1 2 1 2 3 K 3 2 K 3 2 3 P 1 P 2 P 3 P 4 P 5 C 0 C 1 C C P 1 P 2 3 C 4 C 5 2 P 3 P 4 P 5 P 2 = D ( K C ) 2 C1 = P 2 C1 C1 = P 2 P 3 = D ( K C ) 3 C 2 = P3 C 2 C 2 = P3 14/37
CBC 모드 계속 암호화된이후 C i 에오류가발생하면복호화할때 P i 와 P i+1 에만영향을준다. 자체회복 (self-recovering) 기능을지니고있다고한다. 즉, 하나의암호블록에오류가발생하면나머지모든블록의복호화에영향을주지않는다. P 1 P 2 P 3 P 4 C 0 C 1 C 2 C 3 C 4 C 0 C 1 C 2 C 3 C 4 P 1?? P 4 P 2 = D ( K C ) 2 C1 =? C1 =? P 3 = D ( K C )? 3 C 2 = P3 C2 C 2 = P = D ( K C ) C = P C C = P C i 의 j 번째비트오류 4 4 3 4 3 3 4 P i 는쓰레기, P i+1 는 j 번째비트만잘못된다. 15/37
CBC 모드 계속 보안문제 암호화된메시지끝에임의의블록을추가할수있다. C 0 C 1 C 2 C 3 C 4 C 0 C 1 C 2 C 3 C 4 C 1 C 2 C 3 P 1 P 2 P 3 P 4? P 2 P 3 C 1 D K ( C 1) C 4 = P 1 C 0 C 4 =? C D ( C ) C = P C C = P 2 K 2 1 2 1 1 2 두개의암호문을조합하여새암호문을만들수있다. C 0 C 1 C 2 C 3 C 4 C 0 C 1 C' 2 C' 3 C' 4 P 1? P' 3 P' 4 C' 0 C' 1 C' 2 C' 3 C' 4 C 2 DK ( C 2) C1 = P 2 C 1 C1 =? C D ( C ) C = P C C = P 3 K 3 2 3 2 2 3 16/37
CBC 모드 계속 암호문블록을변경하여예측할수있는변경을도입할수있다. C i 의한비트를변경하여 P i+1 의특정비트를변경할수있다. 평문의패턴은 chaining 때문에은닉되지만메시지가매우길경우에는패턴이다시등장한다. 블록의크기가 m 이면 2 m/2 블록다음에는같은패턴이다시등장할수있다. C i 와 C j 가같으면다음이성립한다. P P = C C i j i 1 j 1 17/37
스트림암호방식 가장단순한스트림암호화방식 키스트림생성기 (keystream generator) 를이용한다. 암호화하는사용자와복호화하는사용자는같은키스트림생성기를가지고있다. 암호화하는키스트림에서출력하는바이트 ( 비트 ) 와평문의바이트 ( 비트 ) 를하나씩 XOR하여암호문의바이트 ( 비트 ) 를얻는다. 이방식의안전성은키스트림생성기의출력에의해결정된다. 키스트림생성기가정말로랜덤한비트를출력할경우에는 one-time pad 와동일한안전성을제공한다. 키스트림생성기 키스트림생성기 k i k i p i c i p i 18/37
스트림암호방식 계속 문제점 공격자가암호문과그것에해당하는평문을가지고있으면키스트림을얻을수있다. 공격자가같은키스트림으로암호화된두개의암호문을가지고있으면그것을 XOR 하여두개의평문을 XOR 한데이터를얻을수있다. 이것을공격하여평문을얻는것은비교적쉽다. 매번키스트림이달라야한다. 이와같은문제때문에스트림암호방식도암호키를사용한다. 공격자가키스트림을얻어도키를바꾸면처음부터다시해독공격을해야한다. 19/37
스트림암호방식 계속 키스트림생성기의세가지구성요소내부상태 (internal state): 키스트림생성기의현재상태다음상태함수 (next-state function): 내부상태를입력으로받아새로운상태를출력하여주는함수출력함수 (output function): 키와내부상태를입력으로받아키스트림바이트 ( 비트 ) 를생성하여주는함수 내부상태 다음상태함수 K 출력함수 20/37
자체동기화스트림암호알고리즘 자체동기화스트림암호알고리즘 내부상태 내부상태 출력함수 K 출력함수 p i c i p i 각키스트림바이트 ( 비트 ) 는고정된개수의이전암호문바이트 ( 비트 ) 에의해결정된다. 21/37
자체동기화스트림암호알고리즘 계속 예 3.1) 내부상태가 8 바이트이고, 출력함수는현재의내부상태와키를입력받아한바이트를출력한다가정하자. 또한다음상태함수가이동연산에의해이루어지며, 암호화하는측과복호화하는측의내부상태의초기값은동일하다. 이때C 1 이전달되는과정에서오류가발생했다. 내부상태 ( 암호화측 ) 출력결과내부상태 ( 복호화측 ) 출력결과 I 8 I 7 I 6 I 5 I 4 I 3 I 2 I 1 K 1 C 1 = P 1 K 1 I 7 I 6 I 5 I 4 I 3 I 2 I 1 C 1 K 2 C 2 = P 2 K 2 I 5 I 4 I 3 I 2 I 1 C 1 C 2 C 3 K 4 C 4 = P 4 K 4 I 6 I 5 I 4 I 3 I 2 I 1 C 1 C 2 K 3 C 3 = P 3 K 3 I 4 I 3 I 2 I 1 C 1 C 2 C 3 C 4 K 5 C 5 = P 5 K 5 I 3 I 2 I 1 C 1 C 2 C 3 C 4 C 5 K 6 C 6 = P 6 K 6 I 2 I 1 C 1 C 2 C 3 C 4 C 5 C 6 K 7 C 7 = P 7 K 7 I 1 C 1 C 2 C 3 C 4 C 5 C 6 C 7 K 8 C 8 = P 8 K 8 C 1 C 2 C 3 C 4 C 5 C 6 C 7 C 8 K 9 C 9 = P 9 K 9 I 5 I 8 I 7 I 6 I 5 I 4 I 3 I 2 I 1 K 1 P' 1 = C' 1 K 1 I 7 I 6 I 5 I 4 I 3 I 2 I 1 C' 1 K' 2 P' 2=C 2 2 K' 2 I 4 I 3 I 2 I 1 C' 1 C 2 C 3 K' 4 P' 4 =C 4 K' 4 I 6 I 5 I 4 I 3 I 2 I 1 C' 1 C 2 K' 3 P' 3 =C 3 K' 3 I 4 I 3 I 2 I 1 C' 1 C 2 C 3 C 4 K' 5 P' 5 =C 5 K' 5 I 3 I 2 I 1 C' 1 C 2 C 3 C 4 C 5 K' 6 P' 6 =C 6 K' 6 I 2 I 1 C' 1 C 2 C 3 C 4 C 5 C 6 K' 7 P' 7 =C 7 K' 7 I 1 C' 1 C 2 C 3 C 4 C 5 C 6 C 7 K' 8 P' 8 =C 8 K' 8 C' 1 C 2 C 3 C 4 C 5 C 6 C 7 C 8 K' 9 P' 9 =C 9 K' 9 C 2 C 3 C 4 C 5 C 6 C 7 C 8 C 9 K 10 C 10 =P 10 K 10 C 2 C 3 C 4 C 5 C 6 C 7 C 8 C 9 K 10 P 10 =C 10 K 10 22/37
자체동기화스트림암호알고리즘 계속 자체동기화스트림암호알고리즘에서는동기화되지않으면제대로복호화가이루어지지않는다. 예 3.1 에서보는바와같이암호문이전달되는과정에서 c i 바이트가올바르게전달되지못하면수신측키스트림의내부상태가다르게되므로올바르게복호화되지않는다. 오류가있는부분이더이상내부상태에영향을주지않으면다시정상적으로복호화된다. 즉, 내부상태가이전암호문의 n 바이트에의존하면의미없는데이터를 n 바이트전송하여상호키스트림을동기화할수있다. 오류확산 : 내부상태가이전암호문의 n 바이트에의존할때암호문에한비트오류가발생하면 n+1 바이트평문에영향을준다. 재전송공격에취약하다. 전달되는암호문을보관한후에나중에재전송하면처음동기화하는동안은쓸모없는데이터를얻게되지만다음상태함수에따라정해진수의바이트가지나면올바르게복호화된다. 23/37
자체동기화스트림암호알고리즘 계속 64 비트블록암호방식을이용한 8 비트스트림암호방식 shift register shift register 8bit K 블록암호 64bit K 블록암호 64 비트블록을암호화하는데총 8번의 64비트블록암호화를수행한다. k i k i p i c i c i p i CFB(Cipher FeedBack) 모드 일반블록암호방식의알고리즘은 CFB 모드를이용하여스트림암호방식으로전환할수있다. 24/37
CFB (Cipher FeedBack Mode) 모드 암호화연산만사용한다. 구현이효율적이다. 복호화함수를만들필요가없음. P 1 P 2 IV 0 = C 0 E K E K C 1 C 2 Ci = Pi EK( Ci 1) 25/37
CFB 모드 - 계속 복호화 C 1 C 2 IV 0 =C 0 E K E K P 1 P 2 Pi = Ci EK( Ci 1) 26/37
CFB 모드 계속 데이터를블록단위보다작은단위로암호화할수있다. 초기벡터 : CFB 모드에서는항상다른것을사용해야한다. 같은 IV 를사용하면공격자들은첫번째평문블록을다음과같이얻을수있다. C1 = P1 EK ( C0) C 1 = P1 EK ( C0 ) C C = P P 1 1 1 1 CBC 모드와마찬가지로암호문끝에암호문을만들거나두개의암호문을조합하여새암호문을만들어공격할가능성이있다. 27/37
CFB 모드 계속 오류확산 암호화하기전에평문블록 P i 에오류 P i 에오류가발생하면 C i 이후모든암호문블록에영향을준다. CBC와마찬가지로마지막암호문블록은 MAC 코드로사용할수있다. P 1 P 2 P 3 P 4 C 0 C 1 C 2 C 3 C 4 P 5 C 5 C = P E ( C ) P E ( C ) = C C = P E ( C ) P E ( C ) = C 2 2 K 1 2 K 1 2 3 3 K 2 3 K 2 3 P 1 P 2 P 3 P 4 P 5 C 0 C 1 C C 2 3 C 4 C 5 P 1 P 2 P 3 P 4 P 5 P = C E ( C ) = P E ( C ) E ( C ) = P 2 2 K 1 2 K 1 K 1 2 P = C E ( C ) = P E ( C ) E ( C ) = P 3 3 K 2 3 K 2 K 2 3 28/37
CFB 모드 계속 암호화된이후암호문블록 C i 에오류 n 비트 CFB 모드에서 C i 에오류가발생하면 P i 와 P i+1 블록의복호화과정에영향을준다. P 1 P 2 P 3 P 4 C 0 C 1 C 2 C 3 C 4 C 0 C 1 C 2 C 3 C 4 P 1?? P 4 P 2 = C 2 EK( C1) =? EK( C1) =? P 3 = C3 EK( C 2) = P3 EK( C2) EK( C 2) =? P = C E ( C ) = P E ( C ) E ( C ) = P 4 4 K 3 4 K 3 K 3 4 이때 P i 는 C i 와동일한위치에오류가발생한다. 그러나 C i+1 은결과를예측할수없다. 채우기가필요없음 P n 이 k 바이트이면 E K (C n-1 ) 의 k 바이트만사용 29/37
OFB(Output FeedBack) 모드 CFB 와마찬가지로암호화연산만사용한다. P i-1 P i P i+1 C i-1 C i C i+1 E K E K E K E K C i-1 C i C i+1 P i-1 P i P i+1 Ci = Pi Si, Si = EK( Si 1) P = C S, S = E ( S ) i i i i K i 1 평문를모르는상태에서도전처리가능 S 0 (C 0 ) 를본후에전처리가능 30/37
OFB 모드 계속 S i 는암호알고리즘대신 MAC을사용하여생성할수있다. S 0 = IV, S i = MAC(K, S i-1 ) 데이터를블록단위보다작은단위로암호화할수있다. IV: CFB 모드와마찬가지로항상다른것을사용해야한다. 차이점. 첫번째평문블록뿐만아니라모든평문블록들을 XOR 한값들을얻을수있다. C 1 = P 1 S 1 = P 1 E K ( S 0) C = P S = P E ( S ) 1 1 1 1 K 0 C C = P P 1 1 1 1 C = P S = P E ( S ) 2 2 2 2 K 1 C = P S = P E ( S ) = P E ( S ) 2 2 2 2 K 1 2 K 1 C C = P P 2 2 2 2 31/37
OFB 모드 계속 오류확산 암호화하기전에평문블록 P i 에오류 P i 에오류가발생하면 C i 에같은위치에오류가발생하며, 다른암호문블록에는영향을주지않는다. 마지막블록을 MAC 으로사용할수없다. P 1 P 2 P 3 P 4 C 0 C 1 C 2 C 3 C 4 P 5 C 5 C = P E ( S ) P E ( S ) = C C 3 = P ( ) 3 EK S3 = C3 P 1 P 2 P 3 P 4 P 5 C 0 C 1 2 2 K 1 2 K 1 2 C 2 C 3 C 4 C 5 P = C S = P E ( S ) E ( S ) = P 2 2 2 2 K 1 K 1 2 P = C S = P E ( S ) E ( S ) = P 3 3 3 3 K 2 K 2 3 P 1 P 2 P 3 P 4 P 5 32/37
OFB 모드 계속 암호화된이후암호문블록 C i 에오류 P i 에같은위치에오류가발생하지만다른암호문블록에는영향을주지않는다. P 1 P 2 P 3 P 4 C 0 C 1 C 2 C 3 C 4 C 0 C 1 C 2 C 3 C 4 P 1? P 3 P 4 채우기가필요없음 P 2 = C 2 EK( S1) =? EK( S1) =? P = C S = P E ( S ) E ( S ) = P 3 3 3 3 K 2 K 2 3 P n 이 k 바이트이면 E K (S n ) 의 k 바이트만사용 33/37
8 비트 OFB 모드 shift register shift register K 블록블록암호 K 암호 k i k i p i c i c i p i 이처럼하는것을내부피드백 (internal feedback) 이라한다. CFB 와달리동기화를자체회복할수있는기능이없다. 34/37
Counter 모드 최근에많이사용되고있는암호모드 CFB, OFB 와만찬가지로암호화연산만사용 N i N i +1 N i N i +1 E K E K E K E K P i-1 P i C i-1 C i C i-1 C i P i-1 P i C = P S, S = E ( N ) P = C S, S = E ( N ) i i i i K i i i i i K i 35/37
Counter 모드 계속 초기 N 0 과증가함수는공개되어있다. 증가함수는보통 +1 을사용한다. 하지만초기 N 0 은항상다른것을사용해야한다. 오류확산 같은것을사용하면 OFB 와유사한결과를초래한다. 암호화하기전에평문블록 P i 에오류 P i 에오류가발생하면 C i 에같은위치에오류가발생하며, 다른암호문블록에는영향을주지않는다. 암호화된이후암호문블록 C i 에오류 P i 에같은위치에오류가발생하지만다른암호문블록에는영향을주지않는다. 36/37
OFB vs. Counter 모드 S i 를계산하는방법을제외하고는동일하다. 안전성측면 OFB 의경우에는 S i 를알아도키를모르면 S i+1 를계산할수없다. Counter의경우에는 N i 를알면N i+1 를계산할수있지만 OFB와마찬가지로키를모르면 S i 나 S i+1 를계산할수없다. 효율성측면 OFB 의경우에는각 S i 를순차적으로계산할수밖에없다. i 카운터의경우에는각 S i 를독립적으로계산할수있다. 37/37
암호화모드의비교 앞과뒤에서블록을삭제할수있다. 특정암호문블록의조작은해당평문에영향을준다. ECB CBC CFB OFB Counter 평문패턴의은닉 평문의조작 전처리여부 Enc:( ) Enc:( ) Enc:( ) Enc:( ) Enc:( ) 병렬수행 Dec:( ) Dec:( ) Dec:( ) Dec:( ) Dec:( ) 오류확산단일블록 P i 전체 P i 특정 P i 특정 P i 특정 P i+1 특정 P i+1 전체 블록보다작은단위암호화 블록을교체 / 삽입 / 삭제가가능하다. 현암호문블록을보기전에이전암호문블록을미리복호화해놓을수있다. 암호화할메시지가없는상태에서도 S i 들을미리만들어놓을수있다. 38/37
암호화모드의선택 ECB 는가장빠른모드이지만암호해독하기가장유리한방법이다. 따라서일반메시지를 ECB 모드로암호화하는것은바람직하지않지만암호키와같은크기가작은랜덤한값은문제가없다. 보통파일과같은많은양의데이터를암호화할때에는 CBC를사용한다. 최근에 CBC 대신에 Counter 모드를많이사용한다. 스트림암호방식으로암호화하고싶을경우에는보통 CFB 모드를사용한다. 39/37