Hash Functions

Hash Function
= digest
= HASH

해시값(digest)는 unpredictable 하고 random하다

ex. SHA-256

Hash 함수의 속성

1. pre-image resistance: 해시 함수의 요소가 주어지면 아무도 그에 매핑되는 입력을 찾는 것이 불가능하다는 성질. 즉, one-wayness

주의할 점은, 너무 짧은 문장은 예측가능(predictable)할 수 있다!는 것

2. second pre-image resistance: 만약 input과 그것의 해시값(digest)가 있더라도, 같은 해시값을 내는 다른 input을 찾을 수 없다.(극도로 어렵다. 이론적으로는 가능함)

3. collision resistance: 아무도 똑같은 output을 해시하는 두 개의 다른 input을 만들 수 없다. 하나의 해시값(digest)에 대응하는 input값은 항상 하나이다

해시 함수는 입력 데이터를 '고정된 길이의 요약본'으로 바꿔주는 도구다.
주로 데이터를 검증/확인하는 데 사용한다.
해시 함수는 단독으로 사용되는 일이 거의 없다.
대부분 다른 암호학의 기초 또는 암호학 프로토콜과 결합하여 쓰인다.

몇 가지 예를 살펴보겠다.

1. Commitments

   • 상황: '나'는 주식이 다음달에 50달러가 될 거라는 사실을 알지만, 친구들에게 말할 수 없다. 어떻게 하면 친구들에게 내가 이 사실을 안다는 것을 알려줄 수 있을까?
   • 해결:
     1. "Stock X will reach $50 next month"를 해시로 변환한다
     2. 해시값을 친구들에게 준다
     3. 한달후, 원래 문장을 공개하고 친구들이 이를 다시 해싱하여 결과가 동일한지 확인하게 한다.
   • 목적: Hiding (해시만 보고선 어떤 문장인지 모른다) / Binding (한 번 정한 내용은 변경할 수 없다)

2. Subresource integrity(서브리소스 무결성)

   • 상황: 웹사이트들이 외부에서 javascript 파일을 가져오는데, 이 파일들은 누군가에 의해 조작될 가능성이 있다.
   • 해결: 웹페이지는 javascript 파일의 해시값(ex. SHA-256)을 포함한 태그를 사용한다. > 브라우저는 다운로드한 파일을 해시하고, 그 값이 해시와 일치하면 파일을 실행한다.
   • 효과: 파일이 변경되지 않았음을 보장해 악성 코드 방지

3. BitTorrent

   • 상황: 비트토렌트는 파일을 여러 사용자(peer) 사이에서 나누어 전송한다
   • 해결:
     1. 파일을 작은 조각들로 나누고 각각의 조각을 해시합니다.
     2. 조각의 해시값을 공유하여 파일의 신뢰성을 보장합니다.
     3. 피어는 각 조각의 해시를 검증한 후 파일을 재구성합니다.
   • 효과: 파일이 올바른 조각들로 구성되었는지 확인하고, 손상/변조 방지

4. Tor

   • 상황: Tor는 사용자가 익명으로 인터넷을 탐색할 수 있게 해줍니다. 또한, 추적이 어려운 "숨겨진 웹페이지"를 생성할 수 있습니다.
   • 해결: 숨겨진 웹페이지 주소는 페이지의 공개키를 해시한 값으로 만든다 > 사용자는 이 주소로 웹페이지의 공개키를 인증한다
   • 효과: 페이지가 진짜인지, 사칭이 아닌지 확인한다

표준화된 해시함수

CRC32 : 암호화 해시함수가 아님! 에러 감지 코드 함수이다. checksum과 같은 종류이다.

MD5 / SHA-1 : 해시함수이지만, 충돌된다고 판정나서 지금은 사용하지 않음

1. SHA-2 해시 함수
   Secure Hash Algorithm 2 (SHA-2) : 가장 많이 사용된 해시함수
   SHA-224, SHA-256, SHA-384, SHA-512 : 224, 256, 384, 512 비트를 출력하는 4가지 다른 버전
   SHA-512/224, SHA-512/256 : SHA-512의 결과를 224 bit, 256 bit로 잘라 출력
   현재 가장 많이 사용하는 SHA-2함수 : SHA-256 (세가지 보안 속성에 필요한 최소 128 bit를 제공함)

2. SHA-3 해시 함수
   이전의 3가지 보안 속성()을 준수하다
   length-extension 공격에 강하다.
   secrets을 해시하는데 사용할 수 있다
   SHA-3-224, SHA-3-256, SHA-3-384, SHA-3-512

3. SHAKE, cSHAKE (XOF)

4. TupleHash

이 네 개의 표준화된 해시함수는 아래에 설명하도록 하겠다.

SHA-2 hash function

Merkle–Damgård construction

압축 함수를 반복적으로 호출하여 message를 해시하는 알고리즘.

step 1. 압축 함수에 맞도록 padding을 추가한다.
(padding을 추가했을 때 블록 크기의 배수가 되도록 한다. padding된 input을 자르면 압축함수의 첫번째 인수에 맞추게 된다)

step 2. 첫 번째 압축 함수의 출력을 사용해 메세지 블록을 다시 적용한다. 이것을 반복하면, 마지막 출력은 digest가 된다.

이것은 SHA-2가 동작하는 방법이다.

Merkle–Damgård construction는 압축기능이 충돌에 강하다(collision restistant)고 증명되었다.

WARNING > SHA-2는 해시함수가 사용하기 좋긴하지만, hashing secrets에는 적절하지 않다. 이는 Merkle–Damgård construction의 단점 때문인데, 그 단점은 secrets을 해시하는 데에 사용하면 SHA-2를 (length-extension) 공격에 취약해진다는 점이다.

SHA-3 hash function

permutation(순서를 바꾸는 작업)을 사용했다.

permutation은 가역성이다 = 결과를 보면 어떤 입력이었는지 충분히 알 수 있다.

SHA-3과 Sponge Construction
SHA-3은 데이터를 안전하게 처리하기 위해 설계된 해시 알고리즘이다
기존의 해시 구조(Merkle–Damgård)와 다르게, 스펀지 구조라는 새로운 방식을 사용한다

1. Absorbing phase: 입력 데이터를 부분적으로 처리한다
2. Squeezing phase: 해시 결과를 생성한다

keccak-f permutation
스펀지 구조에서 중요한 역할을 한다

• 특정 크기의 입력 데이터를 받아, 동일한 크기의 출력을 생성한다
• 이를 반복하여 해시값을 만들어낸다

Merkle–Damgård construction을 사용한 기존의 해시 알고리즘(SHA-1, SHA-2 등)과 달리, Sponge construction을 사용하여 암호화의 유연성과 안전성을 높였다.

즉,

• 데이터 처리 방식: Sponge Construction
• 변환 작업: keccak-f permutation

SHAKE, cSHAKE

확장된 출력 함수(extendable output function || XOF)

암호학에서는 하나의 암호학적 primitive(ex. hash function)를 서로 다른 목적에 사용할 경우, 같은 키를 재사용하거나 도메인 분리를 하지 않으면 보안 문제가 생길 수 있다

cSHAKE는 맞춤화 기능으로 특정 요구에 맞는 출력을 생성할 수 있다.

TupleHash

TupleHash로 모호한 해싱을 방지할 수 있다

cSHAKE에 기반하고, cSHAKE와 동일한 표준으로 지정됐다

Hashing Password

비밀번호를 웹사이트에 저장하려면 어떤 방법을 써야 할까?
평문을 그대로 DB에 저장하는 것은 바보같은 짓일 것이다. 공격당하거나 정보가 노출당했을 때 비밀번호가 그대로 노출되면 웹사이트의 평판이 추락할 것이다.

그럼 어떻게 해야할까? 이상적으로는 비밀번호를 해시하고 digest만 저장하는 방법이있다.

그러나 이 방법도 두 가지 문제가 있다.

1. 공격자가 해시된 비밀번호를 brute force attack이나 exhaustive search(가능한 모든 비밀번호를 대입하는 방법)를 시도할 수 있다.
2. Hash function은 빠르다. 공격자는 이를 이용해 brute force(초당 수많은 비밀번호를 대입하는 방법)를 할 수 있다.

이러한 공격을 늦추는 매커니즘이 있어야 한다!

1번째 문제는 salts를 사용해 해결한다. 각 사용자마다 public하고 다른 랜덤의 값이다. 해싱할 때 사용자의 비밀번호와 salt를 사용하는데, 이것은 cSHAKE에서 사용자별 사용자 지정 문자열을 사용하는 것과 같다.

2번째 문제는 느리게 설계된 password hashes를 사용해 해결된다. 현재 가장 최첨단의 선택은 Argon2로 Password Hashing Competition의 우승자이며, 2021년에 RFC로 표준화되었다.
PBKDF2, bcrypt, scrypt같은 비표준 알고리즘도 사용되곤 한다.