본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

SEED 형식 암호에서 공격에 강한 S 박스와 G 함수의 실험적 설계
Experimental Design of S box and G function strong with attacks in SEED-type cipher

박창수   (부경대학교 전자컴퓨터정보통신공학부UU0000598  ); 송홍복   (동의대학교 전자·정보통신공학부UU0000509  ); 조경연   (부경대학교 전자컴퓨터정보통신공학부UU0000598  );
  • 초록

    본 논문에서는 $GF({2^n})$ 상 곱셈의 복잡도와 규칙도를 GF(2)상의 다항식 곱셈을 표현하는 행렬식의 행과 열의 해밍 가중치를 이용하여 정의한다 차분공격에 강한 블록 암호 알고리즘을 만들기 위해서는 치환계층과 확산계층의 $GF({2^n})$ 상 곱셈의 복잡도와 규칙도가 높아야함을 실험을 통하여 보인다. 실험 결과를 활용하여 우리나라 표준인 128 비트 블록 암호 알고리즘인 SEED의 S 박스와 G 함수를 구성하는 방식을 제안한다. S 박스는 비 선형함수와 아핀변환으로 구성한다. 비 선형함수는 차분공격과 선형공격에 강한 특성을 가지며, '0'과 '1'을 제외하고 입력과 출력이 같은 고정점과 출력이 입력의 1의 보수가 되는 역고정점을 가지지 않는 $GF({2^8})$ 상의 역수로 구성한다. 아핀변환은 입력과 출력간의 상관을 최저로 하면서 고정점과 역고정점이 없도록 구성한다. G 함수는 4개의 S 박스 출력을 $GF({2^8}) 상의 4 {\times} 4$ 행렬식을 사용하여 선형변환한다. 선형변환 행렬식 성분은 높은 복잡도와 규칙도를 가지도록 구성한다 또한 MDS(Maximum Distance Separable) 코드를 생성하고, SAC(Strict Avalanche Criterion)를 만족하고, 고정점과 역고정점 및 출력이 입력의 2의 보수가 되는 약한 입력이 없도록 G 함수를 구성한다. 비선형함수와 아핀변환 및 G 함수의 원시다항식은 각기 다른 것을 사용한다. 본 논문에서 제안한 S 박스와 G 함수는 차분공격과 선형공격에 강하고, 약한 입력이 없으며, 확산 특성이 우수하므로 안전성이 높은 암호 방식의 구성 요소로 활용할 수 있다.


    In this paper, complexity and regularity of polynomial multiplication over $GF({2^n})$ are defined by using Hamming weight of rows and columns of the matrix ever GF(2) which represents polynomial multiplication. It is shown experimentally that in order to construct the block cipher robust against differential cryptanalysis, polynomial multiplication of substitution layer and the permutation layer should have high complexity and high regularity. With result of the experiment, a way of constituting S box and G function is suggested in the block cipher whose structure is similar to SEED, which is KOREA standard of 128-bit block cipher. S box can be formed with a nonlinear function and an affine transform. Nonlinear function must be strong with differential attack and linear attack, and it consists of an inverse number over $GF({2^8})$ which has neither a fixed pout, whose input and output are the same except 0 and 1, nor an opposite fixed number, whose output is one`s complement of the input. Affine transform can be constituted so that the input/output correlation can be the lowest and there can be no fixed point or opposite fixed point. G function undergoes linear transform with 4 S-box outputs using the matrix of 4 ${\times}$ 4 over $GF({2^8})$ . The components in the matrix of linear transformation have high complexity and high regularity. Furthermore, G function can be constituted so that MDS(Maximum Distance Separable) code can be formed, SAC(Strict Avalanche Criterion) can be met, and there can be no weak input where a fixed point an opposite fixed point, and output can be two`s complement of input. The primitive polynomials of nonlinear function affine transform and linear transformation are different each other. The S box and G function suggested in this paper can be used as a constituent of the block cipher with high security, in that they are strong with differential attack and linear attack with no weak input and they are excellent at diffusion.


  • 주제어

    S 박스 .   암호 .   블록 암호 .   MDS 코드 .   약한 입력.  

  • 참고문헌 (27)

    1. ANSI X3.92, 'American National Standard for Data Encryption Algorithm(DEA),' NIST, 1983 
    2. E. Biham and A. Shamir, 'Differential cryptoanalysis of DES-like cryptosystems,' Journal of Cryptology, Vol. 4, No. 1, pp. 3-72, 1991 
    3. L. Keliher, H. Meijer, and S. Tavares, 'New Method for Upper Bounding the Maximum Average Linear Hull Probability for SPNs,' Advances in Cryptology -EIROCRYPT 2001, LNCS 2045, Springer -Verlag, pp. 420-436, 2001 
    4. T. Jakobsen and L.R. Knudsen, 'The interpolation attack on block cipher,' Fast Software Encryption, LNCS 1267, E. Biham, Ed., Springer-Verlag, pp. 28-40, 1997 
    5. Webster, A. and S. Tavares, 'On the Design of S-Boxes,' Advances on Cryptology, CRYPTO'85, pp. 523-534, 1985 
    6. Jennifer Seberry, Xian-Mo Zhang and Yuliang Zheng, ' Systematic Generation of Cryptographically Robust 5-boxes,' The preceedings of the First ACM Conference on Computer and Communications Security, pp. 172-182, Nov. 1993 
    7. J. Daemen, R. Govaerts and J. Vandewalle, 'Correlation Matrixes,' Fast Software Encryption, LNCS 1008, Spring-Verlag, pp. 275-285, 1994 
    8. NIST, 'Advanced Encryption Standard Development Effort.' http:// csrc.nist.gov / encryption/aes 
    9. A.M. Youssef, Z.G. Chen and S.E. Tavares, 'Construction of Highly Nonlinear Injective S-boxes With Application to CAST-like Encryption Algorithms,' Proceedings of the Canadian Conference on Electrical and Computer Engineering(CCECE'97), 1997 
    10. H.M. Heys and S.E. Tavares, 'The Design of Substitution Permutation Networks Resistant to Differential and Linear Cryptanalysis, Proceedings of 2nd ACM Conference on Computer and Communications Security, Fairfax, Virginia, pp. 148-155, 1994 
    11. V. Rijmen, J. Daemen, B. Preneel, A. Bosselaers and E. De Win, 'The cipher SHARK,' Fast Software Encryption, LNCS 1039, D. Gollmann, Ed., Springer-Verlag, pp. 99-112, 1996 
    12. 정 찬호, 'SEED에 대한 효과적인 Brute-Force 공격 알고리즘,' 한국항공대학교 컴퓨터공학과 석사학위논문, 2001 
    13. J. S. Kang, C. S. Park, S. J. Lee and J. L. Lim, 'On the optimal diffusion layer with practical security against Differential and Linear Cryptanalysis,' Proceedings of ICISC'99, LNCS 1787, Spring-Verlag, pp. 33-52, 1999 
    14. Young-Ho Seo, Jong-Hyeon Kim and Dong-Wook Kim, 'Hardware Implementation of 128-bit Symmetric Cipher SEED,' The Second IEEE Asia Pacific Conference on ASICs, pp. 183-186, Aug. 2000 
    15. 이 명동, 'SEED 암호 알고리즘의 FPGA 구현을 위한 RTL 수준 VHDL 설계,' 한남대학교 대학원 컴퓨터공학과 석사학위논문, 2001 
    16. 전 신우, 정 용진, '128 비트 SEED 암호 알고리즘의 고속처리를 위한 하드웨어 구현,' 통신정보보호학회지, Vol. 11, No. 1, pp. 13-23, Feb. 2001 
    17. Joan Daemen, Vincent Rijmen, 'AES Proposal: Rijndael', 1999 
    18. H.M. Heys and S.E. Tavares, 'The Design of Product Ciphers Resistant to Differential and Linear Cryptanalysis,' Journal of Cryptology, Vol. 9, no. 1, pp. 1-19, 1996 
    19. M. Matsui, 'The first experimental cryptanalysis of the Data Encryption Standard,' Advances in Cryptology, Proceedings of CRYPTO '94, Springer-Verlag, Berlin, pp. 1-11, 1994 
    20. H.M. Heys and S.E. Tavares, 'Avalanche Characteristics of Substitution Permutation Encryption Networks,' IEEE Transaction on Computer, Vol. 44, pp. 1131-1139, Sep. 1995 
    21. K. Nyberg, 'Differentially uniform mappings for cryptography,' Advances in Cryptology, Proceedings of Eurocrypt '93, LNCS 765, T. Helleseth, ED., Springer-Verlag, pp. 55-64, 1994 
    22. 한국정보보호센터, 128 비트 블록 암호알고 리즘(SEED) 개발 및 분석 보고서, Dec. 1998 
    23. A.M. Youssef, S. Mister and S.E. Tavares, 'On the Design of Linear Transformations for Substitution Permutation Encryption Networks,' ACM Symposium on Applied Computing (SAC'97), Feb. 1997 
    24. Nyberg, K., 'Perfect nonlinear S-boxes,' In Advances in Cryptology, EUROCRYPT'91, Vol. 547, Lecture Notes in Computer Science, Springer-Verlag, pp. 378-386, 1991 
    25. S. Vaudenay, 'On the need for multipermutations: Cryptanalysis of MD4 and SAFER,' Proceedings of Fast Software Encryption (2), LNCS 1008, Springer-Verlag, pp. 286-297, 1995 
    26. J. Daemen, L. Knudsen and V. Rijmen, 'The block cipher SQUARE,' Proceedings of Fast Software Encryption (4), LNCS, Springer-Verlag, 1997 
    27. Serge Mister and Carlisle Adams, 'Practical S-box Design,' Workshop record of the workshop on selected area in Cryptography(SAC'96), Queen's University, pp. 61-76, Aug. 1996 

 저자의 다른 논문

  • 박창수 (7)

    1. 2003 "블록 암호에서 교환 계층의 MDS 코드 생성 확인 알고리즘" 한국해양정보통신학회논문지 = The journal of the Korea Institute of Maritime Information & Communication Sciences 7 (7): 1462~1470    
    2. 2006 "갈로이 선형 궤환 레지스터의 일반화" 電子工學會論文誌. Journal of the Institute of Electronics Engineers of Korea. CI, 컴퓨터 43 (1): 1~8    
    3. 2008 "개선된 역수 알고리즘을 사용한 정수 나눗셈기" 한국해양정보통신학회논문지 = The journal of the Korea Institute of Maritime Information & Communication Sciences 12 (7): 1218~1226    
    4. 2008 "대칭구조 SPN 블록 암호 알고리즘" 멀티미디어학회논문지 = Journal of Korea Multimedia Society 11 (8): 1093~1100    
    5. 2009 "대칭구조 SHACAL-1 블록 암호 알고리즘" 컴퓨터산업학회논문지 = Journal of the Korea Computer Industry Society 10 (4): 167~176    
    6. 2009 "대칭구조RC6블록 암호 알고리즘" 한국해양정보통신학회논문지 = The journal of the Korea Institute of Maritime Information & Communication Sciences 13 (4): 675~683    
    7. 2010 "소프트웨어 구현에 적합한 고속 스트림 암호 AA32" 한국통신학회논문지. The Journal of Korea Information and Communications Society. 네트워크 및 서비스 35 (b6): 954~961    
  • 송홍복 (19)

  • 조경연 (34)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기