diff --git a/tools/releasetools/common.py b/tools/releasetools/common.py
index 1937f29..1533030 100644
--- a/tools/releasetools/common.py
+++ b/tools/releasetools/common.py
@@ -2105,7 +2105,9 @@
   need_passwords = []
   key_passwords = {}
   devnull = open("/dev/null", "w+b")
-  for k in sorted(keylist):
+
+  # sorted() can't compare strings to None, so convert Nones to strings
+  for k in sorted(keylist, key=lambda x: x if x is not None else ""):
     # We don't need a password for things that aren't really keys.
     if k in SPECIAL_CERT_STRINGS or k is None:
       no_passwords.append(k)