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:

$$ 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 $$

Then,

$$ = 58 \times 233 \times 22 \times 140 \times 89 \times 153 (\bmod 251) \\ = 73 $$

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 $$

$$ 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) $$

We can calculate $5^{128}$, $5^{8}$, $5^{4}$, $5^{1}$ very efficiently by:

$$ 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 $$

Then,

$$ = 25 \times 24 \times 16 \times 5 (\bmod 29) \\ = 5 $$

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

in-on-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

$$ \;\;\;\;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 $$

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||m_1)=hash(p_2||m_2)$
      • $p_1$ and $p_2$ could be domain names in a certificate, images, PDF, etc. ... any digital image.

ECB vs. CBC

ecb-cbc

ecb-penguin

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