2014年3月18日 星期二

Python M2Crypto - X.509 Certificate Sign Request 與 Sign Certificate


X.509 憑證基本觀念

X.509 是由 ITU-T 所製定的 PKI 標準，它主要包含以下 4 個規範：
  1. public key certificates
  2. certificate revocation lists
  3. attribute certificates
  4. certification path validation algorithm
X.509 的憑證簽發關係的概念圖如下：


產生 Root CA Certificate

  • 產生一把 RSA key pair (public / private keys) 
  • 準備一個 Root CA 憑證, 以及所需要的資訊，並且設定有效期限(一般來說是10~20年)。
  • 設定此 Root CA 憑證的 X.509 V3 的 Extension 
  • 用此 Root CA 的 RSA private key 來簽署這個憑證( Self-Signed Root CA Certificate)
產生 Self-Signed Root CA Certificate 的基本範例程式:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import M2Crypto
import time
import os
import struct
from M2Crypto import X509, EVP, ASN1

def generate_rsa_keypair(key_len, exponent):
    def empty_callback():
        pass
    rsa = M2Crypto.RSA.gen_key(key_len, exponent, empty_callback)
    return rsa

def create_self_signed_RootCA_certificate(root_ca_info, sign_method="sha256", days=3650):
    # Setp 1: Create RSA-key pair (public/private key)
    rsa = generate_rsa_keypair(2048, 65537)
    private_key = EVP.PKey()
    private_key.assign_rsa(rsa)
    
    # Step 2-1: Prepare X.509 Certificate Signed Request
    req = X509.Request()
    req.set_pubkey(private_key)
    x509_name = req.get_subject()
    x509_name.C = root_ca_info["C"]
    x509_name.CN = root_ca_info["CN"]
    x509_name.ST = root_ca_info["ST"]
    x509_name.L = root_ca_info["L"]
    x509_name.O = root_ca_info["O"]
    x509_name.OU = root_ca_info["OU"]
    req.sign(private_key,sign_method)
    # Step 2-2: Prepare X.509 certificate
    root_ca_cert = X509.X509()
    
    serial = struct.unpack("<Q", os.urandom(8))[0]
    root_ca_cert.set_serial_number(serial)
    root_ca_cert.set_version(3)
    # Setp 2-3: Set required information of RootCA certificate
    root_ca_cert.set_issuer(x509_name)
    root_ca_cert.set_subject(root_ca_cert.get_issuer())
    root_ca_cert.set_pubkey(req.get_pubkey())  # Get the CSR's public key    

    # Step 2-4: Set Valid Date for RootCA certificate
    t = long(time.time())
    now = ASN1.ASN1_UTCTIME()
    now.set_time(t)
    expire = ASN1.ASN1_UTCTIME()
    expire.set_time(t + days * 24 * 60 * 60)
    root_ca_cert.set_not_before(now)
    root_ca_cert.set_not_after(expire)
    # Step 3: Add Extensions for this Root CA certificate
    root_ca_cert.add_ext(X509.new_extension('basicConstraints', 'CA:TRUE'))
    root_ca_cert.add_ext(X509.new_extension('subjectKeyIdentifier', root_ca_cert.get_fingerprint()))
    
    # Step 4: Use Root CA's RSA private key to sign this certificate
    root_ca_cert.sign(private_key, sign_method)
    return root_ca_cert, private_key

if __name__ == '__main__':
    # Generate a Self-Signed Root CA Certificate
    root_ca_info = {}
    root_ca_info['C'] = "TW"
    root_ca_info['CN'] = "Root CA Certificate"
    root_ca_info['ST'] = "Taiwan"
    root_ca_info['O'] = "ijeCorp Ltd."
    root_ca_info['OU'] = "Security"
    root_ca_info['L'] = "Taipei"
    
    root_ca_cert, private_key = create_self_signed_RootCA_certificate(root_ca_info)
    with open('root_ca_cert.crt', 'w') as f:
        f.write(root_ca_cert.as_pem())
    with open('root_ca_private_key.pem', 'w') as f:
        f.write(private_key.as_pem(cipher=None))
    with open('root_ca_public_key.pem', 'w') as f:
        f.write(root_ca_cert.get_pubkey().as_pem(cipher=None))


產生 Certificate Signed Certificate 

  • 產生一把 RSA key pair (public/private key)
  • 準備一個 X.509 Request 
  • 設定 X.509 Request 的資訊
  • 用 RSA private key 去簽署這個 X.509 Request
產生 Certificate Signed Certificate (CSR) 的基本範例程式:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import M2Crypto
from M2Crypto import X509, EVP

def generate_rsa_keypair(key_len, exponent):
    def empty_callback():
        pass

    rsa = M2Crypto.RSA.gen_key(key_len, exponent, empty_callback)
    return rsa

def create_Signed_Certificate_Request(csr_info, key_len=2048, sign_method="sha256"):
    # Step 1: Create a RSA key pair (public/private key)
    rsa_keypair = generate_rsa_keypair(key_len, 65537)
    evp_private_key = EVP.PKey()
    evp_private_key.assign_rsa(rsa_keypair)
    # Step 2: Create a X.509 request 
    csr = X509.Request()
    csr.set_pubkey(evp_private_key)
    # Step 3: Set CSR information
    x509_name = csr.get_subject()
    x509_name.C = csr_info['C']
    x509_name.CN = csr_info['CN']
    x509_name.ST = csr_info['ST']
    x509_name.O = csr_info['O']
    x509_name.OU = csr_info['OU']
    x509_name.L = csr_info['L']

    # Step 4: Use RSA private key to sign it
    csr.sign(evp_private_key, sign_method)
    return csr, evp_private_key

if __name__ == '__main__':
    # Generate CSR for signed Certificate
    csr_info = {}
    csr_info['C'] = "TW"
    csr_info['CN'] = "CA-Certificate"
    csr_info['ST'] = "Taiwan"
    csr_info['O'] = "AbcCorp Ltd."
    csr_info['OU'] = "ABC-CA"
    csr_info['L'] = "Taipei"

    csr, private_key = create_Signed_Certificate_Request(csr_info);

    with open('CSR.pem', 'w') as f:
        f.write(csr.as_pem())
    with open('CSR_private_key.pem', 'w') as f:
        f.write(private_key.as_pem(cipher = None))

Root CA 或是 CA 根據 CSR 簽署一個 Certificate

  • 準備一個 X.509 的憑證
  • 設定 X.509 憑證的有效期限, 有效時間的長短根據需求而有不同
  • 設定 X.509 的 Extension 資訊
  • 根據 CSR 所提供的 subject 以及 public key 來設定 X.509 憑證
  • 使用 Root CA 或是 CA 的 RSA private key 來簽署這個 X.509 憑證
Root CA 根據 CSR 產生 Certificate 的基本範例程式:
此範例程式，只需要研讀 Line 130~133 與 Line 14~47 即可，它是直接以 Root CA 的 private key並且依據 CSR 來簽署憑證


  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
import M2Crypto
import time
import os
import struct
from M2Crypto import X509, EVP, ASN1

def generate_rsa_keypair(key_len, exponent):
    def empty_callback():
        pass

    rsa = M2Crypto.RSA.gen_key(key_len, exponent, empty_callback)
    return rsa

def create_certificate_from_CSR(rootCA_cert, rootCA_private_key, csr, days = 365):
    # Step 1: Prepare X.509 Certificate
    cert = X509.X509()
    serial = struct.unpack("<Q", os.urandom(8))[0]
    cert.set_serial_number(serial)
    cert.set_version(3)
    # Step 2: Set Expired Date
    t = long(time.time())
    now = ASN1.ASN1_UTCTIME()
    now.set_time(t)
    expire = ASN1.ASN1_UTCTIME()
    expire.set_time(t + days * 24 * 60 * 60)
    cert.set_not_before(now)
    cert.set_not_after(expire)
    # Step 3: Set X.509 Extensions
    cert.add_ext(X509.new_extension('nsComment', 'SSL sever'))
    cert.add_ext(X509.new_extension('keyUsage', 'Digital Signature')) 
    cert.add_ext(X509.new_extension('keyUsage', 'Key Encipherment', 1)) # 1 means critical
    cert.add_ext(X509.new_extension('keyUsage', 'Data Encipherment',1))
    cert.add_ext(X509.new_extension('keyUsage', 'Key Agreement', 1))
    cert.add_ext(X509.new_extension('extendedKeyUsage', 'clientAuth'))
    cert.add_ext(X509.new_extension('basicConstraints', 'CA:TRUE'))
    cert.add_ext(X509.new_extension('subjectAltName', 'DNS:www.ijecorp.com'))
    PCI_FULL = "critical, language:Inherit all"
    PCI_LIMITED = "critical, language:1.3.6.1.4.1.3536.1.1.1.9"
    cert.add_ext(X509.new_extension('proxyCertInfo',PCI_FULL, 1))
    # Step 4: Set Subject and Public Key from CSR
    cert.set_issuer(rootCA_cert.get_issuer())
    cert.set_subject(csr.get_subject())
    cert.set_pubkey(csr.get_pubkey())
    # Step 5: Use Private Key of Root CA or CA to sign this X.509 certificate
    cert.sign(rootCA_private_key, 'sha256')

    return cert

def create_Signed_Certificate_Request(csr_info, key_len=2048, sign_method="sha256"):
    # Step 1: Create a RSA key pair (public/private key)
    rsa_keypair = generate_rsa_keypair(key_len, 65537)
    evp_private_key = EVP.PKey()
    evp_private_key.assign_rsa(rsa_keypair)
    # Step 2: Create a X.509 request 
    csr = X509.Request()
    csr.set_pubkey(evp_private_key)
    # Step 3: Set CSR information
    x509_name = csr.get_subject()
    x509_name.C = csr_info['C']
    x509_name.CN = csr_info['CN']
    x509_name.ST = csr_info['ST']
    x509_name.O = csr_info['O']
    x509_name.OU = csr_info['OU']
    # Step 4: Use RSA private key to sign it
    csr.sign(evp_private_key, sign_method)
    return csr, evp_private_key

def create_self_signed_RootCA_certificate(root_ca_info, sign_method="sha256", days=3650):
    # Setp 1: Create RSA-key pair (public/private key)
    rsa = generate_rsa_keypair(2048, 65537)
    private_key = EVP.PKey()
    private_key.assign_rsa(rsa)
    # Step 2-1: Prepare X.509 Certificate Signed Request
    req = X509.Request()
    req.set_pubkey(private_key)
    x509_name = req.get_subject()
    x509_name.C = root_ca_info["C"]
    x509_name.CN = root_ca_info["CN"]
    x509_name.ST = root_ca_info["ST"]
    x509_name.L = root_ca_info["L"]
    x509_name.O = root_ca_info["O"]
    x509_name.OU = root_ca_info["OU"]
    req.sign(private_key,sign_method)
    # Step 2-2: Prepare X.509 certificate
    root_ca_cert = X509.X509()
    serial = struct.unpack("<Q", os.urandom(8))[0]
    root_ca_cert.set_serial_number(serial)
    root_ca_cert.set_version(3)
    # Setp 2-3: Set required information of RootCA certificate
    root_ca_cert.set_issuer(x509_name)
    root_ca_cert.set_subject(root_ca_cert.get_issuer())
    root_ca_cert.set_pubkey(req.get_pubkey())  # Get the CSR's public key    

    # Step 2-4: Set Valid Date for RootCA certificate
    t = long(time.time())
    now = ASN1.ASN1_UTCTIME()
    now.set_time(t)
    expire = ASN1.ASN1_UTCTIME()
    expire.set_time(t + days * 24 * 60 * 60)
    root_ca_cert.set_not_before(now)
    root_ca_cert.set_not_after(expire)
    # Step 3: Add Extensions for this Root CA certificate
    root_ca_cert.add_ext(X509.new_extension('basicConstraints', 'CA:TRUE'))
    root_ca_cert.add_ext(X509.new_extension('subjectKeyIdentifier', root_ca_cert.get_fingerprint()))
    
    # Step 4: Use Root CA's RSA private key to sign this certificate
    root_ca_cert.sign(private_key, sign_method)
    return root_ca_cert, private_key

if __name__ == '__main__':
    # Generate a Self-Signed Root CA Certificate
    root_ca_info = {}
    root_ca_info['C'] = "TW"
    root_ca_info['CN'] = "Root CA Certificate"
    root_ca_info['ST'] = "Taiwan"
    root_ca_info['O'] = "ijeCorp Ltd."
    root_ca_info['OU'] = "Security"
    root_ca_info['L'] = "Taipei"
    root_ca_cert, root_ca_private_key = create_self_signed_RootCA_certificate(root_ca_info)

    # Generate CSR for signed Certificate
    csr_info = {}
    csr_info['C'] = "TW"
    csr_info['CN'] = "MyCompany-Certificate"
    csr_info['ST'] = "."
    csr_info['O'] = "ijeCorp Ltd."
    csr_info['OU'] = "Security"
    csr, ca_private_key = create_Signed_Certificate_Request(csr_info);

    # Use Root CA's private key to sign a certificate from CSR
    cert = create_certificate_from_CSR(root_ca_cert, root_ca_private_key, csr)
    with open('my_cert.crt', 'w') as f:
        f.write(cert.as_pem())
以上的範例程式都是採用 SHA-256 是基於安全性的考量，請參考[2]

Reference:
[1] http://svn.osafoundation.org/m2crypto/trunk/contrib/SimpleX509create.py
[2] http://www.tbs-certificates.co.uk/FAQ/en/475.html


張貼者： 於 沒有留言:
標籤： , , , , , , , , ,

2014年3月12日 星期三

OpenSSL - 金鑰與憑證的管理

Key and Certificate Management

要讓 Web 或者 Service 能夠支援 SSL, 基本上有三個步驟：
1. 產生私有金鑰 (Private Key)
2. 產生 CSR (Certificate Signing Request), 並將 CSR 傳送給 CA
3. 把 CA 所提供的憑證 (Certificate) 安裝在 Web 或 Service的伺服器上

以下利用 OpenSSL 來說明如何完成以上 3 個步驟.

Key Generation

使用 openssl 產生私有金鑰 (private key) 的指令如下：

~$ openssl genrsa -aes256 -out private.key 2048

以下是執行後的輸出畫面, 會要求輸入Pass phrase 來保護這個 RSA private key.

Generating RSA private key, 2048 bit long modulus
.+++
.............................................+++
e is 65537 (0x10001)
Enter pass phrase for private.key:
Verifying - Enter pass phrase for private.key:


這是產生一把長度為 2048 bits 的 RSA private key, 並且使用 AES-256 與輸入的 Pass phrase 來保護這把 Private key。基本上, RSA的 Private key 長度建議至少是2048 bits才是比較安全的。執行後的結果 private.key 是一個加密後的檔案並且以 PEM 的格式儲存，內容類似以下：

-----BEGIN RSA PRIVATE KEY-----
Proc-Type: 4,ENCRYPTED
DEK-Info: AES-256-CBC,4616B291C58D187CE9787AD421E7DA80

9DbRWLR8N29lHz78aUCYWBUzDAK4e7UFfiV+A3oicaHm75FCw5hnf+3ScOUEymWk
Bz+sYKCjHTtD4fMyw4apF1/QmCn6KM+kKY4vsmOx1NXLLNhrX2SpmiZ+dsVfOg0D
IoEhw06Pzd767gy+zr8Q7JeMna1zKG7nzbIMM+WiwmiZKTErl16kyp0HH2OHSkQv
0or3cj83zswhb7VcArt52cJUhNdjkZdb3x+/bbehn5sFCMiNTc4UId5HBH84dyNC
l/KsDmdFfq8kGXhttpllz7pl8naYnamEQ0A+foaWI+MMXmMl5r5kXlDkAkCZ/y9U
LYmBLsSeMwrHVC34M+sCP8GEyeN4znAv9rb0eTs5/zkPo1V/orFxZYaQZwQ0yQn2
pUb10sD7cXrpJ4EQqPJzxOxhFAAq2C35lkYA5yrCwZiH6/Y66PvGYK1W1BMcB9B+
8t3Cn9xiNJ27HQ43oPWu6P07yxJYAPpkJMhiZ6cM1clYbi2ZrYKnajRORIoL0WgI
4d4zGYr48/Pd27ITSUxiBWIVsB8OZPGyjh3ebBGw1fe1i7iC1x/h35b+po8mk6Fg
tmIktPA9z/jUgSaorQsH9YzyA8DU4K1p3LCL4ZxHJJoEKOMv/7avQCRzm+FonWdz
e5rewtx9wNoWKSw4MPU6ozRB2tzW9RUJQeGfCgtwbjMDRQYYLmyLzPshekiR4srF
E3U1aJWwEDVTfdjlEgiB6dKzm/l1ywanBB5Ns84HSsagN7gZEBV3Y7TKlx+9Omd2
N6QIwTG42ERDmsuLlmky6Ju98yMHRNNC7ZrkLhR1c3w+KHht7cIm7VpqouNCYcjR
yhebuXpSakS4mPlYXKmFZlEgJI8NT9H1czn7XsNUE/Ty/wBlhgn5XGbmoRLg8b/L
jNqC/b3N4Xb9nWuirMmPwNf9Ja0M3MRJmjUrA3FJprHrSaJMF7SS3tHeu5vivnrP
P9vfibi8Cu2UVol3/y/gyBNGgsA2UnOz3xzPrY/22NA+VtDILIbsIukeHMGVPzdS
xE3BrgpyF68LrIg/Pb7F5XougYjW9SjuyYnQzum9XgvZGFsZJU+ENOmR+9gk8/iA
v+/RKairKW18E6kaf/9mIfYWWLHSPZyZqqo61Iho/BqO0vOSq7hd5at0KUsbtfr2
4o2cGMp5qYJxPBi5suIR3/H0bZnS72sAVPAeUGEhSi+QX9d9zQYJio8LfxsTZMZj
ArlJY3Lm9cGMEbS/n3jwC7zGE75j4aaNCTWccNWUqhF3p+QOCN3WL/yKXa1nDcx9
4AYt0UT8rHDHNVs1ylK97/e6OwV9bmhXf4shvBavvKcoSPVc2F8c/+yGWl/3BDyZ
MTTNYFN99Yll+g06DhSaQpUACbKpzHfNy83ideruLpqYLptqCEqE66pZZt08AhCg
JKNiTV6c6O09TBfwGz7Cqn+jsCsIN6iUbEOc1lEj9Ga+FtuVFy5h+nrzzSK3pA/W
mhqpnf9a0QmlfkrUBfmjCGyzQ1PnEs0Ki0PyPDISsRUewJXvWsDUoT3+k13nMfdE
hPZoPFjPA6pztnHUxUKDwx9xVmLTLHkLmu3VtWOaWl1qmZP57fMHoKjeaRYNYPN6
-----END RSA PRIVATE KEY-----

Creating Certificate Signing Requests (CSR)

為了向公開具備公信力的 CA 單位提出憑證申請, 必須要提供一個 CSR 的檔案給這個 CA單位。以下就是透過 openssl 使用先前產生的 RSA 金鑰來產生一個 CSR 的檔案，過程當中需要輸入一些相關的資料(可以參考以下範例中的黑色斜線粗體部份)
$ openssl req -new -key private.key -out CSR.csr

Enter pass phrase for private.key:
You are about to be asked to enter information that will be incorporated
into your certificate request.
What you are about to enter is what is called a Distinguished Name or a DN.
There are quite a few fields but you can leave some blank
For some fields there will be a default value,
If you enter '.', the field will be left blank.
-----
Country Name (2 letter code) [AU]:TW
State or Province Name (full name) [Some-State]:.            
Locality Name (eg, city) []:Taipei
Organization Name (eg, company) [Internet Widgits Pty Ltd]:ijeCorp        
Organizational Unit Name (eg, section) []:Security
Common Name (e.g. server FQDN or YOUR name) []:www.ijecorp.com
Email Address []:miller.lai@gmail.com

Please enter the following 'extra' attributes
to be sent with your certificate request
A challenge password []:IM@R.O.C    
An optional company name []:ijeCorp

產生 CSR 後, 可以透過 openssl 來檢測 CSR的內容是否正確，指令如下：
~$ openssl req -text -in CSR.csr -noout

執行後的輸出結果如下：
Certificate Request:
    Data:
        Version: 0 (0x0)
        Subject: C=TW, L=Taipei, O=ijeCorp, OU=Security, CN=www.ijecorp.com/emailAddress=miller.lai@gmail.com
        Subject Public Key Info:
            Public Key Algorithm: rsaEncryption
                Public-Key: (2048 bit)
                Modulus:
                    00:b2:fb:c9:5f:4c:0f:2a:11:d7:81:05:a9:e6:41:
                    43:35:b7:47:ba:be:58:42:32:ad:e9:99:be:c8:82:
                    57:73:ca:87:6c:f9:90:15:1d:4a:6d:cc:fc:81:e2:
                    2e:c2:1f:ed:fd:ae:45:cd:ce:c9:6c:43:f1:47:ef:
                    aa:8d:f8:e3:32:52:10:80:db:0a:b5:fa:be:91:87:
                    94:08:57:86:8e:6b:86:f6:63:05:2d:53:3c:c3:4c:
                    48:ad:4d:ee:f2:de:7c:68:9d:f7:01:5b:a1:99:2e:
                    69:60:b8:b1:59:4c:d8:69:7a:cf:47:bb:3c:c6:6f:
                    5d:99:08:5d:e8:5e:bd:34:e2:52:00:9c:70:62:89:
                    4b:aa:c6:8c:d7:0d:a0:fc:d7:1d:bf:18:9a:d4:e2:
                    b6:f8:26:5d:0b:bb:b0:af:4d:7e:ee:f8:22:cc:18:
                    7f:b7:a4:b4:12:c1:78:34:ed:29:30:b3:fa:93:97:
                    04:4c:a2:32:3b:f4:cb:98:52:6f:ea:11:ab:01:8d:
                    03:b6:d3:b4:cb:0e:f8:3d:cf:2f:ae:3b:51:c9:1d:
                    16:15:e2:d6:cc:8b:35:8e:df:70:c2:c5:18:b7:8f:
                    9f:42:a3:d9:99:55:c0:74:f3:ab:40:98:d0:0a:4d:
                    99:12:2e:92:5b:d6:d3:d6:73:2c:01:76:96:ea:8d:
                    fd:d5
                Exponent: 65537 (0x10001)
        Attributes:
            unstructuredName         :unable to print attribute
            challengePassword        :unable to print attribute
    Signature Algorithm: sha1WithRSAEncryption
         0b:5c:f4:d5:ae:f3:4a:4b:9b:d2:8e:e6:cd:b6:20:2c:9d:61:
         57:f3:9d:7f:95:03:71:9e:95:1b:4c:8f:ad:f8:f9:6c:c3:a6:
         32:be:6a:b9:bf:45:81:0a:6f:6d:3c:29:f6:90:00:81:73:ac:
         65:8d:19:ea:39:86:5d:8f:2b:d7:bf:2f:02:63:01:bb:87:0f:
         dd:3d:81:b2:3c:72:1c:d4:ad:9e:ba:35:e6:41:f2:2f:fb:b8:
         0e:9f:5d:26:2b:52:37:a3:7f:97:b0:35:78:a6:d4:5a:4f:df:
         32:15:9f:45:43:04:95:4e:f4:d6:71:68:57:59:b2:5b:28:e3:
         13:73:96:c8:cf:c1:df:56:e4:b0:f2:d9:ee:e2:67:7a:37:d2:
         ba:f6:17:9e:ca:6a:b2:96:6d:e8:bb:cf:ff:17:13:fb:cc:d6:
         05:95:c2:4b:f9:49:b9:67:d8:c3:39:c9:78:00:56:20:6f:d4:
         2c:5c:66:c7:a0:1b:bd:2f:5d:c7:8b:98:69:93:67:be:44:f6:
         84:b9:8b:ec:45:1b:be:b8:5b:e9:94:00:2f:1c:30:ad:5f:c1:
         57:3c:f9:11:e0:49:85:bd:93:e6:09:54:aa:94:d5:31:b4:89:
         40:8d:c3:b8:e7:f9:80:d7:71:62:dd:51:88:71:51:ed:8f:b4:
         5e:12:93:3a

在確認 CSR 內容正確後，就可以將 CSR 傳送到公認且有公信力的 CA 單位，並請求該單位為此 CSR 產生憑證 (Certificate)。一旦取得 CA 為此 CSR 產生的憑證後, 就可以將它安裝在需要支援 SSL 的伺服器上。

但是，如果只是開發階段需要測試，或只是自己的想要使用並不是要公開對外支援 SSL時候，可以自行產生一個所謂 Self-signed 的憑證。產生 Self-signed 憑證的方式如下：

~$ openssl x509 -req -days 365 -in CSR.csr -signkey private.key -out self-signed.crt

以下是執行後的輸出畫面, 會要求輸入Pass phrase 來取得 private.key 進行 sign 憑證的處理。最後產生一個 PEM 格式的憑證內容在 self-signed.crt 檔案中
Signature ok
subject=/C=TW/L=Taipei/O=ijeCorp/OU=Security/CN=www.ijecorp.com/emailAddress=miller.lai@gmail.com
Getting Private key
Enter pass phrase for private.key:

PEM格式的 self-signed.crt 的內容類似如下：
-----BEGIN CERTIFICATE-----
MIIDgjCCAmoCCQCQyr2MuBjL8jANBgkqhkiG9w0BAQUFADCBgjELMAkGA1UEBhMC
VFcxDzANBgNVBAcMBlRhaXBlaTEQMA4GA1UECgwHaWplQ29ycDERMA8GA1UECwwI
U2VjdXJpdHkxGDAWBgNVBAMMD3d3dy5pamVjb3JwLmNvbTEjMCEGCSqGSIb3DQEJ
ARYUbWlsbGVyLmxhaUBnbWFpbC5jb20wHhcNMTQwMzEyMDEzODU2WhcNMTUwMzEy
MDEzODU2WjCBgjELMAkGA1UEBhMCVFcxDzANBgNVBAcMBlRhaXBlaTEQMA4GA1UE
CgwHaWplQ29ycDERMA8GA1UECwwIU2VjdXJpdHkxGDAWBgNVBAMMD3d3dy5pamVj
b3JwLmNvbTEjMCEGCSqGSIb3DQEJARYUbWlsbGVyLmxhaUBnbWFpbC5jb20wggEi
MA0GCSqGSIb3DQEBAQUAA4IBDwAwggEKAoIBAQCy+8lfTA8qEdeBBanmQUM1t0e6
vlhCMq3pmb7Igldzyods+ZAVHUptzPyB4i7CH+39rkXNzslsQ/FH76qN+OMyUhCA
2wq1+r6Rh5QIV4aOa4b2YwUtUzzDTEitTe7y3nxonfcBW6GZLmlguLFZTNhpes9H
uzzGb12ZCF3oXr004lIAnHBiiUuqxozXDaD81x2/GJrU4rb4Jl0Lu7CvTX7u+CLM
GH+3pLQSwXg07Skws/qTlwRMojI79MuYUm/qEasBjQO207TLDvg9zy+uO1HJHRYV
4tbMizWO33DCxRi3j59Co9mZVcB086tAmNAKTZkSLpJb1tPWcywBdpbqjf3VAgMB
AAEwDQYJKoZIhvcNAQEFBQADggEBAIqbY8rKAJ40JIXmtJJSWrLzZ5R9OXyxKWHy
N/8Szn8oLMeSPX6Fmd2oWGbJEDuHf17l9IkbKnfDIrlW+lbVG4qY2fZmH5GA2rmP
bWMrIzXqH+NJfp9NyUhhCCT59fDrHKiGf13opR8gvOo2ft0GOQ+kZsUn/7t1GoQ9
3Ybch2CNjfob5sEQ+nGDsyg3IRFnunAzeAdKLS9h4BwZOdz2lvVnHNR4Wb/TygDZ
mVL2ntg2uWCWQvJ5QCZlyjXthtp0EeDNiJeL3ThOlsiKujuhjMrqjThZuGqvpVxO
3v46/+iqCkdGuP/C2mZqJwbNYvOoPCBCeBYMXGpDrC2VqwYULy4=
-----END CERTIFICATE-----

此外，如果想要直接從 private key 產生 self-signed 憑證也是可以, 執行的指令如下：

~$ openssl req -new -x509 -days 365 -key private.key -out self-signed-2.crt

但是, 因為 Self-signed 憑證並不是透過公認與具有公信力的 CA 所發行的憑證。因此，當 Web 伺服器是安裝 Self-signed 的憑證來支援 SSL時，一般不同的瀏覽器在第一次瀏覽此網站時，遇到 self-signed 憑證時, 會跳出類似如下圖的畫面。



無論你是透過 CA 取得憑證或是自行產生 self-signed 的憑證, 都可以透過 openssl 指令來檢測憑證的內容，透過以下的指令：
~$ openssl x509 -text -in self-signed.crt -noout

執行後輸出的憑證內容如下，因為它是 self-signed 的憑證，所以只會有基本的資訊：
Certificate:
    Data:
        Version: 1 (0x0)
        Serial Number: 10433359898838879218 (0x90cabd8cb818cbf2)
    Signature Algorithm: sha1WithRSAEncryption
        Issuer: C=TW, L=Taipei, O=ijeCorp, OU=Security, CN=www.ijecorp.com/emailAddress=miller.lai@gmail.com
        Validity
            Not Before: Mar 12 01:38:56 2014 GMT
            Not After : Mar 12 01:38:56 2015 GMT
        Subject: C=TW, L=Taipei, O=ijeCorp, OU=Security, CN=www.ijecorp.com/emailAddress=miller.lai@gmail.com
        Subject Public Key Info:
            Public Key Algorithm: rsaEncryption
                Public-Key: (2048 bit)
                Modulus:
                    00:b2:fb:c9:5f:4c:0f:2a:11:d7:81:05:a9:e6:41:
                    43:35:b7:47:ba:be:58:42:32:ad:e9:99:be:c8:82:
                    57:73:ca:87:6c:f9:90:15:1d:4a:6d:cc:fc:81:e2:
                    2e:c2:1f:ed:fd:ae:45:cd:ce:c9:6c:43:f1:47:ef:
                    aa:8d:f8:e3:32:52:10:80:db:0a:b5:fa:be:91:87:
                    94:08:57:86:8e:6b:86:f6:63:05:2d:53:3c:c3:4c:
                    48:ad:4d:ee:f2:de:7c:68:9d:f7:01:5b:a1:99:2e:
                    69:60:b8:b1:59:4c:d8:69:7a:cf:47:bb:3c:c6:6f:
                    5d:99:08:5d:e8:5e:bd:34:e2:52:00:9c:70:62:89:
                    4b:aa:c6:8c:d7:0d:a0:fc:d7:1d:bf:18:9a:d4:e2:
                    b6:f8:26:5d:0b:bb:b0:af:4d:7e:ee:f8:22:cc:18:
                    7f:b7:a4:b4:12:c1:78:34:ed:29:30:b3:fa:93:97:
                    04:4c:a2:32:3b:f4:cb:98:52:6f:ea:11:ab:01:8d:
                    03:b6:d3:b4:cb:0e:f8:3d:cf:2f:ae:3b:51:c9:1d:
                    16:15:e2:d6:cc:8b:35:8e:df:70:c2:c5:18:b7:8f:
                    9f:42:a3:d9:99:55:c0:74:f3:ab:40:98:d0:0a:4d:
                    99:12:2e:92:5b:d6:d3:d6:73:2c:01:76:96:ea:8d:
                    fd:d5
                Exponent: 65537 (0x10001)
    Signature Algorithm: sha1WithRSAEncryption
         8a:9b:63:ca:ca:00:9e:34:24:85:e6:b4:92:52:5a:b2:f3:67:
         94:7d:39:7c:b1:29:61:f2:37:ff:12:ce:7f:28:2c:c7:92:3d:
         7e:85:99:dd:a8:58:66:c9:10:3b:87:7f:5e:e5:f4:89:1b:2a:
         77:c3:22:b9:56:fa:56:d5:1b:8a:98:d9:f6:66:1f:91:80:da:
         b9:8f:6d:63:2b:23:35:ea:1f:e3:49:7e:9f:4d:c9:48:61:08:
         24:f9:f5:f0:eb:1c:a8:86:7f:5d:e8:a5:1f:20:bc:ea:36:7e:
         dd:06:39:0f:a4:66:c5:27:ff:bb:75:1a:84:3d:dd:86:dc:87:
         60:8d:8d:fa:1b:e6:c1:10:fa:71:83:b3:28:37:21:11:67:ba:
         70:33:78:07:4a:2d:2f:61:e0:1c:19:39:dc:f6:96:f5:67:1c:
         d4:78:59:bf:d3:ca:00:d9:99:52:f6:9e:d8:36:b9:60:96:42:
         f2:79:40:26:65:ca:35:ed:86:da:74:11:e0:cd:88:97:8b:dd:
         38:4e:96:c8:8a:ba:3b:a1:8c:ca:ea:8d:38:59:b8:6a:af:a5:
         5c:4e:de:fe:3a:ff:e8:aa:0a:47:46:b8:ff:c2:da:66:6a:27:
         06:cd:62:f3:a8:3c:20:42:78:16:0c:5c:6a:43:ac:2d:95:ab:
         06:14:2f:2e

以下我們來觀察一個由公開 CA 所 signed 過的憑證內容, 有關 X509v3 extensions 的部分：
Certificate:
    Data:
        Version: 3 (0x2)
        Serial Number:
            18:7a:a9:a8:c2:96:21:0c
        Signature Algorithm: sha256WithRSAEncryption
        Issuer: C=US, O=Apple Inc., OU=Apple Certification Authority, CN=Apple Root CA
        Validity
            Not Before: Feb  1 22:12:15 2012 GMT
            Not After : Feb  1 22:12:15 2027 GMT
        Subject: CN=Developer ID Certification Authority, OU=Apple Certification Authority, O=Apple Inc., C=US
        Subject Public Key Info:
            Public Key Algorithm: rsaEncryption
            RSA Public Key: (2048 bit)
                Modulus (2048 bit):
                    00:89:76:4f:06:5b:9a:41:ee:a5:23:2b:02:a3:5f:
                    d7:73:3f:c0:35:b0:8b:84:0a:3f:06:24:7f:a7:95:
                    3f:eb:4f:0e:93:af:b4:0e:d0:c8:3e:e5:6d:18:b3:
                    1f:e8:89:47:bf:d7:09:08:e4:ff:56:98:29:15:e7:
                    94:9d:b9:35:a3:0a:cd:b4:c0:e1:e2:60:f4:ca:ec:
                    29:78:45:69:69:60:6b:5f:8a:92:fc:9e:23:e6:3a:
                    c2:22:b3:31:4f:1c:ba:f2:b6:34:59:42:ee:b0:a9:
                    02:03:18:91:04:b6:b3:78:2e:33:1f:80:45:0d:45:
                    6f:bb:0e:5a:5b:7f:3a:e7:d8:08:d7:0b:0e:32:6d:
                    fb:86:36:e4:6c:ab:c4:11:8a:70:84:26:aa:9f:44:
                    d1:f1:b8:c6:7b:94:17:9b:48:f7:0b:58:16:ba:23:
                    c5:9f:15:39:7e:ca:5d:c3:32:5f:0f:e0:52:7f:40:
                    ea:be:ac:08:64:95:5b:c9:1a:9c:e5:80:ca:1f:6a:
                    44:1c:6c:3e:c4:b0:26:1f:1d:ec:7b:af:5e:a0:6a:
                    3d:47:a9:58:12:31:3f:20:76:28:6d:1d:1c:b0:c2:
                    4e:11:69:26:8b:cb:d6:d0:11:82:c9:4e:0f:f1:56:
                    74:d0:d9:08:4b:66:78:a2:ab:ac:a7:e2:d2:4c:87:
                    59:c9
                Exponent: 65537 (0x10001)
        X509v3 extensions:
            X509v3 Subject Key Identifier: 
                57:17:ED:A2:CF:DC:7C:98:A1:10:E0:FC:BE:87:2D:2C:F2:E3:17:54
            X509v3 Basic Constraints: critical
                CA:TRUE
            X509v3 Authority Key Identifier: 
                keyid:2B:D0:69:47:94:76:09:FE:F4:6B:8D:2E:40:A6:F7:47:4D:7F:08:5E

             X509v3 CRL Distribution Points: 
                URI:http://crl.apple.com/root.crl

             X509v3 Key Usage: critical
                Digital Signature, Certificate Sign, CRL Sign

 其中幾個比較重要的 X509 Extensions 相關說明如下：
X509v3 Basic Constraints 指定這個憑證是否屬於CA，另外是否為 critical 的限制。
例如：
X509v3 Basic Constraints: critical
    CA:TRUE

X509v3 Key Usage 指定這個憑證可以用來做什麼。
例如：

X509v3 Key Usage: critical
    Certificate Sign, CRL Sign

X509v3 Extended key Usage 指定這個憑證可以用在什麼操作上。
例如：
X509v3 Extended Key Usage: critical
    TLS Web Server Authentication, TLS Web Client Authentication

X509v3 CRL Distribution Points 指定CA所提供的 Revocation List 要去哪邊找。如果這個憑證是每隔一段時間就會更換的話，那麼這個設定就會非常重要。
例如：
X509v3 CRL Distribution Points: 

    Full Name:
      URI:http://www.apple.com/appleca/root.crl

X509v3 Certificate Policies 指定這個憑證是基於什麼 Policy 所簽發出來的。
例如：
X509v3 Certificate Policies: 

    Policy: 1.2.840.113635.100.5.1

      CPS: https://www.apple.com/appleca/

      User Notice:

        Explicit Text: Reliance on this certificate by any party assumes acceptance of the then applicable standard terms and conditions of use, certificate policy and certification practice statements.

Authority Information Access 是用來提供額外的CA資訊，以及即時驗證 certificate revocation的資料。而OCSP是指 CA's Online Certificate Status Protocol 的回應者 (responder)。
例如：
Authority Information Access:
    OCSP - URI: http://ocsp.starfieldtech.com/
    CA Issuers - URI:http://www.cert.com/resp/intermediate.crt

X509v3 Subject Key Identifier 主要在於表示這個 Certificate 包含一個特定的 Public Key。所有的CA Certificate都應該包含這個 extension, 由同一個 CA 所發出來的這些 Certificate 也要包含一個  X509v3 Authority Key Identifier 的 extension , 而它的值會和這個CA 的 Subject Key Identifier 一樣。

 X509v3 Authority Key Identifier 指定這張 Certificate 是由哪一個 CA 所發出來的。

 以下我們可以透過觀察 Facebook網站使用的 HTTPS Certificate來了解 Authority Key Identifier 和 Subject Key Identifier 的關係。








Root CA 是 DigCert  High  Assurance  EV Root CA 憑證的 Subject Key Identifier 和 Authority Key Identifier 分別如下：

X509v3 Subject Key Identifier: 
    B1:3E:C3:69:03:F8:BF:47:01:D4:98:26:1A:08:02:EF:63:64:2B:C3

 X509v3 Authority Key Identifier: 

    keyid:B1:3E:C3:69:03:F8:BF:47:01:D4:98:26:1A:08:02:EF:63:64:2B:C3

Root CA 所簽發的 Intermediate CA - DigiCert SHA2 High Assurance Server CA 憑證的 Subject Key Identifier 和 Authority Key Identifier 分別如下：

 X509v3 Subject Key Identifier: 
    51:68:FF:90:AF:02:07:75:3C:CC:D9:65:64:62:A2:12:B8:59:72:3B

 X509v3 Authority Key Identifier: 
    keyid:B1:3E:C3:69:03:F8:BF:47:01:D4:98:26:1A:08:02:EF:63:64:2B:C3

最後，由  Intermediate CA 所簽發的最後給Facebook的Web Server的憑證的 Subject Key Identifier 和 Authority Key Identifier 分別如下：

X509v3 Subject Key Identifier: 
    43:09:93:40:FA:11:4B:30:33:EC:F2:87:6E:8D:71:18:CF:8A:BC:8E

 X509v3 Authority Key Identifier: 
    keyid:51:68:FF:90:AF:02:07:75:3C:CC:D9:65:64:62:A2:12:B8:59:72:3B

在 verify certificate chain 過程中，Facebook 的 Web Server憑證中的 Authority Key Identifier  必須要對應到 Intermediate CA憑證的 Subject Key Identifier 。而 Intermediate CA憑證的 
Authority Key Identifier 必須要對應到 Root CA 憑證的 Subject Key Identifier。

 而 Root CA憑證中的Authority Key Identifier 則是對應自己的Subject Key Identifier  。

最後，Certificate Chain 的存放順序必須是如下所示，Root CA一定是放在最下方，再依據簽發的順序置放：

 -----BEGIN CERTIFICATE-----
Server certificate
-----END CERTIFICATE-----
-----BEGIN CERTIFICATE-----
Intermediate certificate
-----END CERTIFICATE-----
-----BEGIN CERTIFICATE-----
Root CA's certificate
-----END CERTIFICATE-----

Reference:
[1] Standard X.509 V3 Certificate Extensions
[2] Check Certificate Chain
[3] Creating a .pem File for SSL Certificate Installations
[4] CA建置工具：Openssl的管理與使用介紹（上）
[5] How to create SSL X.509 Certificate ?
[6] OpenSSL Cookbook

張貼者： 於 沒有留言:
標籤： , , , , , , , , , , , , ,

2014年2月19日 星期三

關於 rsync algorithm 演算法


        因為專案需要, 我希望能夠稍微了解真正底層用到的rsync技術, 所以我選讀的這篇文章就是位於澳洲首都特區坎培拉的研究型國立大學, 由 Andrew Tridgell 和 Paul Mackerras 在 1996 年6月所發表 The rsync algorithm [1]這篇技術報告. 而 Andrew Tridgell 在 1999年的2月發表了博士論文 Efficient Algorithms for Sorting and Synchronization [2]. 而目前在 Linux/Unix 底下使用的 rsync [4] 指令是由 Wayne Davison 所維護. 而知名的 Dropbox 服務底層則是改良自 librsync [5].

        而這篇文章, 我主要是著重在於技術報告中提到的 Rolling Checksum 和 Checksum searching 的部份. 由於我並不是資工系畢業的, 也沒學過工程數學或是一些高深的數學演算法, 因此看這篇技術報告時, 只能搭配程式碼來研讀. 網路上其實有不少介紹 Rolling Checksum的文章, 也有對岸簡體文章在說明這部份. 但, 後來找到一個網站是 Jakob Jenkov 所寫的 RSync - Remote Synchronization Protocol [3] 中的 Checkums 章節. 才能比較理解 Rolling checksum 作法的好處, 以及如果要實作 Rolling Checksum 應該怎樣實作. 接著陸續找到一些網路上實作 Rolling checksum 的程式碼研讀後, 對於 Rolling Checksum 就比較能夠掌握.

The rsync algorithm:
        假設有兩台分別為 α 和 ß 的電腦.  α 電腦存取一個檔案 A, 且 ß 電腦存取一個檔案 B. 當檔案 A和檔案 B 具有類似的相同內容時. 在 α 和 ß 電腦之間要同步這個檔案時,可以透過 rsync 演算法來解決每次都要完整傳送整份檔案的困擾. rsync 演算法包含 5 個步驟
  1.  ß 將檔案 B 分割成一系列不重疊的固定大小的區塊(Block), 區塊大小(Block size)的為 S bytes. 最後一個區塊的大小可能會小於 S bytes.
  2.  ß 會把每一個區塊計算出兩個 checksums: 一個稱作 weak "rolling" 32-bits checksum. 另一個是 strong 128-bit MD4 checksum.
  3. 接著 ß 將這些 checksums 都送給  α .
  4. α 會對於檔案 A 中尋找在任何 offset 上所有大小 S bytes的區塊是否有相同的 weak and strong checksum 和 ß 所提供的相同. 這是透過 rolling checksum 的特性, 所以速度相當快.
  5. 最後, α 會傳送一連串的intructions給 ß 來建構出檔案A的複製版本. 每一個 instruction 都會是參照到檔案 B的一個區塊或是 literal data. Literal data 指的是那些在檔案 A 中出現, 但是不符合檔案 B中任何一個區塊的資料. 
        最後,  ß 將會得到一個完整的檔案A的複製, 但是 α 只需要傳送部份檔案A中不存在於檔案B的資料 literal data 給 ß 就可以了. 

Rolling checksum:
        基本上, 如果你是學數學或是資工背景的, 看技術報告 Rolling checksum 章節的定義, 應該就完全能夠理解它所提的 weak rolling checksum 是怎樣運作的.

        在開始解釋它之前, 我們先回到前面 rsync algorithm 的第4個步驟, α 必須對於檔案A 中在任何 offset 上所有大小 S bytes 的區塊, 尋找是否有和  ß 所提供的區塊有相同的 weak and strong checksum. 假設, 檔案 A 的大小為 10 個 bytes, 而 ß 所提供的區塊大小 S 為 4 bytes 的資料給 α . 這時 α 必須從第 0 個 byte 開始比對且必須依序移動每一個 byte 後抓4個bytes的資料來比對, 最差的情況要6次才能比對完一個 ß 所提供第一個區塊資料. 請參考如下圖:


        透過前面這一個簡單的圖示, 我們可以知道, 如果檔案Ａ的資料很大時候,要比對完 ß 所提供的不同區塊, 它會是一個大量的資料運算.

        現在, 回到技術報告中所節錄的 Rolling checksum 定義如下:


        Rolling checksum 是由兩個值計算後所組成, 分別為 a (k, l) 和 b(k, l). 一個區塊的 block 的 Rolling checksum 可以用 s (k, l) 來表示. 而 s (k, l) = a (k, l) + (2^16)* b(k, l).  為了方便解釋, 這裡先會忽略掉 mod M 的部分. 此處我們可以節錄自 Jakob Jenkov 寫的 RSync - Remote Synchronization Protocol [3] 中的 Checkums 章節 中 Rolling Checksum Algorithm 的解釋, 以下的 A 其實就是表示 a(k, l), 而 B 就是表示 b(k, l).
data = 是指一個區塊(block)的資料
i    = index 是區塊上表示每一個 byte 的位置. 如果區塊大小為 4 bytes, 即 blockSize = 4.
       則 i = 0, 1, 2, 3
        
a(k,l)即是 A = data[0] + data[1] + ... data[i];

b(k,l)即是 B = blockSize * data[0] + (blockSize-1) * data[1] + ... +
              (blockSize - i) * data[i] ... + 1 * data[blockSize-1];
        假設有一個區塊大小 4 bytes 的資料如下, 這個區塊的每個byte的值分別為 3, 5, 7, 9. 根據定義計算 A = a(0, i) 和 B = b(0, i) 的方式分別如下：
         而這個特性, 透過觀察可以得到 B 其實是每次的累加 A 所組成
A += data[i];
B += A;
        在 Jakob Jenkov 所寫的 RSync - Remote Synchronization Protocol [3] 中的 Checkums 章節 裡面有提到為什麼 A+= data[i] 後, 要算出 B只要用 B += A; 即可求出.

        因此, 當我們要移動 1 個 byte 來計算下 1 個 4 bytes長度區塊的 Rolling checksum 時, 我們並不需要重新完整算一次. 只需要知道下 1 個 byte的值. 就可以求出來 A 和 B 的值. (以下節錄自Jakob Jenkov的文章 )
start = start index of new block.
end   = end index of new block.  

A -= data[start-1];   //remove old, first byte.
A += data[end];       // 算出新的 A

B -= blockSize * data[start-1];
B += A;               // 算出新的 B
Checksum searching:

        根據技術報告中提到的 checksum searching, 它可以分為 3 個 Level 的 searching方式, 我用以下這張概念圖來解釋它.

        當 α 收到 ß 傳送過來的 checksums 資料時候, 會建立一個大小為 2^16的 Hash Table , 而每個 key 所存的值就是表示一個區塊 32 bits長度 Rolling checksum 的 hash值, 長度為 16 bits. 而 Hash Table每個 key 對應的 entry 可能會指向 null 也可能會指向一個 list 的資料. 這個 list 中的 Node 包含 Rolling Checksum 以及一個 Strong Checksum. 比對的方式如下:
  1. 從A檔案中第 0 個byte開始, 抓出 block size大小的區塊算出 rolling checksum 以及 rolling checksum的 hash值. 如果 hash 值有符合就表示通過了 Level 1的 Check.
  2. 當 Level 1 Check 通過後, 開始找 list 中的node比較其 rolling checksum是否符合.若有則表示通過 Level2 Check.
  3. 一旦 Level2 Check通過, 就要把A檔案中的這個完整區塊的 strong checksum算出來和 node中的 Strong checksum 比對. 
        如果這個offset所取出的區塊在比對過程中有找到符合的, α 就要把目前 offset 以及對應到檔案 B 中的哪一個 block的資訊記錄下來, .如果完全都沒有比對到, 則繼續移動1個byte抓出相同 block size的區塊再比對一次.直到檔案A的所有區塊都比對過為止.

        另外, 以上這張概念圖中 Hash Table 的 key值是排序過的, 這和我們一般所熟知的 Hash Table的是稍微不同的.在 Efficient Algorithms for Sorting and Synchronization [2]論文中的 3.2 章節有一張圖如下, 這才是原作者在 rsync 中所實作的方式.


Reference:

張貼者： 於 3 則留言:
標籤： , ,

2014年1月8日 星期三

儲存 Password 安全性

Password

        Password 是大部份系統用來認證或是識別使用者最常見的方式，特別是網站系統最需要這種機制，來提供一般使用者進行登入取得瀏覽的權限或是使用網站的服務。網站系統最常見的保護方式就是在網頁上提供隨機的圖形驗證碼 CAPTCHA ，來避免有心人透過工具作自動化的方式暴力破解使用者的密碼。然而，一個系統的安全性取決於系統環節中最弱的一環。因此，擋得住網站系統前端，卻擋不住系統後端資料庫時，一旦被攻破資料庫時，若使用者的密碼沒有被保護而以明文(Plain-Text)的方式儲存時，這樣的系統可以說是完全沒有任何安全性。因此，比較有良心的開發人員，會透過其他方式來保護使用的密碼。

早期 Password 的保護方式

        早期對於Password的保護方式是透過 password + salt 方式，把這兩個值當作參數進行 Hash 運算(MD5, SHA1,SHA256...etc)，每一個 password 都需要搭配一個隨機產生的 salt，並且透過 One-way 的 Hash 函數算出一個亂數值的字串來存放。所謂的 One-way 的 Hash 函數是指無法透過知道 salt 和產生後的亂數值算出原本的 password。對於這方面的技術有興趣的可以參考 Slated Password Hashing 的文章。在過去硬體的運算能力不夠快的情況下，這樣的保護機制其實是足夠的。然而運算能力越來越強的情況下，這種保護機制隨即崩盤，請參考2012年Speed Hashing 的文章，裡面主要是提到GPU運算能力可以很容易的破解 SHA1+Salt 所保護的密碼。

建議的 Password 的保護方式

        目前(2013)在密碼學領域建議用來保護密碼的 key derivation function 我目前知道的有以下這幾種： scrypt, bcrypt, PBKDF2. 之前的專案曾經用Python版本的 bcrypt 來做 Password Protection的處理.

Reference

Using scrypt in Python and PostgreSQL - http://kevinryan.me/using-scrypt-in-python-and-postgresql/


張貼者： 於 沒有留言:
標籤： , , , , , ,

Threat Modeling


        Threat Modeling 是在系統設計階段的早期, 以 Data Flow Diagram 為基礎, 來對整個系統設計做安全性威脅的分析. 而這個過程是一個重複的過程, 透過重複分析安全性的威脅, 並且提出相對應的解決方式,並且解加以驗證是否解決或是降低威脅性.

        然而, 它不僅只是在設計階段, 當系統增加功能或是改變原有的功能時, 也可以利用它來分析系統的變動是否出現安全性的威脅.



為了做 Threat modeling 的分析, 我們必須先將系統的 Data Flow Diagram 畫出來. 這個可以藉由微軟所提供的工具 SDL Threat Modeling Tool 來完成 Data Flow Diagram 以及後續的分析.

Data Flow Diagram (DFD)

        基本上 Data Flow Diagram 可以根據不同情況來畫出對應的 DFD. 並且依據每個DFD來進行分析. Data Flow Diagram 主要有 5 個 Elements 如下:
  • Process
    以 High Level 的角度來看時, 它可以是Web Services或是在作業系統上的一個Service. 以 Detail Level 的角度上來看可以是一個DLLs或是一個EXEs的執行檔.
  • Data Store
    通常指的是存放資料的地方, 常見的有資料庫,檔案或是Shared Memory甚至是Queue或Stack.
  • External Entity
    通常指的是會與你的系統互動的使用者或是外部的 Systems 或 Services.
  • Data Flow
    就是指以上 3 種 Elements: Process,External Entity以及 Data Store之間溝通的資料流.
  • Trust Boundary
    是指不容易受到外部影響或是干涉內部運作的一個範圍的分界. 例如: 都在同一個Private Data Center 內部之間的Server溝通. 例如: 透過網路溝通的兩個 processes 通常會有一個 trust boundary 在它們之間, 即使他透過安全的通訊方式也是如此. 


        而畫 Data Flow Diagram 最重要的一個是畫出 Trust Boundary, 它主要的目的是用來判斷哪些 Data Flow的運作是具有安全性威脅.  舉例來說: 一個 Process 內部的 Thread 通常都算是 Trust Boundary 內的, 原因是 Thread 所擁有的權限都是由 Process 所提供且共享的. 常見的 Trust Boundary 例子有 Machine boundaries, privilege boundary, integrity boundary ...等等這些.
       
        此外, 我們也應該要檢視每一個 Processes 和 Data Stores 是否需要再進一步畫出更詳細的 DFD. 所以 DFD 通常又可以分為以下四種, 但是很少需要畫到 Leve 3, 大多只需要畫到 Level 2 就已經可以.

  • Context Diagram
    非常 high-level 完整的 component 或是 product, system 之間的互動
  • Level 1 Diagram
    High level 但是只針對某一個單一的功能或是情況的互動
  • Level 2 Diagram
    多個功能中需要用到的 sub-component 比較詳細的部份
  • Level 3 Diagram
    更為詳細部分

        最後, DFD 應該詳細條列出對應的假設或是相依性的關係. 一開始可以先以 High Level 的方式畫出 DFD, 之後可根據是否需要更詳細的解釋說明安全性在設計上的影響, 或是需要資料通過 trust boundary 的細節...etc. 來決定是否畫出更詳細的 Level 1 ~ Level 3 的 DFD.

        畫 DFD 時候, 需要透過以下幾個問題來驗證你的 DFD 能夠拿來做 threat modeling 分析.
  • Data 如何產生? 來自於 external entities 還是來自於 data stores
  • Data 用在什麼地方? 誰會使用它? 儲存這些資料的理由?
  • Data 如何在不同的 Process 中傳遞.
  • Data 被哪些 Process從 Data Store 存取

Identify Threats

        如果有安全性的專家參予其中分析是最好的, 如果沒有的話,可以透過 STRIDE 的步驟來檢視 DFD 中的每個 element. STRIDE 就是指以下這些:
  • Spoofing 偽造
    例如: 申請類似的網址,偽裝某個知名的網站
  • Tampering 竄改
    例如: 修改軟體所需要的DLL植入惡意程式,或是竄改封包的內容
  • Repudiation 否認
    例如: 否認發送過某個 Email, 或拒絕承認瀏覽過某個網站
  • Information Disclosure 資訊外洩
    例如: 無論是惡意或是無意, 將重要的客戶資料流出, 讓未經授權的人使用.
  • Denial of Service 中斷服務
    例如: 系統無法運作, 或是網站無法服務
  • Elevation of Privilege 提高權限
    例如: 讓一個遠端一般使用者,透過非正常的管道,提升權限能夠執行一些只有系統管理員才能使用的指令集.
        對於DTD中的每一個Element而言, 都有個別需要注意的威脅如下圖:

張貼者： 於 沒有留言:
標籤： ,
訂閱： 文章 (Atom)