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. LSH is one of the cryptographic algorithms approved by the Korean Cryptographic Module Validation Program.
And it is the national standard of South Korea.

Specification

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.

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.
Compression:
* Updating of chaining variables by iteration of a compression function with message blocks.
Finalization:
* Generation of an -bit hash value from the final chaining variable.

function Hash function LSHinput: Bit string message output: Hash value procedure
One-zeros padding of
Generation of message blocks, where from the padded bit string
for 'to do
end for
return'

The specifications of the hash function LSH are as follows.

Algorithm	Digest size in bits	Number of step functions	Chaining variable size in bits	Message block size in bits	Word size in bits
LSH-256-224	224	26	512	1024	32
LSH-256-256	256	26	512	1024	32
LSH-512-224	224	28	1024	2048	64
LSH-512-256	256	28	1024	2048	64
LSH-512-384	384	28	1024	2048	64
LSH-512-512	512	28	1024	2048	64

Initialization

Let be a given bit string message.
The given is padded by one-zeros, i.e., the bit ‘1’ is appended to the end of, and the bit ‘0’s are appended until a bit length of a padded message is, where and is the smallest integer not less than.
Let be the one-zeros-padded -bit string of.
Then is considered as a -byte array, where for all.
The -byte array converts into a -word array as follows.
From the word array, we define the 32-word array message blocks as follows.
The 16-word array chaining variable is initialized to the initialization vector.
The initialization vector is as follows.
In the following tables, all values are expressed in hexadecimal form.


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

In this stage, the 32-word array message blocks, which are generated from a message in the initialization stage, are compressed by iteration of compression functions.
The compression function has two inputs; the -th 16-word chaining variable and the -th 32-word message block.
And it returns the -th 16-word chaining variable.
Here and subsequently, denotes the set of all -word arrays for.
The following four functions are used in a compression function:

Message expansion function
Message addition function
Mix function
Word-permutation function

The overall structure of the compression function is shown in the following figure.
In a compression function, the message expansion function generates 16-word array sub-messages from given.
Let be a temporary 16-word array set to the -th chaining variable.
The -th step function having two inputs and updates, i.e.,.
All step functions are proceeded in order.
Then one more operation by is proceeded, and the -th chaining variable is set to.
The process of a compression function in detail is as follows.

function Compression function input: The -th chaining variable and the -th message block output: The -th chaining variable procedure
for 'to do
end for
return'

Here the -th step function is as follows.
The following figure shows the -th step function of a compression function.

Message Expansion Function MsgExp

Let be the -th 32-word array message block.
The message expansion function generates 16-word array sub-messages from a message block.
The first two sub-messages and are defined as follows.
The next sub-messages are generated as follows.
Here is the permutation over defined as follows.

	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

Message Addition Function MsgAdd

For two 16-word arrays and, the message addition function is defined as follows.

Mix Function Mix

The -th mix function updates the 16-word array by mixing every two-word pair; and for.
For, the mix function proceeds as follows.
Here is a two-word mix function.
Let and be words.
The two-word mix function is defined as follows.

function Two-word mix function input: Words and output: Words and procedure
;;
;;
;;
return, ;

The two-word mix function is shown in the following figure.
The bit rotation amounts,, used in are shown in the following table.


32	even	29	1	0	8	16	24	24	16	8	0
32	odd	5	17	0	8	16	24	24	16	8	0
64	even	23	59	0	16	32	48	8	24	40	56
64	odd	7	3	0	16	32	48	8	24	40	56

The -th 8-word array constant used in for is defined as follows.
The initial 8-word array constant is defined in the following table.
For, the -th constant is generated by for.


	917caf90	97884283c938982a
	6c1b10a2	ba1fca93533e2355
	6f352943	c519a2e87aeb1c03
	cf778243	9a0fc95462af17b1
	2ceb7472	fc3dda8ab019a82b
	29e96ff2	02825d079a895407
	8a9ba428	79f2d0a7ee06a6f7
	2eeb2642	d76d15eed9fdf5fe

Word-Permutation Function WordPerm

Let be a 16-word array.
The word-permutation function is defined as follows.
Here is the permutation over defined by the following table.

	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

Finalization

The finalization function returns -bit hash value from the final chaining variable.
When is an 8-word variable and is a -byte variable, the finalization function performs the following procedure.
Here, denotes, the sub-bit string of a word for.
And denotes, the sub-bit string of a -bit string for.

Security

LSH is secure against known attacks on hash functions up to now.
LSH is collision-resistant for and preimage-resistant and second-preimage-resistant for in the ideal cipher model, where 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.

Platform	P1	P2	P3	P4	P5	P6	P7	P8
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

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.
The following table is measured on Samsung Exynos 5250 ARM Cortex-A15 @ 1.7 GHz dual core platform.

Test vectors

Test vectors for LSH for each digest length are as follows.
All values are expressed in hexadecimal form.
LSH-256-224 = 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 = 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 = 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 = 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 = 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 = 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.

Standardization

LSH is included in the following standard.

KS X 3262, Hash function LSH