LSH (해시 함수)

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

## 알고리즘

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

600픽셀|섬네일|center|해시 함수 LSH 전체 구조

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

* 초기화(Initialization): 입력 메시지를 메시지 블록 비트 길이의 배수가 되도록 패딩을 한 후, 이를 메시지 블록 단위로 분할한다. 그리고 연결 변수를  \textsf{IV} 로 초기화한다.

* 압축(Compression): 32워드 배열 메시지 블록을 압축 함수의 입력으로 하여 얻은 출력값으로 연결 변수를 갱신하며, 이를 마지막 메시지 블록을 처리할 때까지 반복하여 메시지를 압축한다.

* 완료(Finalization): 압축 과정을 통해 연결 변수에 최종 저장된 값으로부터 n비트 길이의 해시 함수 출력값을 생성한다.

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

### 초기화

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

덧붙이기를 마친 메시지를 m_p = m_0 \| m_1 \| \ldots \| m_{(32wt-1)}이라고 하자. 이때 m_p는 4wt 바이트 배열 m_a = (m[0], \ldots , m[4wt-1])로 볼 수 있다. 여기에서 m[k] = m_{8k} \| m_{(8k+1)} \| \ldots \| m_{(8k+7)} (0 \le k \le (4wt-1))이다. 바이트 배열 m_a는 다음과 같이 32t 워드 배열  \textsf{M} = (M[0], \ldots , M[32t-1])으로 변환할 수 있다.

M[s] \leftarrow m[ws/8+(w/8-1)] \| \ldots \| m[ws/8+1] \| m[ws/8] (0 \le s \le (32t-1))

이어서 워드 배열  \textsf{M} 으로부터 다음과 같은 규칙에 따라 t개 메시지 블록  \textsf{M}^{(0)} ,  \textsf{M}^{(1)} , \ldots ,  \textsf{M}^{(t-1)}을 구성할 수 있다.

 \textsf{M}^{(i)} \leftarrow (M[32i], M[32i+1], \ldots , M[32i+31]) (0 \le i \le (t-1))

연결 변수  \textsf{CV}^{(0)} (\in \mathcal{W}^{16})는 초기값을 이용하여 다음과 같이 배열 색인별로 값을 할당하는 방식으로 초기화한다.
이때,  \mathcal{W}^t 는  t \ge 1 일 때  t 개 워드 배열의 전체 집합을 나타낸다.

 \textsf{CV}^{(0)}[l] \leftarrow \textsf{IV}[l]  (0 \le l \le 15)

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

### 압축

초기화 단계에서 생성된 t개의 메시지 블록은 압축 단계에서 순차적으로 압축 함수(compression function)  \textrm{CF} : \mathcal{W}^{16} \times \mathcal{W}^{32} \rightarrow  \mathcal{W}^{16}의 입력값으로 사용된다.
압축 함수  \textrm{CF} 는 연결 변수  \textsf{CV}^{(i)}(\in \mathcal{W}^{16})와 메시지 블록  \textsf{M}^{(i)} (\in \mathcal{W}^{32})를 입력으로 받아 연결 변수  \textsf{CV}^{(i+1)} (\in \mathcal{W}^{16})을 반환한다.

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

* 메시지 확장 함수 \textrm{MsgExp}: \mathcal{W}^{32} \rightarrow  \mathcal{W}^{16(Ns+1)}
* 메시지 덧셈 함수 \textrm{MsgAdd}: \mathcal{W}^{16} \times \mathcal{W}^{16} \rightarrow  \mathcal{W}^{16}
* 섞음 함수 \textrm{Mix}_j: \mathcal{W}^{16} \rightarrow  \mathcal{W}^{16}
* 워드 단위 치환 \textrm{WordPerm}: \mathcal{W}^{16} \rightarrow  \mathcal{W}^{16}

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

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

압축 함수 입력값 중 메시지 블록  \textsf{M}^{(i)} 는 메시지 확장 함수 MsgExp를 거쳐 (N_s+1)개의 16워드 크기 데이터  \textsf{M}_j^{(i)} (0 \le j \le N_s)로 확장된다.
이어서 16워드 크기의 임시 변수  \textsf{T} = (T[0], \ldots , T[15])에  \textsf{CV}^{(i)}를 할당한 후, 순차적으로 단계 함수(step function) \textrm{Step}_j를 통해 데이터  \textsf{M}_j^{(i)} 를 처리하면서  \textsf{T} 를 갱신한다.
단계 함수를 거쳐  \textsf{T} 에 저장된 값은 MsgAdd 함수를 통해 처리된 후 (i+1)번 째 연결 변수  \textsf{CV}^{(i+1)}에 입력된다.
이러한 압축 함수 처리 절차는 다음과 같다.

압축 함수에서 순차적으로  \textsf{M}_j^{(i)} 를 처리하는 단계 함수 \textrm{Step}_j : \mathcal{W}^{16} \times \mathcal{W}^{16} \rightarrow  \mathcal{W}^{16}는 다음과 같다.

\textrm{Step}_j := \textrm{WordPerm} \circ \textrm{Mix}_j \circ \textrm{MsgAdd} (0 \le j \le (N_s-1))

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

600픽셀|섬네일|center|해시 함수 LSH의 <math> j </math> 번째 단계 함수 <math> \textrm{Step}_j </math>

#### 메시지 확장 함수 MsgExp

압축 함수에 입력된 메시지 블록  \textsf{M}^{(i)} = (M^{(i)}[0], \ldots , M^{(i)}[31]) 에 대해, 메시지 확장 함수 MsgExp는  (N_s+1) 개의 16워드 길이의 데이터  \textsf{M}_j^{(i)} (0 \le j \le N_s) 를 생성한다.
생성 방법은 다음과 같다.

*  \textsf{M}_0^{(i)} \leftarrow (M^{(i)}[0], M^{(i)}[1], \ldots , M^{(i)}[15])
*  \textsf{M}_1^{(i)} \leftarrow (M^{(i)}[16], M^{(i)}[17], \ldots , M^{(i)}[31])
*  \textsf{M}_j^{(i)}[l] \leftarrow \textsf{M}_{j-1}^{(i)}[l] \boxplus \textsf{M}_{j-2}^{(i)}[\tau(l)] (0 \le l \le 15, \ 2 \le j \le N_s)

함수 \tau는 다음과 같이 정의된 \mathbb{Z}_{16} 상의 치환이다.

#### 메시지 덧셈 함수 MsgAdd

두 개의 16워드 길이의 변수  \textsf{X} = (X[0], \ldots , X[15]) 와  \textsf{Y} = (Y[0], \ldots , Y[15]) 를 입력으로 받아 16워드 길이의 결과값을 출력하는 메시지 덧셈 함수 \textrm{MsgAdd} : \mathcal{W}^{16} \times \mathcal{W}^{16} \rightarrow  \mathcal{W}^{16}는 다음과 같이 정의한다.

\textrm{MsgAdd}( \textsf{X}, \textsf{Y} ) := (X[0] \oplus Y[0], \ldots , X[15] \oplus Y[15]) 

#### 섞음 함수 Mix

섞음 함수 \textrm{Mix}_j: \mathcal{W}^{16} \rightarrow  \mathcal{W}^{16}는 16워드 길이의 변수  \textsf{T} = (T[0], \ldots , T[15]) 를 입력으로 받아 두 개의 워드 T[l], T[l+8] (0 \le l \le 7)을 쌍으로 구성한 후 아래와 같이 각각을 섞어  \textsf{T} 를 갱신한다.

(T[l], T[l+8]) \leftarrow \textrm{Mix}_{j,l}(T[l], T[l+8]) (0 \le l \le 7)

여기에서 \textrm{Mix}_{j,l} : \mathcal{W}^2 \rightarrow  \mathcal{W}^2은 두 개 워드 X, Y를 처리하는 부분 섞음 함수로 다음과 같다.

부분 섞음 함수  \textrm{Mix}_{j,l} 를 도식화하면 다음 그림과 같다.

250픽셀|섬네일|center|해시 함수 LSH의 부분 섞음 함수

섞음 함수 \textrm{Mix}_{j,l}에 사용되는 비트 순환량 \alpha_j, \beta_j, \gamma_l은 다음 표와 같다.
비트 순환량 \alpha_j, \beta_j는 짝수 단계와 홀수 단계에서 다른 값이 적용된다.

그리고 8워드 길이의 단계 상수  \textsf{SC}_j = (SC_j[0], \ldots , SC_j[7]) 는 먼저  \textsf{SC}_0 를 아래 표와 같이 정의한 후, 나머지  (N_s-1) 개의 상수  \textsf{SC}_j 를  SC_j[l] \leftarrow SC_{j-1}[l] \boxplus SC_{j-1}[l]^{\lll8} (0 \le l \le 7, 1 \le j \le (N_s-1)) 와 같이 유도한다.

#### 워드 단위 치환 WordPerm

워드 단위 치환  \textrm{WordPerm} : \mathcal{W}^{16} \rightarrow  \mathcal{W}^{16} 은 16워드 길이의 변수  \textsf{X} = (X[0], \ldots , X[15]) 를 입력으로 받아 16워드 길이의 결과값을 출력한다.

 \textrm{WordPerm}( \textsf{X}) := (X[\sigma(0)], \ldots , X[\sigma(15)]) 

이때, 사용되는 함수 \sigma는 다음 표와 같이 정의된 \mathbb{Z}_{16} 상의 치환이다.

### 완료

완료 함수 \textrm{FIN}_n : \mathcal{W}^{16} \rightarrow  \{0, 1\}^{n}은 압축 과정의 결과로 생성된 마지막 연결 변수  \textsf{CV}^{(t)} = ( CV^{(t)}[0], \ldots , CV^{(t)}[15])에 적용되어 n비트 길이의 해시값 h를 생성한다.
 \textsf{H} = (H[0], \ldots , H[7])를 8워드 길이의 변수,  \textsf{h}_\textsf{b} = (h_b[0], \ldots , h_b[w-1])는 w 바이트 길이의 변수라고 하면, 출력 함수 \textrm{FIN}_n은 다음 절차를 수행한다.

* H[l] \leftarrow CV^{(t)}[l] \oplus CV^{(t)}[l+8] (0 \le l \le 7)
* h_b[s] \leftarrow H[\lfloor 8s/w\rfloor]^{\ggg(8s \mod w)}_{[7:0]} (0 \le s \le (w-1))
* h \leftarrow (h_b[0] \| \ldots \| h_b[w-1])_{[0:n-1]}

이때, 임의의 워드  X 에 대해  r \ge s 일 때,  X_{[r:s]} 는  X 의 비트열 표현에서 부분 비트열  x_r \| x_{r-1} \| \ldots \| x_s 를 나타낸다.
그리고 임의의 비트열  x 에 대해  r \le s 일 때,  x_{[r:s]} 는  x 의 부분 비트열  x_r \| x_{r+1} \| \ldots \| x_s 를 나타낸다.

## 안전성

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

## 구현 성능

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

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

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

## 테스트 벡터

해시 함수 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

## 각주

분류:암호화 해시 함수