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

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 ${\displaystyle n}$-bit hash value from the final chaining variable.
 function Hash function LSH input: Bit string message ${\displaystyle m}$ output: Hash value ${\displaystyle h\in \{0,1\}^{n}}$ procedure ${\displaystyle \qquad }$One-zeros padding of ${\displaystyle m}$ ${\displaystyle \qquad }$Generation of ${\displaystyle t}$ message blocks ${\displaystyle \{{\textsf {M}}^{(i)}\}_{i=0}^{t-1}}$, where ${\displaystyle t={\Big \lceil }{\frac {|m|+1}{32w}}{\Big \rceil }}$ from the padded bit string ${\displaystyle \qquad }$${\displaystyle {\textsf {CV}}^{(0)}\leftarrow {\textsf {IV}}}$ ${\displaystyle \qquad }$for ${\displaystyle i=0}$ to ${\displaystyle (t-1)}$ do ${\displaystyle \qquad }$${\displaystyle \qquad }$${\displaystyle {\textsf {CV}}^{(i+1)}\leftarrow {\textrm {CF}}({\textsf {CV}}^{(i)},{\textsf {M}}^{(i)})}$ ${\displaystyle \qquad }$end for ${\displaystyle \qquad }$${\displaystyle h\leftarrow {\textrm {FIN}}_{n}({\textsf {CV}}^{(t)})}$ ${\displaystyle \qquad }$return ${\displaystyle h}$

The specifications of the hash function LSH are as follows.

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

Initialization

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

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

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

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

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

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

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

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

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

Compression

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

The following four functions are used in a compression function:

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

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

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

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

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

Message Expansion Function MsgExp

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

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

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

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

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

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

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

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

Mix Function Mix

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

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

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

 function Two-word mix function ${\displaystyle {\textrm {Mix}}_{j,l}}$ input: Words ${\displaystyle X}$ and ${\displaystyle Y}$ output: Words ${\displaystyle X}$ and ${\displaystyle Y}$ procedure ${\displaystyle \qquad }$${\displaystyle X\leftarrow X\boxplus Y}$;${\displaystyle \qquad X\leftarrow X^{\lll \alpha _{j}}}$; ${\displaystyle \qquad }$${\displaystyle X\leftarrow X\oplus SC_{j}[l]}$; ${\displaystyle \qquad }$${\displaystyle Y\leftarrow X\boxplus Y}$;${\displaystyle \qquad Y\leftarrow Y^{\lll \beta _{j}}}$; ${\displaystyle \qquad }$${\displaystyle X\leftarrow X\boxplus Y}$;${\displaystyle \qquad Y\leftarrow Y^{\lll \gamma _{l}}}$; ${\displaystyle \qquad }$return ${\displaystyle X}$, ${\displaystyle Y}$;

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

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

Bit rotation amounts ${\displaystyle \alpha _{j}}$, ${\displaystyle \beta _{j}}$, and ${\displaystyle \gamma _{l}}$
${\displaystyle w}$ ${\displaystyle j}$ ${\displaystyle \alpha _{j}}$ ${\displaystyle \beta _{j}}$ ${\displaystyle \gamma _{0}}$ ${\displaystyle \gamma _{1}}$ ${\displaystyle \gamma _{2}}$ ${\displaystyle \gamma _{3}}$ ${\displaystyle \gamma _{4}}$ ${\displaystyle \gamma _{5}}$ ${\displaystyle \gamma _{6}}$ ${\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 ${\displaystyle j}$-th 8-word array constant ${\displaystyle {\textsf {SC}}_{j}=(SC_{j}[0],\ldots ,SC_{j}[7])}$ used in ${\displaystyle {\textrm {Mix}}_{j,l}}$ for ${\displaystyle 0\leq l<8}$ is defined as follows. The initial 8-word array constant ${\displaystyle {\textsf {SC}}_{0}=(SC_{0}[0],\ldots ,SC_{0}[7])}$ is defined in the following table. For ${\displaystyle 1\leq j, the ${\displaystyle j}$-th constant ${\displaystyle {\textsf {SC}}_{j}=(SC_{j}[0],\ldots ,SC_{j}[7])}$ is generated by ${\displaystyle SC_{j}[l]\leftarrow SC_{j-1}[l]\boxplus SC_{j-1}[l]^{\lll 8}}$ for ${\displaystyle 0\leq l<8}$.

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

Word-Permutation Function WordPerm

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

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

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

 ${\displaystyle l}$ ${\displaystyle \sigma (l)}$ 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 ${\displaystyle {\textrm {FIN}}_{n}:{\mathcal {W}}^{16}\rightarrow \{0,1\}^{n}}$ returns ${\displaystyle n}$-bit hash value ${\displaystyle h}$ from the final chaining variable ${\displaystyle {\textsf {CV}}^{(t)}=(CV^{(t)}[0],\ldots ,CV^{(t)}[15])}$. When ${\displaystyle {\textsf {H}}=(H[0],\ldots ,H[7])}$ is an 8-word variable and ${\displaystyle {\textsf {h}}_{\textsf {b}}=(h_{b}[0],\ldots ,h_{b}[w-1])}$ is a ${\displaystyle w}$-byte variable, the finalization function ${\displaystyle {\textrm {FIN}}_{n}}$ performs the following procedure.

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

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

Security

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

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