Re: [openpgp] Intent to deprecate: Insecure primitives

Daniel Kahn Gillmor <dkg@fifthhorseman.net> Wed, 18 March 2015 01:06 UTC

Return-Path: <dkg@fifthhorseman.net>
X-Original-To: openpgp@ietfa.amsl.com
Delivered-To: openpgp@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 47E281A1BE4 for <openpgp@ietfa.amsl.com>; Tue, 17 Mar 2015 18:06:19 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Level:
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id kvBGzc5CE6Lj for <openpgp@ietfa.amsl.com>; Tue, 17 Mar 2015 18:06:17 -0700 (PDT)
Received: from che.mayfirst.org (che.mayfirst.org [209.234.253.108]) by ietfa.amsl.com (Postfix) with ESMTP id C99A11A1BBD for <openpgp@ietf.org>; Tue, 17 Mar 2015 18:06:16 -0700 (PDT)
Received: from fifthhorseman.net (unknown [38.109.115.130]) by che.mayfirst.org (Postfix) with ESMTPSA id 5E392F984; Tue, 17 Mar 2015 21:06:14 -0400 (EDT)
Received: by fifthhorseman.net (Postfix, from userid 1000) id 7183020296; Tue, 17 Mar 2015 18:05:59 -0700 (PDT)
From: Daniel Kahn Gillmor <dkg@fifthhorseman.net>
To: David Leon Gil <coruus@gmail.com>
In-Reply-To: <CAA7UWsUEF53wTwGtovNPznhxaCOefE-YuxMDiDd-Dqpk-Rmwbg@mail.gmail.com>
References: <CAA7UWsWBoXpZ2q=Lv151R593v3u=SPNif39ySX_-8=fqMniiVg@mail.gmail.com> <87sid5si30.fsf@alice.fifthhorseman.net> <CAA7UWsUEF53wTwGtovNPznhxaCOefE-YuxMDiDd-Dqpk-Rmwbg@mail.gmail.com>
User-Agent: Notmuch/0.18.2 (http://notmuchmail.org) Emacs/24.4.1 (x86_64-pc-linux-gnu)
Date: Tue, 17 Mar 2015 21:05:59 -0400
Message-ID: <87egonm7wo.fsf@alice.fifthhorseman.net>
MIME-Version: 1.0
Content-Type: text/plain
Archived-At: <http://mailarchive.ietf.org/arch/msg/openpgp/_-TR0oQqJyiSrsb4n8gmPNB0m_c>
Cc: "dgil@yahoo-inc.com" <dgil@yahoo-inc.com>, "openpgp@ietf.org" <openpgp@ietf.org>
Subject: Re: [openpgp] Intent to deprecate: Insecure primitives
X-BeenThere: openpgp@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: "Ongoing discussion of OpenPGP issues." <openpgp.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/openpgp>, <mailto:openpgp-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/openpgp/>
List-Post: <mailto:openpgp@ietf.org>
List-Help: <mailto:openpgp-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/openpgp>, <mailto:openpgp-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 18 Mar 2015 01:06:19 -0000

Thanks for the response and the clarifications, David!  More discussion
below...

On Mon 2015-03-16 17:40:52 -0400, David Leon Gil wrote:
> On Sunday, March 15, 2015, Daniel Kahn Gillmor <dkg@fifthhorseman.net> wrote:
>> [David Leon Gil wrote:]
>> > 1. A published public key that is more than 1 year old. (This is
>> > mainly taken care of by requiring > 3070 bit RSA keys...)
>>
>> Can you say more about this?  Is this about a specific cutoff in time,
>> or *anything* that is "more than 1 year old" at the present?  If it's
>> the latter, what effect do you expect this kind of regular key rollover
>> will have?  why is it warranted?
>
> Sure. How many days since the last zero-day security vulnerability on the
> computer you are using? (Hopefully you're using something awesome with
> grsecurity etc., but most users aren't.)
>
> It will be a rolling cut-off. (In future, it is possible that there may be
> some non-user-circumventable prohibition on reusing RSA moduli, in
> particular.)
>
> (This applies, but with somewhat less force, to most hardware-protected
> keys: It is likely that they have been used often enough that more
> sophisticated attacks are likely to have been able to recover the key. And
> if you're using hardware protection, you are probably a likely target of
> attackers with these capabilities.)

This threat analysis might be too narrow: it focuses only on exploitable
software flaws and cryptanalytic attacks, but it omits human factors.  I
worry that acting on it might open up new vectors of attack.

Key continuity is valuable, and understanding how to deal with key
transitions is hard for most end users.  If key transitions happen
regularly and we have no way of surfacing them to the user in a
meaningful, then we have introduced a simple key replacement attack
opportunity for *every* user that comes up at least once a year.  That's
quite a bit cheaper to carry out than factoring a 3072-bit RSA modulus
;)

I can strawman a few approaches to address this without requiring users
to become experts in distinguishing legitimate from fraudulent key
transitions:

 0) subkeys: allow older primary keys, but expect subkeys to be rotated
    regularly, and do not accept regular message signatures from primary
    keys (make them certification-only).  This yields a known key
    migration pattern that can be cryptographically checked.
    Cryptographic certifications by third-parties are made to the
    primary key itself, so those certifications will last (for users who
    want to rely on them) even across subkey rotation.  This approach
    also encourages the use of offline primary keys, which might help
    UI/UX people focus on improving that workflow.  It also works
    entirely with the specs as we know them.

 1) chained primary keys: in this approach, we'd have a primary key that
    gets used for a limited time period (your "one year" cutoff, say),
    but at the end of that time period can certify a replacement primary
    key.  This is a bit more awkward with current tools, but we can
    always build extra tooling.  It also seems unclear how to find the
    new key after a two-period gap: that is, if i know you have key X_0,
    you then replace it with X_1 (certified by X_0, among others), and
    then again with X_2 (certified with X_1, among others), what tooling
    do i use to build the chain?  How do third-party certifications
    persist in this context?  (or do we give up on persistent
    third-party certifications entirely?)

 2) expose key transitions in a way that people can easily understand
    them and distinguish "legit" from "fraudulent"?  I don't even know
    what this would look like, but it smells like it would create a
    serious support burden for any large organization that tried to roll
    it out, as some vocal minority of users will misunderstand and freak
    out thinking that they've been targeted somehow during a standard
    key transition.  We've discussed this situation on the
    messaging@moderncrypto.org list some, with no good proposals i've
    seen other than "rely on your e-mail provider for key continuity".
    But if your provider can swap out your key every year for some other
    key and everyone will accept it, then the "e2e" principle seems to
    be weaker than we'd like.

 3) hope that key transitions somehow won't be an issue or a point of
    weakness?  Not sure how to justify this, but if someone can paint
    this picture convincingly, i'd be a happy camper...

Any other thoughts?


>> > 2. Signature by a public key which has ever signed a message or key
>> > using MD-5 or SHA-1.
>>
>> How would you tell if this is the case?  Isn't ignoring MD5 and SHA1
>> signatures itself sufficient?
>
> An exported key, for example, may have a subkey which it has signed using
> MD5. I consider this to invalidate the signing key.

Why does this invalidate the signing key?  I wouldn't be willing to rely
on the MD5 *signature*, but I don't see why it would invalidate the
entire key, or any signature made over a better algorithm.

The implication seems to be that there is some sort of cross-hash attack
against signatures, like: if you can convince me to sign something with
MD5, then you can craft some phoney signature over an SHA256 digest.

But if this is true (i'm unaware of such an attack), then maybe it's
also true the other way around: if you can convince me to sign something
with SHA256, then maybe you can craft some phoney signature over an MD5
digest.  If this is possible, then you can invalidate my key by
demonstrating an MD5 signature.  this is a surprising outcome!

I think it makes more sense to just ignore signatures over weak digests
than to discard a key that uses a weak digest.

> A brief description of the (tentative) algorithm: Attempt to import an
> importable public key. If any signature packet in the composition uses a
> weak hash algorithm, reject the importable key in its entirety.

This algorithm sounds very risky.  Not every signature in an importable
public key (i prefer the term "OpenPGP certificate") is made by the
public key in the certificate.  I don't think you'd want to reject a key
on the basis of a third-party certification that happens to be in the
certificate.

Also, what if a certification uses an unknown digest algorithm -- this
could be a good algorithm or a bad algorithm, but you don't know which.
It's safest to treat the certification as a bad algorithm, but the right
thing to do in either case is to ignore the certification, but not to
ditch the certificate entirely.

An OpenPGP certificate, once stripped of certifications made over weak
algorithms, still needs to have certain properties (like a
self-certification from the primary key over itself and a User ID).  If
those properties aren't met, then yes: ditch the certificate entirely.
Otherwise, keep the pruned certificate.

wdyt?

           --dkg