주요 발견 공격

이 문서에는 여러 가지 문제가 있습니다.개선을 돕거나 토크 페이지에서 이러한 문제에 대해 논의해 주십시오.(이러한 템플릿메시지를 삭제하는 방법과 타이밍에 대해 설명합니다) 이 기사는 다른 어떤 관련 기사도 없기 때문에 고아이다.관련 기사에서 이 페이지의 링크를 소개해주세요.제안사항은 찾기 링크 툴을 사용해 주세요. (2016년 10월) 이 문서에는 일반적인 참조 목록이 포함되어 있지만 대응하는 충분한 인라인 인용이 없습니다. 좀 더 정확한 인용문을 도입하여 개선해주시기 바랍니다. (2016년 10월) (템플릿 메시지 삭제 방법 및 삭제 시기 확인) (이 템플릿메시지를 삭제하는 방법과 타이밍을 확인합니다)

키 검색 공격이란 암호 방식을 사용하는 컴퓨터 시스템에 대한 공격입니다. 암호 방식을 사용하여 컴퓨터 메모리 또는 비휘발성 스토리지를 검색하여 데이터 복호화 또는 서명에 사용할 수 있는 개인 암호 키를 검색합니다.이 용어는 일반적으로 단순히 바이트의 각 시퀀스를 테스트하여 올바른 답을 제공하는지 여부를 판단하는 것보다 훨씬 효율적으로 메모리를 검색하는 공격의 컨텍스트에서 사용됩니다.콜드 부트 공격과 조합하여 컴퓨터에서 주요 자료를 추출하는 경우가 많습니다.

접근

Shamir와 van Someren은 Key Finding 공격에 관한 중요한^[1] 논문에서 Key Finding에 대해 통계적 또는 Entropic Key Finding과 분석적 Key Finding이라는 두 가지 접근 방식을 제안했습니다.전자는 암호화 키를 구성하는 데이터의 통계 속성 차이를 검출하는 데 의존하며 후자는 타깃 키 재료에 반드시 존재해야 하는 특정 바이트 패턴을 결정하고 이러한 패턴을 찾는 데 의존합니다.

통계 키 검색

일반적으로 대부분의 암호 시스템에서는 암호 키가 가능한 한 랜덤이어야 합니다.대부분의 대칭 암호에서 키는 정말로 랜덤한 비트 집합이어야 합니다.대부분의 비대칭 암호에서 개인 키는 특정 제약(프라이머리티 또는 그룹 내 생성기 등)을 사용하여 무작위로 선택된 숫자이거나 일부 제약이 있는 랜덤 번호 집합에 기반한 계산 결과입니다.어느 경우든 키 재료는 높은 엔트로피를 나타낸다.이와는 대조적으로 컴퓨터 메모리에 있는 대부분의 압축되지 않은 데이터는 상대적으로 엔트로피가 낮습니다.따라서 키가 원시 형태로 메모리에 존재하는 것으로 알려진 경우 엔트로피가 높기 때문에 키가 아닌 데이터의 배경에서 두드러질 수 있으며 공격자는 엔트로피가 높은 메모리 또는 스토리지 영역에서만 일치하는 키를 테스트해야 합니다.

대부분의 데이터의 낮은 엔트로피와 키 데이터의 높은 엔트로피 사이의 대비는 육안 검사로 충분히 알 수 있다.오른쪽 이미지는 이 예를 보여줍니다.

분석 키 검색

통계 키 검색은 검색해야 하는 메모리 양을 줄이는 데 효과적일 수 있지만, 여전히 정확한 키 재료가 포함되어 있는지 확인하기 위해 고엔트로피 영역을 테스트해야 합니다.경우에 따라서는, 특히 공개 키 암호화 시스템의 컨텍스트에서는, 키 자료내에서 발생할 필요가 있는 패턴을 특정해, 이러한 패턴이 검출되는 영역으로 검색을 제한할 수 있습니다.

Shamir와 van^[1] Someren은 공개 키가 알려져 있고 공개 지수가 적은 개인 RSA 키를 찾기 위한 분석 접근법의 한 예를 시연했습니다.RSA 시스템에서 공용 키는 쌍$({\displaystyle n}$ ,${\displaystyle e}$) {$displaystyle (n, e$입니다.$여기$서 n ${\displaystyle =p}$ .$$ { $displaystyle$ n $= p$ .$q$ }는$$ p와 q는 2개의 큰 소수입니다.대응하는 개인키는 (${\displaystyle n,}$ $)$ {$displaystyle (n, d$)}($$또는 $({\displaystyle p,q}$, d$)$ {$displaystyle (p, q,$ d)} 또는$$ 그 일부 바리안트$)$입니다${\displaystyle .}여기$서$$.$d.eq$1 ${\pmod$ ($n)}$은 1에 d를 곱한 것과 같습니다.$(n)}$ 여기서$$ θ는 오일러의 전체 함수를 나타내며 곱셈군 모듈로 n의 크기이다.RSA 키의 경우:

${\displaystyle \varphi }$( n )${\displaystyle =}$( ${\displaystyle p}$-${\displaystyle }$1 ) (${\displaystyle q}$- 1)${\displaystyle =}$ ${\displaystyle n}$- ${\displaystyle p}$ -${\displaystyle \mathrm{q}}$+ 1 ( \$displaystyle$ \$phi$ ( n ) = ( $p$- 1 )= n - p - $q$+ 1 $$}

$n$에서 ${\displaystyle (}$ (${\displaystyle n}$ )$$\ $displaystyle \phi ( n$ )의$$ 값을 구하면 n을 인수분해할 수 있으며, RSA 암호 시스템의 보안은 그 난이도에 달려 있습니다.따라서 공격자는 e와 n을 지정하면 d를 정확하게 판별할 수 없습니다.단, p와 q는 일반적으로 같은 길이의 비트로 선택되며 둘 다 n의 제곱근에 '근접'하다는 것을 알고 있기 때문에 공격은 d가 어떻게 보이는지 상당한 양을 알 수 있습니다.따라서 공격자는 다음과 같이 추측할 수 있습니다.

$\displaystyle \phi (n)\apprough \phi ' (n)=n-2grt {n}}$

그리고 일반적으로 이 근사치는 바이너리 표현에서 더 중요한 비트의 절반에서 정확합니다.e와 d의 관계는 다음을 의미합니다.

${\displaystyle d=(1+k).\phi (n) / e}$

여기서 k의 정확한 값은 알 수 0 < < $.\$ $displaystyle$0 <$k$ <$e$} 이 사실과 $근사치{\displaystyle {}^{}\varphi }$(${\displaystyle }$( n$){ displaystyle$ \$phi$' ($$n$$)를 이용하여 공격자는 k의 각 가능한 값에 대해 d의 바이너리 표현 상위 절반에 대해 가능한 값의 집합을 열거할 수 있다$.$이러한 바이너리 패턴은 추적 복호화를 수행하는 것보다 훨씬 빠르게 여러 개의 크기를 테스트할 수 있습니다.$또한{\displaystyle }$ e $= 3의 일반적$인 경우 k $= 2이므로 d$의 상위 절반 비트를 정확히 결정하고 직접 검색할 수 있습니다$$$.$

어플

키 검색 공격은 콜드 부트 공격과 함께 사용되었으며,^[2] 머신에서 키를 꺼내는 데 사용됩니다.헤닝거와 샤캄은 전원이 ^[3]차단돼 메모리 내 데이터가 파손된 경우에도 키를 추출할 수 있음을 보여줬다.

통계 키 검색은 Nicko van Someren이 MS-CAPI 플러그인의 시그니처를 검증하기 위해 Microsoft가 사용하는 시그니처 검증 키를 특정하기 위해 사용했습니다.이 키들 중 하나는 나중에 마이크로소프트에 의해 NSAKEY로 언급되는 것으로 밝혀져 약간의 논란을 ^[4]불러일으켰다.

경감

키 검색 공격은 여러 가지 방법으로 완화할 수 있습니다.분석 공격의 경우 랜덤화된 키블라인딩은 메모리 내에서 예상되는 패턴을 검출하지 않도록 할 뿐만 아니라 다른 종류의 사이드 채널 공격으로부터 보호합니다.통계적 공격은 다른 종류의 고엔트로피 또는 압축 데이터를 메모리에 저장함으로써 덜 효과적일 수 있으며, 사용하지 않을 때 핵심 재료가 한 곳의 엔트로피 농도를 낮추기 위해 더 큰 메모리 블록에 분산될 수 있다.

레퍼런스