LSH (hash function)

From HandWiki
Short description: 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).

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 [math]\displaystyle{ n }[/math]-bit hash value from the final chaining variable.
  • function Hash function LSH
  • input: Bit string message [math]\displaystyle{ m }[/math]
  • output: Hash value [math]\displaystyle{ h \in \{ 0, 1 \}^n }[/math]
  • procedure

[math]\displaystyle{ \qquad }[/math]One-zeros padding of [math]\displaystyle{ m }[/math]

[math]\displaystyle{ \qquad }[/math]Generation of [math]\displaystyle{ t }[/math] message blocks [math]\displaystyle{ \{ \textsf{M}^{(i)} \}_{i=0}^{t-1} }[/math], where [math]\displaystyle{ t = \Big\lceil \frac{|m| + 1}{32w} \Big\rceil }[/math] from the padded bit string

[math]\displaystyle{ \qquad }[/math][math]\displaystyle{ \textsf{CV}^{(0)} \leftarrow \textsf{IV} }[/math]

[math]\displaystyle{ \qquad }[/math]for [math]\displaystyle{ i = 0 }[/math] to [math]\displaystyle{ (t-1) }[/math] do

[math]\displaystyle{ \qquad }[/math][math]\displaystyle{ \qquad }[/math][math]\displaystyle{ \textsf{CV}^{(i+1)} \leftarrow \textrm{CF} (\textsf{CV}^{(i)}, \textsf{M}^{(i)}) }[/math]

[math]\displaystyle{ \qquad }[/math]end for

[math]\displaystyle{ \qquad }[/math][math]\displaystyle{ h \leftarrow \textrm{FIN}_n(\textsf{CV}^{(t)}) }[/math]

[math]\displaystyle{ \qquad }[/math]return [math]\displaystyle{ h }[/math]

The specifications of the hash function LSH are as follows.

Hash function LSH specifications
Algorithm Digest size in bits ([math]\displaystyle{ n }[/math]) Number of step functions ([math]\displaystyle{ N_s }[/math]) Chaining variable size in bits Message block size in bits Word size in bits ([math]\displaystyle{ w }[/math])
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 [math]\displaystyle{ m }[/math] be a given bit string message. The given [math]\displaystyle{ m }[/math] is padded by one-zeros, i.e., the bit ‘1’ is appended to the end of [math]\displaystyle{ m }[/math], and the bit ‘0’s are appended until a bit length of a padded message is [math]\displaystyle{ 32wt }[/math], where [math]\displaystyle{ t = \lceil (|m| + 1)/32w\rceil }[/math] and [math]\displaystyle{ \lceil x \rceil }[/math] is the smallest integer not less than [math]\displaystyle{ x }[/math].

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

[math]\displaystyle{ M[s] \leftarrow m[ws/8+(w/8-1)] \| \ldots \| m[ws/8+1] \| m[ws/8] }[/math] [math]\displaystyle{ (0 \le s \le (32t-1)) }[/math]

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

[math]\displaystyle{ \textsf{M}^{(i)} \leftarrow (M[32i], M[32i+1], \ldots , M[32i+31]) }[/math] [math]\displaystyle{ (0 \le i \le (t-1)) }[/math]

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

[math]\displaystyle{ \textsf{CV}^{(0)}[l] \leftarrow \textsf{IV}[l] }[/math] [math]\displaystyle{ (0 \le l \le 15) }[/math]

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

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

Compression

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

The following four functions are used in a compression function:

  • Message expansion function [math]\displaystyle{ \textrm{MsgExp}: \mathcal{W}^{32} \rightarrow \mathcal{W}^{16(Ns+1)} }[/math]
  • Message addition function [math]\displaystyle{ \textrm{MsgAdd}: \mathcal{W}^{16} \times \mathcal{W}^{16} \rightarrow \mathcal{W}^{16} }[/math]
  • Mix function [math]\displaystyle{ \textrm{Mix}_j: \mathcal{W}^{16} \rightarrow \mathcal{W}^{16} }[/math]
  • Word-permutation function [math]\displaystyle{ \textrm{WordPerm}: \mathcal{W}^{16} \rightarrow \mathcal{W}^{16} }[/math]

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 [math]\displaystyle{ \textrm{MsgExp} }[/math] generates [math]\displaystyle{ (N_s+1) }[/math] 16-word array sub-messages [math]\displaystyle{ \{ \textsf{M}_j^{(i)} \}_{j=0}^{N_s} }[/math] from given [math]\displaystyle{ \textsf{M}^{(i)} }[/math]. Let [math]\displaystyle{ \textsf{T} = (T[0], \ldots , T[15]) }[/math] be a temporary 16-word array set to the [math]\displaystyle{ i }[/math]-th chaining variable [math]\displaystyle{ \textsf{CV}^{(i)} }[/math]. The [math]\displaystyle{ j }[/math]-th step function [math]\displaystyle{ \textrm{Step}_j }[/math] having two inputs [math]\displaystyle{ \textsf{T} }[/math] and [math]\displaystyle{ \textsf{M}_j^{(i)} }[/math] updates [math]\displaystyle{ \textsf{T} }[/math], i.e., [math]\displaystyle{ \textsf{T} \leftarrow \textrm{Step}_j \left( \textsf{T}, \textsf{M}_j^{(i)} \right) }[/math]. All step functions are proceeded in order [math]\displaystyle{ j = 0, \ldots, N_s - 1 }[/math]. Then one more [math]\displaystyle{ \textrm{MsgAdd} }[/math] operation by [math]\displaystyle{ \textsf{M}_{N_s}^{(i)} }[/math] is proceeded, and the [math]\displaystyle{ (i+1) }[/math]-th chaining variable [math]\displaystyle{ \textsf{CV}^{(i+1)} }[/math] is set to [math]\displaystyle{ \textsf{T} }[/math]. The process of a compression function in detail is as follows.

  • function Compression function [math]\displaystyle{ \textrm{CF} }[/math]
  • input: The [math]\displaystyle{ i }[/math]-th chaining variable [math]\displaystyle{ \textsf{CV}^{(i)} \in \mathcal{W}^{16} }[/math] and the [math]\displaystyle{ i }[/math]-th message block [math]\displaystyle{ \textsf{M}^{(i)} \in \mathcal{W}^{32} }[/math]
  • output: The [math]\displaystyle{ (i + 1) }[/math]-th chaining variable [math]\displaystyle{ \textsf{CV}^{(i+1)} \in \mathcal{W}^{16} }[/math]
  • procedure

[math]\displaystyle{ \qquad }[/math][math]\displaystyle{ \{ \textsf{M}_j^{(i)} \}_{j=0}^{N_s} \leftarrow \textrm{MsgExp} \left( \textsf{M}^{(i)} \right) }[/math]

[math]\displaystyle{ \qquad }[/math][math]\displaystyle{ \textsf{T} \leftarrow \textsf{CV}^{(i)} }[/math]

[math]\displaystyle{ \qquad }[/math]for [math]\displaystyle{ j = 0 }[/math] to [math]\displaystyle{ (N_s - 1) }[/math] do

[math]\displaystyle{ \qquad }[/math][math]\displaystyle{ \qquad }[/math][math]\displaystyle{ \textsf{T} \leftarrow \textrm{Step}_j \left( \textsf{T}, \textsf{M}_j^{(i)} \right) }[/math]

[math]\displaystyle{ \qquad }[/math]end for

[math]\displaystyle{ \qquad }[/math][math]\displaystyle{ \textsf{CV}^{(i+1)} \leftarrow \textrm{MsgAdd} \left( \textsf{T}, \textsf{M}_{N_s}^{(i)} \right) }[/math]

[math]\displaystyle{ \qquad }[/math]return [math]\displaystyle{ \textsf{CV}^{(i+1)} }[/math]

Here the [math]\displaystyle{ j }[/math]-th step function [math]\displaystyle{ \textrm{Step}_j : \mathcal{W}^{16} \times \mathcal{W}^{16} \rightarrow \mathcal{W}^{16} }[/math] is as follows.

[math]\displaystyle{ \textrm{Step}_j := \textrm{WordPerm} \circ \textrm{Mix}_j \circ \textrm{MsgAdd} }[/math] [math]\displaystyle{ (0 \le j \le (N_s-1)) }[/math]

The following figure shows the [math]\displaystyle{ j }[/math]-th step function [math]\displaystyle{ \textrm{Step}_j }[/math] of a compression function.

The [math]\displaystyle{ j }[/math]-th step function [math]\displaystyle{ \textrm{Step}_j }[/math]

Message Expansion Function MsgExp

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

  • [math]\displaystyle{ \textsf{M}_0^{(i)} \leftarrow (M^{(i)}[0], M^{(i)}[1], \ldots , M^{(i)}[15]) }[/math]
  • [math]\displaystyle{ \textsf{M}_1^{(i)} \leftarrow (M^{(i)}[16], M^{(i)}[17], \ldots , M^{(i)}[31]) }[/math]

The next sub-messages [math]\displaystyle{ \{ \textsf{M}_j^{(i)} = ( M_{j}^{(i)}[0], \ldots , M_{j}^{(i)}[15] ) \}_{j=2}^{N_s} }[/math] are generated as follows.

  • [math]\displaystyle{ \textsf{M}_j^{(i)}[l] \leftarrow \textsf{M}_{j-1}^{(i)}[l] \boxplus\textsf{M}_{j-2}^{(i)}[\tau(l)] }[/math] [math]\displaystyle{ (0 \le l \le 15, \ 2 \le j \le N_s) }[/math]

Here [math]\displaystyle{ \tau }[/math] is the permutation over [math]\displaystyle{ \mathbb{Z}_{16} }[/math] defined as follows.

The permutation [math]\displaystyle{ \tau : \mathbb{Z}_{16} \rightarrow \mathbb{Z}_{16} }[/math]
[math]\displaystyle{ l }[/math] 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
[math]\displaystyle{ \tau(l) }[/math] 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 [math]\displaystyle{ \textsf{X} = (X[0], \ldots , X[15]) }[/math] and [math]\displaystyle{ \textsf{Y} = (Y[0], \ldots , Y[15]) }[/math], the message addition function [math]\displaystyle{ \textrm{MsgAdd} : \mathcal{W}^{16} \times \mathcal{W}^{16} \rightarrow \mathcal{W}^{16} }[/math] is defined as follows.

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

Mix Function Mix

The [math]\displaystyle{ j }[/math]-th mix function [math]\displaystyle{ \textrm{Mix}_j: \mathcal{W}^{16} \rightarrow \mathcal{W}^{16} }[/math] updates the 16-word array [math]\displaystyle{ \textsf{T} = (T[0], \ldots , T[15]) }[/math] by mixing every two-word pair; [math]\displaystyle{ T[l] }[/math] and [math]\displaystyle{ T[l+8] }[/math] for [math]\displaystyle{ (0 \le l \lt 8) }[/math]. For [math]\displaystyle{ 0 \le j \lt N_s }[/math], the mix function [math]\displaystyle{ \textrm{Mix}_j }[/math] proceeds as follows.

[math]\displaystyle{ (T[l], T[l+8]) \leftarrow \textrm{Mix}_{j,l}(T[l], T[l+8]) }[/math] [math]\displaystyle{ (0 \le l \lt 8) }[/math]

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

  • function Two-word mix function [math]\displaystyle{ \textrm{Mix}_{j,l} }[/math]
  • input: Words [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math]
  • output: Words [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math]
  • procedure

[math]\displaystyle{ \qquad }[/math][math]\displaystyle{ X \leftarrow X \boxplus Y }[/math];[math]\displaystyle{ \qquad X \leftarrow X^{\lll \alpha_j} }[/math];

[math]\displaystyle{ \qquad }[/math][math]\displaystyle{ X \leftarrow X \oplus SC_j[l] }[/math];

[math]\displaystyle{ \qquad }[/math][math]\displaystyle{ Y \leftarrow X \boxplus Y }[/math];[math]\displaystyle{ \qquad Y \leftarrow Y^{\lll \beta_j} }[/math];

[math]\displaystyle{ \qquad }[/math][math]\displaystyle{ X \leftarrow X \boxplus Y }[/math];[math]\displaystyle{ \qquad Y \leftarrow Y^{\lll \gamma_l} }[/math];

[math]\displaystyle{ \qquad }[/math]return [math]\displaystyle{ X }[/math], [math]\displaystyle{ Y }[/math];

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

Two-word mix function [math]\displaystyle{ \textrm{Mix}_{j,l} (X, Y) }[/math]

The bit rotation amounts [math]\displaystyle{ \alpha_j }[/math], [math]\displaystyle{ \beta_j }[/math], [math]\displaystyle{ \gamma_l }[/math] used in [math]\displaystyle{ \textrm{Mix}_{j,l} }[/math] are shown in the following table.

Bit rotation amounts [math]\displaystyle{ \alpha_j }[/math], [math]\displaystyle{ \beta_j }[/math], and [math]\displaystyle{ \gamma_l }[/math]
[math]\displaystyle{ w }[/math] [math]\displaystyle{ j }[/math] [math]\displaystyle{ \alpha_j }[/math] [math]\displaystyle{ \beta_j }[/math] [math]\displaystyle{ \gamma_0 }[/math] [math]\displaystyle{ \gamma_1 }[/math] [math]\displaystyle{ \gamma_2 }[/math] [math]\displaystyle{ \gamma_3 }[/math] [math]\displaystyle{ \gamma_4 }[/math] [math]\displaystyle{ \gamma_5 }[/math] [math]\displaystyle{ \gamma_6 }[/math] [math]\displaystyle{ \gamma_7 }[/math]
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 [math]\displaystyle{ j }[/math]-th 8-word array constant [math]\displaystyle{ \textsf{SC}_j = (SC_j[0], \ldots , SC_j[7]) }[/math] used in [math]\displaystyle{ \textrm{Mix}_{j,l} }[/math] for [math]\displaystyle{ 0 \le l \lt 8 }[/math] is defined as follows. The initial 8-word array constant [math]\displaystyle{ \textsf{SC}_0 = (SC_0[0], \ldots , SC_0[7]) }[/math] is defined in the following table. For [math]\displaystyle{ 1 \le j \lt N_s }[/math], the [math]\displaystyle{ j }[/math]-th constant [math]\displaystyle{ \textsf{SC}_j = (SC_j[0], \ldots , SC_j[7]) }[/math] is generated by [math]\displaystyle{ SC_j[l] \leftarrow SC_{j-1}[l] \boxplus SC_{j-1}[l]^{\lll 8} }[/math] for [math]\displaystyle{ 0 \le l \lt 8 }[/math].

Initial 8-word array constant [math]\displaystyle{ \textsf{SC}_0 }[/math]
[math]\displaystyle{ w = 32 }[/math] [math]\displaystyle{ w = 64 }[/math]
[math]\displaystyle{ SC_0[0] }[/math] 917caf90 97884283c938982a
[math]\displaystyle{ SC_0[1] }[/math] 6c1b10a2 ba1fca93533e2355
[math]\displaystyle{ SC_0[2] }[/math] 6f352943 c519a2e87aeb1c03
[math]\displaystyle{ SC_0[3] }[/math] cf778243 9a0fc95462af17b1
[math]\displaystyle{ SC_0[4] }[/math] 2ceb7472 fc3dda8ab019a82b
[math]\displaystyle{ SC_0[5] }[/math] 29e96ff2 02825d079a895407
[math]\displaystyle{ SC_0[6] }[/math] 8a9ba428 79f2d0a7ee06a6f7
[math]\displaystyle{ SC_0[7] }[/math] 2eeb2642 d76d15eed9fdf5fe

Word-Permutation Function WordPerm

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

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

Here [math]\displaystyle{ \sigma }[/math] is the permutation over [math]\displaystyle{ \mathbb{Z}_{16} }[/math] defined by the following table.

The permutation [math]\displaystyle{ \sigma : \mathbb{Z}_{16} \rightarrow \mathbb{Z}_{16} }[/math]
[math]\displaystyle{ l }[/math] 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
[math]\displaystyle{ \sigma(l) }[/math] 6 4 5 7 12 15 14 13 2 0 1 3 8 11 10 9

Finalization

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

  • [math]\displaystyle{ H[l] \leftarrow CV^{(t)}[l] \oplus CV^{(t)}[l+8] }[/math] [math]\displaystyle{ (0 \le l \le 7) }[/math]
  • [math]\displaystyle{ h_b[s] \leftarrow H[\lfloor 8s/w\rfloor ]^{\ggg (8s \mod w)}_{[7:0]} }[/math] [math]\displaystyle{ (0 \le s \le (w-1)) }[/math]
  • [math]\displaystyle{ h \leftarrow (h_b[0] \| \ldots \| h_b[w-1])_{[0:n-1]} }[/math]

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

Security

LSH is secure against known attacks on hash functions up to now. LSH is collision-resistant for [math]\displaystyle{ q \lt 2^{n/2} }[/math] and preimage-resistant and second-preimage-resistant for [math]\displaystyle{ q \lt 2^n }[/math] in the ideal cipher model, where [math]\displaystyle{ q }[/math] 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]
Platform P1[lower-alpha 1] P2[lower-alpha 2] P3[lower-alpha 3] P4[lower-alpha 4] P5[lower-alpha 5] P6[lower-alpha 6] P7[lower-alpha 7] P8[lower-alpha 8]
LSH-256-[math]\displaystyle{ n }[/math] 3.60 3.86 5.26 3.89 11.17 15.03 15.28 14.84
LSH-512-[math]\displaystyle{ n }[/math] 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

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

KCMVP

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

Standardization

LSH is included in the following standard.

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

References

  1. ↑ 1.0 1.1 1.2 1.3 1.4 1.5 Kim, Dong-Chan; Hong, Deukjo; Lee, Jung-Keun; Kim, Woo-Hwan; Kwon, Daesung (2015). "LSH: A New Fast Secure Hash Function Family" (in en). Information Security and Cryptology - ICISC 2014. Lecture Notes in Computer Science. 8949. Springer International Publishing. pp. 286–313. doi:10.1007/978-3-319-15943-0_18. ISBN 978-3-319-15943-0. https://link.springer.com/chapter/10.1007/978-3-319-15943-0_18. 
  2. ↑ "KISA 암호이용활성화 - 암호알고리즘 소스코드". https://seed.kisa.or.kr/kisa/Board/22/detailView.do. 
  3. ↑ "KISA 암호이용활성화 - 개요". https://seed.kisa.or.kr/kisa/kcmvp/EgovSummary.do. 
  4. ↑ "Korean Standards & Certifications (in Korean)". https://standard.go.kr. 



Retrieved from "https://handwiki.org/wiki/index.php?title=LSH_(hash_function)&oldid=3367458"