9/28/13

Cryptography & Entropy (Randomness).

Uses for Randomness in Cryptography:

To generate (cryptographic) key material, we need a random number generater, or RNG. Generating good randomness is a vital part of many cryptographic operations.

Entropy:

The measure for randomness is called entropy. Note that the entropy of a value depends on how much you know. A random 32-bit word has 32 bits of entropy.

Idea for it (intuition) is such that if you have a 32-bit word that is completely random, then it has 32 bits of entropy. If the 32-bit word takes only four different values, and each value has a 25% chance of occuring, then the word has 2 bits of entropy. Entropy does not measure how many bits are in a value, but how uncertain you are about the value.

Suppose that you happen to know that the value has exactly 18 bits that are 0, and 14 bits that are 1. There are about 2^28.8 values that satisfy these requirements, and the entropy is also limited to 28.8 bits. In other words, the more you know about a value, the smaller its entropy is.

There are few definitions of entropy that mathematicians use, depending on what they are working on. When physicists talk about entropy, they use the word for a concept from thermodynamics that is only tangentially related.

Real Random:

The world is not ideal, and real random data is extremely hard to find, if at all. Many implementers seem too optimistic about randomness or entropy that can be extracted from various sources. Measured data is often predictable, and there are attacks that try to overhear or affect it, or more.

Some modern computers have a built-in real random number generator, it makes some of the attacks more difficult (such as overhearing time of keystroke used to generate number, or affecting result of random number generation). The random number generator is still only accessible to the operating system, so an application has to trust the operating system to handle the random data in a secure manner.

When more and more data is known about real random number generators, they are less and less useful.

Pseudorandom Data:

Alternative to using real random data (which is not always available, and risky sometimes to use), is to use pseudorandom data. Pseudorandom data is not really random at all. It is generated from a seed by deterministic (for same data, producing same results no matter how many times it's run) algorithm. If you know the seed, you can predict the pseudorandom data.

Pseudorandom Number Generators:

Traditional pseudorandom number generators, or PRNGs, are not secure against a clever adversary. They are designed to eliminate statistical artifacts, not to withstand an intelligent attacker.

In the context of cryptographic system, we have requirements. Even if the attacker sees a lot of the random data generated by the PRNG, she should not be able to predict anything about the rest of the output of the PRNG. We call such PRNG cryptographically strong. For cryptography, only such should be used.

In PRNGs, real random data is used for a single thing: to seed a PRNG. Perhaps once, perhaps many times.

No comments:

Post a Comment