[보안] 대칭키 암호 알고리즘

출처 : http://destiny738.tistory.com/m/post/view/id/468

* 대칭키 알고리즘

 - 스트림 암호와 블럭 암호가 존재

 

* 스트림 암호

 

 - n bit의 키를 이용하여 긴 키 스트림(Long key stream)을 생성하여 Message와 XOR하여 사용한다.

 - 송신자와 수신자는 동일한 스트림 알고리즘과 Key Stream생성값(Key)값을 알고 있어야 한다.

 - 스트림 암호 중에서 A5/1과 RC4를 소개한다.

 ⓐ A5/1

  - HW로 구현되는 스트림 암호를 사용한다.

  - bit단위로 키 스트림이 생성된다.

  - 64bit의 길이를 가진 Key를 사용한다. Key는 3개의 Linear feedback shift register로 구성된다. 

  

  - 알고리즘

   ㄱ. m = maj(x[8], y[10], z[10])                 // maj : 집단에서 가장 많은 수를 뽑아내는 함수

   ㄴ. If ( x[8] == m ) {                                // majority 값과 x의 8번째 bit의 값이 같으면 

          t = x[13] XOR x[17] XOR x[18];         // t값을 구한다. 

          for ( i = 18 ; i > 0 ; i-- ) x[i] = x[i-1];  // key값을 한칸씩 옆으로 민다.

          x[0] = t;                                          // 새로구해진 key 값을 0번째 bit 값에 적용한다.

        } 

   ㄷ. If( y[10] == m ) {

          t = y[20] XOR y[21];

          for ( i = 21 ; i > 0 ; i-- ) y[i] = y[i-1];  // key값을 한칸씩 옆으로 민다.

          y[0] = t;                                          // 새로구해진 key 값을 0번째 bit 값에 적용한다.

        }

    ㄹ. If( z[10] == m ) {

          t = z[7] XOR z[20] XOR z[21] XOR z[22];

          for ( i = 22 ; i > 0 ; i-- ) z[i] = z[i-1];  // key값을 한칸씩 옆으로 민다.

          z[0] = t;                                          // 새로구해진 key 값을 0번째 bit 값에 적용한다.

        }

     ㅁ. Key stream 값을 생성 : x[18] xor y[21] xor z[22]

     ㅂ. ㄱ으로 돌아가서 다시 실행한다. (Message의 길이만큼 반복)

 ⓑ RC4 

  - byte단위로 키스트림이 생성된다.

  - SW로 구현하기에 최적화 되있다.

  - 0부터 255바이트 사이의 랜덤한 길이로 Key를 사용한다.

  - 일회성 암호와 같이 생성한 스트림 바이트를 사용한다.

  - 처음의 키는 반듯이 패기해야한다.

  - 알고리즘

   > N is key length.

   ㄱ. Reset

    for ( i = 0 ; i < 255 ; i++ ){

       S[i] = i;

       K[i] = key[i%N]

    }

    j = 0;

   ㄴ. Shuffle array

   for ( i = 0 ; i < 255 ; i++ ){

      j = ( j + S[i] + K[i] ) % 256;

     swap(S[i], S[j]);

   }

   i = j = 0;

  ㄷ. Make stream

  i = (i+1) % 256;

  j = (j+S[i]) %256;

  swap(S[i],S[j]);

  t = (S[i] + S[j])%256;

  keystreamByte = S[t];

* Feistel cipher

 

 - Message를 블럭단위로 짤라서 암호화 한다.

 - 암호문 : 평문에 반복되는 함수를 적용한 것

  > Feistel cipher 구조, 방식이라고한다.

  > 매 단계 같은 방식으로 섞는다.

  

* DES(Data Encryption standard)

 - 미국 정부 표준

 - IBM의 Lucifer 알고리즘을 수정

 - Block 길이 : 64bit, Key 길이 : 56bit, 16번 섞기를 함.

 

 - 안전성

  ~ Back door가 없다

  ~ S-box에 안전성이 달려 있다.

  ~ 공격을 위해선 exhaustive key search를 사용

  ~ Key길이가 짧고, 현대 컴퓨터의 발달로 exhaustive key search로 찾아 낼 수 있다.

  ~ AES의 탄생(Key길이가 128bit로 늘어남)

* Double DES

 - AEs이전에  DEs를 계속 사용하기 위해서 만들어진 방법

 - 키의 길이를 2배로 늘린다. 하지만 같은 키로 2번을 암호화 하는 것이므로, 실질적인 키의 길이는 56bit로 변화가 없다.

 - C = E(E(P,K),K)

 - single DEs와 같은 계산량을 통해서 해독이 가능하므로 안전하지 못하다.

* Triple DES

 - 키의 길이를 3배로 늘리는 것이다.

 - 하지만, 사용되는 키는 2종류 이므로 실제 키길이는 112bit라고 할 수 있다.

 - C = E(D(E(P,K1),K2),K1)

 - 112bit의 키길이로 현재 사용해도 안전한 알고리즘이다. 하지만, AEs의 탄생으로 사용추세가 줄어들고 있다.

* Advanced Encryption STD(AES)

 - 3DES의 단점 : 효율적인 소프트웨어 코드가 없고, 속도가 느리다. 블럭크기가 작다.

 - AES 모집시 요구사항

  > 저작권 없이 전세계에서 사용할 수 있는 알고리즘

  > 대칭키 방식

  > 블럭 크기는 최소한 128bit, 키 길이는 128-, 192-, 256bit로 가변

 - 안전성과, 견고성, 속도를 사용하여 알고리즘을 체택하였다.

 - Rijndael(초기 버전 이름)

  > 가변의 블럭 크기 및 키 크기

  > 블럭과 키의 키기에 따라 반복 횟수가 정해진다.

 - 최종 선택된 AES

  > 키의 길이는 128, 192, 256bit을 사용한다.(128bit이여도 안전하므로 128bit을 많이 사용한다.)

  > 블럭크기는 128bit로 고정되었다. 

  > 이에 따라 반복횟수는 키의 길이에 따라 각각 10, 12, 14로 고정되게 되었다.

 - DES와의 비교

  > 페이스텔 암호형태가 아니다.

  > 반복적인 블럭 암호이다.(공통점)

 - 알고리즘

  ㄱ. AES AddRoundKey

    ~ Round Key를 key schedule 알고리즘을 이용하여 생성한다.

    ~ 평문 위치와 같은 위치에 있는 키를 XOR 계산을 한다.

  ㄴ. AES BytesSub(S-box 기능)

    ~ S-box를 이용하여 문자를 치환 시킨다.

  ㄷ. AES ShiftRow(P-box 기능)

    ~ 1행은 그대로, 2행은 8bit, 3행은 16bit, 4행은 24bit을 좌측으로 shift시킨다.

  ㄹ. Mix Column

    ~ 각 행을 섞는다.(S-box)

 - AES의 복호화 : 복호화를 하기 위한 역기능이 존재한다.

  ⓐ AddRoundKey 역 : 자신이 역이다.

  ⓑ MixColumn : lookup table을 통해서 찾을 수 있다.

  ⓒ ShiftRow : cyclic shift를 통해서 원래 모습을 찾을 수 있다.

  ⓓ ByteSub : lookup table을 통해서 찾을 수 있다.

* Block Cipher Modes

 - 여러개의 블록으로 구성된 메세지를 어떻게 암호화 할 것인가?

 - ECB(Electronic Codebook mode), CBC(Chiper Block Chaning mode), CMR(Counter Mode mode)가 존재한다.

 - 여기서 CTR과 ECB는 병렬 처리, 랜덤 엑세스가 가능하다.

 ⓐ ECB

  - 고정된 Key K를 갖고 모든 블럭을 암호화 한다.

  - 공격자에게 정보를 줄 가능성이 크다.

  - 전자 코드북을 만드는 방법과 유사

  - 동일한 평문의 블럭을 동일한 암호문이 나오기 때문에 문서의 형태가 나타날 수 있다.

  - 암호문의 블럭 순서를 바꿔서 다른 의미의 문장으로 변환될 가능성이 크다.

 ⓑ CBC 

  - 이전에 생성된 암호문을 Key와 함께 XOR하여 다음 암호문을 생성(처음에는 Initial Vector를 이용하여 생성한다)

  - 동일한 평문 블록도 서로 다른 암호문 블록으로 변환된다.

     

  

  - 전송시 에러가 발생할 경우를 생각해보자.

   > P1, P2, P3, P4를 각각 암호화하여 C1, C2, C3, C4로 전송했다고 하자.

   > 하지만 받는 전송중 에러가 발생하여 C1, G, C3, C4로 받았다고 하자.

   > 이때 받은 사람은 다음과 같이 계산을 할 것이다.

    P1 = Ci(Initial vector) XOR D(C1, Key)  // P1으로 복구가 된다.

    P2 = C1 XOR D(G, Key)  // P2로 복구가 되지 않는다.

    P3 = G XOR D(C3, Key)  // P3로 복구가 되지 않는다.

    P4 = C3 XOR D(C4, Key) // P4로 북구가 된다.

   > 여기서 에러가 발생할 경우 에러가 난 자신의 블럭과 다음 블럭에만 영향을 끼치는 것을 알 수 있다.

   > 오류의 확산 범위가 좁다.

 ⓒ CTR

  - CBC와 비슷한 방식이지만, 암호문을 다시 재사용 하는 것이 아니라, Initial Vector의 값을 shift하면서 XOR연산을 한다.

 

* MAC

 - Message Authentication Code

 - 데이터 무결성을 위해서 MAC이라는 값을 사용한다.

 - MAC을 생성하는 방식은 2가지가 존재한다.

  ⓐ CBC를 사용할 경우, 맨마지막 블럭을 암호화한 결과물을 MAC으로 붙여서 보낸다.

   > 수신자는 동일한 계산을 수행해서 MAC과 자신이 계산한 값을 비교한다.

   > 마지막에 암호화된 Cn과 MAC이 같으면 안되기 때문에(공격자에게 단서제공), MAC전용 Key가 또 필요하다.

  ⓑ Hash 함수를 이용하여 MAC 메세지를 만들어 붙여서 보낸다. (digest message를 생성한다.)

   > ⓐ의 단점에 의해서(MAC전용 Key필요) ⓑ방법을 다 많이쓴다.

* 키분배

 - 대칭키를 분배하는 방법이 필요하다.(추후에 다시 설명, 또는 네트워크 컴퓨팅의 보안 Part를 참조하길 바란다)