[논문]병렬 컴퓨팅을 이용한 DES 키 탐색 안정성 분석

윤준원; 최장원; 박찬열; 공기식

doi:10.9728/dcs.2013.14.1.65

병렬 컴퓨팅을 이용한 DES 키 탐색 안정성 분석
Evaluation of DES key search stability using Parallel Computing 원문보기

디지털콘텐츠학회 논문지 = Journal of Digital Contents Society, v.14 no.1, 2013년, pp.65 - 72

윤준원 (KISTI 국가슈퍼컴퓨팅연구소) , 최장원 (KISTI 국가슈퍼컴퓨팅연구소) , 박찬열 (KISTI 국가슈퍼컴퓨팅연구소) , 공기식 (남서울대학교 멀티미디어학과)

초록
AI-Helper

기상, 바이오, 천문학, 암호학 등 다양한 분야의 대규모 작업을 처리하기 위하여 다수의 계산 자원을 동시에 사용하기 위한 병렬 컴퓨팅 기법들이 제안되어져 왔다. 병렬 컴퓨팅은 여러 프로세서에게 작업을 분담시켜 동시에 계산을 수행하게 함으로써 프로그램의 실행시간을 단축시킬 수 있을 뿐만 아니라 해결할 수 있는 문제의 규모를 확장 시킬 수 있다. 본 논문에서는 실제 암호 알고리즘 분석하기 위하여 병렬 처리 방식을 적용하여 그 효율성을 분석하였다. 암호 알고리즘의 실질적인 안전성 요소인 키의 길이는 전수조사 계산량에 의존한다. 이에 병렬 처리 환경에서 DES 키 탐색 암호 알고리즘의 키 전수조사 작업을 수행하기 위한 세부적인 절차에 대해서 논하였고, 클러스터링 장비에 적용하여 시뮬레이션 수행하였다. 그 결과 컴퓨터의 양에 따라서 계산량의 추이를 실증적으로 예측함으로써 암호 알고리즘의 안전성 강도를 측정할 수 있다.

Abstract ▼ AI-Helper

Current and future parallel computing model has been suggested for running and solving large-scale application problems such as climate, bio, cryptology, and astronomy, etc. Parallel computing is a form of computation in which many calculations are carried out simultaneously. And we are able to shorten the execution time of the program, as well as can extend the scale of the problem that can be solved. In this paper, we perform the actual cryptographic algorithms through parallel processing and evaluate its efficiency. Length of the key, which is stable criterion of cryptographic algorithm, judged according to the amount of complete enumeration computation. So we present a detailed procedure of DES key search cryptographic algorithms for executing of enumeration computation in parallel processing environment. And then, we did the simulation through applying to clustering system. As a result, we can measure the safety and solidity of cryptographic algorithm.

주제어

AI 본문요약
AI-Helper

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

문제 정의

본 논문에서는 분산 네트워크 환경에서 블록 암호 알고리즘의 키 전수조사 계산량 관점의 안전성 분석을 수행하였다. 그 과정은 다음과 같다.

제안 방법

▪DES에 대한 분석 DES에서 전수조사를 할 때 알고리즘을 노드수 변화를 위한 부분만 수정하여 전체 키 중에서 28bit를 모를 때를 기준으로 실험하였다. 기존에 64개의 노드를 사용하였기 때문에 64, 32, 16, 8, 4, 2개의 순으로 노드의 개수를 줄여 가며 전수조사 공격을 해보았다.
클러스터링 장비에서 노드 수는 곧 컴퓨터의 양이라 할 수 있다. 계산을 하는 컴퓨터의 양이 변화할 때 전수조사의 공격량은 어떻게 변하는지 실험한 후, 컴퓨터 양과 전수조사의 공격량은 어떠한 관계가 있는지 측정하였다.
이 평문을 다음의 64bit 키 “0x0468046804680468”로 암호화 하였고(이 키는 parity bit를 제거하여 56bit로 알고리즘에 입력된다), CBC mode를 사용하기 위해 64bit의 Initial vector “0x0123456789abcdef”를 사용하였다. 그 결과 다음의 5개의 암호문 블록을 얻었으며(L/R : 좌우 각 32bit), 이 5개의 암호문 블록을 사용해서 DES의 키 전수 조사를 실시하였다.
▪DES에 대한 분석 DES에서 전수조사를 할 때 알고리즘을 노드수 변화를 위한 부분만 수정하여 전체 키 중에서 28bit를 모를 때를 기준으로 실험하였다. 기존에 64개의 노드를 사용하였기 때문에 64, 32, 16, 8, 4, 2개의 순으로 노드의 개수를 줄여 가며 전수조사 공격을 해보았다. 그 결과는 다음과 같다.
L)를 0x04860486으로 고정시킴으로서 결과적으로 28bit의 길이를 갖는 키에 대한 전수조사가 이루어지게 하였다. 두번째 선택으로 K.R을 랜덤으로 생성하고, 고정되었던 K.L중 하위 3bit만 랜덤하게 생성한 뒤 최하위bit가 parity bit이기 때문에 랜덤하게 생성된 3bit를 1bit left shift시 켜서 나머지 고정된 28bit에 결합시킴으로서 31bit 키 길이에 대한 전수조사가 이루어졌다. 세 번째 선택인 35bit에서는 앞의 과정과 비슷하게 상위 21bit를 고정시키고 랜덤하게 생성된 7bit (1bit left shift된)를 결합하였다.
본 논문에서는 블록암호 DES 키 탐색 알고리즘을 분석을 위해 클러스터링 시스템을 이용하여 시뮬레이션을 수행하였다.
사용한 DES C-code의 출처는 ETRI Library이고, NIST Special Publication 800-17 "Modes of Operation Validation System"의 125p에 있는 test vector를 통해 DES 알고리즘을 검증하였다.
이 평문을 다음의 64bit 키 “0x0468046804680468”로 암호화 하였고(이 키는 parity bit를 제거하여 56bit로 알고리즘에 입력된다), CBC mode를 사용하기 위해 64bit의 Initial vector “0x0123456789abcdef”를 사용하였다.
▪키 생성방법: 키의 구성은 C code의 구조체를 사용하여 좌우 32bit씩 나누었다. 키 생성방법은 첫 번째 선택으로 총 56bit중 우측 28bit(이하 K.R)를 랜덤으로 생성하고, 좌측 28bit(이하 K.L)를 0x04860486으로 고정시킴으로서 결과적으로 28bit의 길이를 갖는 키에 대한 전수조사가 이루어지게 하였다. 두번째 선택으로 K.

성능/효과

키 전수 조사 실험 결과 클러스터 장비 환경에서 실험 가능한 최대 키 길이는 DES의 경우 37비트 키를 찾기 위한 평균 시간이 약 1시간 24분이라는 기록이 관측되었다. 또한, 실험 결과에서 키의 길이가 1-bit 증가되면 키를 찾는 데 약 두 배의 시간이 걸리고, 키를 찾는 데 사용되는 노드의 개수를 두 배로 증가시키면 키를 찾는 데 걸리는 시간을 반으로 단축할 수 있음을 알 수 있었다.
지금까지 연구에서는 블록 암호 알고리즘으로 가장 널리 사용되는 미국 표준 알고리즘 DES에 대해서 클러스터 장비를 이용한 키 전수 조사 관점의 안전성 분석을 실시하였다. 키 전수 조사 실험 결과 클러스터 장비 환경에서 실험 가능한 최대 키 길이는 DES의 경우 37비트 키를 찾기 위한 평균 시간이 약 1시간 24분이라는 기록이 관측되었다. 또한, 실험 결과에서 키의 길이가 1-bit 증가되면 키를 찾는 데 약 두 배의 시간이 걸리고, 키를 찾는 데 사용되는 노드의 개수를 두 배로 증가시키면 키를 찾는 데 걸리는 시간을 반으로 단축할 수 있음을 알 수 있었다.

후속연구

가장 효율 적인 키 전수조사 방법이 사용될 경우의 계산량을 측정함으로써 암호 알고리즘에 대한 안전성 강도를 실질적으로 예측할 수 있는 것이다. 더 나아가 고성능인 컴퓨터를 병렬로 활용할 수 있는 대수와 계산량의 추이를 연구하는 것을 통해 분산 환경의 유휴 컴퓨터 자원을 이용한 공격량을 예측할 수 있을 것이다.
분산환경의 컴퓨터 자원을 이용한 공격량을 예측하기 위해서도 현 단계에서 고성능인 컴퓨터를 병렬로 활용할 수 있는 대수와 계산량의 추이를 연구하는 것이 무엇보다 중요하다. 향후 컴퓨터 계산 능력과 연계 활용 기술은 지속적으로 발전할 것이기 때문에 이러한 관점에서 암호 알고리즘의 안전성을 평가할 수 있는 기술은 정보보호 시스템 설계 시 필수적인 분야가 될 전망이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	병렬 컴퓨팅은 무엇인가?	병렬 컴퓨팅이란 대규모의 문제를 해결하기 위해 분산된 다수의 계산 자원을 동시에 사용하는 것을 말하며, 이를 위해 여러 개의 프로세서를 가지는 단일 컴퓨터, 네트워크로 연결된 다수의 컴퓨터(Workstation Cluster) 또는 이 둘의 결함된 형태로 구성된다. 문제를 병렬로 처리하는 주된 목적은 무엇보다 프로그램의 실제 실행 시간(wall-clock time)을 줄이고자 하는 것이다.
	문제를 병렬로 처리하는 주된 목적은 무엇인가?	병렬 컴퓨팅이란 대규모의 문제를 해결하기 위해 분산된 다수의 계산 자원을 동시에 사용하는 것을 말하며, 이를 위해 여러 개의 프로세서를 가지는 단일 컴퓨터, 네트워크로 연결된 다수의 컴퓨터(Workstation Cluster) 또는 이 둘의 결함된 형태로 구성된다. 문제를 병렬로 처리하는 주된 목적은 무엇보다 프로그램의 실제 실행 시간(wall-clock time)을 줄이고자 하는 것이다. 사용자는 여러 프로세서에게 작업을 분산시켜 동시에 계산을 수행하게 함으로써 프로그램의 실행시간을 단축시킬 수 있으며 또한 해결할 수 있는 문제의 규모를 키울 수 있다[1].
	보다 강력하고 보다 빠른 프로세서를 기반으로 하는 고성능 단일 프로세서 시스템의 개발이 어느정도 한계에 이른 이유는 무엇인가?	고성능 프로세서의 지속적인 개발은 전송속도와 소형화에 대한 물리적인 한계와 비용 상승에 대한 경제적 제한 때문에 어려움이 있다. 따라서 보다 강력하고 보다 빠른 프로세서를 기반으로 하는 고성능 단일 프로세서 시스템의 개발이 어느 정도 한계에 이르렀다.

참고문헌 (9)

Meng, Jiayuan, Raghunathan, Anand, Chakradhar, Srirnat T, Byna, Surendra , "Exploiting the forgiving nature of applications for scalable parallel execution", Parallel & Distributed Processing(IPDPS), pp.1-12, April 2010.
N. Sadashiv, Kumar, S.M.D, "Cluster, grid and cloud computing:A detailed comparison", Computer Science & Education (ICCSE), pp.477-482, July 2011.
Gavril Godza, Valentin Cristea, "Comparative Study of COW and SMP Computer Configurations", Parallel Computing in Electrical Engineering(PARELEC), pp. 205-210, September, 2002.
Xiao Qian, Wang Chengguo, Guo Ge, "The Research of Parallel Computing for Large-Scale Finite Element Model of Wheel/Rail Rolling Contact", Computer Science and Information Technology(ICCSIT), pp. 254-257, July, 2010.
Taejung Park, "CUDA-based Object Oriented Programming Techniques for Efficient Parallel Visualization of 3D Content", Journal of Digital Contents Society Vol.13 No. 2 pp. 169-176, June, 2012.

원문보기 상세보기
Fox, Geoffrey C, "Lessons for massively parallel applications on message passing computers", Thirty-Seventh IEEE Computer Society International Conference, CMPCON, pp.103-114, 1992.
Mamidala, Amith R, "Optimizing MPI Collectives UsingEfficient Intra-node Communication Techniques over the Blue Gene/P Supercomputer", Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), pp.771-780, May, 2011.
NIST, FIPS PUB 46-2 : Announcing the Data Encryption Standard (DES)
NIST, FIPS PUB 197:Announcing the Advanced Encryption Standard (AES)

저자의 다른 논문 :

LOADING...

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증