[정보보안] 7. 블록 암호 - DES

평문을 암호문으로 바꾸기 위해 암호 알고리즘이 적용된다. 암호 알고리즘은 암호화 과정과 복호화 과정을 위해 어떤 키를 사용하는지에 따라 여러 방법들이 제안되고 있다.

중요사항

1. 암호화 키와 복호화 키가 같은 경우와 다른 경우
2. DES를 적용한 암호화 과정 - P box, S box, E box
3. DES의 한계를 극복하기 위한 방법들

블록 암호

일정한 크기의 블록 단위로 처리하는 암호 알고리즘을 블록 암호라고 한다.

• 대표적으로 DES가 있다.
• DES는 평문을 64비트 블록으로 나누고 각각을 암호화한다.

1. DES(Data Encryption Standard)의 등장 배경

• IBM 사에 의해 Lucifer 암호로 시작했고 이후 FIPS와 NAS에서 인정받았다.
• 당시의 키 길이는 128비트였는데 너무 길다고 판단되어 64비트, 56비트로 축소 조정되었다.
• DES는 내부 알고리즘으로 S-Box를 사용하는데 이는 비공개이다.
• 64비트 블록 단위로 암호화하며 56비트(실제 키의 길이는 48비트이며 나머지 8비트는 패리티비트이다)의 키를 사용하며 16라운드를 반복 수행한다.
• 미국 연방정부 표준으로 채택되어 5년마다 검증하고 국가 표준을 변경시킨다. 세계적으로 금융기관에서 많이 사용된다.

→ 64비트의 평문을 56비트의 키로 암호화하여 64비트의 암호문을 출력한다.

2. DES의 암호 알고리즘

전치식과 대치식을 기본으로 하여 이 전치와 대치를 적당히 조절하여 조합한 처리를 16 라운드로 반복함으로써 평문의 비트 패턴을 뒤섞어 의미를 알수 없는 암호문으로 변환한다.

• 64비트 평문을 64비트 암호문으로 암호화하는 대칭 암호 알고리즘이다.
• 키의 비트 길이는 56비트(실제 사용하는 키의 길이 = 48비트)
• 64비트 평문을 하나의 단위로 모아서 암호화한다 → 블럭 암호

3. DES의 Building Block

• SP network(Substitution - Permutation Network) 모형

1. 입력을 L과 R로 나눈다.

• 블록 암호의 이론적 배경은 Shannon의 이론에 근거한다.
  • 혼돈(Confusion)과 확산(Diffusion)
    • 혼돈: 전치를 의미한다. 평문을 구성하는 각각의 비트 정보가 여러 개의 암호문 비트에 의해 분산되는 성질을 나타낸다. 평문과 암호문 간의 관계를 숨기는 성질이다.
    • 확산: 대치(S-Box)를 의미한다. 키의 작은 변화가 암호문에 어떤 변화를 일으킬 것인지 예측할수 없는 성질을 말한다. 키와 암호문 간의 관계를 숨기는 성질이다.
    • 

4. 암호화 구조와 동작 - Feistel 구조

Feistel 구조

비대칭의 순차적 진행과 XOR로 구성된 구조이다.

1. R을 그대로 R로 보낸다.
2. R을 라운드 함수 F로 보낸다.
3. 라운드 함수 F는 R과 서브 키 K1을 입력으로 사용하여 랜덤하게 보이는 비트열을 계산한다.
4. 얻어진 비트열과 L을 XOR한다.
5. 그 결과를 다음 라운드의 L로 사용한다.

• 특징
  1. 원하는 만큼 라운드 수를 늘릴 수 있다.
  2. 라운드 함수 F에 복호화 함수를 사용해서 복호화가 가능하다.
  3. 암호화와 복호화를 완전히 동일한 구조로 실현할 수 있다.

5. DES의 암호화 과정

• 64비트의 평문을 56비트의 키를 적용하여 64비트의 암호문을 만들어낸다.
• 대치와 전치(치환)의 동작이 수행된다.
  • 대치: 어떤 비트들의 유형을 다른 비트들로 변환
  • 치환: 비트들의 순서를 재배열함

1. 64비트 평문은 비트열의 순서를 재배열하는 초기 치환을 수행한다.
2. 초기치환을 통해서 얻어진 64비트가 각 32비트로 된 두 개의 L과 R로 분할되고 R에 대해 E-Box, S-Box, P-Box(선택적)을 통과시키고 L과 XOR한 값을 다음 라운드의 R로 사용한다. 다음 라운드의 L은 처리 과정을 거치기 이전의 R로 사용한다.
3. 이 과정을 16회 반복한다. 단, 마지막 라운드에서는 L과 R을 교환하지 않는다.
4. 16회 반복 후 생성된 L과 R에 대하여 서로 위치를 교환된 후 역 초기치환을 적용하여 64비트의 암호문을 생성한다.

DES의 1라운드 동작 과정

Feistel 구조의 특징

1. 비대칭 구조이다.
   • Mixer: 키 기능과 XOR 연산 부분을 구성하는 부분. 모든 라운드에서 수행
   • Swapper: L과 R의 출력값을 swapping하여 다음이 입력값으로 출력하는 부분. 마지막 라운드에서는 수행하지 않음.
2. E-Box와 S-Box의 입력과 출력이 서로 다르다. → 비선형 함수
3. 키 스케줄
   • 키의 길이는 56비트를 2등분하여 28비트의 좌우로 이동하여 설정한다. 매 라운드마다 좌우를 압축한 후 평문의 R 영역으로 들어가게 된다. 압축된 키 배열은 48비트가 된다. 이 순환 과정을 16번 반복하며 매 라운드의 56비트의 키가 형성되어 반복한다.

DES의 암호화 구조

1. 2개의 P-Box 배치(선택)
2. Round에서 E-Box, S-Box 수행
3. 16번의 Round 수행
4. Round Key Generator 수행

6. DES의 암호화 과정 해석

1. 초기 치환과 종료 치환을 위한 작업 → P-Box(선택적)

P-Box가 다음과 같이 주어진다면 다음과 같이 치환된다.

해당 인덱스에 주어진 번호의 순서대로 치환된다.

58 50 42 34 26 18 10 02        40 08 48 16 56 24 64 32

60 52 44 36 28 20 12 04        39 07 47 15 55 23 63 31

62 54 46 38 30 22 14 06        38 06 46 14 54 22 62 30

64 56 48 40 32 24 16 08   →  37 05 45 13 53 21 61 29

57 49 41 33 25 17 09 01        36 04 44 12 52 20 60 28

59 51 43 35 27 19 11 03        35 03 43 11 51 19 59 27

61 53 45 37 29 21 13 05        34 02 42 10 50 18 58 26

63 55 47 39 31 23 15 07        33 01 41 09 49 17 57 25

2. 확장 E-Box

32비트 중 일부분을 중복 사용하여 치환 작업을 수행한다.

• 32비트의 R은 E-Box를 통과하면 48비트로 확장된다.

이러한 방식은 다음과 같이 총 비트를 4로 나누고 그 비트열의 양 끝을 양옆의 비트열에 추가한 것이다.

3. 암호 박스(S-Box)

S-Box에 의해 48비트(6비트의 입력으로 구성된 8개의 모듈)가 32비트(4비트 출력으로 구성된 8개의 모듈)로 대체된다.

• S-Box는 표준으로 8개의 종류가 제시되며 각각은 6비트를 입력으로 받아들여 4비트 출력을 수행한다. 이렇게 입력과 출력의 비트 수가 다른 함수를 비선형 함수라고 한다.

아래는 S-Box의 예시이다.

• S-Box는 차분 공격, 선형 공격으로 인해 5년마다 미국 NIST에 의해 갱신된다(DES Challenge).

S-Box 동작

• 암호 적용
  • S로 입력되는 첫 번째 비트와 마지막 비트는 2비트로 구성하여 행을 특정하는데 사용되고 중간의 4비트는 열을 특정하는데 사용된다.
  • S1의 입력값이 100011일 때 출력값은?
  • → 양 끝 비트는 11이므로 3번째 행이며 중간 4비트는 1이므로 3번째 행의 1번째 값을 출력한다. 즉 12가 출력된다. 이때 4비트로 출력해야 하므로 1010이 출력된다.
  • S8의 입력값이 000000일 때 출력값은?
  • → 양 끝 비트는 00이므로 0번째 행이며 중간 4비트는 0이므로 0번째 행의 0번째 값을 출력한다. 즉 13이 출력된다. 이때 4비트로 출력해야 하므로 1011이 출력된다.

7. DES에 대한 공격(전사 공격)

차분 해독법

• 블록 암호 해독법으로 Biham과 Shamir가 개발했다.
• 평문의 일부를 변경할 때 암호문이 어떻게 변화하는지 관찰하여 조사하는 암호 해독법이다.

선형 해독법

• 마츠이가 개발했다.
• 평문과 암호문 비트를 몇 개 정도 XOR해서 0이 되는 확률을 조사하는 암호 해독법이다.

8. 해독법에 대한 방안

Double DES

• 암호화 과정을 두 번 반복하여 수행한다.

Triple DES

• 암호화 - 복호화 - 암호화의 과정을 수행한다.
• DES는 전사 공격
• DES는 전사 공격으로 현실적인 시간 내에 해독된다. 따라서 DES를 대신할 블록 암호가 필요했다. 이를 위해 개발된 것이 DES를 3번 중첩한 Triple DES이다.

현황

• 현재도 은행 등에서 Triple DES를 사용하고 있다.
• 처리 속도는 3단이라 빠르지 않다.
• 안전성 면에서도 풀려버린 사례가 있다.
• 우리나라 국가 표준은 SEED 및 ARIA이다.

9. DES 분석

1. 키에 대한 공격

• 1990년대 56비트, 64비트 기준은 현대 기술 수준이 높아져 기밀성과 가용성을 위협한다.
• 1990년 Crypto 90에서 논문이 발표되어 입출력의 연관성을 계산하여 평문이 읽혀졌다.
• linear attack으로 일본의 암호학자 마츠이에 의해 S-Box가 공개되었다.
  • 입력 비트와 출력 비트의 상관관계성을 해석했다.
• 키의 비트가 56비트이므로 전사 공격에 취약하다.
• Triple DES → 3개의 서로 다른 키를 사용하여 3번 암호화한다.

2. DES의 취약성

• 취약 키
  • 0101 0101 0101 0101 이 입력되면 0000 0000 0000 0000 이 출력된다.
  • 1F1E 1F1E 1F1E 1F1E 이 입력되면 0000 0000 FFFF FFFF 가 출력된다.
  • E0E0 E0E0 F1F1 F1F1 이 입력되면 FFFF FFFF 0000 0000 이 출력된다.
  • FEFE FEFE FEFE FEFE 이 입력되면 FFFF FFFF FFFF FFFF 가 출력된다.
• 준 취약키
  • Rounding 수행 시 오직 2가지 다른 형태의 라운드 키만 생성한다.

Key Clustering: 동일한 평문을 서로 다른 두 키로 암호화했을 때 같은 암호문이 나오는 경우

3. Avalanche Effect(쇄도 효과)

암호 알고리즘에서 입력값에 미세한 변화를 줄 경우, 출력값에 상당한 변화가 일어나는 특성이다.

4. 완벽성

• 확산(Diffusion): 키의 작은 변화가 암호문에 어떤 변화를 일으킬 것인지 예측할수 없는 성질을 말한다. 키와 암호문 간의 관계를 숨기는 성질이다. P-Box이다.
• 혼돈(Confusion): 평문을 구성하는 각각의 비트 정보가 여러 개의 암호문 비트에 의해 분산되는 성질을 나타낸다. 평문과 암호문 간의 관계를 숨기는 성질이다. S-Box이다.
• 이 두 가지 효과가 일어나는 성질을 완벽성 효과라고 한다.

10. DES의 대체제

DES가 깨진 이후로 미국은 세계적으로 AES 프로젝트를 제안했다. DES를 대신할 암호 방법을 구하기 위해서였다. 요구 조건은 다음과 같다.

• 잘 알려진 공격에 대한 저항성
• 넓은 범위에서의 코드 선택성과 그에 따른 처리 속도
• S-Box의 병렬 적용 가능
• 기밀성, 유연성, 효율성

11. 블록암호(대칭 키 암호 알고리즘)의 종류

• IDEA
• FEAL
• RC2, 4
• SKIPJACK
• SEED
• AES