LSH 는 대한민국이 PC, 스마트 디바이스 등 범용 CPU에서 무결성을 제공하기 위해 2014년에 개발한 해시 함수이다.[1] LSH는 대한민국 암호모듈 검증제도 검증대상 암호 알고리즘이며, 대한민국 국가 표준(KS X 3262)이다.
해시 함수 LSH의 전체 구조는 아래와 같다.
해시 함수 LSH 전체 구조
LSH는 입력 메시지에 대해 다음과 같은 세 단계를 거쳐 해시값을 출력한다.
초기화(Initialization): 입력 메시지를 메시지 블록 비트 길이의 배수가 되도록 패딩을 한 후, 이를 메시지 블록 단위로 분할한다. 그리고 연결 변수를
IV
{\displaystyle {\textsf {IV}}}
로 초기화한다.
압축(Compression): 32워드 배열 메시지 블록을 압축 함수의 입력으로 하여 얻은 출력값으로 연결 변수를 갱신하며, 이를 마지막 메시지 블록을 처리할 때까지 반복하여 메시지를 압축한다.
완료(Finalization): 압축 과정을 통해 연결 변수에 최종 저장된 값으로부터 n비트 길이의 해시 함수 출력값을 생성한다.
function 해시 함수 LSH
input: 메시지
m
{\displaystyle m}
output: 해시값
h
∈
{
0
,
1
}
n
{\displaystyle h\in \{0,1\}^{n}}
procedure
{\displaystyle \qquad }
m
p
←
pad
(
m
)
{\displaystyle m_{p}\leftarrow {\textrm {pad}}(m)}
;
{\displaystyle \qquad }
m
p
{\displaystyle m_{p}}
로부터 메시지 블록
(
M
(
0
)
,
M
(
1
)
,
⋯
,
M
(
t
−
1
)
)
{\displaystyle (M^{(0)},M^{(1)},\cdots ,M^{(t-1)})}
생성;
{\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)},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}
;
해시 함수 LSH의 규격은 다음 표와 같다.
해시 함수 LSH 규격
구분
출력 비트 길이 (
n
{\displaystyle n}
)
압축 함수의 단계 수 (
N
s
{\displaystyle N_{s}}
)
연결 변수 비트 길이
메시지 블록 비트 길이
워드 비트 길이 (
w
{\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
해시 함수의 입력 메시지를
m
{\displaystyle m}
이라 하자. 먼저
m
{\displaystyle m}
은 덧붙이기(padding) 과정을 거친다. 덧붙이기 과정은
m
{\displaystyle m}
의 끝에 비트 ‘1’을 덧붙인 후, 전체 길이가
32
w
t
{\displaystyle 32wt}
비트가 될 때까지 비트 ‘0’을 덧붙인다. 여기에서
t
=
⌈
(
|
m
|
+
1
)
/
32
w
⌉
{\displaystyle t=\lceil (|m|+1)/32w\rceil }
이다.
덧붙이기를 마친 메시지를
m
p
=
m
0
‖
m
1
‖
…
‖
m
(
32
w
t
−
1
)
{\displaystyle m_{p}=m_{0}\|m_{1}\|\ldots \|m_{(32wt-1)}}
이라고 하자. 이때
m
p
{\displaystyle m_{p}}
는
4
w
t
{\displaystyle 4wt}
바이트 배열
m
a
=
(
m
[
0
]
,
…
,
m
[
4
w
t
−
1
]
)
{\displaystyle m_{a}=(m[0],\ldots ,m[4wt-1])}
로 볼 수 있다. 여기에서
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)}}
(
0
≤
k
≤
(
4
w
t
−
1
)
)
{\displaystyle (0\leq k\leq (4wt-1))}
이다. 바이트 배열
m
a
{\displaystyle m_{a}}
는 다음과 같이
32
t
{\displaystyle 32t}
워드 배열
M
=
(
M
[
0
]
,
…
,
M
[
32
t
−
1
]
)
{\displaystyle {\textsf {M}}=(M[0],\ldots ,M[32t-1])}
으로 변환할 수 있다.
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))}
이어서 워드 배열
M
{\displaystyle {\textsf {M}}}
으로부터 다음과 같은 규칙에 따라
t
{\displaystyle t}
개 메시지 블록
M
(
0
)
{\displaystyle {\textsf {M}}^{(0)}}
,
M
(
1
)
{\displaystyle {\textsf {M}}^{(1)}}
, \ldots ,
M
(
t
−
1
)
{\displaystyle {\textsf {M}}^{(t-1)}}
을 구성할 수 있다.
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))}
연결 변수
CV
(
0
)
{\displaystyle {\textsf {CV}}^{(0)}}
(
∈
W
16
)
{\displaystyle (\in {\mathcal {W}}^{16})}
는 초기값을 이용하여 다음과 같이 배열 색인별로 값을 할당하는 방식으로 초기화한다.
이때,
W
t
{\displaystyle {\mathcal {W}}^{t}}
는
t
≥
1
{\displaystyle t\geq 1}
일 때
t
{\displaystyle t}
개 워드 배열의 전체 집합을 나타낸다.
CV
(
0
)
[
l
]
←
IV
[
l
]
{\displaystyle {\textsf {CV}}^{(0)}[l]\leftarrow {\textsf {IV}}[l]}
(
0
≤
l
≤
15
)
{\displaystyle (0\leq l\leq 15)}
초기값은 다음과 같다.
모든 값은 16진수로 표현되어 있다.
LSH-256-224 초기값
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]}
068608D3
62D8F7A7
D76652AB
4C600A43
BDC40AA8
1ECA0B68
DA1A89BE
3147D354
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]}
707EB4F9
F65B3862
6B0B2ABE
56B8EC0A
CF237286
EE0D1727
33636595
8BB8D05F
LSH-256-256 초기값
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]}
46A10F1F
FDDCE486
B41443A8
198E6B9D
3304388D
B0F5A3C7
B36061C4
7ADBD553
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]}
105D5378
2F74DE54
5C2F2D95
F2553FBE
8051357A
138668C8
47AA4484
E01AFB41
LSH-512-224 초기값
IV
[
0
]
{\displaystyle {\textsf {IV}}[0]}
IV
[
1
]
{\displaystyle {\textsf {IV}}[1]}
IV
[
2
]
{\displaystyle {\textsf {IV}}[2]}
IV
[
3
]
{\displaystyle {\textsf {IV}}[3]}
0C401E9FE8813A55
4A5F446268FD3D35
FF13E452334F612A
F8227661037E354A
IV
[
4
]
{\displaystyle {\textsf {IV}}[4]}
IV
[
5
]
{\displaystyle {\textsf {IV}}[5]}
IV
[
6
]
{\displaystyle {\textsf {IV}}[6]}
IV
[
7
]
{\displaystyle {\textsf {IV}}[7]}
A5F223723C9CA29D
95D965A11AED3979
01E23835B9AB02CC
52D49CBAD5B30616
IV
[
8
]
{\displaystyle {\textsf {IV}}[8]}
IV
[
9
]
{\displaystyle {\textsf {IV}}[9]}
IV
[
10
]
{\displaystyle {\textsf {IV}}[10]}
IV
[
11
]
{\displaystyle {\textsf {IV}}[11]}
9E5C2027773F4ED3
66A5C8801925B701
22BBC85B4C6779D9
C13171A42C559C23
IV
[
12
]
{\displaystyle {\textsf {IV}}[12]}
IV
[
13
]
{\displaystyle {\textsf {IV}}[13]}
IV
[
14
]
{\displaystyle {\textsf {IV}}[14]}
IV
[
15
]
{\displaystyle {\textsf {IV}}[15]}
31E2B67D25BE3813
D522C4DEED8E4D83
A79F5509B43FBAFE
E00D2CD88B4B6C6A
LSH-512-256 초기값
IV
[
0
]
{\displaystyle {\textsf {IV}}[0]}
IV
[
1
]
{\displaystyle {\textsf {IV}}[1]}
IV
[
2
]
{\displaystyle {\textsf {IV}}[2]}
IV
[
3
]
{\displaystyle {\textsf {IV}}[3]}
6DC57C33DF989423
D8EA7F6E8342C199
76DF8356F8603AC4
40F1B44DE838223A
IV
[
4
]
{\displaystyle {\textsf {IV}}[4]}
IV
[
5
]
{\displaystyle {\textsf {IV}}[5]}
IV
[
6
]
{\displaystyle {\textsf {IV}}[6]}
IV
[
7
]
{\displaystyle {\textsf {IV}}[7]}
39FFE7CFC31484CD
39C4326CC5281548
8A2FF85A346045D8
FF202AA46DBDD61E
IV
[
8
]
{\displaystyle {\textsf {IV}}[8]}
IV
[
9
]
{\displaystyle {\textsf {IV}}[9]}
IV
[
10
]
{\displaystyle {\textsf {IV}}[10]}
IV
[
11
]
{\displaystyle {\textsf {IV}}[11]}
CF785B3CD5FCDB8B
1F0323B64A8150BF
FF75D972F29EA355
2E567F30BF1CA9E1
IV
[
12
]
{\displaystyle {\textsf {IV}}[12]}
IV
[
13
]
{\displaystyle {\textsf {IV}}[13]}
IV
[
14
]
{\displaystyle {\textsf {IV}}[14]}
IV
[
15
]
{\displaystyle {\textsf {IV}}[15]}
B596875BF8FF6DBA
FCCA39B089EF4615
ECFF4017D020B4B6
7E77384C772ED802
LSH-512-384 초기값
IV
[
0
]
{\displaystyle {\textsf {IV}}[0]}
IV
[
1
]
{\displaystyle {\textsf {IV}}[1]}
IV
[
2
]
{\displaystyle {\textsf {IV}}[2]}
IV
[
3
]
{\displaystyle {\textsf {IV}}[3]}
53156A66292808F6
B2C4F362B204C2BC
B84B7213BFA05C4E
976CEB7C1B299F73
IV
[
4
]
{\displaystyle {\textsf {IV}}[4]}
IV
[
5
]
{\displaystyle {\textsf {IV}}[5]}
IV
[
6
]
{\displaystyle {\textsf {IV}}[6]}
IV
[
7
]
{\displaystyle {\textsf {IV}}[7]}
DF0CC63C0570AE97
DA4441BAA486CE3F
6559F5D9B5F2ACC2
22DACF19B4B52A16
IV
[
8
]
{\displaystyle {\textsf {IV}}[8]}
IV
[
9
]
{\displaystyle {\textsf {IV}}[9]}
IV
[
10
]
{\displaystyle {\textsf {IV}}[10]}
IV
[
11
]
{\displaystyle {\textsf {IV}}[11]}
BBCDACEFDE80953A
C9891A2879725B3E
7C9FE6330237E440
A30BA550553F7431
IV
[
12
]
{\displaystyle {\textsf {IV}}[12]}
IV
[
13
]
{\displaystyle {\textsf {IV}}[13]}
IV
[
14
]
{\displaystyle {\textsf {IV}}[14]}
IV
[
15
]
{\displaystyle {\textsf {IV}}[15]}
BB08043FB34E3E30
A0DEC48D54618EAD
150317267464BC57
32D1501FDE63DC93
LSH-512-512 초기값
IV
[
0
]
{\displaystyle {\textsf {IV}}[0]}
IV
[
1
]
{\displaystyle {\textsf {IV}}[1]}
IV
[
2
]
{\displaystyle {\textsf {IV}}[2]}
IV
[
3
]
{\displaystyle {\textsf {IV}}[3]}
ADD50F3C7F07094E
E3F3CEE8F9418A4F
B527ECDE5B3D0AE9
2EF6DEC68076F501
IV
[
4
]
{\displaystyle {\textsf {IV}}[4]}
IV
[
5
]
{\displaystyle {\textsf {IV}}[5]}
IV
[
6
]
{\displaystyle {\textsf {IV}}[6]}
IV
[
7
]
{\displaystyle {\textsf {IV}}[7]}
8CB994CAE5ACA216
FBB9EAE4BBA48CC7
650A526174725FEA
1F9A61A73F8D8085
IV
[
8
]
{\displaystyle {\textsf {IV}}[8]}
IV
[
9
]
{\displaystyle {\textsf {IV}}[9]}
IV
[
10
]
{\displaystyle {\textsf {IV}}[10]}
IV
[
11
]
{\displaystyle {\textsf {IV}}[11]}
B6607378173B539B
1BC99853B0C0B9ED
DF727FC19B182D47
DBEF360CF893A457
IV
[
12
]
{\displaystyle {\textsf {IV}}[12]}
IV
[
13
]
{\displaystyle {\textsf {IV}}[13]}
IV
[
14
]
{\displaystyle {\textsf {IV}}[14]}
IV
[
15
]
{\displaystyle {\textsf {IV}}[15]}
4981F5E570147E80
D00C4490CA7D3E30
5D73940C0E4AE1EC
894085E2EDB2D819
초기화 단계에서 생성된
t
{\displaystyle t}
개의 메시지 블록은 압축 단계에서 순차적으로 압축 함수(compression function)
CF
:
W
16
×
W
32
→
W
16
{\displaystyle {\textrm {CF}}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{32}\rightarrow {\mathcal {W}}^{16}}
의 입력값으로 사용된다.
압축 함수
CF
{\displaystyle {\textrm {CF}}}
는 연결 변수
CV
(
i
)
(
∈
W
16
)
{\displaystyle {\textsf {CV}}^{(i)}(\in {\mathcal {W}}^{16})}
와 메시지 블록
M
(
i
)
(
∈
W
32
)
{\displaystyle {\textsf {M}}^{(i)}(\in {\mathcal {W}}^{32})}
를 입력으로 받아 연결 변수
CV
(
i
+
1
)
(
∈
W
16
)
{\displaystyle {\textsf {CV}}^{(i+1)}(\in {\mathcal {W}}^{16})}
을 반환한다.
압축 함수는 다음 네 가지 함수로 구성된다.
메시지 확장 함수
MsgExp
:
W
32
→
W
16
(
N
s
+
1
)
{\displaystyle {\textrm {MsgExp}}:{\mathcal {W}}^{32}\rightarrow {\mathcal {W}}^{16(Ns+1)}}
메시지 덧셈 함수
MsgAdd
:
W
16
×
W
16
→
W
16
{\displaystyle {\textrm {MsgAdd}}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}}
섞음 함수
Mix
j
:
W
16
→
W
16
{\displaystyle {\textrm {Mix}}_{j}:{\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}}
워드 단위 치환
WordPerm
:
W
16
→
W
16
{\displaystyle {\textrm {WordPerm}}:{\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}}
압축 함수의 전체 구조를 도시하면 다음 그림과 같다.
해시 함수 LSH 압축 함수
압축 함수 입력값 중 메시지 블록
M
(
i
)
{\displaystyle {\textsf {M}}^{(i)}}
는 메시지 확장 함수 MsgExp를 거쳐
(
N
s
+
1
)
{\displaystyle (N_{s}+1)}
개의 16워드 크기 데이터
M
j
(
i
)
{\displaystyle {\textsf {M}}_{j}^{(i)}}
(
0
≤
j
≤
N
s
)
{\displaystyle (0\leq j\leq N_{s})}
로 확장된다.
이어서 16워드 크기의 임시 변수
T
=
(
T
[
0
]
,
…
,
T
[
15
]
)
{\displaystyle {\textsf {T}}=(T[0],\ldots ,T[15])}
에
CV
(
i
)
{\displaystyle {\textsf {CV}}^{(i)}}
를 할당한 후, 순차적으로 단계 함수(step function)
Step
j
{\displaystyle {\textrm {Step}}_{j}}
를 통해 데이터
M
j
(
i
)
{\displaystyle {\textsf {M}}_{j}^{(i)}}
를 처리하면서
T
{\displaystyle {\textsf {T}}}
를 갱신한다.
단계 함수를 거쳐
T
{\displaystyle {\textsf {T}}}
에 저장된 값은 MsgAdd 함수를 통해 처리된 후
(
i
+
1
)
{\displaystyle (i+1)}
번 째 연결 변수
CV
(
i
+
1
)
{\displaystyle {\textsf {CV}}^{(i+1)}}
에 입력된다.
이러한 압축 함수 처리 절차는 다음과 같다.
압축 함수에서 순차적으로
M
j
(
i
)
{\displaystyle {\textsf {M}}_{j}^{(i)}}
를 처리하는 단계 함수
Step
j
:
W
16
×
W
16
→
W
16
{\displaystyle {\textrm {Step}}_{j}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}}
는 다음과 같다.
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))}
단계 함수의 전체 구조는 다음 그림과 같다.
해시 함수 LSH의
j
{\displaystyle j}
번째 단계 함수
Step
j
{\displaystyle {\textrm {Step}}_{j}}
압축 함수에 입력된 메시지 블록
M
(
i
)
=
(
M
(
i
)
[
0
]
,
…
,
M
(
i
)
[
31
]
)
{\displaystyle {\textsf {M}}^{(i)}=(M^{(i)}[0],\ldots ,M^{(i)}[31])}
에 대해, 메시지 확장 함수 MsgExp는
(
N
s
+
1
)
{\displaystyle (N_{s}+1)}
개의 16워드 길이의 데이터
M
j
(
i
)
{\displaystyle {\textsf {M}}_{j}^{(i)}}
(
0
≤
j
≤
N
s
)
{\displaystyle (0\leq j\leq N_{s})}
를 생성한다.
생성 방법은 다음과 같다.
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])}
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})}
함수
τ たう
{\displaystyle \tau }
는 다음과 같이 정의된
Z
16
{\displaystyle \mathbb {Z} _{16}}
상의 치환이다.
Z
16
{\displaystyle \mathbb {Z} _{16}}
상의 치환
τ たう
{\displaystyle \tau }
l
{\displaystyle l}
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
τ たう
(
l
)
{\displaystyle \tau (l)}
3
2
0
1
7
4
5
6
11
10
8
9
15
12
13
14
두 개의 16워드 길이의 변수
X
=
(
X
[
0
]
,
…
,
X
[
15
]
)
{\displaystyle {\textsf {X}}=(X[0],\ldots ,X[15])}
와
Y
=
(
Y
[
0
]
,
…
,
Y
[
15
]
)
{\displaystyle {\textsf {Y}}=(Y[0],\ldots ,Y[15])}
를 입력으로 받아 16워드 길이의 결과값을 출력하는 메시지 덧셈 함수
MsgAdd
:
W
16
×
W
16
→
W
16
{\displaystyle {\textrm {MsgAdd}}:{\mathcal {W}}^{16}\times {\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}}
는 다음과 같이 정의한다.
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
j
:
W
16
→
W
16
{\displaystyle {\textrm {Mix}}_{j}:{\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}}
는 16워드 길이의 변수
T
=
(
T
[
0
]
,
…
,
T
[
15
]
)
{\displaystyle {\textsf {T}}=(T[0],\ldots ,T[15])}
를 입력으로 받아 두 개의 워드
T
[
l
]
{\displaystyle T[l]}
,
T
[
l
+
8
]
{\displaystyle T[l+8]}
(
0
≤
l
≤
7
)
{\displaystyle (0\leq l\leq 7)}
을 쌍으로 구성한 후 아래와 같이 각각을 섞어
T
{\displaystyle {\textsf {T}}}
를 갱신한다.
(
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
≤
7
)
{\displaystyle (0\leq l\leq 7)}
여기에서
Mix
j
,
l
:
W
2
→
W
2
{\displaystyle {\textrm {Mix}}_{j,l}:{\mathcal {W}}^{2}\rightarrow {\mathcal {W}}^{2}}
은 두 개 워드
X
{\displaystyle X}
,
Y
{\displaystyle Y}
를 처리하는 부분 섞음 함수로 다음과 같다.
부분 섞음 함수
Mix
j
,
l
{\displaystyle {\textrm {Mix}}_{j,l}}
를 도식화하면 다음 그림과 같다.
해시 함수 LSH의 부분 섞음 함수
섞음 함수
Mix
j
,
l
{\displaystyle {\textrm {Mix}}_{j,l}}
에 사용되는 비트 순환량
α あるふぁ
j
{\displaystyle \alpha _{j}}
,
β べーた
j
{\displaystyle \beta _{j}}
,
γ がんま
l
{\displaystyle \gamma _{l}}
은 다음 표와 같다.
비트 순환량
α あるふぁ
j
{\displaystyle \alpha _{j}}
,
β べーた
j
{\displaystyle \beta _{j}}
는 짝수 단계와 홀수 단계에서 다른 값이 적용된다.
비트 순환량
α あるふぁ
j
{\displaystyle \alpha _{j}}
,
β べーた
j
{\displaystyle \beta _{j}}
,
γ がんま
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}}
32
짝수
29
1
0
8
16
24
24
16
8
0
홀수
5
17
64
짝수
23
59
0
16
32
48
8
24
40
56
홀수
7
3
그리고 8워드 길이의 단계 상수
SC
j
=
(
S
C
j
[
0
]
,
…
,
S
C
j
[
7
]
)
{\displaystyle {\textsf {SC}}_{j}=(SC_{j}[0],\ldots ,SC_{j}[7])}
는 먼저
SC
0
{\displaystyle {\textsf {SC}}_{0}}
를 아래 표와 같이 정의한 후, 나머지
(
N
s
−
1
)
{\displaystyle (N_{s}-1)}
개의 상수
SC
j
{\displaystyle {\textsf {SC}}_{j}}
를
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}}
(
0
≤
l
≤
7
,
1
≤
j
≤
(
N
s
−
1
)
)
{\displaystyle (0\leq l\leq 7,1\leq j\leq (N_{s}-1))}
와 같이 유도한다.
초기 단계 상수
w
=
32
{\displaystyle w=32}
w
=
64
{\displaystyle w=64}
S
C
0
[
0
]
{\displaystyle SC_{0}[0]}
917caf90
97884283c938982a
S
C
0
[
1
]
{\displaystyle SC_{0}[1]}
6c1b10a2
ba1fca93533e2355
S
C
0
[
2
]
{\displaystyle SC_{0}[2]}
6f352943
c519a2e87aeb1c03
S
C
0
[
3
]
{\displaystyle SC_{0}[3]}
cf778243
9a0fc95462af17b1
S
C
0
[
4
]
{\displaystyle SC_{0}[4]}
2ceb7472
fc3dda8ab019a82b
S
C
0
[
5
]
{\displaystyle SC_{0}[5]}
29e96ff2
02825d079a895407
S
C
0
[
6
]
{\displaystyle SC_{0}[6]}
8a9ba428
79f2d0a7ee06a6f7
S
C
0
[
7
]
{\displaystyle SC_{0}[7]}
2eeb2642
d76d15eed9fdf5fe
워드 단위 치환
WordPerm
:
W
16
→
W
16
{\displaystyle {\textrm {WordPerm}}:{\mathcal {W}}^{16}\rightarrow {\mathcal {W}}^{16}}
은 16워드 길이의 변수
X
=
(
X
[
0
]
,
…
,
X
[
15
]
)
{\displaystyle {\textsf {X}}=(X[0],\ldots ,X[15])}
를 입력으로 받아 16워드 길이의 결과값을 출력한다.
WordPerm
(
X
)
:=
(
X
[
σ しぐま
(
0
)
]
,
…
,
X
[
σ しぐま
(
15
)
]
)
{\displaystyle {\textrm {WordPerm}}({\textsf {X}}):=(X[\sigma (0)],\ldots ,X[\sigma (15)])}
이때, 사용되는 함수
σ しぐま
{\displaystyle \sigma }
는 다음 표와 같이 정의된
Z
16
{\displaystyle \mathbb {Z} _{16}}
상의 치환이다.
Z
16
{\displaystyle \mathbb {Z} _{16}}
상의 치환
σ しぐま
{\displaystyle \sigma }
l
{\displaystyle l}
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
σ しぐま
(
l
)
{\displaystyle \sigma (l)}
6
4
5
7
12
15
14
13
2
0
1
3
8
11
10
9
완료 함수
FIN
n
:
W
16
→
{
0
,
1
}
n
{\displaystyle {\textrm {FIN}}_{n}:{\mathcal {W}}^{16}\rightarrow \{0,1\}^{n}}
은 압축 과정의 결과로 생성된 마지막 연결 변수
CV
(
t
)
=
(
C
V
(
t
)
[
0
]
,
…
,
C
V
(
t
)
[
15
]
)
{\displaystyle {\textsf {CV}}^{(t)}=(CV^{(t)}[0],\ldots ,CV^{(t)}[15])}
에 적용되어
n
{\displaystyle n}
비트 길이의 해시값
h
{\displaystyle h}
를 생성한다.
H
=
(
H
[
0
]
,
…
,
H
[
7
]
)
{\displaystyle {\textsf {H}}=(H[0],\ldots ,H[7])}
를 8워드 길이의 변수,
h
b
=
(
h
b
[
0
]
,
…
,
h
b
[
w
−
1
]
)
{\displaystyle {\textsf {h}}_{\textsf {b}}=(h_{b}[0],\ldots ,h_{b}[w-1])}
는
w
{\displaystyle w}
바이트 길이의 변수라고 하면, 출력 함수
FIN
n
{\displaystyle {\textrm {FIN}}_{n}}
은 다음 절차를 수행한다.
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]}}
이때, 임의의 워드
X
{\displaystyle X}
에 대해
r
≥
s
{\displaystyle r\geq s}
일 때,
X
[
r
:
s
]
{\displaystyle X_{[r:s]}}
는
X
{\displaystyle X}
의 비트열 표현에서 부분 비트열
x
r
‖
x
r
−
1
‖
…
‖
x
s
{\displaystyle x_{r}\|x_{r-1}\|\ldots \|x_{s}}
를 나타낸다.
그리고 임의의 비트열
x
{\displaystyle x}
에 대해
r
≤
s
{\displaystyle r\leq s}
일 때,
x
[
r
:
s
]
{\displaystyle x_{[r:s]}}
는
x
{\displaystyle x}
의 부분 비트열
x
r
‖
x
r
+
1
‖
…
‖
x
s
{\displaystyle x_{r}\|x_{r+1}\|\ldots \|x_{s}}
를 나타낸다.
LSH는 현재까지 알려진 모든 해시 함수 공격에 대해 안전하다.
LSH는 ideal cipher model 하에서 쿼리의 수가
q
<
2
n
/
2
{\displaystyle q<2^{n/2}}
일 때 충돌 저항성(collision-resistance)을 가지며, 쿼리의 수가
q
<
2
n
{\displaystyle q<2^{n}}
일 때 역상 저항성(preimage-resistance) 및 제2-역상 저항성(second-preimage-resistance)을 가지는 것이 증명되었다[1] .
또한, LSH-256의 경우 13스텝, LSH-512의 경우 14스텝이 알려진 모든 공격에 대해 안전함이 알려져 있어 50% 이상의 안전성 마진을 제공한다[1] .
LSH는 다양한 소프트웨어 플랫폼에서 SHA-2/3 대비 빠른 속도를 보유하고 있다.
아래 표는 다양한 플랫폼 상에서 LSH의 1MB 메시지에 대한 해시값 계산 속도를 보여준다.
LSH의 1MB 메시지에 대한 해시값 계산 속도 (cycles/byte)[1]
Platform
P1[a]
P2[b]
P3[c]
P4[d]
P5[e]
P6[f]
P7[g]
P8[h]
LSH-256-
n
{\displaystyle n}
3.60
3.86
5.26
3.89
11.17
15.03
15.28
14.84
LSH-512-
n
{\displaystyle 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
아래 표는 Haswell 기반 플랫폼에서 LSH와 몇 종류의 해시 함수 성능을 비교한 것이다.
LSH는 Intel Core i7-4770k @ 3.5 GHz quad core 플랫폼에서, 다른 해시 함수는 Intel Core i5-4570S @ 2.9 GHz quad core 플랫폼에서 성능을 측정한 결과이다.
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
아래 표는 Samsung Exynos 5250 ARM Cortex-A15 @ 1.7 GHz dual core 플랫폼에서 LSH와 몇 종류의 해시 함수 성능을 비교한 것이다.
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
해시 함수 LSH의 테스트 벡터는 다음과 같다.
모든 값은 16진수로 표현되어 있다.
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
C, Java, Python으로 구현된 LSH의 배포용 소스코드는 KISA 암호이용활성화 웹페이지에서 다운받을 수 있다.[2]
LSH는 2019년 대한민국 암호모듈 검증제도 검증대상 암호알고리즘 목록에 포함되었다.[3]
LSH는 아래 표준으로 제정되어 있다.
↑ 가 나 다 라 마 바 Kim, Dong-Chan; Hong, Deukjo; Lee, Jung-Keun; Kim, Woo-Hwan; Kwon, Daesung (2014). 〈LSH: A New Fast Secure Hash Function Family〉. 《International Conference on Information Security and Cryptology - ICISC 2014》. Lecture Notes in Computer Science 8949 . Springer/Heidelberg. 286–313쪽.
↑ “LSH 소스코드” .
↑ “암호모듈검증” .
↑ “e-나라 표준인증” .