Confidentiality with Symmetric Encryption

Symmetric encryption

  • 提供傳輸中或儲存資料的 confidentiality (機密性)
  • 又稱為 Conventional encryption or single-key encryption
  • 安全條件:
    • 強大的加密演算法
      • 在已知部分對應組合 (plaintext–ciphertext pairs) 以及演算法的情況下，仍無法解出明文 (ciphertext) 或是 金鑰 (key)
    • 安全的金鑰分發與管理
  • Model (Five major components)

Attacking Symmetric Encryption

  • Cryptanalytic Attacks

    • 利用:
      • 演算法本身的特性
      • 明文的一般特性
      • 一些明文與密文的對應樣本 (plaintext–ciphertext pairs)
    • 推導出特定的明文或加密金鑰

  • Brute-Force Attacks

    • 利用:
      • 對可能明文的了解
    • 對某些密文嘗試所有可能的金鑰
      • 直到產生可理解的明文
      • 平均需要嘗試所有可能金鑰的一半

Symmetric Block Encryption Algorithms

最常見的對稱式加密方式

  • 將固定大小的明文區塊 (plaintext blocks) 轉為相同大小的密文區塊 (ciphertext blocks)

Data Encryption Standard (DES)

Adopted in 1977 by the NIST (FIPS PUB 46)

  • 曾經是最廣泛使用的加密方案，又稱為 Data Encryption Algorithm (DEA)
  • 64-bit 明文區塊 / 56-bit 金鑰 → 64-bit 密文區塊
  • 安全性問題:
    • 56 bit 金鑰太短
      • 在今天的處理器速度下不足以抵抗暴力破解

Triple DES (3DES)

Part of the DES in 1999: FIPS PUB 46-3

  • 將 DES 演算法重複執行 3 次，並使用 2 or 3 把不同的金鑰
  • 金鑰長度 112 or 168 bits
  • 優點:
    • 金鑰長度足夠抵抗暴力破解 (168-bit)
    • 直接使用 DES 的結構，可以沿用原有的硬體或系統
  • 缺點:
    • 速度慢 (需要執行三次 DES)
    • 區塊大小只有 64 bit，效率低且安全性不足

Advanced Encryption Standard (AES)

NIST Selected Rijndael Algorithm in Nov. 2001: published as FIPS 197

  • 現在已被廣泛應用在商業產品中
  • 作為 3DES 的替代方案 (3DES 不適合長期使用)

統整

  • 實務上的安全問題
    • 如何將對稱式加密應用到大於單一區塊的資料

Other Encryption Algorithms

Electronic codebook (ECB)

解決之前提到的問題

  • Multiple block encryption
  • 每個區塊使用相同的金鑰加密
  • 安全問題: 可能會產生規律

Cipher Block Chaining (CBC)

解決 ECB 的問題

  • Five modes of operation defined by NIST
    • ECB, CBC,…

Stream Cipher

  • 比較
特性 Block Cipher Stream Cipher
處理方式 一次一個 block 連續處理
單位 固定大小 (64 / 128 bit) bit / byte
優點 金鑰可重複使用 速度快 (XOR 運算)
應用 檔案、資料庫 即時通訊

Message Authentication and Hash Functions

  • Message (data) authentication
    • 通信雙方可以確認收到或儲存的訊息是真實的 (authentic)
    • 防止資料或交易被偽造
  • 驗證的主要面向
    • Message contents: 沒有被修改
    • Message source: authentic
  • 其他面向
    • Message timeliness/sequence: 確保訊息沒有被延遲或重播

Message Authentication without Encryption

  • 訊息驗證是獨立於訊息加密的功能
    • ex: 廣播訊息給多個接收者
    • 不是所有接收者都能解密訊息
    • 如果使用加密，會浪費處理器資源
  • 為每個訊息生成並附加驗證標籤 (auth. tag)
    • Message Authentication Code (MAC)
    • One-Way Hash Function

MAC

  • 假設兩個通信方共享同一個秘密金鑰
  • 使用秘密金鑰生成一個小區塊的資料
  • MAC 演算法:
    • NIST 推薦 DES
    • 將訊息加密後取最後 16 或 32 bit 作為驗證碼
  • 缺點:
    • 加密軟體速度慢
    • 加密硬體成本不可忽略
    • 加密硬體對大資料量較優化
  • 驗證 (Authentication) 不需要可逆 (reversible)
    • 只需要一種方法產生 tag，並讓接收方可以驗證

One-way Hash Function

  • 將任意大小的訊息 MM 轉為固定大小的 Tag H(M)H(M)
  • 與 MAC 的差異:
    • 不需要使用秘密金鑰
  • 函數 HH 的特性:
    • 可以應用於任意大小的資料區塊
    • 輸出長度固定
    • 計算容易: 使得硬體與軟體實作都可行
    • One-way (pre-image resistant)
      • 給定雜湊值 hh，幾乎不可能找到 xx 使 H(x)=hH(x) = h
    • Second pre-image (weak collision) resistant
      • 對於輸入 xx，幾乎不可能找到 y≠xy \neq x 使 H(y)=H(x)H(y) = H(x)
    • Collision (strong collision) resistant
      • 幾乎不可能找到兩個不同輸入 x,yx, y 使 H(x)=H(y)H(x) = H(y)

Security of Hash Functions

  • 攻擊方法
    • Cryptanalysis
      • 利用演算法的邏輯弱點，成功與否取決於演算法本身
    • Brute-force
      • 僅取決於 hash code 長度
  • 對暴力破解的安全強度
    • Preimage resistant: 2n2^n
    • Second preimage resistant: 2n2^n
    • Collision resistant: 2n22^{\frac{n}{2}}
      • Birthday attack on a message digest of size n produces a collision
  • 應用:
    • 訊息驗證
    • 數位簽章
    • 密碼儲存
    • 入侵偵測

Public-Key Encryption

Proposed by Diffie and Hellman in 1976

  • Asymmetric algorithm (非對稱)
  • 基於數學函數
    • 與在位元模式上做簡單運算的 Symmetric algorithms 不同
  • 常見誤解
    • 比對稱加密更安全
    • 是一種通用技術，可以取代對稱加密
    • 金鑰分配容易
  • 使用公鑰加密: 用於保密性 (Confidentiality)
  • 使用私鑰加密: 用於驗證身份與完整性 (Authentication & Integrity)
  • 要求
    • 計算上容易
      • Create key pairs
      • for sender knowing public key to encrypt messages
      • for receiver knowing private key to decrypt ciphertext
    • 對攻擊者計算上不可行，即使攻擊者知道公鑰，也無法:
      • 推算出私鑰
      • 還原訊息
    • 任意一把金鑰都可用於加密

Digital Signatures and Key Management

Digital Signatures

  • 將雜湊值 (hash code) 用私鑰加密
  • 目標:
    • 驗證訊息來源 (Authentication)
    • 確保訊息完整性 (Integrity)
    • 防止訊息被否認 (Non-repudiation)
  • 不提供機密性 (Confidentiality)

Public-key Certificates

Secure distribution of public keys

  • Public key distribution
    • 任何人都可以發布自己的公鑰
    • 安全風險: 可能會有偽造的情況
  • Solution: Public-key certificate
    • Certificate: Public key + user ID of the key owner
    • 憑證由受信任第三方簽署: CA (Certificate Authority)
    • 憑證包含 CA 資訊以及有效期限
  • X.509 標準: 全球通用的憑證標準

Symmetric key exchange

  • Diffie-Hellman key exchange
    • 缺點:
      • 無法驗證通訊雙方身份
      • 提出許多變體來解決此問題

Digital envelopes

distribution of secret keys

  • 保護訊息，但發送者與接收者不用共享相同金鑰
  • 也可用來傳送對稱金鑰

Random and Pseudorandom Numbers

Random Numbers

  • 用於產生:
    • Keys for public-key algorithms
    • Stream keys for symmetric stream cipher
    • Symmetric keys…
  • 要求:
    • Randomness (Statistical Properties)
      • Uniform distribution: 每個數字出現頻率大致相同
    • Unpredictability (Cryptographic Security)
      • 序列中下一個數字無法被預測

Random vs. Pseudorandom

  • Pseudorandom: 廣泛被接受
    • 使用確定性演算法 (Deterministic algorithm) 生成
    • 不是真正隨機，但可以通過統計隨機性測試
  • Random: true random number generator (TRNG)
    • 使用非確定性來源生成隨機數
    • 大多透過測量不可預測的自然現象
      • ex: 輻射、氣體放電…
    • 越來越多現代晶片提供