CSE468 Computer Network Security Midterm Review

Computer Network Security Midterm Review

Information Theory

When observing planes flying over Tempe Town Lake to land at the airport, Harlo observed the following probabilities for which airline/company the plane belonged to: ( $\frac{1}{2}$ chance of Southwest, $\frac{1}{8}$ chance of Delta, $\frac{1}{8}$ chance of American Airlines, $\frac{1}{16}$ chance of Spirit Airlines, $\frac{1}{4}$ chance of TWA, $\frac{1}{16}$ chance of FedEx). What is the overall entropy of one instance of observing an airline/company? \(H[p] = -\sum^{k}_{i=1} p_i \log p_i\)

Solve: \(= -(\frac{1}{2} \times log_2{\frac{1}{2}}+\frac{1}{8} \times log_2{\frac{1}{8}}+\frac{1}{8} \times log_2{\frac{1}{8}}+\frac{1}{16} \times log_2{\frac{1}{16}}+\frac{1}{4} \times log_2{\frac{1}{4}}+\frac{1}{16} \times log_2{\frac{1}{16}})\)

Modular exponentiation

Example 01: Use modular exponentiation to calculate $153^{189} \bmod 251$.

Solve:

$189$ in binary is 0b10111101 \(189 = 1 \times 2^7 + 0 \times 2^6 + 1 \times 2^5 + 1 \times 2^4 + 1 \times 2^3 + 1 \times 2^2 + 0 \times 2 ^ 1 + 1 \times 2^0\)

\[153^{189}(\bmod \; 251) = 153^{128+0+32+16+8+4+0+1}(\bmod 251) \\ = 153^{128} \times 153^{32} \times 153^{16} \times 153^{8} \times 153^{4} \times 153^{1}(\bmod 251)\]

We can calculate $153^{128}$, $153^{32}$, $153^{16}$, $153^{8}$, $153^{4}$, and so on very efficiently by: \(\begin{align} 153^0 \bmod 251 = 1 \\ 153^1 \bmod 251 = 153 \\ 153^2 = (153 \times 153) \bmod 251 = 66 \\ 153^4 = (66 \times 66) \bmod 251 = 89 \\ 153^8 = (89 \times 89) \bmod 251 = 140 \\ 153^{16} = (140 \times 140) \bmod 251 = 22 \\ 153^{32} = (22 \times 22) \bmod 251 = 233 \\ 153^{64} = (233 \times 233) \bmod 251 = 73 \\ 153^{128} = (73 \times 73) \bmod 251 = 58 \end{align}\) Then, \(\begin{align} = 58 \times 233 \times 22 \times 140 \times 89 \times 153 (\bmod 251) \\ = 73 \end{align}\) Example 02: Use modular exponentiation to calculate $5^{141} \bmod 29$.

Solve:

$141$ in binary is 0b10001101 \(141 = 1 \times 2^7 + 0 \times 2^6 + 0 \times 2^5 + 0 \times 2^4 + 1 \times 2^3 + 1 \times 2^2 + 0 \times 2 ^ 1 + 1 \times 2^0\)

\[\begin{align} 5^{141}(\bmod 29) = 5^{128+0+0+0+8+4+0+1}(\bmod 29) \\ = 5^{128} \times 5^{8} \times 5^{4} \times 5^{1} (\bmod 29) \end{align}\]

We can calculate $5^{128}$, $5^{8}$, $5^{4}$, $5^{1}$ very efficiently by: \(\begin{align} 5^0 = 1 \\ 5^1 = 5 \\ 5^2 = (5 \times 5) \bmod 29 = 25 \\ 5^4 = (25 \times 25) \bmod 29 = 16 \\ 5^8 = (16 \times 16) \bmod 29 = 24 \\ 5^{16} = (24 \times 24) \bmod 29 = 25 \\ 5^{32} = (25 \times 25) \bmod 29 = 16 \\ 5^{64} = (16 \times 16) \bmod 29 = 24 \\ 5^{128} = (24 \times 24) \bmod 29 = 25 \end{align}\) Then, \(\begin{align} = 25 \times 24 \times 16 \times 5 (\bmod 29) \\ = 5 \end{align}\)

In-path vs. on-path vs. off-path

• kirk and spock are in-path
• appliance is on-path
  • Gets a copy of the packets from the port mirror on kirk
• chekov is on-path
  • Shared Wi-Fi with sulu, kirk has a wireless interface and two fiber optic interfaces
• scotty and bones are off-path

AES S-Box requirement

• Can’t pull it out of our &%# like the NSA did for DES
• Should have good nonlinear properties
  • Better nonlinearity means fewer rounds
• Should be reversible
  • Don’t want to use Feistel structure for performance reasons

Properties of XOR

\[\begin{align} \;\;\;\;0\;0\;1\;0\;1\;0\;1\;0_b \\ \oplus\;1\;0\;0\;0\;0\;1\;1\;0_b \\ =1\;0\;1\;0\;1\;1\;0\;0_b \end{align}\]

Secure hash functions

• Three properties (Hash functions and certificates slides 28-30)

  • Property #1
    • Pre-image resistance
    • Given $h$, it should be infeasible to find m such that $h = hash(m)$
  • Property #2
    • Second pre-image resistance
    • Given a message $m_1$, it should be infeasible to find another message $m_2$ such that $hash(m_1)=hash(m_2)$
  • Property #3
    • Collision resistance
    • It should be infeasible to find two messages, $m_1$ and $m_2$ such that $hash(m_1)=hash(m_2)$

• Three basic attacks (Hash functions and certificates slides 32, 36, 38)

  • Length extension attack
    • One issue is if the attacker doesn’t know the password
    • Another issue is if the password is different but the attacker finds a collision later on
  • Birthday attack
    • Probability of collision is 1 in $2^n$ , but the expected number of hashes until two of them collide is $sqrt(2^n )=2^{\frac{n}{2}}$
      • Why? Third try has two opportunities to collide, fourth has three opportunities, fifth has six, and so on…
  • Chosen-prefix collision attack
    • Given two prefixes $p_1$ an $p_2$, find $m_1$ and $m_2$ such that $hash(p_1 \Vert m_1)=hash(p_2 \Vert m_2)$
    • $p_1$ and $p_2$ could be domain names in a certificate, images, PDF, etc. … any digital image.

ECB vs. CBC

Basics of asymmetric crypto vs. symmetric crypto

• Symmetric encryption
  • Assumes two parties wishing to communicate already have a shared secret
• Asymmetric encryption
  • Makes different assumptions (e.g., that everybody knows the public key or that the eavesdropper is passive)
  • Quantum computers break current algorithms that are used in practice
• Secure hash functions and message authentication