Loading AI tools
위키백과, 무료 백과사전
LSH는 대한민국이 PC, 스마트 디바이스 등 범용 CPU에서 무결성을 제공하기 위해 2014년에 개발한 해시 함수이다.[1] LSH는 대한민국 암호모듈 검증제도 검증대상 암호 알고리즘이며, 대한민국 국가 표준(KS X 3262)이다.
해시 함수 LSH의 전체 구조는 아래와 같다.
LSH는 입력 메시지에 대해 다음과 같은 세 단계를 거쳐 해시값을 출력한다.
; 로부터 메시지 블록 생성; ; for to do ; end for ; return ; |
해시 함수 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진수로 표현되어 있다.
068608D3 | 62D8F7A7 | D76652AB | 4C600A43 | BDC40AA8 | 1ECA0B68 | DA1A89BE | 3147D354 |
707EB4F9 | F65B3862 | 6B0B2ABE | 56B8EC0A | CF237286 | EE0D1727 | 33636595 | 8BB8D05F |
46A10F1F | FDDCE486 | B41443A8 | 198E6B9D | 3304388D | B0F5A3C7 | B36061C4 | 7ADBD553 |
105D5378 | 2F74DE54 | 5C2F2D95 | F2553FBE | 8051357A | 138668C8 | 47AA4484 | E01AFB41 |
0C401E9FE8813A55 | 4A5F446268FD3D35 | FF13E452334F612A | F8227661037E354A |
A5F223723C9CA29D | 95D965A11AED3979 | 01E23835B9AB02CC | 52D49CBAD5B30616 |
9E5C2027773F4ED3 | 66A5C8801925B701 | 22BBC85B4C6779D9 | C13171A42C559C23 |
31E2B67D25BE3813 | D522C4DEED8E4D83 | A79F5509B43FBAFE | E00D2CD88B4B6C6A |
6DC57C33DF989423 | D8EA7F6E8342C199 | 76DF8356F8603AC4 | 40F1B44DE838223A |
39FFE7CFC31484CD | 39C4326CC5281548 | 8A2FF85A346045D8 | FF202AA46DBDD61E |
CF785B3CD5FCDB8B | 1F0323B64A8150BF | FF75D972F29EA355 | 2E567F30BF1CA9E1 |
B596875BF8FF6DBA | FCCA39B089EF4615 | ECFF4017D020B4B6 | 7E77384C772ED802 |
53156A66292808F6 | B2C4F362B204C2BC | B84B7213BFA05C4E | 976CEB7C1B299F73 |
DF0CC63C0570AE97 | DA4441BAA486CE3F | 6559F5D9B5F2ACC2 | 22DACF19B4B52A16 |
BBCDACEFDE80953A | C9891A2879725B3E | 7C9FE6330237E440 | A30BA550553F7431 |
BB08043FB34E3E30 | A0DEC48D54618EAD | 150317267464BC57 | 32D1501FDE63DC93 |
ADD50F3C7F07094E | E3F3CEE8F9418A4F | B527ECDE5B3D0AE9 | 2EF6DEC68076F501 |
8CB994CAE5ACA216 | FBB9EAE4BBA48CC7 | 650A526174725FEA | 1F9A61A73F8D8085 |
B6607378173B539B | 1BC99853B0C0B9ED | DF727FC19B182D47 | DBEF360CF893A457 |
4981F5E570147E80 | D00C4490CA7D3E30 | 5D73940C0E4AE1EC | 894085E2EDB2D819 |
초기화 단계에서 생성된 개의 메시지 블록은 압축 단계에서 순차적으로 압축 함수(compression function) 의 입력값으로 사용된다. 압축 함수 는 연결 변수 와 메시지 블록 를 입력으로 받아 연결 변수 을 반환한다.
압축 함수는 다음 네 가지 함수로 구성된다.
압축 함수의 전체 구조를 도시하면 다음 그림과 같다.
압축 함수 입력값 중 메시지 블록 는 메시지 확장 함수 MsgExp를 거쳐 개의 16워드 크기 데이터 로 확장된다. 이어서 16워드 크기의 임시 변수 에 를 할당한 후, 순차적으로 단계 함수(step function) 를 통해 데이터 를 처리하면서 를 갱신한다. 단계 함수를 거쳐 에 저장된 값은 MsgAdd 함수를 통해 처리된 후 번 째 연결 변수 에 입력된다. 이러한 압축 함수 처리 절차는 다음과 같다.
; ; for to do ; end for ; return ; |
압축 함수에서 순차적으로 를 처리하는 단계 함수 는 다음과 같다.
단계 함수의 전체 구조는 다음 그림과 같다.
압축 함수에 입력된 메시지 블록 에 대해, 메시지 확장 함수 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 |
두 개의 16워드 길이의 변수 와 를 입력으로 받아 16워드 길이의 결과값을 출력하는 메시지 덧셈 함수 는 다음과 같이 정의한다.
섞음 함수 는 16워드 길이의 변수 를 입력으로 받아 두 개의 워드 , 을 쌍으로 구성한 후 아래와 같이 각각을 섞어 를 갱신한다.
여기에서 은 두 개 워드 , 를 처리하는 부분 섞음 함수로 다음과 같다.
;; ; ;; ;; return , |
부분 섞음 함수 를 도식화하면 다음 그림과 같다.
섞음 함수 에 사용되는 비트 순환량 , , 은 다음 표와 같다. 비트 순환량 , 는 짝수 단계와 홀수 단계에서 다른 값이 적용된다.
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 |
워드 단위 치환 은 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 메시지에 대한 해시값 계산 속도를 보여준다.
Platform | P1[lower-alpha 1] | P2[lower-alpha 2] | P3[lower-alpha 3] | P4[lower-alpha 4] | P5[lower-alpha 5] | P6[lower-alpha 6] | P7[lower-alpha 7] | P8[lower-alpha 8] |
---|---|---|---|---|---|---|---|---|
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 플랫폼에서 성능을 측정한 결과이다.
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와 몇 종류의 해시 함수 성능을 비교한 것이다.
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는 아래 표준으로 제정되어 있다.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.