diff --git a/pagure/lib/__init__.py b/pagure/lib/__init__.py
index e3ceade..b542521 100644
--- a/pagure/lib/__init__.py
+++ b/pagure/lib/__init__.py
@@ -220,6 +220,7 @@ def search_user(session, username=None, email=None, token=None, pattern=None):
     return output
 
 
+_is_valid_ssh_key_force_md5 = None
 def is_valid_ssh_key(key):
     """ Validates the ssh key using ssh-keygen. """
     key = key.strip()
@@ -228,14 +229,43 @@ def is_valid_ssh_key(key):
     with tempfile.TemporaryFile() as f:
         f.write(key.encode('utf-8'))
         f.seek(0)
-        proc = subprocess.Popen(['/usr/bin/ssh-keygen', '-l', '-f',
-                                 '/dev/stdin'],
+        cmd = ['/usr/bin/ssh-keygen', '-l', '-f',
+               '/dev/stdin']
+        if _is_valid_ssh_key_force_md5:
+            cmd.extend(['-E', 'md5'])
+        proc = subprocess.Popen(cmd,
                                 stdin=f,
                                 stdout=subprocess.PIPE,
                                 stderr=subprocess.PIPE)
     stdout, stderr = proc.communicate()
     if proc.returncode != 0:
         return False
+
+    if _is_valid_ssh_key_force_md5 is None:
+        # We grab the "key ID" portion of the very first key to verify the
+        # algorithm that's default on this system.
+        # We always want to use the MD5 hash method, to be consistent and a
+        # common lower denominator, so if we detect another method being
+        # default, set a variable so we know we will always need to call with
+        # -E md5.
+        # (Unfortunately, the older openSSH versions that had the default to
+        #  MD5 also don't even support the -E argument...)
+        # Example line:
+        #  with hash: 1024 SHA256:ztcRX... root@test (RSA)
+        #  without  : 1024 f9:a2:... key (RSA)
+        global _is_valid_ssh_key_force_md5
+        keyparts = stdout.split('\n')[0].split(' ')[1].split(':')
+        if len(keyparts) == 2 or keyparts[0].upper() in ('MD5', 'SHA256'):
+            # This means that we get a keyid of HASH:<keyid> rather than just
+            # <keyid>, which indicates this is a system that supports multiple
+            # hash methods. Record this, and recall ourselves.
+            _is_valid_ssh_key_force_md5 = True
+            return is_valid_ssh_key(key)
+        else:
+            # This means this is a system that does not recognize the -E
+            # argument, thus we should never pass it.
+            _is_valid_ssh_key_force_md5 = False
+
     return stdout
 
 
diff --git a/tests/test_pagure_lib.py b/tests/test_pagure_lib.py
index a396c06..6bb5800 100644
--- a/tests/test_pagure_lib.py
+++ b/tests/test_pagure_lib.py
@@ -5239,6 +5239,25 @@ foo bar
         """ Test the is_valid_ssh_key function of pagure.lib. """
         self.assertIsNone(pagure.lib.is_valid_ssh_key(''))
 
+    def test_is_valid_ssh_key_invalid(self):
+        """ Test the is_valid_ssh_key function of pagure.lib. """
+        self.assertEqual(pagure.lib.is_valid_ssh_key('nonsense'), False)
+
+    def test_is_valid_ssh_key(self):
+        """ Test the is_valid_ssh_key function of pagure.lib. """
+        keyinfo = pagure.lib.is_valid_ssh_key('''ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAAAgQDtgzSO9d1IrKdmyBFUvtAJPLgGOhp0lSySkWRSe+/+3KXYjSnsLnCJQlO5M7JfaXhtTHEow86rh4W9+FoJdzo5iocAwH5xPZ5ttHLy7VHgTzNMUeMgKpjy6bBOdPoGPPG4mo7QCMCRJdWBRDv4OSEMLU5jQAvC272YK2V8L918VQ== root@test''')
+        keys = keyinfo.split('\n')
+        self.assertEqual(len(keys), 2)
+        self.assertEqual(keys[1], '')
+        key = keys[0].split(' ')
+        self.assertEqual(key[0], '1024')
+        # We should always get the MD5 version
+        if key[1].startswith('MD5'):
+            self.assertEqual(key[1], 'MD5:f9:a2:14:97:a5:42:78:f7:16:f8:fb:73:ba:f0:f4:fe')
+        else:
+            self.assertEqual(key[1], 'f9:a2:14:97:a5:42:78:f7:16:f8:fb:73:ba:f0:f4:fe')
+        self.assertEqual(key[3], '(RSA)')
+
     def test_create_deploykeys_ssh_keys_on_disk_empty(self):
         """ Test the create_deploykeys_ssh_keys_on_disk function of
         pagure.lib. """