암호 기초

목차

• 보안 기본 개념
• 암호학적 해시 함수
• 대칭키 암호 시스템
• 메시지 인증 코드
• 공개키 암호 시스템
• 개체 인증
• 키 관리 시스템
• 네트워크 보안

 

이하 내용은 암호의 기본적인 개념은 모두 알고 있다고 가정하고 진행한 강의 내용이다.

 

보안 기본 개념

정보보호의 목표

• 기밀성
  • 허가 되지 않은 사용자가 정보의 내용을 알 수 없도록 함
• 무결성
  • 허가 되지 않은 사용자가 정보를 함부로 수정할 수 없도록 함
• 가용성
  • 허가된 사용자가 정보에 접근하려 하고자 할 때, 이것이 방해받지 않도록 함
• 인증
  • 허가되지 않은 사용자인지 허가된 사용자인지 구분할 수 있도록 함
• 책임성
  • 정보보호사고 발생시, 사고의 원인을 파악할 수 있어야 함

 

 

암호 시스템의 안전성

• 공격 모델
  • 암호문 단독 공격 (COA)
  • 알려진 평문 공격 (KPA)
  • 선택된 평문 공격 (CPA)
  • 선택된 암호문 공격 (CCA)
    • CTR, CBC 는 해당 공격에 안전하지 않은 것으로 알려져 있음
      • TLS 1.2 이후부터는 사용하지 않음
• 안전한 암호란?
  • 키를 잘 관리해야 함
  • 키를 모른다 하더라도 암호문의 1bit 의 정보도 알 수 없다.
• Perfect Secrecy
  • 두 개의 같은 길이의 암호문이 주어졌을 때, 각 암호문의 분포가 동일하다. 암호문 보고 어떠한 평문이 암호화 됐는지를 구분할 수 없다.
  • 예시
    • One Time Pad
      • True random generator 에서 추출된 key
      • key 는 한번만 사용됨
      • 단점
        • 비실용적
          • 평문과 같은 길이의 key 를 사용해야 하지만, 긴 평문의 경우에는 매번 생성하기에는 현실적으로 어렵다.
• Semantic Security (=Indistinguishability (IND))
  • 공격자가 암호화하는 알고리즘한테 물어보는 테스트를 통과하면 안전하다
    • 유리하게 공격자한테 환경을 주는 것
      • • 평문 2개를 선택할 수 있는 권한을 줌 (단, 길이는 같게)
  • 랜덤하게 생성한 (50% 확률로) 암호문을 공격자가 1/2 보다 높은 확률로 맞출 수 있으면 안전하지 않다.
  • (adaptive IND-CPA)
    • 공격자한테 m0, m1 을 선택해서 던져볼 수 있다. 암호화 oracle 만 권한을 주는 것임
    • Challenge 에 사용된 메시지를 다시 test (encrytion oracle 에 쿼리) 할 수 있음
  • (adaptive IND-CCA)
    • 공격자는 Challenge 에 대한 응답 메시지를 test (decryption oracle 에 쿼리) 할 수 없음

 

암호학적 해시 함수

메시지 무결성

• 원본 메시지의 변조를 방지하기 위한 서비스
• 대칭키 & 공개키 암호시스템은 기밀성을 제공
• 무결성을 위해 Modification Detection Code (MDC) 사용
  • 변조 감지 코드를 생성하기 위한 방법으로 암호학적 해시 함수 사용

 

암호학적 해시 함수

• 데이터의 무결성을 제공하기 위해 사용됨
• $ h = H(M) $
  • 임의의 크기의 데이터 입력
  • 고정된 크기의 출력
• What is a one-way function (f)
  • x 로 f (x) 를 구하는 것은 쉽지만, f(x) 로 x 를 구하는 것은 어렵다.
• output space 가 작기 때문에 충돌이 발생할 수 밖에 없다.
• 안전한 해시 함수의 3가지 성질
  • 역상 저항성
    • 역함수로 preimage 를 구하기 어렵다
  • 제 2 역상 저항성
    • x 를 주었을 때, 해시가 같은 또 다른 y 를 찾기 어렵다
  • 충돌 저항성
    • 충돌하는 임의의 쌍 x, y 를 찾기 어렵다
    • 충돌 저항성을 깨는 것이 가장 쉽다.
      • 생각보다 많이 발생한다는 것이 Birthday paradox 이다.
        • 방에 23 명이 있을 때, 생일이 같은 2사람을 찾는 것이 약 50% 확률이다.
        • h(x) 의 결과 값이 N 비트라면, Output 의 경우의 수 는 $2^{N}$ 개임
        • 따라서, $2^{N \over 2}$ 개의 해시함수 입력값, 결과 값 쌍을 가지고 있으면, 50% 이상의 확률로 충돌쌍을 찾을 수 있음
• Avalanche Effect
  • input 이 1 bit 만 달라져도 output 이 완전한 변화를 야기함
• 암호학적 해시 함수에 대한 충돌쌍 공격
  • 과거에는 64 bit output 를 가지는 암호학적 해시 함수가 안전하다고 생각됨
  • 그러나 컴퓨터의 발달로 64 bit 암호학적 해시 함수는 쉽게 충돌쌍을 찾을 수 있게 됨
• Secure Hash Algorithm (SHA) groups
  • 1993 년 미국 국가 안전 보장국과 미국 표준 기술연구소(NIST) 가 함께 설계
  • SHA-1 : SHA-0 의 취약점을 보강, 160 bit 해시 값
  • 2002 년 SHA-2 계열 설계

 

메시지 변조 감지 코드

• MDC (Mesage Modification Code)
  • 메시지 m 과 MDC h(m) 은 분리될 수 있으며, h(m) 은 변조되지 않도록 하는 것이 중요
    • Alice 는 메시지 m 에 대한 MDC h(m) 생성
    • Alice -> Bob : m, h(m), 단 h(m) 은 안전한 채널로 전송

 

대칭키 암호 시스템

• 정의
  • 암호화할 때와 복호화할 때 키가 같음
• 특징
  • 혼돈
    • 키와 암호문의 관계를 감추는 성질
      • 예시: 치환
  • 확산
    • 평문과 암호문의 관계를 감추는 성질
      • 평문 한 비트의 변화가 암호문의 모든 비트에 확산
      • 예시: Transposition 
• 종류
  • 블록 암호
    • 암/복호화 과정을 하나의 블록 단위로 수행함
  • 스트림 암호
    • 암/복호화 과정을 하나의 구성 단위 (1bit ) 로 수행함
• 예시
  • DES (Data Encryption Standard)
    • 64 bit 데이터 블록, 56 bit 암호키
    • 현재는 사용하지 않고 3-DES 와 AES 사용
    • Feistel 구조
      • 가역요소와 비가영요소 모두를 사용
        • 암호화/복호화 과정이 동일
      • 좌/우를 반으로 나누어 스위칭
    • F 함수를 잘 설계하는 것이 관건
    • Bruth Forth 로 뚫림 -> 안전하지 않음
  • 다중 DES
    • 짧은 키 길이의 보완을 위해 제안됨
    • 2중 DES
      • 키의 길이가 56 bit + 56 bit = 112 bit 의 효과가 있을까?
        • Meet in the Middle Attack 공격
          • 평문과 암호문이 주어졌을 때, 각각의 가능한 경우를 모두 계산했을 때, 중간에 같은 값이 존재함
          • 약 $2 \times 2^56  = 2^57$ 번의 계산이 필요하고, 정렬이나 검색하는 연산까지 모두 포함하면 약 $2^63$ 번의 계산이 필요
    • 3중 DES
      • 암호화
        • M -> E -> D -> E -> C
      • 복호화
        • C -> D -> E -> D -> M
      • 2중 DES 와는 다르게 과거 기술과의 호환성을 위해 Decryption 이 들어감
      • 하지만, 속도가 느림. 또한, 양자 컴퓨터 도입을 고려하여 AES 를 채택
    • AES
      • 블록 크기는 128 bit
      • 키의 크기는 128bit, 192bit, 256bit 
      • 라운드 수는 각각 10, 12, 14 라운드
        • 라운드 마다 확장된 키가 들어가는 구조
        • 4가지 Layer 로 구성됨
          • SubBytes
            • 한 바이트 단위로 치환
          • ShiftRows
            • state 행 안에서 바이트 단위로 자리 바꿈
          • MixColumns
            • 위치를 바꾸기 위해 내적 연산을 하는 것
          • AddRoundKey
            • 비밀키에서 생성된 128bit 의 라운드 키와 state 가 XOR 연산이 됨

 

 

운영모드와 패딩

• 패딩
  • 블록 사이즈를 채우지 못할 경우 블록 크기의 배수가 되도록 패딩을 해줘야 함
    • 제로 패딩
      • 문제점 : 평문의 패딩 앞에 00 이 있을 때, 어디까지가 패딩인지 알기가 어려움
    • PKCS7 (Public-key Cryptography Standard) 패딩
      • 패딩 바이트 값을 패딩 바이트 크기로 사용
      • 배수가 되더라도 패딩을 해야 함

• 운영모드
  
  • 정의
    • 블록의 단위보다 큰 사이즈의 평문을 암호화하기 위해 필요한 모드
  • 종류
    • ECB 모드
      • 한 블록의 평문은 한 블록의 암호문으로 암호화된다.
      • 장점
        • 병렬 처리가 가능 & 오류확산 X
      • 단점
        • 같은 평문이 같은 암호문으로 암호화되므로 블록 단위의 패턴이 유지됨
      • 사례
        • 화상 회의 줌으로 ECB 모드를 사용해서 보안 이슈가 있었음
    • CBC 모드
      • 한 평문 블록이 암호화 되기 이전에 바로 앞 평문 블록의 암호문과 XOR
      • 초기 벡터 (IV, Initialization Vector)
        • 평문을 암호화할 때마다 초기 벡터를 바꿈으로서 임의화 (randomization) -> probabilistic encryption algorithm)
      • 특징
        • 암호화는 병렬처리가 불가능
        • 복호화는 병렬처리가 가능
    • CTR 모드
      • CTR 이 암호화됨 -> 단 모든 평문 블럭마다 CTR 은 달라야 함
      • 특징
        • 전처리, 병렬처리 가능
• padding oracle attack
  • CBC 모드의 블록 암호화를 사용하는 어플리케이션에 조작된 암호문 값을 입력했을 경우 서버는 각기 다른 반응을 보임
    • 어플리케이션에서 올바른 암호문 값을 받았을 경우 : 200 OK
    • 어플리케이션에서 패딩이 올바르지 않은 암호문을 받았을 경우 : 500 Internal Server Error
    • 어플리케이션에서 패딩은 올바르나 잘못된 암호문을 받았을 경우 : 200 OK - 커스텀 에러 메시지
  • $2^8 \times 2^3  = 2^11$ 만 하면 중간 state 결과값을 모두 알 수 있다.

 

 

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

Message Authentication Code (MAC)

• MAC (e.g., Hash with key H(K, M))
  • 정의
    • 송/수신자가 서로 공유한 키를 이용하여 메시지 인증을 수행함
    • 공격으로부터 안전한 채널을 형성할 필요가 없음
    • 암호학적 해시 함수에 인증 키를 사용하는 구조
  • 특징
    • MAC 충돌 쌍을 찾기 어려워야 함
    • MAC 함수의 결과는 uniform 분포를 따름
  • 구조
    • 암호화 과정을 이용한 MAC
    • 암호학적 해시 함수를 이용한 MAC

 

CCM (Counter with CBC-MAC mode), GCM (Galois Counter Mode) ...

 

공개키 암호 시스템

공개키 암호 개요

• 공개키 암호
  • 암호화와 복호화에 사용되는 키가 다르다.
    • 공개키는 모두에게 공개되고, 개인키는 비밀로 보관
    • 공개키 pk 로부터 개인키 sk 를 도출하는 것은 계산적으로 불가능 (Computationally Infeasible)
• 특징
  • Trapdoor One-Way Function (TOWF)
    • $ f $ 는 계산하기 쉽지만, $f^{-1}$ 는 계산하기 어렵다
    • y 와 trapdoor 가 주어지면 x 는 쉽게 계산될 수 있다.
      • 개인키를 알고 있으면 쉽게 복호화할 수 있다.

 

 

RSA 암호

• 원리
  • 소인수 분해 문제
    • p,q 가 주어지면, n 은 계산하기 쉽지만, n 이 주어지면 p, q 는 계산하기 어렵다
• 문제점
  • Deterministic 알고리즘
    • 평문이 같으면 항상 동일한 암호문이 나옴
    • 평문에 랜덤성을 추가하는 OAEP 로 문제 해결
  • 부채널 공격 (Side Channel Attack)
    • 암/복호화시 비트 연산의 차이로 나타나는 시간차 공격 (Timing Attack) 및 전력차 공격이 가능함
    • 지수 계산할 때 각각의 지수 계산에 동일한 시간을 걸리도록 만들어서 해결 가능
• 권고사항
  • n 비트는 적어도 2048 비트
  • 서로 다른 두 소수 p,q 는 적어도 1024 비트 이상. (단, 너무 가까이 있지 않아야 함)
  • n 를 공통적으로 이용하지 않음
  • 공개키 e 는 $2^16 + 1 = 65537$ 을 이용하거나 혹은 이와 가까이 있는 값을 이용한다.
  • d 가 노출될 경우 수신자는 반드시 n 과 e, 개인키 d 를 즉시 교체해야 한다.
  • OAEP 를 이용

 

전자 서명 (Digital Signature)

• 과정
  • 공개키 알고리즘과 유사하지만, 암호 과정이 아님에 유의. (검증한다.)
  • 키 생성 과정을 통해 검증키 (공개키) pk, 서명키 (개인키) sk 생성함
    • $Sig_{sk}(\cdot)=$ 서명 생성 알고리즘, $Ver_{pk}(\cdot) =$ 검증 알고리즘
    • 해시 후 서명해야 함
    • $s= Sig_{sk}(h(m)))$
• 제공하는 보안 서비스
  • 무결성
  • 메시지 공개 검증
  • 메시지 인증
  • 부인방지
• MAC vs. 전자 서명
  • 공통점
    • MAC 과 전자서명은 모두 무결성, 메시지 인증 제공
  • 차이점
    • 공개 검증
    • 키 관리
    • 부인방지
    • MAC 은 전자서명보다 효율적인 계산이 가능함

 

공개키 기반 구조 (Public Key Infrastructure)

• 공개키 암호시스템을 이용한 키 교환
  
  • 인증서를 이용한 공개키 인증
    • 신뢰할 수 있는 서버 (CA) 가 자신의 개인키로 서명하여 인증서를 발급해줌
  • 인증서 형태 (X.509)
• CA의 공개키 : 모든 디바이스가 알고 있는 값
• PKI 구조
  • 인증 기관들 간 신뢰 모델
    • 계층 모델 (Hierarchical Model) - 국내모델
    • 상위 계층이 바로 아래 계층의 인증서를 발급, 최상위 계층인 루트 인증 기관은 self-signing
    • 매쉬 모델(Mesh Model) : 국가간 상호인증

 

개체 인증 

개체 인증 (Entity Authentication) 의 개요

• 개체 인증
  • 특정 개체를 다른 개체에 인증하는 것
  • 개체는 사람, 프로세스, 디바이스 등이 될 수 있음
  • 개체의 신원을 증명하기 위한 일련의 과정
    • 개체 : 사람, 기기, 프로세스 등
  • 인증 정보
    • What you are (voice, fingerprint, Iris)
    • What you know (password)
    • What you have (smart card, token card)
    • 최근에는 Two-factor 인증 or Multi-factor 인증이 쓰이고 있음

 

Challenge and Response 인증

• 정의
  • password authentication 에서 요구자가 자신이 password 를 알고 있다는 것을 입증해서 자신의 신원을 입증하는 것이다.
    • 요구자가 secret 을 보내지 않고 자신이 secret 을 알고 있다는 것을 입증하는 것이다.
• 발전 과정
  • Symmetric-key Cipher C&R : Using a Nonce
    • Alice -> Bob : "I'm Alice"
    • Alice <- Bob : $R_{B}$
    • Alice -> Bob : $E_{AB} (R_{B})$
  • Symmetric-key Cipher C&R : Bidirectional authentication
    • Alice -> Bob : "I'm Alice, $R_{A}$"
    • Alice <- Bob : $E_{AB} (R_{A}), R_{B}$
    • Alice -> Bob : $E_{AB} (R_{B})$
  • Asymmetric-key Cipher C&R : Bidirectional authentication
    • Alice -> Bob : $ E_{B}("I'm Alice, R_{A})$"
    • Alice <- Bob : $ E_{A} ("I'm Bob", R_{B}, R_{A})$
    • Alice -> Bob : $R_{B}$

 

키 관리 시스템

키 분배 기술

• 대칭키를 이용한 키 분배
  • Pair-wise 방법
    • N 명이 존재할 때, 총 ${n(n-1) \over 2}$ 키 필요함. 사용자는 (n-1) 관리 (n 명에서 2명을 뽑는 조합의 수)
  • 키 분배 센터 (KDC) 방법
    • N 명이 존재할 때, KDC 는 n 개의 키 저장. 사용자는 1개의 키 저장
• 커버로스
  • User (Alice) 가 KDC 의 AS 에 TGS ticket 을 요청
  • AS 는 User 에게 Alice-TGS 세션 키와 TGS 를 위한 ticket 를 제공
  • User 가 Bob 를 위한 ticket 을 요청
  • TGS 가 User 에게 Alice-Bob 세션 키와 Bob 을 위한 ticket 을 제공
  • Alice 가 Server (Bob) 에게 접근을 요청
  • Server 가 Alice 에게 접근을 허가 (세션, 티켓이 유효하다면)

 

키 교환 기술

• Diffie-Hellman 동의 프로토콜
  • 수학적 배경 : Discrete Logarithm Problem (DLP)
  • 문제점
    • Man in the middle attack 이 가능
      • 중간자가 각각의 대칭키를 갖게 됨
• STS (Station-To-Station) 프로토콜
  • Diffie-Hellman 프로토콜에서 서명을 추가한 프로토콜

 

 

네트워크 보안

Backgrounds

• Link Encryption
  • 모든 링크에서 암호화가 독립적으로 수행됨
  • 모든 링크간의 사전에 공유된 키가 필요함
• End-to-End Encryption
  • 암호화가 시작점 (source) 와 도착점 (Destination) 에서 수행됨

 

SSL/TLS 프로토콜

• 정의
  • SSL/TLS 프로토콜은 Client 와 Server 의 통신에 메시지 인증, 기밀성을 제공하고 가용성도 제공
  • 암호화 되지 않은 패킷은 SSL 패킷으로 인코딩 되면서 암호화가 진행됨
• Handshake Protocol
  • 키를 주고 받는 단계 (4단계)
    • Phase 1
      • Client 와 Server 가 아래 정보를 교환
        • SSL 버전, 키 교환 알고리즘, 인증 알고리즘, 암호화 알고리즘, ...
    • Phase 2
      • Server 는 인증서와 키 교환 메시지를 전송하며, 필요할 경우 Client 로부터 인증서 요청 메시지를 전송
      • 이후, Client 는 Server 의 공개키를 알게 됨
    • Phase 3
      • Server 로부터 인증서 요청 메시지를 수신할 경우, Client 의 인증서를 보내줌
      • 이후, Server 는 Client 를 인증할 수 있게 되고, Server 와 Client 는 pre-master secret (PM) 를 공유하게 됨
        • Pre-master secret (PM) 을 이용하여 48 byte 의 Master secret 을 생성함
    • Phase 4
      • Client 와 Server 는 암호 알고리즘과 보안 파라미터를 변경하는 메시지를 주고받고, Handshake 프로토콜 종료 메시지를 주고받음으로써 Handshake 프로토콜을 종료
      • 이후, Client 와 Server 는 data 를 교환할 준비가 됨

 

IPSec

• Why IPSec?
  • 모든 Client/ Server 프로그램이 application layer 에서 보호되지 않음
  • 또한, 특정 application 들은 TCP 가 아닌 UDP 를 쓰기도 함
  • IP 기반 서비스들은 IP 헤더 정보가 중요함
  • IPSec 은 IP 헤더에 암호학적인 보호장치를 두는 것을 의미
• 모드
  • Transport mode
    • IP 헤더와 data 필드사이에 추가필드 (ESP/AH) 를 넣음
    • 하지만, 원본 헤더는 보호되지 않음
      • 보호되지 않는 IP 헤더를 통해 패킷의 source / destination 파악 가능
  • Tunnel mode
    • 원본 IP 헤더가 IPSec 에 의해 encapsulation 이 됨
      • ESP 와 AH 둘 중에 한 개의 보안 프로토콜을 선택함
      • 전체 패킷의 보호가 가능