LSH (해시 함수)

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

 알고리즘 

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

600픽셀|섬네일|center|해시 함수 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) 의 입력값으로 사용된다.
압축 함수 는 연결 변수 와 메시지 블록 를 입력으로 받아 연결 변수 을 반환한다.

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

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

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

600픽셀|섬네일|center|해시 함수 LSH 압축 함수

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

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

;

for  to  do

;

end for

;

return ;

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



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

600픽셀|섬네일|center|해시 함수 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 , 

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

250픽셀|섬네일|center|해시 함수 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)을 가지는 것이 증명되었다.
또한, LSH-256의 경우 13스텝, LSH-512의 경우 14스텝이 알려진 모든 공격에 대해 안전함이 알려져 있어 50% 이상의 안전성 마진을 제공한다.

 구현 성능 

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

+LSH의 1MB 메시지에 대한 해시값 계산 속도 (cycles/byte) Platform P1 P2 P3 P4 P5 P6 P7 P8 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

아래 표는 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) 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) 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 암호이용활성화 웹페이지에서 다운받을 수 있다.

 암호모듈 검증제도 

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

 표준 

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

 KS X 3262, 해시 함수 LSH

 각주 

분류:암호화 해시 함수