LSH (해시 함수)

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

알고리즘

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

해시 함수 LSH 전체 구조

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

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

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

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

function 해시 함수 LSH input: 메시지 $m$ output: 해시값 $h\in \{0,1\}^{n}$ procedure $\qquad$$m_{p}\leftarrow {\textrm {pad}}(m)$; $\qquad$$m_{p}$로부터 메시지 블록 $(M^{(0)},M^{(1)},\cdots ,M^{(t-1)})$ 생성; $\qquad$${\textsf {CV}}^{(0)}\leftarrow {\textsf {IV}}$; $\qquad$for $i=0$ to $(t-1)$ do $\qquad$$\qquad$${\textsf {CV}}^{(i+1)}\leftarrow {\textrm {CF}}({\textsf {CV}}^{(i)},M^{(i)})$; $\qquad$end for $\qquad$$h\leftarrow {\textrm {FIN}}_{n}({\textsf {CV}}^{(t)})$; $\qquad$return $h$;

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

해시 함수 LSH 규격

구분	출력 비트 길이 ($n$)	압축 함수의 단계 수 ($N_{s}$)	연결 변수 비트 길이	메시지 블록 비트 길이	워드 비트 길이 ($w$)
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

초기화

해시 함수의 입력 메시지를 $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\leq k\leq (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\leq s\leq (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\leq i\leq (t-1))$

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

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

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

LSH-256-224 초기값

${\textsf {IV}}[0]$	${\textsf {IV}}[1]$	${\textsf {IV}}[2]$	${\textsf {IV}}[3]$	${\textsf {IV}}[4]$	${\textsf {IV}}[5]$	${\textsf {IV}}[6]$	${\textsf {IV}}[7]$
068608D3	62D8F7A7	D76652AB	4C600A43	BDC40AA8	1ECA0B68	DA1A89BE	3147D354
${\textsf {IV}}[8]$	${\textsf {IV}}[9]$	${\textsf {IV}}[10]$	${\textsf {IV}}[11]$	${\textsf {IV}}[12]$	${\textsf {IV}}[13]$	${\textsf {IV}}[14]$	${\textsf {IV}}[15]$
707EB4F9	F65B3862	6B0B2ABE	56B8EC0A	CF237286	EE0D1727	33636595	8BB8D05F

LSH-256-256 초기값

${\textsf {IV}}[0]$	${\textsf {IV}}[1]$	${\textsf {IV}}[2]$	${\textsf {IV}}[3]$	${\textsf {IV}}[4]$	${\textsf {IV}}[5]$	${\textsf {IV}}[6]$	${\textsf {IV}}[7]$
46A10F1F	FDDCE486	B41443A8	198E6B9D	3304388D	B0F5A3C7	B36061C4	7ADBD553
${\textsf {IV}}[8]$	${\textsf {IV}}[9]$	${\textsf {IV}}[10]$	${\textsf {IV}}[11]$	${\textsf {IV}}[12]$	${\textsf {IV}}[13]$	${\textsf {IV}}[14]$	${\textsf {IV}}[15]$
105D5378	2F74DE54	5C2F2D95	F2553FBE	8051357A	138668C8	47AA4484	E01AFB41

LSH-512-224 초기값

${\textsf {IV}}[0]$	${\textsf {IV}}[1]$	${\textsf {IV}}[2]$	${\textsf {IV}}[3]$
0C401E9FE8813A55	4A5F446268FD3D35	FF13E452334F612A	F8227661037E354A
${\textsf {IV}}[4]$	${\textsf {IV}}[5]$	${\textsf {IV}}[6]$	${\textsf {IV}}[7]$
A5F223723C9CA29D	95D965A11AED3979	01E23835B9AB02CC	52D49CBAD5B30616
${\textsf {IV}}[8]$	${\textsf {IV}}[9]$	${\textsf {IV}}[10]$	${\textsf {IV}}[11]$
9E5C2027773F4ED3	66A5C8801925B701	22BBC85B4C6779D9	C13171A42C559C23
${\textsf {IV}}[12]$	${\textsf {IV}}[13]$	${\textsf {IV}}[14]$	${\textsf {IV}}[15]$
31E2B67D25BE3813	D522C4DEED8E4D83	A79F5509B43FBAFE	E00D2CD88B4B6C6A

LSH-512-256 초기값

${\textsf {IV}}[0]$	${\textsf {IV}}[1]$	${\textsf {IV}}[2]$	${\textsf {IV}}[3]$
6DC57C33DF989423	D8EA7F6E8342C199	76DF8356F8603AC4	40F1B44DE838223A
${\textsf {IV}}[4]$	${\textsf {IV}}[5]$	${\textsf {IV}}[6]$	${\textsf {IV}}[7]$
39FFE7CFC31484CD	39C4326CC5281548	8A2FF85A346045D8	FF202AA46DBDD61E
${\textsf {IV}}[8]$	${\textsf {IV}}[9]$	${\textsf {IV}}[10]$	${\textsf {IV}}[11]$
CF785B3CD5FCDB8B	1F0323B64A8150BF	FF75D972F29EA355	2E567F30BF1CA9E1
${\textsf {IV}}[12]$	${\textsf {IV}}[13]$	${\textsf {IV}}[14]$	${\textsf {IV}}[15]$
B596875BF8FF6DBA	FCCA39B089EF4615	ECFF4017D020B4B6	7E77384C772ED802

LSH-512-384 초기값

${\textsf {IV}}[0]$	${\textsf {IV}}[1]$	${\textsf {IV}}[2]$	${\textsf {IV}}[3]$
53156A66292808F6	B2C4F362B204C2BC	B84B7213BFA05C4E	976CEB7C1B299F73
${\textsf {IV}}[4]$	${\textsf {IV}}[5]$	${\textsf {IV}}[6]$	${\textsf {IV}}[7]$
DF0CC63C0570AE97	DA4441BAA486CE3F	6559F5D9B5F2ACC2	22DACF19B4B52A16
${\textsf {IV}}[8]$	${\textsf {IV}}[9]$	${\textsf {IV}}[10]$	${\textsf {IV}}[11]$
BBCDACEFDE80953A	C9891A2879725B3E	7C9FE6330237E440	A30BA550553F7431
${\textsf {IV}}[12]$	${\textsf {IV}}[13]$	${\textsf {IV}}[14]$	${\textsf {IV}}[15]$
BB08043FB34E3E30	A0DEC48D54618EAD	150317267464BC57	32D1501FDE63DC93

LSH-512-512 초기값

${\textsf {IV}}[0]$	${\textsf {IV}}[1]$	${\textsf {IV}}[2]$	${\textsf {IV}}[3]$
ADD50F3C7F07094E	E3F3CEE8F9418A4F	B527ECDE5B3D0AE9	2EF6DEC68076F501
${\textsf {IV}}[4]$	${\textsf {IV}}[5]$	${\textsf {IV}}[6]$	${\textsf {IV}}[7]$
8CB994CAE5ACA216	FBB9EAE4BBA48CC7	650A526174725FEA	1F9A61A73F8D8085
${\textsf {IV}}[8]$	${\textsf {IV}}[9]$	${\textsf {IV}}[10]$	${\textsf {IV}}[11]$
B6607378173B539B	1BC99853B0C0B9ED	DF727FC19B182D47	DBEF360CF893A457
${\textsf {IV}}[12]$	${\textsf {IV}}[13]$	${\textsf {IV}}[14]$	${\textsf {IV}}[15]$
4981F5E570147E80	D00C4490CA7D3E30	5D73940C0E4AE1EC	894085E2EDB2D819

압축

초기화 단계에서 생성된 $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}$

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

해시 함수 LSH 압축 함수

압축 함수 입력값 중 메시지 블록 ${\textsf {M}}^{(i)}$는 메시지 확장 함수 MsgExp를 거쳐 $(N_{s}+1)$개의 16워드 크기 데이터 ${\textsf {M}}_{j}^{(i)}$ $(0\leq j\leq 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)}$에 입력된다. 이러한 압축 함수 처리 절차는 다음과 같다.

function 압축 함수 ${\textrm {CF}}$ input: 연결 변수 ${\textsf {CV}}^{(i)}$ ($\in {\mathcal {W}}^{16}$)와 메시지 블록 ${\textsf {M}}^{(i)}$ ($\in {\mathcal {W}}^{32}$) output: 연결 변수 ${\textsf {CV}}^{(i+1)}$ ($\in {\mathcal {W}}^{16}$) procedure $\qquad$$\{{\textsf {M}}_{j}^{(i)}\}_{0\leq j\leq N_{s}}\leftarrow {\textrm {MsgExp}}\left({\textsf {M}}^{(i)}\right)$; $\qquad$${\textsf {T}}\leftarrow {\textsf {CV}}^{(i)}$; $\qquad$for $j=0$ to $(N_{s}-1)$ do $\qquad$$\qquad$${\textsf {T}}\leftarrow {\textrm {Step}}_{j}\left({\textsf {T}},{\textsf {M}}_{j}^{(i)}\right)$; $\qquad$end for $\qquad$${\textsf {CV}}^{(i+1)}\leftarrow {\textrm {MsgAdd}}\left({\textsf {T}},{\textsf {M}}_{N_{s}}^{(i)}\right)$; $\qquad$return ${\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\leq j\leq (N_{s}-1))$

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

해시 함수 LSH의 $j$ 번째 단계 함수 ${\textrm {Step}}_{j}$

메시지 확장 함수 MsgExp

압축 함수에 입력된 메시지 블록 ${\textsf {M}}^{(i)}=(M^{(i)}[0],\ldots ,M^{(i)}[31])$에 대해, 메시지 확장 함수 MsgExp는 $(N_{s}+1)$개의 16워드 길이의 데이터 ${\textsf {M}}_{j}^{(i)}$ $(0\leq j\leq 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\leq l\leq 15,\ 2\leq j\leq N_{s})$

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

$\mathbb {Z} _{16}$ 상의 치환 $\tau$

$l$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
$\tau (l)$	3	2	0	1	7	4	5	6	11	10	8	9	15	12	13	14

메시지 덧셈 함수 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\leq l\leq 7)$을 쌍으로 구성한 후 아래와 같이 각각을 섞어 ${\textsf {T}}$를 갱신한다.

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

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

function 부분 섞음 함수 ${\textrm {Mix}}_{j,l}$ input: 워드 $X$, $Y$ output: 워드 $X$, $Y$ procedure $\qquad$$X\leftarrow X\boxplus Y$;$\qquad X\leftarrow X^{\lll \alpha _{j}}$; $\qquad$$X\leftarrow X\oplus SC_{j}[l]$; $\qquad$$Y\leftarrow X\boxplus Y$;$\qquad Y\leftarrow Y^{\lll \beta _{j}}$; $\qquad$$X\leftarrow X\boxplus Y$;$\qquad Y\leftarrow Y^{\lll \gamma _{l}}$; $\qquad$return $X$, $Y$

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

해시 함수 LSH의 부분 섞음 함수

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

비트 순환량 $\alpha _{j}$, $\beta _{j}$, $\gamma _{l}$

$w$	$j$	$\alpha _{j}$	$\beta _{j}$	$\gamma _{0}$	$\gamma _{1}$	$\gamma _{2}$	$\gamma _{3}$	$\gamma _{4}$	$\gamma _{5}$	$\gamma _{6}$	$\gamma _{7}$
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워드 길이의 단계 상수 ${\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]^{\lll 8}$ $(0\leq l\leq 7,1\leq j\leq (N_{s}-1))$와 같이 유도한다.

초기 단계 상수

	$w=32$	$w=64$
$SC_{0}[0]$	917caf90	97884283c938982a
$SC_{0}[1]$	6c1b10a2	ba1fca93533e2355
$SC_{0}[2]$	6f352943	c519a2e87aeb1c03
$SC_{0}[3]$	cf778243	9a0fc95462af17b1
$SC_{0}[4]$	2ceb7472	fc3dda8ab019a82b
$SC_{0}[5]$	29e96ff2	02825d079a895407
$SC_{0}[6]$	8a9ba428	79f2d0a7ee06a6f7
$SC_{0}[7]$	2eeb2642	d76d15eed9fdf5fe

워드 단위 치환 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}$ 상의 치환이다.

$\mathbb {Z} _{16}$ 상의 치환 $\sigma$

$l$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
$\sigma (l)$	6	4	5	7	12	15	14	13	2	0	1	3	8	11	10	9

완료

완료 함수 ${\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\leq l\leq 7)$
• $h_{b}[s]\leftarrow H[\lfloor 8s/w\rfloor ]_{[7:0]}^{\ggg (8s\mod w)}$ $(0\leq s\leq (w-1))$
• $h\leftarrow (h_{b}[0]\|\ldots \|h_{b}[w-1])_{[0:n-1]}$

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

안전성

LSH는 현재까지 알려진 모든 해시 함수 공격에 대해 안전하다. LSH는 ideal cipher model 하에서 쿼리의 수가 $q<2^{n/2}$일 때 충돌 저항성(collision-resistance)을 가지며, 쿼리의 수가 $q<2^{n}$일 때 역상 저항성(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-$n$	3.60	3.86	5.26	3.89	11.17	15.03	15.28	14.84
LSH-512-$n$	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