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, . [deb] "Debian Security Advisory, DSA-1571-1: openssl -- predictable random number generator", May 2008, . [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, . [tor] "The Tor Project", . 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]