osu! Beatmap MD5 Collisions

A long proposed osu! multiplayer feature is to allow players to play different difficulties within the same beatmap set. In a casual setting, players of different skill levels can enjoy multiplayer together without having to worry about a map being too difficult for one, or too easy for another. This is especially the case when introducing friends who are new to the game.

osu! uses MD5 hashes of .osu files to lookup beatmaps. In the case of multiplayer, unsubmitted maps picked by the host are sent to other players in the room by name and hash. If two .osu files have the same MD5 hash, then maybe players can select different versions (difficulties) while the client and server think that they are the same map.

In this proof of concept, we use hashclash to perform a chosen-prefix-collision on two different beatmaps: AKINO from bless4 - MIIRO (Resolve) and Hanatan - Ai no Scenario (Skystar’s Extra), both roughly about 6 stars in difficulty.

Preparing the .osu files

Before running the CPC attack, we should first modify the beatmaps as if they were part of the same set, as well as add a fake section header so that the random suffix bytes minimally interfere with the beatmap parsing.

$ diff -U 1 "AKINO from bless4 - MIIRO (xChippy) [Resolve].osu" "AKINO from bless4 - MIIRO (xChippy) [Resolve] edited.osu"
--- "AKINO from bless4 - MIIRO (xChippy) [Resolve].osu"          2015-06-25 21:02:18.000000000 -0700
+++ "AKINO from bless4 - MIIRO (xChippy) [Resolve] edited.osu"   2020-12-20 17:19:01.728245100 -0800
@@ -21,12 +21,10 @@
 [Metadata]
-Title:MIIRO
-TitleUnicode:海色
-Artist:AKINO from bless4
-ArtistUnicode:AKINO from bless4
+Title:MIIRO vs. Ai no Scenario (Collision ver.)
+TitleUnicode:海色 vs. アイのシナリオ (Collision ver.)
+Artist:AKINO from bless4 & Hanatan
+ArtistUnicode:AKINO from bless4 & 花たん
 Creator:xChippy
-Version:Resolve
+Version:MIIRO - Resolve (MD5)
 Source:艦隊これくしょん -艦これ-
 Tags:Kantai Collection Kancolle opening op jonathanlfj nyquill oyatsu natsu kibbleru
-BeatmapID:612045
-BeatmapSetID:268851

@@ -1108 +1106,3 @@
 376,192,250680,1,14,0:0:0:0:
+
+[Metadata]

In this example, we update the Title and Artist to contain both beatmaps. We also update Version to reflect the map, and remove BeatmapID and BeatmapSetID. At the very end of the map, we add a [Metadata] section header, with a trailing a newline. osu! fails to process garbage bytes in the [HitObjects] section, but only displays a warning for malformed [Metadata].

An alternative method was to take advantage of the fact that hit objects ended with a “hitsound filename”, though it was not resilient to newlines generated by the collision.

$ diff -U 1 "Hanatan - Ai no Scenario (Chaoslitz) [Skystar's Extra].osu" "Hanatan - Ai no Scenario (Chaoslitz) [Skystar's Extra] edited.osu"
--- "Hanatan - Ai no Scenario (Chaoslitz) [Skystar's Extra].osu"          2015-11-28 08:45:38.000000000 -0800
+++ "Hanatan - Ai no Scenario (Chaoslitz) [Skystar's Extra] edited.osu"   2020-12-20 17:19:02.055544100 -0800
@@ -20,12 +20,10 @@
 [Metadata]
-Title:Ai no Scenario
-TitleUnicode:アイのシナリオ
-Artist:Hanatan
-ArtistUnicode:花たん
+Title:MIIRO vs. Ai no Scenario (Collision ver.)
+TitleUnicode:海色 vs. アイのシナリオ (Collision ver.)
+Artist:AKINO from bless4 & Hanatan
+ArtistUnicode:AKINO from bless4 & 花たん
 Creator:Chaoslitz
-Version:Skystar's Extra
+Version:Ai no Scenario - Skystar's Extra (MD5)
 Source:
 Tags:CHiCO with HoneyWorks nico douga magic kaito 1412 まじっく快斗1412 skystar amamiya yuko gaia kawaiwkyik rizia
-BeatmapID:760743
-BeatmapSetID:343365

@@ -1494 +1492,3 @@
 343,91,257543,1,0,0:0:0:0:
+
+[Metadata]

The same is done for the other beatmap, with a different Version.

Running hashclash

The hashclash implementation begins with a CUDA-optimized birthday search, followed by a CPU heavy collision search. On a relatively powerful CPU and GPU (i.e. desktop i7 + gtx 1080), the birthday search takes less than an hour, and the collision search 3 - 4 hours.

$ git clone git@github.com:cr-marcstevens/hashclash.git
$ cd hashclash
$ mkdir cpc_workdir
$ cd cpc_workdir
$ cp ..../miiro.osu ..../ai_no_scenario.osu .
$ ../scripts/cpc.sh miiro.osu ai_no_scenario.osu

When hashclash finishes, it will generate colliding .coll files.

$ md5sum miiro.osu.coll ai_no_scenario.osu.coll
059ecf662e25d80a62f141485ac61aea  miiro.osu.coll
059ecf662e25d80a62f141485ac61aea  ai_no_scenario.osu.coll

Packaging osz files

With the colliding beatmaps, we can now construct two different osz archives, using resources from the original beatmaps.

$ ls -1 "AKINO from bless4 - MIIRO (MD5)"
48320625_p0.jpg
'AKINO from bless4 - MIIRO (xChippy) [Resolve].osu'
BGyey.jpg
KancolleBG.jpg
Wheee.mp3
normal-hitclap3.wav
soft-hitclap2.wav
soft-hitclap3.wav
soft-hitwhistle2.wav
soft-sliderslide.wav
soft-sliderslide2.wav

$ ls -1 "Hanatan - Ai no Scenario (MD5)"
'Hanatan - Ai no Scenario (Chaoslitz) [Skystar'\''s Extra].osu'
bg.jpg
drum-hitclap3.wav
drum-hitnormal.wav
drum-hitnormal2.wav
drum-sliderslide2.wav
normal-hitclap.wav
normal-slidertick4.wav
scenario.mp3
soft-hitclap.wav
soft-hitnormal.wav
soft-hitnormal3.wav
soft-sliderslide2.wav
soft-sliderslide3.wav
video.flv