---
# System prepended metadata

title: 資安概論

---

## Paranoia
### Traditional Security Goals 
1. Confidentiality: Data not leaked
2. Integrity: Data or resource not tampered 
3. Availability: Data or resource accessible when needed
4. Authenticity: Correct belief in data or resource origin

### adversarial  mindset
機票例子

### security goals
### adversarial model
define the adversary, maybe their identity、ability or goals
### Incentives
it consider whether human factors and economics affect the security goal?

##  Symmetric-key Encryption Ciphers
### caesar cipher
slide character for a picticular number(key).usually 1-25

Example:
Plaintext: HELLO
Key = 3
Shifting each letter by 3: H → K, E → H, L → O, L → O, O → R
Ciphertext: 

Ek(m) = (m + k) mod 26 
Dk\(c) = (26 + c – k) mod 26 

**weak**
- 容易被暴力破解-> only 25 possible shifts
- 透過一些常見的character pair 或letter frequency 可以幫助猜測(Statistical attacks)

### Vigènere Cipher
caesar cipher 2.0 -> use phase instead of single number key
![image](https://hackmd.io/_uploads/ryLtQxOgJg.png)
v:21
T:19
(21+19)MOD 26 -> 14 -> O

one time pad->unbreakable (xor舉例)
- Breakable if used twice -> 洩漏太多資訊，讓adversary 可以有東西去比較
- Key must be perfectly random
- Key length = message length -> cons:當message很長 key也需要很長

### symmetric encryption
![image](https://hackmd.io/_uploads/H1FwOede1e.png)
![image](https://hackmd.io/_uploads/HyrKdluxkl.png)
### birthday paradox
- 當一個房間有23人時 至少兩人生日在同一天的機率超過50%
- 對於 N 個可能的值，預計在檢查大約 sqrt(N)（平方根 N）次之後會出現碰撞
- 如果 N = $2^n$（n 位元的金鑰），在 $2^{n/2}$ ("生日界限") 次訊息後預期會出現碰撞

For 64-bit key, E(𝑀1)and E(𝑀2) in the same time. After trying $2^{32}$ transactions, E(𝑀1) = E(𝑀2) happened at least once with
more than 50% chance. -> **birthday attack**

### meet in the middle attack
針對雙重加密的攻擊
C=EK2(EK1(M))->找EK1(M)=DK2\(C)
This does not have 2n bit security !
![image](https://hackmd.io/_uploads/Syctk-nlJl.png)

Brutally need $2^{2n}$ steps
**only take $2^{n+1}$ steps**
> 中途相遇攻擊僅需$2^n$次加密計算來生成查找表，再加上$2^n$次解密查找，總共需要$2^n$+$2^n$=$2^{n+1}$次運算

### pre-computation attack
當可能的訊息集 M 很小，也就是說訊息的種類有限時，可以使用預計算攻擊。攻擊者先對所有可能的訊息 𝑚  進行加密，計算出所有可能的密文 𝑓 ( 𝑚 )。 然後，攻擊者建立一個對應表 ( 𝑚 , 𝑓 ( 𝑚 ) )，其中儲存每個訊息 𝑚  及其相應的密文 𝑓 ( 𝑚 ) 。當攻擊者在實際通信中截獲到某個密文 𝑓 ( 𝑚 )  時，只需在之前建好的對應表中查找相應的 𝑚 即可得知原始訊息，從而破解密文。(called forward searches

### block cipher
把大資訊拆成一塊塊的後分別加密
### Electronic Code Book (ECB) mode
每個區塊都用一樣的key加密
weak:
1.相同的明文區塊會生成相同的密文區塊。
2.區塊順序被竄改
3.資料太小可能被爆破(建表)
### Handling misordered blocks
two ways
1.Crypto the entire message and sign it
2.Crypto some sequence message in the block 
![image](https://hackmd.io/_uploads/HkkyI-hgke.png)
### Cipher-Block Chaining (CBC) mode
random initialization vector(IV)
![image](https://hackmd.io/_uploads/B1G3iphxyx.png)

pros:
1.prevent statistical attack
(xor讓加密模式更隨機)
2.Resist mis-order block attack

cons:
1.Can not do parallel decryption

### Cipher Feedback Mode:Full-block
使用前一個密文進行加密然後跟現在的明文xor
![image](https://hackmd.io/_uploads/BJQ2zC3gkl.png)
**允許parallel decryption**
![image](https://hackmd.io/_uploads/rkjm7CheJe.png)
cons:
Error propagation: 如果前面bit傳輸錯誤或被竄改，後續解碼就會錯誤

### Cipher Feedback Mode:shift
使用密文時先用n bit shift
pro:
**Self-healing property**:
如果接收到的某個密文位錯誤，那麼接下來的 n 位將解密錯誤，在這之後的密文位可以正常解密。


![image](https://hackmd.io/_uploads/SyjGHJae1x.png)

### Counter Mode (CTR) 
CTR中，數據區塊的密鑰是透過加密一個計數器(將唯一的隨機數 nonce 和遞增的計數器值結合）生成的。
**隨機數的存在是為了防止重複使用相同的組合，從而避免安全風險，絕不能使用相同的(nonce,k)**
$k_i = E_k(unique-nonce||i)$
$c_i = m_i \oplus k_i$

![image](https://hackmd.io/_uploads/rJlvyN6xkl.png)
![image](https://hackmd.io/_uploads/HkOv1NpeJe.png)
pro:由於每個區塊都有不同的計數器值，即使明文相同，加密後密文也不同，避免 statistical attack
con:發送及接收端計數器要同步

### Output feedback cipher (OFB)
跟CFB基本一樣，只是回饋至下一端的資訊不同
CFB:傳CIPHER(等於 加密端XOR PLAINTEXT)
OFB:傳加密端輸出
![image](https://hackmd.io/_uploads/rkZh-EaxJl.png)
### Stream ciphers
Ek is encryption func
M is message,M=b1b2b3b4..

**block cipher**:$E_k(m) = E_k(b_1) \, E_k(b_2) 
\, \dots$

---
**Stream ciphers**:
$k=k_1 k_2  \dots$
$E_k(m) = E_{k1}(b_1) \, E_{k2}(b_2) \, \dots$

如果密鑰序列 k 1 ​ ,k 2 ​ ,… 重複出現，則此密碼是「週期性」（periodic）的，且週期為k 1 ​ k 2 ​ … 的一個循環。

ex:Vigenère cipher

- 常用xor 針對each bit

### Synchronous Stream Ciphers
#### n-stage Linear Feedback Shift Register
用來產生key
- n bit register $r = r_0 \dots r_{n-1}$
- n bit “tap sequence $t = t_0…t_{n–1}$

**step**
1.Use $r_{n–1}$ as key bit
2.Compute $x = r_0  t_0 \oplus \dots \oplus r_{n–1} t_{n–1}$ (前面and)
3.Shift r one bit to right, dropping $r_{n–1}$
, x becomes r0
![image](https://hackmd.io/_uploads/r1ILuNaekx.png)

####  n-stage Non-Linear Feedback Shift Register
more diificult for adversary

把xor那一part改成任意function
Compute $x = f(r_0,\dots, r_{n–1})$; f is any 

其他一樣

### Integrity 問題
如何防止被密文被tampered
- Authenticated encryption modes(生成一個驗證標記)
- message authentication code (MAC)(加訊息驗證碼)


## Hash Functions
A hash function is any function which takes an arbitrarily long string of characters or bits as input and returns a fixed-length
output

property
- Fast to compute 
- With any input, hash values (hopefully) distributes uniformly

### pre-image resistance
給定一個隨機的  y（在$\{0,1\}^ n$ 上均勻分布），找到對應的輸入  x 是不可行的，即難以找到滿足 H(x)=y 的 x。

### Collision-resistance
難以找到任何一對不同的輸入(w,x)，使得H(w)=H(x)=y。

### Random Oracle Model (ROM)
隨機預言機是一個理論模型，它被設想為一個能夠回答查詢的「黑盒子」，每次輸入問題 x 時會給出一個隨機的答案 y。

• If n = 256, expected number of guesses is $2^{256}$

![image](https://hackmd.io/_uploads/Skmqrh4Wke.png)

exp: $\frac{2^{252}} {2^{256}}= \frac{1}{16}$

maximun: infinite,since input domain is unlimited

### birthday paradox
ROM + 生日悖論 ⇒ 碰撞抗性
![image](https://hackmd.io/_uploads/rJR1d34W1e.png)

### hash property
- one-way
- non-invertible
- produces unique
- fixed-size outputs for different inputs (with any input lengths)

### software verification
軟體供應商/攻擊者發送不同版本:
![image](https://hackmd.io/_uploads/By5_63NWyg.png)
第三方惡意組織分發惡意軟體:
![image](https://hackmd.io/_uploads/rk7c62EbJg.png)

### crack hash
使用常見密碼P -> HASH(P)可能被記錄 -> 被拿來比對
字典攻擊與暴力破解

### Salting password hashes
如果每個用戶的密碼都是用相同的雜湊函數處理的，攻擊者可以使用預先計算好的字典來破解常見密碼的雜湊值。

SALT:
伺服器不儲存用戶的H(P\)，而是儲存 (salt Alice,H(salt Alice ∥P))

salt是公開的，因為在驗證密碼時需要使用它。其作用在於防止攻擊者使用已知的雜湊值字典來匹配密碼。

salt應該是隨機生成的且每個用戶不同-> no collision

### Resource-intensive hashing
讓雜湊函數H的計算變得緩慢（但可行），以增加破解難度。

Approach: Many iterations of H to slow process
• E.g., store $H^{2048}(P)$

pro:slows attacker
cons:slows user

new way:
Heavy use of fast memory (cache)

### commitment 
![image](https://hackmd.io/_uploads/rkiEz64-kl.png)
m很容易被破解，只有1 bit

所以
![image](https://hackmd.io/_uploads/ryWJmpEWye.png)
![image](https://hackmd.io/_uploads/rJ6SQaV-1x.png)

## Key Exchange Public Key (Asymmetric)Cryptography

### mod
對於任意整數a,b 和模數 m，
如果 a ≡ b  mod m ，
那麼：$a^k$ ≡ $b^k$  mod m ≡ ${(b \space mod\space m)}^k$



### Diffie-Hellman 
在不安全的網路上建立安全的共享密鑰
![image](https://hackmd.io/_uploads/BJpDqaVbke.png)
![image](https://hackmd.io/_uploads/H1_u5TEbJe.png)
![image](https://hackmd.io/_uploads/ByF5qpVZyl.png)

adversary不可能得知shared key因為沒有private key

### Man in The Middle (MITM)
攻擊者秘密攔截(intercept)並可能修改雙方之間的通訊，而通訊雙方誤以為他們直接在互相交流。

sol:authenticate first

### Forward Secrecy (PFS)
確保即使未來的密鑰被攻破，過去的通訊內容仍然保持安全，無法被解密。
![image](https://hackmd.io/_uploads/S1b9iaEb1g.png)

### Certificate Authority, CA
受信任的第三方，負責發佈並驗證公開金鑰的有效性，確保用戶能夠信任它們所使用的公開金鑰屬於正確的對象。

### Signatures
only signer can produce and everybody can verify

- - -

Confidentiality -> 確保只有擁有私鑰的使用者可以解密和閱讀被加密的訊息

Authentication -> 身份驗證確保訊息的發送者是真的 (signature)

Integrity -> 確保加密後的訊息無法在不被發現的情況下被修改。(只有有私鑰者可以對訊息進行簽名)


Non-Repudiation -> 確保訊息的發送者無法在事後否認其行為(只有擁有該私鑰的人才能生成這樣的訊息)

### trapdoor function
function that is easy to compute but believed **hard** to invert without additional information

### RSA

#### Eular Function
IF p is prime number
$φ(p)=(p−1)$
Now, we have n= p * q
p q are prime
$φ(n)=(p−1)×(q−1)$
- - -
![image](https://hackmd.io/_uploads/r1kqjlrZyx.png)
![image](https://hackmd.io/_uploads/BJOMfCEbJx.png)
>應該是ed $\equiv$ 1 mod $\varphi(n)$ 
- - -
multiplicative inverse


可能的問題:
1.Exhaustive search for key
2.Factoring n
3.Timing Attacks
4.Forward search(字典攻擊)
5.Common modulus problem(use same n)


##  Signatures
### order
encrypt then sign:
may be replaces with someone else

it should be **Sign then Encrypt**

![image](https://hackmd.io/_uploads/rJUKZ-HW1e.png)


### Public Key Cryptography
In RSA S(m)=D(m).(這是因為 RSA 使用私鑰對訊息進行簽名，公開金鑰用於驗證簽名)

so If we sign arbitrary(任意) stuff, e.g.,
m=E(M), then in effect we reveal M=D(E(M))
![image](https://hackmd.io/_uploads/BkHYMbHbkl.png)

## Cryptocurrency

- A peer-to-peer digital exchange system
- Cryptography is used to generate & distributed currency units
- No central authority
- Need to be verified the transitions

https://www.youtube.com/watch?v=bBC-nXj3Ng4

### mining
![image](https://hackmd.io/_uploads/SJm22WS-yx.png)

### 51% attack
在虛擬貨幣的系統裡要偽造資訊欺騙他人->必須擁有全世界51%的mining資源

### Proof of stake
- Requires the miner to show how much currency the miner owns in the system
- May get penalty if do something bad

### Proof of Retrievability
依賴於大容量存儲:PoR 的主要用途是確保參與者能夠存儲並保留重要數據檔案的片段。這對於需要長期保存和確保數據完整性和可取回性的情境特別有用，例如去中心化的存儲系統

### Smart contract
A “code” or “script” run on the block chain 

## AI Security
### Deep Learning
- A chain of differentiable functions
![image](https://hackmd.io/_uploads/B1pVlGBbyx.png)

![image](https://hackmd.io/_uploads/B1omxfSWJe.png)
**standard deviation**

maybe be trapped in **Local Minimum**

### Data Poisoning 

manipulate the training dataset to control the prediction behavior


#### Scaling attack
![image](https://hackmd.io/_uploads/rJF8-MBZkg.png)

#### Availability attack
破壞模型的可用性，使其無法在預期的性能水平下工作
ex:Dos

#### Integrity Attack
Backdoor Samples:
插入帶有標記或特徵的特定樣本，讓模型在遇到這些樣本時做出錯誤的預測

#### Adversarial Examples
intentionally crafted input data that includes minor, almost hard to notice change

#### System integration 
- discrimination on sex,race
- terrible suggestion
- privacy leak

XAI:開發和設計人工智慧系統，以便讓人類能夠理解、信任和解釋其決策和行為