This week’s study group was held on Tuesday 30th
October. Gaven and Stefan presented two papers introducing real world attacks
on bad randomness. The talks were based on the following papers:
- Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices by Nadia Heninge, Zakir Durumeric, Eric Wustrow, J. Alex Halderman.
- Ronwas wrong, Whit is right by Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung and Christophe Wachter.
Security
often depends on keys being chosen uniformly at random, thus randomness is
critical for crypto. Long studies have been done in this area and it would be
expected that modern operating systems and server software generate random
numbers securely. Both papers test that proposition empirically by examining
the public keys in use on the Internet.
In Ps and Qs the authors conduct a wide
survey of two of the most important cryptographic protocols TLS and SSH
collecting 5.8 million unique TLS certificates from 12.8 million hosts and 6.2
million unique SSH host keys from 10.2 million hosts. Their results give “a
macroscopic perspective of the universe of keys”. Then they analyze this dataset
to find evidence related to inadequate randomness and find that at least 5.57%
of TLS hosts and 9.60% of SSH hosts use the same keys as other hosts in an
apparently vulnerable manner.
They
also compute the private keys for 64,000 (0.50%) of the TLS hosts and 108,000 (1.06%)
of the SSH hosts from their data by exploiting known weaknesses of RSA and DSA
when used with insufficient randomness. For RSA, distinct moduli that share
exactly one prime factor will result in public keys that appear distinct but their private keys can be computed by calculating the greatest common divisor
(GCD). Their algorithm computes the GCDs of all pairs of 11 million distinct
public RSA moduli in less than 2 hours and they are able to obtain the private
keys for 0.50% of TLS hosts and 0.03% of SSH hosts. For DSA, if a key is used
to sign two different messages using the same ephemeral key, an attacker can
compute the signer’s long-term private key. Their SSH data contained DSA
signatures with the same ephemeral keys during signing. This feature resulted
in successful computing of the private keys for 1.6% of SSH DSA hosts.
An
investigation on hundreds of vulnerable hosts showed that nearly all served
information identifying them as headless or embedded systems. These kinds of devices
usually generate keys automatically during the first boot and they may have
limited entropy sources compared to traditional personal computers. The
investigation also showed that the examination of clusters of hosts that shared
a key or factor links them with a manufacturer or device model. They conclude
that the problems are caused by specific defective implementations that
generate keys without having collected sufficient entropy. They finally
identify vulnerable hardware and software from 54 manufacturers.
In
the same paper the authors explore the root causes of these vulnerabilities by
investigating popular open-source software components from the population of
vulnerable devices. Based on the aforementioned devices it is clear that none implementation was solely responsible for the vulnerabilities. All the examined
software packages relied on /dev/urandom to produce cryptographic keys. Linux’s
random number generator can present a boot-time entropy hole which causes
urandom to produce deterministic output under conditions that can occur in
headless and embedded devices. Experiments with OpenSSL and Dropbear SSH showed that repeated output from the system random number generator can lead to
repeated long-term keys and also to factorable RSA keys and repeated DSA
ephemeral keys.
The
authors also provide some recommendations for developers of operating systems,
cryptographic libraries and applications, for device manufacturers, certificate
authorities, end users and the security and cryptography communities. Their
conclusion states that the margin of safety is slimmer than we might prefer but there
is no reason to doubt the security of most keys generated interactively by
users on traditional personal computers.
To
OS developers it is suggested to make sure the operating system maintains a
secure PRNG that refuses to return data until it has been seeded with a minimum
amount of randomness and is continually seeded with fresh entropy collected
during operation. The operating system should also provide an interface to
indicate how much entropy it has mixed into its PRNG, so that applications can
gauge whether the state is sufficiently secure for their needs. Generally
speaking cryptographic libraries should default to using the most secure
mechanisms available. So, library developers should use RSA and DSA
defensively. Also, if the OS provides a mechanism to flag that the entropy it has
collected is insufficient for cryptographic use, they should do not proceed
with key generation.
Application
developers are advised to generate keys on first use not during installation
or first boot. Developers should avoid working around low-entropy states by
ignoring or disabling such warnings (with extremely dangerous results) and they
must frequently add entropy from the operating system.
Device
makers should tend to generate fresh keys on the device after sufficient
randomness has been collected or to force users to upload their own keys. They
should avoid factory-default keys or certificates. Embedded (or headless)
device makers should make sure that effective entropy sources are present, and
that these are being collected in advance of cryptographic operations. Devices should be initialized with truly random seeds at the factory. Device
makers should test cryptographic randomness on the completed device and use
hardware random number generators when possible.
Cryptographic
keys and certificates that were included in the device or were automatically
generated at first boot, should be manually regenerated by end users. Security
and crypto researchers should be aware that the fact that all major OSs now
provide cryptographic RNGs might lead experts to assume that any entropy
problems that still occur are the fault of developers taking foolish shortcuts.
The paper suggests otherwise: entropy-related vulnerabilities can result from
complex interaction between hardware, operating systems, applications and
cryptographic primitives.
The
second paper brings the same alarming results. Despite the fact that numerous studies
have been conducted to assess the state of the current public key
infrastructure, several problems have been identified that are related
to the way certificates are used. A worrisome finding is that among the 4.7
million distinct 1024-bit RSA moduli that were originally collected by the
authors, 12720 have a single large prime factor in common. In a set of 11.4
million RSA moduli, 26965 are vulnerable, including ten 2048-bit ones. When
exploited, it could affect the expectation of security that the public key
infrastructure is intended to achieve. For
the needs of the current experiment the authors collected as many openly
accessible public keys as possible from the web, resulting in a set of 11.7
million public keys contains 6.4 million distinct RSA moduli. The remainder is
almost evenly split between ElGamal keys and DSA keys, plus a single ECDSA key.
All keys were checked for consistency such as compositeness, primality and
(sub)group membership tests.
The
assumption that entropy of the output distribution (of standardized RSA key
generation) is always almost maximal and the outputs are hard to factor if
factoring in general is hard, sometimes fails. The findings reveal that
duplication of keys is more frequent in the collected set than in sets
described in other works. More seriously, authors discovered 12934 different RSA
moduli that offer no security.
They
conclude that systems such as RSA that require multiple secrets during
key-setup, are more affected by the difficulty to generate proper random values
than systems that require a single secret. For RSA multiple secrets can be
avoided, for instance by using moduli pq for k-bit primes p chosen such that q
= [(22k−1 + p − (22k−1 mod p))/p] is prime.
No comments:
Post a Comment