[SOLVED] CS Cryptography Basics (Pseudo)Randomness

Cryptography Basics (Pseudo)Randomness
ECEN 4133 Jan 21, 2021

Review
Integrity of messages between Alice and Bob
Alice appends bits that only Alice (and Bob) can compute
Solution: Message Authentication Code (MAC)
Hash-based MAC (HMAC) used in practice, e.g. v = HMAC-SHA256k(M)
k
m, v
m, v?
k
Where does k come from?
How do we generate it? [Today]
How do we share it with Alice and Bob, but not Mallory? [Next time]
Mallory
Alice
Bob

Randomness
True Randomness
Output of a physical process that is inherently random Scarce and hard to get
Pseudorandom generator (PRG)
Takes small seed that is really random
Generates long sequence of numbers that are as good as random

True Randomness
Where do we get true randomness?
Want indistinguishable from random meaning: adversary cant guess it Gather lots of details about the computer that the adversary will have trouble
guessing [Examples?]
Problem: Adversary can predict some of this
Problem: How do you know when you have enough randomness?

Getting a large amount of randomness
Difficult to collect lots of true random
Suppose we have 128-bits of true random (k), but want 1024-bits of random Can we expand our 128-bits? [Breakout]
Can we extend to arbitrary lengths?
Any caveats? How many unique sequences of 1024-bits can we produce with this technique?

Getting a large amount of randomness
Pseudo Randomness:
Not truly random usually an expansion of a (shorter) set of true random bits
One solution: Pseudo-random number generator (PRNG):
Given 128-bit true random k
HMAC-SHA256k(0), HMAC-SHA256k(1), HMAC-SHA256k(2), HMAC-SHA256k(n)
Is it secure?
Can an adversary tell what will come next without knowing k?
Given HMAC-SHA256k(a), (but not k), can an adversary predict HMAC-SHA256k(b) for b>a ?

Pseudo-random generators (PRG)
Many different ways:
Using hashes
Using HMACs
Using block ciphers (well talk about these next)
Beware that there also exist non-cryptographic PRNGs:
Linear feedback shift register (LFSR)
Linear Congruential Generator (LCG)
Used by rand() / srand() / Math.random() Dont use for cryptography!!!
128 bits
k PRG
n bits
Output stream
We are talking about Cryptographically Secure PRNG (CSPRNG)
Should be difficult for adversary to predict future (or past!) outputs given some output

Backdoored CSPRNG
Dual_EC_DRBG
Dual Elliptic Curve Deterministic Random Bit Generator
Developed by the NSA in 2006, standardized by NIST
Strange design, very slow, based off elliptic curve cryptography (next week!)
If someone knows a mathematical relationship between P and Q, trivial to compute what comes next in the pseudorandom stream given current output (backdoor!!)
No explanation for how P and Q were chosen by the NSA
NSA paid $10 million to RSA Security to include
in their popular cryptographic library
Snowden documents revealed this to be a standard developed solely by the NSA as a backdoor

Randomness in practice
Modern OSes typically collect randomness, give you API calls to get it
e.g., Linux:
/dev/random is a device that gives random bits, blocks until available
/dev/urandom gives output of a PRG, nonblocking, seeded from /dev/random eventually
Note: both /dev/random and /dev/urandom use a CSPRNG seeded from: Keystroke/mouse movement timing
Network packet timing
Scheduler / interrupt timing
/dev/random tries to do entropy accounting: dont give out more than has been put in to the pool

/dev/(u)random problems
/dev/random blocks slow to read from
/dev/urandom doesnt block but might not be initialized at all!!!
Embedded devices:
Often dont have keyboard/mouse
Might not be connected to Internet at first boot (no packets) Very slow to collect entropy!
Solution:
Usegetrandom()
Added in Linux 3.17 (2014)
Blocks until pool has been initialized

Confidentiality
Integrity: prevent Mallory from tampering kk
Alice
Mallory
Bob
k
Confidentiality: prevent eavesdropper (Eve) from learning the (plaintext) message
v == MACk(m) ?
m, v:= MACk(m)
m, v
Terminology
p plaintext message
c ciphertext
k secret key
E encryption function D decryption function
k c := Ek(p) Eve
Bob
p := Dk(c)

Classical Cryptography
Digression: Classical Cryptography Caesar Cipher
First recorded use: Julius Caesar (100-44 BC)
Replaces each plaintext letter with one a fixed number of places down the alphabet Encryption: ci := (pi + k) mod 26
Decryption: pi := (ci k) mod 26
e.g. (k=3):
Plain: +Shift:
=Cipher:
Plain:
ABCDEFGHIJKLMNOPQRSTUVWXYZ 33333333333333333333333333 DEFGHIJKLMNOPQRSTUVWXYZABC
fox go wolverines
+Key:
=Cipher: ira jr zroyhulqhv
333 33 3333333333
[Break the Caesar cipher?]

Cryptanalysis of the Caesar Cipher Only 26 possible keys:
Try every possible k by brute force
Can a computer recognize the right one?
Use frequency analysis: English text has distinctive letter frequency distribution

Lateradvance: VigenereCipher First described by Bellaso in 1553,
later misattributed to Vigenere
Called le chiffre indechiffrable (the indecipherable cipher)
Encrypts successive letters using a sequence of Caesar ciphers determined by the letters of a keyword For an n-letter keyword k,
Encryption: ci := (pi + ki mod n) mod 26 Decryption: pi := (ci ki mod n) mod 26
Example: k=ABC (i.e. k0=0, k1=1, k2=2)
Plain: bbbbbb amazon
+Key: 012012 012012 =Cipher: bcdbcd anczpp
[Break le chiffre indechiffrable?]

Cryptanalysis of the Vigenere Cipher
Simple, if we know the keyword length, n: 1. Break ciphertext into n slices
2. Solve each slice as a Caesar cipher
How to find n? One way: Kasiski method Published 1863 by Kasiski (earlier known to Babbage?)
Repeated strings in long plaintext will sometimes, by coincidence, be encrypted with same key letters
Plain: CRYPTOISSHORTFORCRYPTOGRAPHY
+Key: ABCDABCDABCDABCDABCDABCDABCD =Cipher: CSASTPKVSIQUTGQUCSASTPIUAQJB
Distance between repeated strings in the ciphertext is likely a multiple of key length e.g., distance 16 implies n is 16, 8, 4, 2, or 1
Find multiple repeats to narrow down
[What if key is as long as the plaintext?]

One-time Pad (OTP)
Alice and Bob jointly generate a secret, very long, string of random bits
(the one-time pad, k) To encrypt: ci = pi xor ki To decrypt: pi = ci xor ki
one-time means you should never reuse any part of the pad. If you do:
Let ki be pad bit
Adversary learns (a xor ki) and (b xor ki) Adversary xors those to get (a xor b), which might be useful [How?]
Provably secure [Why?]
Usually impractical [Why? Exceptions?]
a b axorb 000 011 101 110
a xor b xor b = a a xor b xor a = b

Practical One-time Pad
Idea: Use a pseudorandom generator (CSPRNG) instead of a truly random pad
(Recall: Secure PRG inputs a seed k, outputs a stream that is practically indistinguishable from true randomness unless you know k)
Called a stream cipher:
1. Start with shared secret key k
2. Alice & Bob each use k to seed the PRG
3. To encrypt, Alice XORs next bit of her generators output with next bit of plaintext
4. To decrypt, Bob XORs next bit of his generators output with next bit of ciphertext
Works nicely, but: dont ever reuse the key, or the generator output bits