diff --git a/swh/core/logger.py b/swh/core/logger.py
--- a/swh/core/logger.py
+++ b/swh/core/logger.py
@@ -5,6 +5,7 @@
 
 import datetime
 import logging
+from typing import Any, Generator, List, Tuple
 
 from systemd.journal import JournalHandler as _JournalHandler, send
 
@@ -52,12 +53,21 @@
     return extra_data
 
 
-def flatten(data, separator='_'):
+def flatten(
+        data: Any,
+        separator: str = "_"
+) -> Generator[Tuple[str, Any], None, None]:
     """Flatten the data dictionary into a flat structure"""
-    def inner_flatten(data, prefix):
+
+    def inner_flatten(
+        data: Any, prefix: List[str]
+    ) -> Generator[Tuple[List[str], Any], None, None]:
         if isinstance(data, dict):
-            for key, value in data.items():
-                yield from inner_flatten(value, prefix + [key])
+            if all(isinstance(key, str) for key in data):
+                for key, value in data.items():
+                    yield from inner_flatten(value, prefix + [key])
+            else:
+                yield prefix, str(data)
         elif isinstance(data, (list, tuple)):
             for key, value in enumerate(data):
                 yield from inner_flatten(value, prefix + [str(key)])
diff --git a/swh/core/tests/test_logger.py b/swh/core/tests/test_logger.py
--- a/swh/core/tests/test_logger.py
+++ b/swh/core/tests/test_logger.py
@@ -69,6 +69,16 @@
     ]
 
 
+def test_flatten_dict_binary_keys():
+    d = {b"a": "a"}
+    str_d = str(d)
+    assert list(logger.flatten(d)) == [("", str_d)]
+    assert list(logger.flatten({"a": d})) == [("a", str_d)]
+    assert list(logger.flatten({"a": [d, d]})) == [
+        ("a_0", str_d), ("a_1", str_d)
+    ]
+
+
 def test_stringify():
     assert logger.stringify(None) == 'None'
     assert logger.stringify(123) == '123'