블록 암호는 Feistel 구조와 SPN 구조로 나눌 수 있다. Feistel 구조는 암호 및 복호 알고리즘이 같은 구조이고, SPN 구조는 암호 및 복호 알고리즘이 다르다. SPN 구조에서의 암호 및 복호 라운드 함수는 키 합산층과 S-박스에 의하여 혼돈을 수행하는 치환층 및 확산층의 세 단계로 구성된다. AES, ARIA 등 많은 SPN 구조에서 8 비트 S-박스를 사용하므로 Square 공격, 부메랑 공격, 불능 차분 공격 등이 유효하다. 본 논문에서는 암호와 복호 과정이 동일한 SPN 구조 블록 암호 알고리즘을 제안한다. SPN 구조 전체를 짝수인 N 라운드로 구성하고 1 라운드부터 N/2 라운드까지는 정함수를 적용하고, (N/2)+1 라운드부터 N 라운드까지는 역함수를 적용한다. 또한 정함수단과 역함수단 사이에 대칭 블록을 구성하는 대칭단을 삽입한다. 대칭단은 간단한 비트 슬라이스대합 S-박스로 구성한다. 비트 슬라이스 대합 S-박스는 Square 공격, 부메랑 공격, 불능 차분 공격 등의 공격을 어렵게 한다. 본 논문에서 제안한 SPN 블록 암호는 제한적 하드웨어 및 소프트웨어 환경인 스마트카드와 전자칩이 내장된 태그와 같은 RFID 환경에서 안전하고 효율적인 암호 시스템을 구성할 수 있다.
블록 암호는 Feistel 구조와 SPN 구조로 나눌 수 있다. Feistel 구조는 암호 및 복호 알고리즘이 같은 구조이고, SPN 구조는 암호 및 복호 알고리즘이 다르다. SPN 구조에서의 암호 및 복호 라운드 함수는 키 합산층과 S-박스에 의하여 혼돈을 수행하는 치환층 및 확산층의 세 단계로 구성된다. AES, ARIA 등 많은 SPN 구조에서 8 비트 S-박스를 사용하므로 Square 공격, 부메랑 공격, 불능 차분 공격 등이 유효하다. 본 논문에서는 암호와 복호 과정이 동일한 SPN 구조 블록 암호 알고리즘을 제안한다. SPN 구조 전체를 짝수인 N 라운드로 구성하고 1 라운드부터 N/2 라운드까지는 정함수를 적용하고, (N/2)+1 라운드부터 N 라운드까지는 역함수를 적용한다. 또한 정함수단과 역함수단 사이에 대칭 블록을 구성하는 대칭단을 삽입한다. 대칭단은 간단한 비트 슬라이스 대합 S-박스로 구성한다. 비트 슬라이스 대합 S-박스는 Square 공격, 부메랑 공격, 불능 차분 공격 등의 공격을 어렵게 한다. 본 논문에서 제안한 SPN 블록 암호는 제한적 하드웨어 및 소프트웨어 환경인 스마트카드와 전자칩이 내장된 태그와 같은 RFID 환경에서 안전하고 효율적인 암호 시스템을 구성할 수 있다.
Feistel and SPN are the two main structures in a block cipher. Feistel is a symmetric structure which has the same structure in encryption and decryption, but SPN is not a symmetric structure. Encrypt round function and decrypt round function in SPN structure have three parts, round key addition and...
Feistel and SPN are the two main structures in a block cipher. Feistel is a symmetric structure which has the same structure in encryption and decryption, but SPN is not a symmetric structure. Encrypt round function and decrypt round function in SPN structure have three parts, round key addition and substitution layer with S-box for confusion and permutation layer for defusion. Most SPN structure for example ARIA and AES uses 8 bit S-Box at substitution layer, which is vulnerable to Square attack, Boomerang attack, Impossible differentials cryptanalysis etc. In this paper, we propose a SPN which has a symmetric structure in encryption and decryption. The whole operations of proposed algorithm are composed of the even numbers of N rounds where the first half of them, 1 to N/2 round, applies a right function and the last half of them, (N+1)/2 to N round, employs an inverse function. And a symmetry layer is located in between the right function layer and the inverse function layer. The symmetric layer is composed with a multiple simple bit slice involution S-Boxes. The bit slice involution S-Box symmetric layer increases difficult to attack cipher by Square attack, Boomerang attack, Impossible differentials cryptanalysis etc. The proposed symmetric SPN block cipher with bit slice involution S-Box is believed to construct a safe and efficient cipher in Smart Card and RFID environments where electronic chips are built in.
Feistel and SPN are the two main structures in a block cipher. Feistel is a symmetric structure which has the same structure in encryption and decryption, but SPN is not a symmetric structure. Encrypt round function and decrypt round function in SPN structure have three parts, round key addition and substitution layer with S-box for confusion and permutation layer for defusion. Most SPN structure for example ARIA and AES uses 8 bit S-Box at substitution layer, which is vulnerable to Square attack, Boomerang attack, Impossible differentials cryptanalysis etc. In this paper, we propose a SPN which has a symmetric structure in encryption and decryption. The whole operations of proposed algorithm are composed of the even numbers of N rounds where the first half of them, 1 to N/2 round, applies a right function and the last half of them, (N+1)/2 to N round, employs an inverse function. And a symmetry layer is located in between the right function layer and the inverse function layer. The symmetric layer is composed with a multiple simple bit slice involution S-Boxes. The bit slice involution S-Box symmetric layer increases difficult to attack cipher by Square attack, Boomerang attack, Impossible differentials cryptanalysis etc. The proposed symmetric SPN block cipher with bit slice involution S-Box is believed to construct a safe and efficient cipher in Smart Card and RFID environments where electronic chips are built in.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 암호와 복호 과정이 상이한 SPN 구조 블록 암호 알고리즘을 암복호 과정이 동일한 SPN 구조로 변형시키는 방식을 제안한다. 즉, 제안하는 블록 암호 알고리즘은 짝수 N 라운드로 구성하고, 1 라운드부터 N/2 라운드까지의 전반부 라운드 함수는 키합산층(Key addition layer)과 치환층 (Substitution layer) S 및 확산층(Permutation layer) P의 세 단계로 구성하고 이를 정함수단이라 가칭한다.
본 논문에서는 암호와 복호 과정이 상이한 SPN 구조 블록 암호 알고리즘을 암복호 과정이 동일한 SPN 구조로 변형시키는 방식을 제안했다. 즉, 1 라운드부터 N/2 라운드까지의 전반부 라운드 함수는 키합산층(Key addition layer)과 치환층(Substitution layer) S 및 확산층(Permutation layer) P의 세 단계로 구성하고 이를 정함수단이라 칭했으며, 후반부 (N/2) + 1 라운드부터 N 라운드까지는 역확산층 (Inverse Permutation layer) P-1과 역치환층(Inverse Substitution layer) S-1 및 키합산층(Key addition layer)의 세 단계로 구성하고 이를 역함수단이라 칭했다.
[9]에서는 대칭단으로 대합 행렬식을 사용하였는데, 이는 MDS(Maximum Distance Separated)가 아니며 또한 라운드간 바이트 전달 특성에 영향을 주지 않는다. 본 논문에서는 이를 개선하기 위하여 대칭단으로 비트 슬라이스 대합 S-박스를 적용하여서 안전성을 높였다.
가설 설정
∙ AddRoundKey() 함수는 라운드 키 덧셈 함수이 다.
이는 MixColumn()가 MDS 행렬을 이루기 때문이다. 따라 서 공격이 가장 용이한 경우로 대각선 위치에 있는 오직 한 개의 S-박스만이 활성화되는 경우를 가정하였다.
MixColumn() 함수를 수행하면 한 개의 S-박스 만이 활성화된다. 이는 공격이 가장 용이한 경우를 가정한 것이다. 3 라운드와 4 라운드와 같은 경우가 실제로 발생하는 입력을 찾지 못했으나 공격이 가장 용이한 패스로 설정하였다.
제안 방법
NU-C 컴파일러를 사용하여 동작을 검증하였으며, Windows XP, 셀러론 2.8GHz, 700M RAM 환경에서 1억 개 블록에 대하여 10 라운드 AES와 대칭 AES 및 12 라운드 ARIA의 암호/복호 수행 시간을 측정하였다. 그 결과 대칭 AES는 AES 보다 6% 정도 수행 시간이 증가하는 것으로 나타났다.
즉, 1 라운드부터 N/2 라운드까지의 전반부 라운드 함수는 키합산층(Key addition layer)과 치환층(Substitution layer) S 및 확산층(Permutation layer) P의 세 단계로 구성하고 이를 정함수단이라 칭했으며, 후반부 (N/2) + 1 라운드부터 N 라운드까지는 역확산층 (Inverse Permutation layer) P-1과 역치환층(Inverse Substitution layer) S-1 및 키합산층(Key addition layer)의 세 단계로 구성하고 이를 역함수단이라 칭했다. 또한 정함수단과 역함수단 사이에 바이트 단위 S-박스 공격에 강건하기 위해서 32개의 비트 슬라이스 S-박스로 구성된 대칭단(Symmetry layer) 을 삽입했다
본 논문에서 제안하는 대칭 AES는 암호와 복호 알고리즘이 동일하며, 적용하는 라운드 키는 상호 역순으로 되어있다. 또한 기존의 AES 하드웨어에 대칭 단만을 삽입하여 구성할 수 있으므로 기존 AES와 호환하면서 대칭 AES 기능을 추가로 가지는 AES를 설계할 수 있다.
본 논문에서는 암호와 복호 과정이 상이한 SPN 구조 블록 암호 알고리즘을 암복호 과정이 동일한 SPN 구조로 변형시키는 방식을 제안한다. 즉, 제안하는 블록 암호 알고리즘은 짝수 N 라운드로 구성하고, 1 라운드부터 N/2 라운드까지의 전반부 라운드 함수는 키합산층(Key addition layer)과 치환층 (Substitution layer) S 및 확산층(Permutation layer) P의 세 단계로 구성하고 이를 정함수단이라 가칭한다. 후반부 ‘(N/2) + 1’ 라운드부터 N 라운드까지는 역확산층(Inverse Permutation layer) P-1과 역치환층(Inverse Substitution layer) S-1 및 키합산층 (Key addition layer)의 세 단계로 구성하고 이를 역함수단이라 가칭한다.
이론/모형
AES[4], ARIA[5] 등은 SPN 구조이다. SPN 구조는 C. E Shannon의 혼돈(Confusion)과 확산(Diffusion)[6] 이론을 바탕으로 하였다. SPN 구조에서의 암호 라운드 함수는 키합산층(Key addition layer)과 혼돈을 수행하는 치환층 (Substitution layer) S 및 확산층(Permutation layer) P의 세 단계로 구성된다.
본 논문에서는 AES의 표준인 FIPS-197[4]에서 정의한 기호를 사용한다. AES는 128 비트 블록이며 키의 길이에 의해 가변적인 라운드를 적용한다.
성능/효과
8GHz, 700M RAM 환경에서 1억 개 블록에 대하여 10 라운드 AES와 대칭 AES 및 12 라운드 ARIA의 암호/복호 수행 시간을 측정하였다. 그 결과 대칭 AES는 AES 보다 6% 정도 수행 시간이 증가하는 것으로 나타났다. 이는 표 3의 결과에 일치한다.
본 논문에서는 정함수단에는 안전성이 증명된 AES의 암호 알고리즘을, 역함수단에는 AES의 복호 알고리즘을 사용하였으며, 이를 가칭 대칭 AES라 칭했다. 제안한 대칭 AES는 암호와 복호 알고리즘이 동일하며, 암호와 복호시의 라운드 키는 상호 역순이다.
따라서 AES나 ARIA와 같이 바이트 단위 S-박스만으로 구성된 SPN 구조에서 유용한 공격 방식인 Square 공격, 부메랑 공격, 불능 차분공격, 부정차분공격 등이 제안한 대칭 AES에서는 효율적인 공격 방법이 아니다. 제안한 알고리즘은 높은 안전성을 보여주고 있으며, 암호와 복호가 동일하기 때문에 하드웨어 구성이 간단해서 스마트카드 및 RFID 태그와 같은 제한된 하드웨어 및 소프트웨어 환경에서도 쉽게 구현 가능하다.
가장 대표적인 공격 방법인 차분 공격과 선형 공격은 공격 패스를 설정하고, 설정한 패스에서 활동성을 가지는 S-박스의 차분/선형 확률에 의하여 공격 복잡도를 계산한다. 최소로 활성화되는 S-박스의 수는 10 라운드 대칭 AES에서 51개로 조사되었으며, 이는 기존 AES의 55개보다 적은 수치이다. 그러나 마지막 라운드는 공격하지 않으므로 9 라운드까지의 활성화되는 S-박스의 수가 공격 복잡도를 결정한다.
질의응답
핵심어
질문
논문에서 추출한 답변
Feistel 구조의 장단점은?
Feistel 구조에서 라운드 함수는 입력을 둘로 나누고, 나누어진 반쪽에 라운드 키를 적용하여 비선형변환을 하고, 이를 나머지 반쪽과 배타적 논리합 즉 XOR 연산을 수행한 후에 서로 치환한다. Feistel 구조는 암호와 복호 알고리즘이 동일하므로 하드웨어 및 소프트웨어 구현이 쉬운 장점이 있는 반면에 한 라운드에서 입력의 반만이 비선형 변환되므로 충분한 안전성을 얻기 위해서는 라운드 수가 증가되며, 따라서 하드웨어 구현시 동작 속도가 느려 지는 단점이 있다. AES[4], ARIA[5] 등은 SPN 구조이다.
비밀키 블록 암호는 라운드 함수의 구조에 따라서 어떻게 나눌 수 있나?
이러한 비밀키 블록 암호의 암호 및 복호 알고리즘은 암호 및 복호 함수를 여러 라운드 반복 수행하는 구조이다. 비밀키 블록 암호는 라운드 함수의 구조에 따라서 Feistel 구조[1]와 SPN(Sub stitution Permutation Network) 구조로 나눌 수 있다.
SPN 구조는 어떤 장점을 가지고 있나?
SPN 구조는 암호와 복호 알고리즘이 다르므로 구현이 복잡해지지만 각 라운드에서 입력이 전부 비선형변환되므로 라운드의 수가 적어진다. 따라서 하드웨어의 동작 속도가 빠른 장점을 가진다. 1970년대에 개발되어 산업계표준으로 사용되던 DES는 안전성에 문제가 있어 미국을 비롯한 유럽 및 선진국들은 자국의 표준 블록 암호 개발에 주력하고 있다.
참고문헌 (17)
H. Feistel, "Cryptography and Computer Privacy", Scienti- fic American, Vol. 228, No. 5, pp. 15-23, 1973.
National Bureau of Standards, Data Encryption Standard, FIPS-Pub. 46. National Bureau of Standards, U.S. Depart- ment of Commerce, Washington D.C., January 1977.
SEED, http://www.ietf.org/rfc4269.txt.
Federal Information Processing Standards Publication 197, "Announcing the Advanced Encryption Standard(AES)," Nov. 2001, csrc.nist.gov/publications/fips/ fips197/ fips- 197.pdf.
Daesung Kwon, et. al., "New block cipher : ARIA," Information security and cryptology - ICISC 2003, 6th international, pp. 432-445, 2003.
C.E. Shannon, "Communication Theory of Secrecy System" Bell System Technical Journal, Vol. 28, No. 4, pp. 656-715, 1949.
E. Biham and A. Shamir, "Differential Cryptanalysis of the Full 16-Round DES", LNCS 537, pp. 2-21, 1990.
M. Matsui, "Linear Cryptanalysis Method for DES", LNCS 765, pp. 386-397, 1994.
J. Daemen, L. Knudsan, and V. Rijmen, "The Block Cipher Square," Proceeding of FSE`97, LNCS Vol.1267, pp. 149-165, 1997.
A. Birynkov, "The Boomerang attack on 5 and 6-round reduced AES", LNCS 3373, pp. 42-57, 2005.
J. Cheon, M. Kim, K. Kim, J. Lee and S. Kang, "Improved impossible differential cryptanalysis of Rijndael and Crypton", LNCS 2288, pp. 39-49, 2001.
L. R. Knudsen, "Truncated and higher order differential," Fast Software Encryption-Second International Workshop, LNCS Vol. 1008, pp. 196-211, 1995.
A. M. Youssef, S. Mister, and S. E. Tavares, "On the Design of linear Transformation for Substitution and Permutation Encryption Networks," in the Workshop Record of the Workshop on Selected Areas in Cryptography (SAC `97), pp. 40-48, Aug. 1997.
S. Hong, S. Lee, J. Lim, J. Sung, and D. Cheon, "Provable security against differential and linear crypta- nalysis for the SPN structure," In Fast Software Encryp- tion 2000, LNCS Vol. 1978, pp. 273-283, 2001.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.