해시 및 전자서명

1. 해시

일정 크기의 데이터를 정해진 고정된 길이의 짧은 값으로 변환하는 함수이다. 이 과정을 Message Digest라고 부른다.

날라온 해시랑 내가 계산한 해시값을 비교해서 데이터의 무결성을 확인하기 위한 목적으로 사용된다.

해시의 결과값에서 

암호화는 복호화가 되어야한다. 복호화가 안되면 의미가 없다.

하지만 해시는 결과값을 원래 값으로 복원하는 것이 목적이 아니라 형태 변환이 끝이다. 그래서 해시는 일방향성을 특징으로 가진다. 근본적으로 역연산이 되면 안된다.

예를 들어, 계좌의 패스워드가 그냥 들어가지 않고 해싱 후 저장되기 때문에 패스워드가 기억이 안나면 재설정 해야한다. 번호가 무엇이였는지 알 수 없다.

 

입력 메시지가 조금(1bit)이라도 다르면 해시값이 많이 달라져야 한다.

다른 입력을 넣었을 때 같은 값이 나오는 충돌이 전혀 없을 수는 없겠지만, 그런 일이 거의 없어야한다.

 

cost가 굉장히 낮아서 빠른 시간 안에 시간과 자원이 적게 들어야 효율적이다.

 

관련 용어들로는 다음 4가지가 있다.

해시함수 = Message Digest 함수

메시지 = 프리이미지

해시결과값 = Message Digest, fingerprint

무결성 = 완전성, 보전성

 

보안적으로 요구되는 3가지 사항이 있다.

1) Preimage resistance = Weak onewayness

   y=h(M) 에서 y와 h를 알아도 M을 찾기 굉장히 어려워야 한다. (절대 안되는 것은 아닌데 굉장히 어려워야 한다.

2) 2nd preimage resistance

   y=h(M) 에서 M을 알 때, 해시값이 똑같이 나오는 M과 다른 M'을 찾기 어려워야 한다.오직 하나의 M만 존재해야한다는 것이다.

근데 M을 안다면 그냥 M 넣어서 인증하면 되는데 왜 또 다른 M'을 찾는거지? 상황 자체가 이해가 안되는 듯.

   어차피 해싱값 밖에 모르기 때문에, 다른 메시지를 넣었을 때도 원래 M을 넣은 해싱값과 다르면 안된다.

3) Collision freeness

   h(M) = h(M')이 되는 (M,M') 쌍을 찾기 어려워야 한다. 이걸로 내부의 관리자가 일부는 M으로 하고, 일부는 M'으로 설정해두고 같은 해시값이니까 문제없게... 엥 왜 M으로 하고 M'으로 하고 이러는거지...? 대체 뭔 이득을 보려고?     ' 갑자기 내부부정?

 

해시의 종류

MD5

 

SHA-1 (Secure Hash Algorithm -1)

160bit의 결과가 나온다. MD5보다는 느리지만 조금 더 안전하다. 충돌문제가 있지만 그래도 잘 쓰이고 있다.

SHA-2 

현재 권고되고 있는 해시함수이다. SHA-256, SHA-384, SHA-512를 전부 포함한다. 뒤의 숫자는 결과 bit수이다.

SHA-3

차세대 해시함수로 2012년에 공모로 채택됐다.

 

해시의 목적은 무결성을 확인하기 위함이다.

원래의 메시지를 다른 형태로 바꿔서 보낸 해시값을 같이 보내서, 받은 이가 계산한 결과와 비교해 변조됐는지 확인할 수 있다.

 

파일에는 따로 문제가 없는 것을 확인했는데, 이걸 A가 보냈다는 것을 증명해주지는 않는다.

즉, 인증이 안된다.

 

그래서 등장한게 메시지 인증이다.

 

 

 

2. 메시지 인증

메시지 인증 Message Authentication은 MAC을 만들 때 필요한 키 통해 A한테서 온 것을 인증해준다.

받은 MAC과 계산한 MAC이 같은지 확인함을 통해, 키를 같이 공유한 사람이 맞다는 것을 알고 데이터의 무결성과 인증이 둘다 된다.

암호화와 다르게 원래의 정보와 추가적으로 보낸다는 점에서 해시함수와 같으나, 송수신자간 공유하는 키가 필요하다는 점에서 해시함수와 다르다. 

 

해시 함수를 통해 MAC을 계산하기도 한다.

SHA256을 사용한다. 

 

key, message가 입력값으로 들어간다.

block size보다 key가 길면 길이를 맞춰주고, 짧으면 key에 padding을 붙인다.

XOR 연산자를 활용한 i_key_pad와 o_key_pad 변수를 계산한 후 concatenate와 hash함수를 통해 MAC을 계산한다.

 

MAC이 무결성과 인증을 둘 다 보장해준다고 하지만 취약점은 존재한다.

안전한 방법으로 키를 공유해야 한다.

이전의 메시지를 새 메시지인 척

주문할 때마다 Sequence Number을 늘려서 메시지에 포함(저장해둔다)하여 MAC을 다른 값을 낸다던가,

주문할 때의 시간인 Time Stamp를 메시지에 포함하여 다른 MAC값을 낸다던가, 단, A와 B의 pc의 시간이 조금 다르다면, MAC을 복호화했을 때 수신자의 시간과 맞지 않는 경우가 생긴다. 

뭘 저장하기 싫을 때는 일용으로 랜덤 넘버인 Nonce를 메시지에 포함하여 넘기면 된다. 근데 또 문제가 Nonce도 들키면? 그리고 통신 프로토콜도 조금 달라져야해서 주고받는 횟수가 늘어나는게 또 문제이다.

사진

 

MAC의 취약점을 살펴봤는데 그냥 근본적인 문제는 뭘까? 전혀 해결이 안되는 문제 말이다.

제 3자에 대한 증명 불가

A와 B둘 다 똑같은 키를 공유하기 때문에 특정 문서를 A가 썼는지, B가 썼는지 제 3자에게 증명할 길이 없다.

부인 방지 불가

증명 불가와 비슷하다. 다만 A랑 B가 서로 안썼다고 부정하는 경우이다. 이 경우도 누가 썼는지 알 길이 없다.

 

 

 

3. 전자서명

나쁜놈이 A인척 다른 사람들에게 데이터를 보내는 것을 어떻게 막을 수 있을까? 그것도 MAC에서의 키배송문제 없이 말이다.

 

전자서명에서 일단 "서명"이라는 것은 필체와 도장으로 누가 썼는지를 기록하는 것이다.

컴퓨터상에서 이걸 어떻게 구현할 수 있을까?

 

사진

 

데이터 암호화할 때는 비대칭키를 잘 안 쓴다.

A 입장에서는 내가 보냈다는 것을 믿어줬으면 좋겠고, B 입장에서는 이게 A가 보냈다는 것을 믿고 싶은 상황이다.

그럼 A는 메시지의 해시값을 자신의 개인키로 암호화해서 보내면 (전자서명),

B는 (A에게 받은 공개키로 암호를 복호화한 해시값) = (메시지의 해시값)이면 A가 보냈음을 알 수 있다.

 

그럼 A는 plain text와 개인키로 암호화한 암호를 보낸다.

A가 마음이 바뀌어서 B한테 내가 보낸적 없어! 라고 하는 부인이 불가능하다. A의 공개키로 복호화할수 있는 것은 오직 A의 개인키로만 만들 수 있기 때문이다.

그럼 A가 보냈다는 인증, 부인방지, 무결성을 검증할 수는 있으나, BUT! 여기서 메시지의 기밀성은 보장되지 않는다.

예를 들어서 A가 '나 빵구쟁이임' 이라고 보내는 메시지가 A 챙피하게 그대로 전달된다는 것이다.

 

RSA 전자서명: A가 개인키로 암호화하면, B는 A의 공개키로 복호화한다.

ECC 전자서명: A가 횟수로 암호화하면, B는 최종 위치로 복호화한다.

 

전자서명. 좋지만, 이 또한 문제가 있다.

B가 받은 공개키가 진짜 A의 공개키인지를 증명할 방법이 없다. A가 아니라 나쁜놈이 공개키와 개인키 쌍을 만들어서 나 A야~라고 할 수도 있지 않나?

그래서 공개키 인증서(PKC, Public Key Certificate)을 통해 믿을만한 공개키를 제공한다. 믿을만한 기관(CA)에 의해 관리된다.

CA에 의해 관리되는 안전한 암호화와 전자서명 기능을 제공하는 보안환경을 공개키 기반구조 (Public Key Infrastructure)이라고 한다.

 

그래서 Certificate, 인증서가 뭐냐? 어떻게 사용하나?

상황은 A가 만든 콩개키가 A가 만든지 어떻게 아냐는 것이다.

Step 1. A가 공개키와 개인키 쌍을 생성하면 공개키를 인증기관(CA)에 등록을 하고, 이게 A의 공개키임을 전자서명한다.

Step 2. B가 인증기관(CA)으로부터 A의 인증서(A의 공개키+인증기관의 전자서명)를 내려받는다.

*근데 또 문제가 인증기관의 전자서명은 또 어떻게 검증받냐?

Step 3. 상위 인증기관의 전자서명을 포함한 인증기관의 인증서(인증기관의 공개키+상위인증기관의 전자서명)을 내려받는다.

* 근데 또 문제가 상위인증기관의 전자서명을 또 어떻게 검증받냐?

... 이걸 언제까지 해야되나. 끝이 없다. 그래서 이정도면 믿어주자 한다 (그게 우리나라에서는 KISA). 보통 2-3단계까지 간다.

 

A만 공개키와 개인키를 안다.

아까 말했던 공개키 인증서(PKC, Public Key Certificate)은 사용자의 공개키에 사용자 식별 정보를 추가하여 만든 신분증이다. 공개키와 소유자가 누구인지 저장되고, 

CA에 의해 전자서명하여 인증된다. 

인증서 버전, 인증기관의 일련번호, 인증서 발급할 때 사용한 서명알고리즘, 인증기관 이름, 유효기관, 소유자 이름, 소유자 공개키

가 전부 인증서에 저장된다. 이 모든 내용을 인증기관(CA)의 개인키로 서명하여 정당성이 부여된다.