URL hashing

Ringkasan

Daftar Web Risk terdiri dari hash SHA256 dengan panjang variabel. Untuk mengetahui detail selengkapnya, lihat Daftar Isi. Untuk memeriksa URL terhadap daftar Web Risk, baik secara lokal maupun di server, klien harus terlebih dahulu menghitung awalan hash URL tersebut.

Untuk menghitung awalan hash URL, ikuti langkah-langkah berikut:

  1. Lakukan kanonikalisasi URL seperti yang dijelaskan dalam Kanonikalisasi.
  2. Buat ekspresi akhiran/awalan untuk URL seperti yang dijelaskan di bagian Ekspresi akhiran/awalan.
  3. Hitung hash panjang penuh untuk setiap ekspresi akhiran/awalan seperti yang dijelaskan di bagian Penghitungan hash.
  4. Hitung awalan hash untuk setiap hash panjang penuh, seperti yang dijelaskan dalam Penghitungan awalan hash.

Perhatikan bahwa langkah-langkah ini mencerminkan proses yang digunakan server Web Risk untuk memelihara daftar Web Risk.

Kanonikalisasi

Untuk memulai, kami mengasumsikan bahwa klien telah mem-parsing URL dan membuatnya valid sesuai dengan RFC 2396. Jika URL menggunakan Nama Domain Internasional (IDN), klien harus mengonversi URL ke representasi Punycode ASCII. URL harus menyertakan komponen jalur; yaitu, harus memiliki garis miring di awal (http://google.com/).

Pertama, hapus karakter tab (0x09), CR (0x0d), dan LF (0x0a) dari URL. Jangan hapus urutan escape untuk karakter ini, seperti %0a.

Kedua, jika URL diakhiri dengan fragmen, hapus fragmen tersebut. Misalnya, persingkat http://google.com/#frag menjadi http://google.com/.

Ketiga, hapus escape persen dari URL berulang kali hingga tidak ada lagi escape persen.

Untuk mengkanonisasi nama host

Ekstrak nama host dari URL, lalu:

  1. Hapus semua titik di awal dan akhir.
  2. Ganti titik berurutan dengan satu titik.
  3. Jika nama host dapat diuraikan sebagai alamat IP, normalisasikan ke 4 nilai desimal yang dipisahkan titik. Klien harus menangani encoding alamat IP yang sah, termasuk oktal, hex, dan kurang dari empat komponen.
  4. Ubah seluruh string menjadi huruf kecil.

Untuk melakukan kanonikalisasi jalur

  1. Selesaikan urutan /../ dan /./ di jalur dengan mengganti /./ dengan /, dan menghapus /../ beserta komponen jalur sebelumnya.
  2. Ganti rangkaian garis miring berurutan dengan satu karakter garis miring.

Jangan terapkan kanonisasi jalur ini ke parameter kueri.

Dalam URL, lakukan escape persentase pada semua karakter yang <= ASCII 32, >= 127, #, atau %. Escape harus menggunakan karakter hex huruf besar.

Berikut adalah pengujian untuk membantu memvalidasi penerapan kanonisasi.

Canonicalize("http://host/%25%32%35") = "http://host/%25";
Canonicalize("http://host/%25%32%35%25%32%35") = "http://host/%25%25";
Canonicalize("http://host/%2525252525252525") = "http://host/%25";
Canonicalize("http://host/asdf%25%32%35asd") = "http://host/asdf%25asd";
Canonicalize("http://host/%%%25%32%35asd%%") = "http://host/%25%25%25asd%25%25";
Canonicalize("http://www.google.com/") = "http://www.google.com/";
Canonicalize("http://%31%36%38%2e%31%38%38%2e%39%39%2e%32%36/%2E%73%65%63%75%72%65/%77%77%77%2E%65%62%61%79%2E%63%6F%6D/") = "http://168.188.99.26/.secure/www.ebay.com/";
Canonicalize("http://195.127.0.11/uploads/%20%20%20%20/.verify/.eBaysecure=updateuserdataxplimnbqmn-xplmvalidateinfoswqpcmlx=hgplmcx/") = "http://195.127.0.11/uploads/%20%20%20%20/.verify/.eBaysecure=updateuserdataxplimnbqmn-xplmvalidateinfoswqpcmlx=hgplmcx/";
Canonicalize("http://host%23.com/%257Ea%2521b%2540c%2523d%2524e%25f%255E00%252611%252A22%252833%252944_55%252B") = "http://host%23.com/~a!b@c%23d$e%25f^00&11*22(33)44_55+";
Canonicalize("http://3279880203/blah") = "http://195.127.0.11/blah";
Canonicalize("http://www.google.com/blah/..") = "http://www.google.com/";
Canonicalize("www.google.com/") = "http://www.google.com/";
Canonicalize("www.google.com") = "http://www.google.com/";
Canonicalize("http://www.evil.com/blah#frag") = "http://www.evil.com/blah";
Canonicalize("http://www.GOOgle.com/") = "http://www.google.com/";
Canonicalize("http://www.google.com.../") = "http://www.google.com/";
Canonicalize("http://www.google.com/foo\tbar\rbaz\n2") ="http://www.google.com/foobarbaz2";
Canonicalize("http://www.google.com/q?") = "http://www.google.com/q?";
Canonicalize("http://www.google.com/q?r?") = "http://www.google.com/q?r?";
Canonicalize("http://www.google.com/q?r?s") = "http://www.google.com/q?r?s";
Canonicalize("http://evil.com/foo#bar#baz") = "http://evil.com/foo";
Canonicalize("http://evil.com/foo;") = "http://evil.com/foo;";
Canonicalize("http://evil.com/foo?bar;") = "http://evil.com/foo?bar;";
Canonicalize("http://\x01\x80.com/") = "http://%01%80.com/";
Canonicalize("http://notrailingslash.com") = "http://notrailingslash.com/";
Canonicalize("http://www.gotaport.com:1234/") = "http://www.gotaport.com/";
Canonicalize("  http://www.google.com/  ") = "http://www.google.com/";
Canonicalize("http:// leadingspace.com/") = "http://%20leadingspace.com/";
Canonicalize("http://%20leadingspace.com/") = "http://%20leadingspace.com/";
Canonicalize("%20leadingspace.com/") = "http://%20leadingspace.com/";
Canonicalize("https://www.securesite.com/") = "https://www.securesite.com/";
Canonicalize("http://host.com/ab%23cd") = "http://host.com/ab%23cd";
Canonicalize("http://host.com//twoslashes?more//slashes") = "http://host.com/twoslashes?more//slashes";

Ekspresi akhiran/awalan

Setelah URL dikanonisasi, langkah selanjutnya adalah membuat ekspresi akhiran/awalan. Setiap ekspresi akhiran/awalan terdiri dari akhiran host (atau host lengkap) dan awalan jalur (atau jalur lengkap) seperti yang ditunjukkan dalam contoh ini.

Ekspresi Akhiran/Awalan Regular Expression yang Setara
a.b/mypath/ http\:\/\/.*\.a\.b\/mypath\/.*
c.d/full/path.html?myparam=a http\:\/\/.*.c\.d\/full\/path\.html?myparam=a

Klien akan membentuk hingga 30 kemungkinan kombinasi awalan jalur dan akhiran host yang berbeda. Kombinasi ini hanya menggunakan komponen host dan jalur URL. Skema, nama pengguna, sandi, dan port akan dihapus. Jika URL menyertakan parameter kueri, maka setidaknya satu kombinasi akan menyertakan jalur lengkap dan parameter kueri.

Untuk host, klien akan mencoba paling banyak lima string yang berbeda. Yaitu:

  • Nama host yang tepat dalam URL.
  • Hingga empat nama host yang dibentuk dengan memulai lima komponen terakhir dan menghapus komponen terdepan secara berturut-turut. Domain level teratas dapat dilewati. Nama host tambahan ini tidak boleh diperiksa jika host adalah alamat IP.

Untuk jalur, klien akan mencoba paling banyak enam string yang berbeda. Yaitu:

  • Jalur persis URL, termasuk parameter kueri.
  • Jalur persis URL, tanpa parameter kueri.
  • Empat jalur yang dibentuk dengan memulai dari root (/) dan menambahkan komponen jalur secara berturut-turut, termasuk garis miring di akhir.

Contoh berikut menggambarkan perilaku pemeriksaan:

Untuk URL http://a.b.c/1/2.html?param=1, klien akan mencoba kemungkinan string berikut:

a.b.c/1/2.html?param=1
a.b.c/1/2.html
a.b.c/
a.b.c/1/
b.c/1/2.html?param=1
b.c/1/2.html
b.c/
b.c/1/

Untuk URL http://a.b.c.d.e.f.g/1.html, klien akan mencoba kemungkinan string berikut:

a.b.c.d.e.f.g/1.html
a.b.c.d.e.f.g/
(Note: skip b.c.d.e.f.g, since we'll take only the last five hostname components, and the full hostname)
c.d.e.f.g/1.html
c.d.e.f.g/
d.e.f.g/1.html
d.e.f.g/
e.f.g/1.html
e.f.g/
f.g/1.html
f.g/

Untuk URL http://1.2.3.4/1/, klien akan mencoba kemungkinan string berikut:

1.2.3.4/1/
1.2.3.4/

Penghitungan hash

Setelah kumpulan ekspresi akhiran/awalan dibuat, langkah selanjutnya adalah menghitung hash SHA256 dengan panjang penuh untuk setiap ekspresi. Berikut adalah pengujian unit dalam pseudo-C yang dapat Anda gunakan untuk memvalidasi komputasi hash Anda.

Contoh dari FIPS-180-2:

// Example B1 from FIPS-180-2
string input1 = "abc";
string output1 = TruncatedSha256Prefix(input1, 32);
int expected1[] = { 0xba, 0x78, 0x16, 0xbf };
assert(output1.size() == 4);  // 4 bytes == 32 bits
for (int i = 0; i < output1.size(); i++) assert(output1[i] == expected1[i]);

// Example B2 from FIPS-180-2
string input2 = "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq";
string output2 = TruncatedSha256Prefix(input2, 48);
int expected2[] = { 0x24, 0x8d, 0x6a, 0x61, 0xd2, 0x06 };
assert(output2.size() == 6);
for (int i = 0; i < output2.size(); i++) assert(output2[i] == expected2[i]);

// Example B3 from FIPS-180-2
string input3(1000000, 'a');  // 'a' repeated a million times
string output3 = TruncatedSha256Prefix(input3, 96);
int expected3[] = { 0xcd, 0xc7, 0x6e, 0x5c, 0x99, 0x14, 0xfb, 0x92,
                    0x81, 0xa1, 0xc7, 0xe2 };
assert(output3.size() == 12);
for (int i = 0; i < output3.size(); i++) assert(output3[i] == expected3[i]);

Komputasi awalan hash

Terakhir, klien perlu menghitung awalan hash untuk setiap hash SHA256 dengan panjang penuh. Untuk Web Risk, awalan hash terdiri dari 4-32 byte paling signifikan dari hash SHA256.

Contoh dari FIPS-180-2:

  • Contoh B1 dari FIPS-180-2
    • Inputnya adalah "abc".
    • Hash SHA256 adalah ba7816bf 8f01cfea 414140de 5dae2223 b00361a3 96177a9c b410ff61 f20015ad.
    • Awalan hash 32-bit adalah ba7816bf.
  • Contoh B2 dari FIPS-180-2
    • Inputnya adalah abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq.
    • Hash SHA256 adalah 248d6a61 d20638b8 e5c02693 0c3e6039 a33ce459 64ff2167 f6ecedd4 19db06c1.
    • Awalan hash 48-bit adalah 248d6a61 d206.