(Fintech W-IOI #6-7) 암호학적 Hash 관수 | Digital 서명

 

 

 

 

 

• LAZE SOFTWARE의 [Hash계산 Tool]을 사용한다
  • SHA(Secure Hash Algorithm) Series의 출력을 봐보자
    • SHA Series는 Americal 국립 표준 기술연구소(NIST)에 의해 표준화된 암호학적 Hash 함수군이다
• [Hash치(Message Digest)]로 쓰고 있다
  • 암호학적 Hash 함수의 출력은 정식으로는 [Message Digest]라고 불린다
    • 수업에서는 가능한한 [Digest]라고 부른다

우선 시도해보자

 

• 암호화를 어떻게 파악하나?
  • 암호화는 정보를 부호화하는 Process로, 평문(원 Data)를 암호문으로 변환한다
  • 허가된 자(전형적으로는 열쇄의 소유자)만, 암호문을 복호하여 평문으로 돌려,
    원래의 정보에 Acess하는 것이 가능하다
  • 즉, [암호화 ↔ 복호]의 관계가 있다
• 암호학적 Hash 관수가 출력되는 것은 암호문이 아니다
  • 원래로 돌아갈 수 없다 ← 무슨 도움이 되나 ← 매우 도움된다

암호학적 Hash 관수는 암호화가 아니다

 

• File(Open Source의 App 등)이 진짜인지 확인하고 싶을 때,
  제공자는 File의 지문(Hash값 또는 Digest라고 함)을 공개할 수 있다(보통 16진수 표기)
  • Download한 사람도 같은 방식으로 Digest를 계산하고,
    그 값이 공개되어 있는 값과 같으면 진짜 File을 얻은 것이다. 
  • 가짜 File을 동일한 Digest로 위장하는 것은 매우 어려운 것으로 알려져 있습니다. 
• Digest는 암호학적 Hash 함수를 사용하여 계산됩니다.
  
  • SHA(Secure Hash Algorithm) Series로 대표되는 다양한 종류가 있습니다. 
• 암호학적 Hash 함수는 원래의 Data(원본)가 1 bit만 달라도 전혀 다른 값을 출력하는 함수입니다. 
  
  • 단방향성 : Digest에서 원형을 얻을 수 없습니다. 
  • 따라서 원본 Data를 감추기 위해 사용되기도 합니다. 
  • 무한을 유한으로 Mapping하기 때문에 결과가 충돌할 수 있음.

 

 

• SHA-1은 160bit의 Digest를 출력한다
• 2017년 2월, Google과 Netherland 국립 수학 통계기과학연구센터(CWI)가 발표
• 주의환기

SHA-1에서 실제로 충돌이 보여졌다

 

 

 

 

• 원상 계산 난이도 (Pre-Image Resistance) 
  • 출력 h가 주어졌을 때, h = H ( m )이 될 수 있는 m을 찾는 것이 어려움 
• 제 2 원상 계산 난이도 (약충돌 저항) (Second Pre-Image Resistance) 
  
  • 입력 m 1이 주어졌을 때, H ( m 1) = H ( m 2 )가 되는 m 2 (단, m 1 ≠ m 2 )를 찾기가 어렵다. 
• 단순한 Hash 함수(고정폭의 출력이 균일하게 분포하는)는 이를 만족시키지 못함.
  
  • [256으로 나눈 나머지]는 8bit 값을 반환하는 Hash함수이지만 . . .

암호학적 해시 함수 H가 만족해야 하는 특성

 

 

• 사실 256 bit의 공간을 Image 해보고 싶은데 . . . 
  
  • 너무 거대해서 . . . 
• 관측 가능한 우주의 지름은 일설에 의하면 8.8 × 10^23 km입니다.
  
  • 대략 10^(23+6) mm의 규모
• 한편, 160 bit Digest를 고려하면 1,000, 즉 103을 16번 곱하면 대략적으로 계산할 수 있습니다.
  
  • 최대값은 대략 10^(16×3)
• 우주의 직경이 10^29mm인 반면, 160 bit Digest는 10^48
  
  
• 즉, 충돌 가능성은 우주를 가로지르는 직선 위에 예를 들어 1밀리미터씩 점을 찍어서 두 점이 일치할 확률보다 훨씬 더 낮다는 뜻입니다.
  
  • 하지만 방심하지 말자, 상대는 컴퓨터다!

 

• 자신과 생일이 같은 사람은 거의 만나지 않지만, 지인들끼리 생일이 같은 조합은 무수히 많다.
• 어떤 사람이 모여 있는 방에 들어가서 자신과 같은 생일인 사람이 있을 확률이 50% 이상이 되려면 253명 이상이 필요
• 같은 생일인 두 사람이 있을 확률이 50% 이상이 되려면 23명만 있으면 OK
• 마찬가지로 특정 다이제스트와 충돌하는 데이터를 찾는 것은 어렵지만, 
  다이제스트가 충돌하는 두 개의 데이터를 찾는 것은 그보다 훨씬 쉽다.
• 다이제스트가 n bit인 경우, 2^(n/2) 회 정도의 시도로 충돌하는 Data를 찾을 수 있는 가능성이 높아진다.
• 따라서 160 bit Digest는 생일 공격에 대해 80 bit 강도를 가진다.
  
  • 깨진 SHA-1(160bit)은 어떻게 될까?

 

---

 

 

• 공개키부터 비밀키를 추측하는 것은 매우 곤란하는 것을 이용

공개키 암호계

 

 

Digital 서명(RSA로의 방법을 간단히 설명)

• 본인이 보낸 것이며 변조되지 않았음을 증명할 수 있습니다.
• 이 그림은 RSA의 방법(RSA : Rivest, Shamir, Adleman) ...하지만 사실 개인키는 복호화 키이기 때문에...
• 비트코인 등에서 사용되는 것은 ECDSA(타원곡선 DSA : Digital Signature Algorithm)로, 
  암호화-복호화 관계를 사용하지 않습니다.

 

 

 

• 사전 준비
  
  • User는 키 Pair<공개키, 비밀키>를 만들고, 비밀키는 비밀로 한다 ← 비밀키는 보통 암호화로 보호한다.
  • 공개키를 공개한다(적어도 검증자에게는 공개한다)
  • 공개키가 정말 본인의 것임을 확인할 수 있는 수단이 있다 ← 일반적으로 공개키 인증서를 사용한다.
• 서명
  
  • 입력 : < 평문, 비밀키 >
  • 출력 : 서명 Data
• 검증
  • 입력 : < 평문, 서명 데이터, 공개키 >
  • 출력 : OK (비밀키가 사용되었고 평문은 1 bit도 변하지 않은 것으로 추정) 또는 NG (그렇지 않음)
    
    • [서명 Data가 평문과 공개키를 사용하여 테스트할 수 있는 어떤 수학적 성질을 만족하는지] 확인합니다.
    • 이 검증 과정에서 비밀키를 사실상 추측할 수 없다.

 

 

• Web 세계 등에서는 공개키 Infrastructure가 이용되고 있습니다.
• 거기에는 Root(뿌리)가 존재합니다 ← 누군가를 무조건적으로 신뢰하고, CA는 고장 지점

 

 

 

 

• 일반적으로 공개키의 진위 여부는 CA가 발행한 공개키 인증서로 증명됩니다.
  • 공개키 인증서(이 또한 Digital 서명)는 유효기간이 있습니다. 왜냐하면...
• Digital 서명이 무의미해질 RISK
  
  • 1. 개인키가 유출될 수 있다.
  • 2. 서명 알고리즘이 오래되어 깨질 수 있다.(위조 가능)
  • 3. 공개키 인증서의 유효기간이 만료된다.
• 이러한 위험 때문에 과거의 서명을 검증 가능하게 유지하는 것은 어렵습니다.
• 블록체인은 이(↑) 문제를 극복할 수 있는 측면이 있습니다.