블록 암호는 Feistel 구조와 SPN 구조로 나눌 수 있다. Feistel 구조는 암호 및 복호 알고리즘이 같은 구조이고, SPN 구조는 암호 및 복호 알고리즘이 다르다. 본 논문에서는 암호와 복호 과정이 동일한 SPN 구조 블록 암호 알고리즘을 제안한다. 즉 SPN 구조 전체를 짝수인 N 라운드로 구성하고 1 라운드부터 N/2 라운드까지는 정함수를 적용하고, (N/2)+1 라운드부터 N 라운드까지는 역함수를 적용한다. 또한 정함수단과 역함수단 사이에 대칭 블록을 구성하는 대칭단을 삽입한다. 본 논문에서 정함수로는 AES의 암호 알고리즘을, 역함수로는 AES의 복호 알고리즘을 사용하고, 대칭단은 간단한 행렬식과 라운드 키 합산으로 구성한다. 본 논문에서 제안한 암호와 복호가 동일한 변형 AES는 하드웨어 구성이 간단한 장점을 가지므로 제한적 하드웨어 및 소프트웨어 환경인 스마트카드와 전자 칩이 내장된 태그와 같은 RFID 환경에서 안전하고 효율적인 암호 시스템을 구성할 수 있다.
블록 암호는 Feistel 구조와 SPN 구조로 나눌 수 있다. Feistel 구조는 암호 및 복호 알고리즘이 같은 구조이고, SPN 구조는 암호 및 복호 알고리즘이 다르다. 본 논문에서는 암호와 복호 과정이 동일한 SPN 구조 블록 암호 알고리즘을 제안한다. 즉 SPN 구조 전체를 짝수인 N 라운드로 구성하고 1 라운드부터 N/2 라운드까지는 정함수를 적용하고, (N/2)+1 라운드부터 N 라운드까지는 역함수를 적용한다. 또한 정함수단과 역함수단 사이에 대칭 블록을 구성하는 대칭단을 삽입한다. 본 논문에서 정함수로는 AES의 암호 알고리즘을, 역함수로는 AES의 복호 알고리즘을 사용하고, 대칭단은 간단한 행렬식과 라운드 키 합산으로 구성한다. 본 논문에서 제안한 암호와 복호가 동일한 변형 AES는 하드웨어 구성이 간단한 장점을 가지므로 제한적 하드웨어 및 소프트웨어 환경인 스마트카드와 전자 칩이 내장된 태그와 같은 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. In this paper, we propose a SPN which has a symmetric structure in encryption and decryption. The whole ope...
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. 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. In this paper, AES encryption and decryption function are selected for the right function and the inverse function, respectively. The symmetric layer is composed with simple matrix and round key addition. Due to the simplicity of the symmetric SPN structure in hardware implementation, the proposed modified AES 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. 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. In this paper, AES encryption and decryption function are selected for the right function and the inverse function, respectively. The symmetric layer is composed with simple matrix and round key addition. Due to the simplicity of the symmetric SPN structure in hardware implementation, the proposed modified AES is believed to construct a safe and efficient cipher in Smart Card and RFID environments where electronic chips are built in.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서 10 라운드 변형 AES를 소프트웨어로 구현 시에 소요되는 주요 연산을 에 보인다.
본 논문에서는 암호와 복호 과정이 상이한 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)의 세 단계로 구성하고 이를 역함수단이라 칭했다.
가설 설정
이는 MixColumn()가 MDS 행렬을 이루기 때문이다. 따라서 공격이 가장 용이한 경우로 대각선 위치에 있는 오직 한 개의 S-박스만이 활성화되는 경우를 가정하였다.
MixColumn() 함수를 수행하면 한 개의 S-박스만이 활성화된다. 이는 공격이 가장 용이한 경우를 가정한 것이다. 3 라운드와 4 라운드와 같은 경우가 실제로 발생하는 입력을 찾지 못했으나 공격이 가장 용이한 패스로 설정하였다.
제안 방법
즉, 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)의 세 단계로 구성하고 이를 역함수단이라 칭했다. 또한 정함수단과 역함수단 사이에 규칙적인 라운드의 반복을 피하기 위해 간단한 행렬식과 라운드의 배타적 논리합으로 구성한 대칭단(Symmetry layer)을 삽입했다.
본 논문에서 제안하는 변형 AES는 암호와 복호 알고리즘이 동일하며, 적용하는 라운드 키는 상호 역순으로 되어있다. 또한 기존의 AES 하드웨어에 대칭단만을 삽입하여 구성할 수 있으므로 기존 AES와 호환하면서 변형 AES 기능을 가지는 하드웨어를 용이하게 구현할 수 있다.
부정차분공격은 바이트 단위로 연산이 적용되는 암호에서 바이트 패턴이 서로 다른 경우 ‘1’, 같은 경우 ‘0’으로 정의된 차이 값을 가지고 분석하는 것으로 입력차분과 출력차분의 전부를 고려해야하는 차분분석보다 용이하게 공격할 수 있다. 본 논문에서 제안한 변형 AES는 정함수단과 역함수단이 반씩 적용되며 중간에 대칭단이 삽입된다. 대칭단에서 차분 패스가 변하면서 활성화되는 S-박스의 수가 증가한다.
이론/모형
SPN 구조는 C. E Shannon의 혼돈(Confusion)과 확산(Diffusion)[2] 이론을 바탕으로 하였다. SPN 구조에서의 암호 라운드 함수는 키합산층(Key addition layer)과 혼돈을 수행하는 치환층(Substitution layer) S 및 확산층(Permutation layer) P의 세 단계로 구성된다.
본 논문에서는 AES의 표준인 FIPS-197[8]에서 정의한 기호를 사용한다. AES는 128 비트 블록이며 키의 길이에 의해 가변적인 라운드를 적용한다.
성능/효과
GNU-C 컴파일러를 사용하여 동작을 검증하였으며, Windows XP, 셀러론 2.8GHz, 700M RAM 환경에서 1억 개 블록에 대하여 10 라운드 AES와 변형 AES의 암호/복호 수행 시간을 테스트한 결과 제안한 알고리즘이 약 3% 정도 수행 시간이 증가하는 것으로 나타났다.
본 논문에서 제안하는 변형 AES는 암호와 복호 알고리즘이 동일하며, 적용하는 라운드 키는 상호 역순으로 되어있다. 또한 기존의 AES 하드웨어에 대칭단만을 삽입하여 구성할 수 있으므로 기존 AES와 호환하면서 변형 AES 기능을 가지는 하드웨어를 용이하게 구현할 수 있다.
본 논문에서는 정함수단에는 안전성이 증명된 AES의 암호 알고리즘을, 역함수단에는 AES의 복호 알고리즘을 사용하였으며, 이를 가칭 변형 AES라 칭했다. 제안한 변형 AES는 암호와 복호 알고리즘이 동일하며, 암호와 복호시의 라운드 키는 상호 역순이다.
제안한 알고리즘은 높은 안전성을 보여주고 있으며, 암호와 복호가 동일하기 때문에 하드웨어 구성이 간단해서 스마트카드 및 RFID 태그와 같은 제한된 하드웨어 및 소프트웨어 환경에서도 쉽게 구현 가능하다. 향후 변형 AES의 부정차분공격 등에 대한 보다 심도 깊은 연구가 요구된다.
이들 공격은 공격 패스를 설정하고, 설정한 패스에서 활동성을 가지는 S-박스의 차분/선형 확률에 의하여 공격 복잡도를 계산한다. 차분/선형 공격에서 최소로 활성화되는 S-박스의 수는 10 라운드 변형 AES에서 69개로 조사되었으며, 이는 기존 AES의 55개보다 많아서 변형 AES의 안전성이 높은 것으로 판단되었다.
후속연구
제안한 알고리즘은 높은 안전성을 보여주고 있으며, 암호와 복호가 동일하기 때문에 하드웨어 구성이 간단해서 스마트카드 및 RFID 태그와 같은 제한된 하드웨어 및 소프트웨어 환경에서도 쉽게 구현 가능하다. 향후 변형 AES의 부정차분공격 등에 대한 보다 심도 깊은 연구가 요구된다.
질의응답
핵심어
질문
논문에서 추출한 답변
Feistel 구조의 장단점은 무엇인가?
각 라운드 함수에 적용하는 키를 라운드 키라고 하며, 이는 마스터 키로부터 생성한다. Feistel 구조는 암호와 복호 알고리즘이 동일하므로 하드웨어 및 소프트웨어 구현이 쉬운 장점이 있는 반면에 한 라운드에서 입력의 반만이 비선형변환되므로 충분한 안전성을 얻기 위해서는 라운드 수가 증가되며, 따라서 하드웨어 구현시 동작 속도가 느려지는 단점이 있다.
SPN 구조는 어떤 이론을 바탕으로 하였는가?
SPN 구조는 C. E Shannon의 혼돈(Confusion)과 확산(Diffusion)[2] 이론을 바탕으로 하였다. SPN 구조에서의 암호 라운드 함수는 키합산층(Key addition layer)과 혼돈을 수행하는 치환층(Substitution layer) S 및 확산층(Permutation layer) P의 세 단계로 구성된다.
AES에 대한 안전성 분석에 차분 공격, 선형 공격, Square 공격, 부매랑 공격, 불능 차분 공격, 부정차분공격 등을 사용할 경우의 이점은 무엇인가?
AES에 대한 안전성 분석은 차분 공격[9], 선형 공격[10], Square 공격[11], 부매랑 공격[12], 불능 차분 공격(Impossible Differentials Cryptanalysis)[13], 부정차분공격(Truncated Differentials Cryptanalysis)[14] 등이 수행되었다. 이들 공격은 공격 패스를 설정하고, 설정한 패스에서 활동성을 가지는 S-박스의 차분/선형 확률에 의하여 공격 복잡도를 계산한다. 그러므로 변형 AES의 안전성을 검증하기 위해서는 최적의 패스에서 활동성을 가지는 S-박스의 수를 산출하고 이를 AES와 비교하여 상대적인 안전성을 분석할 수 있다.
참고문헌 (16)
H. Feistel, "Cryptography and Computer Privacy", Scientific American, Vol. 228, No. 5, page 15-23, 1973.
National Bureau of Standards, Data Encryption Standard, FIPS-Pub. 46. National Bureau of Standards, U.S. Department of Commerce, Washington D.C., January 1977
"Report on the Development of the Advanced Encryption Standard(AES)", http://www.csrc.nist.gov/encryption/aes/.
J. Daemen, and V. Rijmen, "AES Proposal: Rijndael," http://www.csrc.nist.gov/encryption/ aes/rijndael/Rijndael.pdf, 1999.
SEED, http://www.kisa.or.kr/seed/.
ARIA, http://www.nsri.re.kr/ARIA/.
Federal Information Processing Standards Publication 197, "Announcing the ADVANCED ENCRYPTION STANDARD(AES)," Nov. 2001,csrc.nist.gov/publications/fips/fips197/fips-197.pdf
E. Biham and A. Shamir, "Differential Cryptanalysis of the Full 16-Round DES", LNCS 537, page 2-21, 1990.
M. Matsui, "Linear Cryptanalysis Method for DES", LNCS 765, page 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, page 42-57, 2005.
J. Cheon, M. Kim, K. Kim, J. Lee and S. Kang, "Improved impossible differential cryptanalysis of Rijndael and Crypton", LNCS 2288, page 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 cryptanalysis for the SPN structure," In Fast Software Encryption 2000, LNCS Vol.1978, pp. 273-283, 2001.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.