Keccak-256

Keccak-256은 Keccak 알고리즘군 중 하나의 알고리즘이며 미국 NIST가 승인하여 사용중인 해시함수 SHA-1, SHA-2에 내재하는 보안 취약점을 개선하고자 개발된 암호화 해시 알고리즘이다. 스위스의 제네바에 본사를 두고 있는 ST마이크로일렉트로닉스(STMicroelectronics) 사의 귀도 베르토니(Guido Bertoni), 조안 대먼(Joan Daemen)과 길레스 반 앗시(Gilles Van Assche) 등 세 사람과 네덜란드의 아인드호벤에 본사를 두고 있는 NXP반도체(NXP Semiconductors) 사의 미하엘 피터스(Michaël Peeters)가 공동으로 개발하였으며 2007년 11월에 미국국립표준기술연구소(NIST)가 조직한 SHA-3 경진대회에서 공개되었다. 경진대회에서 우승한 후 Keccak-256 은 2015년 8월에 미국국립표준기술연구소의 SHA3-256 표준으로 적용되었다.

개요

Keccak은 SHA1, SHA2에 존재하는 보안성 취약문제를 해결하고자 개발 된 암호화 해시 알고리즘이다.

암호화 해시 알고리즘(또는 해시함수)은 임의의 길이를 갖는 메시지를 입력하여 고정 길이의 해시값(메시지 다이제스트; Message Digest)을 출력하고 일정한 보안 특징을 취득하고자 설계한다. 해시 알고리즘은 디지털 서명(Digital Signatures), Message Authentication Codes, Key Derivation Functions, Pseudo random functions 외 기타 보안 애플리케이션에서 널리 사용되고 있다. 미국 연방정보처리표준(FIPS 180-4), 보안 해시 표준(Secure Hash Standard)은 7가지 암호화 해시 알고리즘을 선정하여 미국 연방 내에서 사용하게 하였으며 이는 국제적으로 관련 업계에 널리 사용되어 있다.

2004년부터 2005년 사이에 사용 중이던 몇 가지 해시 알고리즘은 성공적으로 공격을 당하였으며 언론들에서는 NIST가 승인하여 공개한 SHA-1도 폭력 공격에 무너질 가능성이 이론적으로 충분하다고 공개되기 시작하였다. 실제로 이는 2017년 3월에 구글에 의하여 현실적인 입증이 이루어졌다. 이러한 상황에 비추어 NIST는 두 차례 공개 워크샵을 가지고 기승인된 알고리즘에 관한 상황 조사를 추진하였으며 암호화 해시 알고리즘 정책과 표준에 관한 의견을 공개 청구하였다. 최종 결론은 사회 전반을 대상으로 신규 표준으로 적용할 후보 암호화 해시 알고리즘들을 모집하여 공개 경쟁의 방식으로 우승 알고리즘을 선발하고 이를 차세대 비용 알고리즘으로 적용하는 것으로 이루어졌다.

Keccak 알고리즘은 미국국립표준기술연구소가 추진한 SHA-3 경진대회에 참가 한 후보 알고리즘이며 고정 해시길이의 keccak 224, keccak 256, keccak 384, keccak512과 가변 해시 길이의 SHAKE128, SHAKE256으로 구성된다.

Keccak 알고리즘은 2007년 11월부터 경진대회에 참가하여 2012년 12월에 전부의 경쟁 알고리즘들을 물리치고 우승 알고리즘으로 되었으며 2015년 8월에 미국국립표준기술연구소에서 승인 한 SHA3 적용 표준으로 선정되었다.

미국국립표준기술연구소는 Keccak의 우아한 설계와 서로 다른 컴퓨팅 기기에서 작동이 잘 되는 특징을 포함한 여러 칭찬할 만한 품질에 만족을 표시하였으며 구조적으로 깨끗하고 쉽게 분석이 되며(경기 기간에 전부의 제출 된 알고리즘은 공중들에서 오는 검증과 비난을 받아야 한다) SHA-2 또는 최종 경기에 참가 한 다른 알고리즘들 대비 하드웨어의 실행에서 고성능을 나타냈다고 하였다.

NIST 컴퓨터보안전문가 팀 폴크(Tim Polk)는 ‘두 알고리즘은 완전히 달리 설계가 되었기에 SHA-2에서 효과가 있을 공격이 KECCAK에서는 불가능하다’, ‘KECCAK은 SHA-2처럼 공격에 취약하지 않는 액외의 장점을 가지고 있다’고 밝혔다.

Keccak 은 전에 발표되었던 함수 PANAMA와 RadioGatún의 설계를 참조하였고 PANAMA는 1998년에 조안 대먼(Joan Daemen)과 크레이그 클랩(Craig Clapp)이 발표하였으며 RadioGatún은 PANAMA의 후속 버전으로 조안 대먼(Joan Daemen), 미하엘 피터스(Michaël Peeters), 길레스 반 앗시(Gilles Van Assche)이 공동으로 2006년에 NIST 해시 워크샵에서 발표하였다.

경진경과

2007년 11월 2일, 미국국립표준기술연구소(NIST)는 SHA-3 암호화 해시 알고리즘 경진을 조직한다고 선포하였으며 2008년 10월까지 경진에 참가하고자 하는 64개 후보 알고리즘을 접수하였다. 초도 심사를 거쳐 2008년 12월 10일에 51개 알고리즘이 1차 입선 후보자로 경진 참가 자격을 가졌다.

2009년 7월 24일에 14개 알고리즘이 1차 경진을 통과하여 2차 경진 입선 후보 알고리즘으로 되었다. 2차 경진에 진입한 알고리즘으로는 BLAKE, BLUE MIDNIGHT WISH, CubeHash, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Luffa, Shabal, SHAvite-3, SIMD 및 Skein이 있다.

일 년 간의 경진을 거쳐 2010년 12월 9일에 NIST는 2차 경진을 통과한 다섯 가지 알고리즘 BLAKE, Grøstl, JH, Keccak 및 Skein을 결승 경진 후보 알고리즘으로 발표하였다.

2012년 10월 2일, NIST는 알고리즘 캐착(KECCAK)이 경진 우승 알고리즘으로 되었음을 선포하였다.

2014년 NIST는 FIPS 202 "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions" 초안을 공개 발행하였으며 2015년 8월 5일에 공식 승인을 취득하였다.

2015년 8월 5일 NIST는 SHA-3이 신규 해싱 표준(Hashing Standard)이 되었음을 공개 발표하였다.

소개

해시함수 스펀지 구조

Keccak 해시 알고리즘은 Keccak-224, Keccak-256, Keccak-384 와 Keccak-512 등 4개 고정 해시 길이의 암호화 해시 알고리즘과 가변 해시 길이의 SHAKE128과 SHAKE256, 두 개의 확장 가능한 출력 함수(eXtendable-Output Function)(XOF)로 구성되어 있다. 스펀지 구조로 이루어졌기에 스펀지 함수라고도 한다.

스펀지 구조는 Wide random function 혹은 random permutation에 기반하였으며 pseudorandom function의 역할로 입력하는 데이터를 처리 할 시 임의 길이의 데이터 입력을 허용하며 임의 길이 데이터의 출력을 허용한다. 상당히 훌륭한 융통성이 구현되었다.

전반 과정을 보면 임의 길이의 데이터가 입력 시 메시지를 패딩(Padding)하는 패딩 함수가 실행되면서 입력한 데이터의 다이제스트(Digest)를 뽑으며 그 뒤에 전환 함수가 실행되면서 소정 길이의 출력이 이루어진다. SHA-3에 적용한 케착-f [1600](Keccak-f [1600]) 전환 함수는 XOR, AND, NOT을 사용한 순열이다.

Keccak의 속도 문제를 살펴보면 소프트웨어 측면에서 SHA-1보다 3배 더디고 SHA-512 대비 2배 더디다. 하드웨어 측면에서는 SHA-1, SHA-2를 가볍게 넘어서는 성능을 나타낸다. 수치로 보면 약간 실망스럽지만 최신 소프트웨어와 기기에서 해시 확인 절차는 아주 드물게 사용하므로 해시 수행 과정에 소모하는 시간이 2배, 3배가 된다 하더라도 대부분 고객의 시나리오에는 별반 영향을 안 미친다. 이외 CPU의 계산 속도가 나날이 향상됨에 따라 얼마 후에는 아예 느껴지지도 않을 수도 있다.

사례

NIST 표준은 주어진 메세지 M와 출력 길이 d를 대상으로 아래의 사례를 정의하였다.

사례	출력 길이	비율=블록길이	용량	정의	보안강도 충돌	보안강도 프리이미지	보안강도 두 번째 프리이미지
keccak-224(M)	224	1152	448	Keccak[448](M 01, 224)	112	224	224
keccak-256(M)	256	1088	512	Keccak[512](M 01, 256)	128	256	256
keccak-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)

참고자료

• Keccak 팀 공식 홈페이지 - https://keccak.team
• "SHA-3", Wikipedia
• José R.C. Cruz, "Keccak: The New SHA-3 Encryption Standard", Dr Dobb's, 2013-05-07
• Nicodechal, 〈SHA-3 算法计算过程总结〉, Github, 2019-04-08
• "Keccak-main-1.0.pdf", keccak.team

같이 보기

• SHA3-224
• SHA3-256

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

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘 □■⊕, 알고리즘, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 암호기술 개인키 • 경량암호 • 다자간 계산(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) • 암호해독 암호학 인물 라이언 플레이페어 • 레너드 애들먼 • 로널드 리베스트 • 마틴 헬만 • 블레즈 드 비즈네르 • 아디 샤미르 • 앨런 튜링 • 웨슬리 피터슨 • 찰스 휘트스톤 • 휫필드 디피 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반