데이터 암호화 표준

데이터 암호화 표준

DES의 Feistel 함수(F 함수)
일반
디자이너	IBM
초판	1975년(연방등록부)(1977년 1월 표준화)
유래	루시퍼
후계자	트리플 DES, G-DES, DES-X, LOKI89, ICE
암호 상세
키 사이즈	56비트
블록 크기	64비트
구조.	밸런스 페이스텔 네트워크
라운드	16
최고의 퍼블릭 암호 분석
DES는 브루트 포스 [1]공격의 가능성이 있기 때문에 처음부터 안전하지 않은 것으로 간주되어 왔습니다.이러한 공격은 실제로 실증되어 있으며(EFF DES 크래커 참조), 현재는 서비스로서 시판되고 있습니다.2008년 현재 최고의 분석 공격은 2개의 알려진 평문을 필요로43 하며 시간 복잡도는 2입니다39–43(Junod, 2001).

Data Encryption Standard(DES / 'di'i's, d'z/)는 디지털 데이터 암호화를 위한 대칭 키 알고리즘입니다.키 길이가 56비트로 짧기 때문에 현대 응용 프로그램에는 안전하지 않지만 암호 기술의 발달에 큰 영향을 미치고 있습니다.

1970년대 초 IBM에서 개발되었으며 Horst Feistel의 이전 설계를 기반으로 한 이 알고리즘은 민감하고 기밀이 아닌 전자 정부 데이터를 보호하기 위한 후보를 제안하라는 기관의 요청에 따라 NBS(National Bureau of Standards)에 제출되었습니다.1976년 NBS는 국가안전보장국(NSA)과 협의한 후 약간 수정된 버전(차동 암호해석에 대해서는 강화되지만 무차별 공격에는 약함)을 선정하여 1977년 ^[2]미국 공식 FIPS(Federal Information Processing Standard)로 공표하였다.

NSA가 승인한 암호화 표준이 발표됨에 따라 NSA는 신속하게 국제적으로 채택되고 광범위한 학술 조사를 받게 되었습니다.기밀 설계 요소, 대칭 키 블록 암호 설계의 비교적 짧은 키 길이, 그리고 NSA의 개입으로 인해 논란이 일었고, 백도어에 대한 의혹이 제기되었다.이러한 의혹을 불러일으킨 S박스는 NSA가 비밀리에 알고 있던 백도어(차동 암호 분석)를 제거하기 위해 설계한 것입니다.그러나 NSA는 또한 무차별적인 공격에 ^[2]의해 암호를 해독할 수 있도록 키 크기를 대폭 줄였다.시간이 지남에 따라 알고리즘이 받은 엄격한 학술적 정밀조사는 블록 암호와 그 암호해석에 대한 현대적 이해로 이어졌다.

DES는 56비트키 사이즈가 비교적 짧기 때문에 안전하지 않습니다.1999년 1월, distributed.net와 Electronic Frontier Foundation은 공동으로 DES 키를 22시간 15분 만에 공개적으로 파손했습니다(연혁 참조).실제 실행은 불가능하지만 암호의 이론적 약점을 보여주는 분석 결과도 있습니다.이 알고리즘은 이론적인 공격이 있지만 트리플 DES의 형태로 실질적으로 안전하다고 생각됩니다.이 암호는 Advanced Encryption Standard(AES)로 대체되었습니다.DES는 미국 ^[3]국립표준기술원에 의해 표준으로 폐지되었습니다.

일부 문서에서는 DES 표준과 알고리즘을 구별하고 알고리즘을 DEA(Data Encryption Algorithm)라고 부릅니다.

역사

DES의 기원은 1972년으로 거슬러 올라가며, 미국 정부의 컴퓨터 보안에 관한 National Bureau of Standards(National Bureau of Standards) 조사에서 기밀 정보가 아닌 기밀 ^[4]정보를 암호화하기 위한 정부 차원의 표준이 필요하다는 것이 확인되었습니다.

비슷한 시기에 엔지니어 모하메드 아탈라는 1972년 아탈라 코퍼레이션을 설립하고 1973년 상용화된 최초의 하드웨어 보안 모듈(HSM)을 개발했다.안전한 PIN 생성 키로 오프라인 장치를 보호하여 상업적 성공을 거두었습니다.은행과 카드사들은 아탈라가 시장을 장악할 것을 우려했고, 이는 국제 암호화 ^[3]표준의 개발을 촉진시켰다.Atalla는 은행 시장에서 IBM의 초기 경쟁자였으며, DES ^[5]표준을 다루는 IBM 직원들에 의해 영향을 받은 것으로 언급되었습니다.IBM 3624는 나중에 이전의 Atalla ^[6]시스템과 유사한 PIN 검증 시스템을 채택했습니다.

1973년 5월 15일 NBS는 NSA와 협의한 후 엄격한 설계 기준을 충족하는 암호에 대한 제안을 요청했다.어느 제출물도 적절하지 않았다.두 번째 요청은 1974년 8월 27일에 발행되었다.이번에 IBM은 1973-1974년 동안 초기 알고리즘인 Horst Feistel의 Lucper 암호에 기반하여 개발된 암호로 적합하다고 판단되는 후보를 제출했습니다.암호 설계 및 분석에 참여한 IBM의 팀은 Feistel, Walter Tuchman, Don Coppersmith, Alan Konheim, Carl Meyer, Mike Matyas, Roy Adler, Edna Grossman, Bill Notz, Lyn Smith 및 Bryant Tuckerman이었습니다.

설계에 대한 NSA의 관여

1975년 3월 17일, 제안된 DES는 연방 관보에 발표되었다.공개적인 코멘트가 요청되었고, 다음 해에 제안된 표준을 논의하기 위해 두 개의 공개 워크숍이 열렸다.공개키 암호학의 선구자인 마틴 헬먼과 휘트필드 ^[1]디피로부터 NSA의 부적절한 간섭의 증거로 키 길이가 짧아지고 신비로운 "S박스"를 들며 비판이 있었다.이 알고리즘이 정보기관에 의해 은밀하게 약화되어 다른 누구도 암호화된 ^[7]메시지를 쉽게 읽을 수 없게 된 것이 아닌가 하는 의심이 들었다.앨런 콘하임(DES 디자이너 중 한 명)은 "우리는 S박스를 워싱턴으로 보냈습니다.그들은 돌아왔고 모두 ^[8]달랐다.미 상원 정보 특별 위원회는 NSA의 조치를 검토하여 부적절한 개입이 있었는지 여부를 판단했습니다.1978년에 발표된 조사결과에 대한 미분류 요약에서 위원회는 다음과 같이 썼다.

DES의 개발 과정에서, NSA는 키 크기를 줄이는 것으로 충분하다고 IBM을 설득했고, S박스 구조의 개발을 간접적으로 지원했으며, 최종 DES 알고리즘이 통계적 ^[9]또는 수학적 약점으로부터 자유롭다는 것을 증명했습니다.

그러나, 그것은 또한 다음과 같은 것을 발견했다.

NSA는 알고리즘의 설계에 어떠한 조작도 하지 않았다.IBM은 알고리즘을 발명 및 설계하고 이에 관한 모든 관련 결정을 내렸으며, 합의된 키 크기가 DES가 ^[10]의도된 모든 상용 애플리케이션에 충분하다는 데 동의했습니다.

DES 팀의 또 다른 멤버인 Walter Tuchman은 "우리는 IBMers를 사용하여 완전히 IBM 내부에서 DES 알고리즘을 개발했습니다.NSA는 단 한 건의 회선도 지시하지 않았습니다.^[11]이와는 대조적으로 암호 역사에 관한 NSA의 기밀 해제 책에는 다음과 같이 기술되어 있습니다.

1973년 NBS는 민간 산업에 데이터 암호화 표준(DES)을 요청했다.첫 번째 제품은 실망스러웠기 때문에 NSA는 자체 알고리즘을 개발하기 시작했습니다.그 후 연구 및 엔지니어링 담당 부책임자인 Howard Rosenblum은 IBM의 Walter Tuchman이 루시퍼를 일반 용도로 개조하는 작업을 하고 있다는 것을 알게 되었습니다.NSA는 Tuchman에게 허가를 내주고 그가 루시퍼 ^[12]수정에 대해 CIA와 공동으로 작업하도록 그를 데려왔습니다.

그리고.

NSA는 IBM과 긴밀히 협력하여 무차별 공격을 제외한 모든 공격에 대해 알고리즘을 강화하고 S-box라고 불리는 대체 테이블을 강화했습니다.반대로 NSA는 IBM을 설득하여 키의 길이를 64비트에서 48비트로 줄이려고 했습니다.최종적으로 그들은 56비트 ^[13][14]키를 침해했다.

S-box의 숨겨진 약점에 대한 의혹 중 일부는 1990년에 블록 암호를 해독하는 일반적인 방법인 차등 암호 분석의 독자 발견과 공개 출판으로 누그러졌다.DES의 S박스는 무작위로 선택되었을 때보다 공격에 훨씬 더 강한 내성을 가지고 있어 IBM이 1970년대에 이 기술에 대해 알고 있었음을 강하게 시사합니다.1994년에 Don Coppersmith는 S박스의 ^[15]원래 디자인 기준 중 일부를 발표했습니다.스티븐 레비에 따르면, IBM 왓슨 연구원들은 1974년에 차등 암호 분석 공격을 발견했고 NSA로부터 이 기술을 비밀로 ^[16]해달라는 요청을 받았다.Coppersmith는 IBM의 비밀유지 결정에 대해 다음과 같이 설명합니다. "이는 [차이 암호화]가 매우 강력한 도구가 될 수 있고, 많은 계획에 사용될 수 있으며, 공공 영역의 그러한 정보가 국가 안보에 악영향을 미칠 수 있다는 우려가 있었기 때문입니다."Levy는 월터 투치먼의 말을 인용했다: "모든 문서에 기밀 도장을 찍어달라고 부탁했다.때문에 미 정부 분류되는 것으로 간주되었지만 우리는 실제로 각에 금고에서 그들을 가두어 놓, 놓았습니다 많은.그것을 한다고 말했다.그래서 it"았다.[16]브루스 슈나이어 그"그것은 학문적 커뮤니티는 국가 안보국 'tweaks'실제로 DES의 보안 향상시켰다를 알아내기 위해 20년이 걸렸다."[17]을 관찰했다.

표준으로서의 알고리즘

이러한 비판에도 불구하고, DES는 1976년 11월에 연방 표준으로 승인되었고 1977년 1월 15일 FIPS PUB 46으로 발행되었으며, 모든 미분류 데이터에 사용할 수 있도록 승인되었다.이후 1983년, 1988년(FIPS-46-1로 개정), 1993년(FIPS-46-2) 및 1999년(FIPS-46-3)에 표준으로 재확인되었으며, 후자는 "트리플 DES"를 규정하였다(아래 참조).2002년 5월 26일, DES는 공모전 끝에 Advanced Encryption Standard(AES; 고도 암호화 표준)로 대체되었습니다.2005년 5월 19일, FIPS 46-3은 공식적으로 철회되었지만, NIST는 정부의 민감한 ^[18]정보에 대해 2030년까지 트리플 DES를 승인했습니다.

이 알고리즘은 ANSI X3.92(현재의 X3은 INCITS, ANSI X3.92는 ANSI INCITS 92),^[19] NIST SP 800-67^[18] 및 ISO/IEC 18033-3^[20](TDEA의 컴포넌트)에도 지정되어 있습니다.

또 다른 이론적인 공격인 선형 암호 해독은 1994년에 발표되었지만, 1998년에 전자 프런티어 재단의 DES 크래커가 DES를 매우 실질적으로 공격할 수 있다는 것을 증명했고, 대체 알고리즘의 필요성을 강조했습니다.이러한 암호 해독 방법 및 기타 방법에 대해서는 이 문서의 뒷부분에서 자세히 설명합니다.

DES의 도입은 암호학, 특히 블록 암호를 해독하는 방법의 학술 연구에 촉매제가 된 것으로 생각된다.DES에 대한 NIST 회고전에 따르면

DES는 암호화 알고리즘의 비군사적 연구와 개발을 '점프 스타트'했다고 할 수 있습니다.1970년대에는 군사나 정보기관 종사자를 제외하고는 암호학자가 거의 없었고 암호학에 대한 학문적 연구도 거의 없었다.현재 많은 활동적인 학계의 암호학자, 암호학 분야의 강력한 프로그램을 가진 수리학과, 상업적인 정보 보안 회사 및 컨설턴트가 있습니다.한 세대의 암호 분석가가 DES 알고리즘의 분석(즉, "균열"을 시도함)을 중단했습니다.암호학자인 Bruce ^[21]Schneier는 다음과 같이 말했습니다. "DES는 암호 분석 분야를 활성화하는 데 무엇보다 많은 기여를 했습니다.이제 연구해야 할 알고리즘이 생겼습니다."1970년대와 1980년대에 암호학에서 열린 문헌의 놀라운 점유율은 DES를 다루었고, DES는 그 이후의 모든 대칭 키 알고리즘과 ^[22]비교되는 표준입니다.

연표

날짜.	연도	이벤트
5월 15일	1973	NBS는 표준 암호화 알고리즘에 대한 첫 번째 요청을 발행합니다.
8월 27일	1974	NBS가 암호화 알고리즘에 대한 두 번째 요청을 게시합니다.
3월 17일	1975	DES는 코멘트를 위해 연방관보에 게재되어 있습니다.
8월	1976	DES에 관한 첫 번째 워크숍
9월.	1976	두 번째 워크숍, DES의 수학적 기초에 대해 논의합니다.
11월	1976	DES가 표준으로 승인됨
1월 15일	1977	DES는 FIPS 표준 FIPS PUB 46으로 발행됩니다.
6월.	1977	Diffie와 Hellman은 DES 암호는 무차별적인 [1]힘에 의해 깨질 수 있다고 주장한다.
	1983	DES가 처음으로 확인되었습니다.
	1986	DES에 기반한 TV 위성 스크램블링 시스템인 Videocipher II는 HBO에 의해 사용을 시작합니다.
1월 22일	1988	DES는 FIPS 46-1로 두 번째 확인되었으며 FIPS PUB 46을 대체하고 있습니다.
7월.	1991	Biham과 Shamir는 차분 암호 분석을 재발견하여 15라운드 DES 유사 암호 시스템에 적용합니다.
	1992	Biham과 Shamir는 무차별적인 힘보다 덜 복잡한 최초의 이론적인 공격을 보고했습니다: 차분 암호 분석.그러나 비현실적인47 2개의 평문을 선택해야 합니다.
12월 30일	1993	DES는 FIPS 46-2로 세 번째로 재확인되었습니다.
	1994	DES의 첫 번째 실험 암호해석은 선형 암호해석을 사용하여 수행된다(Matsui, 1994).
6월.	1997	DESCHALL 프로젝트는 DES로 암호화된 메시지를 처음으로 공개합니다.
7월.	1998	EFF의 DES 크래커(Deep Crack)는 56시간 만에 DES 키를 파손합니다.
1월	1999	Deep Crack과 distributed.net은 함께 22시간 15분 만에 DES 키를 파손합니다.
10월 25일	1999	DES는 레거시 시스템에서만 단일 DES가 허용되며 트리플 DES의 우선 사용을 규정하는 FIPS 46-3으로 4번째 확인되었습니다.
11월 26일	2001	Advanced Encryption Standard는 FIPS 197에 게재되어 있습니다.
5월 26일	2002	AES가 유효하게 되다
7월 26일	2004	FIPS 46-3(및 몇 가지 관련 표준)의 철회는 연방[23] 관보에 제안되어 있다.
5월 19일	2005	NIST, FIPS 46-3 철회(연방공보 vol 70, 번호 96 참조)
4월	2006	독일 보쿰 대학교와 키엘 대학의 FPGA 기반의 병렬 머신 COPACOBANA는 하드웨어 [24]비용 10,000달러로 9일 만에 DES를 파괴했습니다.1년 이내에 소프트웨어 개선으로 평균 소요 시간이 6.4일로 단축되었습니다.
11월	2008	COPACOBANA의 후속 모델인 RIVYERA 기계는 평균 시간을 하루 미만으로 줄였습니다.
8월	2016	오픈 소스 패스워드 크래킹소프트웨어 해시캣이 범용 GPU의 DES 브루트포스 검색에 추가되었습니다.벤치마킹에 의하면, 시판되고 있는 Nvidia GeForce GTX 1080Ti GPU가 1개의 키를 평균 15일 이내에 회수합니다(완전 검색은 30일 소요).시스템은 8개의 GTX 1080Ti GPU로 구축되었으며, 평균 2일 이내에 [25]키를 복구할 수 있습니다.
7월.	2017	레인보우 테이블을 이용한 선택 플레인텍스트 공격은 특정 선택 플레인텍스트 112233445566778의 DES 키를 25초 만에 회복할 수 있다.새로운 무지개 표는 평문별로 계산해야 한다.레인보우 테이블 세트가 [26]한정되어 다운로드가 가능합니다.

묘사

DES는 전형적인 블록 암호입니다.일반 텍스트비트의 고정 길이 스트링을 일련의 복잡한 조작을 통해 같은 길이의 다른 암호 텍스트 비트 문자열로 변환하는 알고리즘입니다.DES의 경우 블록사이즈는 64비트입니다또한 DES는 키를 사용하여 변환을 커스터마이즈하기 때문에 암호화에 사용되는 특정 키를 알고 있는 사람만이 복호화를 실행할 수 있습니다.키는 표면적으로는 64비트로 구성되지만 알고리즘에 의해 실제로 사용되는 것은 56비트뿐입니다.8비트는 패리티 체크에만 사용되며 이후 폐기됩니다.따라서 유효한 키의 길이는 56비트입니다.

키는 명목상 8바이트로 저장 또는 전송되며 각각 홀수 패리티가 있습니다.ANSI X3.92-1981(현재는 ANSI INCITS 92-1981)에 따르면 섹션 3.5:

KEY의 각 8비트 바이트의 1비트는 키 생성, 배포 및 저장 시 오류 검출에 사용할 수 있습니다.비트 8, 16, 64는 각 바이트가 홀수 패리티임을 확인하는 데 사용됩니다.

다른 블록 암호와 마찬가지로 DES 자체는 안전한 암호화 수단이 아니라 운영 모드에서 사용해야 합니다.FIPS-81 에서는,^[27] DES 로 사용하는 몇개의 모드가 지정되어 있습니다.DES 의 사용에 관한 코멘트는, FIPS-74 ^[28]에 기재되어 있습니다.

암호 해독은 암호화와 동일한 구조를 사용하지만 키는 역순으로 사용합니다.(이를 통해 동일한 하드웨어 또는 소프트웨어를 양방향으로 사용할 수 있다는 장점이 있습니다.)

전체적인 구조

이 섹션은 확인을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.(2009년 8월) (이 템플릿메시지의 삭제 방법과 삭제 타이밍에 대해 설명합니다)

알고리즘의 전체 구조는 그림 1에 나와 있습니다. 라운드로 불리는 16개의 동일한 처리 단계가 있습니다.또한 IP와 FP라는 이름의 초기 및 최종 순열도 있습니다.이 순열은 반전입니다(IP는 FP의 액션을 "undoes"하고 그 반대도 마찬가지입니다.IP 및 FP는 암호화상의 의미는 없지만 1970년대 중반의 8비트 기반 ^[29]하드웨어에 대한 블록 로드를 용이하게 하기 위해 포함되었습니다.

메인 라운드 전에 블록은 2개의 32비트 반으로 분할되어 번갈아 처리됩니다.이 크리스 크로싱을 페이스텔 방식이라고 합니다.Feistel 구조는 복호화와 암호화가 매우 유사한 프로세스임을 보증합니다.단, 유일한 차이점은 복호화 시 서브키가 역순으로 적용된다는 것입니다.나머지 알고리즘은 동일합니다.이로 인해 별도의 암호화 및 복호화 알고리즘이 필요하지 않으므로 특히 하드웨어에서 구현이 크게 간소화됩니다.

symbol 기호는 배타적 논리합(XOR) 연산을 나타냅니다.F-함수는 일부 키와 함께 절반 블록을 스크램블합니다.그런 다음 F-함수의 출력이 블록의 나머지 절반과 결합되고 나머지 절반은 다음 라운드 전에 교환됩니다.최종 라운드가 끝나면 절반은 교환됩니다.이것은 암호화 및 복호화 프로세스를 비슷하게 하는 Feistel 구조의 기능입니다.

Feistel(F) 기능

그림 2에 나타난 F-함수는 한 번에 반 블록(32비트)으로 작동하며 4단계로 구성됩니다.

1. 확장: 32비트 하프 블록은 그림에서 E로 표시된 확장 순열을 사용하여 비트의 절반을 복제하여 48비트로 확장됩니다.출력은 8개의 6비트(8 × 6 = 48비트) 조각으로 구성되며, 각각은 4개의 해당 입력 비트의 복사본과 각 입력 조각에서 양쪽으로 바로 인접한 비트의 복사본을 포함합니다.
2. 키 혼합: 결과는 XOR 연산을 사용하여 하위 키와 결합됩니다.각 라운드에 1개씩 16개의 48비트서브키가 키스케줄(아래 설명)을 사용하여 메인키에서 파생됩니다.
3. 치환: 서브키에 혼합한 후 S박스, 즉 치환박스로 처리하기 전에 블록을 8개의 6비트 조각으로 분할한다.8개의 S박스 각각은 룩업 테이블의 형태로 제공되는 비선형 변환에 따라 6개의 입력 비트를 4개의 출력 비트로 치환한다.S-box는 DES 보안의 핵심을 제공합니다.S-box가 없으면 암호는 선형으로 분할되어 문제가 발생할 수 있습니다.
4. 치환: 마지막으로 S박스로부터의 32개의 출력을 고정치환 P박스에 따라 재배치한다.이는 치환 후 이 라운드의 각 S박스 출력의 비트가 다음 라운드에서 4개의 다른 S박스에 분산되도록 설계되어 있습니다.

S박스로부터의 치환과 P박스 및 E-확장으로부터의 비트의 순열은 각각, 1940년대에 Claude Shannon에 의해서 안전하지만 실용적인 암호의 필요조건으로 식별된 개념인 이른바 「혼란과 확산」을 제공한다.

주요 일정

그림 3은 암호화의 주요 스케줄, 즉 서브키를 생성하는 알고리즘을 나타내고 있습니다.처음에 키의 56비트는 Permated Choice 1(PC-1)에 의해 초기 64비트에서 선택됩니다.나머지 8비트는 폐기되거나 패리티 체크비트로 사용됩니다.다음으로 56비트는 2개의 28비트로 분할되며, 그 후 각각 개별적으로 처리됩니다.연속 라운드에서 양쪽 반쪽이 1비트 또는2비트(각 라운드에 대해 지정) 왼쪽으로 회전하고 다음으로 48개의 서브키 비트가 Permated Choice 2(PC-2)에 의해 선택됩니다(왼쪽 반쪽에서24비트, 오른쪽에서24비트).회전(그림에서 "<<"로 표시됨)은 각 서브키에서 서로 다른 비트 세트가 사용됨을 의미합니다. 각 비트는 16개의 서브키 중 약 14개에서 사용됩니다.

복호화 키 스케줄도 비슷합니다.서브키는 암호화와 비교하여 역순으로 되어 있습니다.이 변경 이외에는 암호화 프로세스와 동일합니다.동일한 28비트가 모든 회전 박스에 전달됩니다.

보안 및 암호 분석

DES의 암호화에 관한 정보는 다른 어떤 블록 암호보다 더 많이 공개되어 있지만, 지금까지 가장 실용적인 공격은 여전히 무차별적인 접근법입니다.여러 가지 사소한 암호 분석 특성이 알려져 있으며, 이론적으로는 무차별 공격보다 덜 복잡하지만 실행하는데 비현실적인 수의 알려진 또는 선택된 평문을 필요로 하며 실제로는 문제가 되지 않는 세 가지 이론적 공격이 가능합니다.

무차별 공격

모든 암호에 대해 가장 기본적인 공격 방식은 무차별 포스입니다.즉, 가능한 모든 키를 차례로 시험합니다.키의 길이에 따라 가능한 키의 수가 결정되며, 따라서 이 접근법의 실현 가능성이 결정됩니다.DES의 경우 표준으로 채택되기 전부터 키 사이즈의 적정성에 대한 의문이 제기되었으며, 이는 이론적인 암호해석이 아닌 작은 키 사이즈였기 때문에 대체 알고리즘이 필요하게 되었다.NSA를 포함한 외부 컨설턴트가 논의한 결과 키 크기가 128비트에서 56비트로 축소되어 단일 칩에 ^[30]맞게 되었습니다.

학계에서는 DES 크래킹 기계에 대한 다양한 제안이 제시되었다.1977년 Diffie와 Hellman은 하루에 ^[1][31]DES 키를 찾을 수 있는 약 2천만 달러의 비용이 드는 기계를 제안했습니다.1993년, Wiener는 7시간 이내에 키를 찾을 수 있는 100만 달러의 비용이 드는 키 검색 기계를 제안했습니다.그러나 이러한 초기 제안 중 어떤 것도 구현되지 않았거나, 적어도 구현이 공개적으로 인정되지 않았습니다.DES의 취약성은 1990년대 ^[32]후반에 실제로 입증되었다.1997년에 RSA Security는 일련의 콘테스트를 후원하여 콘테스트에서 DES로 암호화된 메시지를 해독한 첫 번째 팀에게 $10,000의 상금을 수여했습니다.이 콘테스트는 록 버저, 맷 커틴, 저스틴 돌스키가 이끄는 DESCHALL 프로젝트에 의해 수상되었습니다.이 프로젝트는 인터넷을 통해 수천 대의 컴퓨터를 아이돌 사이클로 사용하고 있습니다.DES를 신속하게 크래킹할 수 있는 가능성은 1998년 사이버 공간 민권 단체인 Electronic Frontier Foundation(EFF)이 약 25만 달러를 들여 맞춤형 DES 크래커를 제작하면서 입증되었습니다(EFF DES 크래커 참조).그들의 동기는 DES가 이론뿐만 아니라 실제에서도 깨지기 쉽다는 것을 보여주는 것이었다. "진실을 눈으로 확인할 수 있을 때까지 믿지 않는 사람이 많다. DES를 며칠 안에 크래킹할 수 있는 물리 머신을 보여주는 것만이 DES에 대한 보안을 신뢰할 수 없다는 것을 일부 사용자에게 납득시킬 수 있는 유일한 방법입니다." 이 머신은 2일 남짓의 검색으로 키를 강제했습니다.

다음으로 확인된 DES 크래커는 독일에 있는 보쿰 대학과 키엘 대학 팀에 의해 2006년에 만들어진 COPACOBANA 기계이다.EFF 기계와 달리 COPACOBANA는 시판되고 재구성 가능한 집적회로로 구성됩니다.XILINX Spartan-3 1000 타입의 Field-Programmable Gate Array(FPGA; 필드 프로그래머블 게이트 어레이) 중 120개가 병렬로 동작한다.20개의 DIMM 모듈로 그룹화되어 있으며 각 모듈에는 6개의 FPGA가 포함되어 있습니다.재구성 가능한 하드웨어를 사용하면 기계는 다른 코드 브레이크 작업에도 적용할 수 있습니다.^[33]COPACOBANA의 가장 흥미로운 측면 중 하나는 비용 요인입니다.기계 한 대를 약 10,000달러에 ^[34]만들 수 있습니다.EFF 머신에 비해 약 25배의 비용 절감은 디지털 하드웨어가 지속적으로 개선되고 있음을 보여주는 예입니다(Moore의 법칙 참조).8년간 인플레이션을 조정하면 약 30배 더 높은 개선 효과를 얻을 수 있습니다.COPACOBANA의 두 프로젝트 파트너의 분사 회사인 SciEngines GmbH는 2007년부터 COPACOBANA의 후계자를 강화 및 개발했습니다.2008년 COPACOBANA RIVYERA는 128대의 Spartan-3 5000을 사용하여 DES를 파손하는 시간을 하루 미만으로 단축했습니다.SciEngines RIVYERA는 128개의 Spartan-3 5000 ^[35]FPGA를 활용하여 브루트포스 브레이킹 DES 기록을 보유하고 있습니다.이번에는 256 Spartan-6 LX150 모델이 더 낮아졌다.

2012년, David Hulton과 Moxie Marlinspike는 48개의 Xilinx Virtex-6 LX240T FPGA를 탑재한 시스템을 발표했습니다.각 FPGA는 400MHz로 동작하는 40개의 완전 파이프라인 DES 코어를 포함하고 있으며, 총 용량은 768기가/초입니다.시스템은 약 26시간 만에 56비트 DES 키 공간을 모두 검색할 수 있으며,^[36][37] 이 서비스는 온라인에서 유료입니다.

무차별적인 공격보다 빠른 공격

16라운드의 DES를 brute-force search보다 복잡도가 낮은 것으로 알려진 공격이 3개 있습니다.그것은 차분 암호 분석(^[38]DC), 선형 암호 분석(LC)^[39] 및 Davies [40]공격입니다.단, 공격은 이론적인 것으로, 일반적으로 ^[41]실전에서는 실행할 수 없는 것으로 간주됩니다.이러한 유형의 공격은 인증상의 약점이라고 불리기도 합니다.

• 차분 암호 해독은 1980년대 후반에 Eli Biham과 Adi Shamir에 의해 재발견되었습니다.IBM과 NSA는 일찍이 알고 있었고 비밀에 부쳐졌습니다.16라운드를 모두 해제하려면 차분 암호해석을 위해 2개의 ^[38]평문을 선택해야 합니다⁴⁷.DES는 DC에 내성을 갖도록 설계되어 있습니다.
• 선형 암호 해독은 마쓰이 미쓰루에 의해 발견되었으며, 알려진 2개의 평문이 필요하다⁴³(Matsui, 1993).^[39] 이 방법이 구현되었으며(Matsui, 1994), DES의 실험 암호 해독이 최초로 보고되었다.DES가 이러한 유형의 공격에 대해 내성을 갖도록 조정되었다는 증거는 없습니다.LC의 일반화(다중 선형 암호 분석)는 1994년에 제안되었으며(Kaliski와 Robshaw), Biryukov와 다른 사람들에 의해 더욱 개선되었습니다.(2004); 그 분석에 따르면 공격의 데이터 요건을 최소 4배(즉,^[42] 2가⁴¹ 아닌⁴³ 2) 줄이기 위해 복수의 선형 근사치를 사용할 수 있다.선형 암호 해석의 선택된 평문 변형에서도 데이터 복잡도의 비슷한 감소를 얻을 수 있다(Knudsen 및 Mathiassen, 2000).^[43]Junod(2001)는 선형 암호 해독의 실제 시간 복잡성을 결정하기 위해 몇 가지 실험을 수행했으며, 예측보다 다소 빨랐으며, 2-2^{41 [44]}DES 평가와 동등한³⁹ 시간이 필요하다고 보고했다.
• 개량된 데이비스의 공격: 선형 및 차분 암호해석은 일반적인 기술로 많은 스킴에 적용할 수 있지만 데이비스의 공격은 DES에 특화된 기술로 80년대에 ^[40]도널드 데이비스가 처음 제안했으며 Biham과 Biryukov(1997)^[45]에 의해 개선되었습니다.가장 강력한 형태의 공격에는 알려진 평문이 2개 필요하며⁵⁰ 계산 복잡도는 2개이며⁵⁰ 성공률은 51%입니다.

또한 축소판 암호, 즉 16라운드 미만의 DES 버전에 대한 공격이 제안되었습니다.이러한 분석은 안전을 위해 얼마나 많은 라운드가 필요한지, 그리고 풀 버전이 얼마나 많은 "보안 여유"를 보유하고 있는지에 대한 통찰력을 제공한다.

미분-선형 암호해석은 1994년 Langford와 Hellman에 의해 제안되었으며, 미분 및 선형 암호해석을 단일 ^[46]공격으로 결합했습니다.공격의 확장 버전은 2개의 선택된 플레인텍스트를 사용하여^15.8 9라운드 DES를 해제할 수 있으며 2시간의 복잡성이 있습니다^29.2(Biham and others, 2002).^[47]

부암호화 속성

DES는 다음과 같은 보완 특성을 나타낸다.

${\displaystyle E_{K}(P)=C\iff E_{\overline {K}}({\overline {P}})=오버라인 {C}}}$

$여기$서 x ${\$ {\$displaystyle {x}$는${\displaystyle }$x의 $비트{\displaystyle }$ 단위 보완어입니다$.\displaystyle$ $x.}$ ${\displaystyle E_{}}$ K는 $키{\displaystyle }$K를 사용한 암호화를 나타냅니다$.\$$displaystyle$$$K$.}$$$$P$는 $일반$ $텍스트$ $블록,$C는$$$$ 암호 블록입니다.보완 속성은 선택된 플레인텍스트 가정 하에서 brute-force 공격의 작업을 2배(또는1비트) 줄일 수 있음을 의미합니다.정의상 이 속성은 TDES ^[48]암호에도 적용됩니다.

DES에는 이른바 약점 키도 4개 있습니다.약한 키에서의 암호화(E)와 복호화(D)의 효과는 동일합니다(인볼루션 참조).

$displaystyle E_{K}(E_{K})(P)$=$P$$}$ 또는 이에 $상당$하는 E${\displaystyle {}_{}{K}_{}}$ = $D$K . { $displaystyle E_${K} =$D_{$K$}.$$}$

6쌍의 반취약 키도 있습니다.반취약 키쌍 중 $하나$인 $(\$을 사용한 암호화는 다른 $(\$와의 복호화와 동일하게 동작합니다.

$displaystyle E_{K_{1}}$=$P$$}$ 또는 이에 $상당$하는 ${\displaystyle {E{}_{}}_{}}$ ${\displaystyle {{K\mathrm{}}_{}}_{}}$ 2${\displaystyle {{}_{}}_{}}$= $D$ . { $displaystyle E_{K_{$2}} =$D_{K_{$1$}}.$$}$

구현에서 약한 키와 반약한 키를 명시적으로 테스트하거나 무작위로 키를 선택하는 것만으로 충분히 쉽게 피할 수 있습니다. 우연히 약한 키 또는 반약한 키를 선택할 확률은 무시할 수 있습니다.공격에는 전혀 이점이 없기 때문에 키는 다른 키보다 약하지 않습니다.

또한 DES는 그룹이 아니며, 보다 정확하게는 기능 구성 하에서 집합 $\{{\displaystyle E_{}}$ K $}(가능$한 모든 $키{\displaystyle }$K {\$displaystyle$$\{E_{K$$\}\backslash \})$은 그룹이 아니며,^[49] 그룹화에 가깝지도 않다는 것이 증명되었습니다.이것은 한동안 미해결 문제였습니다.만약 그렇다면 DES를 해제할 수 있었을 것입니다.또한 Triple DES 등의 여러 암호화 모드에서는 보안이 강화되지 않습니다.다른 키에서의 반복적인 암호화(및 복호화)는 다른 단일 ^[50]키에서의 암호화와 동등하기 때문입니다.

심플한 DES

Simplified DES(SDES)는 학생들이 최신 암호 분석 기술을 배울 수 있도록 교육 목적으로만 설계되었습니다.SDES는 DES와 구조나 특성이 비슷하지만 연필이나 종이를 사용하여 암호화 및 복호화를 훨씬 쉽게 수행할 수 있도록 간소화되었습니다.SDES를 학습하면 DES 및 기타 블록 암호에 대한 통찰력과 그에 ^{[51][52][53][54][55][56][57][58][59]}대한 다양한 암호 공격에 대한 통찰력을 얻을 수 있다고 생각하는 사람도 있습니다.

치환 알고리즘

이 섹션은 확인을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.(2009년 11월) (이 템플릿메시지를 삭제하는 방법과 타이밍에 대해 설명합니다)

소프트웨어에서의 보안과 DES의 비교적 느린 동작에 대한 우려로 연구자들은 1980년대 후반과 1990년대 초에 나타나기 시작한 다양한 대체 블록 암호 설계를 제안하게 되었습니다. 예를 들어 RC5, Blowfish, IDEA, NewDES, SAFER, CAST5, FEAL 등이 있습니다.이러한 설계 대부분은 DES의 64비트 블록 크기를 유지하며 일반적으로 64비트 또는 128비트 키를 사용하지만 "드롭인" 대체 역할을 할 수 있습니다.소련에서는 GOST 28147-89 알고리즘이 도입되어 64비트 블록사이즈와 256비트 키가 사용되었습니다.이 알고리즘은 나중에 러시아에서도 사용되었습니다.

DES 자체는 보다 안전한 방식으로 조정 및 재사용할 수 있습니다.이전의 많은 DES 사용자는 현재 DES의 특허권자 중 한 명이 기술 및 분석한 Triple DES(TDES)를 사용하고 있습니다(FIPS Pub 46-3 참조). 2개의 (2TDES) 키 또는 3개의 (3TDES) 키를 사용하여 DES를 3회 적용합니다.TDES는 매우 느리지만 충분히 안전한 것으로 간주됩니다.계산 비용이 적게 드는 대안은 DES-X로, DES의 전후로 추가 키 재료를 XOR함으로써 키 크기를 늘립니다.GDES는 암호화 속도를 높이기 위한 방법으로 제안된 DES 변종이었지만, 차분 암호 해독의 영향을 받기 쉬운 것으로 나타났습니다.

1997년 1월 2일, NIST는 ^[60]DES의 후계자를 선정하고 싶다고 발표했습니다.2001년 NIST는 국제 대회 후 새로운 암호인 Advanced Encryption Standard(AES)를 ^[61]대체품으로 선택했습니다.AES로 선정된 알고리즘은 디자이너들이 Rijndael이라는 이름으로 제출했습니다.NIST AES 대회의 다른 최종 후보에는 RC6, 서펜트, MARS, Twofish가 포함되었습니다.

「 」를 참조해 주세요.

• Brute Force: 데이터 암호화 표준을 깨다
• DES 보충 재료
• 스킵잭(암호화기)
• 트리플 DES

메모들

레퍼런스

외부 링크

• FIPS 46-3: DES 표준을 설명하는 공식 문서(PDF)
• COPACOBANA, 보쿰과 키엘 대학의 FPGA를 기반으로 한 10,000달러 DES 크래커
• DES 단계별 프레젠테이션 및 신뢰성 높은 메시지 인코딩 애플리케이션
• 소프트웨어에서의 신속한 새로운 DES 구현 - Biham
• 다중 선형 근사
• RFC4772: Data Encryption Standard(DES; 데이터 암호화 표준) 사용에 따른 보안상의 영향