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 can’t 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 (we’ll 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() – Don’t 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”: don’t give out more than has been “put in” to the pool
/dev/(u)random problems
/dev/random blocks – slow to read from
/dev/urandom doesn’t block – but might not be initialized at all!!!
Embedded devices:
◦ Often don’t 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: VigènereCipher First described by Bellaso in 1553,
later misattributed to Vigenère
Called « le chiffre indéchiffrable » (“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 indéchiffrable?]
Cryptanalysis of the Vigènere 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 generator’s output with next bit of plaintext
4. To decrypt, Bob XORs next bit of his generator’s output with next bit of ciphertext
Works nicely, but: don’t ever reuse the key, or the generator output bits