개요: 2005년도에 중국 연구진이 SHA-1 (Secure Hash Algorithm)의 강점을 공격한 바 있다. 이 백서에서는 이 공격 내용을 설명하고 이 알고리즘이 이전에 생각한 것보다 충돌 저항력이 약간 낮다 해도 Maxim의 SHA-1 메모리 소자의 보안은 영향을 받지 않음을 보여준다. 따라서 Maxim의 SHA-1 메모리 소자 (DS1963S, DS1961S, DS2460, DS28CN01, DS28E01-100 및 DS2432)는 계속해서 액세서리/주변기기 인증, 그리고 조작이 불가능하고 검증 가능한 메모리 애플리케이션을 위한 효과적인 저가 솔루션을 제공하게 될 것이다.
개요
Maxim의 SHA-1 메모리 소자는 액세서리/주변기기 인증과 무단 조작이 불가능하고 검증 가능한 메모리 애플리케이션을 위한 매우 효과적인 저가 솔루션을 제공한다. SHA-1 소자를 인증할 수 있는 능력은 고용량 소모품, 고가 하드웨어, 하드웨어 라이센스 관리, 빌딩 접근 제어 또는 무인 판매 등 모조자들의 접근을 차단할 필요가 있는 애플리케이션에서 유용한 기능이다.
궁극적으로 이러한 소자의 활용성은 미국 국가 표준 및 기술 연구소(U.S. National Institute of Standards and Technology: NIST)가 연방 정보 처리 표준 공표 180-1 (Federal Information Processing Standards Publication 180-1; FIPS PUB 180-1)와 ISO/IEC 10118-3에 정의한 바와 같이 안전 해시 알고리즘의 견고성과 보안에 따라 달라진다.
2005년도에 중국 연구진이 이 알고리즘의 강점을 공격한 바 있다 (참고 1 참조). 이 애플리케이션 노트에서는 SHA-1을 사용하는 일부 애플리케이션은 제공되는 보안을 재평가할 필요가 있을 수 있지만 Maxim SHA-1 메모리 소자의 보안은 이 연구소의 주장에 아무런 영향을 받지 않음을 보여준다.
SHA-1에 대한 공격 개요
FIPS PUB 180-1에서는 SHA-1을 데이터의 압축된 표현을 안전하게 계산하기 위한 표준으로 정의하고 있다. 이 문서에서 정의한 바와 같이, 이 알고리즘은 두 가지 주장 때문에 안전한 것으로 간주된다. "(1) 특정 메시지 요약본에 해당하는 메시지를 찾거나, 또는 (2) 동일한 메시지 요약을 생성하는 2개의 서로 다른 메시지를 찾는 것은 전산적으로 불가능하다." 첫 번째 주장은 SHA-1 알고리즘의 결과 출력이 알고리즘에 대한 입력의 전체 문장을 찾아내기에 충분한 정보를 포함하지 않으며 (즉, 알고리즘이 역행할 수 없음), 요약 (출력)을 이용할 수 있다 해도 해당 메시지 (입력)을 찾아내려면 엄청난 리소스와 시간이 소요된다는 것을 의미한다. 두 번째 주장은 동일한 출력을 가져온 2개의 고유한 입력을 찾으려면 엄청난 리소스와 시간이 소요된다는 (즉, 알고리즘은 충돌에 강함) 것을 의미한다. 이러한 가정은 동일한 요약을 공유하는 2개의 메시지가 없다는 것이 아니라 단순히 이 메시지들을 찾는 것이 무척 어렵다는 것을 의미할 뿐이다.
충돌(동일한 요약을 공유하는 한 쌍의 메시지)을 찾아내는 데 필요한 해시 연산의 수를 위한 이론적 경계는 280번의 연산이다 (참고 2 참조). 중국 연구진의 SHA-1 공격은 이러한 경계를 269번의 연산으로 낮추어야 한다는 주장이다. 이 후자의 주장은 실제로 "전산 불가능성"을 211만큼 줄임으로써 두 번째 SHA-1 주장을 약화시킨다. 이것은 동일한 메시지 요약을 생성하는 2개의 서로 다른 메시지를 찾는 것이 더 이상 "전산적으로 불가능하지 않다는 것"을 의미하는 것은 아니며, 단지 이전에 생각했던 것보다 약간 덜 불가능하다는 것을 의미하는 것이다. 더욱이 연구진의 주장은 특정 메시지 요약에 해당하는 메시지를 찾는 것이 더 이상 전산적으로 불가능하지 않다는 것을 의미하는 것은 아니다. 이것은 이 새로운 공격이 두 개의 입력 메시지 모두를 주의깊게 선택할 수 있는 능력에 따라 달라지기 때문이다. 특정 요약에 해당하는 메시지 - 반드시 그 메시지가 아님 - 를 찾기 위한 유일하게 입증된 SHA-1 보안 공격은 2160번의 연산을 수행하는 맹목적인 검색이 필요하다.
두 번째 SHA-1 알고리즘 주장이 이 새로운 중국 연구에 의해 약화되었지만, 이 연구가 첫 번째 SHA-1 주장에 대한 공격으로 이어질 것이라고 의심할 이유는 없다. 요컨대 SHA-1은 여전히 역행될 수 없지만 충돌 내성이 약간 덜할 수 있다. 그럼에도 불구하고 이것은 타임 스탬핑 또는 문서 공증과 같은 디지털 서명에 의존하는 애플리케이션의 경우에는 경종을 울리는 결과일 수 있다. 입력 메시지의 대부분의 정보는 이러한 애플리케이션의 경우 전후관계에 있으므로, 중국 연구진으로부터 효과적이고 특정 애플리케이션과 관련된 공격이 나올 것인지를 알아보아야 한다.
메시지 인증 코드
Maxim SHA-1 메모리 소자는 통신 양방향에서 메시지 인증 코드 (또는 MAC)에 의존한다. MAC을 계산하려면 공개적으로 가시화된 입력 문자열 (메모리 내용, 소자의 고유 일련번호 및 임의 도전으로 구성됨)을 취하고 이것을 SHA1 알고리즘을 위한 입력 메시지로서 비밀 키와 조합해야 한다. 결과 요약 (또는 해시)을 MAC이라 한다. 메시지와 함께 MAC을 전송하면 사용자가 비밀 키를 알고 있고 전송 중 어느 것도 데이터를 건드리지 않았음을 입증하는 안전한 수단이 제공된다. 읽기 동작 시, SHA-1 메모리 소자는 MAC에 응답하여 이것이 진짜이고 호스트가 정확히 데이터를 수신했음을 입증한다. 쓰기 동작 시, 호스트는 소자의 메모리 내용에 변경을 가하는 것이 인증되었고 소자가 새로운 메모리 내용을 정확히 수신하였음을 입증하기 위해 MAC을 제공한다.
이 MAC 기반 보안 시스템의 알고리즘에 대한 공격이 성공하려면 이러한 비밀 키를 찾아내야 할 것이다. 대부분의 사용 가능한 SHA-1 메모리 소자에서 이 키는 64비트 쓰기 전용 값이다. (조만간 새로운 소자는 더 큰 키와 함께 제공될 수 있을 것이다.) 공격자는 소자에게 도전을 보내고, 결과 MAC을 읽은 다음, 일치하는 MAC을 찾을 때까지 모든 64비트 값에 대한 무차별 검색을 실행할 수 있을 것이다. 이러한 행동은 264 SHA-1 연산을 필요로 하고, 그러려면 64 CPU Cray X1 수퍼컴퓨터에서 10년 이상 연산을 해야 할 것이다 (참고 3 참조).
특정 입력 메시지의 요약과 일치시키는 작업인 메시지 찾기는 2160 연산 (비밀 키 찾기에 필요한 264보다 훨씬 더 많음)이 필요하다. Maxim의 입력 메시지의 길이는 512비트로 고정되어 있고 이 비트 중 448개는 알려진 공개 데이터이기 때문에, 가장 직접적인 접근방식은 나머지 64개 비트 (즉, 비밀 키 값)의 정확한 값을 검색하는 것이다. "특정 메시지 요약에 해당하는 메시지 찾기가 전산적으로 불가능"한 한, 무차별 비밀 키 값 검색보다 더 성공적인 공격은 있을 수 없다.
비밀 키 검색을 위한 264 연산의 복잡성은 충돌하는 한 쌍의 메시지를 찾는 데 필요한 269보다 적은 연산이지만, 이러한 공격 클래스 면에서 비교된 바는 없다. 이 연구 팀이 250 연산에서 SHA-1에서 충돌을 찾아내는 방법을 발견했다 해도, 비밀 키 검색은 여전히 비밀 키 값을 찾기 위해 264 SHA-1 연산이 필요할 것이다. 결국, 2개의 입력 메시지 간 충돌을 찾기 위한 새로운 공격은 입력 메시지를 주의깊게 선택해야 하기 때문에 하나의 고정된 특정 입력 메시지의 충돌을 찾기 위해 사용될 수 없다.
요약
SHA-1 메모리 소자가 사용되는 시스템과 관련하여 이 소자에 대한 공격이 있었고 이에 대해 자세히 설명했다 (White Paper 3: Why are SHA-1 Devices Secure? 참조). 그러나 공개적으로 읽을 수 있는 MAC을 사용하여 숨겨진 비밀 키를 찾는 것은 선택된 알고리즘의 강점에 의해 보호되는 유일하게 알려진 공격이다. SHA-1의 경우, 우리는 이 알고리즘이 두 가지 확실한 강점, 즉 충돌에 강함과 역행 불가를 사용하여 정의되었음을 알고 있다. 이 공격은 SHA-1 알고리즘이 이전에 생각했던 것보다 충돌 내성이 약간 덜하다는 것, 그러나 이 공격이 Maxim의 SHA-1 메모리 소자의 보안에는 영향을 주지 않음을 보여주었다.
참고:
SHA-1에서 충돌 찾기는 "생일 역설(birthday paradox)"로 인해
280의 상위 경계를 갖는다. 기본적으로 이 역설에 의하면 임의의 2개의 요소를 n비트의 출력과 일치시키려고 시도할 경우, 일치를 찾을 매우 높은 확률을 가지려면 2(n) 요소가 아니라 2(n/2) 요소를 고려하면 된다. 이것은 잘 알려진 모든 해시의 암호 기법 특성이며 출력의 비트 수에 의해서만 결정된다.
SHA-1 알고리즘은 메시지 블록 요소에 대해 약 1740개의 기본 산술 연산을 수행한다. 추가적인 조작을 위해 20% 오버헤드를 가정할 때, 알고리즘의 완벽한 1회전은 2100회의 클록 사이클 후에 실행될 것이다. 819 기가플롭의 최고 성능으로 동작하는 64개 CPU를 갖춘 Cray X1 수퍼컴퓨터를 사용할 경우, 완벽한 룩업 테이블을 생성하는 데 12.4년의 연속 동작이 필요하게 된다. 2005년도부터 Cray에서 광고하고 있는 64개의 캐비넷으로 구성된 최대 X1 시스템이라면 2개월 이상 소요될 것이다. 그처럼 많은 전산 능력이 든다면 이러한 유형의 공격은 엄청나게 비싸진다.
의견을 보내주세요! 위 내용이 도움이 되셨나요? 여러분의 의견을 기다립니다 — Maxim은 보내주신 정정이나 제안사항을 반영하고 있습니다.
이 페이지를 평가하고 의견을 보내주십시오.
다운로드, PDF 형식
