1. 메시지의 무결성
- 원본 메시지가 불법적으로 수정되지 않았음을 보장해야함
- 결국 원본과 동일함을 보장해야함
- 전통적인 무결성 보장 방법 : 지문을 추가하는 것
- 메시지 다이제스트
- 메시지에서 지문의 역할을 하는 것
- 메시지에 암호 해싱을 적용하여 생성되는 것
- \(Hash(Message) = Message \,Digest\)
- 메시지 다이제스트
1-1. 무결성 점검 과정
- 메시지의 무결성을 점검한다 → 메시지가 수정되었는지 확인한다
- 기존에 저장하던 메시지의 다이제스트
- 수신한 메시지로 생성해낸 메시지 다이제스트
- 비교한 결과 동일함 : 무결성 보존
- 비교한 결과 다름 : 무결성이 깨짐
2. 암호 해시 함수의 정의
- 해시 함수
- 메시지를 고정된 길이의 데이터로 변환
- 문서의 지문과 같은 역할을 수행하는 해시 값
- 조금의 수정이라도 해시 값은 크게 바뀜 → 조작 여부 확인 가능
- 단방향 속성
- 메시지로부터 해시 값은 생성 가능
- 역으로 해시 값으로부터 메시지를 생성 불가능
2-1 암호 해시 함수의 조건
2-1-1. Preimage resistance 단방향성
해시 값을 통해 역으로 메시지를 알아내는 매우 어렵거나 불가능해야 함
2-1-2. Second Preimage Resistance 약한 충돌 저항성
메시지와 해시 값을 알 때, 같지 않은 메시지이면서 해시 값이 같은 메시지를 찾기 어려워야 함
→ 마치 나의 지문과 같은 사람을 찾는 과정이 어려워야 함을 의미
$$ \begin{align*} &msg1,\ Hash(msg1)\ 주어질 때 \\&msg1 != msg2\ \ \ and \ \ \ Hash(msg1)=Hash(msg2)\ 만족하는\\&msg2는\ 찾기어려워야함 \end{align*} $$
2-1-3. Collision resistance 강한 충돌 저항성
같은 해시 값을 갖는 서로 다른 메시지를 찾기 어려워야 함
→ 마치 지문이 같은 두 사람을 찾는 과정이 어려워야 함을 의미
$$ \begin{align*} &Hash(msg1)==Hash(msg2)\ 일\,때 \\&msg1\ 과\ msg2\ 를\ 찾기어려워야함 \end{align*} $$
3. 상용 암호 해시 알고리즘
iterative hashing(반복 해싱)의 개념을 배경에 깔고 시작
3-1. 4가지의 단계
1단계
- 원본 메시지를 n-bit 크기의 블록으로 분할
- 마지막 블록의 경우 남은 메시지가 블록의 크기를 전부 채우지 못할 수 있음
- 메시지의 길이를 알려주는 값 추가
- padding으로 나머지 길이를 채워줌
2단계
- 초기 Digest 값(\(H_0\)) 은 m-bit 크기의 고정된 값 또는 비밀 키를 사용
3단계
- \(Compression\ function\ f(H_{t-1},\ M_t)=H_t\)
- 위의 과정을 반복하여 수행
4단계
- 최종적으로 구해지는 Digest 값 \(H_{t}\)이 최종 해시 함수의 결과 값이 됨
전체 그림
3-2. 암호 해시 알고리즘의 종류
- MD5 : 128-bit
- SHA-1 : 160-bit
- SHA-2 : 해시 값의 크기에 따라 다른 길이
- SHA-256 : 256-bit, 비트코인에서 사용
- SHA-512 : 512-bit
- SHA-384 : 384-bit
- SHA-3
- SHA3-256 : SHA2-256 을 보완
- Keccack-256 : 이더리움에서 사용
3-3. SHA-512 에서의 암호 해싱
- 메시지의 길이 < \(2^{128}\) → 메시지의 길이 < 128-bit
- Digest = 512-bit
- 메시지 블록 = 1024-bit
- 1word = 64-bit
1단계
- 원본 메시지를 1024-bit 크기의 블록으로 분할
마지막 블록의 경우
- 메시지의 길이인 128-bit 을 추가
- 남은 길이만큼 padding 추가
- 10000…..00.. 의 형태로 삽입
$$ \begin{align*} &(Message+Padding+128)\,mod\,(1024)=0\,mod\,(1024) \\&(Padding)\,mod\,(1024)=Padding=(-Message-128)\,mod\,(1024) \end{align*} $$
$$ \begin{align*} Last\ Block=(Message)\,mod\,(1024) +Padding+128=1024bits& \\Padding<1024bit& \\Padding = 1024-(Message)\,mod\,(1024)-128 \end{align*} $$
$$ \begin{align*} (Padding)\,mod\,(1024)&=\{1024-(Message)\,mod\,(1024)-128\}\,mod\,(1024) \\&=\{-(Message)\,mod\,(1024)-(128)\,mod\,(1024)\}\,mod\,(1024) \\&=(-Message-128)\,mod\,(1024) \end{align*} $$
2단계
- SHA-512 : \(H_{0}=512bits=64bits*8=8word\)
- \(H_0\)
- 2부터 19까지 8개의 소수들의 제곱근을 구한 뒤, 소수점부분만 변환하여 사용
3단계
블록 확장
- SHA-512 에서는 round 수를 80으로 고정, 각 round 마다 사용될 80개의 word가 필요함
- 한 블록은 16word → 80word 로 확장
- \(RotR_i(x)\) : 오른쪽 방향으로 x 를 i bit 만큼 rotation
- \(SHL_i(x)\) : 왼쪽 방향으로 x 를 i bit 만큼 shift
- \(W_{16}\) 부터는 이전의 16개의 word를 가져와서 사용
$$ \begin{align*} W_i=W_{i-16}\oplus RotShift_{1-8-7}(W_{i-15})\oplus W_{i-7}\oplus RotShift_{19-61-6}(W_{i-2}) \end{align*} $$
$$ ex)\ \ W77=W_{61}\oplus RotShift_{1-8-7}(W_{62})\oplus W_{70}\oplus RotShift_{19-61-6}(W_{75}) $$
Compression Function f
- 초기 A~H 는 2단계에서 구한 값
- 그 후, 각 라운드의 결과가 다음 A~H
round 79 가 끝나면 Final adding 을 통해 최종 A~H 결과 산출
각 round 수행 과정
- round 에 들어오게되는 A~C 는 결과의 B~D, E~G 는 결과의 F~H
- 결과의 A와 E는 위의 복잡한 과정을 통해 산출
- Y 값을 구할 때 사용되는 \(K_i\) 의 값은 아래의 사진에서 사용
- 2 ~ 409까지 80개의 소수에 대한 세제곱근의 소수점부분만 변환하여 사용
- \(K_0, ... ,K_{79}\)
4단계
최종적으로 \(H_{t}\) 완성
4. 메시지 인증
- 변경 감지 코드 MDC
- Modification Detection Code
- 해당 메시지가 수정되지 않았음을 보장하기 위함
- \(Hash(Message)\) 가 MDC 의 역할
4-1. MDC
만약 메시지와 MDC 를 같은 채널에서 보낸다면?
→ 공격자가 중간에서 탈취
→ 원하는 메시지로 조작하여 다시 MDC 를 만들어 전달
결국 MDC 는 같은 채널이 아닌 다른 안전한 채널에서 보내야 함
4-1-1. MDC 의 문제점
- 메시지를 보낸 사람이 누군지를 인증하지 못함
- MAC
- Message Authentication Code
- 대칭 키 마냥 서로 공유하는 암호 키(K) 가 존재
- \(MAC=Hash(Message\ 에\ K\ 를\ 붙임)\)
- 같은 채널에서 보낸다 하더라도 K 를 모른다면 탈취되어도 변조할 수 없음
- 그러나 Hash 함수가 비교적 간단한 함수라면 쉽게 K가 파악될 수 있음
4-2. HMAC
- Hashed MAC
- NIST 표준 MAC
4-2-1. HMAC 구현 과정
1단계
메시지를 b-bit 의 블록으로 분할
키를 b-bit 로 padding
2단계
1단계의 키를 ipad(0x36….36) 과 XOR 연산
3단계
- 메시지에 b-bit 로 padding 그리고 ipad 와 XOR 연산을 거친 키를 붙여 첫번째 해시 함수 적용
- 첫번째 HMAC 결과
- 해시 함수가 가지는 결과의 bit 를 n 이라고 가정
- 첫번째 HMAC 은 n-bit
- 첫번째 HMAC 을 b-bit 로 padding
4단계
1단계의 키를 opad(0x5C….5C) 와 XOR 연산
5단계
4단계의 키와 3단계의 첫번째 HMAC 을 붙여 마지막 해시 함수 적용
→ 최종 HMAC
전체 그림
