'''LSH'''는 대한민국이 PC, 스마트 디바이스 범용 CPU에서 무결성을 제공하기 위해 2014년에 개발한 해시 함수이다. LSH는 대한민국 암호모듈 검증제도 검증대상 암호 알고리즘이며, 대한민국 국가 표준(KS 3262)이다. == 알고리즘 == 해시 함수 LSH의 전체 구조는 아래와 같다. 해시 함수 LSH 전체 구조 LSH는 입력 메시지에 대해 다음과 같은 단계를 거쳐 해시값을 출력한다. 입력 메시지를 메시지 블록 비트 길이의 배수가 되도록 패딩을 후, 이를 메시지 블록 단위로 분할한다. 그리고 연결 변수를 초기화한다. 32워드 배열 메시지 블록을 압축 함수의 입력으로 하여 얻은 출력값으로 연결 변수를 갱신하며, 이를 마지막 메시지 블록을 처리할 때까지 반복하여 메시지를 압축한다. 압축 과정을 통해 연결 변수에 최종 저장된 값으로부터 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 초기값 +LSH-512-256 초기값 +LSH-512-384 초기값 +LSH-512-512 초기값 ===압축=== 초기화 단계에서 생성된 개의 메시지 블록은 압축 단계에서 순차적으로 압축 함수(compression function) 입력값으로 사용된다. 압축 함수 연결 변수 메시지 블록 입력으로 받아 연결 변수 반환한다. 압축 함수는 다음 가지 함수로 구성된다. 메시지 확장 함수 메시지 덧셈 함수 섞음 함수 워드 단위 치환 압축 함수의 전체 구조를 도시하면 다음 그림과 같다. 해시 함수 LSH 압축 함수 압축 함수 입력값 메시지 블록 메시지 확장 함수 MsgExp를 거쳐 개의 16워드 크기 데이터 확장된다. 이어서 16워드 크기의 임시 변수 할당한 후, 순차적으로 단계 함수(step function) 통해 데이터 처리하면서 갱신한다. 단계 함수를 거쳐 저장된 값은 MsgAdd 함수를 통해 처리된 연결 변수 입력된다. 이러한 압축 함수 처리 절차는 다음과 같다. '''function''' 압축 함수 '''input:''' 연결 변수 ()와 메시지 블록 () '''output:''' 연결 변수 () '''procedure''' '''for''' '''to''' '''do''' '''end for''' '''return''' 압축 함수에서 순차적으로 처리하는 단계 함수 다음과 같다. 단계 함수의 전체 구조는 다음 그림과 같다. 해시 함수 LSH의 번째 단계 함수 ====메시지 확장 함수 MsgExp==== 압축 함수에 입력된 메시지 블록 대해, 메시지 확장 함수 MsgExp는 개의 16워드 길이의 데이터 생성한다. 생성 방법은 다음과 같다. 함수 다음과 같이 정의된 상의 치환이다. 상의 치환 10 11 12 13 14 15 11 10 15 12 13 14 ====메시지 덧셈 함수 MsgAdd==== 개의 16워드 길이의 변수 입력으로 받아 16워드 길이의 결과값을 출력하는 메시지 덧셈 함수 다음과 같이 정의한다. ====섞음 함수 Mix==== 섞음 함수 16워드 길이의 변수 입력으로 받아 개의 워드 쌍으로 구성한 아래와 같이 각각을 섞어 갱신한다. 여기에서 워드 처리하는 부분 섞음 함수로 다음과 같다. '''function''' 부분 섞음 함수 '''input:''' 워드 '''output:''' 워드 '''procedure''' ;; ;; ;; '''return''' 부분 섞음 함수 도식화하면 다음 그림과 같다. 해시 함수 LSH의 부분 섞음 함수 섞음 함수 사용되는 비트 순환량 다음 표와 같다. 비트 순환량 짝수 단계와 홀수 단계에서 다른 값이 적용된다. +비트 순환량 32 짝수 29 16 24 24 16 홀수 17 64 짝수 23 59 16 32 48 24 40 56 홀수 그리고 8워드 길이의 단계 상수 먼저 아래 표와 같이 정의한 후, 나머지 개의 상수 같이 유도한다. +초기 단계 상수 917caf90 6c1b10a2 6f352943 cf778243 2ceb7472 29e96ff2 8a9ba428 2eeb2642 ====워드 단위 치환 WordPerm==== 워드 단위 치환 16워드 길이의 변수 입력으로 받아 16워드 길이의 결과값을 출력한다. 이때, 사용되는 함수 다음 표와 같이 정의된 상의 치환이다. 상의 치환 10 11 12 13 14 15 12 15 14 13 11 10 ===완료=== 완료 함수 압축 과정의 결과로 생성된 마지막 연결 변수 적용되어 비트 길이의 해시값 생성한다. 8워드 길이의 변수, 바이트 길이의 변수라고 하면, 출력 함수 다음 절차를 수행한다. 이때, 임의의 워드 대해 때, 비트열 표현에서 부분 비트열 나타낸다. 그리고 임의의 비트열 대해 때, 부분 비트열 나타낸다. == 안전성 == LSH는 현재까지 알려진 모든 해시 함수 공격에 대해 안전하다. LSH는 ideal cipher model 하에서 쿼리의 수가 충돌 가지며, 쿼리의 수가 역상 제2-역상 가지는 것이 증명되었다. 또한, 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 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 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진수로 표현되어 있다. 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 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 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 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 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 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 3262, 해시 함수 LSH == 참고 문헌 == 분류:암호화 해시 함수