본 논문에서는 새로운 해쉬 알고리듬인 SHA-3과 출력 길이 확장함수인 SHAKE256을 구현하는 해쉬 프로세서를 설계하였다. 해쉬 프로세서는 성능을 극대화하기 위해 Padder 블록, 라운드 코어 블록, 출력 블록이 블록 단계에서 파이프라인 구조로 동작한다. Padder 블록은 가변길이의 입력을 여러 개의 블록으로 만들고, 라운드 코어 블록은 on-the-fly 라운드 상수 생성기를 사용하여 SHA-3와 SHAKE256에 대응하는 해쉬 및 출력 확장 결과를 생성하며, 출력 블록은 결과 값을 호스트로 전달하는 기능을 수행한다. 해쉬 프로세서는 Xilinx Virtex-5 FPGA에서 최대 동작 속도는 220 MHz이며, SHA3-512의 경우 5.28 Gbps의 처리율을 갖는다. 프로세서는 SHA-3 와 SHAKE-256 알고리듬을 지원하므로 무결성, 키 생성, 난수 생성 등의 암호 분야에 응용이 가능하다.
본 논문에서는 새로운 해쉬 알고리듬인 SHA-3과 출력 길이 확장함수인 SHAKE256을 구현하는 해쉬 프로세서를 설계하였다. 해쉬 프로세서는 성능을 극대화하기 위해 Padder 블록, 라운드 코어 블록, 출력 블록이 블록 단계에서 파이프라인 구조로 동작한다. Padder 블록은 가변길이의 입력을 여러 개의 블록으로 만들고, 라운드 코어 블록은 on-the-fly 라운드 상수 생성기를 사용하여 SHA-3와 SHAKE256에 대응하는 해쉬 및 출력 확장 결과를 생성하며, 출력 블록은 결과 값을 호스트로 전달하는 기능을 수행한다. 해쉬 프로세서는 Xilinx Virtex-5 FPGA에서 최대 동작 속도는 220 MHz이며, SHA3-512의 경우 5.28 Gbps의 처리율을 갖는다. 프로세서는 SHA-3 와 SHAKE-256 알고리듬을 지원하므로 무결성, 키 생성, 난수 생성 등의 암호 분야에 응용이 가능하다.
This paper describes a design of hash processor which can execute new hash algorithm, SHA-3 and extendable-output function (XOF), SHAKE-256. The processor that consists of padder block, round-core block and output block maximizes its performance by using the block-level pipelining scheme. The padder...
This paper describes a design of hash processor which can execute new hash algorithm, SHA-3 and extendable-output function (XOF), SHAKE-256. The processor that consists of padder block, round-core block and output block maximizes its performance by using the block-level pipelining scheme. The padder block formats the variable-length input data into multiple blocks and then round block generates SHA-3 message digest or SHAKE256 result for multiple blocks using on-the-fly round constant generator. The output block finally transfers the result to host processor. The hash processor that is implemented with Xilinx Virtex-5 FPGA can operate up to 220-MHz clock frequency. The estimated maximum throughput is 5.28 Gbps(giga bits per second) for SHA3-512. Because the processor supports both SHA-3 hash algorithm and SHAKE256 algorithm, it can be applicable to cryptographic areas such as data integrity, key generation and random number generation.
This paper describes a design of hash processor which can execute new hash algorithm, SHA-3 and extendable-output function (XOF), SHAKE-256. The processor that consists of padder block, round-core block and output block maximizes its performance by using the block-level pipelining scheme. The padder block formats the variable-length input data into multiple blocks and then round block generates SHA-3 message digest or SHAKE256 result for multiple blocks using on-the-fly round constant generator. The output block finally transfers the result to host processor. The hash processor that is implemented with Xilinx Virtex-5 FPGA can operate up to 220-MHz clock frequency. The estimated maximum throughput is 5.28 Gbps(giga bits per second) for SHA3-512. Because the processor supports both SHA-3 hash algorithm and SHAKE256 algorithm, it can be applicable to cryptographic areas such as data integrity, key generation and random number generation.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
NIST의 홈페이지에서는 비트 단위 길이의 테스트 벡터를 사용하는 예제를 제공하고 있는데[10], SHA-3에 대한 대부분의 하드웨어 및 소프트웨어 구현이 컴퓨터 구조의 바이트 처리에 적합하게 바이트 배수 길이의 입력 메시지만 처리하는 한계가 있다. 본 논문에서는 입력 메시지 길이 제한 문제를 해결하기 위해 임의의 비트 길이 입력 메시지를 처리할 수 있는 SHA-3 해쉬 프로세서를 설계하였다.
제안 방법
마지막 iota(ι) 단계는 (x,y)=(0,0)인 lane에 대해 라운드 상수(RC)와 XOR 동작으로 구현된다. 라운드 상수 생성 방안은 룩업 테이블로 구현하는 방안과 하드웨어로 구현하는 방안으로 나눌 수 있는데, 본 논문에서는 속도향상을 위해 그림 6(b) 구조와 같은 on-the-fly 방식의 라운드 상수 발생 회로를 설계하였다. update_logic은 그림 6(a)의 bit-serial GFdivider[11]을 병렬 연산 구조로 수종해서 매 클록마다 t=0, 7, 14, .
Rho(ρ) 단계는 64-비트로 구성된 각 lane을 행과 열의 위치 (x,y)에 따라 결정되는 오프셋 길이만큼 회전 이동하는 동작으로 구현하였다.
SHA-3의 패당 규칙을 지원하는 padder 블록의 구조는 그림 4와 같다. SHA-3의 4가지 모드와 SHAKE-256은 다른 블록 길이(r)를 가지고 있으므로, 모드별로 다른 초기 값을 갖는 pad-counter를 사용하며, 가장 긴 블록 길이를 갖는 SHA3-224의 r=1152-b에 맞추어 36개의 32-비트로 구성된 쉬프트 레지스터 구조를 구현한다. LW_padder회로는 마지막 32-비트 워드인 경우 bit_num[4:0]과 last_q를 사용하여 그림 3의 32-비트 패딩 결과를 생성하며, MUX는 last_q=0,1에 따라{0.
넷째, SHA-3의 최종 표준안에 도입된 영역 파라미터는 메시지의 일부로 처리하여, 호스트 단에서 메시지의 맨 뒤에 추가해서 입력하도록 한다.
둘째, SHA-3의 핵심 내부 f() 함수를 구현하는 라운드 코어 구조는 반복 구조로 구현하지만, padder 블록,라운드 코어블록, 출력 블록 간에는 블록 수준의 파이프라인 처리를 적용하여 성능을 놓이도록 한다.
본 논문에서는 미국 표준 해쉬 알고리듬으로 채택된 SHA-3 알고리듬과 출력 확장 함수인 SHAKE-256을 처리하는 해쉬 프로세서를 하드웨어로 설계한 후 검증하였다. 해쉬 프로세서는 padder 블록, round core 블록,output 블록으로 구성되며, 블록 파이프라인 처리를 통해 성능을 최적화한다.
라운드 코어에서 계산한 SHA-3와 SHAKE-256의 결과를 호스트로 전송하는 역할을 한다. 블록 간에 독립성을 제공하고 블록 파이프라인을 구현하기 위해 라운드 코어의 state 레지스터의 상위 1088-비트를 쉬프터 레지스터 구조의 출력 레지스터(out_R[0] ~ out_R[33])에 병렬로 저장한 후 Mode[2:0]에 따라 32-비트 단위로 좌측 이동하면서 호스트에 결과를 전달한다. 단, SHAKE-256의 경우 원하는 길이의 출력을 생성할 때까지 그림 1의 출력 짜내기 단계를 수행하도록 라운드 코어에 SHAKE_rep 신호로 지시한다.
셋째, 메시지 길이가 바이트의 배수가 아닌 경우도 처리할 수 있도록 하여, SHA-3의 표준안에서 제시된 모든 테스트 벡터를 만족하도록 한다.
첫째, 해쉬 응용과 키, 난수 생성 등에 응용할 수 있도록 4가지 함수로 구성된 SHA-3과 SHAKE256 알고리듬을 하나의 하드웨어로 구현한다.
이론/모형
설계한 해쉬 프로세서는 Verilog-2001 HDL로 모델링하였으며, 동작 검증에 NIST에서 제공한 테스트 벡터와 Modelsim 시뮬레이터를 사용하였다[10]. 그림 9는 입력 길이가 1630-비트인 경우 SHA3-256에 대한 Modelsim 검증 파형을 나타낸다.
성능/효과
LFSR_R 값에 xi (i=0,...,6)을 곱한 후 기약 다항식으로 나눈 후, 추가적으로 mod x 동작을 하므로 유한체 곱셈을 하지 않고 상수로 결정되므로 7개의 결과는 각각 2개 이하의 XOR 연산으로 구현되어 룩업 테이블을 사용하는 방식에 비해 속도 측면과 면적 측면에서 훨씬 효율적이다.
또한 라운드 동작의 세부 iota(ι)단계에서 라운드 상수를 테이블 룩업 방식이 아닌 on-the-fly 하드웨어 방식으로 구현함에 의해서 면적과 속도 향상을 얻을 수 있었다.
Padder 블록과 라운드 코어 블록간의 블록 수준 파이프라인 동작은 모든 메시지 블록이 Padder 블록에 채워질 때까지 반복된다. 마지막 블록이 라운드 코어에서 처리가 완료된 후 출력 블록으로 전달되어 해쉬 결과를 32-비트 단위로 호스트로 전달한다. SHA-3의 4가지 동작 모드별로 블록 길이(r-비트)와 출력 길이(d-비트)가 다르므로 Padder 블록에서 32-비트 단위로 블록을 입력하는 경우 필요한 사이클 수가 모드별로 다르다.
다만 향후 암호 분야에 폭넓게 응용하기 위해 SHAKE-256 지원 확장과 회로의 신뢰성 향상 및 부채널 공격에 대한 대처 연구가 필요하다. 본 논문의 해쉬 프로세서가 지원하지 않은 SHAKE128의 경우 Padder 블록과 Output 블록의 확장으로 쉽게 구현이 가능하다.
표 3은 문헌에서 발표한 SHA3 프로세서와 비교한 결과이다. 본 논문의 해쉬 프로세서는 5개의 기능 지원으로 하드웨어의 복잡도 증가로 최장 경로의 지연 시간이 늘어나 한 개의 라운드 코어를 기준으로 한 처리율은 기존 문헌에 비해 떨어지지만, 블록 수준 파이프라인 동작으로 여러 개의 연속된 메시지에 대한 해쉬 처리의 경우 성능이 높아, 시스템 측면에서는 다른 프로세서에 비해 우수하다고 판단된다. 향후 시뮬레이션 단계의 성능 평가 다음에 FPGA 환경에서 USB 인터페이스로 구현을 검증할 예정이다.
또한 라운드 동작의 세부 iota(ι)단계에서 라운드 상수를 테이블 룩업 방식이 아닌 on-the-fly 하드웨어 방식으로 구현함에 의해서 면적과 속도 향상을 얻을 수 있었다. 설계된 해쉬 프로세서는 Virtex5 FPGA 환경에서 최대 220 MHz의 클록 주파수를 가지며, SHA3-512의 경우 최대 5.28Gbps의 처리율을 가지며, SHAKE-256의 경우 7.04 Gbps의 난수 생성율을 제공한다. 다만 향후 암호 분야에 폭넓게 응용하기 위해 SHAKE-256 지원 확장과 회로의 신뢰성 향상 및 부채널 공격에 대한 대처 연구가 필요하다.
표 2는 해쉬 프로세서의 특성을 요약한 결과이다. 해쉬 프로세서를 Xilinx Virtex5 칩을 사용하여 구현한 결과 최대 동작 주파수가 220 MHz로 평가되었다. 식 (4) 과 식(5)을 적용한 결과 SHA3-512와 SHAKE-512는 각각 5.
후속연구
04 Gbps의 난수 생성율을 제공한다. 다만 향후 암호 분야에 폭넓게 응용하기 위해 SHAKE-256 지원 확장과 회로의 신뢰성 향상 및 부채널 공격에 대한 대처 연구가 필요하다. 본 논문의 해쉬 프로세서가 지원하지 않은 SHAKE128의 경우 Padder 블록과 Output 블록의 확장으로 쉽게 구현이 가능하다.
설계한 해쉬 프로세서는 임의의 비트 길이 메시지 지원, 블록 파이프라인에 따른 높은 시스템 레벨 처리율,SHA-3와 SHAKE-256 알고리듬 지원으로 무결성, 디지털서명, 키 생성, 난수, HMAC 등의 다양한 암호 분야에 효율적으로 응용이 가능하다.
본 논문의 해쉬 프로세서는 5개의 기능 지원으로 하드웨어의 복잡도 증가로 최장 경로의 지연 시간이 늘어나 한 개의 라운드 코어를 기준으로 한 처리율은 기존 문헌에 비해 떨어지지만, 블록 수준 파이프라인 동작으로 여러 개의 연속된 메시지에 대한 해쉬 처리의 경우 성능이 높아, 시스템 측면에서는 다른 프로세서에 비해 우수하다고 판단된다. 향후 시뮬레이션 단계의 성능 평가 다음에 FPGA 환경에서 USB 인터페이스로 구현을 검증할 예정이다.
질의응답
핵심어
질문
논문에서 추출한 답변
해쉬 알고리듬이란 무엇인가?
정보 보호 분야에서 암호화 알고리듬만큼 중요하다고 평가되는 암호학적 해쉬 알고리듬(cryptographic hash function)은 통신 시스템과 저장 매체에 담긴 정보의 위․변조 여부를 확인하는 기술이다[1,2].
SHA-3 표준안은 무엇으로 구성되는가?
NIST는 공청회와 표준화 과정을 거쳐 영역 파라미터를 입력 메시지에 추가하는 최종 문서를 2015년 8월에 발표하였다[5]. SHA-3 표준안은 출력 해쉬값의 길이에 따라 SHA3-224, SHA3-256, SHA3-384, SHA3-512로 구성된 SHA-3 해쉬 알고리듬과 출력 길이를 확장할 수 있는 extendable-output function (XOF)인 SHAKE128, SHAKE256로 구성된다. SHA-3 알고리듬은 스폰지 함수(sponge function)를 사용하며 매개 변수에 따라 처리 성능과 암호 강도를 적절히 조절할 수 있고 가변 길이의 해쉬 출력을 생성할 수 있다.
출력 짜내기 동작는 어디에 사용되는가?
반면 출력 짜내기 동작(squeezing phase)은 흡수 단계 출력의 상위 r-비트의 메시지를 종자로 사용하여 f() 함수의 반복 동작으로 원하는 길이의 출력을 생성한다. 이러한 동작은 출력 확장 함수인 SHAKE128과 SHAKE256에서 사용되며, 키 생성과 난수 생성기로 활용된다. SHA-3의 표준안의 경우 최대 해쉬 출력 길이가 d=512비트로 항상 r-비트 보다 작으므로 출력 짜내기 단계가 필요하지 않다.
참고문헌 (11)
W. Stalling, Cryptography and Network Security-Principle and Practices, 5th ed., Essex, England: Pearson, 2013.
I. S. Janik, "High Level Synthesis and Evaluation of the Secure Hash Standard for FPGAs," Ms. D. dissertation, University of Windsor, Windsor, Ontario, Canada, 2015.
X. Wang, Y. Yin, and H. Yu, "Finding collisions in the full SHA-1," in Advances in Cryptology(Crypto-2005) Lecture Notes in Computer Science, vol. 3621, Berlin, Heidelberg: Springer-Verlag, 2005, pp. 17-36.
W. Stalling, "Inside SHA-3," IEEE Potentials, vol. 22, no. 6, pp. 26-31, Nov.-Dec. 2013.
FIPS PUB 202, SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions, NIST, Gaithersburg, MD, Aug. 2015.
B. Baldwin, A. Byrne, and L. Lu, "A Hardware Wrapper for the SHA-3 Hash Algorithms," in IET Irish Signals and Systems Conference, Cork, Ireland, pp.1-6, 2010.
G. Provelengios et al, "FPGA-Based Design Approaches of Keccak Hash Function," in 15th Euromicro Conference on Digital System Design, Izmir, Turkey, pp.648-653, 2012.
A. Arshad et al "Compact Implementation of SHA3-512 on FPGA," in 2014 Conference on Information Assurance and Cyber Security(CIACS), Rawalpindi, Pakistan, pp.29-33, 2014.
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 Systems, vol. 33, no. 7, pp.1105-1109, July 2014.
NIST, "SHA-3 example: Test vector," [Internet]. Available: http://csrc.nist.gov/groups/ST/hash/sha-3/fips202_standard_2015.html.
K. K. Saluja, "Linear Feedback Shift Registers Theory and Applications," [Internet]. Available: http://homepages.cae.wisc.edu/-ece553/handouts/LFSR-notes.PDF.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.