맨위로가기

갈루와/카운터 모드

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

갈루아/카운터 모드(GCM)는 블록 암호 운용 방식 중 하나로, 카운터 모드(CTR) 암호화와 갈루아 인증 모드를 결합하여 데이터의 기밀성과 무결성을 제공한다. GCM은 초기화 벡터(IV)와 블록 번호를 결합하여 블록 암호(일반적으로 AES)로 암호화하여 암호문을 생성하고, 유한체 연산을 통해 인증 태그를 생성하여 데이터 무결성을 검증한다. GCM은 CTR 모드의 암호화와 갈루아 모드의 인증을 조합하여, 갈루아 필드 곱셈의 병렬 계산이 용이하여 CBC 모드보다 빠른 속도를 제공한다. GCM은 IEEE 802.1AE, WPA3-Enterprise, IPsec, TLS 1.2/1.3 등 다양한 분야에서 활용되며, 하드웨어 가속을 통해 높은 성능을 제공한다. GCM은 안전성이 증명되었지만, 동일한 키에 대해 고유한 IV를 사용해야 하며, 인증 태그 길이와 데이터 길이에 따라 보안이 달라진다.

더 읽어볼만한 페이지

  • 인증된 암호 방식 - CCM 모드
    CCM 모드는 기밀성과 인증을 위해 카운터 모드와 CBC-MAC을 결합한 인증 암호화 방식이며, 러스 하슬리, 더그 와이팅, 닐스 퍼거슨에 의해 설계되었고, IEEE 802.11i, IPsec 등 다양한 프로토콜에서 활용된다.
  • 블록 암호 운용 방식 - CCM 모드
    CCM 모드는 기밀성과 인증을 위해 카운터 모드와 CBC-MAC을 결합한 인증 암호화 방식이며, 러스 하슬리, 더그 와이팅, 닐스 퍼거슨에 의해 설계되었고, IEEE 802.11i, IPsec 등 다양한 프로토콜에서 활용된다.
  • 블록 암호 운용 방식 - 초기화 벡터
    초기화 벡터는 블록 암호 운용 방식에서 암호문의 무작위성을 확보하고 동일 평문 블록 암호화로 인한 보안 취약점을 해결하기 위해 각 블록 암호화 단계에서 입력 데이터를 무작위화하는 데 사용되는 고유하고 예측 불가능한 값이다.
  • 메시지 인증 코드 - HMAC
    HMAC(Keyed-Hash Message Authentication Code)는 공유된 비밀 키와 암호화 해시 함수를 사용하여 메시지의 무결성을 검증하는 메시지 인증 코드로서, IPsec, SSH, TLS, JSON 웹 토큰 등 다양한 보안 프로토콜에서 활용된다.
  • 메시지 인증 코드 - Poly1305
    Poly1305는 16바이트 비밀 키와 메시지를 입력으로 받아 16바이트 해시값을 출력하는 메시지 인증 코드 알고리즘으로, 카터-웨그만 구조에 기반하여 OpenSSH, 구글 Chrome, 안드로이드 등에서 메시지 인증 및 암호화에 활용되며 빠른 계산 속도와 효율적인 작동이 특징이다.
갈루와/카운터 모드
개요
종류인증된 암호화 모드
암호 알고리즘블록 암호
블록 크기블록 암호의 블록 크기에 따라 다름
키 크기블록 암호의 키 크기에 따라 다름
상세 정보
모드카운터 모드
갈루아 필드GF(2^128)
인증 태그 크기 (t)128비트 (일반적으로)
초기화 벡터 (IV)96비트 (권장), 12바이트
병렬 처리가능
특징
장점높은 성능, 병렬 처리 가능
단점구현 복잡성, 부채널 공격에 취약할 수 있음
보안
안전성 증명알려져 있음 (올바른 구현 가정 하에)
주요 보안 고려 사항올바른 IV 생성 및 사용, 태그 길이 선택
용도
일반적인 사용 사례네트워크 프로토콜 (예: IPsec, TLS), 저장 장치 암호화
표준NIST SP 800-38D

2. 기본 운용

GCM은 카운터 모드 암호화와 새로운 갈루아 인증 모드를 결합한 것이다. 주요 특징은 인증에 사용되는 갈루아 필드 곱셈의 병렬 계산이 용이하다는 점이다. 이 기능은 CBC와 같은 체이닝 모드를 사용하는 암호화 알고리즘보다 더 높은 처리량을 허용한다.

암호화에서는 CTR 모드와 마찬가지로 초기화 벡터(IV)로부터 블록 암호(일반적으로 AES)를 사용하여 키 스트림을 생성하고, 평문과 키 스트림의 XOR 연산을 통해 암호문을 생성한다. 암호화는 스트림 암호이므로 키 스트림을 생성할 때마다 다른 IV를 사용하는 것이 중요하다.

CTR 모드의 암호문은 관련 데이터(associated data)에 연결되어 인증을 위해 갈루아 모드로 처리된다. 갈루아 모드에서는 입력된 데이터를 갈루아체 상의 다항식으로 간주하여, 키에 의존하는 값 ''H''에서의 다항식 평가를 수행하고, 마지막으로 그 평가값을 키와 ''IV''에 의존하는 값으로 마스킹하여 인증 태그를 얻는다. 갈루아 모드에서 인증 태그 계산의 메인인 다항식 평가는 갈루아체 상의 덧셈과 곱셈으로 이루어져 병렬 계산이 가능하다.

GCM은 존 비에가와 데이비드 A. 맥그루에 의해 Carter–Wegman 카운터 모드 (CWC 모드)를 개선하기 위해 설계되었다.[4]

2007년 11월, NIST는 GCM과 GMAC을 공식 표준으로 만드는 NIST 특별 간행물 800-38D ''블록 암호 운용 방식에 대한 권장 사항: 갈루아/카운터 모드 (GCM) 및 GMAC''를 발표했다.[5]

2. 1. 암호화

GCM 암호화 운용


일반적인 카운터 모드와 마찬가지로, 블록은 순차적으로 번호가 매겨지며, 이 블록 번호는 초기화 벡터(IV)와 결합되어 블록 암호(일반적으로 고급 암호화 표준(AES))로 암호화된다. 이 암호화의 결과는 XOR 연산을 통해 평문과 결합되어 암호문을 생성한다. 모든 카운터 모드와 마찬가지로, 이것은 본질적으로 스트림 암호이므로 암호화되는 각 스트림에 대해 다른 IV를 사용하는 것이 중요하다.

암호문 블록은 다항식의 계수로 간주되며, 이 다항식은 유한체 산술을 사용하여 키에 의존적인 점에서 평가된다. 그 결과는 암호화되어 데이터의 무결성을 검증하는 데 사용할 수 있는 인증 태그를 생성한다. 암호화된 텍스트에는 IV, 암호문 및 인증 태그가 포함되어 있다.

GCM 작동. 추가 인증 데이터(Auth Data 1)의 단일 블록과 두 개의 평문 블록만 있는 경우.

  • 암호화: 일련의 128비트 카운터는 키 K를 사용하여 블록 암호 E로 암호화된다. (병렬 처리 가능) 결과는 128비트 평문 블록과 비트 단위 XOR 연산을 사용하여 결합되어 일련의 암호문 블록을 생성한다.[1]
  • 인증: 추가 데이터와 이러한 암호문 블록은 갈루아 필드 GF(2128)에서 키 의존 상수 H를 곱하여 결합되어 인증 태그를 생성한다.[1]


GCM은 암호화로 CTR 모드를, 인증으로 갈루아 모드를 조합한 것이다. CTR 모드에서 초기화 벡터 ''IV''로부터 블록 암호(일반적으로 AES)를 사용하여 키 스트림을 생성하고, 평문과 키 스트림의 XOR 연산을 통해 암호문을 생성한다. 암호화는 스트림 암호이기 때문에 키 스트림을 생성할 때마다 다른 ''IV''를 사용하는 것이 중요하다.[2]

CTR 모드의 암호문은 관련 데이터(associated data)에 연결되어 인증을 위해 갈루아 모드로 처리된다. 갈루아 모드에서는 입력된 데이터를 갈루아체 상의 다항식으로 간주하여, 키에 의존하는 값 ''H''에서의 다항식 평가를 수행하고, 마지막으로 그 평가값을 키와 ''IV''에 의존하는 값으로 마스킹하여 인증 태그를 얻는다. 다항식 평가는 갈루아체 상의 덧셈과 곱셈으로 이루어져 병렬 계산이 가능하다. 따라서 CBC 모드와 같이 연쇄 모드를 사용하는 인증 알고리즘보다 속도 향상이 가능하다.[2]

먼저 초기화 벡터 ''IV''에서 초기 카운터 값 ''counter0''을 결정한다. ''IV''는 임의 길이의 비트 열을 사용할 수 있지만, 일반적으로 96비트가 사용된다. 그 경우, ''counter0''은 다음과 같이 정의된다.[3]

: counter0 = IV \parallel 0^{31} \parallel 1

다음으로 CTR 모드를 위한 키 스트림을

: E_K(counter0 + 1) || E_K(counter0 + 2) || E_K(counter0 + 3) || ....

으로 생성하고, 키 스트림과 평문 ''P''의 배타적 논리합을 암호문 ''C''로 한다. 여기서 E_K는 블록 암호(일반적으로 AES)에 의한 암호화이다.[3]

갈루아 모드에서 사용되는 유한체 GF(2128)은 다음 다항식으로 정의된다.[4]

:x^{128} + x^7 + x^2 + x + 1

인증 태그는 GHASH 함수에 데이터 블록을 제공하고, 그 결과를 마스킹하여 생성된다. GHASH 함수는 다음과 같이 정의된다.[4]

:\text{GHASH}(H,A,C) = X_{m+n+1}

여기서 ''H''는 128개의 0으로 이루어진 문자열을 블록 암호로 암호화한 것, ''A''는 인증만 수행하는 데이터, ''C''는 암호문, ''m''은 ''A''에 포함된 128비트 블록의 수, ''n''은 ''C''에 포함된 128비트 블록의 수이며, ''i'' = 0, ..., ''m'' + ''n'' + 1에 대한 ''X''''i''는 다음과 같이 정의된다.[4]

먼저, 관련 데이터(인증만 되는 데이터) ''A''와 암호문 ''C''를 각각 길이가 128비트의 배수가 되도록 0으로 패딩한 다음, 연결하여 하나의 메시지 S_i를 생성한다.[4]

:S_i =

\begin{cases}

A_i & \text{for }i=1,\ldots,m-1 \\

A_m \lVert 0^{128-v} & \text{for }i=m \\

C_{i-m} & \text{for }i=m+1,\ldots, m+n-1 \\

C_n \lVert 0^{128-u} & \text{for }i=m+n \\

\operatorname{len}(A) \lVert \operatorname{len}(C) & \text{for }i=m+n+1 \\

\end{cases}

여기서 len(A)와 len(C)는 ''A''와 ''C''의 비트 길이를 64비트로 표현한 것이며, ''v''는 ''A''의 최종 블록의 비트 길이, ''u''는 ''C''의 최종 블록의 비트 길이이며, \lVert 는 비트 열의 연결을 나타낸다.[4]

이것을 사용하여, ''Xi''는 다음과 같이 정의된다.[4]

:X_i = \sum_{j=1}^i S_j \cdot H^{i-j+1} = \begin{cases}

0 & \text{for } i = 0 \\

\left(X_{i-1} \oplus S_i\right) \cdot H & \text{for } i = 1, \ldots, m + n + 1

\end{cases}

두 번째 표현 방법은 호너의 방법을 이용한 효율적인 반복 알고리즘이며, 각 ''X''''i''는 ''X''''i-1''에 의존한다. 마지막 ''X''''m''+''n''+1만 출력이 된다.[4]

X_i의 반복 계산은 병렬화가 가능하다. ''k''개의 자원을 사용하는 경우, 다음 식과 같이 각 자원이 ''k'' 블록 간격으로 처리하면 된다.[4]

:\begin{align}

X^'_i &= \begin{cases}

0 & \text{for } i \leq 0 \\

\left(X^'_{i-k} \oplus S_i \right) \cdot H^k & \text{for } i = 1, \ldots, m + n + 1 - k \\

\end{cases} \\[6pt]

X_i & = \sum_{j=1}^k \left( X^'_{i+j-2k} \oplus S_{i+j-k} \right) \cdot H^{k-j+1}

\end{align}

GCM은 Carter–Wegman Counter mode()의 개선으로 John Viega와 David A. McGrew에 의해 설계되었다.[5]

2007년 11월 2일, 미국 국립표준기술연구소(NIST)는 NIST Special Publication 800-38D ''블록 암호 운용 모드 권장 사항: 갈루아/카운터 모드(GCM) 및 GMAC''를 발표하여 GCM 및 GMAC를 공식적인 표준으로 인정했다.[5]

2. 2. 인증

GCM은 암호화로 CTR 모드를 사용하고, 인증에는 갈루아 모드를 결합한 방식이다.

암호화 과정에서 CTR 모드와 마찬가지로, 초기화 벡터(IV)를 사용하여 블록 암호(주로 AES)를 통해 키 스트림을 만든다. 이 키 스트림을 평문과 XOR 연산하여 암호문을 생성한다. 암호화는 스트림 암호 방식이므로, 키 스트림을 만들 때마다 서로 다른 IV를 사용하는 것이 중요하다.

CTR 모드의 암호문은 관련 데이터(associated data)와 함께 갈루아 모드에서 인증 과정을 거친다. 갈루아 모드에서는 입력된 데이터를 갈루아체(Galois field) 상의 다항식으로 취급한다. 키에 의존하는 값 ''H''를 사용하여 다항식을 평가하고, 그 결과값을 키와 IV에 의존하는 값으로 마스킹하여 인증 태그를 생성한다. 갈루아 모드에서 인증 태그 계산의 핵심인 다항식 평가는 갈루아체 상의 덧셈과 곱셈으로 이루어져 병렬 계산이 가능하다. 따라서 CBC 모드와 같이 연쇄적인 방식을 사용하는 인증 알고리즘보다 속도가 빠르다.

먼저 초기화 벡터 ''IV''로부터 초기 카운터 값 ''counter0''을 결정한다. ''IV''는 임의 길이의 비트 열을 사용할 수 있지만, 보통 96비트를 사용한다. 이 경우, ''counter0''은 다음과 같이 정의된다.

:

counter0 = IV \parallel 0^{31} \parallel 1



다음으로 CTR 모드를 위한 키 스트림을 다음과 같이 생성한다.

:

E_K(counter0 + 1) || E_K(counter0 + 2) ||E_K(counter0 + 3) || ....



여기서 E_K는 블록 암호(주로 AES)를 사용한 암호화이다. 이 키 스트림과 평문 ''P''의 배타적 논리합을 통해 암호문 ''C''를 얻는다.

갈루아 모드에서 사용되는 유한체 GF(2128)은 다음 다항식으로 정의된다.

: x^{128} + x^7 + x^2 + x + 1

인증 태그는 GHASH 함수에 데이터 블록을 넣고, 그 결과를 마스킹하여 만들어진다. GHASH 함수는 다음과 같이 정의된다.

: \text{GHASH}(H,A,C) = X_{m+n+1}

여기서 ''H''는 128개의 0으로 이루어진 문자열을 블록 암호로 암호화한 것이다. ''A''는 인증만 수행하는(암호화는 하지 않는) 데이터, ''C''는 암호문, ''m''은 ''A''에 포함된 128비트 블록의 수, ''n''은 ''C''에 포함된 128비트 블록의 수이며, ''i'' = 0, ..., ''m'' + ''n'' + 1에 대한 ''X''''i''는 다음과 같이 정의된다.

먼저, 관련 데이터(인증만 되는 데이터) ''A''와 암호문 ''C''를 각각 길이가 128비트의 배수가 되도록 0으로 패딩한 다음, 연결하여 하나의 메시지 S_i를 만든다.

: S_i =

\begin{cases}

A_i & \text{for }i=1,\ldots,m-1 \\

A_m \lVert 0^{128-v} & \text{for }i=m \\

C_{i-m} & \text{for }i=m+1,\ldots, m+n-1 \\

C_n \lVert 0^{128-u} & \text{for }i=m+n \\

\operatorname{len}(A) \lVert \operatorname{len}(C) & \text{for }i=m+n+1 \\

\end{cases}

여기서 len(A)와 len(C)는 ''A''와 ''C''의 비트 길이를 64비트로 표현한 것이고, ''v''는 ''A''의 마지막 블록의 비트 길이, ''u''는 ''C''의 마지막 블록의 비트 길이이며, \lVert 는 비트 열을 연결하는 것을 의미한다.

이를 바탕으로 ''Xi''는 다음과 같이 정의된다.

: X_i = \sum_{j=1}^i S_j \cdot H^{i-j+1} = \begin{cases}

0 & \text{for } i = 0 \\

\left(X_{i-1} \oplus S_i\right) \cdot H & \text{for } i = 1, \ldots, m + n + 1

\end{cases}

두 번째 표현은 호너의 방법을 사용한 효율적인 반복 알고리즘이며, 각 ''X''''i''는 ''X''''i-1''에 의존한다. 최종적으로 ''X''''m''+''n''+1만 출력된다.

X_i의 반복 계산은 병렬화할 수 있다. ''k''개의 자원을 사용하는 경우, 각 자원이 ''k'' 블록 간격으로 처리하면 된다.

: \begin{align}

X^'_i &= \begin{cases}

0 & \text{for } i \leq 0 \\

\left(X^'_{i-k} \oplus S_i \right) \cdot H^k & \text{for } i = 1, \ldots, m + n + 1 - k \\

\end{cases} \\[6pt]

X_i & = \sum_{j=1}^k \left( X^'_{i+j-2k} \oplus S_{i+j-k} \right) \cdot H^{k-j+1}

\end{align}

GCM은 Carter–Wegman Counter mode를 개선하여 John Viega와 David A. McGrew가 설계했다.

2007년 11월 2일, 미국 국립표준기술연구소(NIST)는 NIST Special Publication 800-38D ''블록 암호 운용 모드 권장 사항: 갈루아/카운터 모드(GCM) 및 GMAC''를 발표하여 GCM과 GMAC를 공식 표준으로 인정했다.

3. 수학적 기반

GCM은 카운터 모드 암호화와 갈루아 인증 모드를 결합한 것이다. GCM의 주요 특징은 인증에 사용되는 갈루아 필드 곱셈이 병렬 계산에 용이하다는 점이다. 이러한 특징은 CBC와 같이 체이닝 모드를 사용하는 암호화 알고리즘보다 더 높은 처리량을 제공한다.[3][4]

GCM에서 사용되는 GF(2128) 필드는 다음 다항식으로 정의된다.

:x^{128} + x^7 + x^2 + x + 1

갈루아/카운터 모드(GCM)는 존 비에가와 데이비드 A. 맥그루에 의해 Carter–Wegman 카운터 모드 (CWC 모드)를 개선하기 위해 설계되었다.[4] 2007년 11월, 미국 국립표준기술연구소(NIST)는 GCM과 GMAC을 공식 표준으로 만드는 NIST 특별 간행물 800-38D ''블록 암호 운용 방식에 대한 권장 사항: 갈루아/카운터 모드 (GCM) 및 GMAC''를 발표했다.[5]

3. 1. 갈루아 필드 (GF)

갈루아 필드 곱셈의 병렬 계산이 용이하다는 점이 GCM의 주요 특징이며, 이는 CBC와 같은 체이닝 모드를 사용하는 암호화 알고리즘보다 더 높은 처리량을 가능하게 한다. GCM에서 사용되는 GF(2128) 필드는 다음 다항식으로 정의된다.

: x^{128} + x^7 + x^2 + x + 1

인증 태그는 데이터를 GHASH 함수에 입력하고 그 결과를 암호화하여 구성된다. 이 GHASH 함수는 다음과 같이 정의된다.

: \operatorname{GHASH}(H, A, C) = X_{m+n+1}

여기서 ''H'' = ''Ek''(0128)은 블록 암호를 사용하여 암호화된 128비트 0 문자열인 ''해시 키''이고, ''A''는 인증만 되는 데이터(암호화되지 않음)이고, ''C''는 암호문이며, ''m''은 ''A''의 128비트 블록 수(올림)이고, ''n''은 ''C''의 128비트 블록 수(올림)이며, ''i'' = 0, ..., ''m'' + ''n'' + 1에 대한 변수 ''Xi''는 다음과 같이 정의된다.[3]

먼저, 인증된 텍스트와 암호문은 별도로 128비트의 배수로 0을 채우고 단일 메시지 ''Si''로 결합한다.

: S_i = \begin{cases}

A_i & \text{for }i = 1, \ldots, m - 1 \\

A^*_m \parallel 0^{128-v} & \text{for }i = m \\

C_{i-m} & \text{for }i = m + 1, \ldots, m + n - 1 \\

C^*_n \parallel 0^{128-u} & \text{for }i = m + n \\

\operatorname{len}(A) \parallel \operatorname{len}(C) & \text{for }i = m + n + 1

\end{cases}

여기서 len(''A'')와 len(''C'')는 각각 ''A''와 ''C''의 비트 길이의 64비트 표현이며, ''v'' = len(''A'') mod 128은 ''A''의 마지막 블록의 비트 길이이고, ''u'' = len(''C'') mod 128은 ''C''의 마지막 블록의 비트 길이이며, \parallel는 비트 문자열의 연결을 나타낸다.

그런 다음 ''Xi''는 다음과 같이 정의된다.

: X_i = \sum_{j=1}^i S_j \cdot H^{i-j+1} = \begin{cases}

0 & \text{for } i = 0 \\

\left(X_{i-1} \oplus S_i\right) \cdot H & \text{for } i = 1, \ldots, m + n + 1

\end{cases}

두 번째 형식은 호너 방법을 적용하여 생성된 효율적인 반복 알고리즘이다(각 ''Xi''는 ''X''''i''−1에 의존). 최종 ''X''''m''+''n''+1만 출력을 유지한다.

해시 계산을 병렬화해야 하는 경우, 다음과 같이 ''k''번 인터리빙하여 수행할 수 있다.

: \begin{align}

X^'_i &= \begin{cases}

0 & \text{for } i \leq 0 \\

\left(X^'_{i-k} \oplus S_i \right) \cdot H^k & \text{for } i = 1, \ldots, m + n + 1 - k \\

\end{cases} \\[6pt]

X_i & = \sum_{j=1}^k \left( X^'_{i+j-2k} \oplus S_{i+j-k} \right) \cdot H^{k-j+1}

\end{align}

IV의 길이가 96이 아닌 경우, GHASH 함수는 ''카운터 0''을 계산하는 데 사용된다.

: \mathrm{Counter 0} = \begin{cases}

IV \parallel 0^{31} \parallel 1 & \text{for } \operatorname{len}(IV) = 96 \\

\operatorname{GHASH}\left(IV \parallel 0^{s} \parallel 0^{64} \parallel \operatorname{len}_{64}(IV) \right) \text{ with } s = 128 - \operatorname{len}(IV) \mod 128 & \text{otherwise}

\end{cases}

3. 2. GHASH 함수

GHASH 함수는 데이터를 인증하고 암호화하는 데 사용되는 핵심 함수이다. 이 함수는 해시 키 ''H''와 인증 데이터 ''A'', 그리고 암호문 ''C''를 입력으로 받아 인증 태그를 생성한다.[3]

GHASH 함수는 다음과 같이 정의된다.

:\operatorname{GHASH}(H, A, C) = X_{m+n+1}

여기서 ''H'' = ''Ek''(0128)는 블록 암호를 사용하여 암호화된 128비트 0 문자열인 ''해시 키''이다. ''A''는 인증만 되는 데이터(암호화되지 않음)이고, ''C''는 암호문이다. ''m''은 ''A''의 128비트 블록 수(올림)이고, ''n''은 ''C''의 128비트 블록 수(올림)이다.

사용되는 GF(2128) 필드는 다음 다항식으로 정의된다.

:x^{128} + x^7 + x^2 + x + 1

IV(초기화 벡터)의 길이가 96이 아닌 경우, GHASH 함수는 ''카운터 0''을 계산하는 데 사용된다.[3]

:\mathrm{Counter 0} = \begin{cases}

IV \parallel 0^{31} \parallel 1 & \text{for } \operatorname{len}(IV) = 96 \\

\operatorname{GHASH}\left(IV \parallel 0^{s} \parallel 0^{64} \parallel \operatorname{len}_{64}(IV) \right) \text{ with } s = 128 - \operatorname{len}(IV) \mod 128 & \text{otherwise}

\end{cases}

3. 2. 1. Si 정의

먼저, 인증된 텍스트와 암호문은 별도로 128비트의 배수로 0을 채우고 단일 메시지 ''Si''로 결합한다.[3]

:S_i = \begin{cases}

A_i & \text{for }i = 1, \ldots, m - 1 \\

A^*_m \parallel 0^{128-v} & \text{for }i = m \\

C_{i-m} & \text{for }i = m + 1, \ldots, m + n - 1 \\

C^*_n \parallel 0^{128-u} & \text{for }i = m + n \\

\operatorname{len}(A) \parallel \operatorname{len}(C) & \text{for }i = m + n + 1

\end{cases}

여기서 len(''A'')와 len(''C'')는 각각 ''A''와 ''C''의 비트 길이의 64비트 표현이며, ''v'' = len(''A'') mod 128은 ''A''의 마지막 블록의 비트 길이이고, ''u'' = len(''C'') mod 128은 ''C''의 마지막 블록의 비트 길이이며, \parallel는 비트 문자열의 연결을 나타낸다.

3. 2. 2. Xi 정의

Xi영어는 다음과 같이 정의된다.[3]

:X_i = \sum_{j=1}^i S_j \cdot H^{i-j+1} = \begin{cases}

0 & \text{for } i = 0 \\

\left(X_{i-1} \oplus S_i\right) \cdot H & \text{for } i = 1, \ldots, m + n + 1

\end{cases}

두 번째 형식은 첫 번째 형식에 호너 방법을 적용하여 생성된 효율적인 반복 알고리즘이다 (각 Xi영어는 X영어''i''−1에 의존). 최종 X영어''m''+''n''+1만 출력을 유지한다.

해시 계산을 병렬화해야 하는 경우, 다음과 같이 ''k''번 인터리빙하여 수행할 수 있다.

:\begin{align}

X^'_i &= \begin{cases}

0 & \text{for } i \leq 0 \\

\left(X^'_{i-k} \oplus S_i \right) \cdot H^k & \text{for } i = 1, \ldots, m + n + 1 - k \\

\end{cases} \\[6pt]

X_i & = \sum_{j=1}^k \left( X^'_{i+j-2k} \oplus S_{i+j-k} \right) \cdot H^{k-j+1}

\end{align}

3. 2. 3. 병렬 처리

GCM (갈루아/카운터 모드)에서 인증 태그 생성과 암호화 과정은 병렬 처리를 통해 효율성을 높일 수 있다.

GHASH 함수에서 ''Xi''를 계산할 때, 여러 개의 블록을 동시에 처리할 수 있도록 식을 변형하여 병렬화를 수행한다. ''k''개의 블록을 병렬로 처리하는 경우, 다음과 같이 계산한다.

먼저, ''X'i''를 다음과 같이 계산한다.

:\begin{align}

X^'_i &= \begin{cases}

0 & \text{for } i \leq 0 \\

\left(X^'_{i-k} \oplus S_i \right) \cdot H^k & \text{for } i = 1, \ldots, m + n + 1 - k \\

\end{cases}

\end{align}

그런 다음, ''Xi''는 다음과 같이 계산된다.

:

X_i = \sum_{j=1}^k \left( X^'_{i+j-2k} \oplus S_{i+j-k} \right) \cdot H^{k-j+1}



이러한 병렬 처리 방식을 통해, GCM은 CBC 모드와 같은 순차적인 처리가 필요한 방식보다 훨씬 높은 처리량을 제공할 수 있다. 특히, 인증에 사용되는 갈루아 필드 곱셈의 병렬 계산이 용이하다는 점이 GCM의 큰 장점이다.[3]

3. 3. 초기화 벡터 (IV)

초기화 벡터(IV)는 GCM에서 암호화 및 인증 과정에 사용되는 중요한 요소이다. IV는 각 암호화 작업마다 다른 값을 가져야 하며, 예측 불가능해야 한다.

IV의 길이는 임의의 비트 열을 사용할 수 있지만, 일반적으로 96비트가 사용된다. 96비트 IV를 사용하는 경우, 초기 카운터 값 ''counter0''은 다음과 같이 정의된다.[3]

:

counter0 = IV \parallel 0^{31} \parallel 1



즉, 96비트 IV 뒤에 31개의 0비트와 1개의 1비트를 연결하여 128비트의 ''counter0''을 생성한다.

만약 IV의 길이가 96비트가 아닌 경우, GHASH 함수를 사용하여 ''counter0''을 계산한다.[3]

: \mathrm{Counter 0} = \begin{cases}

IV \parallel 0^{31} \parallel 1 & \text{for } \operatorname{len}(IV) = 96 \\

\operatorname{GHASH}\left(IV \parallel 0^{s} \parallel 0^{64} \parallel \operatorname{len}_{64}(IV) \right) \text{ with } s = 128 - \operatorname{len}(IV) \mod 128 & \text{otherwise}

\end{cases}

여기서 len(IV)는 IV의 비트 길이를 나타내고, s는 128에서 IV의 길이를 128로 나눈 나머지를 뺀 값이다. 즉 96비트가 아닌 IV의 경우에는, IV 뒤에 (s)개의 0을 붙이고, 64개의 0비트, 그리고 len64(IV) 를 GHASH함수에 넣어서 나온 출력이 Counter 0 이 된다.

이렇게 생성된 ''counter0''은 카운터 모드에서 초기 카운터 값으로 사용되며, 이후 카운터는 1씩 증가하면서 암호화에 사용되는 키 스트림을 생성한다.

4. 활용

GCM 모드는 IEEE 802.1AE (MACsec) 이더넷 보안, WPA3-Enterprise 와이파이 보안 프로토콜, IEEE 802.11ad (일명 WiGig), ANSI (INCITS) 파이버 채널 보안 프로토콜 (FC-SP), IEEE P1619.1 테이프 스토리지, IETF IPsec 표준,[6][7] SSH,[8] TLS 1.2[9][10] 및 TLS 1.3에서 사용된다.[11] AES-GCM은 NSA Suite B 암호화 및 2018년 최신 대체품인 상용 국가 안보 알고리즘(CNSA) 제품군에 포함되어 있다.[12] GCM 모드는 SoftEther VPN 서버 및 클라이언트,[13] 뿐만 아니라 버전 2.4부터 OpenVPN에서도 사용된다.

그 효율성과 성능 덕분에 널리 사용되고 있으며, 최첨단 고속 통신은 적절한 하드웨어 자원으로 달성된다고 여겨진다.[25] GCM은 IEEE의 IEEE 802.1AE (MACsec) 이더넷 보안, IEEE 802.11ad (WiGig), IEEE P1619.1, ANSI (INCITS)의 파이버 채널 보안 프로토콜 (FC-SP), IETF의 IPsec[26][27], SSH[28], TLS 1.2[29][30] 등 다양한 표준 규격에 채택되었다. 또한 AES-GCM은 NSA Suite B Cryptography영어 및 그 후계인 상용 국가 안보 알고리즘에 포함되어 있다.

5. 성능

GCM은 암호화 및 인증된 데이터 블록(128비트)마다 블록 암호 연산 1회와 갈루아 필드에서의 128비트 곱셈 1회를 필요로 한다. 블록 암호 연산은 파이프라인화나 병렬화가 용이하며, 곱셈 연산 역시 파이프라인화가 쉽고, 약간의 노력을 통해 병렬화도 가능하다. 예를 들어 실제 연산을 병렬화하거나, 호너 방법을 적용하는 방식이 있다.[14]

인텔은 GCM 사용을 위해 PCLMULQDQ 명령어를 추가했다.[14] 2011년 SPARC는 64 × 64비트 무캐리 곱셈을 수행하는 XMULX 및 XMULXHI 명령어를, 2015년에는 최대 2048 × 2048비트 입력 값에 대한 XOR 곱셈을 수행하여 4096비트 결과를 생성하는 XMPMUL 명령어를 추가했다. 이러한 명령어들은 GF(2''n'')에서의 빠른 곱셈을 가능하게 하며, 모든 필드 표현과 함께 사용할 수 있다.

GCM의 성능은 다양한 플랫폼에서 측정되었다. Käsper와 Schwabe는 64비트 인텔 프로세서에서 AES-GCM 인증 암호화를 바이트당 10.68 사이클로 달성했다.[15] Dai 등은 인텔의 AES-NI 및 PCLMULQDQ 명령어를 사용하여 동일 알고리즘에서 바이트당 3.5 사이클을 보고했다. Shay Gueron과 Vlad Krasnov는 3세대 인텔 프로세서에서 바이트당 2.47 사이클을 달성했다.[16] OpenSSL 및 NSS 라이브러리에 대한 패치도 준비되었다.[16]

메시지에 대해 인증과 암호화를 모두 수행해야 하는 경우, 소프트웨어 구현에서 두 작업의 실행을 겹치게 하여 속도를 향상시킬 수 있다. 작업들을 인터리빙하여 명령어 수준 병렬 처리를 활용함으로써 성능이 향상된다. 이 프로세스를 기능 스티칭(function stitching)[17]이라고 하며, GCM에 특히 적합하다. Manley와 Gregg는 GCM으로 기능 스티칭을 사용할 때 최적화가 얼마나 쉬운지 보여주었다.[18]

GCM은 임베디드 환경에서 병렬 처리가 암호화 하드웨어 엔진의 성능 활용에 적합하지 않다는 비판을 받았다.[19] GCM은 지연과 오버헤드가 적어 패킷화된 데이터 보호에 적합하다.

인텔은 2010년 Westmere 이후 프로세서에 GCM 계산 속도 향상을 위한 CLMUL instruction set (PCLMULQDQ)를 구현했다[31]。이는 GF(2n) 유한체에서의 곱셈을 고속화하는 것으로, 임의의 체 표현에 적용 가능하다.

6. 특허

저자들과 설계자의 진술에 따르면, 갈루아/카운터 모드(GCM)는 특허에 얽매이지 않으며 특허로 인해 사용이 방해받지 않는다.[21][36]

7. 보안

GCM은 구체적 보안 모델에서 안전함이 증명되었다.[22] 임의의 순열과 구별할 수 없는 블록 암호와 함께 사용될 때 안전하지만, 보안은 동일한 키로 수행되는 모든 암호화에 대해 고유한 초기화 벡터를 선택하는 것에 달려있다(''스트림 암호 공격'' 참조). 주어진 키와 초기화 벡터 값에 대해 GCM은 64GiB의 평문을 암호화하는 것으로 제한된다. NIST 특별 출판물 800-38D[5]에는 초기화 벡터 선택에 대한 지침이 포함되어 있으며 단일 키에 대한 가능한 초기화 벡터 값의 수를 제한한다. 동일한 키를 사용하여 더 많은 데이터를 처리할수록 GCM의 보안 보장이 저하되므로, 단일 키의 수명 동안 보호되는 평문과 AD의 총 블록 수는 264로 제한해야 한다.[5]

인증 강도는 모든 대칭 메시지 인증 코드와 마찬가지로 인증 태그의 길이에 따라 달라진다. GCM에서는 더 짧은 인증 태그를 사용하는 것이 권장되지 않는다.

Saarinen은 GCM 약한 키에 대해 설명했다.[24] 이 연구는 다항식 해시 기반 인증이 어떻게 작동하는지에 대한 귀중한 통찰력을 제공한다. 이 연구는 유효한 GCM 메시지가 주어지면 특정 길이의 메시지에 대해 특정 확률로 작동하는 GCM 메시지를 위조하는 방법을 설명하지만, 이전에 알려진 것보다 더 효과적인 공격을 보여주지는 않았다. Saarinen은 또한 소피 제르맹 소수를 기반으로 한 GCM 변형인 소피 제르맹 카운터 모드(SGCM)에 대해서도 설명했다.

7. 1. 초기화 벡터 (IV) 선택

GCM은 구체적 보안 모델에서 안전함이 증명되었다.[22] 보안은 동일한 키로 수행되는 모든 암호화에 대해 고유한 초기화 벡터를 선택하는 것에 달려있다.[5] NIST 특별 출판물 800-38D에는 초기화 벡터 선택에 대한 지침이 포함되어 있으며, 단일 키에 대한 가능한 초기화 벡터 값의 수를 제한한다.[5]

7. 2. 인증 태그 길이

GCM의 인증 강도는 인증 태그의 길이에 따라 달라진다. 따라서, 더 짧은 인증 태그는 사용하지 않는 것이 좋다. 태그의 비트 길이 ''t''는 보안 매개변수이다. 일반적으로 ''t''는 128, 120, 112, 104 또는 96 중 하나의 값을 가질 수 있다. 특정 응용 프로그램에서는 ''t''가 64 또는 32가 될 수 있지만, 이 두 태그 길이를 사용하면 입력 데이터의 길이와 키의 수명이 제한된다. NIST SP 800-38D의 부록 C는 이러한 제약에 대한 지침을 제공한다.[5] 예를 들어, ''t'' = 32이고 최대 패킷 크기가 1024 바이트인 경우, 인증 복호화 함수는 211회 이하로 호출해야 한다. ''t'' = 64이고 최대 패킷 크기가 32768 바이트인 경우, 인증 복호화 함수는 232회 이하로 호출해야 한다.

공격자가 무작위로 ''t''-비트 태그를 선택하면, 주어진 데이터에 대해 정확할 확률은 2−''t''이다. 그러나 GCM에서는 공격자가 암호문과 추가 인증된 데이터(AAD)의 총 길이인 ''n'' 단어를 갖는 태그를 선택하여 성공 가능성을 ''n''배만큼 높일 수 있다. 그럼에도 불구하고, 임의로 큰 ''t''에 대해 이러한 최적 태그는 알고리즘의 생존 척도 1 - ''n''⋅2−''t''에 의해 지배된다. GCM은 매우 짧은 태그 길이나 매우 긴 메시지에는 적합하지 않다.

Ferguson과 Saarinen은 GCM 인증에 대해 보안 하한을 충족하는 최적의 공격 방법을 독립적으로 설명했다. Ferguson은 ''n''이 인코딩의 총 블록 수(GHASH 함수의 입력)를 나타내는 경우, 약 ''n''⋅2−''t''의 확률로 성공할 것으로 예상되는 대상 암호문 위조를 구성하는 방법을 제시했다. 태그 길이 ''t''가 128보다 짧으면 이 공격에서 각 성공적인 위조는 후속 대상 위조가 성공할 확률을 높이고 해시 서브키인 ''H''에 대한 정보를 유출한다. 결국, ''H''가 완전히 손상되어 인증 보장이 완전히 손실될 수 있다.[23]

이 공격과는 별도로, 공격자는 인증된 해독에 대한 주어진 입력에 대해 많은 서로 다른 태그를 체계적으로 추측하여 하나 이상이 유효한 것으로 간주될 확률을 높이려고 시도할 수 있다. 이러한 이유로 GCM을 구현하는 시스템 또는 프로토콜은 각 키에 대해 실패한 검증 시도 횟수를 모니터링하고, 필요한 경우 제한해야 한다.

Saarinen은 GCM 약한 키에 대해 설명했다.[24]

참조

[1] 문서 RFC 256 AES Galois Counter Mode (GCM) Cipher Suites for TLS
[2] 서적 Cryptographic Hardware and Embedded Systems - CHES 2007 . GCM-AES Architecture Optimized for FPGAs Springer
[3] 웹사이트 The Galois/Counter Mode of Operation (GCM) http://csrc.nist.gov[...] 2013-07-20
[4] 서적 Fast Software Encryption Springer 2004
[5] 간행물 Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC http://csrc.nist.gov[...] 2007–2011
[6] 문서 RFC 4106 The Use of Galois/Counter Mode (GCM) in IPsec Encapsulating Security Payload (ESP)
[7] 문서 RFC 4543 The Use of Galois Message Authentication Code (GMAC) in IPsec ESP and AH
[8] 문서 RFC 5647 AES Galois Counter Mode for the Secure Shell Transport Layer Protocol
[9] 문서 RFC 5288 AES Galois Counter Mode (GCM) Cipher Suites for TLS
[10] 문서 RFC 6367 Addition of the Camellia Cipher Suites to Transport Layer Security (TLS)
[11] 문서 RFC 8446 The Transport Layer Security protocol version 1.3
[12] 웹사이트 Algorithm Registration - Computer Security Objects Register | CSRC | CSRC https://csrc.nist.go[...] 2016-05-24
[13] 웹사이트 Why SoftEther VPN – SoftEther VPN Project https://www.softethe[...]
[14] 웹사이트 Intel Carry-Less Multiplication Instruction and its Usage for Computing the GCM Mode (Revision 2.02) https://www.intel.co[...] 2014-04
[15] 서적 Cryptographic Hardware and Embedded Systems - CHES 2009 Springer
[16] 웹사이트 AES-GCM for Efficient Authenticated Encryption – Ending the Reign of HMAC-SHA-1? https://crypto.stanf[...] 2013-02-08
[17] 문서 Fast Cryptographic Computation on Intel Architecture via Function Stitching http://download.inte[...] Intel Corp. 2010
[18] 서적 Progress in Cryptology - INDOCRYPT 2010 Springer
[19] 웹사이트 IoT Security Part 6: Galois Counter Mode https://community.si[...] 2016-05-06
[20] 논문 A Hardware Perspective on the ChaCha Ciphers: Scalable Chacha8/12/20 Implementations Ranging from 476 Slices to Bitrates of 175 Gbit/s 2019-09
[21] 웹사이트 The Galois/Counter Mode of Operation (GCM) Intellectual Property Statement http://csrc.nist.gov[...] Computer Security Resource Center, NIST
[22] 서적 Proceedings of INDOCRYPT 2004 Springer
[23] 문서 Authentication Weaknesses in GCM http://csrc.nist.gov[...] 2005-05-20
[24] 논문 Cycling Attacks on GCM, GHASH and Other Polynomial MACs and Hashes http://eprint.iacr.o[...] FSE 2012 2011-04-20
[25] 문서 Multi-gigabit GCM-AES Architecture Optimized for FPGAs CHES '07: Proceedings of the 9th international workshop on Cryptographic Hardware and Embedded Systems, 2007
[26] IETF RFC The Use of Galois/Counter Mode (GCM) in IPsec Encapsulating Security Payload (ESP)
[27] IETF RFC The Use of Galois Message Authentication Code (GMAC) in IPsec ESP and AH
[28] IETF RFC AES Galois Counter Mode for the Secure Shell Transport Layer Protocol
[29] IETF RFC AES Galois Counter Mode (GCM) Cipher Suites for TLS
[30] IETF RFC Addition of the Camellia Cipher Suites to Transport Layer Security (TLS)
[31] URL http://software.inte[...]
[32] 문서 Cryptographic Hardware and Embedded Systems — CHES 2009, Lecture Notes in Computer Science 5745, Springer-Verlag (2009), pp 1—17.
[33] URL https://groups.googl[...]
[34] 웹사이트 AES-GCM for Efficient Authenticated Encryption – Ending the Reign of HMAC-SHA-1? https://crypto.stanf[...] 2013-02-08
[35] 문서 Fast Cryptographic Computation on Intel Architecture Via Function Stitching http://download.inte[...] Intel Corp. 2010
[36] 문서 authors' statement http://csrc.nist.gov[...]
[37] 논문 The Security and Performance of the Galois/counter mode (GCM) of Operation http://citeseerx.ist[...] Proceedings of INDOCRYPT 2004, LNCS 3348 (2004)
[38] 문서 Authentication Weaknesses in GCM http://csrc.nist.gov[...] 2005-05-20
[39] 논문 Cycling Attacks on GCM, GHASH and Other Polynomial MACs and Hashes http://eprint.iacr.o[...] FSE 2012 2011-04-20
[40] 서적 Cryptographic Hardware and Embedded Systems — CHES 2007 Springer


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com