PRNG: an algorithm that uses a little bit of true randomness to generate a lot of random looking output also called deterministic random bit generators
usage: generate some expensive true randomness use the true randomness as inputs to prng generate random looking numbers quickly and cheaply with prng
rollback resistance: if the attacker learns the inernal prng state, they cannot learn anything about the previous states or outputs
rollback resistance is not required in secure prng, but it is a useful property
consider alice has used the same prng to generate her secret key and the IVs for encryption mallory compromises the internal state of the prng if the prng is not rollback resistant, mallory can derive previous prng output, such as the secret key.
Application: UUIDs
Scenario: you have a set of objects you need to assign a unique name to every object every name must be unique and unpredictable solution: choose a random value. if you use a random enough thing, the probability of generating the same random value twice are atronomically small
uuid is 128 bit unique values, to generate new uuid, seed a secure prng properly, and generate a random value. often written in hexadecimal.
developer generates an AES key by calling the language’s random function, seeded with the current time. we can attacker do? attacker can try infinite timestamps from before and generate keys
When discussing symmetric-key schemes, we assumed Alice and Bob managed to share a secret key. How can Alice and Bob share a symmetric key over an insecure channel?
Diffie Hellman Key exchange suppose alice and bob want a secret paint color alice and bob agre on a common public color yellow alice generates secret color red and bob generates secret color cyan they both mix their secret colors with yellow, so alice has red yellow and bob has cyan yello alice sends red yellow to bob and bob sends cyan yellow to alice eve now knows red yellow and cyan yellow
recall our paint assumption: separating a paint mixture is hard is there a mathematical version of this?
assume everyone knows a large prime p ( e.g. 2048 bits long ) and a generator g discrete log problem: given g, p, g^a mod p for a random a, it is computationally hard to find a.
diffie hellman assumption: given g, p, g^a mod p, and g^b mod p for random a, b, no polynomial time attacker can distinguish between a random value R and g^ab mod p
alice and bob agree on a prime number p and a base value g p = 23 g = 5
alice chooses secret number a, and sends bob A = g^a mod p. here a= 6 A = 5^6 mod 23 = 15625 mod 23 = 8 bob chooses secret number b, and sends alice B = g^b mod p. here b = 15 B = 5^15 mod 23 = 30517578125 mod 23 = 19
alice computes s = B^a mod p s = 19^6 mod 23 = 47045881 mod 23 = 2
bob computes s = A^b mod p s = 8^15 mod 23 = 35184372088832 mod 23 = 2
they have shared a secret value of 2.
benefit of DHE: Forward Secrecy
Alice and Bob use DHE to agree on a key K = g^ab mod p Alice and Bob use K as a symmetric key after they’re done, discard a, b, and K later, eve steals all of alice and bob’s secrets eve can’t decrypt any messages she recorded: nobody saved a, b, or K, and her recording only has g^a mod p and g^b mod p.
sometimes K is called a session key, because it is only used for a session.
what is the problem with DHE? Mallory can MITM by doing 2 key exchanges. 1 with alice and 1 with bob.
DHE is an active protocol: Alice and Bob need to be online at the same time to exchange keys what if bob wants to encrypt something and send it to alice for her to read later? next time: how do we use public key encryption to send encrypted messages when alice and bob dont share keys and arent online at the same time diffie hellman doesnt provide authentication
public key encryption and digital signatures:
a cryptography scheme that both parties in the communication use different keys in public key schemes each person has two keys public key: known to everybody private key: only known by that person keys come in pairs: every public key corresponds to one private key ( mathematically related ) uses number theory examples: modular arithmetic, factoring, discrete logarithm problem
Messages are numbers. contrast with symmetric key crypography ( messages are strings ) benefit: no longer need to assume that alice and bob already share a secret
alice wants to send a message to bob alice uses bob’s public key to encrypt the message bob decrypts the message with his private key
who can perform encryption? i.e. send messages to bob
scenario: alice wants to send a message to bob alice uses bob’s public key to encrypt the message mallory intercepts the message, changes it to another message encrypted with bob’s public key bob decrypts the message with his private key, cannot tell if it’s from allice.
bad mallory can change the message bob has no way to know
scenario: alice wants to send a message to bob alice usees her private key to encrypt the message bob decrypts the message with alice’s public key who can perform encryption? alice, with her own pirvate key who can do decryption? anyone, because the public key is public
mallory cant change message but can decrypt
encryption w public key ( e.g. send message to alice ) C = Enc(pub-alice, M) M = Dec(priv-alice, C)
Encryption w private key, e.g. alice signs the message C = Enc(priv-alice, M) M = Dec(pub-alice, C)
KeyGen() → PK, SK: gneerates a public / private keypair, where PK is the public key, and SK is the private ( secret ) key
Enc(PK, M) → C: Encrypt a plaintext M using public key PK to produce ciphertext C Dec(SK,C) → M: Decrypt a ciphertext C using a secret key SK properties: Correctness: decrypting a ciphertext should result in the message that was originally encrypted Dec(SK, Enc(PK,M)) = M for all KeyGen() → PK, SK and M Efficiency: encryption / decryption should be fast
security: similar to ind-cpa but alice juts gives eve the public key and eve doesnt request encryptions except for the pair m0 m1 you dont need to worry about the game