SHA-3

보안 해시 알고리즘
컨셉트
해시 함수, SHA, DSA
주요기준
SHA-0, SHA-1, SHA-2, SHA-3
v t

SHA-3
(케칵)

일반
디자이너	귀도 베르토니, 호안 데멘, 미차 ë 피터스, 질 반 아시체.
초간본	2016; 7년전(2016)
시리즈	(SHA-0), SHA-1, SHA-2, SHA-3
인증	FIPS PUB 202
세부 사항
다이제스트 사이즈	제멋대로의
구조.	스펀지 시공
스피드	Keccak-f[1600] + XORing 1024 비트를 위한 일반적인 x86-64 기반 시스템에서 12.6 cpb.[1] 이는 대략 SHA2-256에 해당합니다.
최고의 공개 암호 분석
Keccak-512에 대한 프리이미지 공격은 8라운드로 감소하여 2시간과511.5 2개의508 메모리가 필요합니다.[2] 전체 24라운드 Keccak-f[1600]에 대해 제로섬 구분자가 존재하지만 해시 함수 자체를[3] 공격하는 데 사용할 수는 없습니다.

SHA-3(Secure Hash Algorithm 3)은 NIST가 2015년 8월 5일에 발표한 Secure Hash Algorithm 제품군의 최신 멤버입니다.^[4][5][6] 비록 동일한 일련의 표준의 일부이지만, SHA-3는 내부적으로 SHA-1 및 SHA-2의 MD5와 유사한 구조와 다릅니다.

SHA-3는 광범위한 암호 원시 계열인 Keccak(/ˈk ɛt ʃæk/ 또는 ˈk ɛt ʃɑːk/)의 하위 집합으로, Guido Bertoni, Joan Daemen, Micha ë Peeters, 그리고 Gilles Van Assche가 라디오 개툰을 기반으로 설계했습니다. Keccak의 저자들은 스트림 암호, 인증된 암호화 시스템, 특정 아키텍처에서 더 빠른 해싱을 위한 트리 해싱 체계,^[9][10] AED 암호 키악과 케트제를 포함하여 NIST가 아직 표준화하지 않은 기능에 대한 추가적인 사용을 제안했습니다.^[11][12]

Keccak는 스폰지 구조라고 불리는 새로운 접근 방식에 기초를 두고 있습니다.^[13] 스폰지 구성은 광범위한 랜덤 함수 또는 랜덤 순열을 기반으로 하며, 임의의 양의 데이터를 입력(스폰지 용어로 흡수)하고 임의의 양의 데이터를 출력(스퀴징)하는 동시에 이전의 모든 입력에 대해 의사 랜덤 함수의 역할을 합니다. 이는 큰 유연성으로 이어집니다.

NIST는 현재 SHA-2를 철회하거나 개정된 Secure Hash Standard에서 제거할 계획이 없습니다.^{[needs update?]} SHA-3의 목적은 필요한 경우 현재 애플리케이션에서 SHA-2로 직접 대체할 수 있으며 NIST의 전체 해시 알고리즘 툴킷의 견고성을 크게 향상시키는 것입니다.^[14]

메시지 크기가 작은 경우 Keccak 알고리즘과 SHA-3 함수의 개발자는 매개 변수가 조정된 더 빠른 함수 캥거루 트웰브와 추가 오버헤드 없이 새로운 트리 해싱 모드를 사용할 것을 제안합니다.

역사

Keccak 알고리즘은 귀도 베르토니, 조안 데멘(Vincent Rijmen과 함께 리젠다엘 암호를 공동 설계한 사람), 미차 ë 피터스, 질 반 아슈의 작품입니다. 이것은 이전의 해쉬 함수 디자인인 PANMA와 RadioGatun에 기반을 두고 있습니다. PANMA는 1998년에 Daemen과 Craig Clapp에 의해 디자인되었습니다. PANMA의 후속인 Radio Gatun은 Daemen, Peeters, Van Assche에 의해 설계되었으며 2006년 NIST 해시 워크샵에서 발표되었습니다.^[15] 참조 구현 소스 코드는 CC0 웨이버를 통해 공용 도메인에 전용되었습니다.^[16]

2006년 NIST는 새로운 해시 표준인 SHA-3을 만들기 위해 NIST 해시 함수 경쟁을 조직하기 시작했습니다. SHA-2에 대한 유의미한 공격이 입증되지 않았기 때문에 SHA-3은 SHA-2를 대체할 것이 아닙니다. MD5, SHA-0 및 SHA-1에 대한 성공적인 공격으로 인해 ^[17][18]NIST는 다른 유사하지 않은 암호화 해시의 필요성을 인식했습니다. SHA-3가 되었습니다.

설정 기간을 거친 후, 2008년 말까지 입학 허가서를 제출할 예정이었습니다. Keccak는 51명의 후보 중 한 명으로 받아들여졌습니다. 2009년 7월, 2차에 14개의 알고리즘이 선정되었습니다. Keccak는 2010년 12월에 마지막 라운드에 진출했습니다.^[19]

대회 기간 동안 참가자들은 발견된 문제를 해결하기 위해 알고리즘을 "약하게" 사용할 수 있었습니다. Keccak에 변경된 내용은 다음과 같습니다.^[20][21]

• 보안에 대해 좀 더 보수적으로 하기 위해 라운드 수를 12 + ℓ에서 12 + 2 ℓ로 늘렸습니다.
• 메시지 패딩은 좀 더 복잡한 방식에서 아래에 설명된 간단한 101^* 패턴으로 변경되었습니다.
• 가장 가까운 거듭제곱인 2로 반올림하는 것이 아니라 보안 한도까지 요금을 인상했습니다.

2012년 10월 2일, Keccak는 이 대회의 우승자로 선정되었습니다.^[7]

2014년 NIST는 FIPS 202 "SHA-3 표준: 순열 기반 해시 및 확장 가능 출력 기능" 초안을 발표했습니다.^[22] FIPS 202는 2015년 8월 5일에 승인되었습니다.^[23]

2015년 8월 5일, NIST는 SHA-3가 해싱 표준이 되었다고 발표했습니다.^[24]

논란 약화

2013년 초 NIST는 SHA-3 표준에 대한 "용량", 즉 전체 강도 대 속도 파라미터에 대해 제출된 값과 비교하여 다른 값을 선택할 것이라고 발표했습니다.^[25][26] 변화로 인해 약간의 혼란이 발생했습니다.

해시 함수 경쟁은 적어도 SHA-2 인스턴스만큼 안전한 해시 함수를 요구했습니다. 즉, d-비트 출력은 충돌 공격에 대한 d/2-비트 저항성을 가져야 하며, d-비트 출력은 d-비트 출력에 대해 달성 가능한 최대치입니다. Keccak의 보안 증명은 "용량" c를 기반으로 조정 가능한 수준의 보안을 제공하여 충돌 및 초기 이미지 공격 모두에 대해 c/2비트 저항성을 제공합니다. 원래 경쟁 규칙을 충족시키기 위해 Keccak의 저자들은 c = 2d를 제안했습니다. 발표된 변경 사항은 모든 형태의 공격에 대해 동일한 d/2비트 보안을 적용하고 c = d를 표준화하는 것이었습니다. 이것은 반복할 때마다 추가 비트의 입력을 해시할 수 있도록 함으로써 Keccak의 속도를 높였을 것입니다. 그러나 해시 함수는 더 이상 SHA-2와 같은 역상 저항성을 가진 드롭인 대체물이 아니었을 것입니다. 이는 반으로 줄어들었을 것이기 때문에 양자 컴퓨팅의 발전에 취약하고, 이는 다시 한 번 반으로 줄어들 것입니다.^[27]

2013년 9월 Daniel J. Bernstein은 NIST 해시 포럼 메일링^[28] 목록에 SHA-3 사양에 포함되지 않고 기본 Keccak으로 제안된 576비트 용량으로 보안을 강화할 것을 제안했습니다.^[29] 이것은 적어도 SHA3-224와 SHA3-256에 그들의 SHA-2 이전과 동일한 역상 저항을 제공했을 것이지만, SHA3-384와 SHA3-512는 그들의 SHA-2 이전보다 역상 저항이 훨씬 적었을 것입니다. 9월 말, Keccak 팀은 이미 SHA-3 제안서에 c = 256을 옵션으로 설정하여 128비트 보안을 제안했다고 답변했습니다. 그들은 용량 감소가 정당하다고 생각했지만, 부정적인 반응을 고려하여 모든 경우에 대해 c = 512비트로 용량을 늘릴 것을 제안했습니다. 이는 256비트 보안 수준까지 이전 표준과 동일한 수준이지만 합리적인 효율성을 제공하지만 ^[31]SHA2-384 및 SHA2-512에서 제공하는 384-/512비트 프리이미지 저항은 제공하지 않습니다. 저자들은 "256비트 이상의 보안 강도 수준을 주장하거나 의존하는 것은 의미가 없다"고 말했습니다.

2013년 10월 초, Bruce Schneier는 NIST의 결정이 알고리즘 수용에 미칠 수 있는 해로운 영향을 근거로 다음과 같이 비판했습니다.

공기에 대한 불신이 너무 많습니다. NIST는 아무도 믿지 않고 아무도 사용하지 않는 알고리즘을 게시할 위험이 있습니다(^[32]강제된 알고리즘 제외).

그는 이후 다음과 같이 말하면서 이전의 성명을 철회했습니다.

NIST가 알고리즘에 대해 "내부 변경"을 했다고 적었을 때 제가 말한 것을 놓쳤습니다. 그건 제가 좀 엉성했어요. Keccak 순열은 변하지 않습니다. NIST가 제안한 것은 성능의 이름으로 해시 함수의 용량을 줄이는 것이었습니다. Keccak의 좋은 특징 중 하나는 튜닝성이 높다는 것입니다.^[32]

암호학자이자 독립 소프트웨어 개발 회사의 수석 개발자인 Paul Crowley는 Keccak은 조정 가능해야 하며 하나의 프리미티브 내에서 보안 수준이 다를 이유가 없다고 말하며 이번 결정에 대한 지지를 표명했습니다. 그는 또한 다음과 같이 덧붙였습니다.

네, 진입자에 대해 일정 수준의 보안을 요구했다가 다른 표준을 발표하게 된 것은 경쟁에 조금 아쉽습니다. 하지만 지금은 대회를 다시 여는 것 외에는 그것을 고치기 위해 할 수 있는 일이 없습니다. 그들에게 그들의 실수를 고수하라고 요구하는 것은 누구에게도 상황을 개선시키지 않습니다.^[33]

NIST의 SHA-3 제안이 대회에 제출된 참조 코드를 사용하여 테스트 벡터를 생성할 수 있는 Keccak 패밀리의 하위 집합이라고 명시하면서, 원래 팀에 의해 정리된 Keccak에 내부 변경이 있었을 수 있다는 혼란이 있었습니다. 그리고 이 제안은 NIST 해시 팀과 그들 사이의 일련의 논의의 결과였습니다.^[34]

이러한 논란에 대응하여 2013년 11월 NIST의 John Kelsey는 모든 SHA-2 드롭인 교체 사례에 대해 원래의 c=2d 제안으로 돌아갈 것을 제안했습니다. 복귀는 후속^[36] 초안과 최종 발표에서 확인되었습니다.^[4]

설계.

SHA-3는 스폰지 ^[13]구조를 사용하여 데이터가 스폰지에 "흡수"되면 결과가 "퀴즈"됩니다. 흡수 단계에서 메시지 블록은 상태의 부분 집합으로 XOR되며, 그런 다음 순열 $함수{\displaystyle }$ f ${\displaystyle f}$를 사용하여 전체적으로 변환됩니다$.$ $({\displaystyle$ f$}$를 순열이라고 부르는 것은 혼란스러울 수 있습니다. 기술적으로 상태 공간의 순열이므로 2 ${\displaystyle {1600}^{}}$ ≈ 4.4 ⋅ ${\displaystyle {10}^{}}$ $481 {\displaystyle$ 2$^{1600}\약$ 4$.$4\cdot 10^{481} 요소가 있는 집합의 순열이지만 상태 벡터의 비트를 순열하는 것 이상입니다.) "스퀴즈" 단계에서 출력 블록은 상태 변환 함수 $f{\displaystyle }$ ${\displaystyle f}$와 교대로 동일한 상태 하위 집합에서 읽힙니다$.$ 쓰고 읽는 상태 부분의 크기를 "레이트"($r{\displaystyle }$ ${\display r}$로 표시)라고 하고,$$ 입력/출력에 의해 손상되지 않은 부분의 $크기$를 "용량$"($c {\$display style$c}로 표시)이라고 합니다.$$ 용량에 따라 체계의 보안이 결정됩니다. 최대 보안 수준은 용량의 절반입니다.

Given an input bit string ${\displaystyle N}$, a padding function ${\displaystyle pad}$, a permutation function ${\displaystyle f}$ that operates on bit blocks of width ${\displaystyle b}$, a rate ${\displaystyle r}$ and an output length ${\displaystyle d}$, we have capacity ${\displaystyle c=b-r}$ and the sponge construction ${\displaystyle Z={\text{sponge}}[f,pad,r](N,d)}$, yielding a bit string ${\displaystyle Z}$ of length ${\displaystyle d}$, works as follows:^{[5]: 18}

• 패드 함수를 사용하여 입력 N을 패드하여 $길이$를 r ${\display r}$로 나눈 패딩된 비트열 P를 생성합니다($n$ = ${\displaystyle \mathrm{len}}$( P$$) / r {\display n = {\text{len}}(P)/r}가 정수임).
• P를_n−1 연속된 n개의 r비트 조각으로 분할₀ P, ..., P
• 상태 S를 b 0 비트의 문자열로 초기화합니다.
• 각 블록 P에 대해 입력을 상태로 흡수합니다_i.
  • 끝에서 P를_i c 0비트의 문자열로 확장하여 길이 b 중 하나를 산출합니다.
  • XOR S가 있는 경우
  • 결과에 블록 순열 f를 적용하여 새로운 상태 S를 산출합니다.
• Z를 빈 문자열로 초기화합니다.
• Z의 길이가 d보다 작은 경우:
  • S의 첫 번째 비트를 Z에 추가합니다.
  • Z의 길이가 여전히 d비트보다 작으면, f를 S에 적용하여 새로운 상태 S를 산출합니다.
• Z를 d비트로 자르기

내부 상태 S가 Z에 출력되는 것 외에 추가적인 비트의 정보를 포함한다는 사실은 Merkle-Damgórd 구조에 기반한 SHA-2, SHA-1, MD5 및 기타 해시가 취약한 길이 확장 공격을 방지합니다.

SHA-3에서 상태 S는 w = 64, b = 5 × 5 × w = 5 × 5 × 64 = 1600 비트의 w-비트 워드의 5 × 5 배열로 구성됩니다. Keccak는 또한 1비트(총 상태 25비트) 이하의 더 작은 2개의 단어 크기에 대해서도 정의됩니다. 작은 상태 크기는 암호 분석 공격을 테스트하는 데 사용할 수 있으며, 중간 상태 크기(w = 8, 200비트, w = 32, 800비트)는 실용적이고 가벼운 응용 분야에서 사용할 수 있습니다.

SHA3-224, SHA3-256, SHA3-384 및 SHA3-512 인스턴스의 경우 r이 d보다 크므로 스퀴징 단계에서 추가적인 블록 순열이 필요하지 않으며 상태의 선두에 있는 d 비트가 원하는 해시입니다. 그러나 SHAKE128 및 SHAKE256은 임의의 출력 길이를 허용하므로 최적의 비대칭 암호 패딩과 같은 응용 분야에서 유용합니다.

패딩

메시지가 r비트 블록으로 균등하게 분할될 수 있도록 하려면 패딩이 필요합니다. SHA-3는 패딩 함수에서 패턴 101을^* 사용합니다: 1 비트, 0 이상의 0 비트(최대 r - 1) 및 최종 1 비트.

최대 r - 1 0 비트는 마지막 메시지 블록의 길이가 r - 1 비트일 때 발생합니다. 그런 다음 첫 번째 1비트 뒤에 다른 블록이 추가되며 마지막 1비트 앞에 r - 1 0비트가 포함됩니다.

2개의 1비트는 메시지의 길이가 이미 r로 나누어져 있어도 추가됩니다.^{[5]: 5.1} 이 경우 다른 블록이 메시지에 추가되며, 1비트가 포함된 다음 r - 2 0비트의 블록과 1비트가 추가됩니다. 이것은 패딩처럼 보이는 것을 렌더링하여 길이를 분할할 수 있는 메시지가 해당 비트를 제거한 메시지와 동일한 해시를 생성하지 않도록 하기 위해 필요합니다.

첫 번째 1비트가 필요하므로 마지막에 몇 개의 추가 0비트만 다른 메시지는 동일한 해시를 생성하지 않습니다.

최종 1비트의 위치는 사용된 rater(멀티 레이트 패딩)을 나타냅니다. 이는 보안 증명이 서로 다른 해시 변형에 대해 작동하는 데 필요합니다. 그것이 없으면, 같은 짧은 메시지의 다른 해시 변형은 잘라내기까지 동일할 것입니다.

블록 순열

SHA-3에 대한 Keccak-f[1600]인 블록 변환 f는 XOR, AND, NOT 연산을 사용하는 치환으로 소프트웨어와 하드웨어 모두에서 쉽게 구현할 수 있도록 설계되었습니다.

w = 2비트의 모든 단어 크기에 대해 정의됩니다. 메인 SHA-3 서브미션은 64비트 워드인 ℓ = 6을 사용합니다.

상태는 비트의 5×5×w 배열이라고 볼 수 있습니다. a[i][j][k] 비트 (5i + j) × w + k 입력을 little-endian bit numbering convention과 행-메이저 인덱싱을 사용합니다. 즉, i는 행, j 열 및 k 비트를 선택합니다.

인덱스 산술은 처음 두 차원에 대해 모듈로 5를 수행하고 세 번째 차원에 대해 모듈로를 수행합니다.

기본 블록 순열 함수는 다음과 같은 5단계의 12 + 2 ℓ 라운드로 구성됩니다.

θ (세타)

5w(320, w = 64인 경우) 5비트 열의 패리티와 배타적인 열의 패리티를 각각 정규 패턴으로 계산합니다. To be precise, a[i][ j][k] ← a[i][ j][k] ⊕ parity(a[0...4][j-1][k]) ⊕ parity(a[0...4][j+1][k−1])

ρ (rho)

각각의 25개 단어를 다른 삼각수 0, 1, 3, 6, 10, 15, ...만큼 비트와이즈로 회전시킵니다. 정확하게 말하면, a[0][0]은 회전하지 않으며, 모든 0≤ t < 24에 대하여 a[i][j][k] ← a[i][j][j][j][j][k][j][k][j][k]][] = (321 0) t (0 )displaystyle {\begin{pmatrix}i\j\end{pmatrix}}={\begin{pmatrix}3&2\1&0\end{pmatrix}^{t}{\begin{pmatrix}0\1\end{pmatrix}}}.

π (pi)

25개 단어를 고정된 패턴으로 순열합니다. a[3i+2j][i] ← a[i][j].

χ (치)

x ← x ⊕( ¬리 & z)를 사용하여 행을 따라 비트 단위로 결합합니다. To be precise, a[i][ j][k] ← a[i][ j][k] ⊕ (¬a[i][ j+1][k] & a[i][ j+2][k]). 이것은 SHA-3의 유일한 비선형 연산입니다.

ι (iota)

배타적 - 또는 국가의 한 단어로 된 원 상수. 정확하게 말하면, 라운드 n에서, 0 ≤ m ≤ ℓ에 대하여, a[0][0][2-1]은 도-8 LFSR 시퀀스의 비트 m + 7n으로 XOR됩니다. 이것은 다른 단계에 의해 보존되는 대칭성을 깨뜨립니다.

스피드

긴 메시지의 SHA-3 해싱 속도는 b = 1600 비트의 연산인 확장된 P로 f = Keccak-f[1600] 및 XORing S의 계산에 의해 지배됩니다. 그러나 확장된 P의 마지막 c비트는 어쨌든 0이고, 0이 있는 XOR은 NOP이므로 r비트에 대해서만 XOR 연산을 수행하면 충분합니다(SHA3-224의 경우 r = 1600 - 2 × 224 = 1152 비트, SHA3-256의 경우 1088 비트, SHA3-384의 경우 832 비트, SHA3-512의 경우 576 비트). r이 낮을수록(그리고 반대로 c = b - r = 1600 - r이 높을수록), 해시는 덜 효율적이지만, 계산 비용이 많이 드는 f의 각 적용 전에 메시지의 더 적은 비트를 상태(빠른 연산)로 XOR할 수 있기 때문에 더 안전해집니다. 저자들은 Keccak-f[1600] + XORing 1024 비트의 소프트웨어 구현에 대해 다음과 같은 속도를 보고하며,^[1] 이는 대략 SHA3-256에 해당합니다.

• 57.4 cpbon IA-32, Intel^[37] Pentium 3
• 41 cpbon IA-32+MMX, Intel Pentium 3
• 20 cpbon IA-32+SSE, Intel Core 2 Duo 또는 AMD Athlon 64
• 일반적인 x86-64 기반 시스템에서 12.6 cpb
• 6–7 cpb on IA-64^[1]

x86-64의 정확한 SHA3-256의 경우 Bernstein은 CPU에 따라 11.7–12.25 cpb를 측정합니다.^{[38]: 7} SHA-3는 Keccak 기능을 더 빠르게 계산하기 위한 명령어가 없는 명령어 세트 아키텍처(CPU)에서 느리다는 비판을 받아 왔습니다. SHA2-512는 SHA3-512보다 두 배 이상 빠릅니다. 그리고 SHA-1은 3.2GHz의 Intel Skylake 프로세서보다 3배 이상 빠릅니다.^[39] 저자들은 이러한 비판에 대해 SHA3-256과 SHA3-512 대신에 SHAKE128과 SHAKE256을 사용할 것을 제안함으로써 (그러나 충돌 저항성을 유지하면서) 역상 저항을 절반으로 줄이는 대신에. 이를 통해 성능은 SHA2-256 및 SHA2-512와 동등합니다.

그러나 하드웨어 구현에서 SHA-3는 다른 모든 최종 후보들보다 현저하게 ^[40]빠르며, 또한 SHA-2 및 SHA-1보다 빠릅니다.^[39]

2018년 현재, ARM의 ARMv8과^[41] IBM의 s390x 아키텍처에는 Keccak 알고리즘을 더 빠르게 실행할 수 있는 특별한 명령어가 포함되어 있습니다.

인스턴스

NIST 표준은 메시지 M과 출력 길이 d에 대해 다음 인스턴스를 정의합니다.^{[5]: 20, 23}

사례	산출량 크기의	레이터 = 블록크기	용량 c	정의.	에 대한 약간의 저항력으로 구성된 보안 강도
					충돌	프리이미지	2차 전상
SHA3-224(M)	224	1152	448	케칵[448](M01,224)	112	224	224
SHA3-256(M)	256	1088	512	케칵[512](M01,256)	128	256	256
SHA3-384(M)	384	832	768	Keccak[768](M 01, 384)	192	384	384
SHA3-512(M)	512	576	1024	케칵[1024](M01,512)	256	512	512
SHAKE128(M,d)	d	1344	256	케칵[256](M1111,d)	min(d/2,128)	≥min(d,128)	min(d,128)
SHAKE256(M,d)	d	1088	512	Keccak[512](M 1111, d)	min(d/2,256)	≥min(d,256)	min(d,256)

정의는 다음과 같습니다.

• Keccak[c](N, d) = sponge[Keccak-f[1600], pad10^*1, r](N, d)^{[5]: 20}
• Keccak-f[1600] = Keccak-p[1600, 24]^{[5]: 17}
• c는 capacity 입니다.
• r은 비율 = 1600 - c입니다.
• N은 입력 비트 문자열입니다.

SHA-3 인스턴스는 동일한 보안 속성을 갖도록 설계된 SHA-2를 대체하는 것입니다.

SHAKE는 스폰지에서 요청한 만큼의 비트를 생성하므로 확장 가능 출력 함수(XOF)가 됩니다. 예를 들어, SHAKE128(M, 256)은 128비트 보안 강도를 갖는 256자 비트스트림을 갖는 해시 함수로 사용될 수 있습니다. 임의로 큰 길이를 의사 난수 생성기로 사용할 수 있습니다. 또는 SHAKE256(M, 128)을 128비트 길이와 128비트 저항을 갖는 해시 함수로 사용할 수 있습니다.^[5]

모든 인스턴스는 일부 비트를 메시지에 추가하며, 그 중 가장 오른쪽은 도메인 분리 접미사를 나타냅니다. 이것의 목적은 Keccak 해시 함수의 다른 응용 프로그램에 대해 동일한 해시 출력을 생성하는 메시지를 구성할 수 없도록 하는 것입니다. 도메인 구분 접미사는 다음과 같습니다.^[5][42]

접미사	의미.
...0	장래에 사용할 수 있도록 예약된
01	SHA-3
...11	RawSHAKE
1111	흔들다

추가 인스턴스

2016년 12월 NIST는 새로운 문서인 NIST SP.800-185를 발표하고 추가 ^[43]SHA-3 파생 기능을 설명했습니다.

사례	묘사
cSHAKE128(X, L, N, S)	사용자 지정 매개 변수를 통한 명시적 도메인 분리를 지원하는 SHAKE 버전입니다.
cSHAKE256(X, L, N, S)
KMAC128(K, X, L, S)	Keccak 기반의 키드 해시 함수입니다. 일반 해시 함수로 키 없이도 사용할 수 있습니다.
KMAC256(K, X, L, S)
KMACXOF128(K, X, L, S)
KMACXOF256(K, X, L, S)
TupleHash128(X, L, S)	현의 튜플을 해싱하기 위한 기능입니다. 이 기능의 출력은 입력 문자열의 내용과 순서에 따라 달라집니다.
TupleHash256(X, L, S)
TupleHashXOF128(X, L, S)
TupleHashXOF256(X, L, S)
병렬해시128(X,B,L,S)	더 빠른 해시를 위해 현대 프로세서의 병렬성을 활용하도록 설계된 기능입니다. 캥거루 트웰브와 달리 축소 라운드 케칵을 사용하지 않습니다.
병렬해시256(X,B,L,S)
병렬 해시 XOF128(X, B, L, S)
병렬해시XOF256(X,B,L,S)

• X는 주 입력 비트열입니다. 0을 포함하여 모든 길이일 수 있습니다.

• L은 요청된 출력 길이를 비트 단위로 나타내는 정수입니다.

• N은 함수 이름 비트 문자열로, NIST에서 cSHAKE를 기반으로 함수를 정의하는 데 사용됩니다. cSHAKE 이외의 기능을 원하지 않을 때는 N이 빈 문자열로 설정됩니다.

• S는 사용자 지정 비트 문자열입니다. 사용자는 이 문자열을 선택하여 함수의 변형을 정의합니다. 사용자 지정을 원하지 않으면 S가 빈 문자열로 설정됩니다.

• K는 0을 포함한 모든 길이의 키 비트 문자열입니다.

• B는 병렬 해시의 블록 크기(바이트)입니다. 0 < B < 2와²⁰⁴⁰ 같은 임의의 정수일 수 있습니다.

후대의 발전

캥거루 트웰브

캥거루 트웰브

일반
디자이너	귀도 베르토니, 호안 데멘, 미차 ë 피테르스, 질 반 아시체, 로니 반 키어, 베노 î트 비기에
초간본	2016년 8월 10일; 7년전(2016-08-10)
에서 파생됨	케칵
세부 사항
다이제스트 사이즈	제멋대로의
구조.	캥거루 호핑과 함께 스폰지 시공과 나무 해싱
라운즈	12
스피드	0.51 cpb on SkylakeX with AVX-512[44]
최고의 공개 암호 분석
Keccak의 것과 같습니다.

2016년 SHA-3 기능과 Keccak 알고리즘을 만든 팀과 동일한 팀은 나무 해싱을 사용하기 때문에 병렬 실행이 가능한 것을 이용할 수 있는 더 빠른 축소 라운드(SHA-3의 24라운드에서 12라운드와 14라운드로 축소) 대안을 도입했습니다.^[45] 캥거루 트웰브와 마르수필라미 포틴.

이 기능들은 병렬화와 관련하여 FIPS 표준화된 Keccak 기반 병렬화 가능 해시 함수인 ParallelHash와 달리 메시지 크기가 작은 경우 ParallelHash보다 빠릅니다.

라운드 수 감소는 12라운드 Keccak에 가까운 어떤 것에도 실질적인 공격을 하지 않은 Keccak에 초점을 맞춘 엄청난 암호 분석 노력으로 인해 정당화됩니다. 이러한 고속 알고리즘은 SHA-3의 일부가 아니므로 FIPS를 준수하지 않습니다. 그러나 동일한 Keccak 순열을 사용하기 때문에 SHA-3에 대한 공격이 12라운드로 감소하지 않는 한 안전합니다.^[45]

캥거루 트웰브는 스카이레이크 CPU에서 바이트당 0.55 사이클만큼 높은 성능을 가지면서 128비트의 보안을^[46] 갖는 Keccak의 고성능 축소 라운드(24라운드에서 12라운드) 버전입니다.^[47] 이 알고리즘은 IETF RFC 초안입니다.^[48]

캥거루 트웰브의 약간의 변형인 마르수필라미 포틴(Marsupilami F14teen)은 14라운드의 케칵 순열을 사용하며 256비트의 보안을 주장합니다. 256비트 보안은 128비트 보안보다 실제로 더 유용하지는 않지만 일부 표준에서는 필요할 수 있습니다.^[46] 128비트는 현재 하드웨어에 대한 무차별 공격을 물리치기에 이미 충분하므로 256비트 보안이 실용적인 가치를 더하지는 않습니다. 사용자가 고전 컴퓨터 속도의 상당한 발전에 대해 걱정하지 않는 한. 양자 컴퓨터에 대한 저항력은 아래를 참조하십시오.

캥거루 12 및 마르수필라미 14는 SHAKE와 유사한 확장 가능 출력 기능이므로 출력 길이가 다른 공통 메시지에 대해 밀접하게 관련된 출력을 생성합니다(출력이 길수록 짧은 출력의 확장입니다). 이러한 속성은 SHA-3 또는 ParallelHash(XOF 변형 제외)와 같은 해시 함수에서는 나타나지 않습니다.^[5]

파팔레 건설

2016년, Keccak 팀은 Farfalle construction이라는 다른 구성과 Keccak-p 치환을 사용하는 Farfalle의 인스턴스인 Kravatte와 ^[49]두 개의 인증된 암호화 알고리즘 Kravatte-SANE 및 Kravatte-SANSE를^[50] 출시했습니다.

사쿠라나무해싱

RawSHAKE는 아직 표준화되지 않은 트리 해싱을 위한 사쿠라 코딩의 기초가 됩니다. Sakura는 나무 모양에 따라 생성된 다른 접미사인 SHAKE에 해당하는 단일 노드에 1111의 접미사를 사용합니다.^{[42]: 16}

양자 공격에 대한 보안

$양자$ 컴퓨터는 구조화된 ${\displaystyle 프리이미지}$ ${\displaystyle {공격}^{}}$을$$2d = 2d / 2{\displaystyle {\sqrt {2^{d}}=2^{d/2}}에서 수행할 수 있는 일반적인 결과(Grover의 알고리즘)가 있는 반면, 고전적인 브루트 포스 공격에는 2가 필요합니다. 구조화된 역상 공격은 두 번째 역상 공격을^[27] 의미하며, 따라서 충돌 공격을 의미합니다. 양자 컴퓨터는 생일 공격을 수행하여 충돌 저항을 ${\displaystyle \text{exception 25:}}$ 3 = ${\displaystyle {2d}^{}}$/ 3 {\displaystyle {\sqrt[{3}]{2^{d}}=2^{d/3}}(비록 논란이 있지만)에서 깨질 수 있습니다. 최대 강도가 $c{\displaystyle /2\mathrm{}}$ ${\displaystyle c/2}$일 수 있다는 점에 주목하면$,$ 이는 SHA-3의 양자 보안에 대한 다음과^[53] 같은 상한을 제공합니다.

사례	에 대한 약간의 저항력으로 구성된 보안 강도
	충돌 (브라사드 등)	충돌 (번스타인)	프리이미지	2차 전상
SHA3-224(M)	742⁄3	112	112	112
SHA3-256(M)	851⁄3	128	128	128
SHA3-384(M)	128	192	192	192
SHA3-512(M)	1702⁄3	256	256	256
SHAKE128(M,d)	min(d/3,128)	min(d/2,128)	≥min(d/2,128)	min(d/2,128)
SHAKE256(M,d)	min(d/3,256)	min(d/2,256)	≥min(d/2,256)	min(d/2,256)

SHA-2에 의해 사용된 Merkle-Damgórd 구조가 붕괴되고 결과적으로 양자 충돌에 저항하는 것으로 나타났지만,^[54] SHA-3에 의해 사용된 스폰지 구조의 경우, 저자는 블록 함수 f가 효율적으로 가역적이지 않은 경우에만 증거를 제공합니다. 그러나 Keccak-f[1600]는 효율적으로 가역적입니다. 그래서 그들의 증거는 적용되지 않습니다.^{[55][original research]}

SHA-3 변이체의 예

다음 해시 값은 NIST.gov 에서 가져온 것입니다.

SHA3-224("") 6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7 SHA3-256("") a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434a SHA3-384("") 0c63a75b845e4f7d01107d852e4c2485c51a50aaaa94fc61995e71bbee983a2ac3713831264adb47fb6bd1e058d5f004 SHA3-512("") a69f73cca23a9ac5c8b567dc185a756e97c982164fe25859e0d1dcc1475c80a615b2123af1f5f94c11e3e9402c3ac558f500199d95b6d3e301758586281dcd26 SHAKE128("", 256) 7f9c2ba4e88f827d616045507605853ed73b8093f6efbc88eb1a6eacfa66ef26 SHAKE256("", 512) 46b9dd2b0ba88d13233b3feb743eeb243fcd52ea62b81b82b50c27646ed5762fd75dc4ddd8c0f200cb05019d67b592f6fc821c49479ab48640292eacb3b7c4be 

단일 비트를 변경하면 출력의 각 비트가 50% 확률로 변경되어 눈사태 효과가 나타납니다.

SHAKE128("The quick brown fox jumps over the lazy dog", 256) f4202e3c5852f9182a0430fd8144f0a74b95e7417ecae17db0f8cfeed0e3e66e SHAKE128("The quick brown fox jumps over the lazy dof", 256) 853f4538be0db9621a6cea659a06c1107b1f83f02b13d18297bd39d7411cf10c 

SHA 기능 비교

아래 표에서 내부 상태는 다음 블록으로 이월되는 비트 수를 의미합니다.

SHA 기능 비교

• 보다
• 말해라.

알고리즘과 변형		출력크기 (비트)	내부의 상태 크기 (비트)	블록크기 (비트)	라운즈	오퍼레이션스	충돌 공격에 대한 보안 (비트)	길이 확장 공격에 대한 보안 (비트)	Skylake에서의 성능(중앙값 cpb)[57]		초간본
									긴 메시지	8바이트
MD5(참고)		128	128 (4 × 32)	512	4 (각 라운드 16회 운영)	And, Xor, Or, Rot, Add (mod 232)	≤ 18 (충돌 발견)[58]	0	4.99	55.00	1992
SHA-0		160	160 (5 × 32)	512	80	And, Xor, Or, Rot, Add (mod 232)	< 34 (충돌 발견)	0	≈ SHA-1	≈ SHA-1	1993
SHA-1							< 63 (충돌 발견)[59]		3.47	52.00	1995
SHA-2	SHA-224 SHA-256	224 256	256 (8 × 32)	512	64	그리고, Xor, or, Rot, Shr, Add(모드32 2)	112 128	32 0	7.62 7.63	84.50 85.25	2004 2001
	SHA-384	384	512 (8 × 64)	1024	80	그리고, Xor, or, Rot, Shr, Add(모드64 2)	192	128	5.12	135.75	2001
	SHA-512	512					256	0[60]	5.06	135.50	2001
	SHA-512/224 SHA-512/256	224 256					112 128	288 256	≈ SHA-384	≈ SHA-384	2012
SHA-3	SHA3-224 SHA3-256 SHA3-384 SHA3-512	224 256 384 512	1600 (5 × 5 × 64)	1152 1088 832 576	24[61]	그리고, Xor, Rot, Not	112 128 192 256	448 512 768 1024	8.12 8.59 11.06 15.88	154.25 155.50 164.00 164.00	2015
	SHAKE128 SHAKE256	d (arbitrary) d (arbitrary)		1344 1088			min(d/2,128) min(d/2,256)	256 512	7.08 8.59	155.25 155.50

SHA3-256의 AVX-512VL(예: OpenSSL에서 Skylake-X CPU에서 실행됨)을 사용한 최적화된 구현은 큰 메시지의 경우 바이트당 약 6.4 사이클을 달성하고 ^[62]Skylake CPU에서 AVX2를 사용할 경우 바이트당 약 7.8 사이클을 달성합니다.^[63] 다른 x86, 파워 및 ARM CPU의 성능은 사용되는 지침에 따라 다르며 정확한 CPU 모델은 바이트당 약 8 ~ 15 사이클까지 ^[64][65][66]다양하며 일부 구형 x86 CPU는 바이트당 최대 25 ~ 40 사이클까지 다양합니다.^[67]

구현

아래는 SHA-3를 지원하는 암호학 라이브러리 목록입니다.

• 러스트즈 샤쓰리
• 식물
• 통통 튀는 성
• Crypto++
• Libgcrypt
• 네틀
• OpenSSL
• 울프SSL
• MIRACL 암호 SDK
• 골랑스 x/crypto/샤3
• 립케차크

하드웨어 가속

Apple A13 ARMv8 6코어 SoC CPU 코어는 ARMv8.2-SHA 암호 확장 세트의 특수 명령어(EOR3, RAX1, XAR, BCAX)를 사용하여 SHA-3(및 SHA-512)을 가속화할 수 있도록 지원합니다^[68].^[69]

일부 소프트웨어 라이브러리는 SHA-3의 사용을 가속화하기 위해 CPU의 벡터화 기능을 사용합니다. 예를 들어 Crypto++는 x86에서 SSE2를 사용하여 SHA3를 가속화할 ^[70]수 있으며 OpenSSL은 많은 x86 시스템에서도 MMX, AVX-512 또는 AVX-512VL을 사용할 수 있습니다.^[71] 또한 POWER8 CPU는 Power에 정의된 2x64비트 벡터 회전을 구현합니다.SHA-3 구현을 가속화할 수 있는 ISA 2.07.^[72] ARM에 대한 대부분의 구현은 스칼라 코드가 더 빠르기 때문에 네온 벡터 명령을 사용하지 않습니다. 그러나 ARM 구현은 SVE 및 SVE2 벡터 명령어를 사용하여 가속화할 수 있습니다. 예를 들어 Fujitsu A64FX CPU에서 사용할 수 있습니다.^[73]

IBM z/Architecture는 2017년부터 Message-Security-Assist Extension 6의 일부로 SHA-3을 지원합니다.^[74] 프로세서는 각 코어에 내장된 하드웨어 지원 엔진을 사용하여 KIMD 및 KLMD 명령을 통해 전체 SHA-3 및 SHAKE 알고리즘의 완전한 구현을 지원합니다.

프로토콜에서의 사용

• 이더리움 § 에테르

참고 항목

• Ethash – 또 다른 Keccak 기반 해시

참고문헌

외부 링크

• Keccak 웹사이트
• SHA-3 표준