SHA3 편집하기

[[파일:미국 국립표준기술연구소 글자.png|썸네일|300픽셀|'''[[미국 국립표준기술연구소]]'''(NIST)]]

'''SHA-3'''(Secure Hash Algorithm 3)란 [[SHA-1]]과 [[SHA-2]]를 대체하기 위해 [[미국 국립표준기술연구소]](NIST)가 2015년 8월 5일에 발표한 암호화 [[해시함수]]이다. 

== 개요 ==
기존의 방식과는 다르게 NIST([[미국 국립표준기술연구소]])가 직접 디자인한 것이 아니라 공개적인 방식을 통해 후보를 모집한 다음 함수 안정성을 분석하여 몇 차례에 걸쳐 후보를 걸러내어 선정하여 2012년 10월 2일 SHA-1과 SHA-2에서 파생되지 않아 알고리즘에 차이가 크며, 파생되지 않았기 때문에 SHA-2의 취약점을 가지지 않은 [[귀도 베르토니]](Guido Bertoni), [[조안 데먼]](Joan Daemen), [[질 반 아쉐]](Gilles Van Assche), [[마이클 피터스]](Michael Peeters)가 설계한 [[케착]](Keccak)을 SHA-3의 해시 알고리즘으로 선정하였다. 또한 스펀지 구조로 이루어져 있기 때문에 스펀지 함수라고도 불린다.<ref>〈[https://ko.wikipedia.org/wiki/SHA-3 SHA-3]〉, 《위키백과》</ref>

== 등장배경 ==
SHA-3은 2004 ~ 2005년부터 여러 [[암호 해시 알고리즘]]에 대한 공격이 시작되기 시작했다. 당시에 당장에 큰 문제는 없었지만 빠른 시일 내에 현재 사용하는 [[암호 해시 알고리즘]]이 무효화될 것을 고려하여 대비를 해둬야 했기 때문에 2006년 [[미국 국립표준기술연구소]](NIST)는 [[미국 국가안보국]](NSA)와 함께 해시 워크샵에서 공개 대회를 발표하였다.<ref>Roger A. Grimes | CSO, 〈[http://www.itworld.co.kr/opinion/108321 글로벌 칼럼 | 왜 SHA-3을 사용하지 않는가]〉, 《아이티월드》, 2018-02-23</ref> 준비가 끝난 공개 대회는 2008년 말까지 입학 허가서가 제출되었으며 [[케착]](Keccak)은 51명의 후보자 중 한 명으로 선택되어 2009년 7월에 14개 알고리즘이 2차 라운드까지 선발되었고, 2010년 12월에 마지막 라운드까지 진출 하여, 2012년 10월 2일에 최종 우승하여 SHA-3 표준안으로 선정되었다. 또한 2014년에 [[미국 국립표준기술연구소]](NIST)는 연방 정보 처리 표준(FIPS) 202 "SHA-3 표준: 순열 기반 해시와 확장 가능한 출력 기능" 초안을 발행했고, 2015년 8월 5일, [[미국 국립표준기술연구소]](NIST)가 SHA-3 암호화 해시함수 표준을 발표했다.<ref>"[https://csrc.nist.gov/projects/hash-functions/sha-3-project Hash Functions]", ''NIST'', 2017-01-04</ref>

== 특징 ==
SHA-3은 현재 [[SHA-2]]가 출력할 수 있는 메시지 다이제스트의 크기를 모두 출력할 수 있고 암호학적 해시 암수가 갖춰야 할 충돌 저항성, 역상 저항성, 제2역상 저항성을 모두 갖추고 있기 때문에 현재 [[SHA-2]]가 사용되고 있는 모든 곳에서 SHA-3를 바로 적용시키는 것이 가능하다.<ref name="위키피디아">"[https://en.wikipedia.org/wiki/SHA-3 SHA-3]", ''WIKIPEDIA''</ref>

=== 스펀지 구조 ===
SHA-3는 데이터가 스펀지에 '흡수'되는 스펀지 구조를 사용한다. 그 결과 데이터가 스펀지에 "스퀴드(squeezed)"된다. 흡수 단계에서는 메시지 블록이 XORED되어 주의 서브셋으로 되며, 그런 다음 순열 함수 <math>f</math>를 사용하여 전체로 변환된다. "스퀴즈(squeeze)"단계에서는 출력 블록을 상애 변환 함수 <math>f</math>와 교대로 상태 하위 집합에서 읽으며 쓰고 읽는 상태의 부분의 크기를 "레이트(rate)"(<math>r</math>로 표시)라고 하고, 입/출력으로 손대지 않은 부분의 크기를 "용량(capacity)"(<math>c</math>로 표시)이라고 한다. 이 능력은 계획의 보안을 결정하며, 최대 보안 수준은 용량의 절반의 크기를 가진다. 입력 비트 문자열 <math>N</math>, 패딩 함수 패드, 폭 <math>b</math>의 비트 블록, 속도 <math>r</math> 및 출력 길이 <math>d</math>에서 작동하는 순열 함수 <math>f</math>를 고려할 때, 용량 <math>c = b - r,</math> 스펀지 구조 <math>Z =</math> 스펀지<math>[f,pad,r](N,d),</math> 약간의 길이 <math>d</math>를 산출하는 스펀지 구조 <math>Z</math>는 다음과 같이 작용한다.<ref name="위키피디아"></ref>

[[파일:스펀지.png|오른쪽|450픽셀|썸네일|스펀지 암호]]
*예제
**패드 기능을 사용하여 입력 <math>N</math>을 패드하여 <math>r</math>로 분할할 수 있는 길이<math>(n = len(P)/r</math>이 정수<math>)</math>인 패딩 비트 문자열 <math>P</math>를 산출한다.
**<math>P</math>를 연속해서 <math>n</math>개의 비트 조각으로 <math>P_0, .... P_n-1</math>로 나눈다.
**상태 <math>S</math>를 <math>b</math> 0(제로) 비트의 문자열로 초기화한다.
**각 블록 <math>P_i</math>에 대해 입력값을 흡수한다.
***끝에 <math>c</math> 0(제로) 비트의 끈으로 Pi를 확장하고, 길이 <math>b</math> 중 하나를 산출한다.
***XOR that with <math>S</math>
**블록 순열 <math>f</math>를 결과에 적용하여 새로운 상태 <math>S</math>를 산출한다.
**<math>Z</math>를 빈 문자열로 초기화한다.
**<math>Z</math>의 길이가 <math>d</math>보다 작은 경우:
***<math>S</math>의 첫 번째 <math>R</math> 비트를 <math>Z</math>에 추가한다.
***<math>Z</math>가 여전히 <math>d</math>비트보다 작을 경우, <math>f</math>를 <math>S</math>에 적용하여 새로운 상태 <math>S</math>를 산출한다.
**<math>Z</math>를 <math>d</math>비트로 자른다.<ref name="위키피디아"></ref>

내부 상태 <math>S</math>가 <math>Z</math>로 출력되는 것 외에 <math>c</math>의 추가 정보 비트를 포함하고 있다는 사실은 [[머클-담고르드]](Merkle-Damgorrd) 구조에 기초한 SHA-2, SHA-1, MD5 및 기타 해시가 취약한 길이 연장 공격을 방지한다. SHA-3에서 상태 <math>S</math>는 비트 워드의 <math>(w=64), b = 5 \times \!\, 5 \times \!\, w = 5 \times \!\, 5 \times \!\, 64 = 1600</math> 비트의 <math>5 \times \!\, 5</math>의 배열로 구성된다. 또한 케착(Keccak)은 또한 2개의 작은 단어 크기(총 상태 25비트)에 대해 정의되는데, 소형 상태 크기는 암호화 공격을 테스트하는 데 사용할 수 있으며, 중간 상태 크기<math>(w = 8, 200</math>비트에서, <math>w = 32, 800</math>비트까지 사용<math>)</math>는 실용적이고 가벼운 애플리케이션에서 사용할 수 있다. SHA-3-224, SHA-3-256, SHA-334, SHA-3-512 인스턴스의 경우 <math>r</math>은 <math>d</math>보다 크므로, 짜임 단계에서는 추가적인 [[블록 퍼머]]가 필요 없으며, 상태의 선행 <math>d</math>비트는 원하는 [[해시]]이다. 그러나 SHAKE-128 및 SHAKE-256은 임의 출력 길이를 허용하기 때문에 최적의 [[비대칭 암호]]화 [[패딩]]과 같은 응용 프로그램에 유용하다.<ref name="위키피디아"></ref>

=== 패딩함수 ===
메시지를 <math>r</math>-bit [[블록]]으로 균등하게 나눌 수 있도록 [[패딩]]이 필요하다. SHA-3은 [[패딩]] 기능에서 [[패턴]] <math>10*1</math>을 사용하며, 1비트 다음에 0비트 이상(최대 <math>r-1</math>)과 최종 1비트가 요구된다. <math>r-1</math> 제로(0)비트의 최대 값은 마지막 [[메시지 블록]]이 <math>r-1</math>비트 길이일 때 발생하며 마지막 1비트 이전에 <math>r-1</math>의 제로(0)비트를 포함하는 초기 1비트 뒤에 또 다른 [[블록]]이 추가된다. 또한 <math>r</math>에 의해 이미 메시지 길이를 분할할 수 있는 경우에도 1비트 2개가 추가된다. 이 경우, 1비트를 포함하는 또 다른 블록이 메시지에 추가되며 <math>r-2</math>개의 제로(0)비트와 1비트도 추가된다. 이는 패딩과 같이 <math>r</math>에 의해 길이가 분할될 수 있는 메시지가 이러한 비트를 제거한 메시지와 같은 [[해시]]를 생성하지 않도록 하기 위해 필요한 과정이다.
* 처음에는 1비트를 필요로하므로 끝에 몇 개의 추가 0비트만 가진 다른 메시지를 동일한 [[해시]]로 생성하지 않는다.
* 메시지는 [[패딩]] 된 후에 <math>r</math>비트와 같아야 한다. 따라서 마지막 1비트의 위치는 다른 해시 변형(different hash variants)에 대해 보안 증명(security proof) 기능이 작동하기 위해 필요한 크기(rate) <math>r</math>을 멀티 레이트 패딩(multi-rate padding)으로 나타내며, 만약 [[패딩]]이 없다면, 동일한 [[메시지]]의 다른 해시 변형(different hash variants)의 자른 부분까지도 동일하게 나온다.<ref name="위키피디아"></ref>

=== 블록 순열 ===
SHA-3의 케착-f[1600](Keccak-f[1600])인 블록 변환 <math>f</math>는 XOR, AND, NOT를 사용하는 순열로, [[소프트웨어]]와 [[하드웨어]]에서 모두 쉽게 구현할 수 있도록 설계되었다. 이는 <math>w = 2^l</math>비트인 2개의 워드 크기의 모든 [[파워]]에 대해 정의된다. 
*주요 SHA-3 제출은 64비트 단어, <math>l = 6</math>을 사용한다. 상태는 <math>5 \times 5 \times w</math> 비트 배열로 간주할 수 있다. 리틀 엔디안 비트 번호 매기기 규칙과 행 주요 인덱싱을 사용하여 <math>a[i][j][k]</math>를 입력의 비트 <math>(5i + j) * w + k</math>로 한다. 즉, 전 행, <math>j</math> 열, <math>k</math> 비트를 선택한다. 
*인덱스 산술은 처음 2차원에 대해서는 모듈로 5로, 세 번째 치수에 대해서는 모듈로 <math>w</math>를 수행한다. 
*기본 블록 순열 기능은 다음과 같은 5단계의 <math>12 + 2l</math> 라운드로 구성된다.
* 1단계: θ
**<math>5w(320, when</math> <math>w = 64)</math> 5비트 컬럼의 패리티와 이를 정규 패턴으로 인접한 컬럼 2개로 계산한다. 정확히 말하면 <math>a[i][j] \leftarrow a[i][j][k] \oplus parity(a[0...4][j-1][k])</math> <math>\oplus</math> <math>parity(a[0...4][ j+1][k-1])</math>
* 2단계: <math>P</math>
**25개의 단어 각각을 다른 삼각형 번호 0, 1, 3, 6, 10, 15, .....로 회전시킨다. 정확히 말하면 <math>a[0][0]</math>은 회전하지 않으며, 모두 회전하지 않는다.<math>0 \le \!\, t < \!\, 24, a[i][j][k] \leftarrow a[i][j][k-(t+1)(t+2)/2], where {i \choose j} = \begin{Bmatrix} 3 & 2 \\ 1 & 0 \end{Bmatrix}^t {0 \choose 1}</math>.
* 3단계: <math>\pi \!\,</math>
**25개의 단어를 일정한 패턴으로 배치한다. <math>a[j][2i+3j] \leftarrow a[i][j]</math>.
* 4단계: <math>X</math>
**x ← x ⊕(¬y & z)를 사용하여 비트적으로 행을 결합한다. 정확히 말하면 <math>a[i][j][k] \leftarrow a[i][j][k] \oplus (\neg \!\,a[i][j+1][k]</math> & <math>a[i][j+2][k]])</math>이다. SHA-3에서 유일하게 비선형 연산이다.
* 5단계: <math>l</math>
**배타적이거나 둥근 상수로서 주의 한 단어로 되어 있다. 정확히 말하면, 라운드 <math>n</math>에서 <math>0 m \le \!\, l</math>의 경우 <math>a[0][0][2^m-1]</math>은 a도(a degree-8) 8 LFSR의 비트 <math>m + 7_n</math>으로 XORed이다. 이것은 다른 단계들에 의해 보존되는 대칭을 깨뜨린다.<ref name="위키피디아"></ref>

=== 속도와 안정성 ===
SHA-3는 높은 수준의 [[병렬 구조]]를 가지고 메모리 접근에 [[인터리빙]] 방식을 사용하기 때문에 효율성이 아주 좋다. SHA-3 Tree는 MD5보다 높은 보안 강도를 가지면서 더 좋은 효율성을 보여준다. 또한 Tree구조가 아니어도 현재 많이 사용하고 있는 SHA-2보다 안전하고 빠르다는 것을 확인할 수 있다. 현재 한국에서 지정하고 있는 [[해시 함수]]는 SHA-224, SHA-256, SHA-384, SHA-512로 향후 SHA-3 알고리즘으로 적용하여야 한다.<ref name="SHA-3 차이점">박기식 외, 〈[http://kiise.or.kr/e_journal/2014/11/JOK/pdf/03.pdf SHA-3 해시 함수 검정 프로그램과
16bit-UICC 용 SHA-3 구현]〉, 《정보과학회논문지 제41권 제11호(2014. 11)》, 2014-08-29</ref>

=== 최신 개발 현황 ===
2016년 SHA-3 기능과 [[케착]](Keccak) 알고리즘을 만든 팀은 Tree 해싱으로 인해 병렬 실행의 가용성을 이용하여 라운드를 더 빠르게 감소(12 ~ 14회까지 감소) 시켰다. 캥거루트벨(KangarooTwelve)과 마르수필라미(Marsupilami)도 14회로 감소. 이러한 기능은 작은 메시지 크기에 대해 병렬 해시(Parallel Hash)보다 빠르다는 것에 차이가 있다. 지금까지 12라운드에 가까운 어떤 것에 대해서도 실질적인 공격을 가하지 않았던 케착(Keccak)에 초점을 맞춘 엄청난 암호학적 노력에 의해 감소된 회전 수는 정당화되었고, 이러한 고속 알고리즘은 SHA-3의 일부가 아니며(나중에 개발된 것), 따라서 FIPS를 준수하지 않지만, 동일한 케착(keccak) 순열을 사용하고 12라운드 케착(Keccak)에 대한 공격이 없기 때문에 SHA-3 기능만큼은 안전하다고 평가. 
*[[캥거루트벨]](KangarooTwelve)은 128비트 유효 보안 수준을 보유하는 동시에 바이트당 0.55 사이클의 성능을 갖는다고 주장하는 케착(Keccak)의 고성능 감속형 버전이다. 이 알고리즘은 IETF RFC 초안이다. 
*캥거루트벨(KangarooTwelve)의 약간 수정 버전인 [[마르수필라미]](Marsupilami)는 케착(Keccak) 순열의 14 라운드를 사용하며 256비트의 유효 보안 수준을 갖고있다. 256비트 보안은 실제로 128비트 보안보다 유용하지 않지만 일부 표준에서는 필요로할 수 도 있다.<ref name="위키피디아"></ref>

=== 인스턴스(instance) ===
:{|class=wikitable width=800
|-
!align=center|종류
!align=center|출력 크기
!align=center|비율 = 블록 크기
!align=center|용량
!align=center|정의
!align=center|충돌
!align=center|프리이미지
!align=center|두 번째<br>프리이미지
|-
|align=left|SHA3-224(M)
|align=left|224
|align=left|1152
|align=left|448
|align=left|Keccak[448](M 01, 224)
|align=left|112
|align=left|224
|align=left|224
|-
|align=left|SHA3-256(M)
|align=left|256
|align=left|1088
|align=left|512
|align=left|Keccak[512](M 01, 256)
|align=left|128
|align=left|256
|align=left|256
|-
|align=left|SHA3-384(M)
|align=left|384
|align=left|832
|align=left|768
|align=left|Keccak[768](M 01, 384)
|align=left|192
|align=left|384
|align=left|384
|-
|align=left|SHAKE128(M, d)
|align=left|d
|align=left|1344
|align=left|256
|align=left|Keccak[256](M 1111, d)
|align=left|min(d | 2,128)
|align=left|≥min(d,128)
|align=left|min(d,128)
|-
|align=left|SHAKE256(M, d)
|align=left|d
|align=left|1088
|align=left|512
|align=left|Keccak[512](M 1111, d)
|align=left|min(d | 2,256)
|align=left|≥min(d,256)
|align=left|min(d,256)
|-
|}

== SHA2와의 차이점 ==
[[SHA-2]]는 현재 대한민국에서 지정한 표준 해시 알고리즘으로 다양한 분야에 널리 사용되고 있는 해시 함수이다. SHA-2의 구조는 크게 2가지로 나눌 수 있는데 [[전처리]](preprocessing)와 [[해시연산]](hash computation) 과정으로 나눌 수 있다. [[전처리]](preprocessing) 과정에서는 메시지 [[패딩]] 및 다음 단계에서 쓰일 값들을 초기화하는 역할을 하고 있고 Hash computation(해시 연산) 과정에서는 [[패딩]]된 메시지로부터 메시지 스케줄링 과정을 여러 번 반복하여 메시지 다이제스트를 얻는 역할을 한다. 따라서 환경에 따라 차이에 다름이 있을 수 있지만 평균적으로 SHA-3가 [[SHA-2]]보다 4배 정도 빠르다고 할 수 있고 어느 플랫폼에서도 좋은 효율을 보여주고 있다.<ref name="SHA-3 차이점"></ref>

{{각주}}

== 참고자료 ==
* 〈[https://ko.wikipedia.org/wiki/SHA-3 SHA-3]〉, 《위키백과》

== 같이 보기 ==
* [[SHA]]
* [[해시]]
* [[알고리즘]]
* [[암호]]
* [[암호화]]
* [[암호기술]]
* [[미국 국립표준기술연구소]]

{{암호 알고리즘|검토 필요}}
@@ 127번째 줄: / 127번째 줄: @@
 == 참고자료 ==
-*〈[https://ko.wikipedia.org/wiki/SHA-3 SHA-3]〉, 《위키백과》
+* 〈[https://ko.wikipedia.org/wiki/SHA-3 SHA-3]〉, 《위키백과》
-*Roger A. Grimes | CSO, 〈[http://www.itworld.co.kr/opinion/108321 글로벌 칼럼 | 왜 SHA-3을 사용하지 않는가]〉, 《아이티월드》, 2018-02-23
-*"[https://csrc.nist.gov/projects/hash-functions/sha-3-project Hash Functions]", ''NIST'', 2017-01-04
-*"[https://en.wikipedia.org/wiki/SHA-3 SHA-3]", ''WIKIPEDIA''
-*박기식 외, 〈[http://kiise.or.kr/e_journal/2014/11/JOK/pdf/03.pdf SHA-3 해시 함수 검정 프로그램과 16bit-UICC 용 SHA-3 구현]〉, 《정보과학회논문지 제41권 제11호(2014. 11)》, 2014-08-29
 == 같이 보기 ==