Fundamental Concept of Cryptosystem: 개념과 역사를 중심으로

Cryptography의 핵심 목적은 채널들의 통신을 보안하는 것이다. (The main objective of cryptography is to secure communication over insecure communication channels)

그리고 여기서 Security Goals는 Confidentiality, Integrity, Authenticity이다.

Confidentiality

설령 데이터 통신 중간에 공격자가 메시지를 가로챈다고 해도, 그 메시지를 해독할 수 없어야 한다.

Integrity

데이터가 통신 과정에서 공격자에 의해 변경되지 않았음을 보장해야 한다. (데이터의 완전성과 일관성)

Authenticity

데이터의 송신자를 증명할 수 있어야 한다.

 

Fundamental Concept

Cipher(cryptosystem)는 plaintext(평문)을 encrypt(암호화)하는데 사용된다. 암호화한 resut를 ciphertext라고 부른다.

우리는 ciphertext를 복호화하여 plaintext(평문)을 복구한다. cryptosystem을 구성하는데 key가 사용된다.

Symmetric Key vs Public/private Key

Symmetric key cryptosystem에서는 동일한 키를 암호화(encrypt) 그리고 복호화(decrypt)에 사용한다.

Public key cryptosystem은 public key로 암호화(encrypt)를, private key로 복호화(decrypt)를 한다.

Basic assumptions

• 시스템은 완전히 공격자에게 공개되어 있다. (The system is complete known to the attacker)
• 오로지 key만 비공개(secret)다. (only the key is secret)
• 즉, crypto 알고리즘은 비밀이 아니고 모두에게 공개되어 있다. 이는 Kerchoffs' Principle, Saltzer와 Schroeder의 Open Design Principle과도 연관이 있다.

Q: 왜 이런 가정을 할까?

A: 경험적으로 보았을 때

1. secret algorithm은 노출되었을 때 매우 취약해지는 경향이 있다.
2. secret algorithm은 절대 secret으로 남지 않는다. 결국엔 드러난다. (Secret algorithms never remain secret.)

 

Caesar's cipher

카이사르 암호라고도 불리는 caesar cipher는 정말 간단한 치환암호의 일종이다. 문자를 일정 거리만큼 밀어서 다른 글자로 치환하는 방식이다.

• 우리는 모두 고정된 숫자 n이 key라는 것을 알고 있다.
• 우리는 모두 이 cipher algorithm이 알파벳을 일정 거리만큼 이동(shift)하는 것이라는 사실을 알고 있다.
• Only 26 possible keys이기 때문에 Try them all하면 풀린다. (Exhaustive key search)

 

Substitution Cipher with Permutation

카이사르 암호화보다 더 발전된 방식이다. 대입(substitution)과 치환(Permutation)을 활용한 암호화 방식이다.

26개의 알파벳에 대해 permutation을 적용하여 key를 만들고 대입하여 암호화하는 방식이다.

발생할 수 있는 Key의 갯수는 26!로, 2^88보다 큰 값이다.

• 카이사르 암호화에서 적용했던 Exhaustive Key Search로는 이제 현실적인 소요 시간 상 불가능하다.
  • 2^88 경우의 수의 모든 key를 시도해볼 수 없기 때문에
• 그러나, 통계적으로 접근하면, English letter의 빈도 수를 이용할 수 있다.

secure? insecure?

Cryptosystem의 가장 최선의 공격 방식이 Exhaustive key search(전수키 조사)라면 그 시스템은 secure하다고 볼 수 있다.

만약 그 외에 더 빠른 공격 방식이 알려져 있다면 그 cryptosystem은 insecure하다.

그러나 때론 secure cipher보다 insecure cipher가 더 깨기 어려울 수 있다.

 

One-Time Pad

Encryption

Decryption

• secure해 보인다.
  • Substitution Cipher with Permutation에서 ciphertext로부터 plaintext를 통계적 추론이 가능했던 것에 비해서, 해당 cipher는 ciphertext로부터 plaintext에 대한 유용한 정보를 얻을 수 없다.
• 그러나, 올바르게 사용되었을 때만 그렇다.
  • Pad는 반드시 random해야 하며 단 한번만 사용되야하므로 통신마다 매번 발급해야 한다.
    • 재사용되다 누설된다면 과거의 통신 내용이 모두 복호화될 것이다.
  • Pad는 반드시 송신자와 수신자만이 알고 있어야 한다.
    • 일회용 패드를 사용하여 통신한다면 송/수신자가 동일한 패드가 필요한데, 수신자에게 패드를 안전하게 보낼 수 있는 방법이 있다면 평문 그 자체를 안전하게 보낼 방법도 있을 것이다.
  • Pad의 사이즈는 message의 사이즈와 동일하다.
    • 메시지가 대용량이라서 따라도 Pad도 대용량일 때, 송/수신자 간에 패드의 비트열이 조금이라도 어긋난다면 수신자는 복호화가 불가능하다.

 

Codebook cipher

simple substitution과 비슷한 치환 암호의 일종이지만, simple substitution은 각 문자마다 치환을 하는 반면 code book은 단어나 절을 치환한다.

• Additive 사용 시
  • message를 codebook으로 암호화한다.
  • additive book에서 position을 선택한다.
  • ciphertext에 additives를 추가한다.
  • ciphertext와 additive position(MI)를 전송한다.
  • 수신자는 복호화 전에 additives를 substract한다.

 

Symmetric Key Crypto

• Stream Cipher는 one-time pad의 일반화된 방식이다.
  • key는 긴 keystream으로 stretch되어 있다.
  • keystream은 one-time pad처럼 쓰인다.
• Block Cipher는 codebook의 일반화된 방식이다.
  • Block cipher key는 codebook을 선택한다.
  • 각각의 key는 서로 다른 codebook을 얻는다.
  • confusion과 diffusion을 모두 적용한다.

 

Modern Cryptography

Symmetric-Key Cryptography

• Symmetric-Key Cryptography(Shared key ... )
  
  • 통신의 양방향 (암호화, 복호화) 모두 동일한 secret key를 사용한다.
    • 송신자와 수신자가 이미 secret key를 공유한다는 가정이 필요하다.
  • Stream Cipher
  • Block Cipher
    • DES(Data Encryption Standard)
      • Developed by the NSA
      • Stream Cipher로도 사용될 수 있다.
      • Block size는 64 bits
    • AES(Advanced Encryption Standard)
      • Adopted by NIST
      • Block size는 128 bits
      • Key size는 128, 192, 혹은 256 비트다.

• Asymmetric-Key Cryptography(Public-key ... )
  • 통신의 양방향에서 다른 key를 사용한다.
• Hash Algorithms
  • 단방향 암호화 (해시 값을 평문으로 복호화 불가)
    • unhashing or dehashing 같은 건 없다!
  • 해싱에 key는 사용되지 않는다.
  • Fast coputation time (해싱 처리 시간이 빠르다.)
  • 사용 목적
    • Fixed-size fingerprint가 필요할 때 혹은 매우 긴 입력 데이터로부터 고정된 길이의 digest를 생성할 때 쓰인다.
    • Hash passwords가 있다면 서버나 서비스에 Plaintext Passwords를 저장할 필요가 없다.
    • Data Integrity를 보장하기에도 좋다.

MAC

MAC(Message Authentication Code)

단방향 함수로, message digest를 생성하는 key가 존재하는 해시 함수라고 보면 된다.

digest는 메시지의 마지막에 추가되며, 수신자가 검증할 수 있다.

 

MAC vs Hash

• Mac
  • key가 사용된다.
  • 메시지의 integrity와 authenticity를 보장한다.
  • MAC을 verify하기 위해 공유 키(shared key)가 필요하다.
• Hash
  • key가 사용되지 않는다.
  • Integrity만을 보장한다.
  • 누구든 hash를 verify할 수 있다.

 

HMAC

Hash-based Message Authentication Code

오늘날 가장 광범위하게 사용되는 MAC 형태이다.

SHA-256과 같은 해시 함수를 기반으로 MAC을 빌드한다.

 

References

https://marcokhan.tistory.com/225

https://jaebworld.tistory.com/6