[논문]SHA-3 해시 함수의 최적화된 하드웨어 구현

김동성; 신경욱

doi:10.7471/ikeee.2018.22.4.886

SHA-3 해시 함수의 최적화된 하드웨어 구현
An Optimized Hardware Implementation of SHA-3 Hash Functions 원문보기

전기전자학회논문지 = Journal of IKEEE, v.22 no.4, 2018년, pp.886 - 895

김동성 (School of Electronic Engineering, Kumoh National Institute of Technology) , 신경욱 (School of Electronic Engineering, Kumoh National Institute of Technology)

초록
AI-Helper

본 논문에서는 NIST에서 발표한 Secure Hash Algorithm(SHA) 표준의 최신 버전인 SHA-3 해시 함수의 하드웨어 구현과 함께 보안 SoC 응용을 위한 ARM Cortex-M0 인터페이스 구현에 대해 기술한다. 최적화된 설계를 위해 5 가지 하드웨어 구조에 대해 하드웨어 복잡도와 성능의 교환조건을 분석하였으며, 분석 결과를 토대로 라운드 블록의 데이터패스를 1600-비트로 결정하였다. 또한, 라운드 블록과 64-비트 인터페이스를 갖는 패더를 하드웨어로 구현하였다. SHA-3 해시 프로세서, Cortex-M0 그리고 AHB 인터페이스를 집적하는 SoC 프로토타입을 Cyclone-V FPGA 디바이스에 구현하여 하드웨어/소프트웨어 통합 검증을 수행하였다. SHA-3 프로세서는 Virtex-5 FPGA에서 1,672 슬라이스를 사용하였으며, 최대 289 Mhz의 클록 주파수로 동작하여 5.04 Gbps의 처리율을 갖는 것으로 예측되었다.

Abstract ▼ AI-Helper

This paper describes a hardware design of the Secure Hash Algorithm-3 (SHA-3) hash functions that are the latest version of the SHA family of standards released by NIST, and an implementation of ARM Cortex-M0 interface for security SoC applications. To achieve an optimized design, the tradeoff between hardware complexity and performance was analyzed for five hardware architectures, and the datapath of round block was determined to be 1600-bit on the basis of the analysis results. In addition, the padder with a 64-bit interface to round block was implemented in hardware. A SoC prototype that integrates the SHA-3 hash processor, Cortex-M0 and AHB interface was implemented in Cyclone-V FPGA device, and the hardware/software co-verification was carried out. The SHA-3 hash processor uses 1,672 slices of Virtex-5 FPGA and has an estimated maximum clock frequency of 289 Mhz, achieving a throughput of 5.04 Gbps.

주제어

표/그림 (12)

그림 Fig. 1. 3-D array representation of state. 그림 1. 3차원 배열로 표현된 state
그림 Fig. 2. Sponge construction of SHA-3. 그림 2. SHA-3의 스폰지 구조
그림 Fig. 3. Architectures of SHA-3 hash processor depending on datapath bit-width. 그림 3. 데이터패스 크기에 따른 SHA-3 해시 프로세서의 구조
그림 Fig. 4. Performance analysis results for determining SHA-3 hash processor architecture. 그림 4. SHA-3 해시 프로세서의 아키텍처 결정을 위한 성능분석 결과
그림 Fig. 5. Architecture of SHA-3 processor. 그림 5. SHA-3 프로세서의 구조
그림 Fig. 6. FSM of Padder block. 그림 6. Padder 블록의 유한상태머신
그림 Fig. 7. Round block. 그림 7. 라운드 블록
그림 Fig. 8. KECCAK-p permutation block. 그림 8. KECCAK-p 순열 변환 블록
그림 Fig. 9. Timing diagram of SHA-3 hash processor. 그림 9. SHA-3 해시 프로세서의 타이밍 도
그림 Fig. 10. Cortex-M0 interface of SHA-3 slave. 그림 10. SHA-3 슬레이브의 Cortex-M0 인터페이스
그림 Fig. 11. HW/SW co-verification of SHA-3 processor and Cortex-M0 with FPGA implementation. 그림 11. FPGA 구현에 의한 SHA-3 프로세서와 Cortex-M0의 하드웨어/소프트웨어 통합 검증
표 Table. 1. Comparison of SHA-3 hash processors. 표 1. SHA-3 해시 프로세서 비교

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 SHA-3 KECCAK 알고리듬을 저면적 하드웨어 구현에 적합한 하드웨어 구조를 탐색하기 위해 여러 가지 구조를 구상하고, 이를 비교, 분석하였다. 하드웨어 구조의 비교를 위해 SHA3-512 해시 함수를 선택했고, state의 크기는 b=1600로 결정하였다.

제안 방법

KECCAK-p 순열 변환을 구성하는 5 가지의 스텝 매핑을 처리할 때, 각 스텝에서 연산되는 데이터 단위를 고려하여 라운드 블록의 데이터 패스크기를 결정하였다. 두 번째, 세 번째 스텝인 ρ, π의 경우, lane 단위로 연산되기 때문에 64-비트 크기로 데이터패스를 구현하면 Χ 스텝을 제외한 모든 연산에 적합할 것으로 판단하였다.
KECCAK-p 순열변환 블록은 그림 8과 같이 θ 스텝 블록, ρ와 π 스텝 블록, 그리고 χ와 ι 스텝블록으로 분할하여 구현하였다.
NIST FIPS 202에 표준으로 제시된 SHA-3 해시프로세서의 하드웨어 구현을 위한 최적 설계조건을 분석하고, 이를 토대로 경량화 하드웨어로 구현하였다. 저면적 구현을 위해 loop-unrolling 구조를 채택하였고, 면적대비 성능이 가장 우수한 1600-비트 데이터패스로 구현하였다.
설계된 SHA-3 해시 프로세서는 RTL 시뮬레이션을 통한 기능검증을 수행한 후, FPGA 구현을 통해 하드웨어 동작을 검증하였다. SHA-3 해시 프로세서와 UART 블록 그리고 버퍼 회로를 Xilinx Virtex-5 FPGA에 구현했으며, Python을 이용하여 검증용 GUI와 SHA-3 해시 함수의 소프트웨어 버전을 구현하였다. NIST FIPS 180-2 표준 문서의 참조 구현 값을 사용하여 검증한 결과, 소프트웨어결과와 FPGA에 구현된 SHA-3 해시 프로세서의결과가 일치함을 확인하였다.
Cyclone-V FPGA 디바이스가 탑재된 V2M-MPS2 보드를 사용하였으며, Cortex-M0와 SHA3_ahb_slave를 포함하는 그림 10의 회로를 FPGA에 구현하였다. 검증 플랫폼은 UART 포트를 통해 PC와 연결되고, 검증 과정을 제어하는 소프트웨어가 Cortex- M0에 프로그래밍 되며, PC의 GUI 화면을 통해 검증 결과를 확인한다. 그림 11-(b)는 설계된 SHA-3 해시 프로세서의 HW/SW 통합검증 결과 화면이다.
그림 10의 Cortex-M0 인터페이스 설계를 검증하기 위해 SHA-3 해시 코어와 AHB_slave_IF 블록으로 구성된 슬레이브를 BFM(bus function model)시뮬레이션으로 검증하여 데이터의 송수신이 AHB규격에 맞게 동작함을 확인하였다.
따라서 데이터패스를 320-비트의 배수로 선정하는 것도 합리적인 구상이라고 판단했다. 따라서 state에 속한 모든 데이터를 한 번에 연산할 수 있는 1600-비트 데이터패스를 포함하여 64-비트, 320-비트, 640-비트,960-비트의 5 가지 데이터패스 구조를 대상으로 비교, 분석하였다. [9]
본 논문에서는 차세대 해시 함수 표준으로 채택된 SHA-3 해시 알고리듬을 최적 하드웨어 IP(intellectual property)로 구현하고, Cortex-M0 슬레이브 인터페이스와 FPGA 구현을 통해 하드웨어동작을 검증하였다. II장에서는 SHA-3 해시 알고리듬에 대해 간략히 기술하고, III장에서는 하드웨어 설계를 위한 최적 조건 분석 결과에 대해 설명한다.
NIST FIPS 202에 표준으로 제시된 SHA-3 해시프로세서의 하드웨어 구현을 위한 최적 설계조건을 분석하고, 이를 토대로 경량화 하드웨어로 구현하였다. 저면적 구현을 위해 loop-unrolling 구조를 채택하였고, 면적대비 성능이 가장 우수한 1600-비트 데이터패스로 구현하였다. 0.

대상 데이터

그림 11-(b)는 설계된 SHA-3 해시 프로세서의 HW/SW 통합검증 결과 화면이다. 입력 메시지의 길이는 163,809-바이트이며 4가지 SHA-3 해시함수를 검증했다. 그림 11-(b)는 SHA3-256 해시함수의 검증결과를 보인 것이며, 이와 같은 HW/SW통합검증을 통해 SHA-3 해시 프로세서가 Cortex-M0에 슬레이브로 연결되어 정상적으로 동작함을 확인하였다.

데이터처리

설계된 SHA-3 해시 프로세서는 RTL 시뮬레이션을 통한 기능검증을 수행한 후, FPGA 구현을 통해 하드웨어 동작을 검증하였다. SHA-3 해시 프로세서와 UART 블록 그리고 버퍼 회로를 Xilinx Virtex-5 FPGA에 구현했으며, Python을 이용하여 검증용 GUI와 SHA-3 해시 함수의 소프트웨어 버전을 구현하였다.

이론/모형

ι 스텝에서 사용되는 라운드 상수는 문헌 [11]의 방법을 적용하여 8-비트 LUT로 구현하였다.
하드웨어 구현을 위해 loop unrolling, pipelining등 다양한 구조를 고려할 수 있다. loop unrolling구조가 pipelining에 비해 처리율은 낮지만 적은면적으로 구현할 수 있기 때문에 본 논문에서는loop-unrolling 구조를 채택하였다. 선정된 데이터패스를 하드웨어로 구현하기 위해 그림 3과 같은 3가지 구조를 구상하였다.

성능/효과

0.18 μm CMOS 셀라이브러리로 합성한 결과, 클록 주파수 100 Mhz에서 35,753 GE로 합성되었으며, 최대 동작 주파수는 330 Mhz로 예측되었다.
소요된 슬라이스 수는 그림 3-(c) 구조의 1600-비트로 설계된 경우가1,554개로 가장 적은 것으로 평가되었으며, 이는 다른 데이터패스 구조에 비해 1600-비트 레지스터가한 개만 사용되는 것에 기인한다. 1600-비트 데이터패스를 갖는 프로세서가 5.04 Gbps로 가장 높은 처리율을 가지며 면적대비 성능 비도 가장 높게 나타났다.
SHA-3 해시 프로세서와 UART 블록 그리고 버퍼 회로를 Xilinx Virtex-5 FPGA에 구현했으며, Python을 이용하여 검증용 GUI와 SHA-3 해시 함수의 소프트웨어 버전을 구현하였다. NIST FIPS 180-2 표준 문서의 참조 구현 값을 사용하여 검증한 결과, 소프트웨어결과와 FPGA에 구현된 SHA-3 해시 프로세서의결과가 일치함을 확인하였다.
SHA-3 해시 프로세서를 Cortex-M0에 슬레이브로 인터페이스하고, FPGA에 구현하여 HW/SW 통합검증을 통해 정상적으로 동작함을 확인하였다. 본 논문의 SHA-3 해시 프로세서는 저면적 구현을 장점으로 가지며, 따라서 하드웨어 자원이 제한된IoT 분야와 보안 SoC(system-on-chip)에 IP로 이용이 가능할 것으로 평가된다.
두 번째, 세 번째 스텝인 ρ, π의 경우, lane 단위로 연산되기 때문에 64-비트 크기로 데이터패스를 구현하면 Χ 스텝을 제외한 모든 연산에 적합할 것으로 판단하였다.
마지막 라운드 연산이 끝나면, 다음 블록의 연산을 위해서 입력되는 데이터와 1600-비트 레지스터에 저장된 값이 64-비트씩 순차적으로 XOR되어 r-비트만큼 1600-비트 레지스터에 저장되고, 하위 (1600-r)-비트를 capacity로 하여 다음 블록의 첫 번째 라운드 연산에 사용된다. 마지막 블록에 대한연산 결과가 1600-비트 레지스터에 저장되면, 상위64-비트부터 순차적으로 d-비트만큼 출력된다.
또한, 최대 동작 주파수도 문헌 [12], [14]에 비해 높은 것으로 평가되었다. 문헌 [13]의 사례와는 처리량과 하드웨어 자원에 대해서 직접적으로 비교할 수 없지만, 본 논문의 결과는 문헌 [13]에 비해 많은 해시 함수를 지원하고, Padder 블록이 하드웨어로 구현되었다는 점에서 유용성이 우수한 것으로 평가된다.
7 Gbps로 가장 높았으며, 면적대비 성능비도 가장 높았다. 이와 같은 하드웨어 구조에 따른 면적, 성능 분석결과로부터, SHA-3 해시 알고 리듬의 최적 하드웨어 구현을 위해서는 loop-unrolling 구조의 1600-비트 데이터패스로 설계하는 것이 가장 효율적인 것으로 판단된다.
최대 동작주파수는 1600-비트, 960-비트의 데이터패스를 갖는 경우가 330 MHz로 가장 높게 나타났으며, 1600-비트 데이터 패스로 설계된 경우가 35,794 GE로 가장 적은 면적을 차지하였다. 처리율은 1600-비트 데이터패스의 구조가 5.7 Gbps로 가장 높았으며, 면적대비 성능비도 가장 높았다. 이와 같은 하드웨어 구조에 따른 면적, 성능 분석결과로부터, SHA-3 해시 알고 리듬의 최적 하드웨어 구현을 위해서는 loop-unrolling 구조의 1600-비트 데이터패스로 설계하는 것이 가장 효율적인 것으로 판단된다.
18 μm CMOS 셀 라이브러리로 합성한 결과를 토대로 성능 및 면적을 비교 분석한 결과이다. 최대 동작주파수는 1600-비트, 960-비트의 데이터패스를 갖는 경우가 330 MHz로 가장 높게 나타났으며, 1600-비트 데이터 패스로 설계된 경우가 35,794 GE로 가장 적은 면적을 차지하였다. 처리율은 1600-비트 데이터패스의 구조가 5.

후속연구

SHA-3 해시 프로세서를 Cortex-M0에 슬레이브로 인터페이스하고, FPGA에 구현하여 HW/SW 통합검증을 통해 정상적으로 동작함을 확인하였다. 본 논문의 SHA-3 해시 프로세서는 저면적 구현을 장점으로 가지며, 따라서 하드웨어 자원이 제한된IoT 분야와 보안 SoC(system-on-chip)에 IP로 이용이 가능할 것으로 평가된다.

질의응답

핵심어	질문	논문에서 추출한 답변
	대칭키 암호는 어떤 목적으로 사용되는가?	정보보안 시스템은 대칭키 암호, 공개키 암호, 해시 함수, 난수 발생 등 다양한 보안 관련 알고리듬을 기반으로 구현된다. 대칭키 암호는 정보의 기밀성을 보장하기 위해 데이터를 암호화하는 목적으로 사용되며 AES(Advanced Encryption Standard)[1], ARIA(Academy, Research Institute, Agency)[2] 등의 블록암호 알고리듬이 널리 사용되고 있다. 공개키 암호 방식으로는 RSA(Rivest, Shamir, Adleman)[3], ECC(Elliptic Curve Cryptography) [4] 등이 있으며, 키 교환이나 전자서명과 같은 보안 서비스를 제공하기 위해 사용된다.
	정보보안 시스템은 무엇을 기반으로 구현되는가?	정보보안 시스템은 대칭키 암호, 공개키 암호, 해시 함수, 난수 발생 등 다양한 보안 관련 알고리듬을 기반으로 구현된다. 대칭키 암호는 정보의 기밀성을 보장하기 위해 데이터를 암호화하는 목적으로 사용되며 AES(Advanced Encryption Standard)[1], ARIA(Academy, Research Institute, Agency)[2] 등의 블록암호 알고리듬이 널리 사용되고 있다.
	SHA-3 KECCAK 알고리듬이 개발된 이유는 무엇인가?	해시(hash) 함수는 가변길이의 데이터를 고정된 길이의 다이제스트(digest)로 변환하는 암호학적 함수를 의미하며, HAS-160 [5],SHA-1(Secure Hash Algorithm-1), SHA-2 [6],Whirlpool [7] 등이 사용되고 있다. 그러나 보안공격이 날로 정교해짐에 따라 기존에 사용되고 있는 해시 함수들의 수학적 결함이 발견되면서 새로운 해시 함수의 필요성이 제기되었다. 이에 미국국립표준기술연구소(NIST)는 새로운 해시 함수후보 알고리듬을 공개적으로 모집하였고, 2012년에 KECCAK 알고리듬이 새로운 해시 함수인 SHA-3로 선정되어 2015년 8월에 표준안이 공개되었다.

참고문헌 (14)

NIST Std. FIPS-197, Advanced Encryption Standard, National Institute of Standard and Technology (NIST), 2001.
KS X 1213, 128 bit Block Encryption Algorithm ARIA, Korean Agency for Technology and Standards, 2004.
R. Rivest, A. Shamir and L. Adleman, "A method for obtaining Digital Signatures and Public-Key Crypto-system," Communications of Association for Computing Machinery (ACM), vol.21, no.2, pp.120-126, 1978. DOI:10.1145/359340.359342

상세보기
NIST Std. FIPS PUB 186-2, Digital Signature Mechanism with Appendix (Part 3) Korean Certificate-based Digital Signature Algorithm using Elliptic Curve, Telecommu-nications Technology Association, 2012.
TTA std. TTAK.KO-12.0011/R1, Hash Function Standard-Part2: Hash Function Algorithm Standard (HAS-160), Telecommu-nications Technology Association (TTA), 2000.
NIST std. FIPS 180-2, Secure Hash Standard (SHS), National Institute of Standard and Technology (NIST), 2001.
P. Barreto and V. Rijmen, "The Whirlpool Hashing Function," pp.1-20, 2003.
National Institute of Standards and Technology. FIPS PUB 202-SHA3 Standard: Permutation-Based Hash and Extendable-Output function, 2015.
D. S. Kim and K. W. Shin, "Analysis of Optimal Design conditions for SHA3-512 Hash Function," Proceedings of 2018 2nd Conference of the Korea Institute of Information and Communication Engineering, vol.22, no.2, pp.187-189, Oct. 2018.
D. S. Kim and K. W. Shin, "A Hardware Implementation of SHA3 Hash Processor using Cortex-M0," Proceedings of 2019 International Conference on Electronics, Information, and Communication (ICEIC 2019), Accepted.
M. M. Wong, J. Haj-Yahya, S. Sau and A. Chattopadhyay," A New High Throughput and Area Efficient SHA-3 Implementation," Proceedings of 2018 IEEE International Symposium on Circuits and Systems (ISCAS), Florence, pp.1-5, 2018.
G. Provelengios et al, "FPGA-Based Design Approaches of Keccak Hash Function," Proceedings of 15th Euromicro Conference on Digital System Design, Izmir, Turcky, pp.648-653, 2012. DOI:10.1109/DSD.2012.63
S. Bayat-Sarma et al, "Efficient and Concurrent Reliable Realization of the Secure Cryptographic SHA-3 Algorithm," IEEE Transactions on CAD of Integrated Circuit and System, vol.33, no.7, pp.1105-1109, 2014. DOI:10.1109/TCAD.2014.2307002

상세보기
B. Y. Choi, "Efficient Hardware Design of Hash Processor Supporting SHA-3 and SHAKE256 Algorithms," Journal of the Korea Institute of Information and Communication Engineering, vol.21, no.6, pp.1075-1082, 2017. DOI:10.6109/jkiice.2017.21.6.1075

원문보기 상세보기

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증