diff --git a/CMakeLists.txt b/CMakeLists.txt
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -448,6 +448,7 @@ if(WIN32)
         usp10
         psapi
         winhttp
+        bcrypt
     )
 endif()
 
diff --git a/src/core/random_func.cpp b/src/core/random_func.cpp
--- a/src/core/random_func.cpp
+++ b/src/core/random_func.cpp
@@ -10,6 +10,7 @@
 #include "../stdafx.h"
 #include "random_func.hpp"
 #include "bitmath_func.hpp"
+#include "../debug.h"
 
 #ifdef RANDOM_DEBUG
 #include "../network/network.h"
@@ -20,6 +21,15 @@
 #include "../timer/timer_game_calendar.h"
 #endif /* RANDOM_DEBUG */
 
+#if defined(_WIN32)
+#	include <windows.h>
+#	include <bcrypt.h>
+#elif defined(__EMSCRIPTEN__)
+#	include <emscripten.h>
+#elif !defined(__APPLE__) && !defined(__NetBSD__) && !defined(__FreeBSD__)
+#	include <sys/random.h>
+#endif
+
 #include "../safeguards.h"
 
 Randomizer _random, _interactive_random;
@@ -83,3 +93,53 @@ uint32_t DoRandomRange(uint32_t limit, i
 	return ((uint64_t)DoRandom(line, file) * (uint64_t)limit) >> 32;
 }
 #endif /* RANDOM_DEBUG */
+
+/**
+ * Fill the given buffer with random bytes.
+ *
+ * This function will attempt to use a cryptographically-strong random
+ * generator, but will fall back to a weaker random generator if none is
+ * available.
+ *
+ * In the end, the buffer will always be filled with some form of random
+ * bytes when this function returns.
+ *
+ * @param buf The buffer to fill with random bytes.
+ */
+void RandomBytesWithFallback(std::span<uint8_t> buf)
+{
+#if defined(_WIN32)
+	auto res = BCryptGenRandom(nullptr, static_cast<PUCHAR>(buf.data()), static_cast<ULONG>(buf.size()), BCRYPT_USE_SYSTEM_PREFERRED_RNG);
+	if (res >= 0) return;
+#elif defined(__APPLE__) || defined(__NetBSD__) || defined(__FreeBSD__)
+	arc4random_buf(buf.data(), buf.size());
+	return;
+#elif defined(__GLIBC__) && ((__GLIBC__ > 2) || ((__GLIBC__ == 2) && (__GLIBC_MINOR__ >= 25)))
+	auto res = getrandom(buf.data(), buf.size(), 0);
+	if (res > 0 && static_cast<size_t>(res) == buf.size()) return;
+#elif defined(__EMSCRIPTEN__)
+	auto res = EM_ASM_INT({
+		var buf = $0;
+		var bytes = $1;
+
+		var crypto = window.crypto;
+		if (crypto === undefined || crypto.getRandomValues === undefined) {
+			return -1;
+		}
+
+		crypto.getRandomValues(Module.HEAPU8.subarray(buf, buf + bytes));
+		return 1;
+	}, buf.data(), buf.size());
+	if (res > 0) return;
+#else
+#	warning "No cryptographically-strong random generator available; using a fallback instead"
+#endif
+
+	static bool warned_once = false;
+	Debug(misc, warned_once ? 1 : 0, "Cryptographically-strong random generator unavailable; using fallback");
+	warned_once = true;
+
+	for (uint i = 0; i < buf.size(); i++) {
+		buf[i] = static_cast<uint8_t>(InteractiveRandom());
+	}
+}
diff --git a/src/core/random_func.hpp b/src/core/random_func.hpp
--- a/src/core/random_func.hpp
+++ b/src/core/random_func.hpp
@@ -159,4 +159,6 @@ inline bool Chance16R(const uint a, cons
 }
 #endif /* RANDOM_DEBUG */
 
+void RandomBytesWithFallback(std::span<uint8_t> buf);
+
 #endif /* RANDOM_FUNC_HPP */
diff --git a/src/misc.cpp b/src/misc.cpp
--- a/src/misc.cpp
+++ b/src/misc.cpp
@@ -31,7 +31,7 @@
 #include "town_kdtree.h"
 #include "viewport_kdtree.h"
 #include "newgrf_profiling.h"
-#include "3rdparty/md5/md5.h"
+#include "3rdparty/monocypher/monocypher.h"
 
 #include "safeguards.h"
 
@@ -61,25 +61,24 @@ void InitializeOldNames();
 /**
  * Generate an unique ID.
  *
- * It isn't as much of an unique ID as we would like, but our random generator
- * can only produce 32bit random numbers.
- * That is why we combine InteractiveRandom with the current (steady) clock.
- * The first to add a bit of randomness, the second to ensure you can't get
- * the same unique ID when you run it twice from the same state at different
- * times.
- *
- * This makes it unlikely that two users generate the same ID for different
- * subjects. But as this is not an UUID, so it can't be ruled out either.
+ * It isn't as much of an unique ID but more a hashed digest of a random
+ * string and a time. It is very likely to be unique, but it does not follow
+ * any UUID standard.
  */
 std::string GenerateUid(std::string_view subject)
 {
+	std::array<uint8_t, 32> random_bytes;
+	RandomBytesWithFallback(random_bytes);
+
 	auto current_time = std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::steady_clock::now().time_since_epoch()).count();
-	std::string coding_string = fmt::format("{}{}{}", InteractiveRandom(), current_time, subject);
+	std::string coding_string = fmt::format("{}{}", current_time, subject);
 
-	Md5 checksum;
-	MD5Hash digest;
-	checksum.Append(coding_string.c_str(), coding_string.length());
-	checksum.Finish(digest);
+	std::array<uint8_t, 16> digest;
+	crypto_blake2b_ctx ctx;
+	crypto_blake2b_init(&ctx, digest.size());
+	crypto_blake2b_update(&ctx, random_bytes.data(), random_bytes.size());
+	crypto_blake2b_update(&ctx, reinterpret_cast<const uint8_t *>(coding_string.data()), coding_string.size());
+	crypto_blake2b_final(&ctx, digest.data());
 
 	return FormatArrayAsHex(digest);
 }