암호 해시함수의 보안

암호학에서는 암호 해시함수를 크게 두 가지 범주로 나눌 수 있다.첫 번째 범주에는 수학적 문제에 기초하여 설계가 이루어지며 따라서 엄격한 수학적 증명, 복잡성 이론 및 형식적 감소로부터 보안이 뒤따르는 기능들이 포함된다.이러한 기능을 Provable Secure Cryptography Hash Functions라고 한다.이것들을 구성하는 것은 매우 어렵고, 몇 가지 예가 소개되지 않았다.그들의 실용성은 제한되어 있다.

두 번째 범주에는 수학적 문제가 아니라 메시지 비트가 혼합되어 해시를 생성하는 애드호크 구조에 기반한 함수가 있다.그 후 이것들은 깨기 힘들다고 여겨지지만, 공식적인 증거는 제시되지 않는다.널리 사용되는 거의 모든 해시함수가 이 범주에 존재한다.이 기능들 중 일부는 이미 고장났고, 더 이상 사용되지 않고 있다.해시 함수 보안 요약을 참조하십시오.

해시함수의 보안 유형

일반적으로 암호해시함수의 기본 보안은 영상전저항, 2차 사전영상저항, 충돌저항, 사이비랜덤 등 다른 각도에서 볼 수 있다.

사전 이미지 저항: $해시$ h $h$ 을 $h$ (를) $h=hash(m)$ 하면 h $h=hash(m)$ = $h=hash(m)$ a h $){\displaystyle h=hash(m)}$ 과 $m$ 같은 메시지 $m$ ${\displaystym m}$ 을(를) 찾기가 어려워야 한다 $h=hash(m)$ 이 개념은 단방향 함수의 개념과 관련이 있다.이 속성이 부족한 기능은 사전 이미지 공격에 취약하다.
두 번째 사전 이미지 저항: 입력 m $m_{1}$ ${\$ 1}을 $m_{1}$ 를) 지정하면 $hash(m_{1})=hash(m_{2})$ $hash(m_{1})=hash(m_{2})$ 인 $hash(m_{1})=hash(m_{2})$ 2 $hash(m_{1})=hash(m_{2})$ $displaystyle m_{1}:{$ 2 $m_{1}$ 1 $m_{1}$ ${\$ $displaystym m_{1}})$ 을(를) 찾기가 어려우므로 h $hash(m_{1})=hash(m_{2})$ 1 $hash(m_{1})=hash(m_{2})$ ) = $hash(m_{1})=hash(m_{2})$ 2 $hash(m_{1})=hash(m_{2})$ ) = h( $m$ 2 $)=hash(m_{\display_$ {\display_ ${1$ 이 성질을 약한 충돌 저항이라고 부르기도 한다.이 특성이 없는 기능은 두 번째 사전 이미지 공격에 취약하다.
충돌 저항: $hash(m_{1})=hash(m_{2})$ $hash(m_{1})=hash(m_{2})$ ) $hash(m_{1})=hash(m_{2})$ = $hash(m_{1})=hash(m_{2})$ ( m 1 ) = h $hash(m_{1})=hash(m_{2})$ $hash(m_{1})=hash(m_{2})$ 2 $hash(m_{1})=hash(m_{2})$ ) {\ $displaystyle 해시(m_{$ 1}}= $hash(m_{$ 2})}과 $m_{2}$ 같은 두 개의 $m_{1}$ $m_{2}$ m 1 $m_{2}$ {\ $displaystym m_{1$ }{2 $}}$ 를 $m_{1}$ 찾기가 어려워야 한다 $hash(m_{1})=hash(m_{2})$ 이러한 쌍을 (크립토그래픽) 해시 충돌이라고 한다.이 성질을 강한 충돌 저항이라고 부르기도 한다.그것은 최소 두 배 이상의 해시 값을 필요로 한다. 그렇지 않으면 생일 공격에 의해 충돌이 발견될 수 있다.
의사 난수: 해시함수를 바탕으로 의사 난수 생성기와 난수 생성기를 구별하기 어려워야 한다. 예를 들어, 일반적인 난수성 테스트를 통과한다.

"힘들다"의 의미

기본적인 질문은 '힘들다'의 의미다.이 질문에 대답하는 데는 두 가지 방법이 있다.첫째는 직관적/실용적 접근법이다: "강력한 것은 시스템의 보안이 중요하다고 여겨지는 한 시스템 파괴를 막아야 하는 어떤 적국의 손이 닿지 않는 것이 거의 확실하다는 것을 의미한다."

두 번째 접근법은 이론적이며 계산 복잡성 이론에 기초한다.A 문제가 어렵다면 정수 인수 문제나 이산 로그 문제 등 다항 시간대에 해결할 수 없는 문제로 여겨지는 문제로부터 공식적인 보안 감소가 존재한다.

그러나 다항 시간 알고리즘이 존재하지 않는다고 해서 시스템이 자동으로 안전하다고 보장되는 것은 아니다.문제의 난이도 역시 크기에 달려 있다.예를 들어 RSA 공용 키 암호화는 정수 인자화의 난이도에 의존한다.다만 최소 2048비트 이상의 키로만 안전하다고 본다.

암호 케이스

또한 해시에 대한 입력 집합이 상대적으로 작거나 어떤 식으로든 우도에 의해 정렬된 경우 이론적 보안에 관계없이 짐승의 힘 검색이 실용적일 수 있다.프리이미지를 복구할 가능성은 입력 세트 크기와 해시함수의 계산 속도 또는 비용에 따라 달라진다.일반적인 예는 암호 유효성 검사 데이터를 저장하기 위해 해시를 사용하는 것이다.사용자 암호의 일반 텍스트를 저장하기 보다는, 일반적으로 접근 제어 시스템은 암호의 해시를 저장한다.사용자가 액세스를 요청할 때 제출하는 비밀번호가 해시되어 저장된 값과 비교된다.저장된 유효성 검사 데이터를 도난당하면 도둑은 암호가 아닌 해시 값만 갖게 된다.그러나 대부분의 사용자들은 예측 가능한 방법으로 비밀번호를 선택하고 종종 패스워드가 충분히 짧아서 빠른 해시를 사용할 경우 가능한 모든 조합을 시험할 수 있다.^[1]검색 속도를 늦추기 위해 키 파생 함수라고 불리는 특별한 해시가 만들어졌다.암호 크래킹을 참조하십시오.

암호해시함수

대부분의 해시함수는 메시지의 비트가 해시를 생성하기 위해 잘 혼합되어 있는 애드혹 기반으로 구축된다.출력물의 높은 복잡성과 의사 무작위성을 보장하기 위해 다양한 비트 연산(예: 회전), 모듈식 추가 및 압축 기능이 반복적 모드에서 사용된다.이런 식으로 보안은 입증하기가 매우 어렵고 증명은 대개 이루어지지 않는다.불과 몇 년 전만 해도, 가장 인기 있는 해시함수 중 하나인 SHA-1이 제시된 길이보다 덜 안전한 것으로 나타났다. 즉, 충돌은 2번의⁵¹^[2]⁸⁰ 실험에서 발견될 수 있었다.

즉, 오늘날 사용되고 있는 해시함수의 대부분은 내충돌성이 입증되지 않는다.이러한 해시는 순전히 수학적인 함수에 근거한 것이 아니다.이 접근방식은 일반적으로 해싱 기능이 더 효과적이지만, 그러한 기능의 약점이 결국 충돌을 찾기 위해 사용될 위험과 함께 한다.유명한 경우는 MD5이다.

이러한 경우에 "충돌을 찾기 어렵다"는 의미는 "시스템의 보안이 중요하다고 여겨지는 한 시스템 파괴를 막아야 하는 거의 모든 적국의 손이 닿지 않는 범위"를 의미한다.따라서 악의적인 행위자가 업무에 투입할 수 있는 노력은 일반적으로 예상되는 이득에 비례하기 때문에 용어의 의미는 적용에 다소 의존한다.

안전한 해시함수

이 접근법에서 우리는 해시함수의 보안을 어떤 어려운 수학적인 문제에 기초하고 있으며 해시함수의 충돌을 찾는 것이 근본적인 문제를 깨뜨리는 것만큼 어렵다는 것을 증명한다.이것은 고전적 접근법에서처럼 단지 비트의 복잡한 혼합에 의존하는 것보다 다소 강한 보안 개념을 제공한다.

암호화 해시함수는 다항 시간 내에 해결할 수 없는 문제 P로부터 충돌 발견이 가능한 다항식 시간 환원이 가능한 경우 충돌 공격에 대한 보안성을 입증한다.그리고 나서 그 기능은 확실히 안전하거나 또는 단지 증명할 수 있는 것이라고 불린다.

알고리즘 A에 의해 다항식 시간에 충돌을 찾는 것이 실현 가능하다면 다항식 시간에서 해결이 불가능하다고 널리 알려진 문제 P를 해결하기 위해 알고리즘 A를 사용하는 다항식 시간 알고리즘 R(축소 알고리즘)을 찾아 사용할 수 있다는 것이다.그것은 모순이다.충돌 발견이 P를 해결하는 것보다 쉬울 수 없다는 뜻이다.

그러나 이것은 단지 '일부' 경우에 충돌 발견이 어렵다는 것을 나타낼 뿐이다. 왜냐하면 계산적으로 어려운 문제의 모든 경우가 일반적으로 어려운 것은 아니기 때문이다.실제로, NP-하드 문제의 매우 큰 사례들은 일상적으로 해결되는 반면, 가장 어려운 문제들만이 실질적으로 해결이 불가능하다.

그들의 보안을 증명하는 해시함수는 수학함수에 기초한다.

어려운 문제들

다항식 시간 내에 해결할 수 없는 것으로 간주되는 문제의 예

검증 가능한 접근 방식의 단점

보안 감소를 입증할 수 있는 현재의 충돌 내성 해시 알고리즘은 비효율적이어서 실무에 활용할 수 없다.고전적인 해시함수에 비해 상대적으로 느린 경향이 있으며, 전통적으로 암호 해시에 기대되는 모든 기준을 항상 충족하지는 않는다.아주 매끄러운 해시가 그 예다.
해시 알고리즘의 복잡한 비트의 혼합이 상대편이 충돌을 발견하지 못할 정도로 강력하기를 바라는 고전적인 접근법을 사용하는 것보다 해시함수를 구성하는 것이 훨씬 더 어렵다.
그 증거는 종종 점증적으로 딱딱하고 최악의 경우 또는 평균적인 경우 복잡성의 문제를 감소시킨다.최악의 경우는 기본적인 문제의 전형적인 경우보다는 병리학적 사례의 해결의 어려움을 측정한다.하드 평균 복잡성이 있는 문제를 줄이는 것조차도 문제 공간의 일부에 대해 문제를 쉽게 해결할 수 있는 알고리즘이 여전히 있을 수 있기 때문에 제한된 보안만 제공한다.예를 들어, Fast Syndrome Based Hash의 초기 버전은 불안정한 것으로 밝혀졌다.이 문제는 최신판에서 해결되었다.

SWIFT는 이러한 보안 문제를 우회하는 해시함수의 예다.추정 시간 T 내에 확률 P로 SWIFT를 깰 수 있는 알고리즘에 대해서는 T와 P에 따라 특정 어려운 수학 문제의 최악의 시나리오를 시간 T' 내에 해결하는 알고리즘을 찾을 수 있다는 것을 알 수 있다.^{[citation needed]}

(실용적이지 않은) 보안 해시함수의 예

해시(m) = x^m mod n 여기서 n은 복합 숫자를 고려하기 어렵고 x는 미리 지정된 기본 값이다.x에^m2 대한 충돌 x는^m1 x의 순서의 다중 m1 - m2를 나타낸다. 이러한 정보는 x의 특정 특성을 가정하여 다항 시간에서 n을 인자화하는 데 사용될 수 있다.

그러나 알고리즘은 메시지 비트당 평균 1.5배수 modulo n을 요구하기 때문에 상당히 비효율적이다.

보다 실용적으로 안전한 해시함수

VSH - 매우 부드러운 해시 함수 - 비경쟁 모듈형 사각 루트 모듈로 $합성$ 번호 n ${\$ $displaystyle$ n $}$ 을(를) 찾는 경도를 가정할 때 내충돌 방지 해시함수 $($ 이것은 $n$ 을 인수하는 것만큼 단단한 것으로 입증됨). $n$
무해시
ECOH - 타원 곡선만 해시 함수 - 타원 곡선, 서브셋 합계 문제 및 다항식의 합계의 개념을 기반으로 한다.충돌 저항의 보안 증거는 약화되는 가정에 근거했고 결국 두 번째 사전 이미지 공격이 발견되었다.
FSB - Fast Syndrome-Based 해시함수 - FSB를 깨는 것이 적어도 일반 신드롬 디코딩이라고 알려진 특정 NP-완전 문제를 해결하는 것만큼 어렵다는 것을 증명할 수 있다.
SWIFT - SWIFT는 고속 푸리에 변환을 기반으로 하며, 주기/이상 래치에서 짧은 벡터를 찾는 최악의 경우를 가정했을 때 충돌에 내성이 있다.
Chaum, van Heijst, Pfitzmann 해시함수 - 유한그룹 $F_{2p+1}$ $F_{2p+1}$ + $F_{2p+1}$ ${\$ 의 이산 로그 문제를 해결하는 것만큼 충돌을 찾는 것이 어려운 압축함수 $F_{2p+1}$
배낭 기반 해시함수 - 배낭 문제를 기반으로 한 해시함수 계열이다.
제모어-틸리히 해시함수 - 행렬 SL2 그룹의 산술에 의존하는 해시함수군.충돌을 찾는 것은 적어도 이 그룹에서 특정 요소의 인자화를 찾는 것만큼 어렵다.이것은 적어도 PSPACE-완전해야 한다.^{[dubious – discuss]}이 해시의 경우, 결국 $2^{n/2}$ / 2 ${\$ 2 $^{n/2}}$ 에 가까운 시간 복잡성으로 공격이 발견되었다 $2^{n/2}$ 이 박자는 Zémor-Tillrich 해시함수의 $2^{3n/2}$ $2^{3n}$ 2 $2^{3n/2}$ / $2^{3n/2}$ ${\$ 2 $^{3n/2}},$ 2 $2^{3n/2}$ $2^{3n}$ ${\$ 인 생일 바운드 및 이상적인 사전 이미지 콤플렉스로 나타났다.공격에는 크기가 $[\displaystyle 2n}$ 인 축소된 집합의 생일 검색이 포함되기 때문에, 검증 $2n$ 가능한 보안에 대한 개념을 파괴하거나 계획을 무효화하지는 않지만 오히려 초기 매개변수가 너무 작았다는 것을 암시한다.^[3]
시그마 프로토콜의 해시함수 - 구체적으로 어떤 (적합한) 시그마 프로토콜로부터, 검증 가능한 시큐어 해시를 구성하는 일반적인 방법이 존재한다.VSH(VSH*라고 함)의 더 빠른 버전은 이러한 방식으로 얻을 수 있다.

참조

^ Goodin, Dan (2012-12-10). "25-GPU cluster cracks every standard Windows password in <6 hours". Ars Technica. Retrieved 2020-11-23.
^ http://eprint.iacr.org/2008/469.pdf
^ Petit, C.; Quisquater, J.-J.; Tillich, J.-P., "Hard and easy Components of Collision Search in the Zémor-Tillich hash function:new Attacks and Reduced Variants with Equivalent Security" (PDF), {{citation}}:누락 또는 비어 있음 title=(도움말)

[1] Goodin, Dan (2012-12-10). "25-GPU cluster cracks every standard Windows password in <6 hours". Ars Technica. Retrieved 2020-11-23.

[2] ttp://eprint.iacr.org/2008/469.pdf

[3] Petit, C.; Quisquater, J.-J.; Tillich, J.-P., "Hard and easy Components of Collision Search in the Zémor-Tillich hash function:new Attacks and Reduced Variants with Equivalent Security" (PDF), {{citation}}:누락 또는 비어 있음 title=(도움말)

[1]

[2]

[3]

Search