해시 함수_Hash Function(정보보안기사)

1. 해시함수 개념

해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다. 이때 매핑된 결과물은 해시 값 또는 해시 코드라고도 부릅니다. 해시 함수는 해시 테이블, 메시지 다이제스트, 암호학적 해시 등에 사용됩니다.

해시 함수는 입력 데이터에 대해 고정된 크기의 출력을 생성하며, 같은 입력 값에 대해서는 항상 같은 해시 값이 생성됩니다. 그러나 다른 입력 값에 대해서는 가능한 한 다른 해시 값이 생성되어야 합니다. 이러한 특징을 "결정론적"이고 "단방향"이라고 합니다. 결정론적이란 입력 값이 같으면 항상 같은 출력을 보장한다는 의미이고, 단방향이란 출력 값을 통해 입력 값을 유추할 수 없다는 의미입니다.

해시 함수는 데이터의 고유한 지문(fingerprint)을 만들어 내기 때문에 데이터의 검색, 비교, 암호화 등에 활용됩니다. 또한 해시 함수는 데이터 무결성 검증, 메시지 인증, 디지털 서명 등과 같은 암호학적 용도로도 사용됩니다.

 

재요약

해시 함수

해시 함수(Hash function)는 임의의 길이를 갖는 데이터를 고정된 길이의 데이터로 변환시켜 주는 함수입니다. 블록체인에서는 해시 함수가 하는 역할은 ‘암호화'로, 해시값 비교를 통해서 위변조 여부를 판별하고, 무결성을 검증하는 데 사용됩니다. 비트코인의 블록체인에 사용된 해시 함수는 SHA-256(Secure Hash Algorithm-256)입니다.

https://upbitcare.com/academy/education/blockchain/52

해시 함수는 무엇인가? - 업비트 투자자보호센터

 

 

 

 

 

 

2. 일방향 해시함수

1) 개념

일방향 해시 함수(One-way hash function)는 입력값을 고정된 길이의 해시 값으로 변환하는 함수로, 이 변환 과정에서 일반적으로 정보의 손실이 일어나기 때문에 입력값을 복원할 수 없는 함수입니다.

 

일반적으로 해시 함수는 입력값의 길이가 어떻든 고정된 길이의 해시값을 생성합니다. 이때, 같은 입력값에 대해서는 항상 같은 해시값을 반환합니다. 즉, 해시값을 통해 입력값을 추론하는 것은 매우 어렵습니다. 또한 입력값이 조금만 변화해도 해시값은 크게 달라집니다.

 

일방향 해시 함수는 주로 암호학에서 사용됩니다. 예를 들어, 사용자의 패스워드를 일방향 해시 함수를 이용하여 변환한 값을 서버에 저장함으로써, 패스워드를 평문으로 저장하지 않고도 인증을 수행할 수 있습니다. 사용자가 로그인할 때, 입력한 패스워드를 동일한 일방향 해시 함수에 적용하여 생성된 해시값과 저장된 해시값을 비교하여 인증을 수행합니다.

하지만, 최근에는 공격자들이 대량의 미리 계산된 해시값들을 이용하여 레인보우 테이블 공격 등을 수행하고 있기 때문에 보안성이 상대적으로 떨어질 수 있습니다. 따라서 보안 강도가 더 높은 함수들이 개발되고 있습니다.

 

 

 

2) 특징

- 임의 길이의 메시지로부터 고정 길이의 해시값을 계산합니다.

- 해시값을 고속으로 계산할 수 있습니다.

- 일방향성을 갖습니다.

 

- 메시지가 다르면 해시값도 다릅니다.

 

 

 

 

 

3) 해시함수의 충돌

 

암호학적 해시함수는 프리이미지 저항성, 제2프리이미지 저항성, 충돌 저항성의 3가지 기준을 충족해야 한다.

 

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

프리이미지 저항성(Preimage resistance 또는 역상 저항성)은 일방향 해시 함수의 보안성을 나타내는 지표 중 하나입니다. 이는 해시 함수의 입력값을 알고 있더라도 그 입력값을 생성하는 원본 데이터를 계산하기가 어렵다는 것을 의미합니다.

쉽게 말해, 일반적인 상황에서 해시 함수의 출력값을 알고 있다면, 그 출력값으로부터 원래 입력값을 찾아내기가 어렵다는 것입니다. 이는 해시 함수가 역함수를 가지지 않아 원래 데이터를 찾아내기가 매우 어렵기 때문입니다. 이러한 특징은 해시 함수가 암호학에서 중요한 역할을 하는 이유 중 하나입니다.

즉, 프리이미지 저항성은 해시 함수의 안전성을 나타내는 지표 중 하나이며, 이를 만족하는 함수는 안전하게 사용할 수 있습니다.

 

 

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

제2 프리이미지 저항성(Second preimage resistance)은 일방향 해시 함수의 보안성을 나타내는 또 다른 지표입니다. 이는 주어진 입력값에 대해 그 입력값과 다른 두 번째 입력값이 동일한 해시값을 가지는 것이 어렵다는 것을 의미합니다.

더 구체적으로, 주어진 입력값 x에 대한 해시값 h(x)가 주어졌을 때, h(x)와 동일한 해시값을 가지는 또 다른 입력값 y를 찾는 것이 어렵다는 것입니다. 즉, 일반적인 상황에서는 입력값 x와 다른 입력값 y가 주어졌을 때, h(x) = h(y)를 만족하는 것이 어렵다는 것입니다.

제2 프리이미지 저항성은 해시 함수의 안전성을 더욱 강화시키는 지표 중 하나이며, 이를 만족하는 함수는 안전하게 사용할 수 있습니다. 따라서 해시 함수를 선택할 때는 이러한 보안성 지표를 고려하여 적절한 함수를 선택해야 합니다.

 

 

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

충돌 저항성(Collision resistance), 충돌 회피성(Collision avoidance), 강한 충돌 내성(Strong collision resistance)은 일방향 해시 함수의 보안성을 나타내는 지표 중 하나입니다.

해시 함수는 입력값의 길이가 다양한 경우에도 고정된 길이의 출력값을 생성합니다. 이때, 서로 다른 입력값에 대해서도 동일한 출력값이 나타날 수 있는데, 이를 해시 충돌(Hash collision)이라고 합니다. 해시 충돌이 발생하는 경우 보안성에 문제가 생길 수 있으며, 따라서 충돌 저항성은 해시 함수의 안전성을 평가하는 중요한 지표 중 하나입니다.

충돌 저항성을 만족하는 해시 함수는 임의의 입력값에 대해 충돌이 발생할 확률이 매우 낮은 함수를 말합니다. 즉, 일반적으로 충돌을 찾는 것이 어려워야 합니다. 예를 들어, 128비트 출력값을 생성하는 SHA-256 해시 함수는 충돌 저항성을 만족하며, 임의의 입력값에 대해 충돌이 발생할 확률이 매우 낮습니다.

따라서 충돌 저항성은 일방향 해시 함수의 보안성을 평가하는 중요한 지표 중 하나이며, 안전한 암호화 시스템을 구현하기 위해서는 충돌 저항성이 높은 해시 함수를 사용해야 합니다.

 

 

 

 

 

4) 해시함수의 성질들 사이 관계

 

 

 

해시함수의 성질들 사이에는 다음과 같은 관계가 성립합니다.

• 충돌 저항성은 두 번째 역상 저항성을 보장합니다.
• 두 번째 역상 저항이 역상 저항을 보장하지 못하며, 역상 저항이 두 번째 역상 저항을 보장하지 못합니다.
• 충돌 저항성은 역상 저항성을 보장하지 않습니다.

 

 

 

 

 

 

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

1) SHA-512

- SHA-512 다중-블록 메시지로부터 512비트 다이제스트를 생성한다. 각 블록은 1024비트 길이를 가집니다.

 

2) SHA-512 길이 필드와 패딩

- 메시지 다이제스트를 생성하기 전에 SHA-512에서는 메시지에 추가적으로 덧붙이는 128비트의 부호 없는 정수 길이 필드가 필요합니다.

- 이 필드에는 메시지의 길이가 비트수로 표현된 값이 저장된다. 이 길이는 패딩을 하기 전의 원래 메시지 길이를 나타냅니다.

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

 

 

 

 

https://hey-stranger.tistory.com/162

[현대 암호학] 제 12장 - 암호학적 해시 함수

 

 

 

 

 

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

해시함수는 데이터의 무결성을 보장하지만 발신자의 신원 확인이 불가능하다. 이러한 문제를 해결하기 위해 인증 절차를 추가한 것이 메시지 인증 코드(MAC)이다.

 

1) 개념

■ 변경 감지 코드(MDC)

변경 감지 코드(MDC, Modification Detection Code)는 메시지의 무결성을 보장하는 다이제스트이다.

 

인증 과정

• Alice는 안전하지 않은 채널로 메시지 M을 Bob에게 전송
• Hash(M)으로 도출한 해시값 MDC를 안전한 채널로 전송
• Bob은 수신한 메시지를 해시 알고리즘을 통해 해시값 MDC' 도출
• Bob은 안전한 채널로 수신한 해시값 MDC과 계산한 해시값 MDC'를 비교
• 동일하다면 전달받은 메시지의 무결성이 입증됨

 

문제점

• 안전한 채널이 보장됨이 전제임
• 만약 해당 채널이 탈취된다면 메시지와 MDC 모두 위조될 수 있음

 

■ 메시지 인증 코드(MAC)

송ㆍ수신자 간 비밀키를 공유하는 것으로 안전한 채널이 확보되지 않아도 무결성과 전송자의 신원 인증을 가능하게 하는 방법

 

인증 과정

• 원본 메시지 M을 비밀키 K와 병합하여 해시 수행
• 여기서 만들어진 MAC과 메시지 M을 안전하지 않은 채널로 전송
• Bob은 수신한 메시지 M과 비밀키 K로 MAC'을 생성
• 수신한 MAC과 자신이 생성한 MAC'을 비교
• 동일하다면 전달받은 메시지의 무결성이 입증됨과 동시에 출원지가 Alice라 판단

 

문제점

• 송ㆍ수신자 간 비밀키를 공유해야 함
• 따라서 키 배송 문제가 발생

 

2) 종류

■  Nested MAC

MAC의 안전성을 높이기 위해 고안된 방법

 

• 동일한 해시함수로 두 단계 해시 과정을 거침
• 따라서 두 개의 키가 존재

 

 

생성 과정

• 송신자는 내부 MAC을 생성하기 위해 사용할 임시 비밀키를 생성합니다. 이때, 임시 비밀키는 바깥쪽 MAC의 출력값과 다른 값을 사용
• 송신자는 메시지에 대한 내부 MAC을 생성하기 위해 임시 비밀키를 이용하여 MAC을 생성
• 송신자는 바깥쪽 MAC을 생성하기 위해 바깥쪽 MAC의 비밀키를 이용하여 메시지와 내부 MAC 값을 결합하여 MAC을 생성
• 송신자는 메시지와 바깥쪽 MAC 값을 수신 측에게 전송
• 수신 측은 바깥쪽 MAC 값을 검증하고, 내부 MAC 값을 검증한다. 이때, 내부 MAC 값을 검증하기 위해서는 바깥쪽 MAC의 출력값을 이용하여 내부 MAC 생성에 사용된 임시 비밀키를 다시 생성함.

 

 

 

■  HMAC

NIST는 Nested MAC에 관한 표준인 FIPS 198을 제정

 

• Nested MAC에 패딩 요소 추가
• SHA1과 같은 일방향 해시함수 사용

 

생성 과정

• 메시지를 길이가 b비트인 N개의 블록으로 분리
• 비밀키 왼쪽에 0으로 된 열을 추가하여 b비트로 길이를 맞춤, 이때 패딩 이전의 비밀키 길이는 N비트 이상을 권장
• 이렇게 생성된 비밀키를 ipad(Input pad) 상수와 XOR 연산
• 결괏값을 N블록들 앞에 위치시켜 N+1개의 블록으로 만듦
• 블록을 해시함수에 대입하여 얻은 결과를 HMAC이라 한다
• n비트의 HMAC 왼쪽에 0을 패딩 하여 b비트로 만듦
• ipad와는 다른 상수 opad와 b비트로 패딩 한 비밀키를 XOR 연산
• 연산 결괏값과 b비트의 HMAC을 병합하여 해시 연산
• 최종적으로 n비트의 HMAC을 생성

 

■  CMAC

NIST표준 FIPS 113에 정의된 MAC으로써 대칭키 암호시스템의 CBC모드를 활용하는 방법

• 암호 블록체인과 동일한 알고리즘
• 이전 블록의 암호문과 입력값을 XOR 연산하는 방식

 

생성 과정

• 메시지 M을 m비트의 블록 N개로 나눔, 마지막 블록이 m비트가 아닐 시 첫 비트 = 1, 이후 비트 = 0으로 패딩
• 비밀키 K를 사용하여 첫 블록 M1을 암호화하여 M2와 XOR연산
• 해당 과정을 반복하여 수행
• 마지막 블록, 직전 암호문, 새로운 키 k를 XOR 연산
• 해당 결괏값의 왼쪽부터 n비트를 CMAC 값으로 활용

 

k 생성 알고리즘

• 0으로 이루어진 m비트의 블록을 비밀키 K로 암호화
• 패딩이 적용되지 않았을 경우 x를 곱함
• 패딩이 적용된 경우 x^2를 곱함

 

 

3) 활용 사례

■  IPsec

• IP(Internet Protocol)에 보안 기능을 추가한 것
• 통신 내용의 인증과 무결성 확인을 위해 사용

■  SSL/TLS

• 웹 통신 프로토콜
• 통신 내용의 인증과 무결성 확인을 위해 사용

 

4) MAC에 대한 공격

■ 재전송 공격

도청한 메시지와 MAC 값을 반복 송신하여 비정상적인 서비스 요청

 

• 순서 번호- 순서번호가 포함된 MAC을 계산하지 못하도록 하여 방지
• 타임스탬프- MAC값이 바르더라도 시간이 맞지 않다면 오류라고 판단하여 방지
• 비표(nonce) -일회용 랜덤값을 포함하여 MAC값을 계산하게 하여 재전송 공격을 방지

 

 

5) MAC으로 해결할 수 없는 문제

■ 제삼자에 대한 증명

• 공유키를 이용하므로 MAC값을 계산할 수 있는 것은 송ㆍ수신자뿐임
• 하지만 누가 MAC값을 계산했는지는 특정 불가
• 제삼자에게 MAC 값을 계산한 것이 누구인지 증명 불가
• 전자서명을 사용하면 제삼자에 대한 증명 가능

 

■ 부인 방지

• 송신자 Elice는 Bob에게 메시지를 보내지 않았다고 주장
• 해당 주장이 맞는지 확인이 불가하므로 부인방지 불가
• 전자서명을 이용하면 부인방지 가능

 

https://kaite-story.tistory.com/48

[정보보안기사 09] 메시지 인증 코드