SHA3

미국 국립표준기술연구소(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의 해시 알고리즘으로 선정하였다. 또한 스펀지 구조로 이루어져 있기 때문에 스펀지 함수라고도 불린다.

등장배경

SHA-3은 2004 ~ 2005년부터 여러 암호 해시 알고리즘에 대한 공격이 시작되기 시작했다. 당시에 당장에 큰 문제는 없었지만 빠른 시일 내에 현재 사용하는 암호 해시 알고리즘이 무효화될 것을 고려하여 대비를 해둬야 했기 때문에 2006년 미국 국립표준기술연구소(NIST)는 미국 국가안보국(NSA)와 함께 해시 워크샵에서 공개 대회를 발표하였다. 준비가 끝난 공개 대회는 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 암호화 해시함수 표준을 발표했다.

특징

SHA-3은 현재 SHA-2가 출력할 수 있는 메시지 다이제스트의 크기를 모두 출력할 수 있고 암호학적 해시 암수가 갖춰야 할 충돌 저항성, 역상 저항성, 제2역상 저항성을 모두 갖추고 있기 때문에 현재 SHA-2가 사용되고 있는 모든 곳에서 SHA-3를 바로 적용시키는 것이 가능하다.

스펀지 구조

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

스펀지 암호

• 예제
  • 패드 기능을 사용하여 입력 $N$을 패드하여 $r$로 분할할 수 있는 길이$(n=len(P)/r$이 정수$)$인 패딩 비트 문자열 $P$를 산출한다.
  • $P$를 연속해서 $n$개의 비트 조각으로 $P_{0},....P_{n}-1$로 나눈다.
  • 상태 $S$를 $b$ 0(제로) 비트의 문자열로 초기화한다.
  • 각 블록 $P_{i}$에 대해 입력값을 흡수한다.
    • 끝에 $c$ 0(제로) 비트의 끈으로 Pi를 확장하고, 길이 $b$ 중 하나를 산출한다.
    • XOR that with $S$
  • 블록 순열 $f$를 결과에 적용하여 새로운 상태 $S$를 산출한다.
  • $Z$를 빈 문자열로 초기화한다.
  • $Z$의 길이가 $d$보다 작은 경우:
    • $S$의 첫 번째 $R$ 비트를 $Z$에 추가한다.
    • $Z$가 여전히 $d$비트보다 작을 경우, $f$를 $S$에 적용하여 새로운 상태 $S$를 산출한다.
  • $Z$를 $d$비트로 자른다.

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

패딩함수

메시지를 $r$-bit 블록으로 균등하게 나눌 수 있도록 패딩이 필요하다. SHA-3은 패딩 기능에서 패턴 $10*1$을 사용하며, 1비트 다음에 0비트 이상(최대 $r-1$)과 최종 1비트가 요구된다. $r-1$ 제로(0)비트의 최대 값은 마지막 메시지 블록이 $r-1$비트 길이일 때 발생하며 마지막 1비트 이전에 $r-1$의 제로(0)비트를 포함하는 초기 1비트 뒤에 또 다른 블록이 추가된다. 또한 $r$에 의해 이미 메시지 길이를 분할할 수 있는 경우에도 1비트 2개가 추가된다. 이 경우, 1비트를 포함하는 또 다른 블록이 메시지에 추가되며 $r-2$개의 제로(0)비트와 1비트도 추가된다. 이는 패딩과 같이 $r$에 의해 길이가 분할될 수 있는 메시지가 이러한 비트를 제거한 메시지와 같은 해시를 생성하지 않도록 하기 위해 필요한 과정이다.

• 처음에는 1비트를 필요로하므로 끝에 몇 개의 추가 0비트만 가진 다른 메시지를 동일한 해시로 생성하지 않는다.
• 메시지는 패딩 된 후에 $r$비트와 같아야 한다. 따라서 마지막 1비트의 위치는 다른 해시 변형(different hash variants)에 대해 보안 증명(security proof) 기능이 작동하기 위해 필요한 크기(rate) $r$을 멀티 레이트 패딩(multi-rate padding)으로 나타내며, 만약 패딩이 없다면, 동일한 메시지의 다른 해시 변형(different hash variants)의 자른 부분까지도 동일하게 나온다.

블록 순열

SHA-3의 케착-f[1600](Keccak-f[1600])인 블록 변환 $f$는 XOR, AND, NOT를 사용하는 순열로, 소프트웨어와 하드웨어에서 모두 쉽게 구현할 수 있도록 설계되었다. 이는 $w=2^{l}$비트인 2개의 워드 크기의 모든 파워에 대해 정의된다.

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

속도와 안정성

SHA-3는 높은 수준의 병렬 구조를 가지고 메모리 접근에 인터리빙 방식을 사용하기 때문에 효율성이 아주 좋다. SHA-3 Tree는 MD5보다 높은 보안 강도를 가지면서 더 좋은 효율성을 보여준다. 또한 Tree구조가 아니어도 현재 많이 사용하고 있는 SHA-2보다 안전하고 빠르다는 것을 확인할 수 있다. 현재 한국에서 지정하고 있는 해시 함수는 SHA-224, SHA-256, SHA-384, SHA-512로 향후 SHA-3 알고리즘으로 적용하여야 한다.

최신 개발 현황

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비트 보안보다 유용하지 않지만 일부 표준에서는 필요로할 수 도 있다.

인스턴스(instance)

종류	출력 크기	비율 = 블록 크기	용량	정의	충돌	프리이미지	두 번째 프리이미지
SHA3-224(M)	224	1152	448	Keccak[448](M 01, 224)	112	224	224
SHA3-256(M)	256	1088	512	Keccak[512](M 01, 256)	128	256	256
SHA3-384(M)	384	832	768	Keccak[768](M 01, 384)	192	384	384
SHAKE128(M, d)	d	1344	256	Keccak[256](M 1111, 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)

SHA2와의 차이점

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

참고자료

• 〈SHA-3〉, 《위키백과》
• Roger A. Grimes | CSO, 〈글로벌 칼럼 | 왜 SHA-3을 사용하지 않는가〉, 《아이티월드》, 2018-02-23
• "Hash Functions", NIST, 2017-01-04
• "SHA-3", WIKIPEDIA
• 박기식 외, 〈SHA-3 해시 함수 검정 프로그램과 16bit-UICC 용 SHA-3 구현〉, 《정보과학회논문지 제41권 제11호(2014. 11)》, 2014-08-29

같이 보기

• SHA
• 해시
• 알고리즘
• 암호
• 암호화
• 암호기술
• 미국 국립표준기술연구소

이 SHA3 문서는 암호 알고리즘에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘 □■⊕, 알고리즘, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 암호기술 개인키 • 경량암호 • 다자간 계산(MPC) • 다중서명(멀티시그) • 동형암호 • 디지털서명 • 링서명 • 배타적 논리합(XOR) • 복호화 • 블랙박스 암호 • 서명 • 소수 • 소인수분해 • 슈노르서명 • 스케인 • 스키테일 • 스테가노그래피 • 안전한 다자간 계산(SMPC) • 암호 • 암호경제학 • 암호문 • 암호키 • 암호학 • 암호화 • 이산로그 • 전자봉투 • 전자서명 • 전치암호 • 종단간 암호화 • 치환암호(대체암호) • 키 • 패딩 • 패스워드 • 평문 • 합성수 • 해독 • 해시 • 형태보존암호 • 혼돈 • 화이트박스 암호 • 확산 논리연산 논리곱(AND) • 논리연산 • 논리합(OR) • 배타적 논리합(XOR) • 부울곱 • 부울대수 • 부울합 • 부정논리곱(NAND) • 부정논리합(NOR) • 부정연산(NOT) SHA SHA • SHA0 • SHA1 • SHA2 • SHA224 • SHA256 • SHA384 • SHA512 • SHA512/224 • SHA512/256 • SHA3 • SHA3-224 • SHA3-256 • SHA3-384 • SHA3-512 MD MD • MD2 • MD4 • MD5 • RIPEMD • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 기타 해시 CRC-16 • CRC-32 • CRC-64 • Keccak-256 • Keccak-384 • Keccak-512 • Shake-128 • Shake-256 • 베이스32 • 베이스32 파일 • 베이스58 • 베이스64 • 베이스64 파일 • 순환중복검사 대칭키 AES • ARIA(아리아) • DES • HIGHT(하이트) • LEA • SEED(시드) • 대칭키 • 대칭키 암호 알고리즘 • 디피-헬만 • 디피-헬만 키교환 • 레인달 • 블로피시 • 블록암호 • 스트림 암호 • 에스박스(S-Box) • 트리플 DES 비대칭키 PKI • RSA • 공개키 • 공개키 암호 알고리즘 • 비대칭키 • 엘가말 • 타원곡선 • 타원곡선 디지털서명 알고리즘 • 타원곡선암호 영지식증명 영지식 상호 증명(ZKIP) • 영지식 스나크 • 영지식 스타크 • 영지식증명 양자암호 BB84 프로토콜 • E91 프로토콜 • B92 프로토콜 • 비밀키 오류율 • 안전성 증명 • 양자난수생성기 • 양자내성암호 • 양자암호 • 양자얽힘 • 양자역학 • 양자중첩 • 양자컴퓨터 • 양자키 • 양자키분배 • 양자통신 • 연속 변수 프로토콜 암호해독 기지평문공격(KPA) • 선택암호문공격(CCA) • 선택평문공격(CPA) • 암호공격 • 암호문 단독공격(COA) • 암호해독 암호학 인물 라이언 플레이페어 • 레너드 애들먼 • 로널드 리베스트 • 마틴 헬만 • 블레즈 드 비즈네르 • 아디 샤미르 • 앨런 튜링 • 웨슬리 피터슨 • 찰스 휘트스톤 • 휫필드 디피 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반