PGP ( Pretty Good Privacy )

by Hye Jin Youn & Security KAIST
Sponsored by Initech.

---

Copyright (C) May 1999, Hye Jin Youn and Security KAIST

You may freely redistribute or republish this article, provided the following conditions are met as long as it is for non-commercial purposes. Otherwise permissions should be granted:

1. This article is left intact.

2. Proper credit is given to its authors; Hye Jin Youn and the Security KAIST

Contents

---

I. Introduction

1) E-mail privacy

2) E-mail security

II. Basic Cryptographic Algorithm

1. What is Cryptography

2. Conventrional vs Public Cryptosystem

3. Hash Function

4. CryptoAnalysis and Attack on Cryptosystems

III. What is PGP

1. Why PGP is so popular?

2. PGP 의 기능

3. Structure

4. Cryptographic keys

5. Key Ring

5. Certification

IV. Certification

V. Let's use PGP

VI. Reference

Instruction

1. E-mail privacy

자신의 개인적인 정보를 보낼때 우린 엽서( postcard )를 이용해서 보내는 일은 좀처럼 하지 않습니다. 때론, 동봉을 해서 보내는 경우도 있고, 자신이 보냈음을 알리는 사인도 합니다.

e-mail도 이제 우편처럼 우리주위에서 많이 써오는 하나의 전달 수단으로 자리잡게 되었습니다.

그런데, 이 e-mail은 목적지까지 도착할때 수많은 host를 거처가는 경우가 보통입니다. 또한 중간에 제 3자에의해 가로채여서 보여지는 것은 물론, 변조가 되었는지를 알아채기란 그리 쉬운일이 아닙니다. 그렇다면 우린 어떻게 할수있을까요? 전쟁영화들을 보면 자신의 군대에게 명령을 보내기 위해 암호를 사용합니다. 즉, 적군이 그 명령을 보아도 알아채기 어렵게 하기 위해서입니다.

pgp도 이런 방법중 하나로 태어났으며, 현재 전자우편도구로서 널리 사용되고 있습니다.

2. E-mail security

1) Confidentiality : 수신자를 제외한 나머지 ( 제 3자 )가 메세지를 보지 못하게 하는 기능.

2) Message Integrity : 전송중 제 3자에 의해 메세지가 변조되었는지를 확인.

3) User authentiaton : 메세지를 보낸사람이 확실한지를 확인.

4) Nonprepudiation of origin : 송신자가 보내고 안보냈다고 할수 없게 만든다.

5) Non-deniablity of recipt : 수신자가 받고 안받았다고 못하게 만든다.

6) Message replay prevention : 중간에서 지나가는 mail을 잡아놓았다가 다시보내는 공격을 방지.

* 위의 1),2),3),4) 4가지는 pgp에서 지원하나, 5),6),번은 아직 지원되고 있지 않다.

1. What is Cryptographic?

더이상 Cryptographic은 군대나 정부의 소유물이 되지는 않는다. 우리는 이것을 사적정보를 보호하는 수단뿐 아니라, 인증, 서명 전자상거래 등으로 이용범위를 확산시킬수 있다.

또한 crytographic은 이제 수학적 증명을 통해서 풀기어려움을 입증하며, 계산또한 사람이 계산할수 있는 범위를 넘어섰다. 현대에서 가장많이 사용되는 알고리즘으로는 key를 쓴다 .
즉, 암호화( encrypt )와 복호화 ( decrypt )를 key를 이용하여 하는 것이다.

2. Conventional and Public key Cryptosystem

* key를 쓰는 Cryptosystem중 가장 많이 쓰이는 두 종류를 소개하겠다. 이 두종류는 pgp에서도 쓰이므로 잘 봐두기를 바란다.

1) Conventional crytosystem

관용 암호 알고리즘이라고도 하는데, 암호화될때의 key와 복호화될때의 key가 같은 key이다. 즉
Kd = Ke
그렇기 때문에 symmetric cipher라고도 한다.

장점으로는 암호화와 복호화에서 빠른 속도를 보이고 있다.

단점은 송신자와 수신자는 같은 key를 가지고 있어야하므로, key가 전달되는 과정에서 노출될 가능성이 커지므로 키분배가 어렵다.

쓰이는 알고리즘으로는,

• DES( Data Encryption System ) : 56 bit key 사용.
• IDEA( International Data Encryption Algorith ) : 128 bit
• RC5
• CAST-128

3). Public Key Algorithm

암호화 key와 복호화 Key가 다르기때문에 Asymmetric cipher라고도 불리우며, 이때에 public key는 남에게 알려주고. private key만 자신이 보관하기 때문에 secret key라고도 한다. 즉, Kd != Ke

digital signature가 구현가능하며, 공개키는 어떤 사람이 알아도 상관없으므로 키 분배에도 어렵지 않다.

단점은 지금까지의 알고리즘 모두 conventional cryptosystem에 비해 느린 속도를 보이고 있다는 것이다.

현재 많이 쓰이는 알고리즘으로는,

• RSA( Rivest-Shamir-Adelman ) : 1024bit key
• LUC : exponential 함수 대신 Lucas function을 이용.

4). Hash function

• 임의의 스트링을 받으면 일정한 길이의 bit로 표현된다.

• 같은 hash 값을 갖는 두 메세지를 찾기라는 것은 사실상 불가능하다.

• MD5( Message Digest Algorithm 5 ), MD2, MD4, SHA( Secure Hash Algorithm ) 등이 사용되어진다.

5). Crypto-Analysis & Attack on Cryptosystem

• Ciphertext-only attack : M( 메세지 )내용 뿐만 아니라, key모두를 알지 못할경우 언어의 특색을 이용( 원문의 통계적 특성 )하여 경우를 다 대입하여 푼다.

• Known-plaintext attack : M 과 encrypted M을 알고 있을 경우 Key를 찾아내어 다음 M2를 읽어내는 것.

• Chosen-plaintext attack : M과 약간 다른 M'등이 encrypt된 파일을 비교해서 알아내는 것.

• Man-in-the-middle attack : C라는 사람이 B라고 하며 A에게 공개키 Kp(B)를 주었을때 A는 B외에 알아서는 안되는 문서를 C의 key로 encrypt해서 보내므로 중간에 C에게 가로채이면, C가 볼수 있다. 이 외에 C라는 사람이 문서를 주었을때, A는 거짓정보를 믿어버리게 된다.

* 사실 강력한 알고리즘이란 것은 위의 3가지는 풀려서 안된다.

6). The Notion

* 앞으로 그림으로 설명할때, 이런 notion들이 쓰여지므로, 참고해 두세요.
• Ks : session key in conventional encryption schem
• KR(A) : private key of user A
• KU(A) : public key of user A
• EP : public-key encryption
• DP : public-key decryption
• EC : conventional key ecryption
• DC : conventional key decryption
• H : Hash function
• || : 연결
• Z : ZIP algorithm을 이용한 compression
• R64 : radix 64 ASCII format으로 바꾼것.

1. Why PGP is popular?

• Dos, Windows, Unix, Mac등 여러기종의 OS에서 사용가능하다.

• 높은 보안성의 알고리즘을 사용하였다 : PGP에서 사용된.RSA, MD5, IDEA, RHS, CAST-128등은 모두 여러면에서 검증된 훌륭한 보안 알고리즘들이다.

• 한 개인의 작품이다. : 정부나 표준기관이 아닌, 한 개인 ( phil Zimmerman )의 작품이다.

• 소스와 document가 공개되어있다. -> 믿을수 있다.

• 싼가격과 공개용 버전이 있다.

• 전자메일과 호환이 가능하다.

2. pgp의 기능

1) Confientiality

A가 자신의 공개키 Kp(A)를 공개하고, 자신의 secret key( private key ) Ks(A)를 잘 간수하고 있기만 한다면. B가 A에게 비밀문서 ( M )을 Kp(A)로 encrypt해서 보내면, 이 M을 decrypt해서 읽을수 있는 사람은 A밖에 없다.
즉, 그림으로 보면,

2) Authentication

Digital signature :

public key의 중요한 기능중 하나이다.
가령 A라는 사람이 Kp(B)로 encrypted M을 작성한 후 Ks(A)로 digital signature를 해서 보내면, B뿐만 아니라 모든 Kp(A)를 갖은 사람은 Kp(A)로 그 digital signature를 볼수있으나, signature는 A밖에 할수 없으므로 A가 보냈음을 알수 있다.

3) Message integrity

A는 M을 Hash에 넣으면 일정길이의 작은 bit로 나온다.
M' 이것을 Ks(A)로 암호화 하여 , M에 붙여서 보내면, B는 Kp(A)로 이를 풀고, M을 Hash를 이용하여 만든후 M'와 비교하여, 제 3자에 의해 메세지가 변조되지 않았는가를 알수 있다.

4) Compression

- pgp의 option으로 할수도있고, 안할수도 있다.

- 보통 Signature 후에 encrypt전에 하는데, 그 이유는

• signature가 있는 원본과, compression되 M 두가지를 저장할수 있다.

• Zip Algorithm에서 기인되는데,
  만약, sinature전에 compression을 한다면, 보통 M을 decompression하여 Data를 본후 signature로 중간에 고쳐졌는지, 확인을 하는데, 이때 다시 compression을 해야한다.
  하지만, compression은 속도와 압축률에 따라 달라지므로, 두 data확인이 어려워지고 번거로워진다.

5) E-mail Compatibility

- pgp에서 decrypt는 8bit로 되는데 e-mail은 ASC인 7bit까지 밖에 지원이 되지 않는다. 그러므로 decrypted message 3 block을 6bit 4 block으로 만들어준다. 이때 radix 64-conversion이 사용된다.

6) Segmentaion & Reassembly

- PGP에서는 Message가 매우크면 한꺼번에 보내지 않고 잘라서 보낸다.
또한 받았을때는 알아서 붙여준다.

3. Structure

사실 public key에서 사용되는 key는 무척 길다. 그렇기 때문에 만약, 여러개의 pgp의 쌍을 찾기라는 무척 힘들어 질것이다.

이때 key의 구별을 쉽게 하기위해 hash function에 넣어 일정한 길이의 bit수로 나타낸 것을 KeyID라고 한다.

5. Key Rings

- pgp를 처음 설치하면 아래의 화일이 만들어진다. secring.pgp, pubring.pgp, randseed.bin. config.txt가 그것들이다.
예제 보기

이 예제에서 pgp -kg는 처음 키를 생성하는 것이다. 마지막부분을 보면 네개의file이 만들어지는 것을 알수있다.

- private key - : secring.pgp



예제 보기

• Time-Stamp : key 생성시간.

• KeyID : 64bit keyID

• public key

• private key : encrypt된 private key

• user ID : 보통 email address와 비슷하게 쓴다. 즉 예를 들면, vici < vici@sparcs.kaist.ac.kr >

- public key - : pubring.pgp



예제 보기

• Time-Stamp

• KeyID

• public key

• user ID

- randseed.bin( seed 값을 보관하는 곳 )

사용자가 공개키와 비밀키를 만들때 무작위한 방법으로 키보드를 누를때 생성된다. 위의 예제를 보면 나와있다.

- pgp의 아킬라스건이라고 불리우는 어택이 바로 main-in-the-middle-attack이다.

그러므로 키를 받아올때는 많은 주의를 기울여야하는데, 4가지 방법을 보면,

1. floppy disk에 담아서 직접 전달 받는법.:

이는 가장 원시적인 방법이나 가장 확실한 인증 방법이다.

2. finger print 이용.

상대방의 전화목소리를 아는 경우 hash function에 넣어서 키를 일정한 bit로 나타내면 이를 전화기를 통해서 확인한다. 이 방법도 확실하나, 만약 attaker가 전화목소리까지 흉내낸다면 할수 없다. --;

3. signature확인.

아주 확실한 방법은 아니지만, 편리함으로 가장 많이 쓰이는 방법. 2)또는 3)번처럼 자신이 확인하여 확실한 경우, 자신의 signature를 담으로 인하여 다른 사람에게 알려줌 또한, 그 반대로 다른 사람의 signature를 봄으로 인하여, 신뢰도를 측정한다.

- 공개키 인증에 필요한 값들.

1) key legitimacy

• A ID가 붙은 이 key는 진짜 A의 것인가?

• KEYLEGIT field
  • unknown or undefined trust
  • key ownership not trusted
  • marginal trust in key ownership
  • complete trust in key ownership

• * owner trust 와 signature turst에 의해 자동으로 생성되어진다.

2) Owner Trust

• 중개자로서의 A를 어느정도 신임할수 있는가?

• ONWERTRUST field
  • undefined trust
  • unknown user
  • usually not trusted to sign other keys
  • usually trusted to sign other keys
  • always trusted to sign other kyes
  • this key is present in secret key ring ( ultimate trust )

• * 다른 사람의 공개키를 자신의 pubring.pgp에 등록시킬때 스스로 지정해준다.

3) Signature turst

• B의 key에 A의 서명이 있는데 어느정도 믿을만 한가?

• SIGTRUST field
  • undefined trust
  • unknown user
  • usually not trusted to sign other keys
  • usually trusted to sign other keys
  • always trusted to sign other kyes
  • this key is present in secret key ring ( ultimate trust )

• * 서명하는 사용자의 owner trust에서 복사한다.

%> pgp -c textfile
문서를 암호화 하기

%> pgp -cw textfile
원래의 평문을 지우기

예제 보기

%> pgp textfile.pgp
복호화하기.

%> pgp -kg
키만들기 ( key gerneration )

예제 보기

%> pgp -kv
키 보기 ( key view )

%> pgp -ke
키 변경하기 ( key edit )

예제 보기

%> pgp -kx UserID file
자신의 키를 다른 사람들에게 전파시키는 방법으로는 키 화일 전체를 복사해서 옮기는 방법도 있지만 이 방법은 여러 종류의 위 험이 뒤따른다.

그러므로 자신이 보내고자 하는 키만을 빼내어서 보내어야 한다. 이럴 때 쓰는 옵션이 "-kx" 옵션이다 . 옵션 뒤에 나오는 것은 빼낼려고 하는 키의 User ID와 키를 복사해서 담을 화일의 이름이다

%> pgp -kr
키 지우기 ( key remove )
사용자 자신의 공개키 화일에 있는 자신의 키나 다른 사람의 키를 지울 때 쓰는 옵션이 "-kr" 옵션이다. 자신의 키일 경우에는 매칭되는 비밀키도 지울 수 있다.

%> pgp -m cipher.asc
암호문을 옵션 없이 복호화하면 복호화된 평문 화일이 생기는 데 이는 평문과 암호문의 한쌍을 만드는 것이기 때문에 사용자의 유의가 필요하다.

이러한 문제점을 해결하기 위해서 "-m" 옵션을 사용하는 데 이렇게 하면 복호화된 내용이 화면에 보 여질 뿐이고 다 보고 난 후에 하드 디스크에 담을 것인지를 물어 본다. 여기서 no를 입력하면 복호화 된 내용은 디스크에 담겨지 지 않는다.

예제 보기

%> pgp -s textfile
digital signature달기

예제 보기

* 이 밖에 여러가지가 있으나, 여기서는 더이상 다루지 않고, manual page를 참고하시길 바란다.

VI. Refernce

---

http://www.eff.org/pub/Privacy/chaum_privacy_id.article

http://www.ssh.fi/tech/crypto/intro.html

http://www.animatedsoftware.com/hightech/philspgp.htm

http://www.internetworld.com/print/monthly/1995/02/feat34.htm

http://www.stack.nl/~galactus/remailers/bg2pgp.txt

(1) PGP documentation
by Phil Zimmermann

(2) alt.security.pgp: Frequently Asked Questions
by Jeff Licquia, May 25, 1995

(3) Why Should You Sign Your Own PGP Public Key?
by Francis Litterio

(4) EFH PGP Workshop
by Paul Elliott, Electronic Frontiers Houston

(5) The Beginner's Guide to Pretty Good Privacy
by Bill Morton, Version 1.1, April 13, 1995

(6) Known future developments in PGP servers and related subjects

(7) Four11 Directory Services

(8) Differences in International PGP Version by Stale Schumacher

(9) Cryptography And network security
- william stallings