openssh bugs - Aug 2018 - [Bug 2901] New: ssh-keygen generates an invalid key sometimes

https://bugzilla.mindrot.org/show_bug.cgi?id=2901

            Bug ID: 2901
           Summary: ssh-keygen generates an invalid key sometimes
           Product: Portable OpenSSH
           Version: 7.7p1
          Hardware: All
                OS: Linux
            Status: NEW
          Severity: normal
          Priority: P5
         Component: ssh-keygen
          Assignee: unassigned-bugs at mindrot.org
          Reporter: whissi at gentoo.org

Created attachment 3173
  --> https://bugzilla.mindrot.org/attachment.cgi?id=3173&action=edit
test script to generate keys

We received the following bug report: https://bugs.gentoo.org/664384

Summary:
It looks like that `ssh-keygen -t ecdsa -b 521 -f testkey` sometimes
generates an invalid key. I.e. when when you try to change passphrase
of that newly generate key, `ssh-keygen -y -f testkey` will fail with
> Load key "testkey": invalid format
Please see the attached test script (it usually takes between 5-600
attempts).

In addition to Gentoo, I was able to reproduce the same problem on
Debian Stretch using openssh-portable 7.7p1 vanilla sources (I used
https://sourceforge.net/projects/hpnssh/files/OpenSSL-1.1%20Compatibility/
to be able to compile against Debian's OpenSSL 1.1.x version but this
shouldn't matter).

I tested against 7.8p1 and was so far unable to reproduce. According to
bisect, the error disappears with the switch to the "new" private key
format, i.e. commit
> commit ed7bd5d93fe14c7bd90febd29b858ea985d14d45
> Author: djm at openbsd.org <djm at openbsd.org>
> Date:   Wed Aug 8 01:16:01 2018 +0000
> 
>     upstream: Use new private key format by default. This format is
> 
>     suported by OpenSSH >= 6.5 (released January 2014), so it should be
supported
>     by most OpenSSH versions in active use.
> 
>     It is possible to convert new-format private keys to the older
>     format using "ssh-keygen -f /path/key -pm PEM".
> 
But I guess the error is still present. I am just unable to change test
script to produce keys in old format.

-- 
You are receiving this mail because:
You are watching the assignee of the bug.

https://bugzilla.mindrot.org/show_bug.cgi?id=2901

Alexander Sergeyev <sergeev917 at gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |sergeev917 at gmail.com

--- Comment #1 from Alexander Sergeyev <sergeev917 at gmail.com> ---
I would like to make couple of moments clearer.

It seems there are two related problems. The first problem: when
provided an invalid passphrase, `ssh-keygen -p` (ie changing or
removing the passphrase) might log "invalid format" error instead of
the expected "incorrect passphrase supplied to decrypt private key"
error.

The following listing demonstrates this behaviour. Usage of an invalid
passphrase "x" led to "invalid format" error. It's
unlikely to be true
since the key is successfully read with the correct passphrase (at the
end of the listing):
> $ ssh-keygen -p -P x -N '' -f testkey_rsa 0<&- 2>&1
> Failed to load key testkey_rsa: invalid format
> $ ssh-keygen -p -P wrongpassphrase -N '' -f testkey_rsa 0<&-
2>&1
> Failed to load key testkey_rsa: incorrect passphrase supplied to decrypt
private key
> $ ssh-keygen -p -P 12345678 -N '' -f testkey_rsa 0<&-
2>&1
> Your identification has been saved with the new passphrase.
The second problem is about inability to read certain private keys. The
attached script is looping over key generation and trying to read it.
Sometimes the reading part fails with the "invalid format" message and
that is the main problem.

It's observed that key loading fails early. The script uses `ssh-keygen
-p` with an invalid passphrase to validate ability to load the private
key; `ssh-keygen` is expected to either fail right away or complain
about the wrong passphrase. Note that the first problem is interfering
here and might cause a false positive. To that end I urge you to go to
the original bug report and use the third version of the script --
which uses `ssh-keygen -y` instead of `ssh-keygen -p` and more reliable
for the purpose.
> It looks like that `ssh-keygen -t ecdsa -b 521 -f testkey` sometimes
generates an invalid key.
I think it might not be the case. There is a difference between openssh
linked against openssl-1.0.2o and openssl-1.0.2p. The problematic one
is openssl-1.0.2p (newer version); openssh+openssl-1.0.2p can produce
keys which are not loadable ("invalid format"). But when afterwards
openssl is downgraded to openssl-1.0.2o -- the same key becomes
loadable. This contradicts the idea that the key is actually corrupted.
Therefore, I think the source of the problem should attributed to a
regression in either openssl or openssh integration with openssl.

-- 
You are receiving this mail because:
You are watching the assignee of the bug.

https://bugzilla.mindrot.org/show_bug.cgi?id=2901

--- Comment #2 from Thomas Deutschmann <whissi at gentoo.org> ---
(In reply to Alexander Sergeyev from comment #1)
> I think it might not be the case. There is a difference between
> openssh linked against openssl-1.0.2o and openssl-1.0.2p. The
> problematic one is openssl-1.0.2p (newer version);
Like said in the Gentoo bug I cannot confirm this. I see this problem
on boxes which have never seen openssl-1.0.2p.

However, I haven't checked if the key generated with openssh-7.7p1 and
is invalid according to same ssh-keygen command after generation, works
on any different system/version.

-- 
You are receiving this mail because:
You are watching the assignee of the bug.

https://bugzilla.mindrot.org/show_bug.cgi?id=2901

--- Comment #3 from Alexander Sergeyev <sergeev917 at gmail.com> ---
(In reply to Thomas Deutschmann from comment #2)
> Like said in the Gentoo bug I cannot confirm this. I see this
> problem on boxes which have never seen openssl-1.0.2p.
In order to ease reproduction I've prepared docker-based scripts that
compile openssl and openssh from sources on alpine:
https://github.com/sergeev917/openssh-openssl-bug-repro. Even without
using docker it's a better and more complete guide to reproduce the
issue.

The reproducer demonstrates three points: (1) a key loading failure on
openssh + openssl-1.0.2p (2) that the failed key could be load
successfully with openssh + openssl-1.0.2o (3) that `ssh-keygen -p`
might generate bogus "invalid format" messages.

-- 
You are receiving this mail because:
You are watching the assignee of the bug.

https://bugzilla.mindrot.org/show_bug.cgi?id=2901

Damien Miller <djm at mindrot.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |djm at mindrot.org

--- Comment #4 from Damien Miller <djm at mindrot.org> ---
For old-format keys, OpenSSH is basically a thin wrapper around
OpenSSL's PEM key writing routines.

Can you try loading one of the broken keys using "openssl ec -noout
-text -in /path/key"?

Does openssl generate bad keys on its own? Try "openssl ecparam -genkey
-name secp521r1 -noout"

-- 
You are receiving this mail because:
You are watching someone on the CC list of the bug.
You are watching the assignee of the bug.

https://bugzilla.mindrot.org/show_bug.cgi?id=2901

--- Comment #5 from Alexander Sergeyev <sergeev917 at gmail.com> ---
(In reply to Damien Miller from comment #4)
>Can you try loading one of the broken keys using "openssl ec -noout
>-text -in /path/key"?
Openssl is able to load the offending key:

note: running version OpenSSH_7.8p1, OpenSSL 1.0.2p  14 Aug 2018
[attempt #224] found a broken key (passphrase = 12345678):

+ env DISPLAY= SSH_ASKPASS=/bin/false ssh-keygen -y -f testkey
Load key "testkey": invalid format
+ openssl ec -noout -text -in testkey -passin file:./passphrase
read EC key
Private-Key: (521 bit)
priv:
    01:be:d9:aa:d9:a3:e1:27:73:62:36:09:69:ca:60:
    4c:90:f6:ad:45:1f:a6:15:19:a5:f0:9f:3c:86:3b:
    3f:16:c7:5f:a7:54:a8:27:94:3f:27:1e:85:36:42:
    85:d6:f5:7c:78:b8:41:7b:39:9e:66:e1:84:f6:f9:
    da:9e:2d:7f:d5:50
pub:
    04:01:84:66:d3:cf:b7:9e:95:83:b6:10:ba:1a:c4:
    53:69:59:e4:c5:66:e3:34:a8:0c:ac:5e:03:22:6f:
    54:23:26:dc:7d:be:ce:11:70:79:1c:10:b3:a4:dc:
    09:87:75:34:8d:67:04:04:d4:45:2f:f5:43:fe:62:
    63:6b:c9:34:1f:11:e8:01:9d:8d:dd:44:f7:5c:85:
    7f:0c:78:07:4a:d1:2e:3b:bd:39:59:46:06:e5:17:
    d5:db:12:c8:c1:34:00:4a:17:de:dd:7c:f2:ea:79:
    c6:07:0c:6e:3f:30:df:70:ce:3a:51:c4:81:1e:e9:
    cc:a0:b7:8b:05:d7:df:00:4c:45:6c:a5:dc
ASN1 OID: secp521r1
NIST CURVE: P-521
> Does openssl generate bad keys on its own? Try "openssl ecparam
> -genkey -name secp521r1 -noout"
It's not about a bad key, but about key encryption using a passphrase.

-- 
You are receiving this mail because:
You are watching the assignee of the bug.
You are watching someone on the CC list of the bug.

https://bugzilla.mindrot.org/show_bug.cgi?id=2901

--- Comment #6 from Damien Miller <djm at mindrot.org> ---
I took a look at this. It appears that what is happening is that
OpenSSL is decrypting the key with the supplied incorrect passphrase
and finding enough initial valid plaintext upon decryption to continue
doing so.

Hacking sshkey.c to print the error stack yields:

140509893265048:error:0D0680A8:asn1 encoding
routines:ASN1_CHECK_TLEN:wrong tag:tasn_dec.c:1220:
140509893265048:error:0D07803A:asn1 encoding
routines:ASN1_ITEM_EX_D2I:nested asn1
error:tasn_dec.c:386:Type=EC_PRIVATEKEY
140509893265048:error:10092010:elliptic curve
routines:d2i_ECPrivateKey:EC lib:ec_asn1.c:1029:
140509893265048:error:100DE08E:elliptic curve
routines:OLD_EC_PRIV_DECODE:decode error:ec_ameth.c:543:
140509893265048:error:0D0680A8:asn1 encoding
routines:ASN1_CHECK_TLEN:wrong tag:tasn_dec.c:1220:
140509893265048:error:0D07803A:asn1 encoding
routines:ASN1_ITEM_EX_D2I:nested asn1
error:tasn_dec.c:386:Type=PKCS8_PRIV_KEY_INFO
140509893265048:error:0907B00D:PEM
routines:PEM_READ_BIO_PRIVATEKEY:ASN1 lib:pem_pkey.c:142:

Note that all the entries in the stack are parse/format errors and
there's literally nothing in there about invalid decryption.

AFAIK there's literally no way given the OpenSSL API (or maybe the PEM
format itself) to discern between keys with invalid format and valid
keys with an incorrect passphase.

The only think I think we could do is to treat all parsing errors as
incorrect passphrases. This is ugly too and makes it hard to tell a
user when they are trying to operate on a genuinely invalid key.

-- 
You are receiving this mail because:
You are watching someone on the CC list of the bug.
You are watching the assignee of the bug.

https://bugzilla.mindrot.org/show_bug.cgi?id=2901

--- Comment #7 from Damien Miller <djm at mindrot.org> ---
Created attachment 3187
  --> https://bugzilla.mindrot.org/attachment.cgi?id=3187&action=edit
treat all ASN1 parse errors as "incorrect passphrase" if passphrase
specified

-- 
You are receiving this mail because:
You are watching the assignee of the bug.
You are watching someone on the CC list of the bug.

https://bugzilla.mindrot.org/show_bug.cgi?id=2901

--- Comment #8 from Thomas Deutschmann <whissi at gentoo.org> ---
Do we already know for sure what's causing the creation of invalid keys
at all? The original reporter suspects a problem introduced
with
>=openssl-1.0.2p but at least I was unable to prove that.
-- 
You are receiving this mail because:
You are watching the assignee of the bug.
You are watching someone on the CC list of the bug.

https://bugzilla.mindrot.org/show_bug.cgi?id=2901

--- Comment #9 from Damien Miller <djm at mindrot.org> ---
I'm using the test script you attached. The keys it generates are
perfectly valid, they just read as "invalid format" instead of
"incorrect passphrase supplied to decrypt private key" if you try to
load them when specifying an incorrect passphrase.

-- 
You are receiving this mail because:
You are watching the assignee of the bug.
You are watching someone on the CC list of the bug.

https://bugzilla.mindrot.org/show_bug.cgi?id=2901

Damien Miller <djm at mindrot.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Blocks|                            |2893

--- Comment #10 from Damien Miller <djm at mindrot.org> ---
This has been committed and will be in the openssh-7.9 release. Thanks
for the report and script to reproduce it.

commit edbb6febccee084d212fdc0cb05b40cb1c646ab1 (HEAD -> master,
origin/master, origin/HEAD)
Author: djm at openbsd.org <djm at openbsd.org>
Date:   Tue Oct 9 05:42:23 2018 +0000

    upstream: Treat all PEM_read_bio_PrivateKey() errors when a
passphrase

    is specified as "incorrect passphrase" instead of trying to choose
between
    that and "invalid format".

    libcrypto can return ASN1 parsing errors rather than the expected
    decrypt error in certain infrequent cases when trying to
decrypt/parse
    PEM private keys when supplied with an invalid passphrase.

    Report and repro recipe from Thomas Deutschmann in bz#2901

    ok markus@

    OpenBSD-Commit-ID: b1d4cd92395f9743f81c0d23aab2524109580870


Referenced Bugs:

https://bugzilla.mindrot.org/show_bug.cgi?id=2893
[Bug 2893] Tracking bug for 7.9 release
-- 
You are receiving this mail because:
You are watching the assignee of the bug.
You are watching someone on the CC list of the bug.

https://bugzilla.mindrot.org/show_bug.cgi?id=2901

Damien Miller <djm at mindrot.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |FIXED

-- 
You are receiving this mail because:
You are watching someone on the CC list of the bug.
You are watching the assignee of the bug.

https://bugzilla.mindrot.org/show_bug.cgi?id=2901

--- Comment #11 from Alexander Sergeyev <sergeev917 at gmail.com> ---
(In reply to Damien Miller from comment #10)
> This has been committed and will be in the openssh-7.9 release.
> Thanks for the report and script to reproduce it.
Damien, thank you for the fix.

I've updated the reproducing scripts (see comment #3) to apply your
patch and it fixes the problem with misleading "invalid format"
messages.

But the other problem (about inability to load particular _valid_ keys)
remains -- see comments #1 and #3.

Could you please take a look at the reproducing scripts (#3)? Openssl
and openssh are built from sources in clean environment, and any found
unloadable key (with openssh linked against openssl-1.0.2p) is then
load by openssh that is linked against openssl-1.0.2o. The sample
script output could be found in README.md. I would be happy to answer
any questions or assist in investigating this further.

-- 
You are receiving this mail because:
You are watching the assignee of the bug.
You are watching someone on the CC list of the bug.

https://bugzilla.mindrot.org/show_bug.cgi?id=2901

--- Comment #12 from Damien Miller <djm at mindrot.org> ---
I don't see any unloadable keys when trying the
https://raw.githubusercontent.com/sergeev917/openssh-openssl-bug-repro/master/find_key_failure.sh
script using -current.

I'm not using the precise version of OpenSSL or the same Linux
distribution though.

-- 
You are receiving this mail because:
You are watching someone on the CC list of the bug.
You are watching the assignee of the bug.

https://bugzilla.mindrot.org/show_bug.cgi?id=2901

--- Comment #13 from Alexander Sergeyev <sergeev917 at gmail.com> ---
(In reply to Damien Miller from comment #12)
> I don't see any unloadable keys [...] find_key_failure.sh script using
-current.
I've updated the repo to pull openssh-portable sources from github.
Then I reran the pipeline for d1d301a -- with no changes relative to
7.8p1.
> I'm not using the precise version of OpenSSL or the same Linux
distribution though.
Okay. What version of OpenSSL did you use? In some distributions (ie
gentoo) the current stable version of OpenSSL is 1.0.2p -- the version
which fails for me (and in the docker scripts on alpine). Could you try
testing OpenSSH linked against this particular OpenSSL version?

-- 
You are receiving this mail because:
You are watching the assignee of the bug.
You are watching someone on the CC list of the bug.

https://bugzilla.mindrot.org/show_bug.cgi?id=2901

Damien Miller <djm at mindrot.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |CLOSED

--- Comment #14 from Damien Miller <djm at mindrot.org> ---
Close RESOLVED bugs with the release of openssh-8.0

-- 
You are receiving this mail because:
You are watching someone on the CC list of the bug.
You are watching the assignee of the bug.