데이터 암호화 표준

3. 알고리즘 구조

3. 1. 파이스텔 구조

3. 2. Feistel (F) 함수

3. 3. 키 스케줄

4. 보안 및 암호 분석

데이터 암호화 표준(DES)의 암호 해독에 관해서는 다른 블록 암호보다 많은 정보가 공개되었지만, 현재 가장 실용적인 공격 방법은 무차별 대입 공격이다. 다양한 암호 분석적 특성이 알려져 있으며, 이론적으로 무차별 대입 공격보다 복잡성이 낮은 세 가지 공격 방법(차분 공격, 선형 공격, 데이비스 공격)이 가능하다. 그러나 이러한 공격은 실행하기 위해 비현실적인 수의 평문 또는 선택 평문이 필요하며, 실제로는 문제가 되지 않는다.^[38]

DES는 몇 가지 암호학적 특성을 가지고 있다.

• 보완 속성: 평문과 키를 모두 반전시키면 암호문도 반전된다. 즉, $E\_K(P)=C\; \backslash iff\; E\_\{\backslash overline\{K\}\}(\backslash overline\{P\})=\backslash overline\{C\}$이다. 여기서 $\backslash overline\{x\}$는 $x$의 비트 보수, $E\_K$는 키 $K$로 암호화, $P$는 평문, $C$는 암호문을 의미한다. 이 속성은 선택 평문 공격을 가정할 때 전수 공격에 필요한 노력을 절반으로 줄여준다.^[48]
• 약한 키: 암호화와 복호화 과정이 동일하게 작동하는 키이다. 즉, $E\_K(E\_K(P))\; =\; P$ 또는 $E\_K\; =\; D\_K$이다. DES에는 4개의 약한 키가 존재한다.
• 반-약한 키: 한 쌍의 키($K\_1$, $K\_2$) 중 하나로 암호화한 결과가 다른 키로 복호화한 결과와 같은 키이다. 즉, $E\_\{K\_1\}(E\_\{K\_2\}(P))\; =\; P$ 또는 $E\_\{K\_2\}\; =\; D\_\{K\_1\}$이다. DES에는 6쌍의 반-약한 키가 존재한다.

4. 1. 무차별 대입 공격

4. 2. 이론적 공격

• 차분 공격: 1980년대 후반 엘리 비함과 아디 샤미르가 재발견한 공격 방법으로, 2⁴⁷개의 선택 평문이 필요하다.^[39] DES는 이 공격에 대한 내성을 갖도록 설계되었다.
• 선형 공격: 미츠루 마츠이가 발견한 공격 방법으로, 2⁴³개의 기지 평문이 필요하다.^[40] 구현된 사례가 보고되었으며, DES에 대한 최초의 실험적 암호 분석으로 알려져 있다.
• 데이비스 공격: 도널드 데이비스가 처음 제안하고 비류코프가 개선한 공격 방법으로, 가장 강력한 형태는 2⁵⁰개의 기지 평문과 2⁵⁰의 계산 복잡도를 필요로 하며, 51%의 성공률을 보인다.^[44]

4. 3. 기타 암호 분석 특성

• 보완 속성: 평문과 키를 모두 반전시키면 암호문도 반전된다. 즉, $E\_K(P)=C\; \backslash iff\; E\_\{\backslash overline\{K\}\}(\backslash overline\{P\})=\backslash overline\{C\}$이다. 여기서 $\backslash overline\{x\}$는 $x$의 비트 보수, $E\_K$는 키 $K$로 암호화, $P$는 평문, $C$는 암호문을 의미한다. 이 속성은 선택 평문 공격을 가정할 때 전수 공격에 필요한 노력을 절반으로 줄여준다.^[48]
• 약한 키: 암호화와 복호화 과정이 동일하게 작동하는 키이다. 즉, $E\_K(E\_K(P))\; =\; P$ 또는 $E\_K\; =\; D\_K$이다. DES에는 4개의 약한 키가 존재한다.
• 반-약한 키: 한 쌍의 키($K\_1$, $K\_2$) 중 하나로 암호화한 결과가 다른 키로 복호화한 결과와 같은 키이다. 즉, $E\_\{K\_1\}(E\_\{K\_2\}(P))\; =\; P$ 또는 $E\_\{K\_2\}\; =\; D\_\{K\_1\}$이다. DES에는 6쌍의 반-약한 키가 존재한다.

5. 대체 알고리즘

1980년대 후반과 1990년대 초반, 소프트웨어에서 DES의 보안에 대한 우려와 상대적으로 느린 작동 속도 때문에 연구자들은 다양한 대체 블록 암호 설계를 제안했다. 이러한 설계에는 RC5, 블로우피쉬, IDEA, NewDES, SAFER, CAST5, FEAL 등이 포함되었다.^[75] 이들 대부분은 DES와 동일한 64비트 블록 크기를 유지하여 "드롭인" 교체가 가능하도록 설계되었지만, 일반적으로 64비트 또는 128비트 키를 사용했다. 소련에서는 64비트 블록 크기와 256비트 키를 사용하는 GOST 28147-89 알고리즘이 도입되었고, 이후 러시아에서도 사용되었다.

DES 자체를 더 안전하게 재사용하는 방법도 고안되었다. 많은 이전 DES 사용자들이 트리플 DES(TDES)를 사용했는데, 이는 DES의 특허권자 중 한 명이 설명하고 분석한 방식이다(FIPS Pub 46-3 참조). TDES는 두 개(2TDES) 또는 세 개(3TDES)의 서로 다른 키를 사용하여 DES를 세 번 적용하는 방식이다. TDES는 충분히 안전하지만 상당히 느리다는 단점이 있다. 계산 비용이 적게 드는 대안으로는 DES-X가 있는데, 이는 DES 전후에 추가 키 자료를 XOR하여 키 크기를 늘리는 방식이다. GDES는 암호화를 가속화하기 위해 제안된 DES 변형이었지만, 차분 공격에 취약한 것으로 밝혀졌다.

1997년 1월 2일, 미국 국립표준기술연구소(NIST)는 DES를 대체할 알고리즘을 선정하겠다고 발표했다.^[60] 2001년, 국제 경쟁을 거쳐 NIST는 새로운 암호인 고급 암호화 표준(AES)을 대체 암호로 선정했다.^[61] AES로 선정된 알고리즘은 설계자들이 Rijndael이라는 이름으로 제출한 것이었다. NIST AES 공모전의 다른 결선 진출자로는 RC6, 서펜트, MARS, 투피쉬가 있었다.

참조

_[1] 웹사이트 The Legacy of DES - Schneier on Security https://www.schneier[...] 2004-10-06
_[2] Conference A brief history of the data encryption standard ACM Press/Addison-Wesley Publishing Co. New York, NY, USA
_[3] 서적 Cash and Dash: How ATMs and Computers Changed Banking https://books.google[...] Oxford University Press 2018
_[4] 웹사이트 The Economic Impacts of NIST's Data Encryption Standard (DES) Program https://www.nist.gov[...] United States Department of Commerce 2001-10
_[5] 간행물 Automated teller machines: their history and authentication protocols https://slideheaven.[...] 2016-04-01
_[6] 간행물 Exhaustive Cryptanalysis of the NBS Data Encryption Standard http://origin-www.co[...] 1977-06
_[7] 웹사이트 Has DES been broken? http://www.emc.com/e[...] 2009-11-08
_[8] 서적 Applied Cryptography
_[9] 서적 Security for computer networks, 2nd ed. John Wiley & Sons
_[10] 간행물 On foiling computer crime 1979-07
_[11] 간행물 Data Encryption Gurus: Tuchman and Meyer 1978-10
_[12] 웹사이트 American Cryptology during the Cold War, 1945-1989.Book III: Retrenchment and Reform, 1972-1980, page 232 http://www.nsa.gov/p[...] National Security Agency 2009-12-18
_[13] 웹사이트 American Cryptology during the Cold War, 1945-1989.Book III: Retrenchment and Reform, 1972-1980, page 232 http://nsarchive.gwu[...] National Security Agency 2009-12-18
_[14] 웹사이트 American Cryptology during the Cold War, 1945-1989.Book III: Retrenchment and Reform, 1972-1980, page 232 http://nsarchive.gwu[...] National Security Agency 2009-12-18
_[15] 서적 Computer Security and Cryptography
_[16] 문서 Levy, Crypto, p. 55
_[17] 뉴스 Saluting the data encryption legacy http://www.cnet.com/[...] 2004-09-27
_[18] 웹사이트 NIST Special Publication 800-67 Recommendation for the Triple Data Encryption Algorithm (TDEA) Block Cipher, Version 1.1 http://csrc.nist.gov[...] National Institute of Standards and Technology
_[19] 문서 American National Standard, Data Encryption Algorithm American National Standards Institute
_[20] 웹사이트 ISO/IEC 18033-3:2010 Information technology—Security techniques—Encryption algorithms—Part 3: Block ciphers http://www.iso.org/i[...] Iso.org 2010-12-14
_[21] 문서 Bruce Schneier, Applied Cryptography, Protocols, Algorithms, and Source Code in C, Second edition, John Wiley and Sons, New York (1996) p. 267
_[22] 웹사이트 William E. Burr, "Data Encryption Standard", in NIST's anthology "A Century of Excellence in Measurements, Standards, and Technology: A Chronicle of Selected NBS/NIST Publications, 1901–2000. http://nvl.nist.gov/[...]
_[23] 웹사이트 FR Doc 04-16894 http://edocket.acces[...] Edocket.access.gpo.gov
_[24] 문서 S. Kumar, C. Paar, J. Pelzl, G. Pfeiffer, A. Rupp, M. Schimmler, "How to Break DES for Euro 8,980". 2nd Workshop on Special-purpose Hardware for Attacking Cryptographic Systems—SHARCS 2006, Cologne, Germany, April 3–4, 2006.
_[25] 웹사이트 8x1080Ti.md https://gist.github.[...]
_[26] 웹사이트 Crack.sh | the World's Fastest DES Cracker https://crack.sh
_[27] 웹사이트 FIPS 81 - Des Modes of Operation http://csrc.nist.gov[...] csrc.nist.gov
_[28] 웹사이트 FIPS 74 - Guidelines for Implementing and Using the NBS Data http://www.itl.nist.[...] Itl.nist.gov
_[29] 서적 Applied Cryptography
_[30] 문서 Stallings, W. Cryptography and network security: principles and practice. Prentice Hall, 2006. p. 73
_[31] 웹사이트 Bruting DES http://hamburgsteak.[...]
_[32] 문서 A Known-Plaintext Attack on Two-Key Triple Encryption Springer Berlin Heidelberg 1991
_[33] 웹사이트 Getting Started, COPACOBANA — Cost-optimized Parallel Code-Breaker http://www.copacoban[...] 2006-12-12
_[34] 서적 Cryptology Unlocked https://archive.org/[...] John Wiley & Sons 2007-10-16
_[35] 웹사이트 Break DES in less than a single day http://www.sciengine[...]
_[36] 웹사이트 The World's fastest DES cracker http://crack.sh
_[37] 문서 "Think Complex Passwords Will Save You?," David Hulton, Ian Foster, BSidesLV 2017
_[38] 논문 New Comparative Study Between DES, 3DES and AES within Nine Factors 2010
_[39] 서적 Differential cryptanalysis of the data encryption standard https://link.springe[...] Springer-Verlag 1993
_[40] 서적 Advances in Cryptology — EUROCRYPT '93 Springer, Berlin, Heidelberg 1993-05-23
_[41] 서적 Advances in Cryptology – CRYPTO 2004 Springer, Berlin, Heidelberg 2004-08-15
_[42] 서적 Fast Software Encryption Springer, Berlin, Heidelberg 2000-04-10
_[43] 서적 Selected Areas in Cryptography Springer, Berlin, Heidelberg 2001-08-16
_[44] 논문 Investigation of a potential weakness in the DES algorithm, Private communications https://scholar.goog[...] 1987
_[45] 논문 An improvement of Davies' attack on DES 1997-06-01
_[46] 서적 Advances in Cryptology — CRYPTO '94 Springer, Berlin, Heidelberg 1994-08-21
_[47] 서적 Advances in Cryptology — ASIACRYPT 2002 Springer, Berlin, Heidelberg 2002-12-01
_[48] 서적 Handbook of Applied Cryptography https://archive.org/[...] CRC Press 1996
_[49] 서적 Campbell and Wiener, 1992 http://dl.acm.org/ci[...] 1992-08-16
_[50] 웹사이트 Double DES https://www.nku.edu/[...]
_[51] 간행물 Image Encryption using Simplified Data Encryption Standard (S-DES) http://research.ijca[...] 2014
_[52] 서적 Introduction to Cryptography with Open-Source Software https://books.google[...] 2012
_[53] 간행물 Appendix G: Simplified DES http://mercury.webst[...] 2010
_[54] 간행물 Cryptanalysis of Simplified Data Encryption Standard via Optimisation Heuristics http://citeseerx.ist[...] 2006
_[55] 간행물 Simplified DES http://doc.sagemath.[...] 2009
_[56] 서적 Cryptography and Network Security https://books.google[...]
_[57] 간행물 A Simplified Data Encryption Standard Algorithm 1996
_[58] 간행물 Breaking of Simplified Data Encryption Standard Using Binary Particle Swarm Optimization http://ijcsi.org/pap[...] 2012
_[59] 웹사이트 Cryptography Research: Devising a Better Way to Teach and Learn the Advanced Encryption Standard https://web.archive.[...]
_[60] 웹사이트 Announcing Development of FIPS for Advanced Encryption Standard | CSRC http://csrc.nist.gov[...] 2017-01-10
_[61] 문서 November 26, 2001 http://csrc.nist.gov[...]
_[62] 학회자료 A brief history of the data encryption standard ACM Press/Addison-Wesley Publishing Co. New York, NY, USA
_[63] 웹사이트 Has DES been broken? http://www.rsa.com/r[...] 2009-05-27
_[64] 서적 Applied Cryptography
_[65] 서적 Security for computer networks, 2nd ed. John Wiley & Sons
_[66] 논문 On foiling computer crime IEEE 1979-07
_[67] 논문 Data Encryption Gurus:Tuchman and Meyer 1978-10
_[68] 논문 American Cryptology during the Cold War, 1945-1989.Book III:Retrenchment and Reform, 1972-1980
_[69] 서적 Computer Security and Cryptography
_[70] 문서 Crypto
_[71] 웹사이트 NIST Special Publication 800-67 ''Recommendation for the Triple Data Encryption Algorithm (TDEA) Block Cipher'', Version 1.1 http://nvlpubs.nist.[...] National Institute of Standards and Technology 2016-10-09
_[72] 간행물 American National Standard, Data Encryption Algorithm American National Standards Institute 1981
_[73] 웹사이트 ISO/IEC 18033-3:2005 Information technology — Security techniques — Encryption algorithms — Part 3:Block ciphers http://www.iso.org/i[...] Iso.org 2008-10-15
_[74] 서적 Applied Cryptography, Protocols, Algorithms, and Source Code in C, Second edition John Wiley and Sons 1996
_[75] 간행물 Data Encryption Standard http://nvl.nist.gov/[...] NIST 1901–2000
_[76] 웹사이트 FR Doc 04-16894 http://edocket.acces[...] Edocket.access.gpo.gov 2009-06-02
_[77] 웹사이트 Federal Register vol 70, number 96 https://www.gpo.gov/[...] Office of the Federal Register, National Archives and Records Administration 2005-05-19
_[78] 간행물 How to Break DES for Euro 8,980 2nd Workshop on Special-purpose Hardware for Attacking Cryptographic Systems — SHARCS 2006-04-03
_[79] 웹사이트 FIPS 81 - Des Modes of Operation http://csrc.nist.gov[...] Itl.nist.gov 2016-10-09
_[80] 웹사이트 FIPS 74 - Guidelines for Implementing and Using the NBS Data http://www.itl.nist.[...] Itl.nist.gov 2016-10-09
_[81] 서적 Cryptography and network security:principles and practice Prentice Hall 2006
_[82] 웹사이트 US GOVERNMENT'S ENCRYPTION STANDARD BROKEN IN LESS THAN A DAY https://www.distribu[...] distributed.net 1999-01-19
_[83] 논문 Exhaustive Cryptanalysis of the NBS Data Encryption Standard http://origin-www.co[...] 1977-06
_[84] 웹인용 RSA Code-Breaking Contest Again Won by Distributed.Net and Electronic Frontier Foundation (EFF) http://w2.eff.org/Pr[...] 2009-07-12