타원 곡선만 해시

타원 곡선 전용 해시(ECOH)
일반
디자이너	다니엘 R. L. 브라운, 맷 캄파냐, 르네 슈트루익
초간출판	2008
파생된 위치	무해시
디테일
다이제스트 크기	224, 256, 384 또는 512
최고의 공개 암호 분석
	두 번째 사전 이미지

타원 곡선 전용 해시(ECOH) 알고리즘은 NIST 해시함수 대회에서 SHA-3 후보로서 제출되었다. 하지만 두 번째 사전 이미지 공격이 발견돼 대회 초반에 거절당했다.

ECOH는 아직 공격이 성공하지 못한 MuHASH 해시 알고리즘을 기반으로 한다. 하지만, MuHASH는 실용적이기엔 너무 비효율적이어서 변경이 필요했다. 가장 큰 차이점은 무해시가 랜덤 오라클을^{[clarification needed]} 적용하는 경우 ECOH가 패딩 기능을 적용한다는 점이다. 임의의 경솔함을 가정할 때, MuHASH에서 충돌을 발견하는 것은 이산 로그 문제를 해결하는 것을 의미한다. 따라서 MuHASH는 확실히 안전한 해시(즉, 우리는 충돌을 발견하는 것이 적어도 어떤 잘 알려진 수학 문제만큼 어렵다는 것을 알고 있다.

ECOH는 무작위 경구들을 사용하지 않으며 그것의 보안은 이산 로그 문제와 직접적으로 관련이 있지는 않지만, 그것은 여전히 수학적 함수에 기초하고 있다. ECOH는 Summation Polyomial Problem이라 불리는 이진장보다 Summary 다항식 방정식에 대한 낮은 수준의 해결책을 찾는 Semaev의 문제와 관련이 있다. 이 문제를 해결하기 위한 효율적인 알고리즘은 지금까지 주어지지 않았다. 문제가 NP-hard로 입증되지는 않았지만, 그러한 알고리즘은 존재하지 않는다고 가정한다. 특정 가정 하에서, ECOH에서 충돌을 발견하는 것은 부분집합 문제의 한 예로 볼 수도 있다. Summary Polyomial Problem을 해결하는 것 외에도, 두 번째 프리이미지를 찾아 충돌을 일으키는 다른 방법이 있는데, 바그너의 일반적인 생일 공격이다.

ECOH는 해시를 얻기 위해 비트의 고전적인 애드혹 혼합이 아닌 수학적 함수(증거 가능한 보안 접근법)에 기반을 둔 해시함수의 좋은 예다.

알고리즘

$n$ ${\displaystyle$ n $n$ ECOH는 메시지 $M$ ${\$ displaystyle $M$ $}을($ 를) $M_{0},\ldots ,M_{n-1}$ ${\$ displaystyle M $M_{0},\ldots ,M_{n-1}$ …, $M_{0},\ldots ,M_{n-1}$ - $M_{0},\ldots ,M_{n-1}$ ${\$ 로 $M$ $n$ 나눈다 $M_{0},\ldots ,M_{n-1}$ 마지막 블록이 불완전한 경우에는 1개로 패딩한 다음 0으로 패딩한다. 더 나아가 $P$ $P$ 을(를) 타원 곡선 지점에 메시지 블록과 정수를 매핑하는 함수가 되도록 $P$ 하자. 그런 다음 매핑 $P$ $P$ 을 $P$ 를) 사용하여 각 블록을 타원 곡선 $P_{i}$ $P_{i}$ i ${\$ P_ ${i}$ 로 변환하고 $P_{i}$ 이 포인트들을 두 포인트 더 추가한다. $X_{1}$ 의 추가 $X_{1}$ 포인트 X 1 {\displaystyle $X_{1$ }는 패딩을 포함하며 $X_{1}$ 메시지 길이에만 의존한다. 두 번째 추가 지점 $X_{2}$ $X_{2}$ ${\$ }}번은 모든 메시지 블록의 메시지 길이와 XOR에 따라 달라진다 $X_{2}$ . 해시 $H$ $H$ 을(를) 얻기 위해 결과가 잘린다 $H$

${\reasoned}P_{i}&}:=P(M_{i}})\\X_{1}&{}:=P'(n)\X_{2}&}:=P^{*}(M_{i},n)\\Q&{}}=\sum _{i=0}^{n-1P_{i}+X_{1}+X_{1}+X_{2}\\R&{}=f(Q)\end{arged}}}}}$

두 개의 가산점은 $P$ $'$ ${\$ P $'}$ 과 $P'$ $P^{*}$ $P^{*}$ ${\$ 에 의해 계산된다. $P^{*}$ $Q$ $Q$ 는 모든 타원 곡선 포인트와 두 개의 가산점을 함께 추가한다 $Q$ . 마지막으로 결과는 해시 결과 $R$ ${\displaystyle$ R $}$ 을(를) 얻기 위해 출력 변환 함수 f를 통해 $R$ 전달된다. 이 알고리즘에 대한 자세한 내용은 "ECoH: 타원 곡선 전용 해시"를 참조하십시오.

예

ECOH-224, ECOH-256, ECOH-384, ECOH-512 등 4개의 ECOH 알고리즘이 제안되었다. 숫자는 메시지 요약 크기를 나타낸다. 매개변수의 길이, 블록 크기 및 사용된 타원곡선에서 서로 다르다. 처음 두 개는 타원 곡선 B-283을 사용한다: X $X^{283}+X^{12}+X^{7}+X^{5}+1$ + $X^{283}+X^{12}+X^{7}+X^{5}+1$ $X^{283}+X^{12}+X^{7}+X^{5}+1$ + $X^{283}+X^{12}+X^{7}+X^{5}+1$ $X^{283}+X^{12}+X^{7}+X^{5}+1$ + X $X^{283}+X^{12}+X^{7}+X^{5}+1$ + $X^{283}+X^{12}+X^{7}+X^{5}+1$ ${\displaystyle X^{283}+X^{12}+X^{7}+X^{5}+1$ . ECOH-384는 B-409: $X^{409}+X^{87}+1$ $X^{409}+X^{87}+1$ + $X^{409}+X^{87}+1$ $X^{409}+X^{87}+1$ + 1 ${\displaystyle$ X $^{409}+X^{87}+1}$ 의 $X^{409}+X^{87}+1$ 곡선을 매개변수(192, 64, 64, 64)와 함께 사용한다. ECOH-512는 B-571 $X^{571}+X^{10}+X^{5}+X^{2}+1$ $X^{571}+X^{10}+X^{5}+X^{2}+1$ $X^{571}+X^{10}+X^{5}+X^{2}+1$ + $X^{571}+X^{10}+X^{5}+X^{2}+1$ $X^{571}+X^{10}+X^{5}+X^{2}+1$ + $X^{571}+X^{10}+X^{5}+X^{2}+1$ $X^{571}+X^{10}+X^{5}+X^{2}+1$ + $X^{571}+X^{10}+X^{5}+X^{2}+1$ $X^{571}+X^{10}+X^{5}+X^{2}+1$ + 1 ${\displaystyle$ X $^{571}+X^{10}+X^{5}+X^{2}+1}$ 를 파라미터와 함께 사용한다. 최대 $2^{128}$ $2^{128}$ ${\$ 까지의 비트 길이의 메시지를 해시할 수 있다 $2^{128}$

특성.

증분성: 메시지의 작은 변화와 ECOH 계산의 중간 값을 고려할 때 메시지의 ECOH는 빠르게 업데이트될 수 있다.
병렬 처리 가능성: $P_{i}'s$ 은 P $P_{i}'s$ $P_{i}'s$ $P_{i}'s$ $P_{i$ 의 계산이 $병렬$ 시스템에서 수행될 수 있음을 $P_{i}'s$ 의미한다.
속도: ECOH 알고리즘은 SHA-1보다 약 천 배 느리다. 그러나 병렬화와 무반복 곱셈을 지향하는 데스크탑 하드웨어의 발전을 고려할 때, ECOH는 몇 년 안에 긴 메시지의 경우 SHA-1만큼 빠를 수 있다. 짧은 메시지의 경우 ECOH는 광범위한 표를 사용하지 않는 한 상대적으로 느리다.

ECOH의 보안

ECOH 해시함수는 구체적인 수학적 함수에 기초한다. 이들은 충돌 발견 문제가 알려져 있고 어려운 수학 문제(부분집합 문제)로 축소될 수 있도록 설계되었다. 충돌을 발견할 수 있다면 다항식 시간대에 난해하고 풀 수 없는 것으로 가정되는 기초 수학 문제를 풀 수 있다는 뜻이다. 이러한 속성을 가진 함수는 확실히 안전한 것으로 알려져 있으며, 나머지 해시함수들 사이에서 상당히 독특하다. 그럼에도 불구하고, 두 번째 사전 이미지(따라서 충돌)는 증거에 제시된 가정이 너무 강했기 때문에 나중에 발견되었다.

세마예프 합계 다항식

충돌 또는 두 번째 사전 이미지를 찾는 한 가지 방법은 Semaev Summation Polyomials를 해결하는 것이다. 주어진 타원곡선 E의 경우, $n$ $n$ 변수에 $n$ 대칭인 $f_{n}$ $f_{n}$ {\ $displaystyle f_{n}$ 가 $f_{n}$ 존재하며, $E$ $E$ 에서 합이 0인 점의 Absisae에서 평가했을 때 정확히 소멸되는 다항식이 존재하며, 지금까지 이 문제를 해결하기 위한 효율적인 알고리즘은 존재하지 않으며 가정되고 있다 $E$ o는 단단하다(그러나 NP-hard인 것으로 증명되지는 않음).

좀 더 형식적: $\mathbf {F}$ ${\$ 를) 유한한 필드로 하고 $\mathbf {F}$ , $E$ $E$ 은(는) 타원형 곡선으로 F ${\$ 와 $\mathbf {F}$ $O$ ${\displaystysty O}$ 의 계수를 갖는 Weierstrass 방정식이 무한의 $O$ 점으로 한다 $E$ . 만일에는<>존재하다는 것이 많은 제어 입출력을 갖는 다항식 fn(X1,…, XN){\displaystyle f_{n}(X_{1},\ldots ,X_{N})}이 존재한다;y1,…, yn{\displaystyle y_{1},\ldots}가(x1,1y)+에나+(), yn))O{\displaystyle(x_{1},y_{1})+\ldots+(x_ ,y_{n} 알려져 있다.{n $}}.y_{n}=O$ 이 다항식에는 각 변수에 도 $2^{n-2}$ $2^{n-2}$ - $2^{n-2}$ ${\$ 2 $^{n-2}}$ 개가 있다. 문제는 이 다항식을 찾는 것이다.

검증 가능한 보안 토론

ECOH에서 충돌을 찾는 문제는 서브셋 합계 문제와 비슷하다. 부분집합 문제를 해결하는 것은 별개의 로그 문제만큼 어렵다. 일반적으로 다항식 시간에는 이 작업을 수행할 수 없다고 가정한다. 그러나 상당히 느슨한 휴리스틱스는 더 구체적으로 계산에 포함된 매개변수 중 하나가 반드시 무작위일 필요는 없고 특정한 구조를 가지고 있다고 가정해야 한다. 이러한 느슨한 휴리스틱을 채택하는 경우 내부 ECOH 충돌 발견은 부분집합 문제의 한 예로 볼 수 있다.

두 번째 사전 이미지 공격은 일반화된 생일 공격의 형태로 존재한다.

두 번째 사전 이미지 공격

공격에 대한 설명: 이것은 바그너의 일반 생일 공격이다. ECOH-224와 ECOH-256은 2회¹⁴³, ECOH-384는 2회²⁰⁶, ECOH-512는 2회가²⁸⁷ 필요하다. 공격은 체크섬 블록을 고정된 값으로 설정하고 타원 곡선 지점에 대한 충돌 검색을 사용한다. 이 공격을 위해 우리는 메시지 M을 가지고 있고 같은 메시지를 해시하는 M'을 찾으려고 노력한다. 우리는 먼저 메시지 길이를 여섯 블록으로 나누었다. 그래서 $M'=(M_{1},M_{2},M_{3},M_{4},M_{5},M_{6})$ $M'=(M_{1},M_{2},M_{3},M_{4},M_{5},M_{6})$ = $M'=(M_{1},M_{2},M_{3},M_{4},M_{5},M_{6})$ ( $M'=(M_{1},M_{2},M_{3},M_{4},M_{5},M_{6})$ 1, $M'=(M_{1},M_{2},M_{3},M_{4},M_{5},M_{6})$ M $M'=(M_{1},M_{2},M_{3},M_{4},M_{5},M_{6})$ , $M'=(M_{1},M_{2},M_{3},M_{4},M_{5},M_{6})$ 3, $M'=(M_{1},M_{2},M_{3},M_{4},M_{5},M_{6})$ $M'=(M_{1},M_{2},M_{3},M_{4},M_{5},M_{6})$ , $M'=(M_{1},M_{2},M_{3},M_{4},M_{5},M_{6})$ M $M'=(M_{1},M_{2},M_{3},M_{4},M_{5},M_{6})$ , $M'=(M_{1},M_{2},M_{3},M_{4},M_{5},M_{6})$ $M'=(M_{1},M_{2},M_{3},M_{4},M_{5},M_{6})$ ) ${\displaystyle M'=(M_{1},M_{2},M_{3},M_{4},M_{5},M_{6$ K를 자연수가 되게 하라. 우리는 $(M_{0},M_{1})$ ( $(M_{0},M_{1})$ $(M_{0},M_{1})$ , M $(M_{0},M_{1})$ ) $(M_{0},M_{1}$ 에 대해 K의 다른 번호를 $M_{2}$ 하고 $(M_{0},M_{1})$ M $M_{2}$ {\ $displaystyle M_{2$ }} $M_{2}:=M_{0}+M_{1}$ $M_{2}:=M_{0}+M_{1}$ 2 $M_{2}:=M_{0}+M_{1}$ := $M_{2}:=M_{0}+M_{1}$ 0 + $M_{2}:=M_{0}+M_{1}$ $M_{2}:=M_{0}+M_{1}$ {\ $displaystyle M_{$ 2}를 정의한다 $.$ $=M_{0}+M_{1}}$ . We compute the K corresponding elliptic curve points $P(M_{0},0)+P(M_{1},1)+P(M_{2},2)$ and store them in a list. 그런 다음 $(M_{3},M_{4})$ ( $(M_{3},M_{4})$ $(M_{3},M_{4})$ , $(M_{3},M_{4})$ M $(M_{3},M_{4})$ ) $(M_{3},M_{4}$ 에 대해 K 다른 랜덤 값을 선택하고 $(M_{3},M_{4})$ $M_{5}:=M_{3}+M_{4}$ $M_{5}:=M_{3}+M_{4}$ $M_{5}:=M_{3}+M_{4}$ $M_{5}:=M_{3}+M_{4}$ 3 $M_{5}:=M_{3}+M_{4}$ + $M_{5}:=M_{3}+M_{4}$ 4 ${\$ 를 정의한다. $=M_{3}+M_{4}}$ , we compute $Q-X_{1}-X_{2}-P(M_{3},3)-P(M_{4},4)-P(M_{5},5)$ , and store them in a second list. 대상 Q가 알려져 있다는 점에 유의하십시오. $X_{1}$ $X_{1}$ ${\$ }은(는) 우리가 고친 메시지의 길이에 따라서만 $X_{1}$ 달라진다. $X_{2}$ $X_{2}$ ${\$ 모든 메시지 블록의 길이와 XOR에 따라 $X_{2}$ 다르지만, 항상 0이 되도록 메시지 블록을 선택한다. 따라서 $X_{2}$ $X_{2}$ ${\$ }는 우리의 모든 시도를 위해 고정되어 있다 $X_{2}$ .

만약 K가 타원곡선의 점수의 제곱근보다 크면 우리는 두 리스트 사이에 하나의 충돌을 예상한다. This gives us a message $(M_{1},M_{2},M_{3},M_{4},M_{5},M_{6})$ with: $Q=\sum _{i=0}^{5}P(M_{i},i)+X_{1}+X_{2}$ This means that this message leads to the target value Q and thus to a se콘드 프리이미지, 그것이 문제였다. 여기서 우리가 해야 할 워크로드는 K 부분 해시 계산의 두 배다. 자세한 내용은 "타원 곡선 전용 해시(ECOH)에 대한 두 번째 사전 이미지 공격"을 참조하십시오.

실제 매개 변수:

ECOH-224와 ECOH-256은 타원 곡선 B-283을 사용하고, 곡선에는 약 2 $[\$ 2 $^{283}}}}$ 개의 $2^{283}$ 포인트가 있다. $K=2^{142}$ = $K=2^{142}$ $K=2^{142}$ ${\$ 복잡도 $K=2^{142}$ 2 $2^{143}$ ${\$ 을(를) 선택하여 공격을 받는다 $2^{143}$
ECOH-384는 타원 곡선 B-409를 사용하며, 곡선에는 약 $2^{409}$ $(\$ 스타일 $2^{409})$ 의 포인트가 $2^{409}$ 있다. $K=2^{205}$ = $K=2^{205}$ $K=2^{205}$ ${\$ 를 선택하면 복잡도 $2^{206}.$ $2^{206}.$ ${\displaystyle$ 2 $^{206}$ 의 공격이 발생한다 $K=2^{205}$ . $}$
ECOH-512는 타원 곡선 B-571을 사용하며, 곡선에는 약 2 $(\$ 스타일 $2^{571})$ 점이 있다 $2^{571}$ . $K=2^{286}$ = $K=2^{286}$ $K=2^{286}$ ${\$ 을 선택하면 복잡도 $2^{287}.$ $2^{287}.$ ${\displaystyle$ 2 $^{287}$ 의 $K=2^{{286}}$ 공격이 발생한다. $}$