[Crypto] LEA를 통해 알아보는 블록 암호

LEA란 무엇인가

LEA(Lightweight Encryption Algorithm)는 빅데이터, 클라우드 등 고속 환경 및 모바일기기 등 경량 환경에서 기밀성을 제공하기 위해 개발된 128비트 블록암호 알고리즘입니다.

KISA 암호이용활성화, https://seed.kisa.or.kr/kisa/algorithm/EgovLeaInfo.do

주요 특성

• 개발연도 : 2013년
• 알고리즘 구분 : 128비트 블록암호
• 키 길이 : 128비트, 192비트 또는 256비트
• 구조 : ARX(Addition, Rotation, Xor) 기반 GFN(Generalized Feistel Network)

대칭 키

대칭키 암호(Symmetric key)란 암호문을 생성(암호화)할 때 사용하는 키와 암호문으로부터 평문을 복원할 때 사용하는 키가 동일한 암호 시스템으로 일반적으로 알고 있는 암호 시스템이다. 대칭키 암호는 혼돈과 확산의 성질을 이용하여 평문을 암호화 한다. 통상적으로 혼돈(confusion) 효과는 치환(substition)을 통해 형성되고, 확산(diffusion) 효과는 순열(permutation)을 통해 얻는다. 대칭키 암호를 설계할 때 이 치환과 순열 연산을 포함하여 한 개의 라운드(round)를 구성한다. 대칭키 암호에서 라운드를 어떻게 구성할지 결정하였다면, 이 라운드를 반복적으로 사용하는 구조로 대칭키 암호를 완성한다. 이러한 대칭키 암호 방식은 데이터를 변환하는 방법에 따라서 블록암호와 스트림암호로 구별한다.

해시넷, http://wiki.hash.kr/index.php/대칭키_암호_알고리즘

대칭 키의 가장 큰 특성은 다음과 같다.

1. 암호화 할 때 사용하는 키와 복호화 하는 키가 동일하다.
2. 혼돈과 확산의 성질을 이용한다.

   1. 혼돈은 평문과 암호문의 상관관계를 숨기는 것을 말한다. 이 효과는 치환을 통해 얻을 수 있다.
   2. 확산은 평문의 통계적 성질을 암호문 전반에 퍼트려 암호화 알고리즘을 파악하기 어렵게 하는 것을 말한다. 이 효과는 순열을 통해 얻을 수 있다.

1번 특성을 표현한 그림

대칭 키 암호화 방식에서 데이터를 변환하는 방식에 따라 블록 암호와 스트림 암호로 나뉜다.

블록 암호

LEA는 블록 암호 알고리즘이다.
이를 이해하기 위해서는 블록 암호에 대한 전반적인 이해가 필요하다.

블록암호(block cipher)란 기밀성 있는 정보를 정해진 블록 단위로 암호화하는 대칭키 암호 시스템이다. 만약 암호화하려는 정보가 블록의 길이보다 길 경우에는 특정한 운용 모드가 사용된다.(예 : ECB, CBC, OFB, CFB, CTR)

해시넷, http://wiki.hash.kr/index.php/블록암호

블록 암호는 고정된 크기의 블록 단위로 암호화/복호화를 수행하는 대칭키 방식 암호다.
이 때 암호화를 하기 위한 대상인 평문의 길이는 암호 알고리즘의 블록 길이와 동일해야 한다.

• LEA의 경우 128비트. 즉, 16바이트의 평문을 넣어야 한다.
• 만약 평문의 길이가 맞지 않다면 패딩을 넣어서 블록 크기의 배수로 맞춘다.

대표적인 블록 암호 알고리즘은 AES와 DES가 있다.
AES는 SPN 구조를 이용한 알고리즘이며, DES는 Feistel 구조를 이용한 알고리즘이다.

AES 암호 알고리즘 DES 암호 알고리즘

SPN (Substitution-Permutation Network)

SPN 구조는 S-Box와 P-Box를 이용하여 치환과 순혈 과정을 혼합한다.

병렬 구조로 연산을 할 수 있다는 장점이 있으나 별도의 복호화 연산을 구현해야 한다는 단점이 있다.

SPN 기반 블록 암호화는 치환(substitute)과 순열(permutate) 과정을 혼합하여 암호화를 수행하는 것을 의미한다. 치환은 입력으로 받은 값을 일대일로 매칭되는 다른 값으로 출력하는 연산을 의미한다. 그리고 순열은 입력으로 받은 값들의 배열을 변경해서 복잡도를 높이는 연산을 말한다. 해당 연산을 통해서 평문은 암호화된 형식으로 출력하게 된다.

해시넷, http://wiki.hash.kr/index.php/경량암호

GFN (Generalized Feistel Network)

GPN 구조는 기본적으로 대칭 구조를 갖는 Feistel 구조에 기반하지만, 각각의 암호 알고리즘의 특성에 맞추어 branch의 개수 및 내부 구조가 조금씩 달라지는 구조를 의미한다.

SPN 구조와 다르게 S-Box 연산이 아닌 ARX 연산을 이용하여 복호화 연산 (P-Box)를 구현할 필요가 없다는 장점이 있다.

LEA 알고리즘은 GFN-Type3을 적용한 알고리즘이다.

ARX 연산

ARX 기반 암호화는 기존의 SPN 구조와는 달리 간단히 사칙연산을 가지고 블록 알고리즘을 구성한다. 대체적으로 이는 덧셈, 회전, 그리고 배타적 논리합 연산 조합을 갖고 있다. 해당 기법의 주된 관심사는 워드 크기이며, 따라서 이에 따라 해당 사칙연산에 대한 구현 접근 방식도 결정된다.

해시넷, http://wiki.hash.kr/index.php/경량암호

SPN vs GFN

	SPN	GFN
장점	중간 비트의 이동이 없어서 한번에 암호화/복호화가 가능하다. GFN 구조에 비해 효율적으로 설계할 수 있다.	역함수가 필요하지 않다.
단점	라운드 함수의 역함수를 구해야 한다.	연산량이 많이 소요된다. 라운드 함수를 보다 더 안전하게 설계해야 한다.

블록 암호화 운영 모드

Cryptographic mode

블록 암호를 사용하는 방법을 정의한다.
피드백, 단순 연산, 기본 암호와 결합하여 사용한다.
안전성은 모드에 의존하지 않고 암호 알고리즘에 의존한다.

모드의 요구 조건은 다음과 같다.

1. 평문의 패턴을 숨겨야 한다.
2. 모드는 알고리즘의 효율성에 큰 영향을 주어서는 안 된다.
3. Fault-tolerance

ECB 모드

Electronic Codebook Mode

ECB 모드의 동작 방식

• 평문은 특정 크기의 블록으로 나누어서 암호화를 수행한다.
• 평문 블록에 대한 패딩 절차가 필요하다.
• 복호화는 암호화와 방식이 동일하다.

ECB 모드의 특징은 다음과 같다.

1. 가장 간단한 모드다.
2. 평문 블록을 암호문 블록으로 암호화한다.
3. 동일 키를 이용할 때 동일한 평문 블록은 항상 같은 암호문으로 암호화 된다.
4. 각 블록은 독립적으로 암호화된다.

CBC 모드

Cipher Block Chaining Mode

CBC 모드의 암호화 방식

CBC 모드의 복호화 방식

CBC 모드의 수식 표현

• $C_i = E_k(P_i\oplus C_{i-1})$
  $P_i = C_{i-1}\oplus D_k(C_i)$

CBC 모드의 특징

• 블록 암호에 피드백을 추가한다.
• 각 암호문 블록은 해당 평문 블록과 이전의 모든 평문 블록에 의존하여 생성된다.
• 초기화 벡터 (Initalization Vector, IV)

  1. Random data block
  2. 동일한 평문 블록을 다른 암호문 블록으로 암호화한다.
  3. 비밀일 필요는 없다.

• 오류 전파

  특정 평문 블록에 오류가 생기면 이후 모든 암호문 블록에 영향을 미친다.
  하지만 복호화 시 오류가 생긴 블럭을 제외하고 정상적으로 복호화가 된다.

• 긴 메시지일 경우 평문의 패턴이 나타난다.

CTR 모드

Counter Mode

CTR 모드의 수식 표현

• $K_i = E(K, Nonce || i), i = 1,2,...,k$
  $C_i = P_i\oplus K_i$

여기서 K는 키를 말한다.
Nonce는 고유 번호를 말하고 한 번만 사용해야 하며 비밀이 아니다.

CTR 모드의 특징

• 카운터를 이용하여 동일한 평문 블록이 서로 다른 암호문으로 출력된다.
• 스트림 암호의 형태를 가진다. 또한 블록의 순서 상관없이 병렬처리를 할 수 있다.

CFB 모드

Cipher-FeedBack Mode

CFB 모드의 수식 표현

• $C_i = P_i\oplus E_k(C_{i-1})$
  $P_i = C_i\oplus E_k(C_{i-1})$

CFB 모드의 특징

• CBC 모드의 변형으로, 자기 동기 스트림 암호로 변환한다.
• 초기화 벡터를 블록 암호화를 한 후에 평문 블록과 XOR을 해서 암호문 블록을 생성한다.
• 블록 크기보다 작은 단위로 암호화를 진행한다.
  - 8-bit CFB, 1-bit CFB, n-bit CFB
• 초기화 벡터 (Initalization Vector, IV)

  1. 비밀일 필요는 없다.
  2. 유일한 값이어야 한다.

• 오류 전파

  1. 평문의 오류

  • 이후의 모든 암호문에 영향을 미치지만 복호화에서 복원된다.

  2. 암호문의 오류

  • m을 블록 크기라고 할 때, n-bit CFB에서 1개의 암호문에 오류가 발생하면 $\frac{m}{n} - 1$개의 암호문 블록에 영향을 미친다.

OFB 모드

Output-Feedback Mode

OFB 모드의 특징

• 평문 블록과 암호 알고리즘의 출력을 XOR하여 암호문을 생성한다.
• 오류 확장이 없다.

정리

이렇게 LEA 암호 알고리즘이 적용한 방식인 대칭 키 방식과 블록 암호 방식을 알아보았다.
이 내용들을 LEA 알고리즘과 조합하면 다음과 같다.

1. LEA 암호 알고리즘은 GFN 방식을 적용하여 ARX 연산을 한다.
   즉 LEA 암호 알고리즘은 경량 암호 알고리즘이며 IoT 등 성능을 우선시하는 시스템에서 사용된다.
2. LEA 암호 알고리즘은 암호화가 복잡한 SPN 방식이 아니라 GFN 방식을 적용했기 때문에 비교적 빠르다.
   • 국제 표준 알고리즘인 AES 대비 1.5배 ~ 2배의 성능을 보여준다.
3. LEA 암호 알고리즘을 CTR 모드로 운영하면 강도(안전성)를 챙기며 장점인 성능을 극대화 할 수 있다.

마치며

공부하며 작성한 게시글이기 때문에 틀린 내용들이 있을 수 있습니다. 틀린 내용이 보이면 댓글로 알려주시면 정말 감사드리겠습니다.