CS 3710: Intro to Cybersecurity (slides): Asymmetric cryptography

# Asymmetric cryptography
## CS 3710: Intro to Cybersecurity

===

## Asymmetric encryption

---

## Some terminology

_**Difficult problems:**_ when we talk about "difficult problems" in
cryptography, we usually mean *computational difficulty*, e.g.

*"It's possible to solve this problem, if you made every computer on Earth
continually run to try to solve it for the next trillion years."*

</div>
</div>

*Example:* if it takes 1 microsecond to compute a SHA-256 hash and you had one
billion computers running continuously, it would take

$$
\approx 10^{16} \text{ years}
$$

(10 million billion years) to have a 50% chance of getting a hash collision.

</div>

notes:

Math:
- SHA-256 hash length is 256 bits
- Need to compute $\sqrt{2^{256}} = 2^{128}$ hashes to get a 50% chance of
  collision.
- If a hash takes 1 microsecond to compute, then with $10^9$ computers we're
  computing $10^15$ hashes per second.
- Therefore the number of years required to reach a 50% collision probability is

$$
2^{128} / (60 \cdot 60 \cdot 24 \cdot 365.25 \cdot 10^{15}) \approx 10^{16}
\text{ years}
$$

---

## Key exchange

So far, our critical assumption has been that Alice and Bob have pre-shared a
secret key that they can use for symmetric encryption.

</div>
<div class="fragment" data-fragment-index=0>

If they can do that, then great! At least in theory, they can send trillions of
exabytes of data to one another with complete security.

*(In practice, things can be a little more complicated than that.)*

</div>

---

## Key exchange

It would be inconvenient for you to meet up with a Google representative to
determine a secret key you want to use each time you visit `google.com`.

</div>
<div class="fragment" data-fragment-index=0>

To solve this problem, we use _**asymmetric encryption**_.

</div>
</div>

</figcaption>
</figure>

</div>
</div>

---

## Asymmetric encryption

The idea behind _**asymmetric encryption**_ is to generate two keys, a *public
key* and a *private key*.

</figcaption>
</figure>

---

## Asymmetric encryption

Using the public key, you can encrypt some data that only the holder of the
private key will be able to decrypt.

---

## Asymmetric encryption

One way\* to perform key exchange is to have Alice encrypt some secret data with
Bob's public key and then send that data to him.

*Source: Alex Curtiss*

</figcaption>
</figure>

</div>
<div class="fragment fade-out" data-fragment-index=0>

*Source: Alex Curtiss*

</figcaption>
</figure>

</div>
<div class="fragment fade-in-then-out" data-fragment-index=0>

*Source: Alex Curtiss*

</figcaption>
</figure>

</div>
<div class="fragment fade-in-then-out" data-fragment-index=1>

*Source: Alex Curtiss*

</figcaption>
</figure>

</div>
<div class="fragment" data-fragment-index=2>

*Source: Alex Curtiss*

</figcaption>
</figure>

</div>

\* _(Not necessarily the best way)_

notes:

This key exchange algorithm has the drawback that it lacks forward secrecy -- if
Bob's private key becomes compromised in the future, it'll be possible to
decrypt the session between Alice and Bob.

In practice you can avoid this with Diffie-Hellman key exchange (which is beyond
the scope of this class).

---

## Asymmetric encryption: SSH keys

We've already encountered public/private keys many weeks ago when we were
talking about SSH keys. Now we can look into how they're implemented:

`ssh-keygen` generates a public key and a private key, e.g.

<pre>
<code class="text" data-trim
  data-line-numbers="1-7|1">
$ ssh-keygen -t ed25519 -f id_ed25519
Generating public/private ed25519 key pair.
Enter passphrase (empty for no passphrase): 
Enter same passphrase again: 
Your identification has been saved in id_ed25519
Your public key has been saved in id_ed25519.pub
...
</pre>

---

## Asymmetric encryption: SSH keys

*Public key:*

```
$ cat id_ed25519.pub
ssh-ed25519 AAAAC3NzaC1...SMsusemeB4 student@example.org
```

*Private key:*

```
$ cat id_ed25519
-----BEGIN OPENSSH PRIVATE KEY-----
...
-----END OPENSSH PRIVATE KEY-----
```

---

## Asymmetric encryption: SSH keys

To start using this SSH key for login, I first copy it to the host I want to
login to:

```text
student@local$ ssh-copy-id -i id_ed25519.pub student@remote
```
</div>

This adds the public key to the `.ssh/authorized_keys` file:

```text
student@remote$ cat .ssh/authorized_keys
ssh-ed25519 AAAAC3NzaC1...SMsusemeB4 student@example.org
```

</div>

Once the public SSH key is installed on the remote host, I can use the private
SSH key to login:

```text
student@localhost$ ssh -i id_ed25519 student@remote
```

</div>

---

## Authentication with SSH keys

*Source: Alex Curtiss*

</figcaption>
</figure>

</div>
<div class="fragment fade-out" data-fragment-index=0>

*Source: Alex Curtiss*

</figcaption>
</figure>

</div>
<div class="fragment fade-in-then-out" data-fragment-index=0>

*Source: Alex Curtiss*

</figcaption>
</figure>

</div>
<div class="fragment fade-in-then-out" data-fragment-index=1>

*Source: Alex Curtiss*

</figcaption>
</figure>

</div>
<div class="fragment fade-in-then-out" data-fragment-index=2>

*Source: Alex Curtiss*

</figcaption>
</figure>

</div>
<div class="fragment" data-fragment-index=3>

*Source: Alex Curtiss*

</figcaption>
</figure>

</div>

---

## Digital signatures

Another application of asymmetric encryption is for _**signing data**_.

If Bob has Alice's public key, she can sign a particular piece of data with her
private key. Bob can use her public key to verify that the data actually came
from her.

</figcaption>
</figure>

</div>

</figcaption>
</figure>

</div>
</div>

*Source: [David Grayson](https://www.davidegrayson.com/signing/)*

</figcaption>
</figure>

</div>

===

## Algorithms for asymmetric encryption

### *(Warning: some math ahead)*

---

## Discrete log problem

Modern (non-PQC) asymmetric encryption schemes are based on the discrete
logarithm problem:

Given integers $a$, $b$, and $n$, it is generally difficult to find $x$ such
that

$$
b^x = a \mod{n}
$$

---

## RSA

_**RSA:**_ the "classic" asymmetric encryption algorithm, and a bit easier to
explain.

_**Idea:**_ it's easy to generate two large prime numbers $p$ and $q$; it's
difficult for an attacker to factor their product $pq$.

notes:

References:
- [TrailOfBits blog post on problems with
RSA](https://blog.trailofbits.com/2019/07/08/fuck-rsa/)

---

## RSA

RSA seeks to find three (large) integers $e$, $d$, and $n$ such that

$$
(x^e)^d = x \mod{n}
$$

for all integers $x$.

The tuple $(e, n)$ becomes the public key, while the exponent $d$ becomes the
private key.

---

## RSA

_**Encryption:**_ someone with the public key $(e, n)$ can encrypt a message $m$
represented as an integer by computing

$$
c = m^e \mod{n}
$$

</div>
<div class="fragment" data-fragment-index=0>

_**Decryption:**_ the person holding the private key $d$ can now decrypt $m$ by
computing

$$
c^d = (m^e)^d = m \mod{n}
$$

</div>

---

## RSA

[https://blog.trailofbits.com/2019/07/08/fuck-rsa/](https://blog.trailofbits.com/2019/07/08/fuck-rsa/)

</figcaption>
</figure>

notes:

- Prime numbers can't be too close to one another
- Small private exponents
- Padding oracle attacks -- RSA implementors should add padding to a message to
  make it valid, but this is often not done correctly.

---

## Elliptic curve cryptography

A broader class of algorithms used for asymmetric cryptography are based on
*elliptic curves*.

</figcaption>
</figure>

notes:

- Messages don't require padding and therefore avoid padding oracle attacks

---

## Implementing asymmetric encryption in practice

In general: *don't* roll your own implementation of cryptographic algorithms.

You probably want to stick to using a well-respected library like
pyca/cryptography or libsodium

</figcaption>
</figure>

===

## Summary

---

## Why not use asymmetric encryption everywhere?

Instead of doing this complicated key exchange protocol to then switch over to a
symmetric encryption scheme, couldn't we just use asymmetric encryption
everywhere?

No, for several reasons:

- _**Speed:**_ It's much slower than symmetric encryption.

</div>
<div class="fragment fade-in-then-semi-out" data-fragment-index="1">

- _**Message length:**_ You can't encrypt as many bytes in an asymmetric scheme
  as you can in a symmetric one.

</div>
<div class="fragment fade-in-then-semi-out" data-fragment-index="2">

- _**Security:**_ generally speaking, more things can go wrong in asymmetric
  encryption than in symmetric encryption.

</div>

---

## Summary

Asymmetric cryptographic schemes generate a *public* and *private* key, where
the former can be freely shared and the latter is kept secret.

</div>
<div class="fragment" data-fragment-index=0>

Asymmetric schemes provide useful functionalities in settings where a shared
secret key is not available:

- _**Key exchange:**_ you can use asymmetric encryption to agree on a secret key
  that should be used for symmetric encryption.
- _**Signing:**_ verify the origin of a particular piece of data by checking its
  signature.

</div>