본문으로 바로가기

대칭키알고리즘

category IT Tech/Security 2019. 3. 5. 03:04
* 대칭키 알고리즘
 - 스트림 암호와 블럭 암호가 존재
 
* 스트림 암호
 



 - 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필요) ⓑ방법을 다 많이쓴다.

* 키분배
 - 대칭키를 분배하는 방법이 필요하다.


'IT Tech > Security' 카테고리의 다른 글

How to Hack Wi-Fi: Get Anyone's Wi-Fi Password Without Cracking Using Wifiphisher  (0) 2019.03.05
S-DES  (0) 2019.03.05
RC4 알고리즘  (0) 2019.03.05
RSA  (0) 2019.03.05
앨리스와 밥  (0) 2019.03.04