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

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). ===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 \le k \le (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 \le s \le (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 \le i \le (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 \le l \le 15) The initialization vector \textsf{IV} is as follows. In the following tables, all values are expressed in hexadecimal form. ===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 \ge 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. 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 \le j \le (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 \le l \le 15, \ 2 \le j \le N_s) Here \tau is the permutation over \mathbb{Z}_{16} defined as follows. ====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 \le l . For 0 \le j , 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 \le l 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. 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. 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 \le l 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 \le j , 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 \le l . ====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. ===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 \le l \le 7) h_b[s] \leftarrow H[\lfloor 8s/w\rfloor ]^{\ggg (8s \mod w)}_{[7:0]} (0 \le s \le (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 \ge 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 \le j . 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

Text derived from https://en.wikipedia.org/w/index.php?oldid=1235734140 under CC BY-SA 4.0; modifications have been made.