LSH (hash function)

Template:Short description Template:Other uses LSH is a cryptographic hash function designed in 2014 by South Korea to provide integrity in general-purpose software environments such as PCs and smart devices. LSH is one of the cryptographic algorithms approved by the Korean Cryptographic Module Validation Program (KCMVP). And it is the national standard of South Korea (KS X 3262).

Specification

The overall structure of the hash function LSH is shown in the following figure.

Overall structure of LSH

The hash function LSH has the wide-pipe Merkle-Damgård structure with one-zeros padding. The message hashing process of LSH consists of the following three stages.

1. Initialization:
   • One-zeros padding of a given bit string message.
   • Conversion to 32-word array message blocks from the padded bit string message.
   • Initialization of a chaining variable with the initialization vector.
2. Compression:
   • Updating of chaining variables by iteration of a compression function with message blocks.
3. Finalization:
   • Generation of an $n$-bit hash value from the final chaining variable.

function Hash function LSH input: Bit string message $m$ output: Hash value $h\in \{0,1{\}}^n$ procedure $$One-zeros padding of $m$ $$Generation of $t$ message blocks $\{{\mathsf{\text{𝖬}}}^{(i)}{\}}_{i=0}^{t-1}$, where $t=\lceil \frac{|m|+1}{32w}\rceil$ from the padded bit string $$${\mathsf{\text{𝖢𝖵}}}^{(0)}\leftarrow \mathsf{\text{𝖨𝖵}}$ $$for $i=0$ to $(t-1)$ do $$$$${\mathsf{\text{𝖢𝖵}}}^{(i+1)}\leftarrow \text{CF}({\mathsf{\text{𝖢𝖵}}}^{(i)},{\mathsf{\text{𝖬}}}^{(i)})$ $$end for $$$h\leftarrow {\text{FIN}}_n({\mathsf{\text{𝖢𝖵}}}^{(t)})$ $$return $h$

The specifications of the hash function LSH are as follows.

Hash function LSH specifications

Algorithm	Digest size in bits ($n$)	Number of step functions ($N_s$)	Chaining variable size in bits	Message block size in bits	Word size in bits ($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

Initialization

Let $m$ be a given bit string message. The given $m$ is padded by one-zeros, i.e., the bit ‘1’ is appended to the end of $m$, and the bit ‘0’s are appended until a bit length of a padded message is $32wt$, where $t=\lceil (|m|+1)/32w\rceil$ and $\lceil x\rceil$ is the smallest integer not less than $x$.

Let $m_p=m_0\Vert m_1\Vert \dots \Vert m_{(32wt-1)}$ be the one-zeros-padded $32wt$-bit string of $m$. Then $m_p$ is considered as a $4wt$-byte array $m_a=(m[0],\dots ,m[4wt-1])$, where $m[k]=m_{8k}\Vert m_{(8k+1)}\Vert \dots \Vert m_{(8k+7)}$ for all $0\le k\le (4wt-1)$. The $4wt$-byte array $m_a$ converts into a $32t$-word array $\mathsf{\text{𝖬}}=(M[0],\dots ,M[32t-1])$ as follows.

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

From the word array $\mathsf{\text{𝖬}}$, we define the $t$ 32-word array message blocks $\{{\mathsf{\text{𝖬}}}^{(i)}{\}}_{i=0}^{t-1}$ as follows.

${\mathsf{\text{𝖬}}}^{(i)}\leftarrow (M[32i],M[32i+1],\dots ,M[32i+31])$ $(0\le i\le (t-1))$

The 16-word array chaining variable ${\mathsf{\text{𝖢𝖵}}}^{(0)}$ is initialized to the initialization vector $\mathsf{\text{𝖨𝖵}}$.

${\mathsf{\text{𝖢𝖵}}}^{(0)}[l]\leftarrow \mathsf{\text{𝖨𝖵}}[l]$ $(0\le l\le 15)$

The initialization vector $\mathsf{\text{𝖨𝖵}}$ is as follows. In the following tables, all values are expressed in hexadecimal form.

LSH-256-224 initialization vector

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

LSH-256-256 initialization vector

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

LSH-512-224 initialization vector

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

LSH-512-256 initialization vector

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

LSH-512-384 initialization vector

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

LSH-512-512 initialization vector

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

Compression

In this stage, the $t$ 32-word array message blocks $\{{\mathsf{\text{𝖬}}}^{(i)}{\}}_{i=0}^{t-1}$, which are generated from a message $m$ in the initialization stage, are compressed by iteration of compression functions. The compression function $\text{CF}:{𝒲}^{16}\times {𝒲}^{32}\to {𝒲}^{16}$ has two inputs; the $i$-th 16-word chaining variable ${\mathsf{\text{𝖢𝖵}}}^{(i)}$ and the $i$-th 32-word message block ${\mathsf{\text{𝖬}}}^{(i)}$. And it returns the $(i+1)$-th 16-word chaining variable ${\mathsf{\text{𝖢𝖵}}}^{(i+1)}$. Here and subsequently, ${𝒲}^t$ denotes the set of all $t$-word arrays for $t\ge 1$.

The following four functions are used in a compression function:

• Message expansion function $\text{MsgExp}:{𝒲}^{32}\to {𝒲}^{16(Ns+1)}$
• Message addition function $\text{MsgAdd}:{𝒲}^{16}\times {𝒲}^{16}\to {𝒲}^{16}$
• Mix function ${\text{Mix}}_j:{𝒲}^{16}\to {𝒲}^{16}$
• Word-permutation function $\text{WordPerm}:{𝒲}^{16}\to {𝒲}^{16}$

The overall structure of the compression function is shown in the following figure.

Compression function of LSH

In a compression function, the message expansion function $\text{MsgExp}$ generates $(N_s+1)$ 16-word array sub-messages $\{{\mathsf{\text{𝖬}}}_j^{(i)}{\}}_{j=0}^{N_s}$ from given ${\mathsf{\text{𝖬}}}^{(i)}$. Let $\mathsf{\text{𝖳}}=(T[0],\dots ,T[15])$ be a temporary 16-word array set to the $i$-th chaining variable ${\mathsf{\text{𝖢𝖵}}}^{(i)}$. The $j$-th step function ${\text{Step}}_j$ having two inputs $\mathsf{\text{𝖳}}$ and ${\mathsf{\text{𝖬}}}_j^{(i)}$ updates $\mathsf{\text{𝖳}}$, i.e., $\mathsf{\text{𝖳}}\leftarrow {\text{Step}}_j(\mathsf{\text{𝖳}},{\mathsf{\text{𝖬}}}_j^{(i)})$. All step functions are proceeded in order $j=0,\dots ,N_s-1$. Then one more $\text{MsgAdd}$ operation by ${\mathsf{\text{𝖬}}}_{N_s}^{(i)}$ is proceeded, and the $(i+1)$-th chaining variable ${\mathsf{\text{𝖢𝖵}}}^{(i+1)}$ is set to $\mathsf{\text{𝖳}}$. The process of a compression function in detail is as follows.

function Compression function $\text{CF}$ input: The $i$-th chaining variable ${\mathsf{\text{𝖢𝖵}}}^{(i)}\in {𝒲}^{16}$ and the $i$-th message block ${\mathsf{\text{𝖬}}}^{(i)}\in {𝒲}^{32}$ output: The $(i+1)$-th chaining variable ${\mathsf{\text{𝖢𝖵}}}^{(i+1)}\in {𝒲}^{16}$ procedure $$$\{{\mathsf{\text{𝖬}}}_j^{(i)}{\}}_{j=0}^{N_s}\leftarrow \text{MsgExp}\left({\mathsf{\text{𝖬}}}^{(i)}\right)$ $$$\mathsf{\text{𝖳}}\leftarrow {\mathsf{\text{𝖢𝖵}}}^{(i)}$ $$for $j=0$ to $(N_s-1)$ do $$$$$\mathsf{\text{𝖳}}\leftarrow {\text{Step}}_j(\mathsf{\text{𝖳}},{\mathsf{\text{𝖬}}}_j^{(i)})$ $$end for $$${\mathsf{\text{𝖢𝖵}}}^{(i+1)}\leftarrow \text{MsgAdd}(\mathsf{\text{𝖳}},{\mathsf{\text{𝖬}}}_{N_s}^{(i)})$ $$return ${\mathsf{\text{𝖢𝖵}}}^{(i+1)}$

Here the $j$-th step function ${\text{Step}}_j:{𝒲}^{16}\times {𝒲}^{16}\to {𝒲}^{16}$ is as follows.

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

The following figure shows the $j$-th step function ${\text{Step}}_j$ of a compression function.

The $j$-th step function ${\text{Step}}_j$

Message Expansion Function MsgExp

Let ${\mathsf{\text{𝖬}}}^{(i)}=(M^{(i)}[0],\dots ,M^{(i)}[31])$ be the $i$-th 32-word array message block. The message expansion function $\text{MsgExp}$ generates $(N_s+1)$ 16-word array sub-messages $\{{\mathsf{\text{𝖬}}}_j^{(i)}{\}}_{j=0}^{N_s}$ from a message block ${\mathsf{\text{𝖬}}}^{(i)}$. The first two sub-messages ${\mathsf{\text{𝖬}}}_0^{(i)}=(M_0^{(i)}[0],\dots ,M_0^{(i)}[15])$ and ${\mathsf{\text{𝖬}}}_1^{(i)}=(M_1^{(i)}[0],\dots ,M_1^{(i)}[15])$ are defined as follows.

• ${\mathsf{\text{𝖬}}}_0^{(i)}\leftarrow (M^{(i)}[0],M^{(i)}[1],\dots ,M^{(i)}[15])$
• ${\mathsf{\text{𝖬}}}_1^{(i)}\leftarrow (M^{(i)}[16],M^{(i)}[17],\dots ,M^{(i)}[31])$

The next sub-messages $\{{\mathsf{\text{𝖬}}}_j^{(i)}=(M_j^{(i)}[0],\dots ,M_j^{(i)}[15]){\}}_{j=2}^{N_s}$ are generated as follows.

• ${\mathsf{\text{𝖬}}}_j^{(i)}[l]\leftarrow {\mathsf{\text{𝖬}}}_{j-1}^{(i)}[l]⊞{\mathsf{\text{𝖬}}}_{j-2}^{(i)}[\tau (l)]$ $(0\le l\le 15,2\le j\le N_s)$

Here $\tau$ is the permutation over ${\mathbb{Z}}_{16}$ defined as follows.

The permutation $\tau :{\mathbb{Z}}_{16}\to {\mathbb{Z}}_{16}$

$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

Message Addition Function MsgAdd

For two 16-word arrays $\mathsf{\text{𝖷}}=(X[0],\dots ,X[15])$ and $\mathsf{\text{𝖸}}=(Y[0],\dots ,Y[15])$, the message addition function $\text{MsgAdd}:{𝒲}^{16}\times {𝒲}^{16}\to {𝒲}^{16}$ is defined as follows.

$\text{MsgAdd}(\mathsf{\text{𝖷}},\mathsf{\text{𝖸}}):=(X[0]\oplus Y[0],\dots ,X[15]\oplus Y[15])$

Mix Function Mix

The $j$-th mix function ${\text{Mix}}_j:{𝒲}^{16}\to {𝒲}^{16}$ updates the 16-word array $\mathsf{\text{𝖳}}=(T[0],\dots ,T[15])$ by mixing every two-word pair; $T[l]$ and $T[l+8]$ for $(0\le l<8)$. For $0\le j<N_s$, the mix function ${\text{Mix}}_j$ proceeds as follows.

$(T[l],T[l+8])\leftarrow {\text{Mix}}_{j,l}(T[l],T[l+8])$ $(0\le l<8)$

Here ${\text{Mix}}_{j,l}$ is a two-word mix function. Let $X$ and $Y$ be words. The two-word mix function ${\text{Mix}}_{j,l}:{𝒲}^2\to {𝒲}^2$ is defined as follows.

function Two-word mix function ${\text{Mix}}_{j,l}$ input: Words $X$ and $Y$ output: Words $X$ and $Y$ procedure $$$X\leftarrow X⊞Y$;$X\leftarrow X^{⋘{\alpha }_j}$; $$$X\leftarrow X\oplus S{C}_j[l]$; $$$Y\leftarrow X⊞Y$;$Y\leftarrow Y^{⋘{\beta }_j}$; $$$X\leftarrow X⊞Y$;$Y\leftarrow Y^{⋘{\gamma }_l}$; $$return $X$, $Y$;

The two-word mix function ${\text{Mix}}_{j,l}$ is shown in the following figure.

Two-word mix function ${\text{Mix}}_{j,l}(X,Y)$

The bit rotation amounts ${\alpha }_j$, ${\beta }_j$, ${\gamma }_l$ used in ${\text{Mix}}_{j,l}$ are shown in the following table.

Bit rotation amounts ${\alpha }_j$, ${\beta }_j$, and ${\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	even	29	1	0	8	16	24	24	16	8	0
	odd	5	17
64	even	23	59	0	16	32	48	8	24	40	56
	odd	7	3

The $j$-th 8-word array constant ${\mathsf{\text{𝖲𝖢}}}_j=(S{C}_j[0],\dots ,S{C}_j[7])$ used in ${\text{Mix}}_{j,l}$ for $0\le l<8$ is defined as follows. The initial 8-word array constant ${\mathsf{\text{𝖲𝖢}}}_0=(S{C}_0[0],\dots ,S{C}_0[7])$ is defined in the following table. For $1\le j<N_s$, the $j$-th constant ${\mathsf{\text{𝖲𝖢}}}_j=(S{C}_j[0],\dots ,S{C}_j[7])$ is generated by $S{C}_j[l]\leftarrow S{C}_{j-1}[l]⊞S{C}_{j-1}[l{]}^{⋘8}$ for $0\le l<8$.

Initial 8-word array constant ${\mathsf{\text{𝖲𝖢}}}_0$

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

Word-Permutation Function WordPerm

Let $\mathsf{\text{𝖷}}=(X[0],\dots ,X[15])$ be a 16-word array. The word-permutation function $\text{WordPerm}:{𝒲}^{16}\to {𝒲}^{16}$ is defined as follows.

$\text{WordPerm}(\mathsf{\text{𝖷}})=(X[\sigma (0)],\dots ,X[\sigma (15)])$

Here $\sigma$ is the permutation over ${\mathbb{Z}}_{16}$ defined by the following table.

The permutation $\sigma :{\mathbb{Z}}_{16}\to {\mathbb{Z}}_{16}$

$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

Finalization

The finalization function ${\text{FIN}}_n:{𝒲}^{16}\to \{0,1{\}}^n$ returns $n$-bit hash value $h$ from the final chaining variable ${\mathsf{\text{𝖢𝖵}}}^{(t)}=(C{V}^{(t)}[0],\dots ,C{V}^{(t)}[15])$. When $\mathsf{\text{𝖧}}=(H[0],\dots ,H[7])$ is an 8-word variable and ${\mathsf{\text{𝗁}}}_{\mathsf{\text{𝖻}}}=(h_b[0],\dots ,h_b[w-1])$ is a $w$-byte variable, the finalization function ${\text{FIN}}_n$ performs the following procedure.

• $H[l]\leftarrow C{V}^{(t)}[l]\oplus C{V}^{(t)}[l+8]$ $(0\le l\le 7)$
• $h_b[s]\leftarrow H[\lfloor 8s/w\rfloor {]}_{[7:0]}^{⋙(8smodw)}$ $(0\le s\le (w-1))$
• $h\leftarrow (h_b[0]\Vert \dots \Vert h_b[w-1]{)}_{[0:n-1]}$

Here, $X_{[i:j]}$ denotes $x_i\Vert x_{i-1}\Vert \dots \Vert x_j$, the sub-bit string of a word $X$ for $i\ge j$. And $x_{[i:j]}$ denotes $x_i\Vert x_{i+1}\Vert \dots \Vert x_j$, the sub-bit string of a $l$-bit string $x=x_0\Vert x_1\Vert \dots \Vert x_{l-1}$ for $i\le j$.

Security

LSH is secure against known attacks on hash functions up to now. LSH is collision-resistant for $q<2^{n/2}$ and preimage-resistant and second-preimage-resistant for $q<2^n$ in the ideal cipher model, where $q$ is a number of queries for LSH structure. LSH-256 is secure against all the existing hash function attacks when the number of steps is 13 or more, while LSH-512 is secure if the number of steps is 14 or more. Note that the steps which work as security margin are 50% of the compression function.

Performance

LSH outperforms SHA-2/3 on various software platforms. The following table shows the speed performance of 1MB message hashing of LSH on several platforms.

1MB message hashing speed of LSH (cycles/byte)

Platform	P1Template:Efn	P2Template:Efn	P3Template:Efn	P4Template:Efn	P5Template:Efn	P6Template:Efn	P7Template:Efn	P8Template:Efn
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

The following table is the comparison at the platform based on Haswell, LSH is measured on Intel Core i7-4770k @ 3.5 GHz quad core platform, and others are measured on Intel Core i5-4570S @ 2.9 GHz quad core platform.

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

The following table is measured on Samsung Exynos 5250 ARM Cortex-A15 @ 1.7 GHz dual core platform.

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

Test vectors

Test vectors for LSH for each digest length are as follows. All values are expressed in hexadecimal form.

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

Implementations

LSH is free for any use public or private, commercial or non-commercial. The source code for distribution of LSH implemented in C, Java, and Python can be downloaded from KISA's cryptography use activation webpage.

KCMVP

LSH is one of the cryptographic algorithms approved by the Korean Cryptographic Module Validation Program (KCMVP).

Standardization

LSH is included in the following standard.

• KS X 3262, Hash function LSH (in Korean)