정보보안기사 - 해시함수

일방향 해시함수

임의의 길이를 갖는 메세지 입력으로 고정된 길이의 해시값 또는 해시코드라 불리는 값을 출력하는 함수입니다.

서로 다른 두 개의 메세지가 하나의 해시로 출력되는 현상을 '충돌'현상이라고 하며, 이러한 현상을 막기 위해서 '충돌 내성'을 가져야 합니다.

 

• 해시값을 고속으로 계산할 수 있습니다.
• 해시값으로부터 메세지를 구할 수 없는 일방향성을 갖습니다.
• 메세지가 다르면 해시값도 다릅니다.
• 기본적으로 무결성을 검증, 소프트웨어 변경을 검출할 수 있지만 부인방지는 검출할 수 없습니다.
• 메시지 인증코드(MAC), 전자서명에 활요됩니다. (인증을 수행하기 위한 기술)
• 기본적으로 키가 존재하지 않습니다.

 

암호학적 해시 함수 설계시 목적 3가지

역상 저항성(preimage resistance), 제 2 역상 저항성(seconde preimage resistance), 충돌 저항성(collision resistance)

• 역상 저항성(preimage resistance)

y = h(M)에 대해서 y=h(M`)을 만족하는 M`를 찾아낸다는 것이 매우 어려워야 합니다.

즉, 주어진 결과값에 대해 입력값을 계산하기 어려워야 한다.

 

• 제 2 역상 저항성(seconde preimage resistance)

주어진 입력값에 대해 충돌쌍(같은 결과값)을 갖는 다른 입력값을 계산하기 어려워야 합니다.

 

• 충돌 저항성(collision resistance)

충돌쌍(같은 결과값)을 갖는 두 개의 입력값을 계산하는 것이 어려워야 합니다.

 

 

전자서명에 이용되는 해시함수의 특성

• 해시 값을 고속으로 계산
• 역상 저항성(preimage resistance)
• 제 2 역상 저항성(seconde preimage resistance)
• 충돌 저항성(collision resistance)

 

해시함수의 종류

• MD(Message Digest)

MD(Message Digest)는 RSA를 개발한 MIT의 Rivest 교수에 의해 개발된 압축 알고리즘으로 MD2, MD4, MD5의 3가지 버전이 있습니다. 

MD2 8비트 컴퓨터에 최적화, 속도가 느림.

MD4 32비트 커퓨터에 사용, 속도는 빠르지만 안정성이 떨어짐.

MD5 MD4에 비해 속도는 떨어지지만 훨씬 더 안정적이어서 폭넓게 사용 됨.

-> 강한 충돌 내성을 공격하는 생일공격(Birthday Attack)에 노출되어 보안 요구사항이 높은 응용 분야에서는 사용이 권장되지 않고 있습니다.

 

• SHA(Secure Hash Algorithm)

MD4기반으로 개발되었습니다. 취약점 발견으로 SHA-1(FIPS PUB 180-1)이 발표되었으며 512비트 블록을 160비트 MD로 출력하는 해시함수로 SHA함수군 중 가장 많이 사용되며 TLS,SSL, PGP, SSH 등 다양한 보안 프로토콜과 프로그램에서 사용되고 있습니다. 

 

• TIGER

64비트 시스템에 사용하기 위해 개발된 암호화 해시함수로 MD5 및 SHA-1보다 속도가 더 빠릅니다.

 

• HAS160(Hash Function Algorithm Standard 160)

한국형 전자서명 표준인 KCDSA에서 사용할 목적으로 개발된 암호화 해시 알고리즘으로, 512비트의 메시지 블록으로부터 160비트의 해시코드를 출력하는 32비트 시스템에 맞게 설계된 Little Endian 구조의 해시함수입니다.

 

항목	MD5	SHA-1	RIPEMD-160
다이제스트 길이	128비트	160비트	160비트
처리 단위	512비트	512비트	512비트
단계수	64(16번의 4라운드)	80(20번의 4라운드)	160(16번의 5병행 라운드)
최대 메시지 크기	무한	2의 64승 -1	2의 64승 -1
앤디언	Little-endian	Big-endian	Little-endian2

 

암호화 해시함수의 활용

• 무결성 점검

암호화 해시함수는 해시값의 비교를 통해 메시지 또는 문서가 변경되었는지 여부를 판별함으로써 무결성 점검을 위해 사용됩니다.

 

• 소프트웨어 변경 검출

전달받은 소프트웨어가 원본과 동알한 지 여부를 확인하기 위하여 해시함수를 사용할 수 있습니다. 즉, 소프트웨어를 다운로드한 후 해시값을 계산하고 이를 원본 페이지에서 제공하는 해시값과 비교하여 소프트웨어가 변조되었는지 검출합니다.

 

• 메시지 인증코드

키가 있는 해시함수(Keyed Hash Function)를 사용하는 경우 메시지의 무결성 외에 송신자와 수신자 간의 비밀키를 이용하여 메시지 인증을 수행할 수 있습니다.

 

• 전자서명

전자서명에서도 일방향 해시함수가 사용됩니다.

 

해시함수에 대한 공격

• 무차별 공격

'약한 충돌 내성'을 깨고자 하는 공격으로 메시지 다이제스트의 크기가 160비트인 경우 2^160회를 시도하면 원하는 메시지를 찾을 수 있습니다.

 

• 일치블록 연쇄공격

사전에 새로운 메시지 M`를 다양하게 만들어 놓았다가 공격하고자 하는 메시지 M의 해시값 h(M)과 같은 해시값을 가지는 것을 골라 사용하는 공격입니다.

 

• 중간자 연쇄공격

전체 해시값이 아니라 해시 중간 결과에 대한 충돌쌍을 찾습니다.(특정 포인트를 공격대상)

 

• 고정점 연쇄공격

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

 

• 차분 연쇄공격

다운 라운드 블록암호의 공격 : 다중 라운드 블록암호를 사용하는 해시값과 그에 대응하는 출력값의 통계적 특성을 조사하는 기법입니다.

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