SHA3

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 암호화 해시 함수 표준을 발표했다.^[1]^[2]

특징

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

스펀지 구조

SHA-3는 데이터가 스펀지에 '흡수'되는 스펀지 구조를 사용한다. 그 결과 데이터가 스펀지에 "스퀴드(squeezed)"된다. 흡수 단계에서는 메시지 블록이 XORED되어 주의 서브셋으로 되며, 그런 다음 순열 함수 f를 사용하여 전체로 변환된다. "스퀴즈(squeeze)"단계에서는 출력 블록을 상애 변환 함수 f와 교대로 상태 하위 집합에서 읽으며 쓰고 읽는 상태의 부분의 크기를 "레이트(rate)"(표시된(denoted) r)라고 하고, 입/출력으로 손대지 않은 부분의 크기를 "용량(capacity)"(표시된(denoted) 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를 연속해서 r-bit 조각 P0, ..., Pn-1로 나눈다.
- 상태 S를 b 0 비트의 문자열로 초기화한다.
- 각 블록 Pi에 대해 입력값을 흡수한다.
  - 끝에 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는 5 × 5 w-비트 워드의 배열(w=64), b = 5 × 5 × 64 = 합계 1600 비트로 구성된다. 또한 케착(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ℓ 비트인 2개의 워드 크기의 모든 파워에 대해 정의된다.

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

속도와 안정성

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

인스턴스(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배 정도 빠르다고 할 수 있고 어느 플랫폼에서도 좋은 효율을 보여주고 있다.

각주

↑ Roger A. Grimes | CSO, 〈글로벌 칼럼 | 왜 SHA-3을 사용하지 않는가〉, 《아이티월드》, 2018-02-23
↑ "Hash Functions", NIST, 2017-01-04

참고자료

〈SHA-3〉, 《위키백과》

같이 보기

이 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) • 암호해독

암호학 인물	라이언 플레이페어 • 레너드 애들먼 • 로널드 리베스트 • 마틴 헬만 • 블레즈 드 비즈네르 • 아디 샤미르 • 앨런 튜링 • 웨슬리 피터슨 • 찰스 휘트스톤 • 휫필드 디피

위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반

[1] Roger A. Grimes | CSO, 〈글로벌 칼럼 | 왜 SHA-3을 사용하지 않는가〉, 《아이티월드》, 2018-02-23

[2] "Hash Functions", NIST, 2017-01-04

[1]

[2]

위키원

이름공간

변수

보기

더 보기

검색