Debian Weak Keys and ECDSA

647 views
Skip to first unread message

Hanno Böck

unread,
Jul 8, 2022, 5:28:57 AM7/8/22
to dev-secur...@mozilla.org
Hi,

Given that not so long ago there was extensive discussion on this list
about certificates affected by the 2008 Debian OpenSSL bug [1] and
there seem to be related discussions in the CA/Browser Forum [2] I
wanted to share something:

It seems it is widely believed that the Debian OpenSSL bug does not
affect ECDSA / elliptic curve keys [3]. However that is not true. The
affected Debian versions used OpenSSL 0.9.8, which had support for EC
keys.

The source of this confusion seems to be a footnote in a paper
published shortly after that bug [4] ("but the version of OpenSSL
deployed on Debian-derived distributions ships without any elliptic
curve support"). That is wrong.


There's of course the question whether this matters. I did some checks
with certificate collections and I found no such keys used in the wild.
This is also maybe not surprising: In 2008 elliptic curve support in
TLS was still quite uncommon and considered unusual.


In any case: If you feel like blocking those keys is important, I have
created the different relevant variations for the typical curves p256
and p385 and shared them here (together with all the relevant RSA/DSA
variations of vulnerable keys):
https://github.com/badkeys/debianopenssl

I should note that sometimes this old openssl version seems to generate
broken keys that are not usable. I have not investigated this any
further.


My own tool badkeys will detect such keys:
https://badkeys.info/
https://github.com/badkeys/badkeys


If you want to verify this you may find this script helpful:
https://github.com/badkeys/debianssltools/blob/main/fetchdwkbin
It fetches the archived debian openssl packages and the necessary
libraries from the dependencies so you can run them with LD_PRELOAD on
a modern system.


[1]
https://groups.google.com/g/mozilla.dev.security.policy/c/2uuXLPwGoSA/m/bqUDTXPSAgAJ
[2]
https://archive.cabforum.org/pipermail/servercert-wg/2022-July/003260.html
[3]
https://community.letsencrypt.org/t/is-it-possible-to-make-ecdsa-keys-with-insecure-debian-openssl/133847
[4] https://hovav.net/ucsd/dist/debiankey.pdf

--
Hanno Böck
https://hboeck.de/

Rob Stradling

unread,
Jul 8, 2022, 8:18:44 AM7/8/22
to Hanno Böck, dev-secur...@mozilla.org
> The source of this confusion seems to be a footnote in a paper published shortly after that bug [4] ("but the version of OpenSSL deployed on Debian-derived distributions ships without any elliptic curve support"). That is wrong.

Hi Hanno.  I agree that the OpenSSL 0.9.8 branch contained ECDSA code, but it was possible for distro maintainers to easily disable this during the build process.  I know that Red Hat did this due to ECC patent concerns, and I've always assumed that Debian did too.

Have you looked into whether or not Debian's 2008 OpenSSL build process started with something like this...

> ./config -no-ec -no-ecdh -no-ecdsa
Operating system: x86_64-whatever-linux2
Configuring for linux-x86_64
Configuring for linux-x86_64
   no-camellia     [default]  OPENSSL_NO_CAMELLIA (skip dir)
   no-ec           [option]   OPENSSL_NO_EC (skip dir)
   no-ecdh         [forced]   OPENSSL_NO_ECDH (skip dir)
   no-ecdsa        [forced]   OPENSSL_NO_ECDSA (skip dir)
...

?

From: dev-secur...@mozilla.org <dev-secur...@mozilla.org> on behalf of Hanno Böck <ha...@hboeck.de>
Sent: 08 July 2022 10:28
To: dev-secur...@mozilla.org <dev-secur...@mozilla.org>
Subject: Debian Weak Keys and ECDSA
 
CAUTION: This email originated from outside of the organization. Do not click links or open attachments unless you recognize the sender and know the content is safe.



Hi,

Given that not so long ago there was extensive discussion on this list
about certificates affected by the 2008 Debian OpenSSL bug [1] and
there seem to be related discussions in the CA/Browser Forum [2] I
wanted to share something:

It seems it is widely believed that the Debian OpenSSL bug does not
affect ECDSA / elliptic curve keys [3]. However that is not true. The
affected Debian versions used OpenSSL 0.9.8, which had support for EC
keys.

The source of this confusion seems to be a footnote in a paper
published shortly after that bug [4] ("but the version of OpenSSL
deployed on Debian-derived distributions ships without any elliptic
curve support"). That is wrong.


There's of course the question whether this matters. I did some checks
with certificate collections and I found no such keys used in the wild.
This is also maybe not surprising: In 2008 elliptic curve support in
TLS was still quite uncommon and considered unusual.


In any case: If you feel like blocking those keys is important, I have
created the different relevant variations for the typical curves p256
and p385 and shared them here (together with all the relevant RSA/DSA
variations of vulnerable keys):


I should note that sometimes this old openssl version seems to generate
broken keys that are not usable. I have not investigated this any
further.


My own tool badkeys will detect such keys:
https://nam04.safelinks.protection.outlook.com/?url=https%3A%2F%2Fbadkeys.info%2F&amp;data=05%7C01%7Crob%40sectigo.com%7C7605928cf95f4802640a08da60c4490b%7C0e9c48946caa465d96604b6968b49fb7%7C0%7C0%7C637928695060081543%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&amp;sdata=n2%2BSS9wC9Dx%2FPIL4AmzrEzWgxKqHeTWJ837Vcss%2B6Zo%3D&amp;reserved=0
https://nam04.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fbadkeys%2Fbadkeys&amp;data=05%7C01%7Crob%40sectigo.com%7C7605928cf95f4802640a08da60c4490b%7C0e9c48946caa465d96604b6968b49fb7%7C0%7C0%7C637928695060081543%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&amp;sdata=G7Cn2AlEi5IdTdWFmhTPnmiC4zDkO9uM3c7CKuVlbTs%3D&amp;reserved=0



If you want to verify this you may find this script helpful:

It fetches the archived debian openssl packages and the necessary
libraries from the dependencies so you can run them with LD_PRELOAD on
a modern system.


[1]
https://nam04.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgroups.google.com%2Fg%2Fmozilla.dev.security.policy%2Fc%2F2uuXLPwGoSA%2Fm%2FbqUDTXPSAgAJ&amp;data=05%7C01%7Crob%40sectigo.com%7C7605928cf95f4802640a08da60c4490b%7C0e9c48946caa465d96604b6968b49fb7%7C0%7C0%7C637928695060081543%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&amp;sdata=PIh7P91mKdVeQRBvu2adA4HtfyFUYuUMEmmNMWyTyjs%3D&amp;reserved=0
[2]
https://nam04.safelinks.protection.outlook.com/?url=https%3A%2F%2Farchive.cabforum.org%2Fpipermail%2Fservercert-wg%2F2022-July%2F003260.html&amp;data=05%7C01%7Crob%40sectigo.com%7C7605928cf95f4802640a08da60c4490b%7C0e9c48946caa465d96604b6968b49fb7%7C0%7C0%7C637928695060081543%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&amp;sdata=4GY%2BpoLa21rl%2Bvhd6N8iuJX4kOpjHjgQX3%2BpNCFJc3k%3D&amp;reserved=0
[3]
https://nam04.safelinks.protection.outlook.com/?url=https%3A%2F%2Fcommunity.letsencrypt.org%2Ft%2Fis-it-possible-to-make-ecdsa-keys-with-insecure-debian-openssl%2F133847&amp;data=05%7C01%7Crob%40sectigo.com%7C7605928cf95f4802640a08da60c4490b%7C0e9c48946caa465d96604b6968b49fb7%7C0%7C0%7C637928695060081543%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&amp;sdata=e6c3XqeNoZTm61MyRu3L93hgN3RZietZnnqYs6skm7s%3D&amp;reserved=0
[4] https://nam04.safelinks.protection.outlook.com/?url=https%3A%2F%2Fhovav.net%2Fucsd%2Fdist%2Fdebiankey.pdf&amp;data=05%7C01%7Crob%40sectigo.com%7C7605928cf95f4802640a08da60c4490b%7C0e9c48946caa465d96604b6968b49fb7%7C0%7C0%7C637928695060081543%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&amp;sdata=KI0wGcGEmUsXaS9kOM2ZGeDwU4pGDTcrI5MvjaUAbv8%3D&amp;reserved=0

--
Hanno Böck
https://nam04.safelinks.protection.outlook.com/?url=https%3A%2F%2Fhboeck.de%2F&amp;data=05%7C01%7Crob%40sectigo.com%7C7605928cf95f4802640a08da60c4490b%7C0e9c48946caa465d96604b6968b49fb7%7C0%7C0%7C637928695060081543%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&amp;sdata=IA8oqofl9GrGmenndCb%2BoQqw8c8WA%2B1GkLf5g%2FjmaEI%3D&amp;reserved=0

--
You received this message because you are subscribed to the Google Groups "dev-secur...@mozilla.org" group.
To unsubscribe from this group and stop receiving emails from it, send an email to dev-security-po...@mozilla.org.
To view this discussion on the web visit https://nam04.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgroups.google.com%2Fa%2Fmozilla.org%2Fd%2Fmsgid%2Fdev-security-policy%2F20220708112853.51605585%2540computer&amp;data=05%7C01%7Crob%40sectigo.com%7C7605928cf95f4802640a08da60c4490b%7C0e9c48946caa465d96604b6968b49fb7%7C0%7C0%7C637928695060081543%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&amp;sdata=6FIAqujVyJzHSNqSNty%2B5tvqZJ1QlwL22bEnN%2B2u64o%3D&amp;reserved=0.

Julien Cristau

unread,
Jul 8, 2022, 8:24:33 AM7/8/22
to Rob Stradling, Hanno Böck, dev-secur...@mozilla.org
Build logs from that era (e.g. https://buildd.debian.org/status/fetch.php?pkg=openssl&arch=i386&ver=0.9.8g-1&stamp=1192885956&raw=0) suggest EC support was not disabled, as far as I can tell.

Cheers,
Julien

To view this discussion on the web visit https://groups.google.com/a/mozilla.org/d/msgid/dev-security-policy/MW4PR17MB4729410BDA8D258087F95B5EAA829%40MW4PR17MB4729.namprd17.prod.outlook.com.

Hanno Böck

unread,
Jul 8, 2022, 8:30:02 AM7/8/22
to Rob Stradling, dev-secur...@mozilla.org
On Fri, 8 Jul 2022 12:18:39 +0000
Rob Stradling <r...@sectigo.com> wrote:

> Hi Hanno. I agree that the OpenSSL 0.9.8 branch contained ECDSA
> code, but it was possible for distro maintainers to easily disable
> this during the build process. I know that Red Hat did this due to
> ECC patent concerns, and I've always assumed that Debian did too.
>
> Have you looked into whether or not Debian's 2008 OpenSSL build
> process started with something like this...

It doesn't.
Check here, which is one of the versions in the affected timeframe:
https://snapshot.debian.org/package/openssl/0.9.8g-3/

openssl_0.9.8g-3.diff.gz adds a few no-* options to the compilation,
but not no-ec.

Also given I actually created ec keys with those affected versions I am
pretty sure they haven't disabled it :-)

Rob Stradling

unread,
Sep 8, 2022, 9:44:48 AM9/8/22
to Hanno Böck, dev-secur...@mozilla.org
Hanno and Julien, thanks for confirming that EC key generation was enabled in the affected Debian distributions.

https://github.com/CVE-2008-0166/key_generator is now able to generate the secp256r1 and secp384r1 keypairs that are predictable (due to the CVE-2008-0166 vulnerability), and I've generated and added the private keys (uncompressed, with named curve parameters, in SEC1 format) to https://github.com/CVE-2008-0166/private_keys.

Do you have any thoughts on whether CAs should also consider the compressed and/or hybrid point conversion forms when blocking the corresponding public keys?  The vulnerable Debian OpenSSL versions appear to support these point conversion forms - "openssl ecparam -genkey -conv_form <compressed,uncompressed,hybrid>" - but AFAICT the "-conv_form" option is always ignored when "-genkey" is used.

I think the best approach is for CAs to use some sort of normalized form when performing key checks.  For example: always set the public exponent to 65537 before adding an RSA public key to a blocklist (or before checking if it's already blocked); and always convert the EC point to the uncompressed form before adding an EC public key to a blocklist (or before checking if it's already blocked).

BTW Hanno, there are some discrepancies between the predictable EC keypairs in https://github.com/CVE-2008-0166/private_keys and the ones in https://github.com/badkeys/debianopenssl :
  - In around half of your "noreadrnd" (aka "nornd-old") keys, the public key BITSTRING has a nonzero "unused bits" octet.  (AIUI, the "unused bits" should always be zero, because https://www.rfc-editor.org/rfc/rfc5915#section-3 defers to https://www.rfc-editor.org/rfc/rfc5480#section-2.2, which defines the public key as an OCTET STRING).
  - Some of your "noreadrnd" key files cannot be parsed by "openssl ec".  For example, 10211-nornd-old.key is missing a trailing 0x00 byte at the end of the public key.  (Compare that against https://github.com/CVE-2008-0166/private_keys/blob/main/le32/secp256r1/secp256r1_10211_noreadrnd_le32.key)

From: Hanno Böck <ha...@hboeck.de>
Sent: 08 July 2022 13:29
To: Rob Stradling <r...@sectigo.com>
Cc: dev-secur...@mozilla.org <dev-secur...@mozilla.org>
Subject: Re: Debian Weak Keys and ECDSA
 
CAUTION: This email originated from outside of the organization. Do not click links or open attachments unless you recognize the sender and know the content is safe.


On Fri, 8 Jul 2022 12:18:39 +0000
Rob Stradling <r...@sectigo.com> wrote:

> Hi Hanno.  I agree that the OpenSSL 0.9.8 branch contained ECDSA
> code, but it was possible for distro maintainers to easily disable
> this during the build process.  I know that Red Hat did this due to
> ECC patent concerns, and I've always assumed that Debian did too.
>
> Have you looked into whether or not Debian's 2008 OpenSSL build
> process started with something like this...

It doesn't.
Check here, which is one of the versions in the affected timeframe:


openssl_0.9.8g-3.diff.gz adds a few no-* options to the compilation,
but not no-ec.

Also given I actually created ec keys with those affected versions I am
pretty sure they haven't disabled it :-)

--
Hanno Böck

Hanno Böck

unread,
Sep 9, 2022, 5:54:36 AM9/9/22
to 'Rob Stradling' via dev-security-policy@mozilla.org, Rob Stradling
On Thu, 8 Sep 2022 13:44:42 +0000
"'Rob Stradling' via dev-secur...@mozilla.org"
<dev-secur...@mozilla.org> wrote:

> I think the best approach is for CAs to use some sort of normalized
> form when performing key checks. For example: always set the public
> exponent to 65537 before adding an RSA public key to a blocklist (or
> before checking if it's already blocked); and always convert the EC
> point to the uncompressed form before adding an EC public key to a
> blocklist (or before checking if it's already blocked).

What I do in badkeys is that I don't blocklist keys, but values.
Modulus for RSA, x coordinate for EC.

For EC this makes me not worry about any encoding issues, and the x
coordinate is enough to uniquely identify a key.

For RSA there's a simple mathematical reason: If you have two keys with
the same N and different e, and one key is broken, then the other is
automatically broken as well (because if you know d you can factor N
and this calculate any other key with the same N and a different e).

The debian bug is a good example why this is a good idea: You can
create RSA keys with e=3 with that old openssl version, the default is
e=65537. If you block whole keys and you would want to consider that
you'd need to double the number of keys to block. But if you block the
modulus you already have that case covered.

Rob Stradling

unread,
Sep 13, 2022, 3:53:51 PM9/13/22
to Hanno Böck, 'Rob Stradling' via dev-security-policy@mozilla.org
> What I do in badkeys is that I don't blocklist keys, but values.
> Modulus for RSA, x coordinate for EC.

I agree that this approach makes sense.

> The debian bug is a good example why this is a good idea: You can
> create RSA keys with e=3 with that old openssl version, the default is
> e=65537. If you block whole keys and you would want to consider that
> you'd need to double the number of keys to block. But if you block the
> modulus you already have that case covered.

That's only true for a key-based blocklist system that doesn't "normalize" the keys, whereas I'm suggesting modifying the blocked keys and the candidate keys as follows...
  - always set the RSA modulus to 65337
  - always use the uncompressed ECC key format
  - always re-encode the key to ensure canonical DER encoding
...before adding them to the blocklist or checking if they're already blocked.

I think that both your approach and my approach are valid.  If starting from scratch, I'd choose your approach.  My approach is a bit more complex and probably will require more care when implementing, but it might be a better fit for any CA that already has a key-based blocklist system.

From: Hanno Böck <ha...@hboeck.de>
Sent: 09 September 2022 10:54
To: 'Rob Stradling' via dev-secur...@mozilla.org <dev-secur...@mozilla.org>
Cc: Rob Stradling <r...@sectigo.com>

Subject: Re: Debian Weak Keys and ECDSA
CAUTION: This email originated from outside of the organization. Do not click links or open attachments unless you recognize the sender and know the content is safe.


Reply all
Reply to author
Forward
0 new messages