안전 해시 함수

안전 해시 함수

일방향 해시 함수 혹은 안전 해시 함수는 메시지 인증과 디지털 서명에서 매우 중요한 함수이다.

안전 해시 함수는 암호학적으로 안전한 해시 함수로, 일방향성, 프리이미지 저항성, 충돌 저항성의 조건을 만족하고 보안성이 검증된 함수를 말합니다

해시 함수 요건

해시 함수의 목적은 파일 메시지 데이터 블록에 대한 fingerprint를 만드는 것이다.

메시지 인증에 사용하기 위해서 해시 함수 H는 다음과 같은 속성이 있어야 한다

1. H는 어떠한 크기의 데이터 블록에도 적용 될 수 있어야 한다.
2. H는 일정한 길이의 출력을 생성해야 한다.
3. H(x)는 어떤 x에 대해서도 계산이 쉬워야 하고, 하드웨어적이나 소프트웨어적으로 구현을 실제로 할 수 있어야 한다
4. 일방향 성질(프리이미지 저항성) : H(x) = h가 성립 되는 x를 찾는 것이 계산적으로 불가능 해야 한다
5. 약한 충돌 저항성(2차 프리이미지 저항성) : H(x) = H(y)를 만족하는 y!=x를 찾는 것이 계산적으로 불가능 해야 한다.
6. 충돌 저항성(강한 충돌 저항성) : H(x)=H(y)를 만족하는 쌍 (x,y)를 찾는 것이 계산적으로 불가능해야 한다.

각 속성의 세부 사항

1~3 번의 성질은 메시지 인증에 해시 함수를 응용하기 위한 필요한 사항이다

일방향 성질 : 주어진 메시지 코드를 만드는 것은 쉽지만, 주어진 코드로부터 메시지를 만들어 내는 것은 불가능해야 한다.

• 일방향이 아니면, 공격자가 쉽게 비밀 값을 찾아낼 수 있다.
  프리이미지 저항 성질 : 주어진 메시지의 해시값과 동일한 해시 값을 갖는 다른 메시지를 만드는게 불가능하다
• 암호화된 해시 코드가 사용 될 경우에 위조를 방지 하기 위함
• 이 성질이 사실이 아닐 경우, 해시 코드를 가로채거나 구할 수 있다.

충돌 저항성 : Birth day attack을 방어한다

• birthday attack을 하면, m-비트 해시 함수에 대한 공격 난이도가 2^m에서 2^(m/2)로 낮아진다

• 약한 해시 함수 : 1~5까지 만족하는 해시 함수

• 강한 해시 함수 : 1~6까지 만족하는 해시 함수

해시 함수 보안 - 전수 공격

전수 공격에 대한 해시 함수의 강도는 알고리즘이 생성하는 해시 코드의 길이에 전적으로 달려 있다.
길이가 n-bit인 해시 코드에 대한 공격 난이도는 다음과 같이 비례적으로 증가한다

레퍼런스

• [[Notes/충돌 저항성|충돌 저항성]]