LSH (hash function)

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.^[1] 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).

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

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 {\displaystyle n} -bit hash value from the final chaining variable.

function Hash function LSH input: Bit string message m {\displaystyle m} output: Hash value h ∈ { 0 , 1 } n {\displaystyle h\in \{0,1\}^{n}} procedure {\displaystyle \qquad } One-zeros padding of m {\displaystyle m} {\displaystyle \qquad } Generation of t {\displaystyle t} message blocks { M ( i ) } i = 0 t − 1 {\displaystyle \{{\textsf {M}}^{(i)}\}_{i=0}^{t-1}} , where t = ⌈ | m | + 1 32 w ⌉ {\displaystyle t={\Big \lceil }{\frac {|m|+1}{32w}}{\Big \rceil }} from the padded bit string {\displaystyle \qquad } CV ( 0 ) ← IV {\displaystyle {\textsf {CV}}^{(0)}\leftarrow {\textsf {IV}}} {\displaystyle \qquad } for i = 0 {\displaystyle i=0} to ( t − 1 ) {\displaystyle (t-1)} do {\displaystyle \qquad } {\displaystyle \qquad } CV ( i + 1 ) ← CF ( CV ( i ) , M ( i ) ) {\displaystyle {\textsf {CV}}^{(i+1)}\leftarrow {\textrm {CF}}({\textsf {CV}}^{(i)},{\textsf {M}}^{(i)})} {\displaystyle \qquad } end for {\displaystyle \qquad } h ← FIN n ( CV ( t ) ) {\displaystyle h\leftarrow {\textrm {FIN}}_{n}({\textsf {CV}}^{(t)})} {\displaystyle \qquad } return h {\displaystyle h}

The specifications of the hash function LSH are as follows.

Hash function LSH specifications

Algorithm	Digest size in bits ( n {\displaystyle n} )	Number of step functions ( N s {\displaystyle N_{s}} )	Chaining variable size in bits	Message block size in bits	Word size in bits ( w {\displaystyle 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

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

Let m p = m 0 ‖ m 1 ‖ … ‖ m ( 32 w t − 1 ) {\displaystyle m_{p}=m_{0}\|m_{1}\|\ldots \|m_{(32wt-1)}} be the one-zeros-padded 32 w t {\displaystyle 32wt} -bit string of m {\displaystyle m} . Then m p {\displaystyle m_{p}} is considered as a 4 w t {\displaystyle 4wt} -byte array m a = ( m [ 0 ] , … , m [ 4 w t − 1 ] ) {\displaystyle m_{a}=(m[0],\ldots ,m[4wt-1])} , where m [ k ] = m 8 k ‖ m ( 8 k + 1 ) ‖ … ‖ m ( 8 k + 7 ) {\displaystyle m[k]=m_{8k}\|m_{(8k+1)}\|\ldots \|m_{(8k+7)}} for all 0 ≤ k ≤ ( 4 w t − 1 ) {\displaystyle 0\leq k\leq (4wt-1)} . The 4 w t {\displaystyle 4wt} -byte array m a {\displaystyle m_{a}} converts into a 32 t {\displaystyle 32t} -word array M = ( M [ 0 ] , … , M [ 32 t − 1 ] ) {\displaystyle {\textsf {M}}=(M[0],\ldots ,M[32t-1])} as follows.

M [ s ] ← m [ w s / 8 + ( w / 8 − 1 ) ] ‖ … ‖ m [ w s / 8 + 1 ] ‖ m [ w s / 8 ] {\displaystyle M[s]\leftarrow m[ws/8+(w/8-1)]\|\ldots \|m[ws/8+1]\|m[ws/8]} ( 0 ≤ s ≤ ( 32 t − 1 ) ) {\displaystyle (0\leq s\leq (32t-1))}

From the word array M {\displaystyle {\textsf {M}}} , we define the t {\displaystyle t} 32-word array message blocks { M ( i ) } i = 0 t − 1 {\displaystyle \{{\textsf {M}}^{(i)}\}_{i=0}^{t-1}} as follows.

M ( i ) ← ( M [ 32 i ] , M [ 32 i + 1 ] , … , M [ 32 i + 31 ] ) {\displaystyle {\textsf {M}}^{(i)}\leftarrow (M[32i],M[32i+1],\ldots ,M[32i+31])} ( 0 ≤ i ≤ ( t − 1 ) ) {\displaystyle (0\leq i\leq (t-1))}

The 16-word array chaining variable CV ( 0 ) {\displaystyle {\textsf {CV}}^{(0)}} is initialized to the initialization vector IV {\displaystyle {\textsf {IV}}} .

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

The initialization vector IV {\displaystyle {\textsf {IV}}} is as follows. In the following tables, all values are expressed in hexadecimal form.

LSH-256-224 initialization vector

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

LSH-256-256 initialization vector

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

LSH-512-224 initialization vector

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

LSH-512-256 initialization vector

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

LSH-512-384 initialization vector

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

LSH-512-512 initialization vector

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

In this stage, the t {\displaystyle t} 32-word array message blocks { M ( i ) } i = 0 t − 1 {\displaystyle \{{\textsf {M}}^{(i)}\}_{i=0}^{t-1}} , which are generated from a message m {\displaystyle m} in the initialization stage, are compressed by iteration of compression functions. The compression function CF : W 16 × W 32 → W 16 {\displaystyle {\textrm {CF}}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{32}\rightarrow {\mathcal {W}}^{16}} has two inputs; the i {\displaystyle i} -th 16-word chaining variable CV ( i ) {\displaystyle {\textsf {CV}}^{(i)}} and the i {\displaystyle i} -th 32-word message block M ( i ) {\displaystyle {\textsf {M}}^{(i)}} . And it returns the ( i + 1 ) {\displaystyle (i+1)} -th 16-word chaining variable CV ( i + 1 ) {\displaystyle {\textsf {CV}}^{(i+1)}} . Here and subsequently, W t {\displaystyle {\mathcal {W}}^{t}} denotes the set of all t {\displaystyle t} -word arrays for t ≥ 1 {\displaystyle t\geq 1} .

The following four functions are used in a compression function:

• Message expansion function MsgExp : W 32 → W 16 ( N s + 1 ) {\displaystyle {\textrm {MsgExp}}:{\mathcal {W}}^{32}\rightarrow {\mathcal {W}}^{16(Ns+1)}}
• Message addition function MsgAdd : W 16 × W 16 → W 16 {\displaystyle {\textrm {MsgAdd}}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}}
• Mix function Mix j : W 16 → W 16 {\displaystyle {\textrm {Mix}}_{j}:{\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}}
• Word-permutation function WordPerm : W 16 → W 16 {\displaystyle {\textrm {WordPerm}}:{\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}}

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

In a compression function, the message expansion function MsgExp {\displaystyle {\textrm {MsgExp}}} generates ( N s + 1 ) {\displaystyle (N_{s}+1)} 16-word array sub-messages { M j ( i ) } j = 0 N s {\displaystyle \{{\textsf {M}}_{j}^{(i)}\}_{j=0}^{N_{s}}} from given M ( i ) {\displaystyle {\textsf {M}}^{(i)}} . Let T = ( T [ 0 ] , … , T [ 15 ] ) {\displaystyle {\textsf {T}}=(T[0],\ldots ,T[15])} be a temporary 16-word array set to the i {\displaystyle i} -th chaining variable CV ( i ) {\displaystyle {\textsf {CV}}^{(i)}} . The j {\displaystyle j} -th step function Step j {\displaystyle {\textrm {Step}}_{j}} having two inputs T {\displaystyle {\textsf {T}}} and M j ( i ) {\displaystyle {\textsf {M}}_{j}^{(i)}} updates T {\displaystyle {\textsf {T}}} , i.e., T ← Step j ( T , M j ( i ) ) {\displaystyle {\textsf {T}}\leftarrow {\textrm {Step}}_{j}\left({\textsf {T}},{\textsf {M}}_{j}^{(i)}\right)} . All step functions are proceeded in order j = 0 , … , N s − 1 {\displaystyle j=0,\ldots ,N_{s}-1} . Then one more MsgAdd {\displaystyle {\textrm {MsgAdd}}} operation by M N s ( i ) {\displaystyle {\textsf {M}}_{N_{s}}^{(i)}} is proceeded, and the ( i + 1 ) {\displaystyle (i+1)} -th chaining variable CV ( i + 1 ) {\displaystyle {\textsf {CV}}^{(i+1)}} is set to T {\displaystyle {\textsf {T}}} . The process of a compression function in detail is as follows.

function Compression function CF {\displaystyle {\textrm {CF}}} input: The i {\displaystyle i} -th chaining variable CV ( i ) ∈ W 16 {\displaystyle {\textsf {CV}}^{(i)}\in {\mathcal {W}}^{16}} and the i {\displaystyle i} -th message block M ( i ) ∈ W 32 {\displaystyle {\textsf {M}}^{(i)}\in {\mathcal {W}}^{32}} output: The ( i + 1 ) {\displaystyle (i+1)} -th chaining variable CV ( i + 1 ) ∈ W 16 {\displaystyle {\textsf {CV}}^{(i+1)}\in {\mathcal {W}}^{16}} procedure {\displaystyle \qquad } { M j ( i ) } j = 0 N s ← MsgExp ( M ( i ) ) {\displaystyle \{{\textsf {M}}_{j}^{(i)}\}_{j=0}^{N_{s}}\leftarrow {\textrm {MsgExp}}\left({\textsf {M}}^{(i)}\right)} {\displaystyle \qquad } T ← CV ( i ) {\displaystyle {\textsf {T}}\leftarrow {\textsf {CV}}^{(i)}} {\displaystyle \qquad } for j = 0 {\displaystyle j=0} to ( N s − 1 ) {\displaystyle (N_{s}-1)} do {\displaystyle \qquad } {\displaystyle \qquad } T ← Step j ( T , M j ( i ) ) {\displaystyle {\textsf {T}}\leftarrow {\textrm {Step}}_{j}\left({\textsf {T}},{\textsf {M}}_{j}^{(i)}\right)} {\displaystyle \qquad } end for {\displaystyle \qquad } CV ( i + 1 ) ← MsgAdd ( T , M N s ( i ) ) {\displaystyle {\textsf {CV}}^{(i+1)}\leftarrow {\textrm {MsgAdd}}\left({\textsf {T}},{\textsf {M}}_{N_{s}}^{(i)}\right)} {\displaystyle \qquad } return CV ( i + 1 ) {\displaystyle {\textsf {CV}}^{(i+1)}}

Here the j {\displaystyle j} -th step function Step j : W 16 × W 16 → W 16 {\displaystyle {\textrm {Step}}_{j}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}} is as follows.

Step j := WordPerm ∘ Mix j ∘ MsgAdd {\displaystyle {\textrm {Step}}_{j}:={\textrm {WordPerm}}\circ {\textrm {Mix}}_{j}\circ {\textrm {MsgAdd}}} ( 0 ≤ j ≤ ( N s − 1 ) ) {\displaystyle (0\leq j\leq (N_{s}-1))}

The following figure shows the j {\displaystyle j} -th step function Step j {\displaystyle {\textrm {Step}}_{j}} of a compression function.

Let M ( i ) = ( M ( i ) [ 0 ] , … , M ( i ) [ 31 ] ) {\displaystyle {\textsf {M}}^{(i)}=(M^{(i)}[0],\ldots ,M^{(i)}[31])} be the i {\displaystyle i} -th 32-word array message block. The message expansion function MsgExp {\displaystyle {\textrm {MsgExp}}} generates ( N s + 1 ) {\displaystyle (N_{s}+1)} 16-word array sub-messages { M j ( i ) } j = 0 N s {\displaystyle \{{\textsf {M}}_{j}^{(i)}\}_{j=0}^{N_{s}}} from a message block M ( i ) {\displaystyle {\textsf {M}}^{(i)}} . The first two sub-messages M 0 ( i ) = ( M 0 ( i ) [ 0 ] , … , M 0 ( i ) [ 15 ] ) {\displaystyle {\textsf {M}}_{0}^{(i)}=(M_{0}^{(i)}[0],\ldots ,M_{0}^{(i)}[15])} and M 1 ( i ) = ( M 1 ( i ) [ 0 ] , … , M 1 ( i ) [ 15 ] ) {\displaystyle {\textsf {M}}_{1}^{(i)}=(M_{1}^{(i)}[0],\ldots ,M_{1}^{(i)}[15])} are defined as follows.

• M 0 ( i ) ← ( M ( i ) [ 0 ] , M ( i ) [ 1 ] , … , M ( i ) [ 15 ] ) {\displaystyle {\textsf {M}}_{0}^{(i)}\leftarrow (M^{(i)}[0],M^{(i)}[1],\ldots ,M^{(i)}[15])}
• M 1 ( i ) ← ( M ( i ) [ 16 ] , M ( i ) [ 17 ] , … , M ( i ) [ 31 ] ) {\displaystyle {\textsf {M}}_{1}^{(i)}\leftarrow (M^{(i)}[16],M^{(i)}[17],\ldots ,M^{(i)}[31])}

The next sub-messages { M j ( i ) = ( M j ( i ) [ 0 ] , … , M j ( i ) [ 15 ] ) } j = 2 N s {\displaystyle \{{\textsf {M}}_{j}^{(i)}=(M_{j}^{(i)}[0],\ldots ,M_{j}^{(i)}[15])\}_{j=2}^{N_{s}}} are generated as follows.

• M j ( i ) [ l ] ← M j − 1 ( i ) [ l ] ⊞ M j − 2 ( i ) [ τ ( l ) ] {\displaystyle {\textsf {M}}_{j}^{(i)}[l]\leftarrow {\textsf {M}}_{j-1}^{(i)}[l]\boxplus {\textsf {M}}_{j-2}^{(i)}[\tau (l)]} ( 0 ≤ l ≤ 15 ,   2 ≤ j ≤ N s ) {\displaystyle (0\leq l\leq 15,\ 2\leq j\leq N_{s})}

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

The permutation τ : Z 16 → Z 16 {\displaystyle \tau :\mathbb {Z} _{16}\rightarrow \mathbb {Z} _{16}}

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

For two 16-word arrays X = ( X [ 0 ] , … , X [ 15 ] ) {\displaystyle {\textsf {X}}=(X[0],\ldots ,X[15])} and Y = ( Y [ 0 ] , … , Y [ 15 ] ) {\displaystyle {\textsf {Y}}=(Y[0],\ldots ,Y[15])} , the message addition function MsgAdd : W 16 × W 16 → W 16 {\displaystyle {\textrm {MsgAdd}}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}} is defined as follows.

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

The j {\displaystyle j} -th mix function Mix j : W 16 → W 16 {\displaystyle {\textrm {Mix}}_{j}:{\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}} updates the 16-word array T = ( T [ 0 ] , … , T [ 15 ] ) {\displaystyle {\textsf {T}}=(T[0],\ldots ,T[15])} by mixing every two-word pair; T [ l ] {\displaystyle T[l]} and T [ l + 8 ] {\displaystyle T[l+8]} for ( 0 ≤ l < 8 ) {\displaystyle (0\leq l<8)} . For 0 ≤ j < N s {\displaystyle 0\leq j<N_{s}} , the mix function Mix j {\displaystyle {\textrm {Mix}}_{j}} proceeds as follows.

( T [ l ] , T [ l + 8 ] ) ← Mix j , l ( T [ l ] , T [ l + 8 ] ) {\displaystyle (T[l],T[l+8])\leftarrow {\textrm {Mix}}_{j,l}(T[l],T[l+8])} ( 0 ≤ l < 8 ) {\displaystyle (0\leq l<8)}

Here Mix j , l {\displaystyle {\textrm {Mix}}_{j,l}} is a two-word mix function. Let X {\displaystyle X} and Y {\displaystyle Y} be words. The two-word mix function Mix j , l : W 2 → W 2 {\displaystyle {\textrm {Mix}}_{j,l}:{\mathcal {W}}^{2}\rightarrow {\mathcal {W}}^{2}} is defined as follows.

function Two-word mix function Mix j , l {\displaystyle {\textrm {Mix}}_{j,l}} input: Words X {\displaystyle X} and Y {\displaystyle Y} output: Words X {\displaystyle X} and Y {\displaystyle Y} procedure {\displaystyle \qquad } X ← X ⊞ Y {\displaystyle X\leftarrow X\boxplus Y} ; X ← X ⋘ α j {\displaystyle \qquad X\leftarrow X^{\lll \alpha _{j}}} ; {\displaystyle \qquad } X ← X ⊕ S C j [ l ] {\displaystyle X\leftarrow X\oplus SC_{j}[l]} ; {\displaystyle \qquad } Y ← X ⊞ Y {\displaystyle Y\leftarrow X\boxplus Y} ; Y ← Y ⋘ β j {\displaystyle \qquad Y\leftarrow Y^{\lll \beta _{j}}} ; {\displaystyle \qquad } X ← X ⊞ Y {\displaystyle X\leftarrow X\boxplus Y} ; Y ← Y ⋘ γ l {\displaystyle \qquad Y\leftarrow Y^{\lll \gamma _{l}}} ; {\displaystyle \qquad } return X {\displaystyle X} , Y {\displaystyle Y} ;

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

The bit rotation amounts α j {\displaystyle \alpha _{j}} , β j {\displaystyle \beta _{j}} , γ l {\displaystyle \gamma _{l}} used in Mix j , l {\displaystyle {\textrm {Mix}}_{j,l}} are shown in the following table.

Bit rotation amounts α j {\displaystyle \alpha _{j}} , β j {\displaystyle \beta _{j}} , and γ l {\displaystyle \gamma _{l}}

w {\displaystyle w}	j {\displaystyle j}	α j {\displaystyle \alpha _{j}}	β j {\displaystyle \beta _{j}}	γ 0 {\displaystyle \gamma _{0}}	γ 1 {\displaystyle \gamma _{1}}	γ 2 {\displaystyle \gamma _{2}}	γ 3 {\displaystyle \gamma _{3}}	γ 4 {\displaystyle \gamma _{4}}	γ 5 {\displaystyle \gamma _{5}}	γ 6 {\displaystyle \gamma _{6}}	γ 7 {\displaystyle \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 {\displaystyle j} -th 8-word array constant SC j = ( S C j [ 0 ] , … , S C j [ 7 ] ) {\displaystyle {\textsf {SC}}_{j}=(SC_{j}[0],\ldots ,SC_{j}[7])} used in Mix j , l {\displaystyle {\textrm {Mix}}_{j,l}} for 0 ≤ l < 8 {\displaystyle 0\leq l<8} is defined as follows. The initial 8-word array constant SC 0 = ( S C 0 [ 0 ] , … , S C 0 [ 7 ] ) {\displaystyle {\textsf {SC}}_{0}=(SC_{0}[0],\ldots ,SC_{0}[7])} is defined in the following table. For 1 ≤ j < N s {\displaystyle 1\leq j<N_{s}} , the j {\displaystyle j} -th constant SC j = ( S C j [ 0 ] , … , S C j [ 7 ] ) {\displaystyle {\textsf {SC}}_{j}=(SC_{j}[0],\ldots ,SC_{j}[7])} is generated by S C j [ l ] ← S C j − 1 [ l ] ⊞ S C j − 1 [ l ] ⋘ 8 {\displaystyle SC_{j}[l]\leftarrow SC_{j-1}[l]\boxplus SC_{j-1}[l]^{\lll 8}} for 0 ≤ l < 8 {\displaystyle 0\leq l<8} .

Initial 8-word array constant SC 0 {\displaystyle {\textsf {SC}}_{0}}

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

Let X = ( X [ 0 ] , … , X [ 15 ] ) {\displaystyle {\textsf {X}}=(X[0],\ldots ,X[15])} be a 16-word array. The word-permutation function WordPerm : W 16 → W 16 {\displaystyle {\textrm {WordPerm}}:{\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}} is defined as follows.

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

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

The permutation σ : Z 16 → Z 16 {\displaystyle \sigma :\mathbb {Z} _{16}\rightarrow \mathbb {Z} _{16}}

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

The finalization function FIN n : W 16 → { 0 , 1 } n {\displaystyle {\textrm {FIN}}_{n}:{\mathcal {W}}^{16}\rightarrow \{0,1\}^{n}} returns n {\displaystyle n} -bit hash value h {\displaystyle h} from the final chaining variable CV ( t ) = ( C V ( t ) [ 0 ] , … , C V ( t ) [ 15 ] ) {\displaystyle {\textsf {CV}}^{(t)}=(CV^{(t)}[0],\ldots ,CV^{(t)}[15])} . When H = ( H [ 0 ] , … , H [ 7 ] ) {\displaystyle {\textsf {H}}=(H[0],\ldots ,H[7])} is an 8-word variable and h b = ( h b [ 0 ] , … , h b [ w − 1 ] ) {\displaystyle {\textsf {h}}_{\textsf {b}}=(h_{b}[0],\ldots ,h_{b}[w-1])} is a w {\displaystyle w} -byte variable, the finalization function FIN n {\displaystyle {\textrm {FIN}}_{n}} performs the following procedure.

• H [ l ] ← C V ( t ) [ l ] ⊕ C V ( t ) [ l + 8 ] {\displaystyle H[l]\leftarrow CV^{(t)}[l]\oplus CV^{(t)}[l+8]} ( 0 ≤ l ≤ 7 ) {\displaystyle (0\leq l\leq 7)}
• h b [ s ] ← H [ ⌊ 8 s / w ⌋ ] [ 7 : 0 ] ⋙ ( 8 s mod w ) {\displaystyle h_{b}[s]\leftarrow H[\lfloor 8s/w\rfloor ]_{[7:0]}^{\ggg (8s\mod w)}} ( 0 ≤ s ≤ ( w − 1 ) ) {\displaystyle (0\leq s\leq (w-1))}
• h ← ( h b [ 0 ] ‖ … ‖ h b [ w − 1 ] ) [ 0 : n − 1 ] {\displaystyle h\leftarrow (h_{b}[0]\|\ldots \|h_{b}[w-1])_{[0:n-1]}}

Here, X [ i : j ] {\displaystyle X_{[i:j]}} denotes x i ‖ x i − 1 ‖ … ‖ x j {\displaystyle x_{i}\|x_{i-1}\|\ldots \|x_{j}} , the sub-bit string of a word X {\displaystyle X} for i ≥ j {\displaystyle i\geq j} . And x [ i : j ] {\displaystyle x_{[i:j]}} denotes x i ‖ x i + 1 ‖ … ‖ x j {\displaystyle x_{i}\|x_{i+1}\|\ldots \|x_{j}} , the sub-bit string of a l {\displaystyle l} -bit string x = x 0 ‖ x 1 ‖ … ‖ x l − 1 {\displaystyle x=x_{0}\|x_{1}\|\ldots \|x_{l-1}} for i ≤ j {\displaystyle i\leq j} .

LSH is secure against known attacks on hash functions up to now. LSH is collision-resistant for q < 2 n / 2 {\displaystyle q<2^{n/2}} and preimage-resistant and second-preimage-resistant for q < 2 n {\displaystyle q<2^{n}} in the ideal cipher model, where q {\displaystyle q} is a number of queries for LSH structure.^[1] 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.^[1]

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)^[1]

Platform	P1[a]	P2[b]	P3[c]	P4[d]	P5[e]	P6[f]	P7[g]	P8[h]
LSH-256- n {\displaystyle n}	3.60	3.86	5.26	3.89	11.17	15.03	15.28	14.84
LSH-512- n {\displaystyle 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)^[1]

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)^[1]

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 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

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.^[2]

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

LSH is included in the following standard.

• KS X 3262, Hash function LSH (in Korean)^[4]