diff --git a/keyserver/src/database/migration-config.js b/keyserver/src/database/migration-config.js
--- a/keyserver/src/database/migration-config.js
+++ b/keyserver/src/database/migration-config.js
@@ -184,6 +184,25 @@
       );
     },
   ],
+  [
+    17,
+    async () => {
+      await dbQuery(
+        SQL`
+          ALTER TABLE cookies 
+            DROP INDEX device_token,
+            DROP INDEX user_device_token;
+
+          ALTER TABLE cookies
+            MODIFY device_token mediumtext 
+              CHARACTER SET utf8mb4 COLLATE utf8mb4_bin DEFAULT NULL,
+            ADD UNIQUE KEY device_token (device_token(512)),
+            ADD KEY user_device_token (user,device_token(512));
+        `,
+        { multipleStatements: true },
+      );
+    },
+  ],
 ]);
 const newDatabaseVersion: number = Math.max(...migrations.keys());
 
diff --git a/keyserver/src/database/setup-db.js b/keyserver/src/database/setup-db.js
--- a/keyserver/src/database/setup-db.js
+++ b/keyserver/src/database/setup-db.js
@@ -31,7 +31,7 @@
         platform varchar(255) DEFAULT NULL,
         creation_time bigint(20) NOT NULL,
         last_used bigint(20) NOT NULL,
-        device_token varchar(255) DEFAULT NULL,
+        device_token mediumtext CHARACTER SET utf8mb4 COLLATE utf8mb4_bin DEFAULT NULL,
         versions json DEFAULT NULL,
         device_id varchar(255) DEFAULT NULL,
         signed_identity_keys mediumtext CHARACTER SET utf8mb4 COLLATE utf8mb4_bin DEFAULT NULL,
@@ -249,8 +249,8 @@
 
       ALTER TABLE cookies
         ADD PRIMARY KEY (id),
-        ADD UNIQUE KEY device_token (device_token),
-        ADD KEY user_device_token (user,device_token);
+        ADD UNIQUE KEY device_token (device_token(512)),
+        ADD KEY user_device_token (user,device_token(512));
 
       ALTER TABLE days
         ADD PRIMARY KEY (id),