본문으로 이동

LSH (해시 함수)

위키백과, 우리 모두의 백과사전.

LSH는 대한민국이 PC, 스마트 디바이스 등 범용 CPU에서 무결성을 제공하기 위해 2014년에 개발한 해시 함수이다.[1] LSH는 대한민국 암호모듈 검증제도 검증대상 암호 알고리즘이며, 대한민국 국가 표준(KS X 3262)이다.

알고리즘

[편집]

해시 함수 LSH의 전체 구조는 아래와 같다.

해시 함수 LSH 전체 구조

LSH는 입력 메시지에 대해 다음과 같은 세 단계를 거쳐 해시값을 출력한다.

  • 초기화(Initialization): 입력 메시지를 메시지 블록 비트 길이의 배수가 되도록 패딩을 한 후, 이를 메시지 블록 단위로 분할한다. 그리고 연결 변수를 로 초기화한다.
  • 압축(Compression): 32워드 배열 메시지 블록을 압축 함수의 입력으로 하여 얻은 출력값으로 연결 변수를 갱신하며, 이를 마지막 메시지 블록을 처리할 때까지 반복하여 메시지를 압축한다.
  • 완료(Finalization): 압축 과정을 통해 연결 변수에 최종 저장된 값으로부터 n비트 길이의 해시 함수 출력값을 생성한다.
  • function 해시 함수 LSH
  • input: 메시지
  • output: 해시값
  • procedure

;

로부터 메시지 블록 생성;

;

for to do

;

end for

;

return ;

해시 함수 LSH의 규격은 다음 표와 같다.

해시 함수 LSH 규격
구분 출력 비트 길이 () 압축 함수의 단계 수 () 연결 변수 비트 길이 메시지 블록 비트 길이 워드 비트 길이 ()
LSH-256-224 224 26 512 1024 32
LSH-256-256 256
LSH-512-224 224 28 1024 2048 64
LSH-512-256 256
LSH-512-384 384
LSH-512-512 512


초기화

[편집]

해시 함수의 입력 메시지를 이라 하자. 먼저 은 덧붙이기(padding) 과정을 거친다. 덧붙이기 과정은 의 끝에 비트 ‘1’을 덧붙인 후, 전체 길이가 비트가 될 때까지 비트 ‘0’을 덧붙인다. 여기에서 이다.

덧붙이기를 마친 메시지를 이라고 하자. 이때 바이트 배열 로 볼 수 있다. 여기에서 이다. 바이트 배열 는 다음과 같이 워드 배열 으로 변환할 수 있다.

이어서 워드 배열 으로부터 다음과 같은 규칙에 따라 개 메시지 블록 , , \ldots , 을 구성할 수 있다.

연결 변수 는 초기값을 이용하여 다음과 같이 배열 색인별로 값을 할당하는 방식으로 초기화한다. 이때, 일 때 개 워드 배열의 전체 집합을 나타낸다.

초기값은 다음과 같다. 모든 값은 16진수로 표현되어 있다.

LSH-256-224 초기값
068608D3 62D8F7A7 D76652AB 4C600A43 BDC40AA8 1ECA0B68 DA1A89BE 3147D354
707EB4F9 F65B3862 6B0B2ABE 56B8EC0A CF237286 EE0D1727 33636595 8BB8D05F
LSH-256-256 초기값
46A10F1F FDDCE486 B41443A8 198E6B9D 3304388D B0F5A3C7 B36061C4 7ADBD553
105D5378 2F74DE54 5C2F2D95 F2553FBE 8051357A 138668C8 47AA4484 E01AFB41
LSH-512-224 초기값
0C401E9FE8813A55 4A5F446268FD3D35 FF13E452334F612A F8227661037E354A
A5F223723C9CA29D 95D965A11AED3979 01E23835B9AB02CC 52D49CBAD5B30616
9E5C2027773F4ED3 66A5C8801925B701 22BBC85B4C6779D9 C13171A42C559C23
31E2B67D25BE3813 D522C4DEED8E4D83 A79F5509B43FBAFE E00D2CD88B4B6C6A
LSH-512-256 초기값
6DC57C33DF989423 D8EA7F6E8342C199 76DF8356F8603AC4 40F1B44DE838223A
39FFE7CFC31484CD 39C4326CC5281548 8A2FF85A346045D8 FF202AA46DBDD61E
CF785B3CD5FCDB8B 1F0323B64A8150BF FF75D972F29EA355 2E567F30BF1CA9E1
B596875BF8FF6DBA FCCA39B089EF4615 ECFF4017D020B4B6 7E77384C772ED802
LSH-512-384 초기값
53156A66292808F6 B2C4F362B204C2BC B84B7213BFA05C4E 976CEB7C1B299F73
DF0CC63C0570AE97 DA4441BAA486CE3F 6559F5D9B5F2ACC2 22DACF19B4B52A16
BBCDACEFDE80953A C9891A2879725B3E 7C9FE6330237E440 A30BA550553F7431
BB08043FB34E3E30 A0DEC48D54618EAD 150317267464BC57 32D1501FDE63DC93
LSH-512-512 초기값
ADD50F3C7F07094E E3F3CEE8F9418A4F B527ECDE5B3D0AE9 2EF6DEC68076F501
8CB994CAE5ACA216 FBB9EAE4BBA48CC7 650A526174725FEA 1F9A61A73F8D8085
B6607378173B539B 1BC99853B0C0B9ED DF727FC19B182D47 DBEF360CF893A457
4981F5E570147E80 D00C4490CA7D3E30 5D73940C0E4AE1EC 894085E2EDB2D819

압축

[편집]

초기화 단계에서 생성된 개의 메시지 블록은 압축 단계에서 순차적으로 압축 함수(compression function) 의 입력값으로 사용된다. 압축 함수 는 연결 변수 와 메시지 블록 를 입력으로 받아 연결 변수 을 반환한다.

압축 함수는 다음 네 가지 함수로 구성된다.

  • 메시지 확장 함수
  • 메시지 덧셈 함수
  • 섞음 함수
  • 워드 단위 치환

압축 함수의 전체 구조를 도시하면 다음 그림과 같다.

해시 함수 LSH 압축 함수

압축 함수 입력값 중 메시지 블록 는 메시지 확장 함수 MsgExp를 거쳐 개의 16워드 크기 데이터 로 확장된다. 이어서 16워드 크기의 임시 변수 를 할당한 후, 순차적으로 단계 함수(step function) 를 통해 데이터 를 처리하면서 를 갱신한다. 단계 함수를 거쳐 에 저장된 값은 MsgAdd 함수를 통해 처리된 후 번 째 연결 변수 에 입력된다. 이러한 압축 함수 처리 절차는 다음과 같다.

  • function 압축 함수
  • input: 연결 변수 ()와 메시지 블록 ()
  • output: 연결 변수 ()
  • procedure

;

;

for to do

;

end for

;

return ;

압축 함수에서 순차적으로 를 처리하는 단계 함수 는 다음과 같다.

단계 함수의 전체 구조는 다음 그림과 같다.

해시 함수 LSH의 번째 단계 함수

메시지 확장 함수 MsgExp

[편집]

압축 함수에 입력된 메시지 블록 에 대해, 메시지 확장 함수 MsgExp는 개의 16워드 길이의 데이터 를 생성한다. 생성 방법은 다음과 같다.

함수 는 다음과 같이 정의된 상의 치환이다.

상의 치환
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
3 2 0 1 7 4 5 6 11 10 8 9 15 12 13 14

메시지 덧셈 함수 MsgAdd

[편집]

두 개의 16워드 길이의 변수 를 입력으로 받아 16워드 길이의 결과값을 출력하는 메시지 덧셈 함수 는 다음과 같이 정의한다.

섞음 함수 Mix

[편집]

섞음 함수 는 16워드 길이의 변수 를 입력으로 받아 두 개의 워드 , 을 쌍으로 구성한 후 아래와 같이 각각을 섞어 를 갱신한다.

여기에서 은 두 개 워드 , 를 처리하는 부분 섞음 함수로 다음과 같다.

  • function 부분 섞음 함수
  • input: 워드 ,
  • output: 워드 ,
  • procedure

;;

;

;;

;;

return ,

부분 섞음 함수 를 도식화하면 다음 그림과 같다.

해시 함수 LSH의 부분 섞음 함수

섞음 함수 에 사용되는 비트 순환량 , , 은 다음 표와 같다. 비트 순환량 , 는 짝수 단계와 홀수 단계에서 다른 값이 적용된다.

비트 순환량 , ,
32 짝수 29 1 0 8 16 24 24 16 8 0
홀수 5 17
64 짝수 23 59 0 16 32 48 8 24 40 56
홀수 7 3

그리고 8워드 길이의 단계 상수 는 먼저 를 아래 표와 같이 정의한 후, 나머지 개의 상수 와 같이 유도한다.

초기 단계 상수
917caf90 97884283c938982a
6c1b10a2 ba1fca93533e2355
6f352943 c519a2e87aeb1c03
cf778243 9a0fc95462af17b1
2ceb7472 fc3dda8ab019a82b
29e96ff2 02825d079a895407
8a9ba428 79f2d0a7ee06a6f7
2eeb2642 d76d15eed9fdf5fe

워드 단위 치환 WordPerm

[편집]

워드 단위 치환 은 16워드 길이의 변수 를 입력으로 받아 16워드 길이의 결과값을 출력한다.

이때, 사용되는 함수 는 다음 표와 같이 정의된 상의 치환이다.

상의 치환
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
6 4 5 7 12 15 14 13 2 0 1 3 8 11 10 9

완료

[편집]

완료 함수 은 압축 과정의 결과로 생성된 마지막 연결 변수 에 적용되어 비트 길이의 해시값 를 생성한다. 를 8워드 길이의 변수, 바이트 길이의 변수라고 하면, 출력 함수 은 다음 절차를 수행한다.

이때, 임의의 워드 에 대해 일 때, 의 비트열 표현에서 부분 비트열 를 나타낸다. 그리고 임의의 비트열 에 대해 일 때, 의 부분 비트열 를 나타낸다.

안전성

[편집]

LSH는 현재까지 알려진 모든 해시 함수 공격에 대해 안전하다. LSH는 ideal cipher model 하에서 쿼리의 수가 일 때 충돌 저항성(collision-resistance)을 가지며, 쿼리의 수가 일 때 역상 저항성(preimage-resistance) 및 제2-역상 저항성(second-preimage-resistance)을 가지는 것이 증명되었다[1]. 또한, LSH-256의 경우 13스텝, LSH-512의 경우 14스텝이 알려진 모든 공격에 대해 안전함이 알려져 있어 50% 이상의 안전성 마진을 제공한다[1].

구현 성능

[편집]

LSH는 다양한 소프트웨어 플랫폼에서 SHA-2/3 대비 빠른 속도를 보유하고 있다. 아래 표는 다양한 플랫폼 상에서 LSH의 1MB 메시지에 대한 해시값 계산 속도를 보여준다.

LSH의 1MB 메시지에 대한 해시값 계산 속도 (cycles/byte)[1]
Platform P1[a] P2[b] P3[c] P4[d] P5[e] P6[f] P7[g] P8[h]
LSH-256- 3.60 3.86 5.26 3.89 11.17 15.03 15.28 14.84
LSH-512- 2.39 5.04 7.76 5.52 8.94 18.76 19.00 18.10
  1. Intel Core i7-4770K @ 3.5GHz (Haswell), Ubuntu 12.04 64-bit, GCC 4.8.1 with “-m64 -mavx2 -O3”
  2. Intel Core i7-2600K @ 3.40GHz (Sandy Bridge), Ubuntu 12.04 64-bit, GCC 4.8.1 with “-m64 -msse4 -O3”
  3. Intel Core 2 Quad Q9550 @ 2.83GHz (Yorkfield), Windows 7 32-bit, Visual studio 2012
  4. AMD FX-8350 @ 4GHz (Piledriver), Ubuntu 12.04 64-bit, GCC 4.8.1 with “-m64 -mxop -O3”
  5. Samsung Exynos 5250 ARM Cortex-A15 @ 1.7GHz dual core (Huins ACHRO 5250), Android 4.1.1
  6. Qualcomm Snapdragon 800 Krait 400 @ 2.26GHz quad core (LG G2), Android 4.4.2
  7. Qualcomm Snapdragon 800 Krait 400 @ 2.3GHz quad core (Samsung Galaxy S4), Android 4.2.2
  8. Qualcomm Snapdragon 400 Krait 300 @ 1.7GHz dual core (Samsung Galaxy S4 mini), Android 4.2.2

아래 표는 Haswell 기반 플랫폼에서 LSH와 몇 종류의 해시 함수 성능을 비교한 것이다. LSH는 Intel Core i7-4770k @ 3.5 GHz quad core 플랫폼에서, 다른 해시 함수는 Intel Core i5-4570S @ 2.9 GHz quad core 플랫폼에서 성능을 측정한 결과이다.

Speed benchmark of LSH, SHA-2 and the SHA-3 finalists at the platform based on Haswell CPU (cycles/byte)[1]
Algorithm Message size in bytes
long 4,096 1,536 576 64 8
LSH-256-256 3.60 3.71 3.90 4.08 8.19 65.37
Skein-512-256 5.01 5.58 5.86 6.49 13.12 104.50
Blake-256 6.61 7.63 7.87 9.05 16.58 72.50
Grøstl-256 9.48 10.68 12.18 13.71 37.94 227.50
Keccak-256 10.56 10.52 9.90 11.99 23.38 187.50
SHA-256 10.82 11.91 12.26 13.51 24.88 106.62
JH-256 14.70 15.50 15.94 17.06 31.94 257.00
LSH-512-512 2.39 2.54 2.79 3.31 10.81 85.62
Skein-512-512 4.67 5.51 5.80 6.44 13.59 108.25
Blake-512 4.96 6.17 6.82 7.38 14.81 116.50
SHA-512 7.65 8.24 8.69 9.03 17.22 138.25
Grøstl-512 12.78 15.44 17.30 17.99 51.72 417.38
JH-512 14.25 15.66 16.14 17.34 32.69 261.00
Keccak-512 16.36 17.86 18.46 20.35 21.56 171.88

아래 표는 Samsung Exynos 5250 ARM Cortex-A15 @ 1.7 GHz dual core 플랫폼에서 LSH와 몇 종류의 해시 함수 성능을 비교한 것이다.

Speed benchmark of LSH, SHA-2 and the SHA-3 finalists at the platform based on Exynos 5250 ARM Cortex-A15 CPU (cycles/byte)[1]
Algorithm Message size in bytes
long 4,096 1,536 576 64 8
LSH-256-256 11.17 11.53 12.16 12.63 22.42 192.68
Skein-512-256 15.64 16.72 18.33 22.68 75.75 609.25
Blake-256 17.94 19.11 20.88 25.44 83.94 542.38
SHA-256 19.91 21.14 23.03 28.13 90.89 578.50
JH-256 34.66 36.06 38.10 43.51 113.92 924.12
Keccak-256 36.03 38.01 40.54 48.13 125.00 1000.62
Grøstl-256 40.70 42.76 46.03 54.94 167.52 1020.62
LSH-512-512 8.94 9.56 10.55 12.28 38.82 307.98
Blake-512 13.46 14.82 16.88 20.98 77.53 623.62
Skein-512-512 15.61 16.73 18.35 22.56 75.59 612.88
JH-512 34.88 36.26 38.36 44.01 116.41 939.38
SHA-512 44.13 46.41 49.97 54.55 135.59 1088.38
Keccak-512 63.31 64.59 67.85 77.21 121.28 968.00
Grøstl-512 131.35 138.49 150.15 166.54 446.53 3518.00

테스트 벡터

[편집]

해시 함수 LSH의 테스트 벡터는 다음과 같다. 모든 값은 16진수로 표현되어 있다.

LSH-256-224("abc") = F7 C5 3B A4 03 4E 70 8E 74 FB A4 2E 55 99 7C A5 12 6B B7 62 36 88 F8 53 42 F7 37 32

LSH-256-256("abc") = 5F BF 36 5D AE A5 44 6A 70 53 C5 2B 57 40 4D 77 A0 7A 5F 48 A1 F7 C1 96 3A 08 98 BA 1B 71 47 41

LSH-512-224("abc") = D1 68 32 34 51 3E C5 69 83 94 57 1E AD 12 8A 8C D5 37 3E 97 66 1B A2 0D CF 89 E4 89

LSH-512-256("abc") = CD 89 23 10 53 26 02 33 2B 61 3F 1E C1 1A 69 62 FC A6 1E A0 9E CF FC D4 BC F7 58 58 D8 02 ED EC

LSH-512-384("abc") = 5F 34 4E FA A0 E4 3C CD 2E 5E 19 4D 60 39 79 4B 4F B4 31 F1 0F B4 B6 5F D4 5E 9D A4 EC DE 0F 27 B6 6E 8D BD FA 47 25 2E 0D 0B 74 1B FD 91 F9 FE

LSH-512-512("abc") = A3 D9 3C FE 60 DC 1A AC DD 3B D4 BE F0 A6 98 53 81 A3 96 C7 D4 9D 9F D1 77 79 56 97 C3 53 52 08 B5 C5 72 24 BE F2 10 84 D4 20 83 E9 5A 4B D8 EB 33 E8 69 81 2B 65 03 1C 42 88 19 A1 E7 CE 59 6D

구현

[편집]

C, Java, Python으로 구현된 LSH의 배포용 소스코드는 KISA 암호이용활성화 웹페이지에서 다운받을 수 있다.[2]

암호모듈 검증제도

[편집]

LSH는 2019년 대한민국 암호모듈 검증제도 검증대상 암호알고리즘 목록에 포함되었다.[3]

표준

[편집]

LSH는 아래 표준으로 제정되어 있다.

  • KS X 3262, 해시 함수 LSH[4]

각주

[편집]
  1. Kim, Dong-Chan; Hong, Deukjo; Lee, Jung-Keun; Kim, Woo-Hwan; Kwon, Daesung (2014). 〈LSH: A New Fast Secure Hash Function Family〉. 《International Conference on Information Security and Cryptology - ICISC 2014》. Lecture Notes in Computer Science 8949. Springer/Heidelberg. 286–313쪽. 
  2. “LSH 소스코드”. 
  3. “암호모듈검증”. 
  4. “e-나라 표준인증”.