[정보보안기사] SECTION 05 해시함수와 응용

SECTION 05 해시함수와 응용

1. 일방향 해시함수

■개념 및 특징

○임의의 길이를 갖는 메시지를 고정된 길이의 해시 값(해시코드)로 출력하는 함수

○고속으로 계산

○일방향성(One-Way)으로 해시 값으로부터 원본 메시지를 역산 할 수 없음.

○입력 메시지의 1bit 바뀌어도 해시 값이 다름

○무결성을 확인하기 위해 사용

○2개의 다른 메시지가 같은 해시 값을 같은 것을 충돌(Collision)이라 하고, 일방향 해시함수는 충돌내성을 가질 필요가 있음

■해시함수의 분류와 보안요구사항

○프리이미지 저항성(역상 저항성)

○y = h(M)일 때, 공격자가 출력값 y에 대해 입력값 M를 찾아내는 것이 매우 힘들어 야 한다는 성질

○제 2프리이미지 저항성(두번째 역상 저항성, 약한 충돌 내성)

-메시지를 쉽게 위조할 수 없도록 해야 한다.

-공격자가 메시지 M에 대한 결과 값 h(M)을 가로 채고, h(M)과 동일한 결과 값을 만드는(h(M)=h(M’)의 성질을 만족하는) 메시지 M’를 찾는 것이 계산적으로 불가능 해야 함

○충돌 저항성(충돌 회피성, 강한 충돌 내성)

-h(M)=h(M’)을 만족하는 임의의 두 값 M과 M’를 찾는 것이 계산적으로 불가능 해야함.

■전자서명에서 해시함수의 특징 (★★★★)

○고속으로 계산할 수 있어야 함.

○약 일방향성 : y=h(M)일 때, y로부터 메시지 M을 찾는 것이 불가능

○강일방향성 : 서명문 M과 해시값 y=h(M)이 주어졌을 때, h(M’) = y 가 되는 M’를 찾는 것이 불가능

○충돌회피성 : h(M) = h(M’)가 되는 쌍을 찾는 것이 계산상 불가능

■키가 없는 해시함수와 키를 사용하는 해시

○해시 연산에 따른 분류

-전용 해시함수

-블록 암호를 기초로 한 해시함수

-모듈 연산을 기초로 한 해시함수

■전용 해시함수

○SHA-1, RIPEMD/128/160, HAVAL 등

○메시지 다이제스트(Message Digest)

-MD2 -> MD4 -> MD5로 발전

-MD5 : 메시지를 512비트로 된 블록들로 나누고 128비트 다이제스트를 출력

-현재 128bit는 너무 짧다고 알려져서 사용하지 않음

○SHA(Secure Hash Algorithm)

-해시 값이 각 256, 384, 512 비트임.

-SHA-1과 하부구조가 동일하며, 모듈러 연산과 논리적 2진 연산을 이용

-2005년 SHA-1은 강한 충돌 내성이 깨졌다는 것을 접수하고 SHA-3을 제정함.

○RIPEMD-160

-160bit 메시지 다이제스트를 생성

○Tiger

-64bit 시스템에서 해시 함수를 수행하기 위해 설계, MD5, SHA-1보다 속도가 빠름

-HAVAL

-128, 160, 192, 224, 256 bit인 메시지 다이제스트를 출력하고, 사용하는 블록크기는 1024비트

■블록암호 기반 해시 함수

○해시 함수 안에 사용하는 압축 함수 자리에 대칭키 블록 암호를 상용 할 수 있음

■모듈 연산에 기반을 둔 함수

○압축 함수의 기반을 모듈 연산의 반복적인 수행에 두고 있는 해시함수

○소프트웨어 자체에 내장된 모듈 연산을 사용할 수 있다는 장점은 있으나 속도가 빠르지 않고 안전성에 대한 역사가 짧음

■키를 사용하는 해시 함수

○키를 사용하는 해시함수는 메시지 인증 기능을 가진 함수

○해시 함수 자체이 안전성과 키의 비밀성까지 안전성을 두고 있음.

■암호학적 해시함수 응용

○무결성 검증

-메시지 혹은 문서의 무결성을 검증하기 위해 사용

-새로운 메시지 다이제스트는 이전의 메시지 다이제스트와 비교하여 검증

○소프트웨어 변경 검출

-입수한 소프트웨어가 변경되었는지 확인하는 방법

-소프트웨어를 입수 한 후, 그것을 직접 해시 하여 나온 값을 오리지널 사이트에서 제공하는 해시 값과 비교

○메시지 인증 코드

-일반적으로 메시지 인증은 키가 있는 해시함수로 알려진 메시지인증 코드 (MAC, message Authentication Code)를 사용

-상호간에 교환되는 정보를 인증하기 위해서 사용

○전자서명

-현실사회의 서명(사인)에 해당하는 행위(내가 했음을 증명)임

■일방향 해시함수에 대한 공격

○무차별 공격

-Sha-1의 경우 해시값이 160비트 이므로 2^160회를 시행하면 원하는 메시지가 발견됨

○일치블록 연쇄 공격

-메시지 M을 다양하게 만들어 놓았다가 공격하고자 하는 메시지M의 해시값 h(M)과 같은 해시 함수를 갖는 것을 골라서 사용하는 공격

○중간자 연쇄 공격

-전체 해시 값이 아니라, 해시 중간의 결과에 대한 충돌 쌍을 찾음.

○고정점 연쇄 공격

-메시지 블록과 연쇄변수 쌍을 얻게 되면, 연쇄 변수가 발생하는 특정한 점에서 임의의 수의 동등한 블록들 x를 a시지 중간에 삽입해도 전체 해시값이 변하지 않음

○차분 연쇄공격

-다중 라운드 블록암호의 공격 : 입력값과 그에 대응하는 출력 값 차이를 통계적 특성을 조사하는 방법

-해시함수의 공격 : 압축 함수의 입출력 차이를 조사하여 0의 충돌 쌍을 주로 찾아내는 방법

■일방향 해시함수로 해결할 수 없는 문제

○조작과 변경을 검출할 수 있지만, 거짓행세를 검출하지 못함.

○파일의 무결성을 조사하는 것 뿐 아니라, 이 파일이 정말 앨리스의 것인가를 확인하고 싶은 경우 무결성 외에 인증 절차(메시지 인증코드, 전자서명)가 필요

2. 랜덤 오라클 모델과 해시함수에 대한 공격

■랜덤 오라클 모델

○개념

-1993년 소개된 해시함수에 대한 이상적인 수학모델

-임의의 길이를 갖는 메시지에 오라클은 0과 1로 이루어진 난수 스트링인 고정된 길이의 메시지 다이제스트를 생성해서 제공

-이미 다이제스트가 존재하는 메시지가 주어지면, 오라클은 저장되 있던 다이제스트를 제공

-새로운 메시지에 대한 다이제스트는 다른 모든 다이제스트와 독집적으로 선택될 필요가 있고, 다이제스트를 만들이 위해 공식이나 알고리즘을 사용해서는 안됨

■비둘기 집 원리

○만약에 n+1마리의 비둘기가 n개의 비둘기집에 들어가 있다면, 적어도 한 비둘기 집에는 두 마리의 비둘기가 들어가 있다는 뜻

■생일문제(생일 공격)

○특정 해시 값을 생성하는 메시지를 구하는 것이 아니라, 해시값은 뭐든지 괜찮으며 어쨌든 같은 해시 값을 생성하는 2개의 메시지를 구하는 것

○생일 패러독스(Birthday Paradox)

-랜덤으로 선택한 N명의 그룹을 생각한다. N명 중 적어도 2명의 생일이 일치할 확률이 2분의 1이상이 되도록 하기 위해서는 N이 최저 몇 명이 되어야 할까?

-정답 : N = 2

-즉 23명만 있으면 확률이 0.507297이 됨

-계산법 : N명 전원의 생일이 일치하지 않을 확률을 구하고, 그것을 1에서 빼낸다 1명째는 365일 중생일이 언제라도 괜찮고, 2명째는 1명의 생일을 제외한 364일이 괜찮다. 3명짼 363, 4명짼 362, N명째는 365-(N-1)=365-N+1

3. 암호학적 해시함수의 예

■SHA-512

○다중-블록 메시지로부터 512bit의 다이제스트를 생성

○각 메시지 블록은 1024 bit의 길이를 가지고, 메시지의 총 길이는 2^128bit를 넘지 않는다..

○메시지의 길이가 2^128 bit보다 작은 경우, 패딩을 붙임

○패딩에는 원래 메시지의 길이를 표시함.

○공격자가 해시 값이 같으면서, 입력 값이 다른 메시지를 찾는 것을 어렵게 하는 보안 요소

■SHA-3

○이론적으로 공격 방법이 알려져 버린 SHA-1을 대신하여 새로운 표준이된 일방향 해시 알고리즘

○2012년 KECCAK를 SHA-3으로 선정.

4. 메시지 인증코드(MAC)

다음에.. 계속 추가해기..