본문 바로가기
KERD
논문KCI 등재

소프트웨어 구현에 적합한 스트림 암호의 대수적 공격에 대한 안전성

Security Analysis of Software-Oriented Stream Ciphers against Algebraic Attacks

이상진|문덕재|임흥수|지성택|성재철
한국정보보호학회 (Korea Institute Of Information Security And Cryptology)|2005.02|정보보호학회논문지 (Journal of The Korea Institute of Information Security and Cryptology)|제15권 제1호|pp. 29-40

0

조회

0

다운로드

2

인용

0

참고문헌

주제분류컴퓨터학

초록

본 논문에서는 최근 제안된 소프트웨어 구현에 적합한 (블록 단위) 스트림 암호인 HELIX, SCREAM, MUGI, PANAMA 알고리즘들의 대수적 공격에 대한 안전성을 분석한다.[14,16,24,10] 대수적 공격은 알려진 입출력 쌍을 가지고 내부 알고리즘의 기본 대수 방정식을 이용하는 방법으로, 과포화된 다변수 연립 방정식을 통하여 변수의 값을 얻고 이를 이용하여 키를 복구해내는 방법이다.[3,4,7,8,18] 이 분석법은 초기 대수적 특성을 지닌 블록 암호의 분석에 적용되었으나, 이후 블록 암호보다는 스트림 암호의 분석에 보다 용이하게 적용되었다.[1,5,6] 그러나 일반적인 알고리즘을 이 분석법을 그대로 적용하기에는 많은 어려움이 존재한다. 따라서 본 논문에서는 최근 제안된 워드 단위의 소프트웨어 구현에 적합한 스트림 암호의 각 알고리즘에 대해 대수적 방정식과 변수의 수를 비교 및 분석함으로써 각 알고리즘의 대수적 공격에 대한 내성을 살펴본다. 또한 이러한 분석을 통해 대수적 공격에 안전한 소프트웨어 구현에 적합한 스트림 암호의 설계 시 고려해야 할 세 가지 설계 고려사항을 제시한다.

Abstract

In this paper we consider the security of recently proposed software-oriented stream cipher HELIX, SCREAM, MUGI, and PANAMA against algebraic attacks.[14,15,24,10] Algebraic attack is a key recovery attack by solving an over-defined system of multi-variate equations with input-output pairs of an algorithm.[3,4,7,8,18] The attack was firstly applied to block ciphers with some algebraic properties and then it has been more usefully applied to stream ciphers.[1,5,6] However, it is difficult to obtain over-defined algebraic equations for a given cryptosystem in general. Here we analyze recently proposed software-oriented stream ciphers by constructing a system of equations for each cipher. Furthermore we propose three design considerations of software-oriented stream ciphers.

참고문헌 (26)

  1. "Algebraic Attacks on Combiners with Memory", lncs 2729, pp.162~175 (2003), springer- verlag
  2. "Rabbit : A New High-Performance Stream Cipher", 2887, pp.307~327 (2003), Springer-Verlag
  3. "The Security of Hidden Field Equations", lncs 2020, pp.266~281 (2001), springer-verlag
  4. "XL algorithm and Cryptanalysis of Toyocrypt The 5th International Conference on Information Security and Cryptography - ICISC 2002", 2587 (2002), Springer- Verlag
  5. "Fast Algebraic Attack on Stream Ciphers with Linear Feedback", lncs 2729, pp.176~194 (2003), springer- verlag
  6. "Algebraic Attacks on Stream Ciphers with Linear Feedback", 2656, pp.345~359 (2003), springer-verlag
  7. "About the XL Algorithm over GF Topics in Cryptology - CT-RSA 2003", 2612, pp.141~157 (2003), Springer-Verlag
  8. "Cryptanalysis of Block Ciphers with Overdefined System of Equations", lncs 2501, pp.267~287 (2002), springer-verlag
  9. "Fast Hashing and Stream Cipher with PANAMA", lncs 1372, pp.60~74 (1998), springer-verlag
  10. "TWOPRIME : A Fast Stream Ciphering Algorithm", 1372, pp.82~102 (1997), Springer-Verlag
  11. "BEEPBEEP : Embedded Real-Time Encryption", 2365, pp.164~178 (2002), Springer-Verlag
  12. "A New Version of the Stream Cipher SNOW", lncs 2595, pp.47~61 (2002), springer- verlag
  13. "Fast Encryption and Authentication in as Single Cryptographic Primitive", 2887, pp.330~346 (2003), Springer-Verlag
  14. "An Integrity- Aware Block Encryption Based on Cryptographic Pseudorandom Number Generator" (2000)
  15. "Scream : A Software-Efficinet Stream Cipher", 2365 (2002), Springer-Verlag
  16. "Primitive Specification and Supporting Documentation for SOBER-t32 Submission to NESSIE" (2000)
  17. "Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization", lncs 1666, pp.19~30 (1999), springer-verlag
  18. "NESSIE Project, New European Schemes for Signatures, Integrity and Encryption" (2000)
  19. ""RC4" Unpublished Work (A description of RC4 appears in B. Schneier," (1996), Applied Cryptography,
  20. "A Software-Optimized Encryption Algorithm", lncs 809(springer-verlag), pp.56~63 (1993)
  21. "A Software-Optimized Encryption Algorithm", 11(4), pp.274~287 (1998)
  22. "Turing : A Fast Stream Cipher", 2887, pp.290~306 (2003), Springer-Verlag
  23. "A New Keystream Generatior MUGI", 2365, pp.179~194 (2002), Springer-Verlag
  24. "A New Stream Cipher HC- 256", lncs 3017, pp.226~244 (2004), springer-verlag
  25. "The Software-Oriented Stream Cipher SSC2", 2000 lncs 1978, pp.31~48 (2004), springer-verlag
  26. "VMPC One-Way Function and Stream Cipher", 3017, pp.210~225 (2004), Springer-Verlag

관련 논문AI추천

블록암호에 대한 새로운 다중선형공격법성재철, 이상진, 홍득조, 홍석희한국정보보호학회 · 정보보호학회논문지2007 · 제17권 제6호Summation Generator에 대한 대수적 공격홍진, 김재헌, 문덕재, 이동훈, 한재우한국정보보호학회 · 정보보호학회논문지2004 · 제14권 제1호스트림 암호 MICKEY의 TMD-Tradeoff와 내부 상태 엔트로피의 손실에 관한 분석홍진, 김우환한국정보보호학회 · 정보보호학회논문지2007 · 제17권 제2호선형 다항식의 역원의 maximal 대수적 차수이동훈한국정보보호학회 · 정보보호학회논문지2005 · 제15권 제6호대수기하 부호를 이용한 공개키 암호김재헌, 박상우, 이정근한국정보보호학회 · 정보보호학회논문지2005 · 제15권 제6호전력 분석 공격에 안전한 효율적인 SEED 마스킹 기법김희석, 이옥연, 조영인, 최두호, 한동국, 홍석희한국정보처리학회 · 정보처리학회논문지C2010 · 제17권 제3호

이 간행물의 다른 논문 (4건)

접근제어 정책구현을 위한 역할기반 XML 암호화박석, 최동희pp. 3-15보안 프로토콜의 안전성 분석을 위한 정형적 방법론전철욱, 강인혜, 최진영, 김현석, 김일곤pp. 17-27축소 라운드 SHACAL-2의 차분-선형 유형 공격임종인, 김종성, 이상진, 홍석희, 김구일pp. 57-66가변 라운드 수를 갖는 블록 암호에 대한 차분 연관 암호 공격김종성, 이창훈, 성재철pp. 77-86
원문 보기