Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
LSH (hash function)
Cryptographic 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).

We don't have any images related to LSH (hash function) yet.
We don't have any YouTube videos related to LSH (hash function) yet.
We don't have any PDF documents related to LSH (hash function) yet.
We don't have any Books related to LSH (hash function) yet.
We don't have any archived web articles related to LSH (hash function) yet.

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.

  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
AlgorithmDigest size in bits ( n {\displaystyle n} )Number of step functions ( N s {\displaystyle N_{s}} )Chaining variable size in bitsMessage block size in bitsWord size in bits ( w {\displaystyle w} )
LSH-256-22422426512102432
LSH-256-256256
LSH-512-224224281024204864
LSH-512-256256
LSH-512-384384
LSH-512-512512

Initialization

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]}
068608D362D8F7A7D76652AB4C600A43BDC40AA81ECA0B68DA1A89BE3147D354
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]}
707EB4F9F65B38626B0B2ABE56B8EC0ACF237286EE0D1727336365958BB8D05F
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]}
46A10F1FFDDCE486B41443A8198E6B9D3304388DB0F5A3C7B36061C47ADBD553
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]}
105D53782F74DE545C2F2D95F2553FBE8051357A138668C847AA4484E01AFB41
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]}
0C401E9FE8813A554A5F446268FD3D35FF13E452334F612AF8227661037E354A
IV [ 4 ] {\displaystyle {\textsf {IV}}[4]} IV [ 5 ] {\displaystyle {\textsf {IV}}[5]} IV [ 6 ] {\displaystyle {\textsf {IV}}[6]} IV [ 7 ] {\displaystyle {\textsf {IV}}[7]}
A5F223723C9CA29D95D965A11AED397901E23835B9AB02CC52D49CBAD5B30616
IV [ 8 ] {\displaystyle {\textsf {IV}}[8]} IV [ 9 ] {\displaystyle {\textsf {IV}}[9]} IV [ 10 ] {\displaystyle {\textsf {IV}}[10]} IV [ 11 ] {\displaystyle {\textsf {IV}}[11]}
9E5C2027773F4ED366A5C8801925B70122BBC85B4C6779D9C13171A42C559C23
IV [ 12 ] {\displaystyle {\textsf {IV}}[12]} IV [ 13 ] {\displaystyle {\textsf {IV}}[13]} IV [ 14 ] {\displaystyle {\textsf {IV}}[14]} IV [ 15 ] {\displaystyle {\textsf {IV}}[15]}
31E2B67D25BE3813D522C4DEED8E4D83A79F5509B43FBAFEE00D2CD88B4B6C6A
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]}
6DC57C33DF989423D8EA7F6E8342C19976DF8356F8603AC440F1B44DE838223A
IV [ 4 ] {\displaystyle {\textsf {IV}}[4]} IV [ 5 ] {\displaystyle {\textsf {IV}}[5]} IV [ 6 ] {\displaystyle {\textsf {IV}}[6]} IV [ 7 ] {\displaystyle {\textsf {IV}}[7]}
39FFE7CFC31484CD39C4326CC52815488A2FF85A346045D8FF202AA46DBDD61E
IV [ 8 ] {\displaystyle {\textsf {IV}}[8]} IV [ 9 ] {\displaystyle {\textsf {IV}}[9]} IV [ 10 ] {\displaystyle {\textsf {IV}}[10]} IV [ 11 ] {\displaystyle {\textsf {IV}}[11]}
CF785B3CD5FCDB8B1F0323B64A8150BFFF75D972F29EA3552E567F30BF1CA9E1
IV [ 12 ] {\displaystyle {\textsf {IV}}[12]} IV [ 13 ] {\displaystyle {\textsf {IV}}[13]} IV [ 14 ] {\displaystyle {\textsf {IV}}[14]} IV [ 15 ] {\displaystyle {\textsf {IV}}[15]}
B596875BF8FF6DBAFCCA39B089EF4615ECFF4017D020B4B67E77384C772ED802
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]}
53156A66292808F6B2C4F362B204C2BCB84B7213BFA05C4E976CEB7C1B299F73
IV [ 4 ] {\displaystyle {\textsf {IV}}[4]} IV [ 5 ] {\displaystyle {\textsf {IV}}[5]} IV [ 6 ] {\displaystyle {\textsf {IV}}[6]} IV [ 7 ] {\displaystyle {\textsf {IV}}[7]}
DF0CC63C0570AE97DA4441BAA486CE3F6559F5D9B5F2ACC222DACF19B4B52A16
IV [ 8 ] {\displaystyle {\textsf {IV}}[8]} IV [ 9 ] {\displaystyle {\textsf {IV}}[9]} IV [ 10 ] {\displaystyle {\textsf {IV}}[10]} IV [ 11 ] {\displaystyle {\textsf {IV}}[11]}
BBCDACEFDE80953AC9891A2879725B3E7C9FE6330237E440A30BA550553F7431
IV [ 12 ] {\displaystyle {\textsf {IV}}[12]} IV [ 13 ] {\displaystyle {\textsf {IV}}[13]} IV [ 14 ] {\displaystyle {\textsf {IV}}[14]} IV [ 15 ] {\displaystyle {\textsf {IV}}[15]}
BB08043FB34E3E30A0DEC48D54618EAD150317267464BC5732D1501FDE63DC93
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]}
ADD50F3C7F07094EE3F3CEE8F9418A4FB527ECDE5B3D0AE92EF6DEC68076F501
IV [ 4 ] {\displaystyle {\textsf {IV}}[4]} IV [ 5 ] {\displaystyle {\textsf {IV}}[5]} IV [ 6 ] {\displaystyle {\textsf {IV}}[6]} IV [ 7 ] {\displaystyle {\textsf {IV}}[7]}
8CB994CAE5ACA216FBB9EAE4BBA48CC7650A526174725FEA1F9A61A73F8D8085
IV [ 8 ] {\displaystyle {\textsf {IV}}[8]} IV [ 9 ] {\displaystyle {\textsf {IV}}[9]} IV [ 10 ] {\displaystyle {\textsf {IV}}[10]} IV [ 11 ] {\displaystyle {\textsf {IV}}[11]}
B6607378173B539B1BC99853B0C0B9EDDF727FC19B182D47DBEF360CF893A457
IV [ 12 ] {\displaystyle {\textsf {IV}}[12]} IV [ 13 ] {\displaystyle {\textsf {IV}}[13]} IV [ 14 ] {\displaystyle {\textsf {IV}}[14]} IV [ 15 ] {\displaystyle {\textsf {IV}}[15]}
4981F5E570147E80D00C4490CA7D3E305D73940C0E4AE1EC894085E2EDB2D819

Compression

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.

Message Expansion Function MsgExp

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} 0123456789101112131415
τ ( l ) {\displaystyle \tau (l)} 3201745611108915121314

Message Addition Function MsgAdd

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])}

Mix Function Mix

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}}
32even291081624241680
odd517
64even235901632488244056
odd73

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]} 917caf9097884283c938982a
S C 0 [ 1 ] {\displaystyle SC_{0}[1]} 6c1b10a2ba1fca93533e2355
S C 0 [ 2 ] {\displaystyle SC_{0}[2]} 6f352943c519a2e87aeb1c03
S C 0 [ 3 ] {\displaystyle SC_{0}[3]} cf7782439a0fc95462af17b1
S C 0 [ 4 ] {\displaystyle SC_{0}[4]} 2ceb7472fc3dda8ab019a82b
S C 0 [ 5 ] {\displaystyle SC_{0}[5]} 29e96ff202825d079a895407
S C 0 [ 6 ] {\displaystyle SC_{0}[6]} 8a9ba42879f2d0a7ee06a6f7
S C 0 [ 7 ] {\displaystyle SC_{0}[7]} 2eeb2642d76d15eed9fdf5fe

Word-Permutation Function WordPerm

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} 0123456789101112131415
σ ( l ) {\displaystyle \sigma (l)} 6457121514132013811109

Finalization

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

Security

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]

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)[1]
PlatformP11P22P33P44P55P66P77P88
LSH-256- n {\displaystyle n} 3.603.865.263.8911.1715.0315.2814.84
LSH-512- n {\displaystyle n} 2.395.047.765.528.9418.7619.0018.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]
AlgorithmMessage size in bytes
long4,0961,536576648
LSH-256-2563.603.713.904.088.1965.37
Skein-512-2565.015.585.866.4913.12104.50
Blake-2566.617.637.879.0516.5872.50
Grøstl-2569.4810.6812.1813.7137.94227.50
Keccak-25610.5610.529.9011.9923.38187.50
SHA-25610.8211.9112.2613.5124.88106.62
JH-25614.7015.5015.9417.0631.94257.00
LSH-512-5122.392.542.793.3110.8185.62
Skein-512-5124.675.515.806.4413.59108.25
Blake-5124.966.176.827.3814.81116.50
SHA-5127.658.248.699.0317.22138.25
Grøstl-51212.7815.4417.3017.9951.72417.38
JH-51214.2515.6616.1417.3432.69261.00
Keccak-51216.3617.8618.4620.3521.56171.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]
AlgorithmMessage size in bytes
long4,0961,536576648
LSH-256-25611.1711.5312.1612.6322.42192.68
Skein-512-25615.6416.7218.3322.6875.75609.25
Blake-25617.9419.1120.8825.4483.94542.38
SHA-25619.9121.1423.0328.1390.89578.50
JH-25634.6636.0638.1043.51113.92924.12
Keccak-25636.0338.0140.5448.13125.001000.62
Grøstl-25640.7042.7646.0354.94167.521020.62
LSH-512-5128.949.5610.5512.2838.82307.98
Blake-51213.4614.8216.8820.9877.53623.62
Skein-512-51215.6116.7318.3522.5675.59612.88
JH-51234.8836.2638.3644.01116.41939.38
SHA-51244.1346.4149.9754.55135.591088.38
Keccak-51263.3164.5967.8577.21121.28968.00
Grøstl-512131.35138.49150.15166.54446.533518.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.9

KCMVP

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

Standardization

LSH is included in the following standard.

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

References

  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 ↩

  9. "KISA 암호이용활성화 - 암호알고리즘 소스코드". seed.kisa.or.kr. https://seed.kisa.or.kr/kisa/Board/22/detailView.do ↩

  10. "KISA 암호이용활성화 - 개요". seed.kisa.or.kr. https://seed.kisa.or.kr/kisa/kcmvp/EgovSummary.do ↩

  11. "Korean Standards & Certifications (in Korean)". https://standard.go.kr ↩