Symmetric Encryption (1) - DES

고둑·2021년 10월 22일
1
post-thumbnail

대칭키 암호화 기법

  • 대칭키 암호화 기법은 암호화/복호화에 같은 키를 사용하는 기법이다.

  • Symmetric encryption, conventional encryption, single-key encryption, secret-key encryption 모두 대칭 암호키를 나타내는 말이다. 상황에 따라서 혼용이 가능하다.

  • 대칭키 암호화를 사용하기 위해서는 두 가지 필수사항이 존재한다.

    • 강력한 암호화 알고리즘 :
      Known algorithm and a number of ciphertext (Weak requirement)
      Known algorithm and a number of ciphertext and plaintext pair (Strong requirement)

    • 비밀스러운 키 공유 :
      수신자와 발신자 모두 비밀 키의 복제본을 수신받아야하고 이 과정에서 키는 매우 안전하게 보관되어야한다.
      비밀 키가 공개되면 그 키로 암호화된 모든 연결은 복호화가 가능해진다.

대칭키 암호화 공격

  • Cryptanalytic attack을 하려면
    • 알고리즘 자체의 취약점을 이용하거나
    • plaintext의 일반적인 특징을 이용하거나 (예를 들어 영어 알파벳 사용 빈도 같은 거)
    • 브루트포싱
      • 성공적인 브루트포싱 공격을 위해서는 평균적으로 가능한 모든 조합의 절반을 시도하면 된다.
      • 브루트포싱을 성공하기 위해서는 평문을 평문으로 인식할 수 있어야한다. 따라서 zip파일같이 확인 불가능한 plaintext를 가지고 있는 파일은 공격이 더욱 힘들다.

대칭키 암호화 알고리즘

rkwkd

  • DES
  • Triple DES
  • AES

DES (Data Encryption Standard)

1975년에 IBM에서 개발하고 1979년에 미국 NBS(National Bureau of Standards, 현 NIST)가 국가 표준 암호 알고리즘으로 지정한 대칭키 암호 알고리즘.

  • 64비트의 평문을 64비트의 암호 문으로 암호화하는 대칭키 암호 알고리즘이다.
  • DES의 키는 64비트이나 8비트는 정보의 전달 과정에서 오류가 생겼는지를 검사하는 Parity bit이므로 실질적인 키는 56비트이다.
  • 이때 암호문은 16번의 반복을 통해 만들어지는데 이때 16번의 반복동안 라운드 함수를 적용하게된다.
  • 이때 라운드 함수에 적용되는 키는 키 스케줄에 의해 생성된 라운드 키를 사용한다.

DES 암호화 과정

  1. Initial permutaion (초기 전치)
    • Plaintext를 64비트씩 나누어 PT => M1, M2, ... 로 설정한다
    • 64비트 블럭으로 나뉘어 저장된 Plaintext들을 초기 치환(IP)를 거쳐 IP(M) => P1, P2, ...로 바뀐다.
    • IP는 아래와 같은 방법으로 1번째 자리에 58번째 비트를 넣는거와 같이 블록 전체를 치환한다.
  2. 16 rounds of Calculating functions
    • 64비트의 블럭을 좌우 32비트씩 나누고 각각 L0, R0에 대입한다.
    • L0, R0을 가지고 L1=R0, R1=L0⊕f(R0,K1)로 L1과 R1을 만든다.
    • 과정을 16번 반복하고 그 과정에서 과정이 반복될 수록 K1~K16까지 사용한다.
  3. Final permutation (역 전치)
    - 16라운드를 진행하여 L16과 R16을 얻고난 다음 좌우를 바꾼 64비트 (R16,L16)에 아래와 같이 초기 전치 IP의 역 전치 IP-1를 적용한다.

DES의 f함수

DES를 진행하다보면 R1=L0⊕f(R0,K1)이란 식으로 R1을 구하는 것을 볼 수 있다.
이때 사용하는 f함수의 작동 방법은 아래와 같다.

  • 입력받은 32비트 값을 아래와 같이 확대 전치(E)를 이용하여 48비트로 확장시킨다.
  • 키 스케줄을 통해 만들어진 48비트의 라운드 키와 확대 전치를 통해 48비트가 된 값을 xor(⊕)연산을 해준다.
  • S-Box를 통해 치환을 하여 48비트 48비트의 값을 32비트로 치환시킨다.
  • 마지막으로 아래와 같이 평형 전치(P)를 이용해 결과 값을 함수의 리턴 값으로 출력해준다.

DES의 S-Box

S-Box를 통해 48비트 크기의 암호화 진행중인 무언가를 32비트의 무언가로 치환시키는데 사용하는 알고리즘이다.

S-Box에 들어가기 직전 48비트는 각각 6비트씩 8개로 쪼개지게되고 아래 그림과 같은 방식으로 4비트로 치환된다.

치환된 데이터를 합치면 4비트씩 8개 총 32비트로 치환되게된다.

DES의 Key-schedule

공유하는 64비트의 대칭 키를 기반으로 16개의 48비트인 sub-key(라운드 키)를 만드는 알고리즘이다.

  • 64비트의 대칭 키에서 키 전치(PC 1)을 이용하여 8비트의 Parity 비트를 제거하고 56비트의 실질적인 키를 이용한다. 8, 16, 24, 32, 40, 48, 56, 64번째 비트 제거

  • 이렇게 남은 56비트를 왼쪽, 오른쪽 각각 28비트씩 따로 저장하고 각 라운드마다 스케줄에 따라 지정된 비트를 좌측으로 쉬프트하고 다시 합친다. (1,2,9,16 번째는 1번, 나머지는 2번 쉬프트한다.)

  • 축약 전치(PC 2)를 이용하여 기존 64비트의 재결합된 비밀 키를 48비트로 전치한다.
    9, 18, 22, 25, 35, 38, 43, 54번째 비트 제거

    이런 방식을 16번 반복하여 16개의 48비트 라운드 키를 만들어 낸다.

    DES의 취약점

  • IBM에서 만든 Lucifer를 NSA에서 개량해서 만든 S-Box가 DES의 전신인데 이 DES의 S-Box에 암호학에서 흔하게 사용하는 'nothing up my sleeve number'를 사용하지 않고 근본없는 이상한 숫자를 집어넣었다. 이걸 계기로 NSA가 DES에 백도어를 설치했다는 의심을 하였지만 지금까지 연구한 바로는 취약점이 발견되지 않았다. 하지만 가능성이 0은 아니다.

  • DES에 가장 효과적인 공격 방법은 브루트 포싱이다.

  • 요즘 컴퓨팅 성능의 비약적인 발전으로 64비트의 DES는 매우 취약해졌다. 실제로 1998년 7월, EFF(Electronic Frontier Foundation)에서 DES 암호화가 적용된 암호를 22시간 15분만에 해독했다고 발표를 했다.

Triple DES (A.K.A 3DES)

DES의 취약점에서 볼 수 있듯이 DES는 더 이상 안전한 암호화 알고리즘이 아니게 되었고 차세대 암호화 알고리즘의 필요성이 대두되었다.
이에 따라서 NIST는 DES의 취약점이 개선된 새로운 암호화 알고리즘인 AES의 공모를 받게되었다.
하지만 암호화 알고리즘은 취약점에 대한 충분한 검증이 있어야하기 때문에 무턱되고 새로운 암호화 표준으로 새로운 알고리즘을 쓰기에는 너무 큰 리스크가 있었다. 그래서 NIST는 DES와 AES 사이의 간극을 채우기위해 기존에 이미 검증된 DES를 3번 이용해 암호화 하는 Triple DES 방식을 발표하였고 사용을 권고하였다.

Triple DES의 암호화 방식

3DES의 암호화 방식을 식으로 나타내면 CT = E(D(E(PT, K1), K2), K3)이다.

  • 3DES의 암호화 방식은 총 2가지 방식로 나뉘는데 키를 2가지 쓰는 방식과 3가지 쓰는 방식으로 나뉜다.
    • 2가지 키를 이용하는 방식은 위 그림에서 K1과 K3의 값이 같은 경우이다. 인코딩을 같은 공개 키로 시작과 끝에 한 번씩 하는 방식이다.
      • 일반적인 상황에서는 56*2 = 112비트 키로도 충분히 안전하기때문에 많은 곳에서 2개의 키를 이용하고 있다.
    • 3개의 키를 이용하는 경우는 키의 크기는 168비트로 기존 2가지 키를 사용하는 방식보다 보안이 뛰어나지만 연산 시간이 더 소요된다.
  • 1개의 키로 3DES를 돌리는 바보같은 짓은 하지말자. 1개의 키로 암호화, 복호화, 암호화를 거치면 걍 DES로 암호화한 것과 같아진다. 즉 뻘짓이란 소리다.

Triple DES의 취약점

기존에 사용하던 DES 알고리즘을 이용하므로 큰 변화가 없어 편하기는 하지만 결과적으론 기존에 1번 돌리던 알고리즘을 3번 돌리는 것으로 처리속도 문제(성능)의 하락폭이 3배에 근접했다.
그리고 실시간으로 진화하는 컴퓨터의 연산 속도를 따라가기에는 태생이 DES이기 때문에 역부족이였다. 따라서 Triple DES는 AES가 정착하기 전까지 DES에서 벗어나기 위한 하나의 징검다리의 의미로 접근하면 편할것이다.

AES는 다음에...ㅎ

profile
문워킹은 하지말자

0개의 댓글