해시 함수

해시 함수(hash function)는 임의의 길이의 데이터message를 고정 길이의 데이터hash value, hash code, digest, hash로 매핑하는 함수이다.

동일한 input에 대해서는 같은 결과를 도출한다.

암호화 해시 함수 (Cryptographic Hash Function)

해시 함수의 일종으로, 해시값으로부터 원래의 입력값과의 관계를 찾기 어려운 성질을 가진다.

• 역상 저항성 (pre-image resistance)
  해시값이 주어졌을 때, 해시값을 생성한 입력값을 찾는 것이 계산상 어렵다.
  제 1 역상 공격(주어진 해시값을 출력하는 입력값을 찾는 공격)에 대해 안전한 것을 말한다.

• 제 2 역상 저항성 (second pre-image resistance)
  해시값과 입력값이 주어졌을 때, 해시값을 생성하는 또 다른 입력값2를 찾는 것이 계산상 어렵다.
  제 2 역상 공격(주어진 입력값과 같은 해시값을 출력하는 다른 입력값을 찾는 공격)에 대해 안전한 것을 말한다.

• 충돌 저항성 (collision resistance)
  같은 해시값을 생성하는 두 개의 입력값을 찾는 것이 계산상 어려워야 한다.
  해시 충돌에 대해 안전해야 한다는 것을 말한다.

여기서 제 2 역상 저항성과 충돌 저항성의 차이점은?
제 2 역상 저항성에서는 공격자가 입력값 외 동일한 해시값을 생성하는 입력값2를 찾는 것이고,
충돌 저항성은 공격자가 동일한 해시값을 생성하는 입력값 두 개를 자유롭게 선택할 수 있다.
Second pre-image resistance vs Collision resistance

해시 충돌

해시 함수가 서로 다른 두 개의 입력값에 대해 같은 출력값을 도출하는 상황이다.
무한한 입력값을 받아 유한한 출력값을 생성하는 경우, 비둘기집 원리에 의해 해시 충돌은 항상 존재한다.

비둘기집 원리

• n + 1개의 물건을 n개의 상자에 넣을 때 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리
• 5명의 사람을 서로 같은 팀이 되지 않도록 4개의 팀에 나누는 것은 불가능하다

생일 문제

• 사람이 임의로 모였을 때 그 중에 생일이 같은 두 명이 존재할 확률을 구하는 문제
• 1년은 365일이므로 366명이 모인다면 비둘기집 원리에 따라 생일이 같은 두 명이 반드시 존재한다
• 23명만 모여도 두 명이 생일이 같을 확률은 50%가 넘고, 57명이 모이면 99%를 넘어간다

순환 중복 검사 (CRC, cyclic redundancy check)

네트워크 등을 통하여 데이터를 전송할 때, 전송된 데이터에 오류가 있는지 확인하는 방식이다.

• 데이터를 전송하기 전, 주어진 데이터에 대한 CRC 값을 계산하여 데이터에 붙여 전송한다.
• 받은 데이터의 값으로 CRC 값을 계산해 오류가 덧붙여 전송되었는지 확인한다.

주어진 CRC 값을 가지는 다른 데이터를 만들기 쉽다.
⇒ 제 2 역상저항성, 충돌 저항성을 가지지 않음

CRC32

CRC 방식 중 CRC-32 다항식을 이용해 체크값을 구한다.

x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 +x4 + x2 + x + 1
0x04C11DB7

MD5 (Message-Digest algorithm 5)

임의의 길이의 데이터로부터 128비트 고정 길이 출력값을 도출하는 알고리즘이다.

현재 MD5를 보안 관련 용도로 쓰는 것은 권장하지 않는다.

• 설계 결함
• 해시 충돌을 찾는 알고리즘 발표

1. MD5는 512bit 단위로 알고리즘을 수행하므로, 512bit로 나누어 떨어지도록 패딩 작업을 한다.
   (첫 단일 비트, 1을 메시지 끝 부분에 추가한 뒤 512 배수 길이보다 64bit 적은 곳까지 0으로 채운다. 그 뒤 본래 메시지의 길이로 64비트를 채운다.)
2. 메인 알고리즘은 32비트 워드(상수값으로 초기화된 A, B, C, D) 4개로 이루어진 하나의 128bit state에 대해 동작한다.
3. 각각의 512bit 입력 메시지 블록을 처리(4단계, 16개의 연산으로 이루어진 한 단계를 라운드라고 한다)하고 나면 state 값이 변한다.

잘못된 정보가 있다면 알려주시면 감사하겠습니다 😊

참고: 위키백과