Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Loading an Ed25519Key with a comment of certain lengths results in "Invalid key". #1306

Closed
parke opened this issue Sep 30, 2018 · 10 comments

Comments

@parke
Copy link

commented Sep 30, 2018

Ed25519Keys with comments of certain lengths cannot be loaded as of paramiko 2.4.2. Attempts to load these keys result in an "Invalid key" exception.

If the Ed25519Key is encrypted with a passphrase, and if the length of the comment mod 16 equals 13, loading the key causes an "Invalid key" exception.

If the Ed25519Key is not encrypted with a passphrase, and if the length of the comment mod 8 equals 5, loading the key causes an "Invalid key" exception.

Reproduce code:

#  generate comments of lengths 0 through 63                                

comments  =  []
for  n  in  range ( 0, 64 ):  comments .append ( '_' * n )

def  path  ( n ):  return  '/tmp/key_ed25519_%s' % n

#  generate the first key with a comment of length 0                        

passphrase  =  ''    #  an empty passphrase is much faster                  

os .system ( 'rm -f %s' % path(0) )
os .system ( 'ssh-keygen -t ed25519 -N "%s" -C "%s" -f %s > /dev/null' %
             ( passphrase, comments[0], path(0) ) )

#  generate the other keys by copying the first key and                     
#  then changing the comment                                                

for  n  in  range ( 1, len ( comments ) ):
  os .system ( 'cp  %s  %s' % ( path(0), path(n) ) )
  os .system ( 'ssh-keygen -c -P "%s" -C "%s" -f %s > /dev/null' %
               ( passphrase, comments[n], path(n) ) )

#  see which keys can be loaded                                             

for  n  in  range ( 0, len ( comments ) ):
  s  =  comments[n]
  try:
    pkey  =  paramiko .ed25519key .Ed25519Key .from_private_key_file (
      filename=path(n), password=passphrase )
    print ( '    %11s    %2d  %s' % ( '+', len(s), s ) )
  except  paramiko .ssh_exception .SSHException  as  se:
    print ( '    %11s    %2d  %s' % ( str ( se ), len(s), s ) )

Note: The above code will take significantly longer to run if a non-empty passphrase is specified. Presumably the delay is due to the passphrase being repeatedly hashed in order to reduce the effectiveness of brute force passphrase attacks.

Output of the above (when run with an empty password):

          +     0  
          +     1  _
          +     2  __
          +     3  ___
          +     4  ____
Invalid key     5  _____
          +     6  ______
          +     7  _______
          +     8  ________
          +     9  _________
          +    10  __________
          +    11  ___________
          +    12  ____________
Invalid key    13  _____________
          +    14  ______________
          +    15  _______________
          +    16  ________________
          +    17  _________________
          +    18  __________________
          +    19  ___________________
          +    20  ____________________
Invalid key    21  _____________________
          +    22  ______________________
          +    23  _______________________
          +    24  ________________________
          +    25  _________________________
          +    26  __________________________
          +    27  ___________________________
          +    28  ____________________________
Invalid key    29  _____________________________
          +    30  ______________________________
          +    31  _______________________________
          +    32  ________________________________
          +    33  _________________________________
          +    34  __________________________________
          +    35  ___________________________________
          +    36  ____________________________________
Invalid key    37  _____________________________________
          +    38  ______________________________________
          +    39  _______________________________________
          +    40  ________________________________________
          +    41  _________________________________________
          +    42  __________________________________________
          +    43  ___________________________________________
          +    44  ____________________________________________
Invalid key    45  _____________________________________________
          +    46  ______________________________________________
          +    47  _______________________________________________
          +    48  ________________________________________________
          +    49  _________________________________________________
          +    50  __________________________________________________
          +    51  ___________________________________________________
          +    52  ____________________________________________________
Invalid key    53  _____________________________________________________
          +    54  ______________________________________________________
          +    55  _______________________________________________________
          +    56  ________________________________________________________
          +    57  _________________________________________________________
          +    58  __________________________________________________________
          +    59  ___________________________________________________________
          +    60  ____________________________________________________________
Invalid key    61  _____________________________________________________________
          +    62  ______________________________________________________________
@lae

This comment has been minimized.

Copy link

commented Dec 12, 2018

I was also able to reproduce this issue while attempting to use napalm (which depends on paramiko) with an Ed25519 key and a 13 character comment.

@bitprophet

This comment has been minimized.

Copy link
Member

commented Jan 3, 2019

I feel like I've seen other reports of this same issue, but can't easily find 'em, so this will be it for now. Thanks for the report.

I can also say I've gotten a separate OOB report of the same issue:

Due to his username and the host name, his key comment was 21 characters, which reliably breaks

If I don't get to this by EOM, I'll actually be working with that reporter at a new job & will be able to confirm fix that way; though this looks like it should be trivially reproducible.

@parke

This comment has been minimized.

Copy link
Author

commented Jan 3, 2019

If I don't get to this by EOM, I'll actually be working with that reporter at a new job & will be able to confirm fix that way; though this looks like it should be trivially reproducible.

(EOM = end of month?)

The bug is trivially reproducible, is it not? I provided code that reliably reproduces the bug.

I suspect the fix is also trivial, but I did not try to understand the code enough to see exactly where the bug is. I suspect it is an off-by-one division error, possibly on some padding or something similar.

P.S. - Also, I have since learned that you may be able to edit the comment of an ED25519 key using only a text editor. (Whereas I believe the comment of an RSA key cannot be successfully edited in a text editor.) If you can edit the comment in a text editor, then reproducing the bug should be even simpler than my above example.

@metabsd

This comment has been minimized.

Copy link

commented Feb 13, 2019

If I have problem to load my Ed25519Key this is normal!!! I generate the key from Ubuntu 16.04 with this command ssh-keygen -o -a 100 -t ed25519

Python 3.6.5 (default, Apr 24 2018, 13:40:33)
[GCC 5.4.0 20160609] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import paramiko
>>> import socket
>>> client = paramiko.SSHClient()
>>> client.set_missing_host_key_policy(paramiko.AutoAddPolicy())
>>> pkey = paramiko.Ed25519Key.from_private_key_file("/home/myhome/.ssh/id_ed25519_users")
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/local/lib/python3.6/site-packages/paramiko/pkey.py", line 206, in from_private_key_file
    key = cls(filename=filename, password=password)
  File "/usr/local/lib/python3.6/site-packages/paramiko/ed25519key.py", line 81, in __init__
    signing_key = self._parse_signing_key_data(data, password)
  File "/usr/local/lib/python3.6/site-packages/paramiko/ed25519key.py", line 156, in _parse_signing_key_data
    message = Message(unpad(private_data))
  File "/usr/local/lib/python3.6/site-packages/paramiko/ed25519key.py", line 41, in unpad
    raise SSHException("Invalid key")
paramiko.ssh_exception.SSHException: Invalid key
@metabsd

This comment has been minimized.

Copy link

commented Feb 13, 2019

If I specify a passphrase it's working.

@lphuberdeau

This comment has been minimized.

Copy link

commented Feb 28, 2019

Removing unpad() entirely from the code seems to resolve the issue for me as well as with the test script provided by @parke - and all unit tests still pass.

The other key implementations appear to have no similar mechanisms. What is unpad intended to do?

diff --git a/paramiko/ed25519key.py b/paramiko/ed25519key.py
index 68ada224..c8487bf2 100644
--- a/paramiko/ed25519key.py
+++ b/paramiko/ed25519key.py
@@ -32,19 +32,6 @@ from paramiko.ssh_exception import SSHException, PasswordRequiredException
 OPENSSH_AUTH_MAGIC = b"openssh-key-v1\x00"
 
 
-def unpad(data):
-    # At the moment, this is only used for unpadding private keys on disk. This
-    # really ought to be made constant time (possibly by upstreaming this logic
-    # into pyca/cryptography).
-    padding_length = six.indexbytes(data, -1)
-    if padding_length > 16:
-        raise SSHException("Invalid key")
-    for i in range(1, padding_length + 1):
-        if six.indexbytes(data, -i) != (padding_length - i + 1):
-            raise SSHException("Invalid key")
-    return data[:-padding_length]
-
-
 class Ed25519Key(PKey):
     """
     Representation of an `Ed25519 <https://ed25519.cr.yp.to/>`_ key.
@@ -153,7 +140,7 @@ class Ed25519Key(PKey):
                 decryptor.update(private_ciphertext) + decryptor.finalize()
             )
 
-        message = Message(unpad(private_data))
+        message = Message(private_data)
         if message.get_int() != message.get_int():
             raise SSHException("Invalid key")
 

@ploxiln

This comment has been minimized.

Copy link
Contributor

commented Feb 28, 2019

If the key data is not a multiple of 16 8, then between 1 to 15 7 bytes (inclusive) is added such the length is a multiple of 16 8. These extra bytes are called padding. In this scheme, the value of these bytes is incrementing - so the first padding byte is value 1, second padding byte is value 2, etc. (Some schemes pad with just 0 bytes, but for cryptographic purposes that can combine with other stuff to be a weakness.)

So, unpad() assumes that the last byte is padding, and also indicates the amount of padding, and it checks that the padding meets the rule. But what if the key data has no padding added, because it was already a multiple of 8? In this case, unpad()'s assumption is wrong, the last byte is not padding, and does not indicate the amount of padding. Instead of raise SSHException("Invalid key") it should just return data - because this padding check is how it knows whether the last byte was padding or not.

@ploxiln

This comment has been minimized.

Copy link
Contributor

commented Feb 28, 2019

https://coolaj86.com/articles/the-openssh-private-key-format/

n bytes (between 0 and 7) of padding

  • bytes > 0x00 and < 0x08 must be trimmed (from the right)
  • the padding must be a (right-trimmed) substring of 0x01020304050607
  • (that includes the empty substring)
  • if the last byte isn't padding, it's part of the comment (0x21 to 0x7e)

ploxiln added a commit to ploxiln/paramiko-ng that referenced this issue Mar 2, 2019

ploxiln added a commit to ploxiln/paramiko-ng that referenced this issue Mar 2, 2019

fix ed25519 ssh key unpad() when padding not present (not needed)
fixes paramiko#1306

support up to 15 bytes padding ... should only be up to 7,
but test key has 8 bytes of padding, not sure if realistic
@ploxiln

This comment has been minimized.

Copy link
Contributor

commented Mar 2, 2019

please check that #1400 fixes this for you

@lphuberdeau

This comment has been minimized.

Copy link

commented Mar 4, 2019

I verified locally with #1400 and it works as expected. I also cherry-picked into 2.4 and it works there as well.

Thank you for looking into it. Hopefully the fix makes it into a release soon.

ploxiln added a commit to ploxiln/paramiko-ng that referenced this issue Apr 30, 2019

fix ed25519 ssh key unpad() when padding not present (not needed)
fixes paramiko#1306

support up to 15 bytes padding ... should only be up to 7,
but test key has 8 bytes of padding, not sure if realistic

ploxiln added a commit to ploxiln/paramiko-ng that referenced this issue Apr 30, 2019

fix ed25519 ssh key unpad() when padding not present (not needed)
fixes paramiko#1306

support up to 15 bytes padding ... should only be up to 7,
but test key has 8 bytes of padding, not sure if realistic

ploxiln added a commit to ploxiln/paramiko-ng that referenced this issue Apr 30, 2019

fix ed25519 ssh key unpad() when padding not present (not needed)
fixes paramiko#1306

support up to 15 bytes padding ... should only be up to 7,
but test key has 8 bytes of padding, not sure if realistic

ploxiln added a commit to ploxiln/paramiko-ng that referenced this issue May 23, 2019

@bitprophet bitprophet closed this Jun 21, 2019

bitprophet added a commit that referenced this issue Jun 21, 2019

bitprophet added a commit that referenced this issue Jun 21, 2019

ploxiln added a commit to ploxiln/paramiko-ng that referenced this issue Jun 22, 2019

ploxiln added a commit to ploxiln/paramiko-ng that referenced this issue Jun 22, 2019

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
6 participants
You can’t perform that action at this time.