Class / Cryptographic Hashing and Message Authentication

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

 

전체 그림

 

---