SSE와 AVX를 활용한 LSH의 병렬 최적 구현

국문 초록 (Abstract)

해시함수는 인증, 서명, 데이터 무결성 등을 수행하기 위해 반드시 필요한 암호학적 프리미티브이다. 2005년 중국의 Wang교수에 의해 MD5와 SHA-1과 같은 구조에 대해 충돌쌍 공격이 제기됨으로써 NIST는 SHA-3 프로젝트를 진행하여 Keccak을 새로운 표준 해시함수로 선정하였다. 또한 국내의 경우 국가보안기술연구소에서는 높은 안전성과 효율성을 제공하는 해시함수 LSH를 개발했다. LSH는 초기화, 압축, 완료함수로 이루어지며 함수 내에서 2<SUP>w</SUP>상에서의 덧셈, 비트단위 순환, 워드 단위 순환 및 xor연산을 수행한다. 이러한 연산은 동시에 독립적으로 수행될 수 있으며 병렬화가 가능하다. 본 논문에서는 LSH를 분석하여 구조적인 측면에서 속도를 개선할 수 있는 방법을 제안하고 SIMD의 SSE와 AVX를 활용하여 LSH 함수를 병렬 구현한다.

다국어 초록 (Multilingual Abstract)

Hash function is a cryptographic primitive which conduct authentication, signature and data integrity. Recently, Wang et al. found collision of standard hash function such as MD5, SHA-1. For that reason, National Security Research Institute in Korea suggests a secure structure and efficient hash function, LSH. LSH consists of three steps, initialization, compression, finalization and computes hash value using addition in modulo 2<SUP>w</SUP>, bit-wise substitution, word-wise substitution and bit-wise XOR. These operation is parallelizable because each step is independently conducted at the same time. In this paper, we analyse LSH structure and implement it over SIMD-SSE, AVX and demonstrate the superiority of LSH.

목차 (Table of Contents)

• 요약
• ABSTRACT
• Ⅰ. 서론
• Ⅱ. 해시함수 LSH
• Ⅲ. LSH의 구조 분석 및 최적 병렬 구현
• Ⅳ. LSH 병렬화의 성능 측정 결과
• Ⅴ. 결론
• References

참고문헌 (Reference)

1 "eBASH"

2 "SHA-3 STANDARDIZATION"

3 Kim, D. C., "Lsh: A new fast secure hash function family" 286-313, 2014

4 "Korea cryptographic forum"

5 Bertoni, G., "Keccak sponge function family main document" 3 : 30-, 2009

6 "Intel Intrinsics Guide"

7 X. Wang, "Finding Collisions in the Full SHA-1" 17-36, 2005

8 NIST, "DRAFT FIPS PUB 202"

9 X. Wang, "Cryptanalysis on SHA-1" 2005

10 "CRYPTOGRAPHIC HASH AND SHA-3STANDARD DEVELOPMENT"