IT Security 2 (Ch13~Ch15)

Chapter 13: Biometrics

Positive/ Negative Recognition

• Positive recognition: Authentication
  • 系統驗證是不是此人
  • PIN, password, smart card…

  是不是Bob?

• Negative recognition: Identification
  • 系統建立此人是否符合 (即使那個人否認)
  • identifying criminals, social welfare double dippers
  • PIN, password 在此不適合用

  是誰?

Biometric System

• 定義
  • 蒐集biometric data
  • extract a salient(顯著的) feature set
  • 比較 database
  • 執行 action
• Inter/ Intra class variation
  • biometric trait 通常不會百分之百相似
  • 因為
    • 使用者特徵改變
    • 環境改變
    • 使用者和機器互動方式不同
  • Intra-class variation
    • 同個使用者的差異
  • Inter-class variation
    • 不同使用者間的差異
  • Useful features set 通常 Inter 越高 Intra 越低
• Performance Measurement
  • False Accept Rate (FAR) = False Match Rate (FMR)
    • 不是本人卻被接受
  • False Reject Rate (FRR) = False Non-Match Rate (FNMR)
    • 是本人卻被拒絕
  • t: threshold
  • FAR 和 FRR 的取捨被 t 決定
• Receiver Operating Characteristics
  • biometric system 的正確性
  • 根據 FAR 和 FRR 對於不同的 t
• Doddington's zoo
  • Sheep
    • match well
    • low false accepts and false reject rates
  • Goats
    • high false reject rate
  • Lambs
    • high false match rate
  • Wolves
    • good at impersonation
  • 如果可以分類 data，每個data可以被用不同的方式處理
• Failure to enroll rate
  • 衡量為什麼使用者不能被enroll
  • 失敗通常因為 system 拒絕 poor quality inputs
  • 高失敗導致 high quality inputs 但要降低acceptance，使用者要repeat enrollment process

Characteristics

• Universality
  • 每個個體都有的特徵
• Uniqueness
  • 每個個體都不同
• Permanence
  • 長期不變
• Measurability
  • 可取得(acquirable)、可數位化(Digitizable)
• Performance
  • 正確且用需要的資源符合應用限制
• Acceptability
  • 個體願意提供
• Unfakeability (?)
  • 不能偽裝成其他人

Vulnerabilities

• Circumvention (規避)
  • 攻擊者取得database資料並修改
• Covert Acquisition
  • 取得別的使用者的 biometric information
• Collusion and Coercion (強迫)
  • 聯合其他合法使用者
• Denial of Service
  • 拒絕合法的使用者
  • 產生許多 noise 破壞系統
• Repudiation
  • 攻擊者可以說自己資料被偷了 (假裝使用者)

Risks for users

• not secure
  • 不用取得使用者授權就能得到
• cannot be revoked
  • 如果被惡意使用，無法撤回
• secondary use
  • 如果有第二個應用，則自己的identity可能被追蹤

Attacks

• spoofing
  • 假造 biometric sample
    • 使通過
    • 使不通過
• sensors
  • 調包或破壞sensors
• segmentation
  • 使系統只觀察到某特定 features
• replay
  • 攔截 output 再利用
• malware-based attacks
  • 調包extractor
• attacks against feature extraction
  • 如果攻擊者知道algorithm，可以偽造假的features
• attacks against quality control
  • 用 lamb 污染 template data set
  • 以降低 threshold
• data storage
  • template 需要加密
  • 不能 insert 假的資料
  • 不能 unauthorized 刪除
• availability of templates in plaintext
  • 通常需要 plaintext access
  • 與傳統 passwords 的 salted 和 hashed 不同

Spoof Detection

• Fingerprints
  • 用膠假造
  • 偵測：
    • 汗 (persiration)
    • 手的反光度 (reflection)
    • 溫度
    • 脈搏 (pulse)
• Irises
  • 圖片
  • contact lens
  • 3D
  • 偵測：
    • reaction to light
    • blink/ move eyes
• Face
  • 圖片
  • 保障：
    • 給反應
    • blink/ move

Chapter 14: Secure Multi-Party-Computation (SMPC)

Goal

• Traditional
  • trust
  • insecure channel
• Multi-party computation
  • do NOT trust
  • distributed
  • private

Millionaire Problem

• Problem

  • if \(i \geq j\) ?
  • \(\begin{cases}{y_A=y_B=1 \iff j \leq i} \\ {y_A=y_B=0 \iff j>i} \end{cases}\)

• Solution

  • 假設 \(1<i,j<10\)

  1. B 有 \(j\) million

     隨機選擇 \(N\)-bit 的 \(x\)
     計算 \(E_A(x)\)
     把 \(E_A(x)-j+1\) 傳給 A

  2. A 有 \(i\) million

     對於 \(u=1,...,10\) 計算
     \(y_u=D_A(E_A(x)-j+u)\)

     若 \(u=j\)，則 \(y_u=x\)

     隨機選則 \(N/2\)-bit 的質數 \(p\)
     對於 \(u=1,...,10\) 計算
     \(z_u=y_u\text{ mod }p\)

     若 \(u=j\)，\(z_u=x\text{ mod }p\)

     把 \(p,z_1,...z_i,z_{i}+1,...,z_{10}+1\) 傳給 B

     若 \(z_u\) 的差沒有超過2
     重新選擇 \(p\)
     確保 \(z_a+1 \neq z_b\)

  3. B

     檢查第 \(j\) 個值是否等於 \(x\text{ mod }p\)
     如果是: \(j \leq i\)
     else: \(j>i\)
     告訴 A 結果

     Note:
     \(\begin{cases} {\text{if }j\text{ in }(z_1,...,z_i),} \\ {\Rightarrow z_j=y_j=D_A(E_A(x))\text{ mod }p=x\text{ mod }p}\\ {\Rightarrow j^{\text{ th}}=x\text{ mod }p}\\ {\Rightarrow j \leq i} \\ {\text{other }z_u=y_u\text{ mod }p=D_A(E_A(x)-j+u)\text{ mod }p}\\ {\Rightarrow \text{unknown to B}} \\ {\text{if }j\text{ in }(z_{i+1}+1,...,z_{10}+1),} \\ {\Rightarrow z_{i+1}+1=y_{i+1}+1=D_A(E_A(x)-j+i+1)+1\text{ mod }p}\\ {\Rightarrow \text{unknown to B}} \\ \end{cases}\)
     可以是 random order，B 只要檢查 \(x\text{ mod }p\) 是否在裡面

• Leakage

  • 定義
    A 的回傳值 \(w_u=\begin{cases} {z_u \text{ , if }u\leq i} \\ {z_u+1 \text{ , if }u>i} \end{cases}\)
  • 若存在 \(u^*\) 使得 \(w_{u^*},w_{u^*+1}\) 差剛好 2，且 \(w_{u^*}<w_{u^*+1}\)
    則 B 可以知道 \(i\neq u^*\)
    因為 \(w_i<w_{i+1}\) 永遠不會差 2

Semi-honest & malicious

• Semi-honest (honest-but-curious/ passive)
  • follow protocol
  • 但想知道更多 information
• Malicious
  • 違反protocol
    • 使違反 unattractive
  • 說謊
    • 無法避免

Correctness & Security

• Correctness
  • 正確計算 function \(f\)
  • 像有trusted third party一樣
• Security
  • 違反者不能得到更多訊息 (從input/ 結果得知)
  • example
    • 三人投票，一人說no，兩人說yes
    • 則說no的會知道其他人說yes
• Terms
  • Distance
    • 兩個在 set \(X\) 中離散機率分佈 \(A,B\) 的 Distance為
      • \(\frac{1}{2}\times \sum_x(|Pr(A=x)-Pr(B=x)|)\)
  • Probability ensemble
    • ensemble \(A_i, (i \in I)\) 是一個離散機率分佈的set
  • negligible
    • 一個函數 \(f(n)\) 逐漸小於多項式 \(p\) 的倒數
    • for each \(p(n),\ \exists\ m_p\) such that
      \(|f(n)|<\frac{1}{p(n)}, \forall n>m_p\)
  • equal
    • ensembles \(A_i, B_i\) are equal
  • statistically close
    • \(\text{dist}(A_i,B_i)\) 對所有 \(I\) 中的 \(i\) 是 negligible function
  • computationally indistinguishable \(A_i\approx B_i\)
    • 對所有 probabilistic polynomial-time algorithm \(D\)
      \(|Pr(D(A_i)=1)-Pr(D(B_i)=1)|\) 對 \(i\) 是 negligible function

SMC definition

• First Attemp
  • 計算 \(f(X_A,X_B)\) 是安全的
  • 如果有 Simulator algorithm \(S_A, S_B\)
  • Correctness
    • \((y_A,y_B)\approx f(x_A,x_B)\)
  • Security
    • \(\text{view}_A(\text{real protocol})\approx S_A(x_A,y_A)\)
      \(\text{view}_B(\text{real protocol})\approx S_B(x_B,y_B)\)
    • corrupt party 的 view 可以由他的 input/output simulate
  • 不能用在 randomized functionaility
    • \(f(b)\)，其中 \(b\) 是 random bit
    • A 隨機選 random bit
    • A 送 \(b\) 給 B
    • A 輸出 \(b\)
    • 正確但 insecure 因為 B 不能知道任何訊息
• 定義
  • Security
    • \(\text{view}_A(\text{real protocol},y_B)\approx (S_A(x_A,y_A),y_B)\)
      \(\text{view}_B(\text{real protocol},y_A)\approx (S_B(x_B,y_B),y_A)\)

    如果違反者的 view 跟 honest 的人的 output 相關
    simulator 可以 capture 此相關性

Homomorphic Encryption

• Semantic Secure
  • 實驗流程
    1. \(A\) 選擇一組 plaintext \((m_0,m_1)\)
    2. 隨機選擇 \(b\in \{0,1\}\)
       計算 \(c=E(m_b)\)
       傳給 \(A\)
    3. \(A\) 猜測 \(b'\in \{0,1\}\)
    4. \(\text{return}\begin{cases} {1, \text{if }b'=b} \\ {0, \text{otherwise}} \end{cases}\)
  • semantic secure \(\iff\) 任何 polynomial-time 的 \(A\)，存在一個 negligible function \(\mu\) 使得
    \(Pr[b=b']-\frac{1}{2} \leq \mu(n)\)

    需要 \(E\) 是 probabilistic

• Homomorphic Encryption
  • plaintext \((\mathbb{P},+)\)
  • ciphertext \((\mathbb{C},\otimes)\)
  • \(E: \mathbb{P}\rightarrow \mathbb{C}\)
  • additively homomorphic
    • \(E(m_1+m_2)=E(m_1)\otimes E(m_2)\)
  • fully homomorphic encryption
    • additively and multiplicatively
• Paillier
  • public key: \((N,g)\)
    • \(N\) is a RSA modulus
    • \(g\in\mathbb{Z}_{N^2}^*\)
  • plaintext \((\mathbb{Z}_N,+)\)
  • ciphertext \((\mathbb{Z}_{N^2}^*,\cdot)\)
  • \(E(m,r)=g^mr^N\text{ mod }N^2\)
    • \(r\in\mathbb{Z}_{N}^*\)
  • Homomorphic addition
    • \(E(m_1)+_hE(m_2):=E(m_1)\cdot E(m_2)=E(m_1+m_2)\)
  • Homomorphic scalarm multiplication
    • \(a\times_hE(m):=(E(m))^a=E(a\times m)\text{ for }a\in\mathbb{Z}\text{\\}\{0\}\)
  • Ciphertext blinding
    • \(Blind(E(m)):=E(m)+_hE(0)\)

Private equality checking

• Goal
  • \(B\) 和 \(A\) 想要 \(A\) 確認是否 \(a=b\)
• Protocol
  1. \(A\)

     計算 \(E(-a)\)

  2. \(B\)

     選擇隨機數 \(r\)
     計算 \(E(b)\)
     計算 \(E(b-a)\)
     計算 \(E(r(b-a))\)
     計算 \(E(r(b-a)+b)\)

     皆用 additively homomorphic

  3. \(A\)

     解密 \(E(r(b-a)+b)\)
     若為 \(b==a\) ，則 \(a=b\)
     反之為一隨機數

Private set intersection

• Goal
  • \(B\) 和 \(A\) 想要 \(A\) 找出 \(S_A\cap S_B\)
• Protocol
  1. \(A\)

     計算多項式 \(f(X)=\Pi(X-a_i)(i=1,...,k)=X^k+a_{k-1}X^{k-1}+...+a_0\)
     計算 \(E(a_i)\) 並傳給 \(B\)

  2. \(B\)

     選擇隨機數 \(r_i (i=1,...,k)\)
     計算 \(c_i=E(r_if(b_i)+b_i)\) 並傳給 \(A\)

     \(A\) 和 \(B\) 的 set 個數相等為 \(k\)

  3. \(A\)

     解密 \(E(r_if(b_i)+b_i)\)
     看哪個對應到自己的 \(a_i\)

     \(f(b_i)=0\) 如果 \(b_i=a_j\)

Binary Less-Than Protocol

• Threshold Paillier
  • Idea: split the private key
  • 用 Shamir's secret sharing
• Less than with shared output
  • Goal: \(A\) 知道 \(o_A\)，\(B\) 知道 \(o_B\)
    \(o_A\oplus o_B\) 隱含 \(b<b'\)
    (但 \(A,B\) 都不知道 \(b,b'\))
  • Idea: \(b<b' \iff b'(1-b)=1\)
  • Assumption:
    \(\pi_{Mult}(E(x),E(y))=E(x\cdot y)\)
    所有人可以知道結果但不能知道 \(x,y\)
• Protocol
  1. \(A\) \(B\)

     input: \(E(b),E(b')\)
     計算 \(\pi_{Mult}(E(1-b),E(b'))=E(c)\)

  2. \(B\)

     \(o_B\leftarrow_{rnd}\{0,1\}\)
     \(E(c'):=\begin{cases}{blind(E(c))\text{ , if }o_b=0}\\ {blind(E(1-c))\text{ , otherwise}}\end{cases}\)

  3. \(A\) \(B\)

     解密 \(E(c')\)
     只有 \(A\) 知道 \(c'\)
     設 \(o_A=c'\)
     \(A\) output \(o_A\)
     \(B\) output \(o_B\)

Chapter 15: E-Voting

Security of (E)-Voting

• was each vote captured correctly?
• was each vote counted correctly?
• Can the tally be independently verified?
• Is each vote anonymous
• Can anyone sell their vote?
• Can voters be coered(被要脅) to vote in a particular way?
• 其他voting的優點
  • Optical scanners
    • 避免miscounting
  • Direct recording electronic voting system
    • 減少 voters' error
    • 使 different disabilities 也可以投
  • Internet voting
    • convenient
    • disabilities

Three Ballot Voting

• paper based system 用電子計票

• Goal

  • 不用 cryptography 但盡可能達到越多 security properties

    因 cryptography 難理解，難被大家信任

• basic idea

  • 三張選票
  • 不想要的候選人三張加總為1票
  • 想要的候選人三張加總為2票
  • 

• operation

  • 投票者可以拿一張的選票備份
  • 檢查serial number
  • fake vote可以有最多1/3的機率被檢查到(如果voters都有檢查備份)

• weakness

  • 需要trust裝置
  • votes pattern 的選擇要夠random
  • Usability 差: 即使MIT學生也覺得confused
  • serial number 被禁止：不能 link 選票和人

Bingo Voting

• based on trusted random number generator
• 用 voting machine
• coercion(強迫) impossible
• cryptographic protocols
• Commitment scheme
  1. commitment
     • commitment \(c\) 由 message \(m\) 計算而來
     • 由 \(c\) 不能得知 \(m\)
  2. open/ unveil
     • \(m\) 和 random number 公布
     • 每個人都可以 check \(c\) 是 \(m\) 的 commitment
  • commitment 的性質
    • Hiding: 由 \(c\) 不能知道 \(m\)
    • Blinding: 給定 \(c\) 和 \(m\)，不能知道另一個 \(m'\neq m\) 使得 commitment 為 \(c\)
  • Pedersen Commitments
    • 基於 discrete logarithm problem
    • 要 commit \(m\) 及 random number \(r\)
    • \(c=h^mg^r\)
    • binding property:
      • 假設有 \(m',r'\)
      • \(c=h^{m'}g^{r'}\)
      • \(log_g(h)=(r-r')(m-m')^{-1}\text{ mod }q\)
      • committing entity 知道 \(log_g(h)\)
    • hiding property:
      • \(r\) random
      • \(g^r\) random
      • \(c=h^mg^r\) random
      • 因此不能從 \(c\) 知道 \(m\)
    • Masking
      • 新的 commitment
      • 隨機一 \(s\)
      • 計算 \(c'=cg^s\)
      • \(c'=h^mg^{r+s}\)
• Voting
  • voter在機器前選擇自己的候選人
  • 對那個候選人產生一組新的 random number
  • 機器印出候選人和 random number 的 pair
  • 其餘沒有被選到的候選人的 random number 為機器原本就產生的
  • 檢查 receipt 中有被改過的 random number 就是自己選的候選人
• Counting
  • 公開沒有被選到的候選人的 Dummy-votes
• Pederson commitments in Bingo Voting
  • 證明只有 \(L-1\) 組 dummy votes 被用
    ( \(L\) 為候選人個數)
  • 公布 \(C=(P,r)\) 真正選擇的候選人
  • 和 \(L-1\) (list1) 的 commitment
  • 用 Mask 產生 list2
  • 再 Mask 一次產生 list3
  • 擲銅板決定公布 list1 / list2 的關係或 list2 / list3 的關係
• Problems
  • 使用者要相信 cryptographic protocol
  • implementation 可能會有非預期的漏洞 (需要 open source)

Scantegrity

• 
• how it work?
  • 用 human readible 和 machine readible serial number
  • 得到 serial number 之後可以驗票
  • 選票上的 letter 不能和候選人相關
  • 公開後可以知道 serial number 和選擇的 letter
    • sereal number: \(1234\)
    • letter: \(A\)
    • candidate: \(Bob\)