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

Specification

edit

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  -bit hash value from the final chaining variable.
  • function Hash function LSH
  • input: 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.

Hash function LSH specifications
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
LSH-512-224 224 28 1024 2048 64
LSH-512-256 256
LSH-512-384 384
LSH-512-512 512

Initialization

edit

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.

LSH-256-224 initialization vector
               
068608D3 62D8F7A7 D76652AB 4C600A43 BDC40AA8 1ECA0B68 DA1A89BE 3147D354
               
707EB4F9 F65B3862 6B0B2ABE 56B8EC0A CF237286 EE0D1727 33636595 8BB8D05F
LSH-256-256 initialization vector
               
46A10F1F FDDCE486 B41443A8 198E6B9D 3304388D B0F5A3C7 B36061C4 7ADBD553
               
105D5378 2F74DE54 5C2F2D95 F2553FBE 8051357A 138668C8 47AA4484 E01AFB41
LSH-512-224 initialization vector
       
0C401E9FE8813A55 4A5F446268FD3D35 FF13E452334F612A F8227661037E354A
       
A5F223723C9CA29D 95D965A11AED3979 01E23835B9AB02CC 52D49CBAD5B30616
       
9E5C2027773F4ED3 66A5C8801925B701 22BBC85B4C6779D9 C13171A42C559C23
       
31E2B67D25BE3813 D522C4DEED8E4D83 A79F5509B43FBAFE E00D2CD88B4B6C6A
LSH-512-256 initialization vector
       
6DC57C33DF989423 D8EA7F6E8342C199 76DF8356F8603AC4 40F1B44DE838223A
       
39FFE7CFC31484CD 39C4326CC5281548 8A2FF85A346045D8 FF202AA46DBDD61E
       
CF785B3CD5FCDB8B 1F0323B64A8150BF FF75D972F29EA355 2E567F30BF1CA9E1
       
B596875BF8FF6DBA FCCA39B089EF4615 ECFF4017D020B4B6 7E77384C772ED802
LSH-512-384 initialization vector
       
53156A66292808F6 B2C4F362B204C2BC B84B7213BFA05C4E 976CEB7C1B299F73
       
DF0CC63C0570AE97 DA4441BAA486CE3F 6559F5D9B5F2ACC2 22DACF19B4B52A16
       
BBCDACEFDE80953A C9891A2879725B3E 7C9FE6330237E440 A30BA550553F7431
       
BB08043FB34E3E30 A0DEC48D54618EAD 150317267464BC57 32D1501FDE63DC93
LSH-512-512 initialization vector
       
ADD50F3C7F07094E E3F3CEE8F9418A4F B527ECDE5B3D0AE9 2EF6DEC68076F501
       
8CB994CAE5ACA216 FBB9EAE4BBA48CC7 650A526174725FEA 1F9A61A73F8D8085
       
B6607378173B539B 1BC99853B0C0B9ED DF727FC19B182D47 DBEF360CF893A457
       
4981F5E570147E80 D00C4490CA7D3E30 5D73940C0E4AE1EC 894085E2EDB2D819

Compression

edit

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.

 
Compression function of LSH

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.

 
The  -th step function  

Message Expansion Function MsgExp

edit

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.

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

edit

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

 

Mix Function Mix

edit

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.

 
Two-word mix function  

The bit rotation amounts  ,  ,   used in   are shown in the following table.

Bit rotation amounts  ,  , and  
                       
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  -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  .

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

Word-Permutation Function WordPerm

edit

Let   be a 16-word array. The word-permutation function   is defined as follows.

 

Here   is the permutation over   defined by the following table.

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

edit

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

edit

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

Performance

edit

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-  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
  1. ^ Intel Core i7-4770K @ 3.5GHz (Haswell), Ubuntu 12.04 64-bit, GCC 4.8.1 with “-m64 -mavx2 -O3”
  2. ^ Intel Core i7-2600K @ 3.40GHz (Sandy Bridge), Ubuntu 12.04 64-bit, GCC 4.8.1 with “-m64 -msse4 -O3”
  3. ^ Intel Core 2 Quad Q9550 @ 2.83GHz (Yorkfield), Windows 7 32-bit, Visual studio 2012
  4. ^ AMD FX-8350 @ 4GHz (Piledriver), Ubuntu 12.04 64-bit, GCC 4.8.1 with “-m64 -mxop -O3”
  5. ^ Samsung Exynos 5250 ARM Cortex-A15 @ 1.7GHz dual core (Huins ACHRO 5250), Android 4.1.1
  6. ^ Qualcomm Snapdragon 800 Krait 400 @ 2.26GHz quad core (LG G2), Android 4.4.2
  7. ^ Qualcomm Snapdragon 800 Krait 400 @ 2.3GHz quad core (Samsung Galaxy S4), Android 4.2.2
  8. ^ Qualcomm Snapdragon 400 Krait 300 @ 1.7GHz dual core (Samsung Galaxy S4 mini), Android 4.2.2

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

edit

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

edit

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]

KCMVP

edit

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

Standardization

edit

LSH is included in the following standard.

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

References

edit
  1. ^ a b c d e f Kim, Dong-Chan; Hong, Deukjo; Lee, Jung-Keun; Kim, Woo-Hwan; Kwon, Daesung (2015). "LSH: A New Fast Secure Hash Function Family". Information Security and Cryptology - ICISC 2014. Lecture Notes in Computer Science. Vol. 8949. Springer International Publishing. pp. 286–313. doi:10.1007/978-3-319-15943-0_18. ISBN 978-3-319-15943-0.
  2. ^ "KISA 암호이용활성화 - 암호알고리즘 소스코드". seed.kisa.or.kr.
  3. ^ "KISA 암호이용활성화 - 개요". seed.kisa.or.kr.
  4. ^ "Korean Standards & Certifications (in Korean)".