# Cryptography
> FSA March 25, 2017

Foundational ideas in Cryptography

____
## Crypto
* Cryptography: code-making / secret keeping
* Cryptanalysis: code-breaking / secret revealing

Cryptography is the masonry of software security. It is not the same AS software security.

#### Randomness
* not 'predictable/patterned'
* uniformly distributed output
* next is unrelated to previous
* next is unrelated to previous previous

**Random Number Generator**
* We need random numbers for some algos, including quicksort
* Avoiding deadlocks and 'starvation' in parallel programming
* simulations/games

Don't be fooled by a seeming non-random pattern in a string of iterations.

Random Number Generators:
* quantum mechanics
* thermal noise
* 10th char of most recent tweet?
* randomness is `subjective` in some way, because we may be able to increase the information that we have to predict something

Pseudo-Random Number Generators:
* Not truly random, but easier to work with
* Easier and deterministic (repeatable)
* 'die hard' tests – a suite of tests that look at the quality of a pseudo-random number generator
* PRNG is less crypto-secure than a CSPRNG

> PRNGS use a seed and typically input one iteration's seed as the seed of the next iteration. Check out Mersenne twister and middle squares method.

**CSPRNG**
Pass statistical tests.
Satisfies the 'next-bit test'
Withstands 'state compromise extensions'

#### Hashing
Takes some input string ('message') and outputs a string ('digest').
The same message is always going to get the same output. Digest is usually a fixed size.
The hashing algorithm is *irreversible*.

> Collisions are a problem (remember our hash table workshop?)

Irreversibility is less strange than it seems. What if I tell you a sum is 15? What were my inputs? You don't know.

* '+' <-- addition
* sha1
* md5
* neurons

Possible collisions are infinite.

**Why do we hash?**

Identity:
* Useful for identifying something quickly (think hash table)
* bloom filter
* git commit ids
* equality testing

> Storing hashed passwords in your database protects somewhat from compromise. You can hash the password and see if it matches the hash in the DB, without knowing the user's password.

Cryptography:
* password verification
* integrity verification
* some PRNGs
* proof of work (in cryptography)

**How**

1. pad – we make sure it is of a certain size (our target size)
2. partition – split the string into chunks of our target size
3. combine – smoosh all of our chunks into a

AKA Merkle-Damgard construction

**For example: Simple Hash**
1. pad string to at least twice the desired length
2. partition into chunks of desired length
3. combine (reduce) this partitions using XOR

#### XOR
```
XOR TRUTH TABLE
______
00 | 0
01 | 1
10 | 1
11 | 0
```
XOR produces an evenly distributed output.

#### Cryptographic Hashing
1. Pre-image resistance: a hacker can't find collision given hash result
– What if I can create something that produces the same results?

2. Second pre-image resistance: a hacker can't find collision given input message
– If you know a file that was used to produce a hash, then you can't come up with another string of text that will produce the same hash.
I receive a hashed output. Someone in the middle comes up with a different file that has the same hashed output. This is bad!

3. Collision resistance: a hacker can't find some arbitrary collision
– Impossible to find some arbitrary collision. I can't figure out two messages in general that hash to the same output.

> When people say an algo is 'collision resistant', they usually mean all three.

#### HMAC
Hash-message authentication code

key + message => digest
key is a secret

Scenario:
1. When I buy something I'm asked to make a secret
2. Secret hashed together with purchase
3. Creates an HMAC which you can verify again using the 'receipt' (purchase) and the secret

Can be used to confirm message receipt without exposing identity or message.

#### PBKDF2
> Password based key derivation function!

We use this on passwords. It repeatedly calls a hashing algorithm on 'salted' text.

My password `cats`, adds some secret salt to the front, `jazz82cats` (an HMAC). The salted password is hashed repeatedly and stored in the database.

1. Why should we hash passwords before storing in our DB?
Avoid having them easily stolen.

2. Why salt?
Common passwords could be guessed via collisions by testing a large quantity of passwords. Helps us avoid rainbow table hacks – because the hacker also needs the salt.

3. Why repeatedly hash?
Slows down algorithms. It slows us down a bit, sure. But for a hacker we significantly slow their brute force attacks by increasing the how many times they have to hash every possible password.


#### Encryption
TBD


#### Asymmetric-key (RSA)
TBD