# HG changeset patch
# User Mads Kiilerich <mads@kiilerich.com>
# Date 1601759868 -7200
# Node ID 12824a48192d1186292d222c0985029f5171b40b
# Parent  c3ae916ef55f6e386757133d1149e0e487efccca
ssh: verify SSH keys haven't been truncated

Ed Wong reported problems with a SSH key that accidentally was copy-pasted with
extra newlines. This truncation wasn't detected, so the truncated key was added
to authorized_keys where it obviously didn't work for sshd.

The base64 decoding would sometimes catch truncated keys - but not always. We
seem to have to look inside the key, parse it according to the RFCs, and verify
they contain the right amount of data for the key type.

It is an additional burden to have to parse SSH key internals just to validate
them. We could consider using some external method for validation. But the
explicit validation introduced here might be more spot-on for our needs.

diff -r c3ae916ef55f -r 12824a48192d kallithea/lib/ssh.py
--- a/kallithea/lib/ssh.py	Mon Sep 28 14:10:41 2020 +0200
+++ b/kallithea/lib/ssh.py	Sat Oct 03 23:17:48 2020 +0200
@@ -24,10 +24,11 @@
 import base64
 import logging
 import re
+import struct
 
 from tg.i18n import ugettext as _
 
-from kallithea.lib.utils2 import ascii_bytes, ascii_str
+from kallithea.lib.utils2 import ascii_str
 
 
 log = logging.getLogger(__name__)
@@ -36,6 +37,14 @@
 class SshKeyParseError(Exception):
     """Exception raised by parse_pub_key"""
 
+algorithm_types = {  # mapping name to number of data strings in key
+    # https://tools.ietf.org/html/rfc4253#section-6.6
+    'ssh-rsa': 2,  # e, n
+    'ssh-dss': 4,  # p, q, g, y
+    # https://tools.ietf.org/html/rfc8709
+    'ssh-ed25519': 1,
+    'ssh-ed448': 1,
+}
 
 def parse_pub_key(ssh_key):
     r"""Parse SSH public key string, raise SshKeyParseError or return decoded keytype, data and comment
@@ -60,15 +69,15 @@
     >>> parse_pub_key('''ssh-rsa  AAAAB2NzaC1yc2EAAAALVGhpcyBpcyBmYWtlIQ==''')
     Traceback (most recent call last):
     ...
-    kallithea.lib.ssh.SshKeyParseError: Invalid SSH key - it is a ssh-rsa key but the base64 part contains 'csh-rsa'
+    kallithea.lib.ssh.SshKeyParseError: Invalid SSH key - base64 part 'AAAAB2NzaC1yc2EAAAALVGhpcyBpcyBmYWtlIQ==' seems truncated (it contains a partial string length)
     >>> parse_pub_key('''ssh-rsa AAAAB2NzaC1yc2EAAAANVGhpcyBpcyE=''')
     Traceback (most recent call last):
     ...
-    kallithea.lib.ssh.SshKeyParseError: Invalid SSH key - it is a ssh-rsa key but the base64 part contains 'csh-rsa'
+    kallithea.lib.ssh.SshKeyParseError: Invalid SSH key - base64 part 'AAAAB2NzaC1yc2EAAAANVGhpcyBpcyE=' seems truncated (it is too short for declared string length 13)
     >>> parse_pub_key('''ssh-rsa AAAAB2NzaC1yc2EAAAANVGhpcyBpcyBmYWtlIQ==''')
     Traceback (most recent call last):
     ...
-    kallithea.lib.ssh.SshKeyParseError: Invalid SSH key - it is a ssh-rsa key but the base64 part contains 'csh-rsa'
+    kallithea.lib.ssh.SshKeyParseError: Invalid SSH key - base64 part 'AAAAB2NzaC1yc2EAAAANVGhpcyBpcyBmYWtlIQ==' seems truncated (it contains too few strings for a ssh-rsa key)
     >>> parse_pub_key('''ssh-rsa AAAAB2NzaC1yc2EAAAANVGhpcyBpcyBmYWtlIQAAAANieWU=''')
     Traceback (most recent call last):
     ...
@@ -91,7 +100,8 @@
         raise SshKeyParseError(_("Invalid SSH key - it must have both a key type and a base64 part, like 'ssh-rsa ASRNeaZu4FA...xlJp='"))
 
     keytype, keyvalue, comment = (parts + [''])[:3]
-    if keytype not in ('ssh-rsa', 'ssh-dss', 'ssh-ed448', 'ssh-ed25519'):
+    keytype_data_size = algorithm_types.get(keytype)
+    if keytype_data_size is None:
         raise SshKeyParseError(_("Invalid SSH key - it must start with key type 'ssh-rsa', 'ssh-dss', 'ssh-ed448', or 'ssh-ed25519'"))
 
     if re.search(r'[^a-zA-Z0-9+/=]', keyvalue):  # make sure b64decode doesn't stop at the first invalid character and skip the rest
@@ -102,8 +112,25 @@
     except base64.binascii.Error:  # Must be caused by truncation - either "Invalid padding" or "Invalid base64-encoded string: number of data characters (x) cannot be 1 more than a multiple of 4"
         raise SshKeyParseError(_("Invalid SSH key - base64 part %r seems truncated (it can't be decoded)") % keyvalue)
 
-    if not key_bytes.startswith(b'\x00\x00\x00%c%s\x00' % (len(keytype), ascii_bytes(keytype))):
-        raise SshKeyParseError(_("Invalid SSH key - it is a %s key but the base64 part contains %r") % (keytype, ascii_str(key_bytes[4:].split(b'\0', 1)[0])))
+    # Check key internals to make sure the key wasn't truncated in a way that base64 can decode:
+    # Parse and verify key according to https://tools.ietf.org/html/rfc4253#section-6.6
+    strings = []
+    offset = 0
+    while offset < len(key_bytes):
+        try:
+            string_length, = struct.unpack_from('!I', key_bytes, offset)
+        except struct.error:  # unpack_from requires a buffer of at least 283 bytes for unpacking 4 bytes at offset 279 (actual buffer size is 280)
+            raise SshKeyParseError(_("Invalid SSH key - base64 part %r seems truncated (it contains a partial string length)") % keyvalue)
+        offset += 4
+        string = key_bytes[offset:offset + string_length]
+        if len(string) != string_length:
+            raise SshKeyParseError(_("Invalid SSH key - base64 part %r seems truncated (it is too short for declared string length %s)") % (keyvalue, string_length))
+        strings.append(string)
+        offset += string_length
+    if len(strings) != keytype_data_size + 1:
+        raise SshKeyParseError(_("Invalid SSH key - base64 part %r seems truncated (it contains too few strings for a %s key)") % (keyvalue, keytype))
+    if ascii_str(strings[0]) != keytype:
+        raise SshKeyParseError(_("Invalid SSH key - it is a %s key but the base64 part contains %r") % (keytype, ascii_str(strings[0])))
 
     return keytype, key_bytes, comment