10. Hash Functions

Hash Functions

해시 함수는 임의의 메시지를 정해진 크기로 응축한다.

h = H(M)

해시는 메시지의 변동을 감지하는데 사용된다. 약간의 변화로도 아예 다른 결과가 나오기 때문이다.

단방향 속성을 가졌기에 해시 값에서 원본 데이터를 복구하는 것은 불가능하다.

또 서로 다른 두 메시지가 같은 해시 값을 가질 확률이 매우 낮아야 한다.

 

데이터 검증 방법으로 송신자가 데이터를 해시한 값을 뒤에 붙이고 수신자가 받은 데이터를 해시한 값과 대비해보는 방법을 생각해볼 수 있지만, 이는 man in the middle attack에 취약하다.

 

 

Message Authentication Code

MAC는 키 해시 함수로도 알려져 있다.

비밀 키와 데이터 블록을 입력으로 받고 해시 값(MAC)을 생성한다. MAC는 보호되는 메시지와 연관이 있다.

MAC의 주요 목적은 두 당사자 사이에 교환되는 정보의 진위를 인증한다. 두 당사자는 서로 공유하는 비밀 키를 사용하고, MAC는 데이터의 무결성과 출처의 인증을 보장하는데 사용된다. 즉 데이터가 전송 중 변경되지 않았고 올바른 출처에서 보낸 것임을 확인할 수 있다.

 

 

디지털 서명은 MAC와 유사하게 작동하지만, 몇 가지 중요한 차이점이 있다.

1. 먼저 메시지의 해시 값이 생성되고 개인키로 암호화한다. 이 암호화된 해시 값이 디지털 서명이다.

2. 수신자는 발신자의 공개 키를 사용하여 디지털 서명은 복호화한다. 그 이후 복호화된 해시 값을 메시지의 해시 값과 비교하여 무결성을 검증한다.

 

메시지 M은 해시함수를 통해 해시값 H(M)으로 변환되고 E_PRa로 암호화되어, 디지털 서명 E(PRa, H(M))이 생성된다.

M과 디지털 서명은 목적지 B로 전송되고, 수신자 B는 메시지를 해시한 값과 디지털 서명을 복호화한 값과 비교하여 무결성을 확인한다.

 

메시지 M와 디지털 서명 E(PRa, H(M))을 패키지한 데이터를 K로 암호화하여, E(K, [M || E(PRa, H(M))])이 만들어진다.

수신자 B는 받은 데이터를 K로 복호화하고, 위에서와 같이 무결성을 확인한다.

 

 

해시함수는 이 밖에도 단방향 패스워드 파일을 생성(실제 비밀번호를 해시화해서 저장), 침입 탐지 및 바이러스 탐지를 위한 무결성 확인, 유사난수 함수(PRF)와 유사난수 생성기(PRNG)에서 사용될 수 있다.

 

해시함수가 충족해야 하는건 다음과 같다.

Requirement		Description
변수 입력 크기	해시 함수 H는 어떤 크기의 데이터 블록에도 적용될 수 있어야 한다.
고정 출력 크기	H는 고정된 길이의 출력을 생성한다.
효율성	주어진 입력 x에 대해 H(x)를 계산하는 것은 상대적으로 쉬워야하고 효율적이여야 한다.
원상태 이미지 저항성 (단방향성)	주어진 해시 값 h에 대해 해당하는 원래의 입력 y를 찾는 것은 불가능해야 한다.
2차 원상태 이미지 저항성	원본 입력값 x에 대해 같은 해시를 갖는 다른 입력 y를 찾는 것이 불가능해야한다.
충돌 저항성	두 개의 서로 다른 입력 x와 y에 대해 H(x) = H(y)를 생성하는 것은 불가능해야한다.
유사랜덤성	H의 출력은 유사랜덤성에 대한 표준 테스트를 만족해야한다.

 

 

 

Attacks on Hash Functions

1. Premage Attack

주어진 해시 값에 대응하는 입력값 y를 찾아낸다. 해시 함수의 단방향성을 무력화시킨다.

 

2. Second Premage Attack

주어진 입력 x에 대해 H(x)와 같은 해시 값을 생성하는 또 다른 y를 찾는다.

원본 문서와 해시가 같은 위조 문서를 만들어내는 것과 관련이 있다.

 

3. Collision Attack

두 개의 서로 다른 메시지 x와 y를 찾아내어 H(x) = H(y)를 만든다.

해시 함수의 충돌 저항성을 깨뜨려는 시도로, 해시 함수가 서로 다른 두 입력에 대해 동일한 출력을 생성하지 않아야 한다는 원칙을 위배시킨다.

128bit hash는 이론상 2^64번의 시도로 충돌을 찾을 수 있기에 현재는 불안전하다.

160bit hash는 2^80번의 시도가 필요하고 더 안전하지만 이것도 미래에는 취약해질 수 있다.

현재는 대부분 256bit 해시함수를 사용한다.

 

3-1. Birthday Attack

생일 문제라는 확률 이론의 패러독스를 기반으로 한다. 생일 문제란 무작위로 선택된 사람들의 집단에서 두 사람이 같은 생일을 갖게 될 확률이 의외로 높다는 것을 말한다. 이 문제에 적용시키면, 해시 공간의 크기에 따라 예상보다 적은 수의 시도로 두 개의 다른 입력이 같은 해시 값을 갖게 될 확률이 높다는 것을 의미한다.

 

먼저 사용자가 유효한 메시지 x에 서명할 준비가 되어 있다고 가정하자.

공격자는 x의 변형된 버전 x'을 2^(m/2)개 만들어내며 모두 본질적으로 같은 의미를 가진다.

공격자는 사기성 메시지 y의 변형된 버전 y'을 또 다른 2^(m/2)개 생성한다.

두 세트의 메시지를 비교하여 동일한 해시 값을 갖는 한 쌍을 찾는다. 생일 문제에 따르면 이러한 쌍을 찾을 확률은 0.5 이상이다.

 

 

Secure Hash Algorithm - SHA

SHA는 미국 국립표줄기술연구소 NIST와 국가안보국 NSA에 의해 설계된 해시 함수들의 집합이다.

SHA-1은 160bit 해시 값을 생성하고, 이가 덜 안전한 것으로 간주되어 SHA-2를 사용하게 되었다. (SHA-256, SHA-512 등). SHA-3은 Keccak 알고리즘을 기반으로 한다.

 

 

SHA-2는 SHA-256, SHA-384, SHA-512가 존재한다.

이 알고리즘들은 각각 다른 비트 길이의 메시지 다이제스트를 생성하고, 각기 다른 보안 수준과 성능 특성을 제공한다. SHA-1에 비해 해시 값이 더 길고, 복잡한 연산을 더 많이 수행하여 보안을 강화한다.

SHA-2는 AES와의 호환성을 염두에 두고 설계되었고, AES가 제공하는 높은 보안 수준에 부합하도록 만들어졌다.

머클-담가드 구조를 사용한다.

 

IV, CV_0 (initial value)은 해시 계산의 시작점으로 사용되는 초기 고정 값이다.

CV_i (chaning value)는 각 단계에서 계산되는 중간 값으로, 이전 단계의 결과가 다음 단계의 입력으로 사용된다.

Y_i (i th input block)는 처리되는 원본 메시지를 블록 단위로 나눈 것으로, 각 블록은 b비트의 길이를 갖는다.

f (compression algorithm)는 입력 블록과 이전의 체이닝 변수를 받아 새로운 체이닝 변수를 생성하는 압축 변수이다.

L은 입력 데이터를 나눈 총 블록 수를 나타낸다.

n은 생성된 해시 코드의 길이이다.

b는 각 입력 블록의 길이이다.

 

해시함수는 메시지의 각 블록을 순차적으로 처리하고, 각 단계에서 이전 단계의 결과를 체이닝하며 마지막 블록이 처리된 후 최종 해시 값 CV_L을 생성한다.

 

 

위 그림은 SHA-512를 나타낸 것이다.

메시지의 뒤에는 1로 시작하는 패딩이 붙고 그 뒤에는 원래 메시지의 길이 L을 나타내는 128bit의 블록이 추가된다. 메시지 + 패딩 + L은 1024의 배수이다.

각각의 블록 M_i는 응축함수 F에 의해 처리되고, F(M_i)는 체이닝 값과 word 단위로 mod 2^64에서 덧셈을 수행한다. 이 값은 다음 연산에서의 체이닝 값이 된다.

이렇게 마지막 블록 M_n에 대하여 처리를 해주면 그 값이 해시 값이 된다.

 

 

SHA-3은 케책 알고리즘을 사용한 해시 알고리즘으로, SHA-2를 보완하는 것을 목적으로 한다.

SHA-2가 머클-담가드 구조를 기반으로 하는 반면, SHA-3는 스폰지 구조를 사용한다. 이 구조는 데이터를 "흡수 단계"에서 입력하여 변환한 후, "짜내기 단계"에서 해시 값을 출력한다.

이러한 설계 덕에 SHA-2와는 독립적인 보안 속성을 갖고 있고, 다양한 길이의 출력을 효율적으로 생성한다.

 

흡수 단계는 입력 메시지가 비트레이트 크기 r의 블록으로 나눠지고, 각 블록은 내부 함수 f에 의해 처리된다. 각 블록이 처리될 때마다 블록의 데이터는 현재의 내부 상태와 결합되어 상태를 업데이트한다.

 

짜내기 단계는 내부 상태가 모든 입력 데이터로 업데이트되면 해시 출력이 필요한 길이에 도달할 때까지 내부 상태의 비트레이트 부분이 출력으로 제공된다. 필요에 따라 내부 함수 f가 추가적으로 적용되어 더 많은 출력 데이터를 생성할 수도 있다.

 

 

메시지는 r bit 단위로 쪼개진다. 마지막 r bit보다 작은 부분이 있다면, padding을 채운다.

Z0, Z1, ... , Zj-1 은 해시 함수의 출력 블록을 나타낸다.

출력은 메시지의 해시 값을 나타내는데, 이는 해시 함수의 스펙에 따라 필요한 길이로 조정된다.

 

r bit는 비트레이트, c bit는 용량(capacity)을 나타낸다. b bit는 블록의 총 크기를 나타낸다.

여기서 용량은 보안 수준을 결정하는 내부 상태의 부분으로, 외부로 노출되지 않고 내부에서만 유지된다. 이 부분은 공격자가 해시 함수의 출력을 예측하거나 변조하는 것을 더 어렵게 만든다.

 

흡수 단계에서는, r비트의 블록 P0, P1, ... Pk-1으로 나뉜다.

각 블록은 0^c (c 비트의 0으로 이뤄진 문자열)와 함께 내부 함수 f로 전달된다.

내부 함수 f에 메시지 블록과 현재 상태를 XOR 연산하여 입력으로 들어가, 내부 상태 s를 업데이트한다.

맨 처음의 상태는 0으로 채워져 있다.

 

짜내기 단계에서는, 내부 상태 s에서 r bit의 데이터를 추출하여 해시 출력 Z0, Z1, ... 을 생성한다.

데이터를 추출할 때마다 내부 상태 s에 f를 적용시켜 추가 상태 s를 처리한다.