본 논문에서는 라운드 함수의 업데이트 함수로 SP 구조를 사용하고 비밀 S-box가 적용된 GFN(Generalized Feistel Networks) Type I, Type II, Type III에 대한 안전성을 분석한다. 이 환경에서 공격자는 S-box에 대한 정보를 갖지 못한다. 인테그랄 공격 기법(Integral attack) 기반의 선택 평문 공격으로 9 라운드(Type I), 6 라운드(Type II), 6라운드(Type III)에 대한 비밀 S-box 정보를 복구할 수 있다. 선택 암호문 공격으로 전환할 경우 GFN Type I의 16 라운드까지 비밀 S-box의 정보가 복구된다. 결론적으로 m비트 비밀 S-box와 $k{\times}k$MDS 행렬이 라운드 함수로 사용된 GFN Type I, Type II, Type III에 대하여 비밀 S-box를 복구하는데 ${\frac{2^{3m}}{32k}},{\frac{2^{3m}}{24k}},{\frac{2^{3m}}{36k}}$만큼의 시간복잡도가 필요하다.
본 논문에서는 라운드 함수의 업데이트 함수로 SP 구조를 사용하고 비밀 S-box가 적용된 GFN(Generalized Feistel Networks) Type I, Type II, Type III에 대한 안전성을 분석한다. 이 환경에서 공격자는 S-box에 대한 정보를 갖지 못한다. 인테그랄 공격 기법(Integral attack) 기반의 선택 평문 공격으로 9 라운드(Type I), 6 라운드(Type II), 6라운드(Type III)에 대한 비밀 S-box 정보를 복구할 수 있다. 선택 암호문 공격으로 전환할 경우 GFN Type I의 16 라운드까지 비밀 S-box의 정보가 복구된다. 결론적으로 m비트 비밀 S-box와 $k{\times}k$ MDS 행렬이 라운드 함수로 사용된 GFN Type I, Type II, Type III에 대하여 비밀 S-box를 복구하는데 ${\frac{2^{3m}}{32k}},{\frac{2^{3m}}{24k}},{\frac{2^{3m}}{36k}}$만큼의 시간복잡도가 필요하다.
In this paper, we analyze Generalized Feistel Network(GFN) Type I, Type II, Type III that round function use SP update function, secret S-box and $k{\times}k$ MDS matirx. In this case an attacker has no advantage about S-box. For each type of GFN, we analyze and restore secret S-box in 9,...
In this paper, we analyze Generalized Feistel Network(GFN) Type I, Type II, Type III that round function use SP update function, secret S-box and $k{\times}k$ MDS matirx. In this case an attacker has no advantage about S-box. For each type of GFN, we analyze and restore secret S-box in 9, 6, 6 round using the basis of integral cryptanalysis with chosen plaintext attack. Also we restore secret S-box in 16 round of GFN Type I with chosen ciphertext attack. In conclusion, we need $2^{2m}$ data complexity and ${\frac{2^{3m}}{32k}},{\frac{2^{3m}}{24k}},{\frac{2^{3m}}{36k}}$ time complexity to restore m bit secret S-box in GFN Type I, Type II, Type III.
In this paper, we analyze Generalized Feistel Network(GFN) Type I, Type II, Type III that round function use SP update function, secret S-box and $k{\times}k$ MDS matirx. In this case an attacker has no advantage about S-box. For each type of GFN, we analyze and restore secret S-box in 9, 6, 6 round using the basis of integral cryptanalysis with chosen plaintext attack. Also we restore secret S-box in 16 round of GFN Type I with chosen ciphertext attack. In conclusion, we need $2^{2m}$ data complexity and ${\frac{2^{3m}}{32k}},{\frac{2^{3m}}{24k}},{\frac{2^{3m}}{36k}}$ time complexity to restore m bit secret S-box in GFN Type I, Type II, Type III.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 SP 함수를 업데이트 함수로 사용하는 GFN Type I, Type II, Type III에서 비밀 S-box를 사용하였을 때, S-box에 대한 정보가 전혀 없는 공격자가 S-box를 복원하는 방법에 대하여 알아보았다. 또한, [1,2]에서 보여준 SP 구조에서 비밀 S-box의 복원에서 동차방정식이 구성되는데 반해 GFN에서는 비동차방정식이 구성되어 훨씬 수월하게 비밀 S-box가 복원됨을 알 수 있다.
본 논문에서는 비밀 S-box가 적용된 GFN Type I, Type II, Type III에 대해 비밀 S-box를 복원하는 방법을 소개한다. 이때 라운드 함수의 업데이트 함수는 SP구조로 가정하고, S로 사용되는 S-box는 공격자에게 정보가 알려지지 않은 m비트 전단사 S-box(Secret bijective S-box)를 사용하고, P로는 확산(Diffusion)의 영향이 가장 큰 MDS(Maximum Distance Seperable) 코드를 사용한다고 가정한다.
비밀 S-box에 대한 연구는 암호 알고리즘에 적용된 화이트박스(White-box)를 복원하는 연구의 중요한 흐름 중 하나로 볼 수 있다. 화이트박스는 암호 알고리즘의 안전성을 높이기 위한 방법으로 암호 연산 중 생기는 모든 정보가 사용자에게 노출 되더라도 안전한 암호 시스템을 만드는 것을 목표로 한다. 비밀 S-box는 공격자에게 S-box에 대한 정보가 노출되지 않기 때문에, 공격자가 연산 중간값을 알더라도 비밀값을 복원하는데 어려움이 존재한다.
가설 설정
각 브랜치를 업데이트하는 Fi,j함수는 동일한 m비트 비밀 S-box k개와동일한 k×k MDS 행렬을 사용하는 SP 구조로 가정한다.
본 논문에서는 비밀 S-box가 적용된 GFN Type I, Type II, Type III에 대해 비밀 S-box를 복원하는 방법을 소개한다. 이때 라운드 함수의 업데이트 함수는 SP구조로 가정하고, S로 사용되는 S-box는 공격자에게 정보가 알려지지 않은 m비트 전단사 S-box(Secret bijective S-box)를 사용하고, P로는 확산(Diffusion)의 영향이 가장 큰 MDS(Maximum Distance Seperable) 코드를 사용한다고 가정한다. GFN이 특정된 라운드함수를 사용하지 않기 때문에 구조적 암호 분석 기법으로 분석이 될 수 있으며, 인테그랄 공격을 적용하여 비밀 S-box를 복원할 수 있다.
제안 방법
2) 충분한 방정식을 획득하면 이를 이용하여 S-box를 복원할 연립방정식을 구성한다. 가능한 S-box의 진리표를 2m × m행렬로 구성하면, S-box가 전단사함수이기 때문에 m개의 열들이 선형독립을 이룬다.
Zheng 등에 의해 제안되었다[6]. 이 연구진은 브랜치의 개수가 임의의 t개로 확장되었을 경우에 대하여, 각 라운드별로 브랜치가 업데이트되는 방법에 따라 Type I, Type II, Type III로 구분하여 정의하였다. GFN은 페이스텔 구조 보다 다양한 라운드 함수를 구성할 수 있는 장점으로 인해 많은 암호 설계에 적용되었으며, 대표적으로 GFN Type II를 사용한 CLEFIA [15]가 존재한다.
대상 데이터
본 논문에서는 브랜치의 개수가 4개인 GFN Type I, Type II, Type III에 대하여 분석을 진행할 것이다(Fig 2. 참고). 각 브랜치를 업데이트하는 Fi,j함수는 동일한 m비트 비밀 S-box k개와동일한 k×k MDS 행렬을 사용하는 SP 구조로 가정한다.
성능/효과
3) 획득한 연립방정식의 해로부터 정확한 S-box를 복원할 수는 없지만, 연립방정식 해의 아핀 동치(affine equivalent) 중 하나는 정확한 S-box를 표현하고 있다. 그렇기 때문에 연립방정식으로부터 얻어진 임의의 S-box를 실제 S-box로 가정하면, 임의의 아핀 함수와 역함수가 A2 계층에 추가로 적용된 형태로 생각할 수 있다.
4) 암호문으로부터 S1 계층을 같은 방법으로 제거한 후 남은 A1′ 계층과 A2′ 계층의 복원은Biham‘s low rank detection technique[14]을 이용하여 해결할 수 있다.
m비트 비밀 S-box를 사용하였을 경우 이를 복원하는데 GFN Type I, Type II, Type III 에 대하여 각각 최대 16라운드, 6라운드, 6라운드까지 공격이 가능하고, , , 의 복잡도가 필요하다. 이 결과로 2.5라운드 SP 구조에 해당되는 SASAS에서의 S 계층 복원 공격보다 더 많은 라운드가 분석되어 라운드 하한을 더 크게 가져가야함을 알 수 있다.
Biryukov와 Shamir는 S(Substitution) 계층과 A(Affine) 계층으로 나누어진 SASAS 구조에 대해 S 계층과 A 계층을 복원하는 방법을 소개하였다 [2]. 이러한 분석으로 2.5 라운드로 구성된 SP 구조는 전수조사보다 효과적으로 내부 상태를 완벽하게 복원할 수 있으므로 안전하지 않음을 알 수 있다.
이를 이용하여 선택 평문 공격의 결과로 9라운드(Type I), 6라운드(Type II), 6라운드(Type III)에서 비밀 S-box가 복원됨을 보이고, 각각 (Type I), (Type II), (Type III)의 복잡도가 필요함을 보인다.
후속연구
본 논문의 비밀 S-box의 복원과정이 인테그랄 공격에 기반을 두고있는 방법인 만큼 Division Property를 이용하여 비밀 S-box를 복원할 수 있는 추가적인 기법의 연구가 가능할 것으로 전망한다. Division Property를 적용한 추가적인 연구가 이루어진다면, 비밀 S-box를 적용하더라도 안전성에 위협을 받지 않도록 암호알고리즘을 설계할 수 있을 것이다.
Todo에 의해 제안된 이후 몇몇 암호들이 기존에 알려진 인테그랄 공격보다 더 많은 라운드가 분석이 되었다. 본 논문의 비밀 S-box의 복원과정이 인테그랄 공격에 기반을 두고있는 방법인 만큼 Division Property를 이용하여 비밀 S-box를 복원할 수 있는 추가적인 기법의 연구가 가능할 것으로 전망한다. Division Property를 적용한 추가적인 연구가 이루어진다면, 비밀 S-box를 적용하더라도 안전성에 위협을 받지 않도록 암호알고리즘을 설계할 수 있을 것이다.
참고문헌 (15)
T.Tiessen, L.R.Knudsen, S.Kolbl, and M.M.Lauridsen, Security of the AES with a Secret S-box, Fast Software Encryption 2015, August 2015.
A.Biryukov, and A.Shamir, Structural Cryptanalysis of SASAS, EUROCRYPT 2001, April, 2001.
L.Knudsen, and D.Wagner, Integral Cryptanalysis (Extended Abstract), Fast Software Encryption 2002, July, 2002.
National Institute of Standards and Technology, Advanced Encryption Standard, Federal Information Processing Standard (FIPS), November, 2001.
National Bureau of Standards, Data Encryption Standard (DES), Federal Information Processing Standard (FIPS), 1999.
Y.Zheng, T.Matsumoto, and H.Imai, On the construction of block ciphers provably secure and not relying on any unproved hypotheses. CRYPTO 1989. LNCS, vol. 435, pp. 461-480. Springer, Heidelberg (1990)
J.Daemen, L.Knudsen, and V.Rijmen, The block cipher Square, Fast Software Encryption 97, January, 1997.
Y.Todo, Integral Cryptanalysis on Full MISTY1, Fast Software Encryption 2015, August, 2015.
M.Matsui, New block encryption algorithm MISTY, Fast Software Encryption 97, January, 1997.
J.Park, S.Lee, J.Kim, and J.Lee, Korea Internet and Security Agency, The SEED encryption algorithm, RFC 4269, 2005.
D.Hong, J.Sung, S.Hong, J.Lim, S.Lee, B.Koo, C.Lee, D.Chang, J.Lee, K.Jeong, H.Kim, J.Kim, and S.Chee, HIGHT: A New Block Cipher Suitable for Low-Resource Device, International Workshop on Cryptographic Hardware and Embedded Systems, October, 2006.
D.Hong, J.Lee, D.Kim, K.H.Ryu, and D.Lee, LEA: A 128-Bit Block Cipher for Fast Encryption on Common Processors, International Workshop on Information Security Applications, 2013.
D.Kwon, J.Kim, S.Park, S.H.Sung, Y.Sohn, J.H.Song, Y.Yeom, E.Yoon, S.Lee, J.Lee, S.Chee, D.Han, and J.Hong, New Block Cipher: ARIA, International Conference on Information Security and Cryptology, 2003.
E. Biham, Cryptanalysis of Patarin's 2-Round Public key System with S-boxes(2R), EUROCRYPT 2000, May, 2000.
T.Shirai, K.Shibutani, T.Akishita, S.Moriai, and T.Iwata, The 128-bit Blockcipher CLEFIA, Fast Software Encryption 2007, March, 2007.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.