diff --git a/libavformat/matroskaenc.c b/libavformat/matroskaenc.c
index 1833d2a122..89bf68114c 100644
--- a/libavformat/matroskaenc.c
+++ b/libavformat/matroskaenc.c
@@ -205,6 +205,16 @@ static int ebml_num_size(uint64_t num)
     return bytes;
 }
 
+/**
+ * Write a (random) UID with fixed size to make the output more deterministic
+ */
+static void put_ebml_uid(AVIOContext *pb, uint32_t elementid, uint64_t uid)
+{
+    put_ebml_id(pb, elementid);
+    avio_w8(pb, 0x88);
+    avio_wb64(pb, uid);
+}
+
 /**
  * Write a number in EBML variable length format.
  *
@@ -1186,7 +1196,7 @@ static int mkv_write_track(AVFormatContext *s, MatroskaMuxContext *mkv,
     track = start_ebml_master(pb, MATROSKA_ID_TRACKENTRY, 0);
     put_ebml_uint (pb, MATROSKA_ID_TRACKNUMBER,
                    mkv->is_dash ? mkv->dash_track_number : i + 1);
-    put_ebml_uint (pb, MATROSKA_ID_TRACKUID, mkv->tracks[i].uid);
+    put_ebml_uid  (pb, MATROSKA_ID_TRACKUID, mkv->tracks[i].uid);
     put_ebml_uint (pb, MATROSKA_ID_TRACKFLAGLACING , 0);    // no lacing (yet)
 
     if ((tag = av_dict_get(st->metadata, "title", NULL, 0)))
@@ -1562,7 +1572,7 @@ static int mkv_write_tag_targets(AVFormatContext *s, uint32_t elementid,
     *tag    = start_ebml_master(pb, MATROSKA_ID_TAG,        0);
     targets = start_ebml_master(pb, MATROSKA_ID_TAGTARGETS, 0);
     if (elementid)
-        put_ebml_uint(pb, elementid, uid);
+        put_ebml_uid(pb, elementid, uid);
     end_ebml_master(pb, targets);
     return 0;
 }
@@ -1766,7 +1776,7 @@ static int mkv_write_attachments(AVFormatContext *s)
 
         put_ebml_string(dyn_cp, MATROSKA_ID_FILEMIMETYPE, mimetype);
         put_ebml_binary(dyn_cp, MATROSKA_ID_FILEDATA, st->codecpar->extradata, st->codecpar->extradata_size);
-        put_ebml_uint(dyn_cp, MATROSKA_ID_FILEUID, track->uid);
+        put_ebml_uid(dyn_cp, MATROSKA_ID_FILEUID, track->uid);
         end_ebml_master(dyn_cp, attached_file);
     }
     end_ebml_master_crc32(pb, &dyn_cp, mkv);
diff --git a/tests/fate/matroska.mak b/tests/fate/matroska.mak
index 98a49a4d74..7c48de1a61 100644
--- a/tests/fate/matroska.mak
+++ b/tests/fate/matroska.mak
@@ -4,7 +4,7 @@
 FATE_MATROSKA-$(call DEMMUX, MATROSKA, MATROSKA) += fate-matroska-remux
 fate-matroska-remux: CMD = md5pipe -i $(TARGET_SAMPLES)/vp9-test-vectors/vp90-2-2pass-akiyo.webm -color_trc 4 -c:v copy -fflags +bitexact -strict -2 -f matroska
 fate-matroska-remux: CMP = oneline
-fate-matroska-remux: REF = e5457e5fa606d564a54914bd12f426c8
+fate-matroska-remux: REF = 5ae8144848acd392eaca8d43ff4aa5e6
 
 FATE_MATROSKA_FFPROBE-$(call ALLYES, MATROSKA_DEMUXER) += fate-matroska-spherical-mono
 fate-matroska-spherical-mono: CMD = run ffprobe$(PROGSSUF)$(EXESUF) -show_entries stream_side_data_list -select_streams v -v 0 $(TARGET_SAMPLES)/mkv/spherical.mkv
diff --git a/tests/fate/wavpack.mak b/tests/fate/wavpack.mak
index 286e17f2ae..b7bb563802 100644
--- a/tests/fate/wavpack.mak
+++ b/tests/fate/wavpack.mak
@@ -91,12 +91,12 @@ fate-wavpack-matroskamode: CMD = md5 -i $(TARGET_SAMPLES)/wavpack/special/matros
 FATE_WAVPACK-$(call DEMMUX, WV, MATROSKA) += fate-wavpack-matroska_mux-mono
 fate-wavpack-matroska_mux-mono: CMD = md5pipe -i $(TARGET_SAMPLES)/wavpack/num_channels/mono_16bit_int.wv -c copy -fflags +bitexact -f matroska
 fate-wavpack-matroska_mux-mono: CMP = oneline
-fate-wavpack-matroska_mux-mono: REF = c5a2b46d8b31c9c2e7bfb436f9d56f02
+fate-wavpack-matroska_mux-mono: REF = ed8bf42aad172ec8e0ecc906e2fa27e6
 
 FATE_WAVPACK-$(call DEMMUX, WV, MATROSKA) += fate-wavpack-matroska_mux-61
 fate-wavpack-matroska_mux-61: CMD = md5pipe -i $(TARGET_SAMPLES)/wavpack/num_channels/eva_2.22_6.1_16bit-partial.wv -c copy -fflags +bitexact -f matroska
 fate-wavpack-matroska_mux-61: CMP = oneline
-fate-wavpack-matroska_mux-61: REF = 22fc2a591be22657d19cab89ad6eef55
+fate-wavpack-matroska_mux-61: REF = 425d2f82a22b86e4a8a71c2319284780
 
 FATE_SAMPLES_AVCONV += $(FATE_WAVPACK-yes)
 fate-wavpack: $(FATE_WAVPACK-yes)
diff --git a/tests/ref/fate/aac-autobsf-adtstoasc b/tests/ref/fate/aac-autobsf-adtstoasc
index 9bf9dfe78f..edae3e6423 100644
--- a/tests/ref/fate/aac-autobsf-adtstoasc
+++ b/tests/ref/fate/aac-autobsf-adtstoasc
@@ -1,5 +1,5 @@
-b09fc2f554712adbf84fe7899eb679d4 *tests/data/fate/aac-autobsf-adtstoasc.matroska
-6695 tests/data/fate/aac-autobsf-adtstoasc.matroska
+ad50ade359efa0321c9111a08edada28 *tests/data/fate/aac-autobsf-adtstoasc.matroska
+6709 tests/data/fate/aac-autobsf-adtstoasc.matroska
 #extradata 0:        2, 0x0030001c
 #tb 0: 1/1000
 #media_type 0: audio
diff --git a/tests/ref/fate/binsub-mksenc b/tests/ref/fate/binsub-mksenc
index 4b13ef217a..9c2c3ea9bc 100644
--- a/tests/ref/fate/binsub-mksenc
+++ b/tests/ref/fate/binsub-mksenc
@@ -1 +1 @@
-a5811caa0caba3a3f9a449b91569745c
+0248927de98ee861f626bd26ed61f9a0
diff --git a/tests/ref/fate/rgb24-mkv b/tests/ref/fate/rgb24-mkv
index b9db53f592..57e812e48b 100644
--- a/tests/ref/fate/rgb24-mkv
+++ b/tests/ref/fate/rgb24-mkv
@@ -1,5 +1,5 @@
-ffe2c21083d56764aaae7945fd146326 *tests/data/fate/rgb24-mkv.matroska
-58305 tests/data/fate/rgb24-mkv.matroska
+00bd029ef542bf0eae4bd7c3480bff2a *tests/data/fate/rgb24-mkv.matroska
+58326 tests/data/fate/rgb24-mkv.matroska
 #tb 0: 1/10
 #media_type 0: video
 #codec_id 0: rawvideo
diff --git a/tests/ref/lavf/mka b/tests/ref/lavf/mka
index a244893cf2..f5f8db1598 100644
--- a/tests/ref/lavf/mka
+++ b/tests/ref/lavf/mka
@@ -1,3 +1,3 @@
-a91bfdb08ff5a1e62b039748d16b07f7 *tests/data/lavf/lavf.mka
-43652 tests/data/lavf/lavf.mka
+4184b7103e80e40e477b9c04b7360fc8 *tests/data/lavf/lavf.mka
+43673 tests/data/lavf/lavf.mka
 tests/data/lavf/lavf.mka CRC=0x3a1da17e
diff --git a/tests/ref/lavf/mkv b/tests/ref/lavf/mkv
index 05999b79fb..d9bdf98176 100644
--- a/tests/ref/lavf/mkv
+++ b/tests/ref/lavf/mkv
@@ -1,3 +1,3 @@
-3cddd26ed41f34925d3f34acabab174e *tests/data/lavf/lavf.mkv
-320555 tests/data/lavf/lavf.mkv
+03d729410856242aaedcbd8c6f71d97e *tests/data/lavf/lavf.mkv
+320597 tests/data/lavf/lavf.mkv
 tests/data/lavf/lavf.mkv CRC=0xec6c3c68
diff --git a/tests/ref/lavf/mkv_attachment b/tests/ref/lavf/mkv_attachment
index 790c0f693b..809975da50 100644
--- a/tests/ref/lavf/mkv_attachment
+++ b/tests/ref/lavf/mkv_attachment
@@ -1,3 +1,3 @@
-f54cf193e1925eff8a44554116a5e149 *tests/data/lavf/lavf.mkv_attachment
-472703 tests/data/lavf/lavf.mkv_attachment
+bcc4ace0ebdfd0eade8cb490d99185e5 *tests/data/lavf/lavf.mkv_attachment
+472752 tests/data/lavf/lavf.mkv_attachment
 tests/data/lavf/lavf.mkv_attachment CRC=0xec6c3c68
diff --git a/tests/ref/seek/lavf-mkv b/tests/ref/seek/lavf-mkv
index 6ed1f3a763..8434aae988 100644
--- a/tests/ref/seek/lavf-mkv
+++ b/tests/ref/seek/lavf-mkv
@@ -1,48 +1,48 @@
-ret: 0         st: 1 flags:1 dts: 0.000000 pts: 0.000000 pos:    803 size:   208
+ret: 0         st: 1 flags:1 dts: 0.000000 pts: 0.000000 pos:    845 size:   208
 ret: 0         st:-1 flags:0  ts:-1.000000
-ret: 0         st: 0 flags:1 dts: 0.011000 pts: 0.011000 pos:   1019 size: 27837
+ret: 0         st: 0 flags:1 dts: 0.011000 pts: 0.011000 pos:   1061 size: 27837
 ret: 0         st:-1 flags:1  ts: 1.894167
-ret: 0         st: 0 flags:1 dts: 0.971000 pts: 0.971000 pos: 292435 size: 27834
+ret: 0         st: 0 flags:1 dts: 0.971000 pts: 0.971000 pos: 292477 size: 27834
 ret: 0         st: 0 flags:0  ts: 0.788000
-ret: 0         st: 0 flags:1 dts: 0.971000 pts: 0.971000 pos: 292435 size: 27834
+ret: 0         st: 0 flags:1 dts: 0.971000 pts: 0.971000 pos: 292477 size: 27834
 ret: 0         st: 0 flags:1  ts:-0.317000
-ret: 0         st: 0 flags:1 dts: 0.011000 pts: 0.011000 pos:   1019 size: 27837
+ret: 0         st: 0 flags:1 dts: 0.011000 pts: 0.011000 pos:   1061 size: 27837
 ret:-1         st: 1 flags:0  ts: 2.577000
 ret: 0         st: 1 flags:1  ts: 1.471000
-ret: 0         st: 1 flags:1 dts: 0.993000 pts: 0.993000 pos: 320276 size:   209
+ret: 0         st: 1 flags:1 dts: 0.993000 pts: 0.993000 pos: 320318 size:   209
 ret: 0         st:-1 flags:0  ts: 0.365002
-ret: 0         st: 0 flags:1 dts: 0.491000 pts: 0.491000 pos: 146987 size: 27925
+ret: 0         st: 0 flags:1 dts: 0.491000 pts: 0.491000 pos: 147029 size: 27925
 ret: 0         st:-1 flags:1  ts:-0.740831
-ret: 0         st: 0 flags:1 dts: 0.011000 pts: 0.011000 pos:   1019 size: 27837
+ret: 0         st: 0 flags:1 dts: 0.011000 pts: 0.011000 pos:   1061 size: 27837
 ret:-1         st: 0 flags:0  ts: 2.153000
 ret: 0         st: 0 flags:1  ts: 1.048000
-ret: 0         st: 0 flags:1 dts: 0.971000 pts: 0.971000 pos: 292435 size: 27834
+ret: 0         st: 0 flags:1 dts: 0.971000 pts: 0.971000 pos: 292477 size: 27834
 ret: 0         st: 1 flags:0  ts:-0.058000
-ret: 0         st: 1 flags:1 dts: 0.000000 pts: 0.000000 pos:    803 size:   208
+ret: 0         st: 1 flags:1 dts: 0.000000 pts: 0.000000 pos:    845 size:   208
 ret: 0         st: 1 flags:1  ts: 2.836000
-ret: 0         st: 1 flags:1 dts: 0.993000 pts: 0.993000 pos: 320276 size:   209
+ret: 0         st: 1 flags:1 dts: 0.993000 pts: 0.993000 pos: 320318 size:   209
 ret:-1         st:-1 flags:0  ts: 1.730004
 ret: 0         st:-1 flags:1  ts: 0.624171
-ret: 0         st: 0 flags:1 dts: 0.491000 pts: 0.491000 pos: 146987 size: 27925
+ret: 0         st: 0 flags:1 dts: 0.491000 pts: 0.491000 pos: 147029 size: 27925
 ret: 0         st: 0 flags:0  ts:-0.482000
-ret: 0         st: 0 flags:1 dts: 0.011000 pts: 0.011000 pos:   1019 size: 27837
+ret: 0         st: 0 flags:1 dts: 0.011000 pts: 0.011000 pos:   1061 size: 27837
 ret: 0         st: 0 flags:1  ts: 2.413000
-ret: 0         st: 0 flags:1 dts: 0.971000 pts: 0.971000 pos: 292435 size: 27834
+ret: 0         st: 0 flags:1 dts: 0.971000 pts: 0.971000 pos: 292477 size: 27834
 ret:-1         st: 1 flags:0  ts: 1.307000
 ret: 0         st: 1 flags:1  ts: 0.201000
-ret: 0         st: 1 flags:1 dts: 0.000000 pts: 0.000000 pos:    803 size:   208
+ret: 0         st: 1 flags:1 dts: 0.000000 pts: 0.000000 pos:    845 size:   208
 ret: 0         st:-1 flags:0  ts:-0.904994
-ret: 0         st: 0 flags:1 dts: 0.011000 pts: 0.011000 pos:   1019 size: 27837
+ret: 0         st: 0 flags:1 dts: 0.011000 pts: 0.011000 pos:   1061 size: 27837
 ret: 0         st:-1 flags:1  ts: 1.989173
-ret: 0         st: 0 flags:1 dts: 0.971000 pts: 0.971000 pos: 292435 size: 27834
+ret: 0         st: 0 flags:1 dts: 0.971000 pts: 0.971000 pos: 292477 size: 27834
 ret: 0         st: 0 flags:0  ts: 0.883000
-ret: 0         st: 0 flags:1 dts: 0.971000 pts: 0.971000 pos: 292435 size: 27834
+ret: 0         st: 0 flags:1 dts: 0.971000 pts: 0.971000 pos: 292477 size: 27834
 ret: 0         st: 0 flags:1  ts:-0.222000
-ret: 0         st: 0 flags:1 dts: 0.011000 pts: 0.011000 pos:   1019 size: 27837
+ret: 0         st: 0 flags:1 dts: 0.011000 pts: 0.011000 pos:   1061 size: 27837
 ret:-1         st: 1 flags:0  ts: 2.672000
 ret: 0         st: 1 flags:1  ts: 1.566000
-ret: 0         st: 1 flags:1 dts: 0.993000 pts: 0.993000 pos: 320276 size:   209
+ret: 0         st: 1 flags:1 dts: 0.993000 pts: 0.993000 pos: 320318 size:   209
 ret: 0         st:-1 flags:0  ts: 0.460008
-ret: 0         st: 0 flags:1 dts: 0.491000 pts: 0.491000 pos: 146987 size: 27925
+ret: 0         st: 0 flags:1 dts: 0.491000 pts: 0.491000 pos: 147029 size: 27925
 ret: 0         st:-1 flags:1  ts:-0.645825
-ret: 0         st: 0 flags:1 dts: 0.011000 pts: 0.011000 pos:   1019 size: 27837
+ret: 0         st: 0 flags:1 dts: 0.011000 pts: 0.011000 pos:   1061 size: 27837
