공부/암호학

Hash Function

은붕어_ 2025. 8. 7. 18:00
반응형

요즘 어쩌다보니 암호학 공부를 열심히 하게 되었습니다….. 오늘은 해시함수입니다. 해시 함수는 컴퓨터 보안의 세계에서 누구나 한번쯤은 들어본 적있는 빠질 수 없는 기술입니다. 단순한 데이터 압축이 아니라, 정보의 무결성을 지키고 비밀번호를 안전하게 저장하며, 블록체인의 기반까지 형성하는 근간이 된다고 생각합니다.

해시 함수란?

해시 함수는 임의의 길이를 가진 데이터를 고정된 길이로 변환하는 단방향 함수입니다.

즉, 아무리 긴 입력이 들어가도 일정한 길이의 고정된 결과값(해시)이 나옵니다.

주요 특징:

  • 단방향성: 출력만으로는 원래 입력을 유추할 수 없음 (비가역성)
  • 동일 입력 → 항상 동일 출력
  • 입력 조금만 달라도 전혀 다른 해시값 (눈사태 효과)
  • 다이제스트 : 입력값을 해시함수를 통해 해싱을 한 후의 결과값(=해시값)

해시 함수의 3가지 보안 조건

역상 저항성: 해시값 H가 주어졌을 때, 원래 입력 I을 찾는 게 거의 불가능해야 함

 

제2 역상 저항성: 주어진 입력 I와 해당하는 다이제스트가 주어졌을때 같은 해시값을 만드는 또 다른 입력값을 찾는 게 어려워야 함

 

충돌 저항성: 서로 다른 두 입력값이 같은 해시값을 갖지 않도록 설계되어야 함

 

 

이 중 가장 강력한 요구 조건은 ‘충돌 저항성’이며, 이걸 만족하면 나머지도 대부분 따라옵니다.

생일 역설과 비둘기집 원리

  • 생일 역설: 23명만 있어도 두 사람이 생일이 같을 확률이 50% 이상
  • 해시에서는 n비트 출력이면 약 2ⁿ⁄²개만 입력해도 충돌이 생길 수 있음
  • → 그래서 SHA-256 같은 해시를 사용해 128비트 충돌 저항성을 확보

 

  • 비둘기집 원리: 입력은 무한하고 출력은 유한 → 충돌은 이론적으로 불가피
  • → 좋은 해시는 실질적으로 충돌 찾는 것이 불가능하도록 설계

해시 함수의 실제 활용

분야 역할

Git 커밋 추적 및 무결성 검증
파일 공유 (토렌트) 신뢰성 보장
비밀번호 저장 평문 저장 대신 해시값 저장 (솔트 포함)
  • 솔트(Salt): 사용자별 무작위 값 추가 → 같은 비밀번호도 서로 다른 해시 생성
  • 메모리 하드 알고리즘 (예: Argon2): 무차별 공격에 저항

SHA 시리즈 요약

알고리즘 상태

MD4, MD5 Ron Rivest가 설계한 128비트 출력 해시 함수, 충돌 성공 → 사용 금지
SHA-0, SHA-1 NIST에서 발표한 160비트 출력 해시 함수, 충돌 성공 → 사용 금지
SHA-2 NIST에서 발표한 256~512비트 출력 해시 함수, 머클-담고르 구조 기반, 가장 널리 사용됨 (SHA-256, 512 등)
SHA-3 NIST에서 공모 후 발표한 256~512비트 출력 해시 함수, 스펀지 구조 기반, 더 유연하고 구조적 보안 강함

KECCAK

KECCAK(케척)은 SHA-3 공모전에서 선정된 해시 알고리즘으로, NIST의 기존 SHA-1, SHA-2 계열과 달리 **스펀지 구조(Sponge Construction)**를 기반으로 합니다.

내부적으로는 permutation 함수와 비트 연산을 반복해 출력값을 만들어내며, 보안성과 유연성 면에서 높은 평가를 받았습니다.

  • 2007년 Guido Bertoni 등이 제안
  • AES처럼 substitution-permutation 네트워크(SPN)를 기반으로 작동
  • 내부 상태: 1600비트 (r + c 구조), r은 출력과 입력에 사용되는 rate, c는 내부 보안의 capacity
  • SHAKE, cSHAKE, KMAC 등의 기반이 되는 알고리즘

머클-담고르

머클-담고르(Merkle–Damgård)는 대부분의 전통적 해시 함수가 따르는 구조입니다.

  • 입력 메시지를 고정된 크기의 블록으로 분할하고,
  • 이를 순차적으로 **압축 함수(compression function)**에 적용해
  • 마지막 출력값을 해시값으로 사용하는 방식입니다.

특징:

  • 입력 길이의 제한이 없고, 출력은 고정
  • 구조상 **길이 확장 공격(length extension attack)**에 취약할 수 있음
  • MD5, SHA-1, SHA-2 등이 이 구조를 따름

데이비스-마이어구조

 

 

 

머클-담고르 구조에서 사용되는 압축 함수의 대표적인 구현 방식입니다.

  • 블록 암호를 활용하여,
  • H_i+1 = E_Mi(H_i) ⊕ H_i 형태로 계산
  • 입력 메시지를 암호화에 키로 사용하고,
  • 이전 해시값을 평문으로 넣어 XOR로 최종값 생성

특징:

  • 충돌에 강하지만, 구현 시 충돌 저항성과 블록 암호 안전성 모두에 의존
  • SHA-1 등에서 사용됨

스펀지 구조

 

KECCAK과 SHA-3 계열의 핵심 구조입니다.

  1. 흡수 단계(absorbing):
    • 입력 데이터를 r비트 단위로 쪼개서 내부 상태에 XOR
    • 그 후 비선형 변환 함수(f)를 적용해 내부 상태 갱신
  2. 짜내기 단계(squeezing):
    • 내부 상태에서 r비트씩 출력
    • 원하는 출력 길이가 될 때까지 반복 가능 → XOF 지원

특징:

  • 입력·출력 구조가 대칭적이라 XOF(확장 출력 함수) 구현이 가능
  • 메시지 길이 공격에 강하고 구조적으로 안전성 우수
  • SHA-3, SHAKE, cSHAKE, KMAC, TupleHash 등에서 사용

SHA-3의 확장

알고리즘 상태

XOF eXtendable Output Function의 약자로, 출력 길이를 사용자가 지정할 수 있는 해시 함수. SHA-3와 스펀지 구조 기반
SHAKE SHA-3의 확장형 XOF. SHAKE128, SHAKE256 등 버전 존재. 출력 길이 유연하며 랜덤 바이트 생성, MAC에 적합(SHA+KEccak)
cSHAKE SHAKE에 도메인 구분 문자열(customization string) 기능을 추가한 버전. 같은 입력이라도 다른 목적이면 다른 출력 생성 가능
튜플해시 여러 메시지를 순서와 구분을 보존한 채 해시. 내부적으로 cSHAKE 사용. 인증·식별·다중 입력 처리에 적합

해시 함수를 공부하면서 가장 크게 느낀 건, 이게 암호화처럼 보이지만 결국 그 자체로는 암호화는 아니라는 점이었습니다. 복호화가 불가능하다는 특성 때문에 오히려 보안 쪽에서는 아주 중요한 역할을 한다는 걸 알게 됐습니다. 개인적으로는 해시를 쓰는 가장 큰 이유가 고유한 값을 만드는 것, 그리고 원래 값을 숨기는 것이라고 생각합니다. 이 두가지 특성으로 다양한 분야에서 해시를 사용하게 만들었다고 생각합니다.

 

 

 

 

반응형