서펜트 (암호)
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
서펜트(Serpent)는 32라운드의 치환-순열 네트워크 구조를 가진 블록 암호 알고리즘이다. 사용자 제공 키를 확장하여 라운드마다 사용될 서브키를 생성하는 키 스케줄링 과정을 거치며, 초기 순열과 최종 순열을 포함한다. 서펜트는 8개의 4비트 S-box를 사용하며, 128비트, 192비트, 256비트 키 길이를 지원한다. Rijndael과 함께 AES 후보로 경쟁했으며, Rijndael이 AES로 선정되었다. XSL 공격, 중간 만남 공격, 선형 암호 분석 공격 등 다양한 공격에 대한 연구가 진행되었다. 최초 버전인 서펜트-0에서 약간 수정된 서펜트-1이 AES 공모전에 제출되었다.
더 읽어볼만한 페이지
- 블록 암호 - 데이터 암호화 표준
데이터 암호화 표준(DES)은 미국 국립표준기술연구소에서 개발되어 널리 사용되었던 대칭키 암호 알고리즘이지만, 짧은 키 길이와 취약점 때문에 고급 암호화 표준(AES)으로 대체되었고, 트리플 DES 형태로 일부 시스템에서 사용되며 암호학 발전에 기여한 역사적 의미가 있다. - 블록 암호 - 고급 암호화 표준
고급 암호화 표준(AES)은 미국 국립표준기술연구소에서 제정한 대칭 키 암호화 블록 암호 표준으로, 치환-순열 네트워크 구조에 기반하여 128비트 블록 크기와 다양한 키 크기를 지원하며, 빠른 속도와 효율성으로 널리 사용된다. - 공식 웹사이트에 알 수 없는 변수를 사용한 문서 - 브루클린 미술관
브루클린 미술관은 1823년 브루클린 견습생 도서관으로 시작하여 현재 약 50만 점의 소장품을 보유한 뉴욕 브루클린 소재의 미술관으로, 다양한 분야의 예술 작품을 전시하며 특히 아프리카 미술과 여성주의 미술에 대한 기여가 크다. - 공식 웹사이트에 알 수 없는 변수를 사용한 문서 - 광주지방기상청
광주지방기상청은 광주광역시와 전라남도 지역의 기상 예보, 특보, 관측, 기후 정보 제공 등의 업무를 수행하는 기상청 소속 기관으로, 1949년 광주측후소로 설치되어 1992년 광주지방기상청으로 개편되었으며, 기획운영과, 예보과, 관측과, 기후서비스과와 전주기상지청, 목포기상대를 두고 있다.
| 서펜트 (암호) | |
|---|---|
| 개요 | |
 | |
| 설계자 | 로스 앤더슨, 엘리 비함, 라스 크누센 |
| 발표일 | 1998년 8월 21일 |
| 파생 | Square |
| 인증 | AES 최종 후보 |
| 키 크기 | 128, 192 또는 256 비트 |
| 블록 크기 | 128 비트 |
| 구조 | Substitution-permutation network |
| 라운드 수 | 32 |
| 암호 해독 | 256을 깨뜨리는 두 가지 공격도 설명한다. 첫 번째는 2118개의 알려진 평문, 2228.8의 시간 및 2228의 메모리가 필요하다. 다른 공격은 2116개의 알려진 평문과 2121의 메모리가 필요하지만 2237.5의 시간도 필요하다. |
2. 키 스케줄
서펜트의 키 스케줄은 사용자 제공 키를 확장하여 각 라운드마다 사용될 서브키(라운드 키)를 생성하는 과정이다. 이 과정은 키 초기화, 프리키 생성, 서브키 생성의 세 단계로 나뉜다.[3]
키 스케줄의 C 언어 구현은 다음과 같다.
```cpp
#define FRAC 0x9e3779b9 // 황금비율의 소수 부분
#define ROTL(A, n) ((A) << n | (A) >> 32-n)
uint32_t key[8]; // 사용자가 제공한 키
uint32_t subkey[33][4]; // 라운드 키
const uint8_t S[8][16] = {}; // S-box
/* 키 스케줄: 사전 키 얻기 */
void get_pre(uint32_t w[4*33], const uint32_t k[8]) {
uint32_t x[4*33+8];
for (int i = 0; i < 8; i++)
x[i] = k[i];
for (int i = 8; i < 140; i++) {
x[i] = ROTL(x[i-8] ^ x[i-5] ^ x[i-3] ^ x[i-1] ^ FRAC ^ (i-8), 11);
w[i-8] = x[i];
}
}
void key_schedule() {
uint32_t w[4*33];
get_pre(w, key);
get_sk(w, subkey);
}
```
각 단계에 대한 자세한 내용은 하위 섹션을 참조할 수 있다.
2. 1. 키 초기화
서펜트의 키 스케줄은 3단계로 구성된다. 첫 단계에서는 256비트 미만의 짧은 키를 256비트 길이로 만든다. 짧은 키 끝에 "1" 비트를 추가하고, 256비트가 될 때까지 "0" 비트를 추가하여 패딩을 진행한다.[3]2. 2. 프리키 생성
초기화된 키를 사용하여 프리키(prekey)를 생성한다. 32비트 키 부분을 XOR 연산하고, 황금비의 분수인 ''FRAC''과 라운드 인덱스를 키 부분과 XOR 연산하며, XOR 연산의 결과는 11만큼 왼쪽으로 회전한다. ''FRAC''과 라운드 인덱스는 라운드 동안 키 비트의 균등한 분포를 달성하기 위해 추가되었다.[3]2. 3. 서브키 생성
프리키로부터 33개의 128비트 서브키가 생성된다.[3]라운드 키 또는 "서브키"는 키 비트를 올바른 열에 배치하기 위해 "초기 순열 IP"에 배치된다.[3]
C 언어 소스 코드는 다음과 같다.
```cpp
/* 키 스케줄: 서브 키 얻기 */
void get_sk(const uint32_t w[4*33], uint32_t (*sk)[4]) {
uint8_t i, p, j, s, k;
for (i = 0; i < 33; i++) {
p = 32 + 3 - i;
for (j = 0; j < 4; j++)
sk[i][j] = 0;
for (k = 0; k < 32; k++) {
s = S[p % 8][((w[4 * i + 0] >> k) & 0x1) << 0 |
((w[4 * i + 1] >> k) & 0x1) << 1 |
((w[4 * i + 2] >> k) & 0x1) << 2 |
((w[4 * i + 3] >> k) & 0x1) << 3 ];
for (j = 0; j < 4; j++) {
sk[i][j] |= ((s >> j) & 0x1) << k;
}
}
}
}
2. 4. 초기 순열 (IP)
생성된 서브키는 초기 순열(Initial Permutation, IP)을 거쳐 비트 위치가 변경된다.[3]3. S-Box
서펜트는 8개의 서로 다른 4x4 S-box(Substitution-box)를 사용한다. 서펜트 S-Box는 4비트 순열이다. Rijndael은 8×8 S-box를 1개 사용하지만, 서펜트는 8개의 서로 다른 4×4 S-box를 사용한다.
3. 1. S-Box 구성
서펜트 S-Box는 DES S-Box의 32개 행을 기반으로 구성되었다. 이러한 행들은 "sboxesforserpent" 키를 사용하여 항목 교환 방식으로 변환되었으며, 원하는 속성을 가진 배열이 서펜트 S-Box로 저장되었다. 이 과정은 총 8개의 S-Box가 발견될 때까지 반복되었다.[3]3. 2. S-Box 특징
4. 순열 및 변환
서펜트는 데이터를 섞기 위해 여러 종류의 순열 및 변환 과정을 거친다. 초기 순열과 최종 순열은 128비트 블록의 비트 위치를 변경한다. 선형 변환은 XOR, S-Box, 비트 왼쪽 시프트 및 비트 왼쪽 회전 연산을 포함하며, 주로 4개의 32비트 워드에서 수행된다.
4. 1. 초기 순열 (IP)
초기 순열은 128비트 블록의 비트 위치를 변경한다. 0부터 127까지의 각 비트 i에 대해, 원래 비트(i)와 (32 * i) % 127 위치의 비트를 서로 바꾼다.4. 2. 최종 순열 (FP)
최종 순열은 한 번에 128비트에 대해 작동하며 비트를 이동시킨다. 이는 초기 순열의 역순열이다.```cpp
for i in 0 .. 127
swap( bit(i), bit((4 * i) % 127) )
4. 3. 선형 변환 (LT)
선형 변환(LT)은 XOR, S-Box, 비트 왼쪽 시프트 및 비트 왼쪽 회전 연산으로 구성된다. 이러한 연산은 4개의 32비트 워드에서 수행된다. 구체적인 연산 과정은 다음과 같다.
for (short i = 0; i < 4; i++) {
X[i] = S[i][B[i] ^ K[i]];
}
X[0] = ROTL(X[0], 13);
X[2] = ROTL(X[2], 3);
X[1] = X[1] ^ X[0] ^ X[2];
X[3] = X[3] ^ X[2] ^ (X[0] << 3);
X[1] = ROTL(X[1], 1);
X[3] = ROTL(X[3], 7);
X[0] = X[0] ^ X[1] ^ X[3];
X[2] = X[2] ^ X[3] ^ (X[1] << 7);
X[0] = ROTL(X[0], 5);
X[2] = ROTL(X[2], 22);
for (short i = 0; i < 4; i++) {
B[i + 1] = X[i];
}
코드는 C++ 형태로 작성되어 있으며, 주요 변수 및 함수는 다음과 같이 나타낼 수 있다.
- `X[i]`: S-Box 연산의 결과값을 저장하는 배열
- `S[i]`: S-Box
- `B[i]`: 입력값 배열
- `K[i]`: 키 배열
- `ROTL(a, b)`: a를 b 비트만큼 왼쪽으로 회전시키는 함수
위 코드에서 `ROTL` 함수는 주어진 값을 특정 비트 수만큼 왼쪽으로 회전시키는 연산을 수행한다. 예를 들어 `ROTL(X[0], 13)`은 `X[0]`의 값을 13비트만큼 왼쪽으로 회전시킨다.
5. Rijndael vs. Serpent
Rijndael과 서펜트는 모두 AES 후보였으며, SPN 구조를 가진 블록 암호 알고리즘이다. Rijndael은 키 크기에 따라 10, 12, 14 라운드로 구성되는 반면, 서펜트는 32 라운드로 구성된다.[7] Rijndael의 키 크기와 블록 크기는 128비트, 192비트, 256비트 중 선택할 수 있다.
5. 1. 라운드 수
Rijndael은 키 크기에 따라 10, 12, 14 라운드로 구성되는 반면, 서펜트는 32 라운드로 구성되어 더 높은 보안 수준을 갖는다.[7] Rijndael은 라운드 수가 10, 12, 14라운드인 SPN 구조를 가지는 반면, 서펜트는 32 라운드의 SPN 구조로, 최적화된 구현을 단순화하기 위해 처음과 마지막에 재배열을 수행한다. 서펜트는 32 라운드를 실행함으로써 Rijndael보다 보안 수준이 높다. 그러나 10 라운드의 Rijndael은 빠르고 구현도 용이하다. 따라서 Rijndael이 AES로 선정되었다.5. 2. 라운드 함수
Rijndael의 라운드 함수는 비선형 계층, 선형 혼합 계층, 키 혼합 XOR 계층의 세 부분으로 구성된다. 서펜트의 라운드 함수는 키 혼합 XOR, 동일한 4×4 S-box 32개를 병렬 적용, 선형 변환으로 구성되며, 마지막 라운드에서는 선형 변환 대신 다른 키 혼합 XOR이 적용된다.[7] Rijndael의 비선형 계층은 8×8 S-box를 사용하는 반면, 서펜트는 8개의 서로 다른 4×4 S-box를 사용한다.[7]5. 3. S-Box
Rijndael은 8×8 S-box를 1개 사용하는 반면, 서펜트는 8개의 서로 다른 4×4 S-box를 사용한다.[7]5. 4. AES 선정
Rijndael은 Serpent보다 보안 수준은 낮지만, 10 라운드의 Rijndael은 속도가 빠르고 구현이 용이하다는 장점이 있었다.[7] 이러한 이유로 Rijndael이 AES로 선정되었다.6. 보안
서펜트는 높은 보안 수준을 목표로 설계되었으나, 몇 가지 공격 방법이 제안되었다.
- 2000년, Kohno 등의 논문은 서펜트의 일부 라운드에 대한 중간 만남 공격과 확대 부메랑 공격을 제시했다.[8]
- 2001년, 엘리 비함 등은 선형 암호 분석 공격을 통해 서펜트의 일부 라운드를 깰 수 있음을 보였다.[9]
- 2009년 논문에서는 서펜트 S-box의 비선형 차수에 대한 문제점이 발견되었다.[10]
- 2011년, Hongjun Wu 등은 선형 암호 분석을 사용하여 서펜트-128의 11라운드를 깰 수 있음을 보였고, 같은 논문에서 서펜트-256의 12라운드를 깨는 두 가지 공격도 설명했다.[11]
6. 1. XSL 공격
XSL 공격이 효과적이라면, 서펜트의 보안을 약화시킬 것이다. 그러나 많은 암호 분석가들은 구현상의 고려 사항을 감안할 때 XSL 공격이 무차별 대입 공격보다 더 많은 비용이 들 것이라고 믿는다.6. 2. 기타 공격
2000년, Kohno 등의 논문은 서펜트의 32라운드 중 6라운드에 대한 중간 만남 공격과 9라운드에 대한 확대 부메랑 공격을 제시했다.[8]2001년, 엘리 비함, Orr Dunkelman, Nathan Keller는 선형 암호 분석 공격을 통해 2118개의 알려진 평문과 289의 시간을 사용하여 서펜트-128의 32라운드 중 10라운드를, 2118개의 알려진 평문과 2187의 시간을 사용하여 서펜트-192/256의 11라운드를 깰 수 있음을 보였다.[9]
2009년 논문에서는 서펜트 S-box의 비선형 차수가 설계자가 주장한 3이 아니라 2차인 요소가 4개 있다는 것을 발견했다.[10]
2011년, Hongjun Wu, Huaxiong Wang, Phuong Ha Nguyen은 선형 암호 분석을 사용하여 2116개의 알려진 평문, 2107.5의 시간 및 2104의 메모리를 사용하여 서펜트-128의 11라운드를 깰 수 있음을 보였다.[11] 같은 논문은 서펜트-256의 12라운드를 깨는 두 가지 공격도 설명한다. 첫 번째 공격은 2118개의 알려진 평문, 2228.8의 시간 및 2228의 메모리가 필요하다. 다른 공격은 2116개의 알려진 평문과 2121의 메모리가 필요하지만, 2237.5의 시간도 필요하다.
7. Serpent-0 vs. Serpent-1
원래의 서펜트-0은 제5회 고속 소프트웨어 암호화 워크숍에서 발표되었지만, 약간 수정된 버전인 서펜트-1이 AES 공모전에 제출되었다. AES 제출 논문에서는 키 스케줄링의 차이점을 포함한 변경 사항들을 논의한다.[1]
참조
[1]
논문
Report on the development of the Advanced Encryption Standard (AES)
https://doi.org/10.6[...]
2001-05
[2]
웹사이트
Serpent Home Page
https://www.cl.cam.a[...]
[3]
웹사이트
Serpent: A Candidate Block Cipher for the Advanced Encryption Standard
http://www.cl.cam.ac[...]
University of Cambridge Computer Laboratory
2006-10-23
[4]
웹사이트
serpent.pdf
https://www.cl.cam.a[...]
2022-04-25
[5]
뉴스
Serpent Holds the Key to Internet Security – Finalists in world-wide encryption competition announced
http://www.cl.cam.ac[...]
1999
[6]
간행물
SERPENT – A Candidate Block Cipher for the Advanced Encryption Standard
http://www.cl.cam.ac[...]
1999
[7]
논문
The Twofish Team's Final Comments on AES Selection
https://www.schneier[...]
2015-01-19
[8]
논문
Preliminary Cryptanalysis of Reduced-Round Serpent
https://www.schneier[...]
[9]
논문
Linear Cryptanalysis of Reduced Round Serpent
Fast Software Encryption|FSE
[10]
논문
On Algebraic Relations of Serpent S-boxes
https://eprint.iacr.[...]
[11]
서적
Information Security and Privacy
ACISP 2011
2014-09-25
[12]
웹사이트
Serpent 公式サイト
http://www.cl.cam.ac[...]
[13]
논문
Report on the development of the Advanced Encryption Standard (AES)
https://doi.org/10.6[...]
2001-05
[14]
웹인용
Serpent Home Page
https://www.cl.cam.a[...]
[15]
웹인용
Serpent: A Candidate Block Cipher for the Advanced Encryption Standard
http://www.cl.cam.ac[...]
University of Cambridge Computer Laboratory
2006-10-23
[16]
웹인용
serpent.pdf
https://www.cl.cam.a[...]
2022-04-25
[17]
뉴스
Serpent Holds the Key to Internet Security – Finalists in world-wide encryption competition announced
http://www.cl.cam.ac[...]
1999
[18]
간행물
SERPENT – A Candidate Block Cipher for the Advanced Encryption Standard
http://www.cl.cam.ac[...]
1999
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com