Introduction to Blockchain Security Practices

Lesson Topics

Randomness
Hash functions
Signatures

Randomness

Without randomness, all operations would be predictable, and therefore insecure
Cryptography (and blockchains) could not exist
Needed for generating secret keys, encryption protocols, and more

"Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin. For, as has been pointed out several times, there is no such thing as a random number — there are only methods to produce random numbers, and a strict arithmetic procedure of course is not such a method."

—John von Neumann

True random processes

Thermal noise
Radioactive decay
Network packet arrival times
Wiggling mouse/pounding on keyboard (?)

Pseudo-randomness

PRNG (Pseudo-Random Number Generator)
- Deterministic process that generates numbers
CSPRNG (Cryptographically Secure PRNG)
- Must be unpredictable and unbiased
- "Stretches" the randomness from a "seed" (small value from a true RNG)

Random mistake 1: Bad RNGs

Linear Congruential Generator (LCG)

Stars are drawn in "random" spots

Random mistake 2: Small seeds

If your seed is 32 bits you will only have
```
2³² = ~4 billion
```
different possible sequences
Easily breakable , even if PRNG is strong
Use at least 128 bits of randomness for your seeds

Random mistake 3: Mod bias

function rollD6() {
    return 1 + (getRandom() % 6);
}

Depending on the output range of getRandom(), rollD6() will be biased
Why?

Demos

Moral of the story

For crypto, always use a secure random number generator provided by your environment or OS
- Web-browser: window.crypto.getRandomValues()
- node.js: crypto.randomBytes()
- Linux/OS X: /dev/urandom
- Windows: RtlGenRandom

15 minute break

Principle: Computational Infeasability

Relied on by all practical cryptography
If attackers could try every possible random value, they could crack your crypto-system
- Called a "brute force" attack
So, we make sure there are so many possible random values that it would take practically forever for them to do so

Hash functions

The core building block of blockchains
Functions that take an unlimited-size input message $m$ and return a fixed size output $h$ :

$h = H(m)$

Preimage-resistance

Hashing is a "one-way" function
If you only know the hash of a secret, it's hard to find that secret
Formally: given an arbitrary $h$ , it is computationally infeasible to find an $m$ such that $H(m) = h$

Hashing mistake 1: Small preimage domain

Be careful when anonymizing names/IPs/emails/etc by hashing
If there aren't that many possible secrets, you can just try all of them
Exercise: preimage.html
- So much for "one-way" function

Collision-resistance

Hard to find any two messages that hash to the same value
Formally: Computationally infeasible to find distinct $m$ and $m'$ such that $H(m) = H(m')$
We know all hash functions have collisions because...

Pigeon-hole principle

Collision attacks

Hash functions are almost always attacked by finding collisions, not specific preimages
MD5 and SHA1 are insecure because it is easier than it should be to find collisions
- Both are still practically secure against preimage attacks
Why is it easier to find collisions?

Birthday experiment

Doesn't always work, but it's fun when it does

Rho method (tortoise and hare)

Memory-efficient way to search for collisions
Named because it looks like greek letter ρ

Hashing mistake 2: Equivalent inputs

function uniqueUserId(username, accountId) {
    return sha1(username + accountId);
}

uniqueUserId("john", 234)

uniqueUserId("john2", 34)

Hashing mistake 3: Length extension

With older hash functions, given a hash you can add data to the end of an unknown preimage and compute a valid hash for it:
- MD5, SHA1, SHA2-256
Doesn't have this problem:
- SHA3, Keccak, BLAKE2, SHA2-512/256, double SHA2-256 (see bitcoin)

15 minute break

Kerckhoffs's principle

Everything about how a cryptosystem works should be open and public information, except for each user's secret key(s)
The opposite is security through obscurity, which is bad because it doesn't work

Signatures

Digital signatures let you create messages such as

"I, Alice, send 10 bitcoins to Bob"

... and prove that this message was created by Alice, and not some attacker

Public and private keys

Use good randomness to choose a private key
- Always keep your private key secret!
Each private key has a corresponding public key
- Your public key is your bitcoin/ethereum address

Signatures made simple

Let's say all you have is a preimage-attack resistant hash function.

Suppose you want to sign a 1 bit message:

Private key: 2 random secrets $r_0$ , $r_1$
Public key: $[H(r_0), H(r_1)]$
To sign the message "0", reveal $r_0$
To sign the message "1", reveal $r_1$

Problem: Key-pair only useful one time

Types of signatures

RSA
Elliptic curves
Hash-based
Lattices

On blockchains, almost always elliptic curves

secp256k

This is the type of elliptic curve signature used by Bitcoin, Ethereum, others
Private keys are 32 bytes
Public keys are 64 bytes (more on this later)
Signatures are 64 bytes

secp256k private keys

Randomly choose a 256-bit number
Almost any number will work, except:
- 0
- Numbers greater than 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140
If you pick a 256 bit number at random, chance it is a valid private key: 99.999999999999999999999999999999999999626%

There are 2 separate hash functions:
- keccak256
- SHA3 (standardised)
Confusingly, Ethereum folks sometimes say "SHA3", but they always mean keccak256
- So be careful when using libraries in various languages!

Public keys and addresses

secp256k public keys are 64 bytes
Ethereum addresses are 20 bytes
To compute an ethereum address from a public key:
- Hash public key with keccak256 (giving 32 bytes)
- Take last 20 bytes of hash
- Encode as hexadecimal
- Prefix with "0x"
- Optional: Compute checksum

Why hash public keys?

Smaller (20 bytes instead of 64)
Can be recovered from signatures anyway (later lesson)
Quantum computer resistance (sort of)
We know there is at least one ethereum address with multiple valid private keys
- Why?

Multi-Signatures

When several people agree on something, they can all sign same message

Schnorr Multi-Signatures

Schnorr signatures let you combine these into a single signature, that can still be verified