- Hash Function

해시 함수란?

임의 길이 데이터(입력) → 고정 길이 데이터(출력)로 매핑하는 단방향 함수 (비용 고려)

결과값: Hash Value, Code, Check-sum, Digest ~ 해시 테이블 구조에 이용(검색 용이/단, 해시충돌 확률 고려)

해시 충돌 예시 (같은 결괏값)-무결성 검증 불가

 

* 데이터 무결성(Data Integrity)이란?  정확성(Accuracy), 일관성(Consistency), 유효성(Assurance) 유지 <위변조 확인>

◻︎ 해시 함수의 구분

 

- 비암호적 해시 함수(보안성 제공X): CRC32(Cycle Rebundancy Check)

= 파일 우발적인 수정 검출(깨진파일여부, 순환중복검사)

- 암호적 해시 함수(Cryptographic Hash Function): MD5, SHA계열 (패딩 방식에 따라 최대 길이 제한)

* pre-images(역상/제2역상), Collision(충돌-쌍)에 대한 안정성 필요

 

* 역상<𝐻(x) = h, x는 h의 역상> 저항성(Preimage Resistance)이란?

해시 함수 출력값으로 입력값(원본 데이터) 추출 불가 - 일방향

즉, 어떤 해쉬값에 대하여, 공격자가 그 역상을 찾아내는 것이 계산적으로 실행 불가능하다는 보안 보장 속성

* 제 2 역상 저항성이란? 입력값 1과 결괏(해시)값를 가지고, 다른 입력값을 찾을 수 없다는 특성

* 충돌 저항성(Collison Resistance)이란? 가능한 해시 결과값보다 입력값 종류가 많은 경우, 중복/충돌 발생(비둘기 집 원리)

// 충돌 저항성 만족시, 제 2 역상 저항성 만족

* Birthday Attack 가능: 무차별 대입 공격으로 해킹-확률적 가능성 보장, 해시 충돌되는 값 도출 (해시 충돌 쌍을 찾아내서 위/변조)

~> 공격 복잡도 2𝑛/2개 메시지-해시값 쌍 (메모리 요구량) + 해시/정렬 (연산량) ~ 해시 함수 출력 길이는 안정성 파라미터*2

예시) 𝐻(𝑚) = 𝑚 (𝑚𝑜𝑑 𝑘) 의 경우, 역상저항성 + 충돌저항성 = 만족X :  같은 결괏값 가능성 -->  원본 데이터 해킹 가능 

 

# 이상적인 해시 함수 보안-속성

Speed, Deterministic(동일 입력~해시함수*~동일 출력), Unifomity(데이터 전반-동일한 양 해싱 수행), Fixed-size(고정 크기의 출력), Not reversible functions(단방향 함수), Avalanche effect(입력 정보-단일 문자 변경시, 출력 값 변경)

 

# 해시 함수 구성

 

1) 압축 기반

Building block - 정해진 크기의 입출력을 갖는 압축함수 (충돌 저항성 가짐/입력크기 > 출력크기)

~압축 함수를 반복적으로 사용 - Domain Extension 기법 (Merkle-Damgard)

(패딩된 메시지=특정 길이) 블록 분할: y0(IV) + m... ⟷ f(내부 상태 섞음) => yi, 연쇄적 계산 결과

* 안정성: 블록 암호

 

2) 치환 기반 (결정론적 난수 비트 생성기, 스트림 암호, 의사난수 함수, 인증 암호로도 사용됨)

하나의 치환 함수 f를 반복적으로 적용(XOR 연산) - 스폰지 방식 (메시지 흡수 Absorbing & 압착 Squeezing)

* 보안성(안정성 보장) - 내부 상태값 길이(w) & 메시지 블록 길이(r)에 의존 + 함수 f가 랜덤 치환(통계적X) 처럼 행동해야 함

스펀지 용량 c = w - r 일때, 기본 안정성 수준은 c/2 => 64-bit 메시지 블록,

128-bit 안정성을 위해서는 128*2+64 = 내부 상태값 길이 필요

 

* 충돌 공격의 복잡도(Birthday Attack) = 2n/2 or 2c/2 중 작은 값 <해시값 길이 n에도 의존>

흡수 : 내부상태값 r, c로 분할 ~> r과 메시지 블록 Pi를 XOR ~> 치환 함수 f 를 이용하여, 내부 상태값을 같은 길이 다른 값으로 변환

압착 : 모든 메시지 블록 흡수 후, 내부 상태값에 F 재적용~일부 비트 추출 후 해시값 생성(길이 추가시, 비트 추출 과정 추가 반복)

 

# SHA 족 해시 알고리즘

https://bmsce.ac.in/Content/CS/NV_CNS_UNITV.pdf

---

해시함수 응용 예시)

1. Digital Signature (메시지-해시값에 서명)
2. Public-Key Encryption
3. Integrity Verification (무결성 검증-파일 식별값)
4. Commitment (Hiding/Binding)
5. Message Authentication
6. Password Protection
7. Key Agreement
8. Merkle Tree - 메시지 검증/부인 방지 목적의 해쉬값 전송 (log2 t<메시지 개수>개로 검증 가능)
9. Bitcoin - 비트코인 채굴(코인 검증: Nonce 값 변경 ~> 블록해쉬값 000000..으로 시작될 때까지 시도)

해시함수 보안 문제)

* Length-extension Attack (길이 연장 공격): 메시지 m1의 해시값 + 길이 ->→ (m1 + pad(m1) + m2) 해시값 도출 가능

취약: M-D 구성, SHA-2 알고리즘 ~> 마지막 압축 함수 실행 변경으로 해소 *BLAKE2

 

* Proof-of-storage (저장 증명): In Cloud Computing-Application Program, Client 파일 저장 요청

-> Server 저장 확인_프로토콜 - 내부에서 해시함수 이용, 난수 값 C ⟷ H(M|C) 일치 확인

ㄴ 해시함수 취약-속임수: 블록단위 중간 연쇄값..반복연산 형태 ~ 메시지(해시계산 후) 폐기,

최종 연쇄값만 저장 *H(C|M)으로 수정=방어

 

---

 

 

[References]

https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%95%A8%EC%88%98

https://blog.naver.com/softwidesec/222536537576

https://3-24.github.io/cryptography/length-extension-attack/