1Random Number Generation and Electronic CashDawn [email protected] Number Generation• Many crypto protocols require parties to generate random numbers– Key generation– Generating nonces• How to generate random numbers?– Step 1: how to generate truly random bits?– Step 2: crypto methods to stretch a little bit of true randomness into a large stream of pseudorandom values that are indistinguishable from true random bits (PRNG)3Case Study• Random number generation is easy to get wrong• Can you spot the problems in this example?unsigned char key[16];srand(time(null));for (i=0; i<16; i++)key[i] = rand() & 0xFF;wherestatic unsigned int next = 0;void srand(unsigned int seed) {next = seed;}int rand(void) {next = next * 1103515245 + 12345;return next % 32768;}4Real-world Examples• X Windows “magic cookie” was generated using rand()• Netscape browsers generated SSL session keys using time & process ID as seed (1995)• Kerberos– First discover to be similarly flawed– 4 yrs later, discovered flaw with memset()• PGP used return value from read() to seed its PRNG, rather than the contents of buffer • On-line poker site used insecure PRNG to shuffle cards5Lessons Learned• Seeds must be unpredictable• Algorithm for generating pseudorandom bits must be secure6Generating Pseudorandom Numbers• True random number generator (TRNG)– Generates bits that are distributed uniformly at random, so that all outputs are equally likely, with no patterns, correlations, etc.• Cryptographically secure pseudorandom number generator (CS-PRNG)– Taking a short true-random seed, and generates long sequence of bits that is computationally indistinguishable from true random bits7CS-PRNG• CS-PRNG: cryptographically secure pseudorandom number generator– G: maps a seed to an output G(S)» E.g., G: {0,1}128-> {0,1}1000000– Let K denote a random variable distributed uniformly at random in domain of G– Let U denote a random variable distributed uniformly at random in range of G– G is secure if output G(K) is computationally indistinguishable from U• Sample construction– Use the seed as a key k, and compute AES-CBC(k, 0n)8TRNG (I)• TRNG should be random and unpredictable• Good or bad choices?– IP addresses– Contents of network packets– Process IDs– High-speed clock– Soundcard– Keyboard input– Disk timings9TRNG (II)• How to convert non-uniform sources of randomness into TRNG?– Use a cryptographic hash function, such as SHA1– Suppose x is a value from an imperfect source, or a concatenation of values from multiple sources, and it is impossible for an attacker to predict the exact value x except with probability 1/2n– Then hash(x) truncated to n bits should provide a n-bit value that is uniformly distributed, if hash() is secure10Administrative Matters• HW2 gradedMean: 41.7Standard deviation: 13.21st quartile: 39.82nd quartile (median): 44.53rd quartile: 50.0Maximum: 57.0 11Ecash• Example for how crypto helps e-commerce• Traditional cashAliceCustomerBobMerchantBank1. Withdraw cash2. Spend cash for goods3. Deposit cash12Ecash• Digital form of cash• First attempt, what’s the problem?AliceCustomerBobMerchantBank1. Withdraw ecash:Signature($1, serial #)2. Spend cash for goods:Send Signature($1, serial #)3. Deposit cash:Send Signature($1, serial #)13Desired Properties for Ecash• Anonymous: bank should not know how Alice spends her money• Prevent forging• Prevent double spending14Building Block: Blind Signatures• Blind signature: achieve anonymity– How can Alice get a signature from the Bank without the Bank knowing what message is being signed?• Protocol: – generating blind signature on message m in RSA setting– Bank’s private key (d, p, q), public key (e, N)– Alice computes t/r mod N = mdmod NAliceCustomerBanks = rem mod Nt = sdmod N15Ecash Using Blind Signature• How to use blind signature to build ecash?• A valid $1 bill is a pair (x,y), where y = hash(x)dmod N, hash() is one-way function• How does the ecash protocol work?• Why do we need hash()?• How to prevent double spending?• What to do for different denominations?– Nickles, dimes, dollars16Other Methods for Ecash• Use zero-knowledge proofs (out of scope)– More building blocks of ZKP– Support many properties» Identifying double spenders17Conclusion• Random number generator– CS-PRNG» Definition» How to construct it?– TRNG• Ecash– Example of the power of crypto– Blind
View Full Document
Unlocking...