Cara Kerja Pembagian Rahasia Shamir

• Pembagian rahasia Shamir membagi sebuah rahasia menjadi beberapa bagian, dan hanya dapat dipulihkan ketika jumlah yang terkumpul mencapai ambang batas atau lebih; jika kurang dari itu, tidak ada informasi yang terungkap
• Berguna saat sulit mempercayakan seluruh rahasia kepada satu orang, seperti untuk master key perusahaan, pemulihan akun keluarga, atau cadangan tim, sambil tetap membutuhkan pemulihan meski sebagian bagian hilang
• Model intinya menyembunyikan rahasia sebagai nilai pada titik 0 dari sebuah polinomial, lalu membagikan setiap bagian sebagai satu titik di atas kurva
• Untuk ambang batas k, digunakan polinomial berderajat k - 1; dua bagian berarti garis lurus, tiga bagian parabola, dan empat bagian kurva kubik
• Ente Legacy Kit menggunakan metode ini sebagai satu lapisan agar kartu tidak menjadi kunci pemulihan permanen, serta memungkinkan kartu yang telah diterbitkan untuk dicabut

---

Cara membagi rahasia dengan titik dan polinomial

• Metode ini diperkenalkan oleh Adi Shamir pada 1979, dan intinya bukan sekadar “sulit dibobol”, melainkan bahwa jika jumlah bagian yang dibutuhkan tidak mencukupi maka tidak ada informasi sama sekali yang terungkap
• Dua titik yang berbeda menentukan tepat satu garis lurus, tetapi jika hanya ada satu titik maka ada tak terhingga banyaknya garis yang melewati titik itu, dan masing-masing memotong sumbu vertikal di posisi yang berbeda
• Jika rahasianya adalah angka 7, nilai ini bisa disembunyikan pada posisi tempat garis memotong sumbu vertikal
• Kemiringan garis bukanlah rahasia itu sendiri, melainkan berperan sebagai keacakan untuk menyembunyikan rahasia
• Jika setiap orang diberi satu titik di atas garis, maka dengan hanya satu titik milik satu orang saja akan ada tak terhingga banyak garis yang mungkin, dan semuanya kompatibel dengan rahasia yang berbeda-beda
• Jika dua titik digabungkan, garisnya menjadi tetap, dan rahasia dapat dipulihkan dengan membaca nilai yang dimiliki garis itu pada 0
• Struktur ini adalah skema pembagian rahasia 2-of-n; titik dapat dibuat sebanyak yang diinginkan, tetapi sembarang dua titik dapat memulihkan garis
• Saat ambang batas meningkat, digunakan kurva dengan derajat yang lebih tinggi
  • Parabola harus ditentukan oleh tiga titik, jadi jika rahasia disembunyikan pada posisi tempat parabola memotong sumbu vertikal, maka pemulihan dapat dilakukan dengan sembarang tiga bagian dan tidak dapat dilakukan dengan dua bagian
  • Secara umum, untuk ambang batas k digunakan polinomial berderajat k - 1
  • 2 bagian berarti garis lurus, 3 bagian berarti parabola, 4 bagian berarti kurva kubik
  • Implementasi nyata tidak memakai kertas grafik, melainkan aritmetika medan hingga, tetapi strukturnya tetap sama: rahasia adalah nilai pada 0, koefisien acak menyembunyikannya, dan setiap bagian adalah satu titik pada polinomial
  • Yang penting, jika bagian yang tersedia tidak mencukupi, persoalannya bukan sekadar sulit menghitung rahasia, tetapi semua rahasia yang mungkin tetap sama-sama mungkin

Ente Legacy Kit dan referensi

• Ente menggunakan ide ini dalam Legacy Kit
• Tujuan yang dibutuhkan bukan hanya membagi rahasia, tetapi juga memungkinkan pemulihan tanpa membuat bagian-bagian yang terpisah itu menjadi kunci pemulihan permanen
• Legacy Kit menggunakan metode Shamir sebagai satu lapisan dalam alur yang lebih besar
• Kartu tidak berisi kunci pemulihan itu sendiri; sebagai gantinya, kartu ikut berpartisipasi dalam pemulihan yang dimediasi server setelah merekonstruksi rahasia terpisah secara lokal
• Berkat struktur ini, kartu yang sudah diterbitkan dapat dicabut, dan kartu yang hilang tidak menjadi tanggung jawab permanen
• Referensi
  • “How to Share a Secret” oleh Adi Shamir
  • “Sharing Secrets Among Friends” oleh Bruce Schneier
  • Kisah PayPal dari Max Levchin
  • Kode sumber Ente

[GN⁺]

Komentar Hacker News

• Saya menulis tesis master tentang topik ini. Saya membuat aplikasi yang membagi dan menyimpan data ke beberapa penyedia penyimpanan umum seperti Dropbox, Google Drive, dan OneDrive, lalu menggunakan pembagian rahasia untuk membantu enkripsi
  Keuntungannya adalah penyedia tidak lagi bisa membaca data, ada redundansi tambahan karena cukup dua lokasi yang tetap hidup, dan tidak seperti aplikasi penyimpanan aman lain yang selesai begitu Anda lupa kata sandi utama, prosedur pemulihan akun yang sudah ada tetap bisa digunakan

  • Idenya terdengar bagus, saya penasaran apakah setelah itu berlanjut menjadi produk atau aplikasi open source

• Saya penasaran apakah ada cara menggabungkan beberapa pasangan kunci/nilai menjadi satu ciphertext. Bukan sekadar menempelkannya atau membuat ukuran hasil meledak, tetapi dengan cara agar semua orang yang memasukkan informasi ke skema ini menyimpan gumpalan terenkripsi yang sama, namun dengan kunci masing-masing mereka bisa mendekripsi nilai yang berbeda
  Dengan begitu orang-orang bisa saling menjadi cadangan satu sama lain, sambil tetap memiliki penyangkalan yang masuk akal tentang apa yang sebenarnya disimpan

• Dalam tesis master saya, saya menerapkan Shamir secret sharing pada jaringan mesh. Tujuannya agar meskipun satu node di mesh direbut penyerang dan rahasia node itu dipulihkan, keseluruhan enkripsi tetap tidak bisa dibobol

• Tim kami menggunakan teknik ini untuk mendistribusikan frasa sandi penyimpanan rahasia cadangan dengan cara yang “aman secara demokratis”. Penyimpanan cadangan itu berisi cara mengakses penyimpanan rahasia utama
  https://packages.debian.org/trixie/ssss adalah implementasi yang cukup baik dan lumayan intuitif

• Shamir pernah benar-benar menyelamatkan saya. Saya harus buru-buru memulihkan cadangan yang hampir terlupakan, dan saya bisa merekonstruksi kata sandi acak yang dipakai saat itu
  Untungnya saya sudah membagikan fragmen terdistribusi kepada keluarga “untuk berjaga-jaga”

• Bagian “hal yang berguna bukanlah bahwa jika fragmennya terlalu sedikit maka sulit menghitung rahasianya. Yang berguna adalah bahwa jika fragmennya terlalu sedikit, tidak ada informasi sama sekali tentang rahasia itu. Kurang satu fragmen saja, semua rahasia yang mungkin tetap sama-sama mungkin” mengingatkan saya pada proses memfaktorkan bilangan dengan medan kuadrat atau variannya
  Kita mencari sistem kongruensi mod n dan pada akhirnya menghitung faktor prima, tetapi sebelum cukup banyak terkumpul hal itu mustahil. Setiap kongruensi pasti memuat sebagian informasi, jadi saya selalu penasaran, di ruang seperti apa sebenarnya kita sedang mengurangi derajat kebebasan?
  Di sini juga, setiap fragmen membatasi ruang polinomial, tetapi belum cukup untuk memberi tahu di mana kunci memotong sumbu

• Ini benar-benar teknik yang keren, dan cukup menarik sebagai contoh hal yang bisa dilakukan ilmuwan komputer dengan polinomial sampai-sampai bisa diajarkan di sekolah menengah

  • Saya guru matematika sekolah menengah, dan memang mengajarkannya seperti ini kepada murid-murid
    Saat mengajar cara mendapatkan kembali persamaan fungsi linear, saya memperkenalkan Shamir, lalu siswa memilih PIN rahasia sebagai kemiringan, membuat dua titik, dan membagikannya kepada dua siswa lain. Kedua siswa itu harus berpasangan untuk menemukan kembali PIN tersebut, dan para siswa selalu sangat terlibat

• Bruce Schneier menjelaskan ini dalam buku klasik Applied Cryptography, dan HashiCorp Vault juga pernah memiliki implementasi Go. Secara praktis, saya selalu penasaran berapa bit seharusnya ukuran fragmen yang didistribusikan
  Jawaban yang saya dengar di newsgroup adalah “1 bit lebih panjang dari panjang kunci sebenarnya”. Sekarang saya penasaran bagaimana ancaman komputasi kuantum akan memengaruhi 1) pemilihan ukuran fragmen dan 2) kelebihan serta kekurangan pembagian rahasia secara umum

  • Skema Shamir dasar itu aman secara teori informasi, dan sama sekali tidak terpengaruh oleh komputer kuantum
    Anda bisa membuat fragmen Shamir ‘ambang dari 10’ untuk rahasia 1 byte dan memberikan 9 dari fragmen 1 byte itu, dan komputer mana pun di alam semesta tidak akan bisa menemukan rahasianya. Dalam implementasi nyata, beberapa byte tambahan dibutuhkan untuk kode autentikasi pesan atau checksum demi verifikasi integritas
  • Biasanya pembagian rahasia dilakukan di medan hingga karena komputer umumnya tidak suka dengan pecahan. Ukuran fragmen adalah titik (x, y); x bisa kecil, biasanya sekitar log n jika ada n peserta, dan y adalah titik acak dalam medan tersebut
    Shamir secret sharing aman secara teori informasi, jadi untuk rahasia k-dari-n, jika Anda tidak punya k titik maka bahkan brute force tetap membuat semua rahasia sama-sama masuk akal. Karena itu ukuran bit medannya bisa dipilih sesuka Anda, tetapi tentu harus lebih besar daripada ukuran bit rahasianya. Anda tidak bisa menyembunyikan 100 bit di medan hingga yang hanya punya 5 elemen
    Biasanya Anda harus mencegah penyerang melakukan brute force terhadap rahasianya sendiri, karena meskipun skemanya aman secara teori informasi, rahasia itu sendiri biasanya tidak demikian. Misalnya seed dompet kripto, jadi Anda menambahkan keacakan pada rahasia dan memilih ukuran bit medan yang cukup besar untuk mencegah serangan seperti itu
    Tergantung model ancamannya, medan 80 bit atau 128 bit sudah cukup aman, dan ukuran fragmennya juga hanya sedikit lebih besar dari 80 bit atau 128 bit. Untuk komputer kuantum, karena skema ini aman secara teori informasi, serangan semacam itu tidak mungkin ada
  • Setahu saya HashiCorp masih memiliki implementasi untuk proses seal/unseal Vault, kecuali kalau ada perubahan
  • Skema Shamir didasarkan pada teorema dasar aljabar. Untuk mendefinisikan polinomial derajat n secara unik, dibutuhkan n+1 titik
    Jadi untuk membuat konfigurasi n-of-k, Anda membuat polinomial p(x) berderajat n-1, lalu mengambil k titik acak dari polinomial itu. Fragmen ke-i hanyalah (xi, yi), jadi jumlah bitnya ditentukan oleh medan yang membentuk polinomial tersebut
    Medan itu harus cukup besar untuk menampung seluruh rahasia, dan karena Anda harus menyimpan dua nilai (x, y), ukuran fragmen minimal dua kali ukuran rahasia. Meski begitu, Anda tetap memerlukan pemeriksaan integritas untuk memastikan fragmen tidak rusak
    Menurut pemahaman saya, komputasi kuantum tidak mengubah apa pun di sini. Jika kurang satu titik saja, titik terakhir bisa mengubah rahasia menjadi apa pun, dan tidak ada cara untuk membedakannya
  • Seluruh rahasia tidak harus berupa satu elemen dari medan dasarnya. Itu juga bisa berupa n-tuple dari elemen-elemen medan yang lebih kecil
    Jika Anda tidak mengharapkan jumlah fragmen yang sangat banyak, GF(2^8) adalah pilihan yang cukup alami, dan tidak perlu menangani operasi bilangan bulat besar

• Implementasi Ente ada di sini: (https://2of3.ente.com/)

  • Ini yang paling saya suka dari semua yang pernah saya lihat sejauh ini, dan sangat ramah pengguna. Meski begitu, akan lebih baik jika sedikit lebih bisa dikonfigurasi
    Idealnya, akan bagus jika bisa membuat konfigurasi seperti 3 of 4: A B C D atau 2 of 3: E F G dan 1 of 1: H
    Akan bagus juga jika ada cara memberi nama pada kartu agar jelas persis apa yang dibutuhkan saat pemulihan. Tentu saja, kesederhanaan desain saat ini juga punya kelebihannya sendiri
  • Ada juga implementasi yang dipaketkan untuk sebagian besar distribusi Linux: http://point-at-infinity.org/ssss
  • Ada beberapa versi berbasis browser, dan bisa dipakai online atau diunduh untuk digunakan offline
    https://bs.parity.io/ -- http://passguardian.com/ -- https://iancoleman.io/shamir/

• Beberapa tahun lalu saya membuat alat kecil yang menjalankan Shamir secret sharing di browser. Jika halamannya diunduh, alat itu bisa dipakai sepenuhnya offline
  https://simon-frey.com/s4/

  • Beberapa tahun lalu saya mengunduh halaman itu dan menyimpannya di beberapa USB disk, bersama basis data KeePass dan fragmen kata sandinya
    Saya membagikannya ke beberapa anggota keluarga, dan memberi tahu mereka untuk menyerahkannya kepada istri saya jika saya meninggal