Network Working Group S. Farrell
Internet-Draft Trinity College Dublin
Intended status: Experimental February 16, 2012
Expires: August 19, 2012
Public Key Checking Protocol
draft-farrell-kc-00
Abstract
Some asymmetric key generation implementations do not use sufficient
randomness giving rise to a number of bad public keys, for example
with known factors, being used on the Internet. This memo specifies
[[for now: just sketches]] an experimental protocol that could be
used by a private key holder to talk to a server that knows the
values of (some of) those bad keys that have been seen in the wild.
The protocol only allows a holder of the relevant private key to
request information, as doing otherwise could weaken the overall
security of the Internet and also considers confidentiality and
privacy as important requirements, as information that a given bad
public key is associated with a particular identifier could also
weaken the security of the Internet.
Status of this Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on August 19, 2012.
Copyright Notice
Copyright (c) 2012 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
Farrell Expires August 19, 2012 [Page 1]
Internet-Draft Public Key Checking Protocol February 2012
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Protocol Overview . . . . . . . . . . . . . . . . . . . . . . . 4
3. Message Formats . . . . . . . . . . . . . . . . . . . . . . . . 5
4. Responder Actions . . . . . . . . . . . . . . . . . . . . . . . 5
5. Requestor Actions . . . . . . . . . . . . . . . . . . . . . . . 5
6. Security Considerations . . . . . . . . . . . . . . . . . . . . 5
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 5
8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 5
9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 6
9.1. Normative References . . . . . . . . . . . . . . . . . . . 6
9.2. Informative References . . . . . . . . . . . . . . . . . . 6
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 6
Farrell Expires August 19, 2012 [Page 2]
Internet-Draft Public Key Checking Protocol February 2012
1. Introduction
[[Text in double square brackets (like this) is commentary. So far
this is just a sketch. I'll do more if there's interest. I'm also
happy to get some help if someone wants to.]]
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119].
Recent publications [blog][lenstra] have found yet again that some
asymmetric key generation implementations do not use sufficient
randomness giving rise to a number of bad public keys, estimated to
be of the order of 0.2% of tested keys, being used on the Internet.
Nonetheless, this small percentage maps to some tens of thousands of
bad keys. And the distribution of bad keys is likely to be
concentrated on specific devices or devices used in specific ways, so
that their Pesudo Random Number Generators (PRNG) for one reason or
another have not produced sufficient randomness at key generation
time.
The publications referred to above involved acquiring large (in
millions) sets of keys and then analysing those for example looking
for common factors. While that is a computationally expensive
process, once done, it should be much quicker to incrementally check
if for example a single new RSA public key has one of the already
known common factors or if any public key is an exact match for a
known-bad key. Thus if a server were to store and analyse many
public keys it could assist key generators in knowing if they have
inadvertently produced a bad key. Note that such a server cannot,
(especially in real-time), determine that a public key is good, but
only whether the public key is known to be bad.
The entire set of known-bad keys cannot however be made available to
all, as some of those keys are in real use and simply publishing
their values could put Internet users at risk. However, if we have a
server with the bad keys and a protocol that only allows the relevant
private key holder to make requests then we may be able to provide a
useful service.
In addition to requiring that only private key holders can query the
server, we must also ensure that eavesdroppers cannot tell whether
the answer to the query is that the key is known to be bad or not
known to be bad. For example, response packet sizes could expose
this information.
Servers implementing this protocol are REQUIRED to store the public
keys presented to them for offline analysis. (Though they may also
Farrell Expires August 19, 2012 [Page 3]
Internet-Draft Public Key Checking Protocol February 2012
acquire public keys for analysis in many other ways.) Thus, the
answer that a requestor receives might change from not-known-bad to
known-bad in a matter of minutes or hours. Some requestors could
take advantage of this and not actually use a key until they have
gotten not-known-bad answers for a configured period.
Note also that my public key may be good now. But might become known
to be bad after someone else has posted e.g. a public key with a
common factor. In other words, ever private key holder could benefit
from periodally checking with a responder for this protocol.
While a server may take hours to find new bad keys, once a server has
a set of e.g. factors of RSA moduli, then it can easily check if a
supplied public key has one of those as a factor, and this is one of
the bad-key patterns seen in the wild. This will not detect all bad
keys however, a process that does reqiure more computation.
Similarly, if there are blacklists of bad keys (e.g. as happened in
the Debian case [deb]) then those can be spotted immediately. So the
server can in such cases give quick and accurate answers.
Ultimately, the server can do anything it wants for any algorithm -
the specific checks are not a part of this protocol.
While a server here could lie and say that a key is not-known-bad
even if it is in fact known-bad, using more than one server could
mitigate that and reduce the level of trust required in the server's
honesty. Clients can also test any server for this kind of
dishonesty by occasionally generating and sending bad keys to check
if the server is honest. This is why we REQUIRE the servers to store
and analyse the keys presented to it. [[Could be interesting games
to play here.]]
2. Protocol Overview
The abstract protocol is simple:
1. the requestor sends a message asking for a challenge
2. the responder replies with a challenge
3. the requestor sends a signed query containing the public key and
challenge
4. the responder replies saying the public key is known to be bad,
or not known to be bad
This protocol MUST be run over a server-authenticated TLS [RFC5246]
session using a TLS ciphersuite that provides strong confidentiality.
Farrell Expires August 19, 2012 [Page 4]
Internet-Draft Public Key Checking Protocol February 2012
In order to ensure confidentiality even in the face of traffic
analysis, we ensure that all request messages are the same size (for
a given public key size) and similarly for response messages. This
can involve the responder sending random bits to the requestor, and
those MUST be of sufficient quality to be useful as input to key
generation.
For additional privacy, a requestor might choose to run this protocol
over some onion routing network such as Tor. [tor] The protocol is
designed to allow for such use-cases. [[not sure yet how to do that
though, help appreciated]]
Note that the challenge has no strucure from the requestor
perspective but might have for the responder. For example, a
responder could include encrypted values in order to ensure that the
challenge is valid and or fresh. [[we might want to make that a MUST
but its probably only useful if done so I could test it from
outside.]]
3. Message Formats
TBD
4. Responder Actions
TBD
5. Requestor Actions
TBD
6. Security Considerations
You'd have to imagine there are:-)
7. IANA Considerations
Dunno
8. Acknowledgements
Farrell Expires August 19, 2012 [Page 5]
Internet-Draft Public Key Checking Protocol February 2012
9. References
9.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC5246] Dierks, T. and E. Rescorla, "The Transport Layer Security
(TLS) Protocol Version 1.2", RFC 5246, August 2008.
9.2. Informative References
[blog] Heniger, N., "New research: There's no need to panic over
factorable keys--just mind your Ps and Qs", February 2012,
<https://freedom-to-tinker.com/blog/nadiah/
new-research-theres-no-need-panic-over-factorable-keys-
just-mind-your-ps-and-qs>.
[deb] "Debian Security Advisory, DSA-1571-1: openssl --
predictable random number generator", May 2008,
<http://www.debian.org/security/2008/dsa-1571>.
[lenstra] Lenstra, A., Hughes, J., Augier, M., Bos, J., Kleinjung,
T., and C. Wachter, "Ron was wrong, Whit is right",
Cryptology ePrint Archive Report 2012/064, February 2012,
<http://eprint.iacr.org/2012/064>.
[tor] "The Tor Project", <http://www.torproject.org/>.
Author's Address
Stephen Farrell
Trinity College Dublin
Dublin, 2
Ireland
Phone: +353-1-896-2354
Email: stephen.farrell@cs.tcd.ie
Farrell Expires August 19, 2012 [Page 6]