Shamir'in gizli paylaşımı nasıl çalışır

 (ente.com)
2 puan yazan GN⁺ 7 시간 전 | 1 yorum | WhatsApp'ta paylaş
  • Shamir gizli paylaşımı, bir sırrı birden çok parçaya böler; yalnızca eşik sayısına ulaşınca geri yüklenebilir ve daha az parçayla hiçbir bilgi açığa çıkmaz
  • Şirket ana anahtarı, aile hesabı kurtarma veya ekip yedekleri gibi durumlarda, tüm sırrı tek bir kişiye emanet etmenin zor olduğu ve bazı parçalar kaybolsa bile kurtarma gerektiği senaryolarda kullanışlıdır
  • Temel model, sırrı bir polinomun 0 noktasındaki değeri olarak gizler ve her parçayı eğri üzerindeki bir nokta olarak dağıtır
  • Eşik k için derece k - 1 olan bir polinom kullanılır; iki parça bir doğruya, üç parça bir parabol'e, dört parça ise kübik eğriye karşılık gelir
  • Ente Legacy Kit, bu yöntemi tek bir katman olarak kullanarak kartların kalıcı kurtarma anahtarına dönüşmesini engeller ve verilmiş kartların iptal edilebilmesini sağlar

Sırrı noktalara ve polinomlara bölme yöntemi

  • Adi Shamir tarafından 1979'da yayımlanan bu yöntemin özü, yalnızca “kırılması zordur” olmaması; gerekli parça sayısı eksikse hiçbir bilginin ortaya çıkmamasıdır
  • Farklı iki nokta tam olarak bir doğruyu belirler; ancak tek bir nokta varsa, o noktadan geçen sonsuz sayıda doğru vardır ve her biri dikey ekseni farklı bir konumda keser
  • Sır 7 sayısıysa, bu değer doğrunun dikey ekseni kestiği yerde gizlenebilir
  • Eğim, sırrın kendisi değil; sırrı gizlemek için kullanılan rastgelelik rolünü oynar
  • Her kişiye doğru üzerindeki bir nokta verilirse, tek bir kişinin elindeki bir noktayla uyumlu olabilecek sonsuz sayıda doğru vardır ve bunların her biri farklı bir sırla eşleşebilir
  • İki nokta birleştirildiğinde doğru sabitlenir ve doğrunun 0 noktasındaki değeri okunarak sır geri elde edilebilir
  • Bu yapı bir 2-of-n gizli paylaşım düzenidir; istenen kadar nokta üretilebilir, ancak herhangi iki nokta doğruyu yeniden kurmaya yeter
  • Eşik büyüdükçe daha yüksek dereceli eğriler kullanılır
    • Bir parabol ancak üç noktayla belirlenebilir; bu yüzden sır, parabolün dikey ekseni kestiği yerde gizlenirse herhangi üç parçayla kurtarma mümkündür, iki parçayla ise mümkün değildir
    • Genel olarak eşik k için derece k - 1 olan bir polinom kullanılır
    • 2 parça doğruya, 3 parça parabole, 4 parça ise kübik eğriye karşılık gelir
    • Gerçek uygulamalar grafik kağıdı yerine sonlu cisim aritmetiği kullanır; ancak sır yine 0 noktasındaki değerdir, rastgele katsayılar bunu gizler ve her parça polinom üzerindeki bir nokta olarak kalır
    • Önemli nokta, parça sayısı yetersiz olduğunda sırrın hesaplanmasının sadece zor olması değil, mümkün olan tüm sırların hâlâ olası kalmasıdır

Ente Legacy Kit ve başvuru kaynakları

İlgili okumalar

1 yorum

 
GN⁺ 7 시간 전
Hacker News yorumları

  • Bu konuda yüksek lisans tezi yazmıştım. Dropbox, Google Drive, OneDrive gibi sıradan depolama sağlayıcılarının birkaçına veriyi bölerek kaydeden bir uygulama yaptım ve şifrelemeyi desteklemek için gizli paylaşımı kullandım
    Avantajı, sağlayıcıların artık veriyi okuyamaması, yalnızca 2 tanesi ayakta kalsa bile çalışabildiği için ek yedeklilik sağlaması ve ana parolayı unutunca her şeyin bittiği diğer güvenli depolama uygulamalarının aksine mevcut hesap kurtarma süreçlerinin aynen kullanılabilmesiydi

    • Fikir güzel görünüyor; sonrasında bunun bir ürüne ya da açık kaynaklı bir uygulamaya dönüşüp dönüşmediğini merak ediyorum

  • Birden fazla anahtar/değer çiftini tek bir şifreli metin içinde birleştirmenin bir yolu olup olmadığını merak ediyorum. Yani basitçe art arda eklemeden ya da çıktı boyutunu patlatmadan, bu düzene bilgi koyan herkesin aynı şifreli parçayı saklayıp kendi anahtarıyla farklı bir değeri çözebilmesi gibi
    Böylece insanlar birbirlerinin yedeği olabilirken, neyin saklandığı konusunda da makul inkar edilebilirliğe sahip olabilirler

  • Yüksek lisans tezimde Shamir gizli paylaşımını mesh ağlara uygulamıştım. Amaç, mesh'teki bir düğüm saldırgan tarafından ele geçirilip o düğümün sırrı çıkarılsa bile tüm şifrelemenin kırılmasını imkansız kılmaktı

  • Ek bir gizli depoyu açan parolayı “demokratik olarak güvenli” şekilde dağıtmak için ekibimiz bu tekniği kullanıyor. O ek depoda, asıl gizli depoya nasıl erişileceğine dair bilgi bulunuyor
    https://packages.debian.org/trixie/ssss fena değil ve oldukça sezgisel bir uygulama

  • Shamir sayesinde bir kez ciddi anlamda kurtuldum. Neredeyse unutulmuş bir yedeği acilen geri yüklemem gerekti ve o sırada kullanılan rastgele parolayı yeniden oluşturabildim
    “Ne olur ne olmaz” diye aile üyelerine dağıtılmış parçalar vermiş olmam iyi olmuş

  • “Faydalı olan şey, parça sayısı yetersiz olduğunda sırrı hesaplamanın zor olması değildir. Parça sayısı yetersiz olduğunda sır hakkında hiçbir bilgi olmamasıdır. Bir parça eksikse, olası tüm sırlar hâlâ mümkündür” kısmı bana kuadratik elek ya da onun türevleriyle sayı çarpanlara ayırmayı hatırlatıyor
    Sonunda mod n kongrüanslarından bir sistem bulunup asal çarpanlar hesaplanıyor ama yeterince birikmeden önce bu imkansız. Her kongrüans da bir miktar bilgi taşıyor olmalı; hep hangi uzayda serbestlik derecesini azaltıyor olduğumuzu merak etmişimdir
    Burada da her parça polinom uzayını kısıtlıyor ama anahtarın ekseni kestiği noktayı söyleyecek kadar değil

  • Gerçekten harika bir teknik ve bilgisayar bilimcilerin polinomlarla yapabildiği ilginç şeylerden biri olarak ortaokulda bile öğretilebilecek türden

    • Ortaokul matematik öğretmeniyim ve bunu gerçekten öğrencilerime böyle öğretiyorum
      Doğrusal fonksiyon denklemini geri bulma dersinde Shamir'i tanıtıyor, öğrencilerin gizli PIN'i eğim olarak seçip iki nokta oluşturup bunu iki farklı öğrenciye vermesini sağlıyorum. O iki öğrenci eşleşip PIN'i yeniden bulmak zorunda kalıyor ve öğrenciler her zaman çok ilgili oluyor

  • Bruce Schneier bunu klasik kitap Applied Cryptography'de anlatmıştı ve HashiCorp Vault'ta da bir Go uygulaması vardı. Pratik açıdan, dağıtılan parçaların kaç bit olması gerektiğini hep merak etmişimdir
    Haber gruplarında duyduğum cevap “gerçek anahtar uzunluğundan 1 bit fazla” olmuştu. Günümüzde kuantum hesaplama tehdidinin 1) parça boyutu seçimini ve 2) genel olarak gizli paylaşımın artılarını ve eksilerini nasıl etkileyeceğini merak ediyorum

    • Temel Shamir yöntemi bilgi kuramsal olarak güvenlidir ve kuantum bilgisayarlardan da tamamen etkilenmez
      1 baytlık bir sır için ‘10 üzerinden eşik’ Shamir parçaları üretip bunların 9 tane 1 baytlık parçasını verseniz bile, evrendeki hiçbir bilgisayar sırrı çıkaramaz. Gerçek uygulamalarda bütünlük denetimi için mesaj doğrulama kodu ya da sağlama toplamı eklemek gerekir; bu yüzden birkaç bayt daha büyür
    • Bilgisayarlar genelde hatayı sevmediği için gizli paylaşım sonlu cisim üzerinde yapılır. Parça boyutu bir nokta (x, y) biçimindedir; x küçük olabilir ve katılımcı sayısı n ise genelde log n civarındadır, y ise cisim içindeki rastgele bir noktadır
      Shamir gizli paylaşımı bilgi kuramsal olarak güvenli olduğu için, k-out-of-n bir sırda k adet nokta olmadan kaba kuvvet denemesi yapıldığında tüm sırlar eşit derecede makul görünür. Bu yüzden cismin bit boyutunu istediğiniz gibi seçebilirsiniz ama elbette sırrın bit boyutundan büyük olmalıdır. 5 elemanlı bir sonlu cisimde 100 bit saklayamazsınız
      Genelde saldırganın sırrın kendisini kaba kuvvetle denemesini engellemek gerekir. Yöntem bilgi kuramsal olarak güvenli olsa da sırların kendisi çoğu zaman değildir. Örneğin cüzdan seed'i böyledir; bu yüzden sırra rastgelelik eklenir ve cisim bit boyutu yeterince büyük seçilerek bu tür saldırılar önlenir
      Tehdit modeline göre 80 bit ya da 128 bitlik bir cisim yeterince güvenli olabilir ve parça boyutu da 80 ya da 128 bitten biraz daha büyük olur. Kuantum bilgisayarlara gelince, bu yöntem bilgi kuramsal olarak güvenli olduğundan burada bir saldırı var olamaz
    • HashiCorp'un Vault'un seal/unseal süreci için hâlâ bir uygulamaya sahip olduğunu sanıyorum. Tabii bir şey değişmediyse
    • Shamir yöntemi cebirin temel teoremine dayanır. Bir n'inci derece polinomu benzersiz biçimde tanımlamak için n+1 nokta gerektiği fikri
      Bu yüzden n-of-k yapısı kurmak için n-1 dereceli bir p(x) polinomu oluşturur ve o polinomdan rastgele k nokta seçersiniz. i'inci parça basitçe (xi, yi) olur; dolayısıyla bit sayısını polinomun kurulduğu cisim belirler
      Cisim, tüm sırrı taşıyacak kadar geniş olmalı ve hem (x, y) değerlerini saklamak gerektiğinden parça boyutu en az sırrın iki katıdır. Tabii parçanın bozulmadığını doğrulamak için bir bütünlük kontrolü de gerekir
      Kuantum hesaplamanın burada hiçbir şeyi değiştirmediğini düşünüyorum. Tek bir nokta eksik olduğunda bile son nokta sırrı herhangi bir şeye dönüştürebilir ve bunu ayırt etmenin bir yolu yoktur
    • Tüm sırın alttaki cismin tek bir elemanı olması şart değil. Daha küçük cisim elemanlarından oluşan bir n-tuple da olabilir
      Absürt derecede çok sayıda parça beklemiyorsanız GF(2^8) oldukça doğal bir seçimdir ve büyük tamsayı aritmetiğiyle uğraşmanız gerekmez

  • Ente'nin uygulaması burada: (https://2of3.ente.com/)

    • Şimdiye kadar gördüklerim içinde en çok bunu beğendim ve çok kullanıcı dostu. Yine de biraz daha yapılandırılabilir olmasını isterdim
      İdeal olarak 3 of 4: A B C D ya da 2 of 3: E F G ve 1 of 1: H gibi yapılar oluşturabilse güzel olurdu
      Kurtarma sırasında tam olarak neye ihtiyaç olduğunu açıkça göstermek için kartlara ad vermenin bir yolu da iyi olurdu. Elbette mevcut tasarımın sadeliği de kendi başına bir avantaj
    • Çoğu Linux dağıtımında paketlenmiş bir uygulama da var: http://point-at-infinity.org/ssss
    • Tarayıcı tabanlı birkaç sürüm var; çevrimiçi kullanılabilir ya da indirilip çevrimdışı olarak çalıştırılabilir
      https://bs.parity.io/ -- http://passguardian.com/ -- https://iancoleman.io/shamir/

  • Birkaç yıl önce tarayıcıda Shamir gizli paylaşımı çalıştıran küçük bir araç yapmıştım. Sayfayı indirirseniz tamamen çevrimdışı da kullanabilirsiniz
    https://simon-frey.com/s4/

    • Birkaç yıl önce o sayfayı indirip birkaç USB diske kaydetmiştim; içine KeePass veritabanımı ve parola parçalarını da koymuştum
      Bunları aileden birkaç kişiye dağıttım ve ölürsem eşime vermelerini söyledim