LSH (해시 함수)

'''LSH'''는 대한민국이 PC, 스마트 디바이스 등 범용 CPU에서 무결성을 제공하기 위해 2014년에 개발한 해시 함수이다. 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)을 가지는 것이 증명되었다.
또한, 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
분류:암호화 해시 함수