[Downloads/History] Comply with RFC 4122 when generating GUIDs.

components/history/core/browser/download_database.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "components/history/core/browser/download_database.h"
 
 #include <limits>
 #include <string>
 #include <vector>
 
@@ skipping 174 matching lines @@
   return EnsureColumnExists("etag", "VARCHAR NOT NULL DEFAULT \"\"") &&
          EnsureColumnExists("last_modified", "VARCHAR NOT NULL DEFAULT \"\"");
 }
 
 bool DownloadDatabase::MigrateHashHttpMethodAndGenerateGuids() {
   if (!EnsureColumnExists("guid", "VARCHAR NOT NULL DEFAULT ''") ||
       !EnsureColumnExists("hash", "BLOB NOT NULL DEFAULT X''") ||
       !EnsureColumnExists("http_method", "VARCHAR NOT NULL DEFAULT ''"))
     return false;
 
-  // Generate GUIDs for each download. The GUID is generated thusly:
+  // Generate GUIDs for each download. GUIDs based on random data should conform
+  // with RFC 4122 section 4.4. Given the following field layout (based on RFC
+  // 4122):
   //
-  //    XXXXXXXX-RRRR-RRRR-RRRR-RRRRRRRRRRRR
+  //  0                   1                   2                   3
+  //  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+  //  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+  //  |                          time_low                             |
+  //  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+  //  |       time_mid                |         time_hi_and_version   |
+  //  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+  //  |clk_seq_hi_res |  clk_seq_low  |         node (0-1)            |
+  //  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+  //  |                         node (2-5)                            |
+  //  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+  //
+  // * Bits 4-7 of time_hi_and_version should be set to 0b0100 == 4
+  // * Bits 6-7 of clk_seq_hi_res should be set to 0b10
+  // * All other bits should be random or pseudorandom.
+  //
+  // We are going to take the liberty of setting time_low to the 32-bit download
+  // ID. That will guarantee that no two randomly generated GUIDs will collide
+  // even if the 90 bits of entropy doesn't save us.
+  //
+  // Translated to the canonical string representation, the GUID is generated
+  // thusly:
+  //
+  //    XXXXXXXX-RRRR-4RRR-yRRR-RRRRRRRRRRRR
   //    \__  __/ \___________  ____________/
   //       \/                \/
-  //       |          Random hex digits
+  //       |          R = random hex digit.
+  //       |          y = one of {'8','9','A','B'} selected randomly.
+  //       |          4 = the character '4'.
   //       |
   //       Hex representation of 32-bit download ID.
   //
-  // The 96 random bits provide entropy while the 32-bits from the download ID
-  // ensure that the generated identifiers will at least be unique amongst the
-  // download rows in the unlikely event there's a collision in the 96 entropy
-  // bits.
-  //
   // This GUID generation scheme is only used for migrated download rows and
   // assumes that the likelihood of a collision with a GUID generated via
   // base::GenerateGUID() will be vanishingly small.
+  //
+  // A previous version of this code generated GUIDs that used random bits for
+  // all but the first 32-bits. I.e. the scheme didn't respect the 6 fixed bits
+  // as prescribed for type 4 GUIDs. The resulting GUIDs are not believed to
+  // have an elevated risk of collision with GUIDs generated via
+  // base::GenerateGUID() and are considered valid by all known consumers. Hence
+  // no additional migration logic is being introduced to fix those GUIDs.
   const char kMigrateGuidsQuery[] =
       "UPDATE downloads SET guid = printf"
-      "(\"%08X-%s-%s-%s-%s\", id, hex(randomblob(2)), hex(randomblob(2)),"
-      " hex(randomblob(2)), hex(randomblob(6)))";
+      "(\"%08X-%s-4%s-%01X%s-%s\","
+      " id,"
+      " hex(randomblob(2)),"
+      " substr(hex(randomblob(2)),2),"
+      " (8 | (random() & 3)),"
+      " substr(hex(randomblob(2)),2),"
+      " hex(randomblob(6)))";
   return GetDB().Execute(kMigrateGuidsQuery);
 }
 
 bool DownloadDatabase::InitDownloadTable() {
   const char kSchema[] =
       "CREATE TABLE downloads ("
       "id INTEGER PRIMARY KEY,"             // Primary key.
       "guid VARCHAR NOT NULL,"              // GUID.
       "current_path LONGVARCHAR NOT NULL,"  // Current disk location
       "target_path LONGVARCHAR NOT NULL,"   // Final disk location
@@ skipping 388 matching lines @@
 size_t DownloadDatabase::CountDownloads() {
   EnsureInProgressEntriesCleanedUp();
 
   sql::Statement statement(GetDB().GetCachedStatement(SQL_FROM_HERE,
       "SELECT count(*) from downloads"));
   statement.Step();
   return statement.ColumnInt(0);
 }
 
 }  // namespace history