[ 컴퓨터 보안 ] 13. Cryptography : Asymmetric Key - Message Digest

Message Digest

: Hash 함수를 통해 Message 를 Unique하게 나타낼 수 있다.

* Message의 지문같은 것이라고 생각하면 된다.

 

➡️ For Data Integrity 

 

( 계약서 - 날인 ) 느낌으로

( Document - Digest ) 개념을 생각할 수 있다.

 

하나의 계약서에 도장을 서로 겹쳐서 찍어 서로의 것을 대조하여 달라진 게 없는지 확인할 수 있듯이

Message에 대해서 ( 받은 Digest )와 ( 내가 받은 Message를 Digest했을 때 )를 비교해서 확인할 수 있다.

 

---

 

📌 작동 개념

 

7391743이라는 숫자의 데이터를 Digest 시킨다고 생각하자

우리가 만든 함수에서 쓰이는 매커니즘은 다음과 같다.

 

초기 세팅 : 두 개의 값을 곱한다.

   ➡️ 십의 자리가 넘냐?

          > 넘음 : 십의 자리 수를 뺀다.

          > 안 넘음 : 그 다음 숫자 하나 가져와서 또 곱함

 

그렇게 마지막까지 돌린 다음에 나온 일의 자리 숫자가 Digest

앞에 두 개 곱합
가장 앞자리 수 버림
그 다음 숫자 곱함
그 다음 숫자 곱함
또 곱함
==> 10의 자리수가 넘는다?
10의 자리수 버림
다음 거 곱
...반복

끝났을 때 나오는 값이 Digest값

이 예시같은 경우에는 다른 meesage도 
같은 값이 나올 수 있다.

 

단, 이런 경우에는 

서로 다른 Message M , M' 에 대해서 같은 Digest값이 나올 수도 있다.

 

무튼 그냥 두 개만 알아두면 됨

 

   주어진 메시지(데이터)를 가지고 막 섞어서 하는 거다.

+ 다른 메시지어도 같은 Digest값이 나올 수도 있다 ( Weak Hash algorithm 인 경우 )

 

 

---

📌 Requirements

1. 받은 Message에 상응하는 Digest 를 찾을 수 있어야 한다.

➡️우리가 Message를 받았으면, 이를 가지고 Digest를 만들 수 있어야 한다.

 

 

2. Digest를 가지고 Original Message를 찾는 것은 어려워야한다.

➡️ Digest를 가진 상태에서 원본 Message를 찾기가 쉬우면 언제든지 공격받기 쉬워진다.

 

3. 같은 Message를 넣으면 항상 같은 Digest가 나와야 한다.

 

➡️ 하나의 Message에 대해서 Digest는 항상 같게 나와야 한다.

 

 

4. 두 개의 다른 메시지가 주어졌을 땐, 두 개의 Digest는 다르게 나와야 한다.

➡️ 다른 Message에 대해서는 어떻게든 다른 Digest가 나와야 한다. 

 

 

원본 Message가 조금만 달라져도, Digest는 극단적으로 바뀐다.

 

---

Hash

h = H(M)

H() = Hash 알고리즘

M   = 원본 Message

 

* Input에 대해 Secret Key 없이 그냥 Message만 넣으면 된다.

 

 

 

📌 Requirements

- Variable input size : 들어오는 양이 어떻든 Hash 함수에 적용 가능해야함

- Fixed output size   : 결과로 나오는 값은 결과가 고정되어 있음

- Efficiency

 

- ⭐️⭐️ Preimage Resistant (One-way Property) : 단방향이어야 함 ⭐️⭐️

  ➡️ Digest가 주어졌을 때, 이를 가지고 반대로 Original Message를 찾는 것이 불가능 해야한다.

 

이브가 h(M)값을 훔쳐가서 값을 알아낸 뒤에

해당 h(M)과 같은 M'을 만들어내어

그걸 M 내용인 것처럼 보낼 수 있다.

 

ex) M = Alice 계좌로 30만원 보내줘 , h(M) = 가나다라

      M' = Eve 계좌로 1000만원 보내줘, h(M') = 가나다라

      

 

---

- ⭐️⭐️ Second Preimage Resistant (Weak Collision Resistant) : 다른 Message면 Digest도 달라야함 ⭐️⭐️

  ➡️ x 라는 block 이 주어졌을 때, 같은 Block이 아니면, Digest도 같을 수 없다. 

      = 서로 다른 Message라면, 서로 다른 Digest를 가지고 있어야 한다.

 

 

다른 메시지는 다른 Digest 값을 만들어 내야함

 

 

 

- ⭐️⭐️ Collision Resistant (Strong Collision Resistant) : Hash 한 결과가 같은 두 쌍을 찾는 것이 불가능해야함

  ➡️ 같은 Digest 결과를 가지는 Message Pair를 찾는 것이 불가능해야한다.

     => H(x) = H(y) 를 가지는 (x,y) 쌍을 찾는 것이 불가능해야함 

 

 

공격자가 같은 Digest를 만드는 쌍을 찾을 수 없어야 한다.

 

---

Interated Hash Function

: Hash function 은 Interation 으로 만드는 게 가장 깔끔하다.

 

 

 

📌 Merkel- Damgard

 

Fixed length를 만들기 위해 Padding을 추가한다.

전체 메시지를 n비트씩 쪼개서 Compression function에 넣는다.
(여기에 Initial vector처럼 H0이 있음)

그렇게 시행한 결과를 그 다음 H1으로 하여 Input으로 사용

Output이 다음 실행에 Input이 됨 

 

 

---

 

근데 저 안에 있는 Compression Function 에서

Hash function 에 대한 방법이 많다.

 

1. Scratch가 있고

2. Block Cipher 방식이 있다.

 

 

📌 Block Cipher

 

- Compression Function = Encryption Cipher로 바뀜

- 앞 Stage의 Cipher Text ➡️ 다음 Stage의 Plain Text (Input)

- 입력된 n bits의 Block이 하나의 Key가 된다.

 

 

 

📌 Whirlpool

 

- 얘네는 n bits로 된 Block을 Plain Text(Input) 으로 받는다.

- 이전 Stage의 Cipher Text = 이를 XOR 시킨 값을 Key로 사용한다. 

- 이거 병렬로 가능한가??? 알아보기

 

 

 

 

 

(출처)

한동대학교 고윤민교수님 - 컴퓨터 보안