diff --git a/libavformat/matroskaenc.c b/libavformat/matroskaenc.c
index 135d5e3abd..cf2bb7b933 100644
--- a/libavformat/matroskaenc.c
+++ b/libavformat/matroskaenc.c
@@ -226,6 +226,16 @@ static void put_ebml_num(AVIOContext *pb, uint64_t num, int bytes)
         avio_w8(pb, (uint8_t)(num >> i * 8));
 }
 
+/**
+ * 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);
+    put_ebml_num(pb, 8, 0);
+    avio_wb64(pb, uid);
+}
+
 static void put_ebml_uint(AVIOContext *pb, uint32_t elementid, uint64_t val)
 {
     int i, bytes = 1;
@@ -1104,7 +1114,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)))
@@ -1485,7 +1495,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;
 }
@@ -1684,7 +1694,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, MATROSKA_ID_ATTACHMENTS, 0, 0);
diff --git a/tests/fate/matroska.mak b/tests/fate/matroska.mak
index 4b9ee7a872..8cc35d52da 100644
--- a/tests/fate/matroska.mak
+++ b/tests/fate/matroska.mak
@@ -12,7 +12,7 @@ fate-matroska-prores-header-insertion-bz2: CMD = framecrc -i $(TARGET_SAMPLES)/m
 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 = 49a60ef91cf7302ab7276f9373f8a429
+fate-matroska-remux: REF = 8369f24de64aaa52cf57a699dcdc7d58
 
 FATE_MATROSKA-$(call ALLYES, MATROSKA_DEMUXER VORBIS_PARSER) += fate-matroska-xiph-lacing
 fate-matroska-xiph-lacing: CMD = framecrc -i $(TARGET_SAMPLES)/mkv/xiph_lacing.mka -c:a copy
diff --git a/tests/fate/wavpack.mak b/tests/fate/wavpack.mak
index bc7a5cc92f..e3cf4ec632 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 = a9da0444604848080b08e32de19f42d9
+fate-wavpack-matroska_mux-mono: REF = 7ebd447336f0ba76b41a3f32d1551f05
 
 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 = 60812e377937456863a3c899ee068060
+fate-wavpack-matroska_mux-61: REF = c95bca3c3023230a324c633942c453d5
 
 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 45b68b62bd..f1c6f889d4 100644
--- a/tests/ref/fate/aac-autobsf-adtstoasc
+++ b/tests/ref/fate/aac-autobsf-adtstoasc
@@ -1,5 +1,5 @@
-d10b73732b32f6b2f08885b40c41c77f *tests/data/fate/aac-autobsf-adtstoasc.matroska
-6606 tests/data/fate/aac-autobsf-adtstoasc.matroska
+9d0c81ce285a84c0137316004d091d95 *tests/data/fate/aac-autobsf-adtstoasc.matroska
+6620 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 3266501de6..b4c08e57dd 100644
--- a/tests/ref/fate/binsub-mksenc
+++ b/tests/ref/fate/binsub-mksenc
@@ -1 +1 @@
-03d376cc2e8622e7af540d4d9809dbf7
+3dd15fa67a1df541aa89565ceb7047cf
diff --git a/tests/ref/fate/matroska-flac-extradata-update b/tests/ref/fate/matroska-flac-extradata-update
index f274e1a75d..dfb2851b0f 100644
--- a/tests/ref/fate/matroska-flac-extradata-update
+++ b/tests/ref/fate/matroska-flac-extradata-update
@@ -1,5 +1,5 @@
-5070c157123b54e218c7e0a45d5606c8 *tests/data/fate/matroska-flac-extradata-update.matroska
-1977 tests/data/fate/matroska-flac-extradata-update.matroska
+83aca2772c52f6f802cac288f889382b *tests/data/fate/matroska-flac-extradata-update.matroska
+2019 tests/data/fate/matroska-flac-extradata-update.matroska
 #extradata 0:       34, 0x7acb09e7
 #extradata 1:       34, 0x7acb09e7
 #extradata 2:       34, 0x443402dd
diff --git a/tests/ref/fate/rgb24-mkv b/tests/ref/fate/rgb24-mkv
index 686c45ebfb..fc73604ebc 100644
--- a/tests/ref/fate/rgb24-mkv
+++ b/tests/ref/fate/rgb24-mkv
@@ -1,5 +1,5 @@
-f9feab2a7ed8f1049df1b70982291505 *tests/data/fate/rgb24-mkv.matroska
-58192 tests/data/fate/rgb24-mkv.matroska
+661b2d8ad9b7c5bf7389d3408c3695c4 *tests/data/fate/rgb24-mkv.matroska
+58206 tests/data/fate/rgb24-mkv.matroska
 #tb 0: 1/10
 #media_type 0: video
 #codec_id 0: rawvideo
diff --git a/tests/ref/lavf-fate/av1.mkv b/tests/ref/lavf-fate/av1.mkv
index bd8ae6eefa..28a8c890c7 100644
--- a/tests/ref/lavf-fate/av1.mkv
+++ b/tests/ref/lavf-fate/av1.mkv
@@ -1,3 +1,3 @@
-be4903a6a6710043383c8f38a535a8d3 *tests/data/lavf-fate/lavf.av1.mkv
-55636 tests/data/lavf-fate/lavf.av1.mkv
+339f457b665fb5e8652fd50f2d3c4823 *tests/data/lavf-fate/lavf.av1.mkv
+55650 tests/data/lavf-fate/lavf.av1.mkv
 tests/data/lavf-fate/lavf.av1.mkv CRC=0x7c27cc15
diff --git a/tests/ref/lavf/mka b/tests/ref/lavf/mka
index f212097bac..b3c4117d92 100644
--- a/tests/ref/lavf/mka
+++ b/tests/ref/lavf/mka
@@ -1,3 +1,3 @@
-9bd06ae5291de75c19a60c3f39db4c09 *tests/data/lavf/lavf.mka
-43538 tests/data/lavf/lavf.mka
+0d48d93057f14704f6b839bb15e7328a *tests/data/lavf/lavf.mka
+43552 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 04b554bb56..014ea06003 100644
--- a/tests/ref/lavf/mkv
+++ b/tests/ref/lavf/mkv
@@ -1,3 +1,3 @@
-85ef0666b3ad642221793b1c4f985011 *tests/data/lavf/lavf.mkv
-320418 tests/data/lavf/lavf.mkv
+06c38b55305367672a7fc4efb71947bc *tests/data/lavf/lavf.mkv
+320446 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 08c9c1ebdb..f297d407c8 100644
--- a/tests/ref/lavf/mkv_attachment
+++ b/tests/ref/lavf/mkv_attachment
@@ -1,3 +1,3 @@
-6f68dccaaaf875a0671f47e5b21c8cca *tests/data/lavf/lavf.mkv_attachment
-472566 tests/data/lavf/lavf.mkv_attachment
+cf27537eabb1f4f222e7391aa4f5250d *tests/data/lavf/lavf.mkv_attachment
+472601 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 a3dce35d86..e9f1e521f2 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:    666 size:   208
+ret: 0         st: 1 flags:1 dts: 0.000000 pts: 0.000000 pos:    694 size:   208
 ret: 0         st:-1 flags:0  ts:-1.000000
-ret: 0         st: 0 flags:1 dts: 0.011000 pts: 0.011000 pos:    882 size: 27837
+ret: 0         st: 0 flags:1 dts: 0.011000 pts: 0.011000 pos:    910 size: 27837
 ret: 0         st:-1 flags:1  ts: 1.894167
-ret: 0         st: 0 flags:1 dts: 0.971000 pts: 0.971000 pos: 292298 size: 27834
+ret: 0         st: 0 flags:1 dts: 0.971000 pts: 0.971000 pos: 292326 size: 27834
 ret: 0         st: 0 flags:0  ts: 0.788000
-ret: 0         st: 0 flags:1 dts: 0.971000 pts: 0.971000 pos: 292298 size: 27834
+ret: 0         st: 0 flags:1 dts: 0.971000 pts: 0.971000 pos: 292326 size: 27834
 ret: 0         st: 0 flags:1  ts:-0.317000
-ret: 0         st: 0 flags:1 dts: 0.011000 pts: 0.011000 pos:    882 size: 27837
+ret: 0         st: 0 flags:1 dts: 0.011000 pts: 0.011000 pos:    910 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: 320139 size:   209
+ret: 0         st: 1 flags:1 dts: 0.993000 pts: 0.993000 pos: 320167 size:   209
 ret: 0         st:-1 flags:0  ts: 0.365002
-ret: 0         st: 0 flags:1 dts: 0.491000 pts: 0.491000 pos: 146850 size: 27925
+ret: 0         st: 0 flags:1 dts: 0.491000 pts: 0.491000 pos: 146878 size: 27925
 ret: 0         st:-1 flags:1  ts:-0.740831
-ret: 0         st: 0 flags:1 dts: 0.011000 pts: 0.011000 pos:    882 size: 27837
+ret: 0         st: 0 flags:1 dts: 0.011000 pts: 0.011000 pos:    910 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: 292298 size: 27834
+ret: 0         st: 0 flags:1 dts: 0.971000 pts: 0.971000 pos: 292326 size: 27834
 ret: 0         st: 1 flags:0  ts:-0.058000
-ret: 0         st: 1 flags:1 dts: 0.000000 pts: 0.000000 pos:    666 size:   208
+ret: 0         st: 1 flags:1 dts: 0.000000 pts: 0.000000 pos:    694 size:   208
 ret: 0         st: 1 flags:1  ts: 2.836000
-ret: 0         st: 1 flags:1 dts: 0.993000 pts: 0.993000 pos: 320139 size:   209
+ret: 0         st: 1 flags:1 dts: 0.993000 pts: 0.993000 pos: 320167 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: 146850 size: 27925
+ret: 0         st: 0 flags:1 dts: 0.491000 pts: 0.491000 pos: 146878 size: 27925
 ret: 0         st: 0 flags:0  ts:-0.482000
-ret: 0         st: 0 flags:1 dts: 0.011000 pts: 0.011000 pos:    882 size: 27837
+ret: 0         st: 0 flags:1 dts: 0.011000 pts: 0.011000 pos:    910 size: 27837
 ret: 0         st: 0 flags:1  ts: 2.413000
-ret: 0         st: 0 flags:1 dts: 0.971000 pts: 0.971000 pos: 292298 size: 27834
+ret: 0         st: 0 flags:1 dts: 0.971000 pts: 0.971000 pos: 292326 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:    666 size:   208
+ret: 0         st: 1 flags:1 dts: 0.000000 pts: 0.000000 pos:    694 size:   208
 ret: 0         st:-1 flags:0  ts:-0.904994
-ret: 0         st: 0 flags:1 dts: 0.011000 pts: 0.011000 pos:    882 size: 27837
+ret: 0         st: 0 flags:1 dts: 0.011000 pts: 0.011000 pos:    910 size: 27837
 ret: 0         st:-1 flags:1  ts: 1.989173
-ret: 0         st: 0 flags:1 dts: 0.971000 pts: 0.971000 pos: 292298 size: 27834
+ret: 0         st: 0 flags:1 dts: 0.971000 pts: 0.971000 pos: 292326 size: 27834
 ret: 0         st: 0 flags:0  ts: 0.883000
-ret: 0         st: 0 flags:1 dts: 0.971000 pts: 0.971000 pos: 292298 size: 27834
+ret: 0         st: 0 flags:1 dts: 0.971000 pts: 0.971000 pos: 292326 size: 27834
 ret: 0         st: 0 flags:1  ts:-0.222000
-ret: 0         st: 0 flags:1 dts: 0.011000 pts: 0.011000 pos:    882 size: 27837
+ret: 0         st: 0 flags:1 dts: 0.011000 pts: 0.011000 pos:    910 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: 320139 size:   209
+ret: 0         st: 1 flags:1 dts: 0.993000 pts: 0.993000 pos: 320167 size:   209
 ret: 0         st:-1 flags:0  ts: 0.460008
-ret: 0         st: 0 flags:1 dts: 0.491000 pts: 0.491000 pos: 146850 size: 27925
+ret: 0         st: 0 flags:1 dts: 0.491000 pts: 0.491000 pos: 146878 size: 27925
 ret: 0         st:-1 flags:1  ts:-0.645825
-ret: 0         st: 0 flags:1 dts: 0.011000 pts: 0.011000 pos:    882 size: 27837
+ret: 0         st: 0 flags:1 dts: 0.011000 pts: 0.011000 pos:    910 size: 27837
