$\require{mediawiki-texvc}$

연합인증

연합인증 가입 기관의 연구자들은 소속기관의 인증정보(ID와 암호)를 이용해 다른 대학, 연구기관, 서비스 공급자의 다양한 온라인 자원과 연구 데이터를 이용할 수 있습니다.

이는 여행자가 자국에서 발행 받은 여권으로 세계 각국을 자유롭게 여행할 수 있는 것과 같습니다.

연합인증으로 이용이 가능한 서비스는 NTIS, DataON, Edison, Kafe, Webinar 등이 있습니다.

한번의 인증절차만으로 연합인증 가입 서비스에 추가 로그인 없이 이용이 가능합니다.

다만, 연합인증을 위해서는 최초 1회만 인증 절차가 필요합니다. (회원이 아닐 경우 회원 가입이 필요합니다.)

연합인증 절차는 다음과 같습니다.

최초이용시에는
ScienceON에 로그인 → 연합인증 서비스 접속 → 로그인 (본인 확인 또는 회원가입) → 서비스 이용

그 이후에는
ScienceON 로그인 → 연합인증 서비스 접속 → 서비스 이용

연합인증을 활용하시면 KISTI가 제공하는 다양한 서비스를 편리하게 이용하실 수 있습니다.

GPGPU 기술을 활용한 차분 확률의 통계적 분석
The Statistical Analysis of Differential Probability Using GPGPU Technology 원문보기

情報保護學會論文誌 = Journal of the Korea Institute of Information Security and Cryptology, v.29 no.3, 2019년, pp.477 - 489  

조은지 (고려대학교) ,  김성겸 (고려대학교) ,  홍득조 (전북대학교) ,  성재철 (서울시립대학교) ,  홍석희 (고려대학교)

초록
AI-Helper 아이콘AI-Helper

본 논문에서는 마르코프 암호 가정 하에 구한 기대 차분 확률과 차분 확률의 분포를 실험적으로 검증한다. 첫 번째로, 마르코프 암호 가정 하에 구한 기대 차분 확률과 실험을 통해 구한 확률이 일치하는지를 경량 블록암호 PRESENT의 6라운드에 적용하여 타당함을 보인다. 두 번째로, 마르코프 암호 가정 하에 구한 기대 차분 확률에 통계적으로 근사하지만, 차분 확률의 알려진 분포를 따르지 않는 경우가 있음을 경량 블록암호 GIFT의 4라운드에 적용하여 실험적으로 보인다. 마지막으로 키 스케줄이 표본 추출 모델을 통한 고정키의 차분 확률의 분포에 영향을 미치는지를 분석하기 위해 GIFT의 라운드 키의 XOR 위치와 개수를 바꾸어 얻은 차분 확률들을 제시한다. 이 결과를 통해 표본 추출 가정에 키 스케줄만의 유일한 영향이 아님을 알 수 있다. 통계적 분석을 위한 데이터 수집은 GPGPU 기술을 활용하여 CPU만을 이용한 프로그램에 비해 약 157배 빠르게 수행할 수 있었다.

Abstract AI-Helper 아이콘AI-Helper

In this paper, we experimentally verify the expected differential probability under the markov cipher assumption and the distribution of the differential probability. Firstly, we validate the expected differential probability of 6round-PRESENT of the lightweight block cipher under the markov cipher ...

주제어

표/그림 (15)

AI 본문요약
AI-Helper 아이콘 AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

  • 본 논문에서는 마르코프 암호 가정 하에 구한 기대 차분 확률 EMarkov가 실제 차분 확률과 같은지 확인하기 위해 다음의 통계적 가설을 설정하였다.
  • 본 논문에서는 마르코프 암호 가정 하에 구한 기대 차분 확률과 차분 확률의 분포를 실험적으로 검증 한다. 본 논문의 의의는 첫 번째, 마르코프 암호 가정 하의 이론적 기대 차분 확률과 실험적 확률의 통계적 비교를 경량 블록암호 PRESENT의 6라운드에 적용하여 근사함을 보인다.
  • 본 절에서는 차분 확률의 분포가 평균과 분산이 Np×EMarkov인 푸아송분포를 따르는지를 확인하기 위해 GIFT에 적용하여 모집단의 모분산과 모평균을 검정한다.
  • 고정키에서의 차분 확률의 분포는 푸아송분포에 근사한다고 알려져 있다[6]. 하지만 이를 실험적으로 검증하지 않았으므로, 본 논문은 GPU를 기반으로 얻은 데이터를 이용하여 동일하게 적용되지 않는 예시를 제시한다. 세 번째, [6]의 표본 추출 가정에 키 스케줄이 영향을 미치는 지를 분석하기 위해 GIFT의 라운드 키의 XOR 위치와 개수를 바꾸어 얻은 실험 결과를 통해 키 스케줄을 변경하여도 표본 추출 가정을 만족하지 않음을 보인다.

가설 설정

  • 따라서 가정 1은 마르코프 암호 이론에서 사용된 가정에 비해 더 약한 가정이다. [6]은 블록암호에서의 키 k0에 따라 정해지는 Np개의 쌍이 실제 표본 추출된 것과 동일한 지의 타당성은 보이지 않았으므로 본 논문에서 가정 1의 타당성을 실험적으로 검증한다.
  • 모수에 관한 주장을 가설이라 하고, 가설에는 귀무가설과 대립가설이 있다. 귀무가설 H0은 검정 대상이 되는 가설로 증거가 없는 가설이고, 유의수준에 따라 기각하는 것이 목표이다. 대립가설 H1은 귀무가설에 상반되는 가설로 강력한 증거에 의하여 입증하고자 하는 가설이다.
  • 귀무가설 H0은 검정 대상이 되는 가설로 증거가 없는 가설이고, 유의수준에 따라 기각하는 것이 목표이다. 대립가설 H1은 귀무가설에 상반되는 가설로 강력한 증거에 의하여 입증하고자 하는 가설이다.
  • 마르코프 암호는 각 라운드 키들이 균일하게 독립임을 만족해야 하지만, 가정 1은 사용하는 키스케줄의 라운드 키의 독립성을 요구하지 않는다. 따라서 가정 1은 마르코프 암호 이론에서 사용된 가정에 비해 더 약한 가정이다. [6]은 블록암호에서의 키 k0에 따라 정해지는 Np개의 쌍이 실제 표본 추출된 것과 동일한 지의 타당성은 보이지 않았으므로 본 논문에서 가정 1의 타당성을 실험적으로 검증한다.
  • 하지만 마르코프 암호 이론에 따른 블록암호의 차분 공격에 대한 저항성 평가 [3,4,5]에서는 고정된 키에 따라 달라질 수 있는 차분 확률을 고려하기 어렵다. 따라서 확률 동등성 가정(the hypothesis of stochastic equivalence) 에 따라 고정된 비밀키에 대한 차분 경로의 확률은 모든 비밀키의 평균값의 확률에 근사하다고 가정한 다. 이와 관련된 고정키에 대한 확률을 고려한 차분 확률에 관한 연구로 [6,7] 등이 있다.
  • 그러나 가정 1은 모든 라운드 키가 균일하게 독립적이지 않게 하는 키 스케줄을 사용하는 블록암호에도 적용할 수 있다. 마르코프 암호는 각 라운드 키들이 균일하게 독립임을 만족해야 하지만, 가정 1은 사용하는 키스케줄의 라운드 키의 독립성을 요구하지 않는다. 따라서 가정 1은 마르코프 암호 이론에서 사용된 가정에 비해 더 약한 가정이다.
본문요약 정보가 도움이 되었나요?

질의응답

핵심어 질문 논문에서 추출한 답변
푸아송분포를 따르지 않는 원인이 키 스케줄의 영향인지 어떻게 확인 하였는가? 제시한 그래프의 형태는 특정키에서의 차분 확률이 마르코프 암호 가정 하의 기대 차분 확률과 큰 차이가 날 수 있음을 뜻한다. 또한, 푸아송분포를 따르지 않는 원인이 키 스케줄의 영향인지를 확인하기 위하여 GIFT의 라운드 키의 XOR 연산 위치를 바꾸어 가며 차분 확률을 구하였다. 그리고 이 결과를 통해서 키 스케줄만의 영향이 아님을 확인하였다.
GIFT의 4라운드에서 결과를 만족하지 않는 경우는 무엇인가? 차분 확률의 분포가 푸아송분포를 따른다는 [6]의 정리1은 GIFT의 4라운드에 적용하여 만족하지 않는 경우가 있음을 실험을 통하여 보였다. 이 결과는 마르코프 암호 가정 하의 기대 차분 확률을 만족하지만, 차분 확률의 분포가 푸아송분포를 따르지 않는 경우를 보여준다. 제시한 그래프의 형태는 특정키에서의 차분 확률이 마르코프 암호 가정 하의 기대 차분 확률과 큰 차이가 날 수 있음을 뜻한다.
차분 분석(Differential Cryptanalysis)이란 무엇인가? 차분 분석(Differential Cryptanalysis)은 Eli Biham과 Adi Shamir에 의해 제안되어 현재까지 블록암호의 안전성 분석에 사용되는 대표적인 분석법이다[1]. 이 방법은 특정 차분을 만족하는 평문 쌍이 해당 암호문 쌍에 미치는 영향을 분석하여 비밀 정보를 알아내거나 구별 공격을 하는 데 이용된다.
질의응답 정보가 도움이 되었나요?

참고문헌 (14)

  1. Eli Biham and Adi Shamir. "Differential cryptanalysis of DES-like cryptosystems." CRYPTO'90, Lecture Notes in Computer Science, vol. 537, pp. 2-21. August, 1991. 

  2. Biryukov Alex, Patrick Derbez and Leo Perrin. "Differential analysis and meet-in-the-middle attack against round-reduced TWINE." International Workshop on Fast Software Encryption. Springer, Berlin, Heidelberg, pp. 3-27, Mar. 2015. 

  3. Lai Xuejia, James L. Massey, and Sean Murphy. "Markov ciphers and differential cryptanalysis." Workshop on the Theory and Application of Cryptographic Techniques. Springer, Berlin, Heidelberg, pp. 17-38, Apr. 1991. 

  4. O'Connor Luke and Jovan Dj Golic. "A unified markov approach to differential and linear cryptanalysis." International Conference on the Theory and Application of Cryptology. Springer, Berlin, Heidelberg, pp. 385-397, Nov. 1994. 

  5. Vaudenay Serge. "On the security of CS-cipher." International Workshop on Fast Software Encryption. Springer, Berlin, Heidelberg, pp. 260-274, Mar. 1999. 

  6. Daemen Joan and Vincent Rijmen. "Probability distributions of correlation and differentials in block ciphers." Journal of Mathematical Cryptology JMC 1.3 pp. 221-242. 2007 

  7. Sun Ling, Wei Wang, and Meiqin Wang. "More Accurate Differential Properties of LED64 and Midori64." IACR. Transactions on Symmetric Cryptology, pp. 93-123, 2018. 

  8. Luebke David, et al. "GPGPU: general-purpose computation on graphics hardware." Proceedings of the 2006 ACM/IEEE conference on Supercomputing. ACM, pp. 208, Nov. 2006. 

  9. Stevens, Marc, et al. "The first collision for full SHA-1." Annual International Cryptology Conference. Springer, Cham, pp. 570-596, Aug. 2017. 

  10. NVIDIA. NVIDIA CUDA Compute Unified Device Architecture: Programming Guide (Version 7.0), http://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html,2014. 

  11. Knudsen Lars R. and John E. Mathiassen. "On the role of key schedules in attacks on iterated ciphers." European Symposium on Research in Computer Security. Springer, Heidelberg, pp. 322-334, Sep. 2004. 

  12. DEGROOT, Morris H.; SCHERVISH, Mark J. Probability and statistics. Pearson Education, 2012. 

  13. Bogdanov Andrey, et al. "PRESENT: An ultra-lightweight block cipher." International Workshop on Cryptographic Hardware and Embedded Systems. Springer, Berlin, Heidelberg, pp. 450-466, Sep. 2007. 

  14. Banik, Subhadeep, et al. "GIFT: a small PRESENT." International Conference on Cryptographic Hardware and Embedded Systems. Springer, Cham, pp. 321-345, Sep. 2017. 

저자의 다른 논문 :

LOADING...

관련 콘텐츠

오픈액세스(OA) 유형

FREE

Free Access. 출판사/학술단체 등이 허락한 무료 공개 사이트를 통해 자유로운 이용이 가능한 논문

이 논문과 함께 이용한 콘텐츠

저작권 관리 안내
섹션별 컨텐츠 바로가기

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

AI-Helper 아이콘
AI-Helper
안녕하세요, AI-Helper입니다. 좌측 "선택된 텍스트"에서 텍스트를 선택하여 요약, 번역, 용어설명을 실행하세요.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.

선택된 텍스트

맨위로