Mining Your P’s and Q’s: Detection of Widespread Weak Keys in Network
Devices:
Summary: The authors
conducted an Internet-wide scan of RSA public keys and DSA signatures. With
this information, they searched for pairs of hosts whose RSA keys share prime
factors, or whose DSA signatures share ephemeral keys. Both scenarios
potentially compromise each host’s private key. The study showed that devices
are vulnerable when they generate keys on boot, before the OS has been able to
collect sufficient entropy to seed their pseudo-random number generators.
Thoughts: The results of
this study seem to indicate that currently used entropy sources provide good
sources of randomness when given sufficient collection time. However, the
authors note that several popular implementations of RSA and DSA do not use the
Linux interface random, which blocks
until sufficient entropy has been collected, but instead use random, which immediately returns with
the requested number of random bytes. The authors also note that the greatest
vulnerabilities come from imbedded or headless devices that do not have user
input nor, sometimes, disk drives. Both of which are commonly used to generate
entropy.
This discussion seems to indicate
that our work should focus on sources of randomness that would be available to
such embedded devices. Also, it would be helpful if an entropy source could be
discovered that would quickly generate randomness. This would discourage
developers from dismissing the use of a blocking implementation.
Analysis of the Linux Random Number Generator:
Summary: The authors have
analyzed the source code for the Linux Random Number Generator (LRNG). They
provide details as to its functionality and mention several potential security
flaws. The LRNG maintains three separate entropy pools. The primary pool gets
takes entropy from mouse/keyboard inputs, disk I/O operations, and certain
interrupts. The secondary and urandom pools then take entropy from the primary
pool. The secondary pool feeds the random system call which blocks until
sufficient entropy has been gathered. The urandom pool feeds the urandom system
call which immediately returns with the requested number of random bytes,
regardless of the amount of entropy gathered.
Thoughts: Most of the
vulnerabilities described by the authors seem to be a result of the specific
implementation of the LRNG, and could be remedied by the solutions that the
authors suggest. The largest vulnerability however, is for embedded devices
with no hard disk such as certain routers. As the authors note, the only real
source of entropy is network interrupts which are also potentially observable
by an attacker. The best advancement to the field would be to find a better
source of entropy for embedded devices such as this.
When Good Randomness Goes Bad: Virtual Machine Reset Vulnerabilities
and Hedging Deployed Cryptography:
Summary: The authors
discuss how a VM snapshot may cache cryptographic randomness. Running from this
snapshot can then lead to using repeated, and thus predictable randomness. The
most significant/likely vulnerability is that DSA may generate a repeated r
value due to the RNG being seeded with the same, old value.
The authors also discuss a method
for hedging against potential randomness failures. The general idea is to hash
the generated random bits before using them in any cryptographic operation.
This does not alleviate the problem of bad randomness, but ensures slightly
stronger security in the face of a bad RNG.
Thoughts: The authors have
pointed out a significant vulnerability that comes about from repeated
randomness. They point out that the problem can be solved by ensuring that
fresh randomness is incorporated into any cryptographic operations immediately
before it is computed. They do mention however, that this may be a problem if
such randomness sources are also cached. Therefore, they suggest using hardware
generated randomness for this purpose rather than an entropy pool such as the
Linux random number generator, which may be cached. This discussion highlights
the largest problem in the field: there is a tradeoff between performance and
security. It may take a significant amount of time to generate sufficient
entropy for many cryptographic operations to be considered secure. However,
many developers are more interested in the performance of their applications,
and are not willing to wait for this security.
The authors also discuss hedging
which adds some security in the face of a bad RNG. However, they note that this
merely allows a function to fail gracefully. Therefore, despite this method,
effective random number generation is still extremely important.
A Statistical Test Suite for Random and Pseudorandom Number Generators
for Cryptographic Applications:
Summary: This paper
describes a test suite that can be used to determine if a given random number
generator outputs bit sequences that are sufficiently random. The main purpose
of the tests described is to ensure that the random number generator produces
bits that are uniformly random, and completely independent. The following table
outlines each test and its purpose.
|
Test
|
Purpose
|
|
The Frequency (Monobit) Test
|
Determine whether the number of ones and zeros in a sequence are
approximately the same as would be expected for a truly random sequence
|
|
Frequency Test within a Block
|
Determine whether the frequency of ones in an M-bit block is
approximately M/2, as would be expected under an assumption of randomness.
|
|
The Runs Test
|
Determine whether the number of runs of ones and zeros of
various lengths is as expected for a random sequence.
|
|
Tests for the Longest-Run-of-Ones in a Block
|
Determine whether the length of the longest run of ones within
the tested sequence is consistent with the length of the longest run of ones
that would be expected in a random sequence.
|
|
The Binary Matrix Rank Test
|
Check for linear dependence among fixed length substrings of the
original sequence.
|
|
The Discrete Fourier Transform (Spectral) Test
|
Detect periodic features (i.e., repetitive patterns that are
near each other) in the tested sequence that would indicate a deviation from
the assumption of randomness.
|
|
The Non-overlapping Template Matching Test
|
Detect generators that produce too many occurrences of a given
non-periodic (aperiodic) pattern.
|
|
The Overlapping Template Matching Test
|
Same as Non-Overlapping Template Matching Test but when the
pattern is found, the
window slides only one bit before resuming the search.
|
|
Maurer's "Universal Statistical" Test
|
Detect whether or not the sequence can be significantly
compressed without loss of information.
|
|
The Linear Complexity Test
|
Determine whether or not the sequence is complex enough to be
considered random.
|
|
The Serial Test
|
Determine whether the number of occurrences of the 2m
m-bit
overlapping patterns is approximately the same as would be expected for a
random sequence.
|
|
The Approximate Entropy Test
|
Compare the frequency of overlapping blocks of two
consecutive/adjacent lengths (m and m+1) against
the expected result for a random sequence.
|
|
The Cumulative Sums (Cusums) Test
|
Determine whether the cumulative sum of the partial sequences
occurring in the tested sequence is too large or too small relative to the
expected behavior of that cumulative sum for random sequences.
|
|
The Random Excursions Test
|
Determine if the number of visits to a particular state within a
cycle deviates from what one would expect for a random sequence.
|
|
The Random Excursions Variant Test
|
Detect deviations from the expected number of visits to various
states in the random walk.
|
Thoughts: This test suite
will be very useful for our purposes. It will be crucial in testing the sources
of randomness that we come up with. A RNG is of no use if its results are not
random or independent as an attacker may be able to gain information if the RNG
is used for cryptographic purposes.
How to Generate Cryptographically Strong Sequences of Pseudo Random
Bits:
Summary: The authors
present a pseudo random number generator that, given a random seed, is capable
of producing a statistically random bit sequence. The generator relies on the intractability
of the Discrete Logarithm Problem to show that given any sequence of generated
bits, an attacker cannot predict the next bit with probability greater than 0.5
in polynomial time.
Thoughts: Pseudo Random
number generators are extremely important for cryptographic applications since
such functions often cannot wait for a true random number generator to provide
enough randomness for each bit requested. Therefore, a true RNG can act as a
seed to a PRNG to provide a statistically random sequence. This assumes
however, that the PRNG sequence appears random and independent without
knowledge of the seed. For our purposes, PRNG’s are important in that we must
find entropy sources that can generate a seed for such a generator.
