💻 computer science

Renting the Cracking Machine with a Cost-and-Time Analysis of Exhaustive DES-56 Key Search in the Cloud

이 논문은 일반적인 AWS EC2 인스턴스를 사용하여 56비트 DES 키 공간을 전체 전수 조사하는 데 약 120만 달러의 비용과 적절한 규모의 플릿(fleet)을 통해 약 21년이 소요되는 반면, 자금력이 충분한 공격자가 시간을 사기 위해 돈을 지불한다면 단 하루 만에 조사를 완료하는 것이 실질적으로 가능하다는 점과 더불어, 더 작은 부분 공간 공격은 무시할 수 있는 비용으로 실행될 수 있음을 입증한다.

원저자: Gonzalo Sharif Curi Martínez, Rodrigo Ramele

게시일 2026-07-28✓ Author reviewed ⓘ

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Gonzalo Sharif Curi Martínez, Rodrigo Ramele

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

디지털 자물쇠와 열쇠의 세계를 상상해 보십시오. 그곳에서는 의도된 수신자만이 읽을 수 있도록 비밀 메시지가 암호화됩니다. 수십 년 동안, 데이터 암호 표준(DES)이라 불리는 특정한 자물쇠는 비밀을 안전하게 지키는 황금 표준이었습니다. DES를 56개의 숫자가 있는 다이얼을 가진 거대한 조합 자물쇠라고 생각해 보십시오. 이 자물쇠를 깨뜨리려면 도둑은 자물쇠가 딸깍 하고 열릴 때까지 가능한 모든 조합을 하나씩 다 시도해야 합니다. 숫자의 범위가 매우 높았기 때문에, 한때는 슈퍼컴퓨터나 거대하고 특수 제작된 기계만이 충분히 빠르게 이 모든 조합을 시도할 수 있을 것이라고 생각되었습니다. 하지만 세상이 변했습니다. 오늘날 우리에게는 '클라우드'가 있습니다. 이는 자신만의 컴퓨터를 사는 대신, 매 분 단위로 거대하고 보이지 않는 컴퓨터 군단을 빌려 쓰는 것과 같습니다. 연구자들이 던져온 핵심 질문은 이것입니다. 만약 당신이 단지 이 오래된 자물쇠를 부수고 싶다면, 그 군단을 빌리는 데 비용이 얼마나 들며, 얼마나 기다려야 하는가? 만약 비용이 낮고 시간이 짧다면, 그 오래된 자물쇠는 더 이상 안전하지 않으며, 우리의 오래된 비밀들이 실제로 얼마나 취약한지 정확히 알아야 하기 때문에 이 질문은 중요합니다.

이 논문은 곤살로(Gonzalo)와 로드리고(Rodrigo)라는 두 명의 연구자가 실제로 아마존의 AWS 클라우드에서 컴퓨터 군단을 빌려 DES 자물쇠를 부수는 방식으로 답을 찾기로 결심한 대담한 실험과 같습니다. 그들은 특수한 기계를 만들지 않았습니다. 그저 신용카드만 있으면 누구나 이용할 수 있는 표준 컴퓨터들을 사용했습니다. 그들은 이 작업을 위해 37대의 컴퓨터 팀을 구성하여 서로 협력하게 했으며, 각 컴퓨터는 방대한 숫자 조합 중 서로 다른 조각을 확인하도록 했습니다. 그들은 이 작업을 거대한 보물찾기처럼 다루었습니다. 즉, "보물"(비밀 키)을 출발선으로부터 서로 다른 거리에 숨겨두고, 컴퓨터 군단이 그것을 찾는 데 시간이 얼마나 걸리는지 측정했습니다.

결과는 작은 거리에서는 놀라울 정도로 빠르고 저렴했습니다. 보물이 가까운 곳(첫 1억 개 조합 이내)에 숨겨졌을 때, 컴퓨터들은 대부분의 시간을 그저 깨어나서 작업할 준비를 하는 데 보냈습니다. 이런 경우, 전체 작업은 약 2분이 걸렸고 비용은 50센트 미만이었습니다. 이는 마치 택시 기사에게 몇 달러를 주고 동네 구멍가게까지 가달라고 하는 것과 같았습니다. 운전 자체는 순식간이었지만, 시간은 주로 기사가 도착하기를 기다리는 데 소요되었습니다.

하지만 보물을 더 멀리 숨길수록 이야기는 달라졌습니다. 보물을 150억 개 조합까지 밀어냈을 때, 실제로 키를 찾는 데 드는 시간이 주요 요인이 되었습니다. 컴퓨터들은 꾸준히 작동하여 약 87분 만에 키를 찾아냈으며, 비용은 약 18달러였습니다. 연구자들은 컴퓨터가 매우 효율적이어서 단 한 대의 기계로 초당 거의 3백만 개의 조합을 확인할 수 있다는 것을 발견했습니다. 37대의 기계를 모두 합치면, 초당 1억 개 이상의 키를 확인하고 있었습니다.

그들의 발견 중 가장 흥激적인 부분은 만약 당신이 단순히 일부분이 아니라 전체 자물쇠를 정말로 부수고 싶다면 어떤 일이 벌어지는가 하는 점입니다. 전체 자물쇠에는 약 72경 개의 가능한 조합이 있습니다. 현재의 37대 컴퓨터 설정으로는 모든 조합을 확인하는 데 약 21년이 걸립니다. 이는 불가능해 보이지만, 연구자들은 이 작업이 매우 나누기 쉽기 때문에 돈을 시간과 맞바꿀 수 있다는 것을 보여주었습니다. 만약 당신이 아주 큰 주머니를 가지고 있어 약 14만 대의 거대한 컴퓨터 함대를 빌릴 수 있다면, 단 하루 만에 전체 자물쇠를 부술 수 있습니다. 이 거대한 노력에 드는 총비용은 약 120만 달러가 될 것입니다.

그래서 이것이 무엇을 의미할까요? 이 논문은 오래된 DES 자물쇠가 사실상 깨졌음을 증명합니다. 만약 나쁜 놈이 적은 돈을 가지고 있다면, 커피 한 잔 값으로 특정하고 제한적인 부분의 코드를 깰 수 있습니다. 만약 그들이 많은 돈을 가지고 있다면, 단 하루 만에 전체 코드를 깰 수 있습니다. 연구자들은 또한 자신들의 컴퓨터 기반 접근 방식이 빠르긴 했지만, 현대의 그래픽 카드(비디오 게임에 사용되는 종류)를 사용하면 이를 훨씬 더 저렴하고 빠르게 만들 수 있어, 시간과 비용을 또 다른 백 배까지 줄일 수 있다고 언급했습니다. 결론은 명확합니다. 56비트 자물쇠는 더 이상 장벽이 아닙니다. 그것은 단지 당신이 이 자물쇠를 부수기 위해 얼마만큼의 현금을 쓸 용의가 있느냐의 문제입니다.

기술 요약: 클라우드에서의 전수 DES-56 키 탐색에 대한 비용 및 시간 분석을 통한 크래킹 머신 임대

문제 정의
데이터 암호 표준(DES)은 유효 키 길이( $2^{56} \approx 7.2 \times 10^{16}$ 키)를 가지며, 1998년 이후로 이미 암호학적으로 파괴되었습니다. 이전의 연구들은 전용 하드웨어(ASIC, FPGA)와 알고리즘 최적화를 사용하여 DES를 파괴하는 것이 가능하다는 것을 입증해 왔으나, 현대의 범용 클라우드 인프라를 사용하여 전수 키 탐색을 수행할 때 필요한 비용과 시간에 대한 구체적이고 재현 가능한 최근 데이터는 부족한 실정입니다. 본 연구가 다루는 핵심 질문은 다음과 같습니다: 공격자가 사용한 초 단위의 컴퓨팅 시간만큼만 비용을 지불하는 렌탈 클라우드 클러스터에서 실행될 때, 전체 DES 브루트 포스(brute-force) 공격은 얼마나 비싸고 얼마나 빠른가?

방법론
저자들은 DES 키 탐색의 성능과 비용을 실증적으로 측정하기 위해 Amazon Web Services(AWS) 상에 분산 브루트 포스 시스템을 구현했습니다.

시스템 아키텍처: 시스템은 코디네이터(Python)와 37개의 워커 노드(AWS EC2 c6i.2xlarge 인스턴스, 각 인스턴스당 8 vCPU)를 활용합니다. 56비트 키 공간은 37개의 서로 소인 범위로 분할됩니다. 코디네이터는 사용자 데이터(user-data) 스크립트를 통해 인스턴스를 실행하고, 탐색 범위를 배분하며, 후보 보고를 위한 Amazon SQS(Simple Queue Service)와 중단 신호 방송을 위한 Amazon S3를 통해 결과를 관리합니다.
워커 구현: 워커는 8개의 vCPU에 걸쳐 탐색을 병렬화하기 위해 Open-MP를 사용한 C 언어로 작성되었습니다. 처리량을 극대화하기 위해 네 가지 특정 최적화가 포함되었습니다:
1. SP-테이블: S-박스 치환과 P-치환을 결합하여 L1 캐시에 완전히 들어가는 사전 계산된 테이블.
2. 바이트 인덱스 LUT: 비트 수준의 루프를 제거하기 위해 비트 치환(IP, IP⁻¹, PC-1, PC-2)을 위한 룩업 테이블.
3. 직접 비트 시프트 확장: 중간 48비트 값을 생성하지 않도록 확장 함수를 서브키 XOR 및 테이블 인덱싱과 융합.
4. 조기 거부 (COA 모드): 암호문 단독 공격(Ciphertext-Only Attack, COA) 모드에서, 출력되는 바이트가 인쇄 불가능한 문자일 경우 즉시 복호화를 중단합니다. 이는 단 한 블록만으로도 무작위 키의 약 99.96%를 거부하여, 키당 유효 비용을 획기적으로 줄여줍니다.
스코어링 메커서리즘: 시스템은 스페인어 단일 문자 빈도를 기반으로 한 로그 빈도 점수를 사용하여 의미 있는 평문을 식별하는 암호문 단독 공격(COA) 모드로 작동합니다. 유효한 후보와 무작위 노이즈를 구분하는 임계값은 $-4.0 \times \text{nbytes}$ 입니다.
실험 설계: 저자들은 두 그룹으로 나뉜 15회의 독립적인 실험을 수행했습니다:
- 그룹 A (부팅 주도형): AWS 인스턴스 프로비저닝 지연 시간의 영향을 측정하기 위해 작은 키 오프셋( $10^6$ ~ $10^8$ )을 사용한 10회의 실험.
- 그룹 B (탐색 주도형): 순수 탐색 처리량과 선형 스케일링을 측정하기 위해 더 큰 오프셋( $10^9$ ~ $1.5 \times 10^{10}$ )을 사용한 5회의 실험.

주요 결과

처리량: 시스템은 37개 인스턴스 전체에서 약 1억 800만 키/초(인스턴스당 2.91 M 키/s)의 집계 처리량을 달ometric했습니다. 오프셋 대비 탐색 시간에 대한 선형 적합도는 $R^2 = 0.9994$ 를 기록하여 일정한 처리량을 확인했습니다.
시간 및 비용 영역:
- 작은 오프셋 ( $\le 10^8$ ): 총 시간은 AWS 부팅 지연 시간(약 90초)에 의해 지배됩니다. 이 실험들의 평균 시간은 $116.8 \pm 20.1$ 초였으며, 공격당 평균 비용은 $0.41였습니다.
- 큰 오프셋: 탐색 시간이 지배적인 요인이 됩니다. $1.5 \times 10^{10}$ 오프셋에 위치한 키를 찾는 데 약 87분이 소요되었고 비용은 $18이 들었습니다.
전체 키 공간 외삽:
- 측정된 처리량에 따르면, 단일 37-인스서스 플릿(fleet)이 전체 $2^{56}$ 키 공간을 모두 소진하려면 최악의 경우 약 21년, 기대되는 경우 약 10.6년이 필요합니다.
- 그러나 작업의 무작위로 분산 가능한(embarrassingly parallel) 특성 덕분에, 시간은 돈과 선형적으로 교환될 수 있습니다. 저자들은 완전한 전수 탐색 비용이 기대값 기준 약 $120만**(기대 사례) 또는 **$ 230만(최악의 사례)이 될 것으로 추정합니다.
- 충분히 큰 규모의 플릿(예: 약 $1.4 \times 10^5$ 인스턴스)을 사용하면, 동일한 예산 내에서 하루 만에 전체 탐색을 완료할 수 있습니다.

의의 및 주장
본 논문은 범용 클라우드 인프라에서 DES를 깨는 데 드는 비용과 시간에 대한 최초의 실증적이고 재현 가능한 해답을 제공합니다. 저자들은 다음과 같이 결론짓습니다:

제한된 부분 공간 공격 (Bounded-Subspace Attacks): 알려진 관리 가능한 수준의 키 공간 내에 있는 키의 경우, 공격은 매우 저렴하고(1달러 미만) 빠릅니다(몇 분 내).
전체 소진 (Full Exhaustion): 비용은 많이 들지만, 전수 탐색은 충분한 자금을 가진 공격자에게 "확실히 손에 닿는 범위"에 있습니다. 이는 더 이상 기술적 장벽이 아니라 예산의 문제입니다.
경제적 변화: 역사적인 전용 하드웨어(예: 2006년의 COPACOBANA)와 비교할 때, 클라우드 컴퓨팅은 초기 자본 투자 없이 진입 장벽을 획기적으로 낮춥니다.
미래 전망: 저자들은 현재의 CPU 기반 구현이 가장 비용 효율적인 옵션은 아니라고 언급합니다. 그들은 GPU로 시스템을 이식할 경우(수십억 키/초의 처리량 가능성 언급) 시간과 비용을 모두 1~2 자릿수(orders of magnitude) 정도 줄일 수 있을 것이라고 제안합니다.

본 논문은 탄력적인 클라우드 용량과 병렬 처리를 결식하면 키 공간이 충분한 자금력을 갖춘 엔티티에게 사실상 탐색 가능한 상태가 되므로, DES가 현대 시대에 의미 있는 보안을 제공하지 못한다고 단언합니다.

유사한 논문