# LSH (hash function)

LSH is a cryptographic hash function designed in 2014 by South Korea to provide integrity in general-purpose software environments such as PCs and smart devices. LSH is one of the cryptographic algorithms approved by the Korean Cryptographic Module Validation Program (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.
* Initialization:
** One-zeros padding of a given bit string message.
** Conversion to 32-word array message blocks from the padded bit string message.
** Initialization of a chaining variable with the initialization vector.
* Compression:
** Updating of chaining variables by iteration of a compression function with message blocks.
* Finalization:
** Generation of an $n$-bit hash value from the final chaining variable.
* function Hash function LSH
* input: Bit string message $m$
* output: Hash value $h\in \{0,1\}^{n}$
* procedure
* $\qquad$One-zeros padding of $m$
* $\qquad$Generation of $t$ message blocks $\{{\textsf {M}}^{(i)}\}_{i=0}^{t-1}$, where $t={\Big \lceil }{\frac {|m|+1}{32w}}{\Big \rceil }$ from the padded bit string
* $\qquad$${\textsf {CV}}^{(0)}\leftarrow {\textsf {IV}}$
* $\qquad$for $i=0$ to $(t-1)$ do
* $\qquad$$\qquad$${\textsf {CV}}^{(i+1)}\leftarrow {\textrm {CF}}({\textsf {CV}}^{(i)},{\textsf {M}}^{(i)})$
* $\qquad$end for
* $\qquad$$h\leftarrow {\textrm {FIN}}_{n}({\textsf {CV}}^{(t)})$
* $\qquad$return $h$
The specifications of the hash function LSH are as follows.
Hash function LSH specifications :
| Algorithm | Digest size in bits ($n$) | Number of step functions ($N_{s}$) | Chaining variable size in bits | Message block size in bits | Word size in bits ($w$) |
| LSH-256-224 | 224 | 26 | 512 | 1024 | 32 |
| LSH-256-256 | 256 | 26 | 512 | 1024 | 32 |
| LSH-512-224 | 224 | 28 | 1024 | 2048 | 64 |
| LSH-512-256 | 256 | 28 | 1024 | 2048 | 64 |
| LSH-512-384 | 384 | 28 | 1024 | 2048 | 64 |
| LSH-512-512 | 512 | 28 | 1024 | 2048 | 64 |

### Initialization

Let $m$ be a given bit string message. The given $m$ is padded by one-zeros, i.e., the bit ‘1’ is appended to the end of $m$, and the bit ‘0’s are appended until a bit length of a padded message is $32wt$, where $t=\lceil (|m|+1)/32w\rceil$ and $\lceil x\rceil$ is the smallest integer not less than $x$.
Let $m_{p}=m_{0}\|m_{1}\|\ldots \|m_{(32wt-1)}$ be the one-zeros-padded $32wt$-bit string of $m$. Then $m_{p}$ is considered as a $4wt$-byte array $m_{a}=(m[0],\ldots ,m[4wt-1])$, where $m[k]=m_{8k}\|m_{(8k+1)}\|\ldots \|m_{(8k+7)}$ for all $0\leq k\leq (4wt-1)$. The $4wt$-byte array $m_{a}$ converts into a $32t$-word array ${\textsf {M}}=(M[0],\ldots ,M[32t-1])$ as follows.
$M[s]\leftarrow m[ws/8+(w/8-1)]\|\ldots \|m[ws/8+1]\|m[ws/8]$ $(0\leq s\leq (32t-1))$
From the word array ${\textsf {M}}$, we define the $t$ 32-word array message blocks $\{{\textsf {M}}^{(i)}\}_{i=0}^{t-1}$ as follows.
${\textsf {M}}^{(i)}\leftarrow (M[32i],M[32i+1],\ldots ,M[32i+31])$ $(0\leq i\leq (t-1))$
The 16-word array chaining variable ${\textsf {CV}}^{(0)}$ is initialized to the initialization vector ${\textsf {IV}}$.
${\textsf {CV}}^{(0)}[l]\leftarrow {\textsf {IV}}[l]$ $(0\leq l\leq 15)$
The initialization vector ${\textsf {IV}}$ is as follows. In the following tables, all values are expressed in hexadecimal form.
LSH-256-224 initialization vector :
| ${\textsf {IV}}[0]$ | ${\textsf {IV}}[1]$ | ${\textsf {IV}}[2]$ | ${\textsf {IV}}[3]$ | ${\textsf {IV}}[4]$ | ${\textsf {IV}}[5]$ | ${\textsf {IV}}[6]$ | ${\textsf {IV}}[7]$ |
| 068608D3 | 62D8F7A7 | D76652AB | 4C600A43 | BDC40AA8 | 1ECA0B68 | DA1A89BE | 3147D354 |
| ${\textsf {IV}}[8]$ | ${\textsf {IV}}[9]$ | ${\textsf {IV}}[10]$ | ${\textsf {IV}}[11]$ | ${\textsf {IV}}[12]$ | ${\textsf {IV}}[13]$ | ${\textsf {IV}}[14]$ | ${\textsf {IV}}[15]$ |
| 707EB4F9 | F65B3862 | 6B0B2ABE | 56B8EC0A | CF237286 | EE0D1727 | 33636595 | 8BB8D05F |
LSH-256-256 initialization vector :
| ${\textsf {IV}}[0]$ | ${\textsf {IV}}[1]$ | ${\textsf {IV}}[2]$ | ${\textsf {IV}}[3]$ | ${\textsf {IV}}[4]$ | ${\textsf {IV}}[5]$ | ${\textsf {IV}}[6]$ | ${\textsf {IV}}[7]$ |
| 46A10F1F | FDDCE486 | B41443A8 | 198E6B9D | 3304388D | B0F5A3C7 | B36061C4 | 7ADBD553 |
| ${\textsf {IV}}[8]$ | ${\textsf {IV}}[9]$ | ${\textsf {IV}}[10]$ | ${\textsf {IV}}[11]$ | ${\textsf {IV}}[12]$ | ${\textsf {IV}}[13]$ | ${\textsf {IV}}[14]$ | ${\textsf {IV}}[15]$ |
| 105D5378 | 2F74DE54 | 5C2F2D95 | F2553FBE | 8051357A | 138668C8 | 47AA4484 | E01AFB41 |
LSH-512-224 initialization vector :
| ${\textsf {IV}}[0]$ | ${\textsf {IV}}[1]$ | ${\textsf {IV}}[2]$ | ${\textsf {IV}}[3]$ |
| 0C401E9FE8813A55 | 4A5F446268FD3D35 | FF13E452334F612A | F8227661037E354A |
| ${\textsf {IV}}[4]$ | ${\textsf {IV}}[5]$ | ${\textsf {IV}}[6]$ | ${\textsf {IV}}[7]$ |
| A5F223723C9CA29D | 95D965A11AED3979 | 01E23835B9AB02CC | 52D49CBAD5B30616 |
| ${\textsf {IV}}[8]$ | ${\textsf {IV}}[9]$ | ${\textsf {IV}}[10]$ | ${\textsf {IV}}[11]$ |
| 9E5C2027773F4ED3 | 66A5C8801925B701 | 22BBC85B4C6779D9 | C13171A42C559C23 |
| ${\textsf {IV}}[12]$ | ${\textsf {IV}}[13]$ | ${\textsf {IV}}[14]$ | ${\textsf {IV}}[15]$ |
| 31E2B67D25BE3813 | D522C4DEED8E4D83 | A79F5509B43FBAFE | E00D2CD88B4B6C6A |
LSH-512-256 initialization vector :
| ${\textsf {IV}}[0]$ | ${\textsf {IV}}[1]$ | ${\textsf {IV}}[2]$ | ${\textsf {IV}}[3]$ |
| 6DC57C33DF989423 | D8EA7F6E8342C199 | 76DF8356F8603AC4 | 40F1B44DE838223A |
| ${\textsf {IV}}[4]$ | ${\textsf {IV}}[5]$ | ${\textsf {IV}}[6]$ | ${\textsf {IV}}[7]$ |
| 39FFE7CFC31484CD | 39C4326CC5281548 | 8A2FF85A346045D8 | FF202AA46DBDD61E |
| ${\textsf {IV}}[8]$ | ${\textsf {IV}}[9]$ | ${\textsf {IV}}[10]$ | ${\textsf {IV}}[11]$ |
| CF785B3CD5FCDB8B | 1F0323B64A8150BF | FF75D972F29EA355 | 2E567F30BF1CA9E1 |
| ${\textsf {IV}}[12]$ | ${\textsf {IV}}[13]$ | ${\textsf {IV}}[14]$ | ${\textsf {IV}}[15]$ |
| B596875BF8FF6DBA | FCCA39B089EF4615 | ECFF4017D020B4B6 | 7E77384C772ED802 |
LSH-512-384 initialization vector :
| ${\textsf {IV}}[0]$ | ${\textsf {IV}}[1]$ | ${\textsf {IV}}[2]$ | ${\textsf {IV}}[3]$ |
| 53156A66292808F6 | B2C4F362B204C2BC | B84B7213BFA05C4E | 976CEB7C1B299F73 |
| ${\textsf {IV}}[4]$ | ${\textsf {IV}}[5]$ | ${\textsf {IV}}[6]$ | ${\textsf {IV}}[7]$ |
| DF0CC63C0570AE97 | DA4441BAA486CE3F | 6559F5D9B5F2ACC2 | 22DACF19B4B52A16 |
| ${\textsf {IV}}[8]$ | ${\textsf {IV}}[9]$ | ${\textsf {IV}}[10]$ | ${\textsf {IV}}[11]$ |
| BBCDACEFDE80953A | C9891A2879725B3E | 7C9FE6330237E440 | A30BA550553F7431 |
| ${\textsf {IV}}[12]$ | ${\textsf {IV}}[13]$ | ${\textsf {IV}}[14]$ | ${\textsf {IV}}[15]$ |
| BB08043FB34E3E30 | A0DEC48D54618EAD | 150317267464BC57 | 32D1501FDE63DC93 |
LSH-512-512 initialization vector :
| ${\textsf {IV}}[0]$ | ${\textsf {IV}}[1]$ | ${\textsf {IV}}[2]$ | ${\textsf {IV}}[3]$ |
| ADD50F3C7F07094E | E3F3CEE8F9418A4F | B527ECDE5B3D0AE9 | 2EF6DEC68076F501 |
| ${\textsf {IV}}[4]$ | ${\textsf {IV}}[5]$ | ${\textsf {IV}}[6]$ | ${\textsf {IV}}[7]$ |
| 8CB994CAE5ACA216 | FBB9EAE4BBA48CC7 | 650A526174725FEA | 1F9A61A73F8D8085 |
| ${\textsf {IV}}[8]$ | ${\textsf {IV}}[9]$ | ${\textsf {IV}}[10]$ | ${\textsf {IV}}[11]$ |
| B6607378173B539B | 1BC99853B0C0B9ED | DF727FC19B182D47 | DBEF360CF893A457 |
| ${\textsf {IV}}[12]$ | ${\textsf {IV}}[13]$ | ${\textsf {IV}}[14]$ | ${\textsf {IV}}[15]$ |
| 4981F5E570147E80 | D00C4490CA7D3E30 | 5D73940C0E4AE1EC | 894085E2EDB2D819 |

### Compression

In this stage, the $t$ 32-word array message blocks $\{{\textsf {M}}^{(i)}\}_{i=0}^{t-1}$, which are generated from a message $m$ in the initialization stage, are compressed by iteration of compression functions. The compression function ${\textrm {CF}}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{32}\rightarrow {\mathcal {W}}^{16}$ has two inputs; the $i$-th 16-word chaining variable ${\textsf {CV}}^{(i)}$ and the $i$-th 32-word message block ${\textsf {M}}^{(i)}$. And it returns the $(i+1)$-th 16-word chaining variable ${\textsf {CV}}^{(i+1)}$. Here and subsequently, ${\mathcal {W}}^{t}$ denotes the set of all $t$-word arrays for $t\geq 1$.
The following four functions are used in a compression function:
* Message expansion function ${\textrm {MsgExp}}:{\mathcal {W}}^{32}\rightarrow {\mathcal {W}}^{16(Ns+1)}$
* Message addition function ${\textrm {MsgAdd}}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}$
* Mix function ${\textrm {Mix}}_{j}:{\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}$
* Word-permutation function ${\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 ${\textrm {MsgExp}}$ generates $(N_{s}+1)$ 16-word array sub-messages $\{{\textsf {M}}_{j}^{(i)}\}_{j=0}^{N_{s}}$ from given ${\textsf {M}}^{(i)}$. Let ${\textsf {T}}=(T[0],\ldots ,T[15])$ be a temporary 16-word array set to the $i$-th chaining variable ${\textsf {CV}}^{(i)}$. The $j$-th step function ${\textrm {Step}}_{j}$ having two inputs ${\textsf {T}}$ and ${\textsf {M}}_{j}^{(i)}$ updates ${\textsf {T}}$, i.e., ${\textsf {T}}\leftarrow {\textrm {Step}}_{j}\left({\textsf {T}},{\textsf {M}}_{j}^{(i)}\right)$. All step functions are proceeded in order $j=0,\ldots ,N_{s}-1$. Then one more ${\textrm {MsgAdd}}$ operation by ${\textsf {M}}_{N_{s}}^{(i)}$ is proceeded, and the $(i+1)$-th chaining variable ${\textsf {CV}}^{(i+1)}$ is set to ${\textsf {T}}$. The process of a compression function in detail is as follows.
* function Compression function ${\textrm {CF}}$
* input: The $i$-th chaining variable ${\textsf {CV}}^{(i)}\in {\mathcal {W}}^{16}$ and the $i$-th message block ${\textsf {M}}^{(i)}\in {\mathcal {W}}^{32}$
* output: The $(i+1)$-th chaining variable ${\textsf {CV}}^{(i+1)}\in {\mathcal {W}}^{16}$
* procedure
* $\qquad$$\{{\textsf {M}}_{j}^{(i)}\}_{j=0}^{N_{s}}\leftarrow {\textrm {MsgExp}}\left({\textsf {M}}^{(i)}\right)$
* $\qquad$${\textsf {T}}\leftarrow {\textsf {CV}}^{(i)}$
* $\qquad$for $j=0$ to $(N_{s}-1)$ do
* $\qquad$$\qquad$${\textsf {T}}\leftarrow {\textrm {Step}}_{j}\left({\textsf {T}},{\textsf {M}}_{j}^{(i)}\right)$
* $\qquad$end for
* $\qquad$${\textsf {CV}}^{(i+1)}\leftarrow {\textrm {MsgAdd}}\left({\textsf {T}},{\textsf {M}}_{N_{s}}^{(i)}\right)$
* $\qquad$return ${\textsf {CV}}^{(i+1)}$
Here the $j$-th step function ${\textrm {Step}}_{j}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}$ is as follows.
${\textrm {Step}}_{j}:={\textrm {WordPerm}}\circ {\textrm {Mix}}_{j}\circ {\textrm {MsgAdd}}$ $(0\leq j\leq (N_{s}-1))$
The following figure shows the $j$-th step function ${\textrm {Step}}_{j}$ of a compression function.

#### Message Expansion Function MsgExp

Let ${\textsf {M}}^{(i)}=(M^{(i)}[0],\ldots ,M^{(i)}[31])$ be the $i$-th 32-word array message block. The message expansion function ${\textrm {MsgExp}}$ generates $(N_{s}+1)$ 16-word array sub-messages $\{{\textsf {M}}_{j}^{(i)}\}_{j=0}^{N_{s}}$ from a message block ${\textsf {M}}^{(i)}$. The first two sub-messages ${\textsf {M}}_{0}^{(i)}=(M_{0}^{(i)}[0],\ldots ,M_{0}^{(i)}[15])$ and ${\textsf {M}}_{1}^{(i)}=(M_{1}^{(i)}[0],\ldots ,M_{1}^{(i)}[15])$ are defined as follows.
* ${\textsf {M}}_{0}^{(i)}\leftarrow (M^{(i)}[0],M^{(i)}[1],\ldots ,M^{(i)}[15])$
* ${\textsf {M}}_{1}^{(i)}\leftarrow (M^{(i)}[16],M^{(i)}[17],\ldots ,M^{(i)}[31])$
The next sub-messages $\{{\textsf {M}}_{j}^{(i)}=(M_{j}^{(i)}[0],\ldots ,M_{j}^{(i)}[15])\}_{j=2}^{N_{s}}$ are generated as follows.
* ${\textsf {M}}_{j}^{(i)}[l]\leftarrow {\textsf {M}}_{j-1}^{(i)}[l]\boxplus {\textsf {M}}_{j-2}^{(i)}[\tau (l)]$ $(0\leq l\leq 15,\ 2\leq j\leq N_{s})$
Here $\tau$ is the permutation over $\mathbb {Z} _{16}$ defined as follows.
The permutation $\tau :\mathbb {Z} _{16}\rightarrow \mathbb {Z} _{16}$ :
| $l$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| $\tau (l)$ | 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 ${\textsf {X}}=(X[0],\ldots ,X[15])$ and ${\textsf {Y}}=(Y[0],\ldots ,Y[15])$, the message addition function ${\textrm {MsgAdd}}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}$ is defined as follows.
${\textrm {MsgAdd}}({\textsf {X}},{\textsf {Y}}):=(X[0]\oplus Y[0],\ldots ,X[15]\oplus Y[15])$

#### Mix Function Mix

The $j$-th mix function ${\textrm {Mix}}_{j}:{\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}$ updates the 16-word array ${\textsf {T}}=(T[0],\ldots ,T[15])$ by mixing every two-word pair; $T[l]$ and $T[l+8]$ for $(0\leq l<8)$. For $0\leq j<N_{s}$, the mix function ${\textrm {Mix}}_{j}$ proceeds as follows.
$(T[l],T[l+8])\leftarrow {\textrm {Mix}}_{j,l}(T[l],T[l+8])$ $(0\leq l<8)$
Here ${\textrm {Mix}}_{j,l}$ is a two-word mix function. Let $X$ and $Y$ be words. The two-word mix function ${\textrm {Mix}}_{j,l}:{\mathcal {W}}^{2}\rightarrow {\mathcal {W}}^{2}$ is defined as follows.
* function Two-word mix function ${\textrm {Mix}}_{j,l}$
* input: Words $X$ and $Y$
* output: Words $X$ and $Y$
* procedure
* $\qquad$$X\leftarrow X\boxplus Y$;$\qquad X\leftarrow X^{\lll \alpha _{j}}$;
* $\qquad$$X\leftarrow X\oplus SC_{j}[l]$;
* $\qquad$$Y\leftarrow X\boxplus Y$;$\qquad Y\leftarrow Y^{\lll \beta _{j}}$;
* $\qquad$$X\leftarrow X\boxplus Y$;$\qquad Y\leftarrow Y^{\lll \gamma _{l}}$;
* $\qquad$return $X$, $Y$;
The two-word mix function ${\textrm {Mix}}_{j,l}$ is shown in the following figure.
The bit rotation amounts $\alpha _{j}$, $\beta _{j}$, $\gamma _{l}$ used in ${\textrm {Mix}}_{j,l}$ are shown in the following table.
Bit rotation amounts $\alpha _{j}$, $\beta _{j}$, and $\gamma _{l}$ :
| $w$ | $j$ | $\alpha _{j}$ | $\beta _{j}$ | $\gamma _{0}$ | $\gamma _{1}$ | $\gamma _{2}$ | $\gamma _{3}$ | $\gamma _{4}$ | $\gamma _{5}$ | $\gamma _{6}$ | $\gamma _{7}$ |
| 32 | even | 29 | 1 | 0 | 8 | 16 | 24 | 24 | 16 | 8 | 0 |
| 32 | odd | 5 | 17 | 0 | 8 | 16 | 24 | 24 | 16 | 8 | 0 |
| 64 | even | 23 | 59 | 0 | 16 | 32 | 48 | 8 | 24 | 40 | 56 |
| 64 | odd | 7 | 3 | 0 | 16 | 32 | 48 | 8 | 24 | 40 | 56 |
The $j$-th 8-word array constant ${\textsf {SC}}_{j}=(SC_{j}[0],\ldots ,SC_{j}[7])$ used in ${\textrm {Mix}}_{j,l}$ for $0\leq l<8$ is defined as follows. The initial 8-word array constant ${\textsf {SC}}_{0}=(SC_{0}[0],\ldots ,SC_{0}[7])$ is defined in the following table. For $1\leq j<N_{s}$, the $j$-th constant ${\textsf {SC}}_{j}=(SC_{j}[0],\ldots ,SC_{j}[7])$ is generated by $SC_{j}[l]\leftarrow SC_{j-1}[l]\boxplus SC_{j-1}[l]^{\lll 8}$ for $0\leq l<8$.
Initial 8-word array constant ${\textsf {SC}}_{0}$ :
| | $w=32$ | $w=64$ |
| $SC_{0}[0]$ | 917caf90 | 97884283c938982a |
| $SC_{0}[1]$ | 6c1b10a2 | ba1fca93533e2355 |
| $SC_{0}[2]$ | 6f352943 | c519a2e87aeb1c03 |
| $SC_{0}[3]$ | cf778243 | 9a0fc95462af17b1 |
| $SC_{0}[4]$ | 2ceb7472 | fc3dda8ab019a82b |
| $SC_{0}[5]$ | 29e96ff2 | 02825d079a895407 |
| $SC_{0}[6]$ | 8a9ba428 | 79f2d0a7ee06a6f7 |
| $SC_{0}[7]$ | 2eeb2642 | d76d15eed9fdf5fe |

#### Word-Permutation Function WordPerm

Let ${\textsf {X}}=(X[0],\ldots ,X[15])$ be a 16-word array. The word-permutation function ${\textrm {WordPerm}}:{\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}$ is defined as follows.
${\textrm {WordPerm}}({\textsf {X}})=(X[\sigma (0)],\ldots ,X[\sigma (15)])$
Here $\sigma$ is the permutation over $\mathbb {Z} _{16}$ defined by the following table.
The permutation $\sigma :\mathbb {Z} _{16}\rightarrow \mathbb {Z} _{16}$ :
| $l$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| $\sigma (l)$ | 6 | 4 | 5 | 7 | 12 | 15 | 14 | 13 | 2 | 0 | 1 | 3 | 8 | 11 | 10 | 9 |

### Finalization

The finalization function ${\textrm {FIN}}_{n}:{\mathcal {W}}^{16}\rightarrow \{0,1\}^{n}$ returns $n$-bit hash value $h$ from the final chaining variable ${\textsf {CV}}^{(t)}=(CV^{(t)}[0],\ldots ,CV^{(t)}[15])$. When ${\textsf {H}}=(H[0],\ldots ,H[7])$ is an 8-word variable and ${\textsf {h}}_{\textsf {b}}=(h_{b}[0],\ldots ,h_{b}[w-1])$ is a $w$-byte variable, the finalization function ${\textrm {FIN}}_{n}$ performs the following procedure.
* $H[l]\leftarrow CV^{(t)}[l]\oplus CV^{(t)}[l+8]$ $(0\leq l\leq 7)$
* $h_{b}[s]\leftarrow H[\lfloor 8s/w\rfloor ]_{[7:0]}^{\ggg (8s\mod w)}$ $(0\leq s\leq (w-1))$
* $h\leftarrow (h_{b}[0]\|\ldots \|h_{b}[w-1])_{[0:n-1]}$
Here, $X_{[i:j]}$ denotes $x_{i}\|x_{i-1}\|\ldots \|x_{j}$, the sub-bit string of a word $X$ for $i\geq j$. And $x_{[i:j]}$ denotes $x_{i}\|x_{i+1}\|\ldots \|x_{j}$, the sub-bit string of a $l$-bit string $x=x_{0}\|x_{1}\|\ldots \|x_{l-1}$ for $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}$ and preimage-resistant and second-preimage-resistant for $q<2^{n}$ in the ideal cipher model, where $q$ is a number of queries for LSH structure. LSH-256 is secure against all the existing hash function attacks when the number of steps is 13 or more, while LSH-512 is secure if the number of steps is 14 or more. Note that the steps which work as security margin are 50% of the compression function.

## Performance

LSH outperforms SHA-2/3 on various software platforms. The following table shows the speed performance of 1MB message hashing of LSH on several platforms.
1MB message hashing speed of LSH (cycles/byte) :
| Platform | P1 | P2 | P3 | P4 | P5 | P6 | P7 | P8 |
| LSH-256-$n$ | 3.60 | 3.86 | 5.26 | 3.89 | 11.17 | 15.03 | 15.28 | 14.84 |
| LSH-512-$n$ | 2.39 | 5.04 | 7.76 | 5.52 | 8.94 | 18.76 | 19.00 | 18.10 |
* ↑ Intel Core i7-4770K @ 3.5GHz (Haswell), Ubuntu 12.04 64-bit, GCC 4.8.1 with “-m64 -mavx2 -O3”
* ↑ Intel Core i7-2600K @ 3.40GHz (Sandy Bridge), Ubuntu 12.04 64-bit, GCC 4.8.1 with “-m64 -msse4 -O3”
* ↑ Intel Core 2 Quad Q9550 @ 2.83GHz (Yorkfield), Windows 7 32-bit, Visual studio 2012
* ↑ AMD FX-8350 @ 4GHz (Piledriver), Ubuntu 12.04 64-bit, GCC 4.8.1 with “-m64 -mxop -O3”
* ↑ Samsung Exynos 5250 ARM Cortex-A15 @ 1.7GHz dual core (Huins ACHRO 5250), Android 4.1.1
* ↑ Qualcomm Snapdragon 800 Krait 400 @ 2.26GHz quad core (LG G2), Android 4.4.2
* ↑ Qualcomm Snapdragon 800 Krait 400 @ 2.3GHz quad core (Samsung Galaxy S4), Android 4.2.2
* ↑ 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) :
| Algorithm | Message size in bytes | Message size in bytes | Message size in bytes | Message size in bytes | Message size in bytes | Message size in bytes |
| Algorithm | 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) :
| Algorithm | Message size in bytes | Message size in bytes | Message size in bytes | Message size in bytes | Message size in bytes | Message size in bytes |
| Algorithm | 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.

## KCMVP

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

## Standardization

LSH is included in the following standard.
* KS X 3262, Hash function LSH (in Korean)