[Crypto] Dreamhack STAGE 5

https://dreamhack.io/lecture/roadmaps/3

Cryptography

---

[ Crypto stage5: Hash ]

 

* 해시 함수(Hash Function)

- 임의 크기의 데이터를 입력으로 받아서, 고정된 크기의 데이터를 반환하는 함수

- 해시 함수의 반환값은 해시 값(hash value)라고 부름

- 암호학적 해시 함수는(cryptographic hash function) 해시 함수 중에서 특정 성질을 만족하는 함수를 의미

 

* 암호학적 해시 함수의 성질

 1. 제 1 역상 저항성(preimage resistance)

    → 암호학적 해시 함수 H에 대해 y가 주어졌을 때 H(x) = y를 만족하는 x를 찾는 것이 어렵다.

    → 함수가 일방향 함수여야 함을 의미

 2. 제2 역상 저항성(second preimage resistance)

    → 암호학적 해시 함수 H에 대해 x가 주어졌을 때 x != x’, H(x)=H(x’)을 만족하는 x’을 찾는 것이 어렵다.

 3. 충돌 저항성(collision resistance)

    → 암호학적 해시 함수 H에 대해 x != x’, H(x)=H(x’)을 만족하는 x, x’을 찾는 것이 어렵다

    → 추가로, 현대에서는 눈사태 효과(acalanche effect)를 이상적인 해시 함수의 조건 중 하나로 보기도 함.

          이 성질은 대칭키 암호 시스템의 확산과 비슷하게 입력에 조그만 변화가 발생하면, 해시값에도 큰 변화가 발생하는

          성질임

 

* 일방향함수(one-way function)

→ 임의의 인자에 대한 함숫값은 쉽게 계산할 수 있지만, 함수 값으로부터 함수의 인자를 알아내기 어려운 함수

 

* 생일 역설(birthday paradox)

→ 암호학적 해시 함수의 충돌 저항성과 관련된 이론 중 하나

→ 일반적인 직관과 다르게 전체 인원이 적어도, 그 안에 생일이 같은 학생이 높은 확률로 존재하는 현상

→ 공역의 크기가 365인 해시 함수 H가 있을 때, H에 대해 무작위로 30개의 해시값을 생성하면 충돌이 발생할 확률이

       70% 이상인 것으로 재해석될 수 있음

→ 아무리 정교한 해시 함수를 만들더라도, 공역의 크기가 작으면 해시 함수는 충돌 저항성을 만족하기 어려움

 

* 암호학적 해시 함수의 사용

 1. 어떤 통신의 무결성을 보이기 위해 사용

   - 무결성(integrity): 수신한 데이터가 원본과 같을 때, 이 데이터는 무결하며, 데이터가 무결하게 송수신되는 성질의

      통신

   - 송신자가 데이터와 함께 데이터의 해시 값을 보내면, 수신자는 받은 데이터로부터 해시값을 생성하고, 이를 송신자가

      보낸 해시값과 비교하여 받은 데이터가 변조되지 않았는지 확인할 수 있음

 

  2. 민감한 데이터를 보관할 때 사용

    - 비밀번호를 해시 값으로 저장하면 데이터베이스가 유출되어도 비밀번호의 원본이 알려질 가능성이 거의 없음

    - 사용자를 인증할 때는 사용자가 입력한 비밀번호의 해시 값을 저장한 해시 값과 비교

 

 

[해시함수의 종류]

* MD5

 - 임의 입력으로부터 128비트(=16바이트)의 값을 생성하는 함수

 - 임의 길이의 입력을 블록 암호와 비슷하게 512비트 단위로 쪼갠 후 연산을 거쳐 값을 생성

 

* SHA256

  - 미국 표준 기술 연구소(NIST)에서 만들어낸 해시 함수

  - 현재까지 취약점이 발견되지 않아 해시가 필요한 대부분의 곳에서 사용되고 있음

  - 256비트(=32바이트)의 출력을 내는 함수

  - MD5에 비해 길이가 2배로 늘어나 충돌 저항성이 크게 증가함

 

* MAC(Message Authentication Code, 메시지 인증 코드)

  - MAC은 데이터와 함께 보내는 추가적인 정보

  - MAC을 통해 데이터의 무결성을 보장할 수 있고, 현재 통신 중인 상대방이 위장한 공격자가 아니라는 사실 또한

     알아낼 수 있음

  - MAC을 만들기 위해서는 메시지와 키가 필요하며, 이때 키는 송신자와 수신자 사이에서 사전에 공유되어야 함

 

 1. 송신자는 수신자에게 메시지를 보낼 때, 메시지와 키를 이용해 계산된 MAC 값을 같이 보냄

 2. 수신자는 기존에 알고 있던 키를 이용해 수신한 메시지의 MAC을 계산하고, 이를 전송받은 MAC과 일치하는지 비교

 

→ 공격자가 메시지를 위조하기 위해서는 위조된 메시지에 대한 올바른 MAC값을 알아야 하는데,

      키를 모르는 공격자는 MAC 값을 계산할 수 없음

 

* HMAC

 - 해시 함수를 기반으로 하는 MAC

→ HMAC을 사용하면 메시지를 도청당해도 역상 저항성으로 인해 공격자가 HMAC에 사용된 키를 알아낼 수 없으며, 메시지를 위조하면 위조한 메시지에 대한 올바른 HMAC을 생성할 수 없음