대칭 키 암호(Symmetric-key algorithm)

대칭 키 암호

• 암호화와 복호화에 같은 암호를 사용하는 방식으로 ^[각주:1] 혼돈(confusion)과 확산(diffusion)^[각주:2] 두 개념을 만족하기 위해 P-Box와 S-Box 그리고 그 밖의 구성요소를 결합하여 설계한다.
  이렇게 구성된 암호를 합성 암호(Product Cipher)라 하며, 반복적으로 사용되는 합성 암호를 라운드(Rounds)라고 한다.
• 대칭 키 암호화는 블록^[각주:3]을 암호화하는 블록 암호(Block cipher)와 연속적인 데이터를 암호화하는 스트림 암호(Stream cipher)가 있다.^[각주:4]
• 너무 오래 되 취약점이 발견된 DES와 1997년 NIST의 공모를 통해 현 미국 표준 방식이 된 AES,^[각주:5] AES와 함께 후보에 올랐던 MARS, RC6, Serpent, Twofish 등이 이에 속한다.
• 관용 암호 방식, 비밀 키 암호 방식, 단일 키 암호 방식과 같은 뜻이다

---

블록 암호

• 암호 키와 알고리즘이 블록 단위로 처리되는 암호화 방법이다.
• 블록 암호는 평문 블록을 암호 블록으로 만들 때 적용되는 방식에 따라 Feistel 암호 구조와 SPN(Substitution-Permutation Network) 암호 구조로 나뉜다.

http://www.ddanzi.com/ddanziNews/3230042

Feistel 구조

• 암호화 방식이 특정 계산 함수의 반복으로 이루어진다.
  이때, 각 과정에 사용되는 함수는 라운드 함수(round function)이라고 부른다.
• DES, blowfish, SEED 등 많은 알고리즘이 Feistel 구조를 가지고 있다.

Feistel 작동 과정

평문을 같은 길이로 나눈 L0와 R0, 암호화에 사용되는 키 K, 키를 사용하는 라운드 함수 F

1. 평문을 같은 길이의 L과 R로 나눈다
2. R과 K로 라운드 함수 R을 실행한다.
3. 라운드 함수 R의 실행 결과와 L을 XOR 연산한다.
4. 다음 연산에서 XOR연산의 결과를 R로써 사용한다.
   즉, L에서 내려온 것은 R로, R에서 내려온 것은 L로 사용한다.
5. 라운드 크기만큼 반복하면 암호문이 완성된다. (복호화 과정은 L과 R만 바꿔주면 된다.)

Feistel의 특징

• SPN 구조에 비해 설계가 자유롭다.
• 암호화와 복호화 과정이 동일하기 때문에 별도의 복호 화기가 필요 없다.^[각주:6]
  다만 복호화 과정의 키 입력 순서는, 암호화 과정과 반대이다. 
• Feistel의 암호 강도를 결정짓는 요소는, 평문 블록의 길이, 키 K의 길이, 라운드의 수이다. 
  충분히 안전하다는 것을 보장하기 위해서, 평문 블록의 길이는 64bit 이상, 키 K의 길이는 64bit 내외, 라운드 수는 16회 이상이어야 한다. 최근에는 128bit 이상의 키를 사용하기를 권장되고 있다.
• 평문을 나눈 길이가 같지 않은 Unbalanced Feistel 구조 또한 존재하며
  Feistel은 블록 암호 외에 다른 암호 알고리즘 에도 사용된다.^[각주:7] 
• 구현 시 스왑(Swap) 단계 때문에 연산량이 비교적 많이 소요된다.

SPN(Substitution-Permutation Network) 구조

• 여러 개의 함수를 중첩하면 개별 함수로 이루어진 암호보다 안전하다는 Shannon의 이론에 근거하여
  S-box와 B-box를 이용한 구조이다.
• AES, ARIA, SHAR 등이 SPN 구조를 따른다.

SPN 작동 과정

문자의 자리를 변경하는 P-BOX, 문자를 규칙에 따라 치환하는 S-BOX, 암호화에 사용되는 키 K

1. 평문과 K를 XOR 연산한다.
2. 연산된 결과를 여러 개의 작은 블록으로 나눈다.
3. 나눠진 각각의 작은 블록들을 S-BOX에 넣어 치환한다.
4. 치환된 결과를 P-BOX에서 문자의 자리를 변경한다.
5. 위 과정을 반복하여 암호문을 완성한다.

SPN의 특징

• Feistel과 다르게 병렬 연산이 가능하지만, 별도의 복호화 모듈을 구현해야 한다.^[각주:8]]
• 비트의 이동 없이 한 번에 암호화/복호화가 가능하기 때문에 Feistel 구조에 비해 효율적으로 설계할 수 있다.
• 암호화 과정이 연산 - S-BOX - P-BOX - 암호문의 과정을 거친다면,
  복호화 과정은 암호문 - 역방향 P-BOX - 역방향 S-BOX - 평문의 과정을 거친다.

---

 스트림 암호

• 한 번에 1비트의 데이터 흐름(스트림)을 순차적으로 처리해가는 암호 알고리즘의 총칭으로 평문과 키 스트림을 XOR 연산 하여 생성한다.
• 일반적인 스트림 암호는 유사난수를 1비트 단위로 생성하고,
  생성된 값과 암호화하려는 각 값을 XOR하여 1비트의 암호화된 자료를 얻는다.
• 비트 단위로 암호화하기 때문에 다른 비트에 영향이 없다. (에러 전파 현상 방지)
• 설계에 따라 스트림 암호 또한 블록 암호만큼의 안전성을 보장하며 블록 암호에 비해 빠른 속도를 가진다.^[각주:9]
• 동기식(독립적) 방식과 비동기식(종속적) 방법으로 나뉜다.

http://www.ddanzi.com/ddanziNews/3230042

동기식 스트림 암호

• 키 스트림은 평문 혹은 암호문에게서 독립적이다.(키 스트림은 평문, 암호문과 어떠한 관계도 없다.)
• 암호화/복호화 동기화가 필요하다.
• OTP(One-Time Pad/Password), 귀환 시프트 레지스터(Feedback Shift Register), 선형 귀환 시프트 레지스터(Linear Feedback Shift Register) 등

비동기식 스트림 암호

• 키 스트림의 각 비트는 평문이나 암호문에 종속적으로 결정된다.
• 암호화/복호화 동기화가 필요없다.
• 블록암호에 CFB(cipher feedback mode)와 결합하여사용된다. 

스트림 암호 설계 시 고려사항

1. 암호화의 연속은 긴 주기를 가져야 한다.

• 의사 난수 생성기는 언젠가 반복되는 비트 스트림을 생산하는 함수를 사용한다.
  즉, 반복 주기가 길다는 것은 암호를 해독하는 것이 그만큼 어렵다는 것을 의미한다.

2. 키 스트림은 진 난수 스트림과 최대한 비슷해야 한다.

• 예를 들어, 1과 0의 개수가 거의 동일해야 한다. 만약, 키 스트림이 바이트의 스트림으로 처리되었다면,
  256개의 모든 가능한 바이트 값은 대략 거의 같은 빈도로 나타나야 한다.
• 키 스트림이 랜덤 하게 나타날수록 암호문은 더 랜덤화 되며, 암호 해독은 더욱 어려워진다. 

3. 전사적 공격에 대응하기 위해서는 키가 충분히 길어야 한다.

• 블록 암호에도 적용할 수 있기 때문에 현재 기술 수준을 볼 때 키 길이가 적어도 128비트인 것이 바람직하다.

구분	스트림 암호	블록 암호
장점	빠른 암호화 속도, 에러 전파현상 없음	높은 확산, 기밀성, 해시함수 등
단점	낮은 확산	비교적 느린 암호화, 에러 발생 가능성
사례	OTP, RC4, FSR, LFSR, MUX generator 등	DSE, IDEA, SEED, MARS, RC6, Serpent, Twofish, AES 등
암호화 단위	비트	블록

---

대칭 키 암호 공격 기법

차분 공격(Differential Cryptanalysis)

• 1991년 Eli Biham(אלי ביהם)과 Adi Shamir(עֲדִי שָמִיר)에 의해 알려진 공격 기법이다.^[각주:10]
• 입력값의 변화에 따른 출력 값의 변화를 이용하는 방법이다.(평문의 일부를 변경하면 암호문이 어떻게 변화하는지)
• 현대 블록 암호는 차분 공격으로부터 안전하게 설계 하지만, 다양하게 변형된 차분 공격 방식이 존재하기 때문에 아직도 블록 암호 분석 시 유용하게 쓰인다.[footntoe] Higher-order differential cryptanalysis, Truncated differential cryptanalysis, Impossible differential cryptanalysis, Boomerang attack등[/footnote]

선형 공격(Linear Cryptanalysis)

• 마츠이 미츠루(松井 充)의 논문에서 처음 공개되었으며, 해당 논문에서는 선형 공격으로 FEAL 암호를 공격하는 방법을 제시했다.
• 암호화 과정에서의 근사적 선형 관계식을 찾는 것을 목적으로 한다.(평문과 암호문 비트를 몇 개 정도 XOR 연산하여 0이 되는 확률을 분석)[footnote]
• 가장 이상적인 즉, 충분히 랜덤 하게 되어 있는 암호화 함수는 평문과 암호문의 XOR연산 결과가 0이 될 확률이 1/2이 되어야 하지만, 암호화 방법에 따라서 이 확률이 1/2과 크게 다를 수 있다.
  이러한 선형 관계식을 찾는 방법은 암호화 과정에 따라 다르다.
  대입-혼합 네트워크(substitution-permutation network)의 경우 혼합 과정은 선형적이며, S-박스에서의 대입 과정에서만 비선형적인 변환이 일어난다.
  따라서 S-박스의 비선형 구조를 선형 과정으로 근사화하는 방법을 찾는 것이 목표가 된다.
• 근사 선형 관계성을 찾았다면, 이를 통해 선택 평문 공격(Chosen-Plaintext Attack)을 수행할 수 있다.
  공격자가 임의로 만든 평문을 암호화할 수 있을 때, 관계식에서 입력한 평문과 암호문이 얼마나 일치하는지 횟수를 측정한다.
  이 횟수를 기반으로 암호화 키 비트들에 대한 관계식을 확률적으로 추정할 수 있다.

전수 공격(Exhaustive key search)

• 1977년 Whitfield Diffie와 Martin Hellman이 제안한 방법으로 암호화할 때 일어날 수 있는 가능한 모든 경우를 조사하는 방법이다.
• 경우의 수가 적을 때는 가장 정확한 방법이지만, 일반적으로는 실현 불가능하다.

통계적 분석(Statisticla analysis)

• 암호문의 단어별 빈도와 알려진 통계 자료를 통해 암호를 해독하는 방법이다.

수학적 분석(Mathmetical analysis)

• 통계적인 방법을 포함하며 수학적인 이론을 이용하여 해독하는 방법이다.

 

1. skogkatt이라는 평문을 1234로 암호화했으면 복호화도 1234로 해야 한다 [본문으로]
2. 혼돈 - 암호문과 키의 상관관계를 숨긴다. 확산 - 평문의 통계적 성질을 암호문 전반에 퍼트려 숨긴다. 예로, 영어에서 가장 많이 사용되는 알파벳 통계를 통한 유추를 막아야 한다. [본문으로]
3. 또는 일정 비트 수, 단위 [본문으로]
4. 이 외에도 여러 암호 방식이 존재하지만 거의 사용되지 않는다. [본문으로]
5. 공모 시 해당 알고리즘의 이름은 Rijndael(레인달)이다. [본문으로]
6. 암호화에 있어서는 상당한 메리트로 암호화/복호화의 두 알고리즘을 서로 다른 알고리즘으로 구현할 필요가 없으며 라운드 함수에 관계없이 역변환이 가능하다. [본문으로]
7. OAPE 등 [본문으로]
8. 암호화/복호화 과정에서 역함수가 필요하다. [본문으로]
9. 스트림 암호를 사용하는 RC4의 경우 단 몇줄의 코드로 구현할 수 있다. [본문으로]
10. 차후 NSA는 이 공격을 1974년부터 인지하고 있었고 DES를 설계할 때 차분 공격으로부터 최대한 안전하게끔 만들었다고 밝혔다. 그리고 1993년 Eli Biham과 Adi Shamir가 차분 공격을 통한 DES의 취약점을 발견했다. [본문으로]