diff --git a/kallithea/lib/ssh.py b/kallithea/lib/ssh.py
--- a/kallithea/lib/ssh.py
+++ b/kallithea/lib/ssh.py
@@ -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 @@ log = logging.getLogger(__name__)
 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 @@ def parse_pub_key(ssh_key):
     >>> 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 @@ def parse_pub_key(ssh_key):
         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 @@ def parse_pub_key(ssh_key):
     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