Indexing Data-Level Security

Menyeimbangkan faktor keamanan dan utilitas pada proses pencarian sebuah data terenkripsi

Layer Keamanan pada level data memang merepotkan, ketika kita memutuskan untuk meningkatkan security-level bukan hanya pada layer Application-Level tapi hingga ke Data-Layer.

Hal ini tentu membuat repot para Data Engineer maupun Developer yang mengelola dan menggunakan data untuk keperluan sebuah aplikasi. Fungsi pencarian dari database seperti DBMS (Postgresql,MySQL dan sejenisnya) pasti tidak dapat digunakan. Seperti pada contoh simpel pencarian berikut.

SELECT nama FROM penduduk WHERE nik = $nomor_nik

Proses bisnis aplikasi yang membutuhkan query dari suatu data untuk disajikan pada aplikasi tentu akan membutuhkan effort lebih tinggi dikarenakan data yang digunakan tidak lagi dalam bentuk plain namun terenkripsi.

Security begins where comfort ends

Frasa kalimat tersebut memang familiar di dunia cybersecurity yang merepresentasikan realitas pahit dalam pengamanan sebuah sistem elektronik. Kueri SQL seperti SELECT, LIKEterancam tidak bisa digunakan demi menutupi celah kebocoran data pada data-layer.

Masalah Indexing pada enrcrypted-data

Enkripsi terhadap data sensitif (seperti nama, alamat atau nomor identitas) minimal menggunakan standar seperti AES-256-GCM sebelum disimpan secara at-rest pada database sistem elektronik. Algoritma tersebut mewajibkan penggunaan Initialization Vector (IV) atau nonce unik untuk setiap kali enkripsi dijalankan.

Mekanisme enkripsi AES-256-GCM

Seperti mengirimkan pesan menggunakan amplop. Isi pesan sebelum dimasukkan ke amplop, diacak menjadi tulisan yang tidak bisa dibaca (AES 256 sebagai kunci amplop). Setelah amplop ditutup, ditempel segel khusus (Operasi GCM sebagai segel keaslian amplop). Setiap amplop yang dikirim walaupun isi pesannya sama akan diberikan nomor seri unik (Nonce IV).

Sifat keacakan ini memang bagus jika dilihat dari faktor keamanannya, namun secara fundamental melumpuhkan ultilitas database dengan kueri dasar seperti WHEREatau operator LIKE untuk scanning substring.

Solusi Hash

Salah satu operasi kriptografi yang output-nya akan sama dengan inputnya adalah fungsi hashing. Namun tidak boleh asal untuk memilih fungsi hash yang dapat digunakan untuk menyimpan sebuah “data” yang berisikan data terenkripsi yang sekaligus digunakan untuk indexing pencarian. Hash yang dipilih harus tahan terhadap kemungkinan hash-collision attack.

Terdapat beberapa pilihan mekanisme hashing yang dapat dimanfaatkan untuk operasi pencarian, diantaranya:

Hash Utuh

Mengubah data secara utuh satu kesatuan menggunakan hashing sebelum dimasukkan ke database.

Mekanisme hash keseluruhan

Mekanisme ini memiliki kelebihan pada kemudahan dalam mengubah data untuk kompatibel terhadap fungsi pencarian data dari aplikasi serta dari sisi pengelolaan database hanya cukup menambahkan satu kolom khusus yang berisikan hashing dari masing-masing data yang telah terenkripsi.

Namun teknik ini kurang optimal pada faktor seperti UX (User Experience) dikarenakan sisi end-user harus menuliskan input secara utuh (exact match). Perbedaan karakter memiliki efek terhadap fungsi kriptografi hash, yang nantinya mengakibatkan hasil kueri menghasilkan nilai nihil (false negative)

Hash per-x-Blok

Cara ini dilakukan dengan membagi sebuah data menjadi beberapa blok sesuai kebutuhan. Seperti contoh pada gambar berikut data “balerina capucina” akan dibagi menjadi 4 blok.

Mekanisme hash per-x blok

Pendekatan ini adalah versi “mendingan” dari segi UX pada mekanisme hash utuh. Alih-alih menuliskan input secara utuh, dari segi end-user cukup menuliskan sesuai blok hash-nya. Walupun seperti itu, mekanisme ini tetap memiliki potensi dari hasil kueri nilai nihil atau false negative dari hasil perbedaan input per-blok nya.

Hash Per-Karakter

Alih-alih melakukan hashing satu keutuhan atau sesuai jumlah blok. Pada pendekatan ini, berfokus pada faktor UX dinamis dengan menyimpan nilai hash setiap karakter dari suatu data.

Nilai suatu data akan disimpan nilai hash nya di setiap kombinasi rangkaian hashnya. Misal dari contoh berikut, data “balerina capucina” akan memiliki 17 nilai hash yang berbeda untuk disimpan pada database.

1 | 'b'                    | 575a0b1c44d8843f

 2 | 'ba'                   | a7f09059a74517b4
 3 | 'bal'                  | 87a1d800884e2297
 4 | 'bale'                 | a64c37dc319f68b9
 5 | 'baler'                | 0b8bd43c847df90c
 6 | 'baleri'               | 6d7fd1705e18758a
 7 | 'balerin'              | 0a2c5a9d707f9367
 8 | 'balerina'             | 3a076af8f4337000
 9 | 'balerina '            | f6167adcdc3f930e
10 | 'balerina c'           | 0fb465f91ffc4d10
11 | 'balerina ca'          | 661129e3309e46a2
12 | 'balerina cap'         | c025e41638d3109d
13 | 'balerina capu'        | 4e88803a97242006
14 | 'balerina capuc'       | 806825c34ba88f36
15 | 'balerina capuci'      | 69cca13ed700b8c9
16 | 'balerina capucin'     | 1e06d8599df221b7
17 | 'balerina capucina'    | 10cd5cd92ebcfed6

Mekanisme ini memiliki kelebihan dari segi UX. End-User menuliskan input dan dari aplikasi akan bisa langsung melakukan kueri terhadap nilai data, proses ini akan terlihat seamless bagi end-user.

Get amerta’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Namun kekurangan, dari pendekatan ini adalah membuat storage membengkak dikarenakan data hash yang harus disimpan tergantung dari seberapa panjang nilai karakter data yang disimpan.

Dari sekian solusi hashing yang telah dibahas, mekanisme tersebut memiliki tujuan yang sama. Yaitu menyimpan sebuah data dalam bentuk yang deterministik dalam database sehingga menghasilkan nilai yang sama.

Namun, beberapa contoh mekanisme tersebut dapat disesuaikan dengan kebutuhan proses bisnis aplikasi serta jenis pemanfaatan datanya. Ibarat sebuah beberapa jenis pisau yang digunakan untuk memotong, tetapi jenis pisau dapur, pisau bedah dan pisau cutter memiliki fungsi yang berbeda sesuai kebutuhannya.

Tantangan peforma indexing

Dari ketiga mekanisme pemanfaatan hashing tersebut memang dapat digunakan untuk melakukan indexing data, namun apa jadinya jika data yang dikelola adalah ratusan ribu hingga jutaan baris data?

Hal inilah yang dapat menjadi masalah dikedepannya, yaitu ketika faktor peforma, utilitas dan keamanan harus seimbang.

N-Gram Indexing Tokens

Saya menemukan sebuah ulasan tentang mekanisme dari N-Gram Indexing. Pada artikel tersebut fokus pada cara mengimplementasikan substring search terhadap data yang telah terenkripsi dengan metode indexing per-blok dengan tetap menimbang faktor latency dan keamanan dari proses indexing data.

Lalu berdsarkan ulasan tersebut, dengan bantuan claude 😹 . Saya mencoba untuk membuat sebuah proof of concept implementasi dari konsep N-Gram Indexing Tokens. Pada praktik tersebut saya menggunakan kondisi kolom yang dilakukan enkripsi adalah data NIK & nama penduduk.

Skema aplikasi yang akan dipakai adalah substring search. Dengan diawali tahap:

1. Pecah Data menjadi 3 Blok (Trigrams)

Dimulai dari n-grams, khususnya trigrams. Contohnya, suatu kata diubah menjadi rangkaian 3 karakter. Proses ini terjadi pada fungsi berikut:

const NGramSize = 3

func generateNGrams(s string) []string {
 runes := []rune(s)
 if len(runes) <= NGramSize {
  return []string{string(runes)}
 }
 result := make([]string, 0, len(runes)-NGramSize+1)
 for i := 0; i+NGramSize <= len(runes); i++ {
  result = append(result, string(runes[i:i+NGramSize]))
 }
 return result
}

Jadi jaya menjadi jay dan aya

Ada faktor krusial di tahap ini, sebuah fungsi yang sama dijalankan saat data pada proses insert dan search. Ketika timbul data baru, akan dipecah menjadi trigram; ketika end-user melakukan pencarian, kueri akan melakukan proses yang sama.

2. Hash setiap Trigram

Trigram yang telah dihasilkan tetaplah sebuah plaintext, jadi trigram tersebut akan dilakukan tokenisasi menggunakan servis kriptografi dengan endpoint /tokenize/blind-index

Sisi frontend aplikasi akan menerima nilai dari blind-index. Database hanya akan menerima nilai hash.

Hal inilah yang menjadikannya “blind index” indeks yang bisa dicari tapi tidak bisa dibalik nilainya. Tanpa key-nya, hash dari jay tidak mengekspos apapun.

3. Pencarian baris data berdasar Hash Token

Sekarang, pada servis pencarian ke database. Setiap blind token, akan melakukan kueri lookup terhadap index. (SearchNgramHandler)

query := `
    SELECT d.id, d.name, d.nik, de.id as enc_id, de.name_enc, de.nik_enc
    FROM data d
    LEFT JOIN data_enc de ON d.id = de.data_id
    WHERE d.id IN (
        SELECT data_id FROM index_data WHERE ngram_data_index = $1
    )
`
rows, err := db.Query(query, ngram)

Tabel index_data hanya menyimpan trigram yang sudah di-hash pada kolom ngram_data_index . Database melakukan pencocokan berdasarkan nilai hash yang cocok.

Proses hashing setiap trigram terlihat ‘mahal’ tetapi dari hal tersebut merupakan inti dari kecepatan pada servis database untuk melakukan kueri lookup. Seperti pada database schema berikut

CREATE INDEX idx_ngram_search ON index_data (ngram_data_index)

PostgreSQL menggunakan algoritma B-tree index pada proses pengolahan datanya. Algoritma tersebut mengubah setiap kueri per-trigram menjadi index equality lookup, bukan dengan sequential scan.

4. Visualisasi Alur Data

Ada dua alur pada pendekatan indexing data menggunakan n-gram token, yaitu insert dan search. sdsdsdsd Kedua alur tersebut melewati proses hashing dengan HMAC-SHA256 dari fungsi generateNGrams() . Token hasil search hanya akan cocok dengan token pada tabel index_data jika proses tokenisasinya sama, byte per byte.

Data Baru → Data Index (sekaligus saat proses insert)

Insert: name = "Jaya Wijaya"
         │
         ▼
generateNGrams(normalize(name))                      services/crypto/main.go
         │
         ▼
["jay","aya"," wi","wij","ija", ...]                 trigrams, sliding window
         │
         ▼
HMAC-SHA256(blind_key, trigram)  per trigram         POST /tokenize/blind-index
         │
         ▼
[hash1, hash2, hash3, ...]                           blind tokens; plaintext trigram discarded
         │
         ▼
INSERT INTO index_data (data_id, ngram_data_index)   Database API, one row per unique trigram
         │
         ▼
data ─┬─ data_enc                                    (AES-256-GCM ciphertext of name/nik)
      └─ index_data                                  (hash1..hashN — searchable, not reversible to plaintext)

Input Searching → Searching Index (per kueri)

Search: query = "jaya"
         │
         ▼
generateNGrams(query)                              services/crypto/main.go (fungsi yang sama dengan insert)
         │
         ▼
["jay", "aya"]
         │
         ▼
HMAC-SHA256(blind_key, trigram)                    per trigram   POST /tokenize/blind-index
         │
         ▼
[hash("jay"), hash("aya")]                         query itu sendiri tidak pernah sampai ke database
         │
         ▼
SearchNgramHandler()                               SELECT data_id FROM index_data WHERE ngram_data_index = $1
         │                                         (sekali per hash — B-tree index equality lookup, bukan scan)
         ▼
data ⋂ index_data WHERE ngram_data_index = hash    himpunan kandidat per hash
         │
         ▼
union + dedupe berdasarkan record id               gabungkan semua hash query
         │
         ▼
verifikasi ulang di klien: name.includes(query)    handleIndexedSearch() di SearchPanel.jsx
         │
         ▼
record yang cocok & terverifikasi                  plaintext tidak pernah keluar dari klien / crypto service

Alur Data:

search term → generateNGrams() → HMAC hash each → SearchNgramHandler() per hash → union of matching record IDs → client-side re-verify.

🚨🚨PENTING!!🚨🚨

Konsep N-Gram bergantung dari ukuran NGram yang dibuat diawal. Ukuran tidak bisa diganti ditengah jalan, seperti 1000 data awal memakai 3 blok lalu untuk 500 data selanjutnya memakai 5 blok. Hal ini tidak bisa dilakukan dan diperlukan reindexing kembali. Begitu pula dengan penggunaan algoritma hashing yang diimplementasikan data index.

Bentuk data yang tersimpan pada database

Data plain

Encrypted Data

Index Data

Setiap data terenkripsi memiliki data_id yang nantinya digunakan dari front-end aplikasi untuk melakukan kueri menampilkan data terenkripsi berdasarkan nilai masukkan searching index.

contoh dari sampel 2 juta baris data (kolom nik & nama)

Jumlah baris untuk kolom Index Data

Peningkatan untuk kondisi dua kolom (NIK dan Nama) masing-masing sebanyak 2 juta baris data (total 4 juta data terdiri dari NIK dan Nama) sebanyak 8 kali lipat dari data terenkripsi. Tentu faktor ini diluar variabel seperti kombinasi nama yang tentunya beragam (berbeda dengan NIK yang panjang jumlah pasti)

Terakhir, pada tulisan ini saya hanya membahas cara untuk melakukan indexing data terenkripsi. Belum use-case lainnya seperti ketika data mengalami perubahan sehingga perlu penyesuaian pada kamus indexing-nya, peforma kemampuan read-write dari servis database.

^_^