Tajne udostępnianie

Dzielenie się tajemnicą (zwane również dzieleniem tajemnicy ) odnosi się do metod rozpowszechniania tajemnicy wśród grupy w taki sposób, że żadna osoba nie posiada żadnych zrozumiałych informacji na temat tajemnicy, ale gdy wystarczająca liczba osób połączy swoje „udziały”, tajemnica może zostać zrekonstruowany. Podczas gdy niezabezpieczone udostępnianie poufne pozwala atakującemu uzyskać więcej informacji przy każdym udostępnieniu, bezpieczne udostępnianie poufne to „wszystko albo nic” (gdzie „wszystko” oznacza niezbędną liczbę udostępnień).

W jednym typie schematu dzielenia się tajemnicą jest jeden dealer i n graczy . Krupier przekazuje graczom udział w tajemnicy, ale dopiero po spełnieniu określonych warunków gracze będą mogli odtworzyć sekret ze swoich udziałów. Rozdający osiąga to, dając każdemu graczowi część w taki sposób, że dowolna grupa t (dla progu ) lub więcej graczy może razem zrekonstruować sekret, ale żadna grupa mniej niż t graczy nie może. Taki układ nazywa się a ( t , n ) -schemat progowy (czasami jest zapisywany jako ( n , t ) -schemat progowy).

Tajne udostępnianie zostało wymyślone niezależnie przez Adi Shamira i George'a Blakleya w 1979 roku.

Znaczenie

Schematy tajnego udostępniania są idealne do przechowywania informacji, które są bardzo wrażliwe i bardzo ważne. Przykłady obejmują: klucze szyfrujące , kody startowe rakiet i numerowane konta bankowe . Każda z tych informacji musi być ściśle poufna, ponieważ ich ujawnienie może mieć katastrofalne skutki; jednak bardzo ważne jest, aby ich nie zgubić. Tradycyjne metody szyfrowania nie nadają się do jednoczesnego osiągnięcia wysokiego poziomu poufności i niezawodności. Dzieje się tak, ponieważ podczas przechowywania klucza szyfrowania należy wybrać między przechowywaniem jednej kopii klucza w jednym miejscu w celu zachowania maksymalnej poufności lub przechowywaniem wielu kopii klucza w różnych lokalizacjach w celu zwiększenia niezawodności. Zwiększenie niezawodności klucza poprzez przechowywanie wielu kopii obniża poufność poprzez tworzenie dodatkowych wektorów ataku; jest więcej okazji, aby kopia wpadła w niepowołane ręce. Schematy tajnego udostępniania rozwiązują ten problem i umożliwiają osiągnięcie dowolnie wysokiego poziomu poufności i niezawodności.

Dzielenie się tajemnicą pozwala również dystrybutorowi tajemnicy zaufać grupie „łącznie”. Tradycyjnie przekazanie sekretu grupie na przechowanie wymagałoby od dystrybutora całkowitego zaufania wszystkim członkom grupy. Schematy dzielenia się tajemnicą pozwalają dystrybutorowi bezpiecznie przechowywać tajemnicę w grupie, nawet jeśli nie wszystkim członkom można zawsze ufać. Tak długo, jak liczba zdrajców nigdy nie przekracza liczby krytycznej potrzebnej do odtworzenia tajemnicy, tajemnica jest bezpieczna.

Schematy tajnego udostępniania są ważne w środowiskach przetwarzania w chmurze . W ten sposób klucz może być dystrybuowany na wiele serwerów za pomocą progowego mechanizmu udostępniania tajnych informacji. Klucz jest następnie rekonstruowany w razie potrzeby. Zasugerowano również tajne udostępnianie w sieciach czujników , w których łącza mogą być podsłuchiwane poprzez wysyłanie danych w udziałach, co utrudnia zadanie podsłuchującemu. Bezpieczeństwo w takich środowiskach można zwiększyć poprzez ciągłą zmianę konstrukcji udziałów.

„Bezpieczne” kontra „niepewne” udostępnianie tajnych informacji

Bezpieczny schemat udostępniania poufnych informacji rozdziela udziały w taki sposób, że każdy, kto ma mniej niż t udziałów, nie ma więcej informacji na temat sekretu niż ktoś, kto ma 0 udziałów.

Rozważmy na przykład tajny schemat udostępniania, w którym tajna fraza „hasło” jest podzielona na udziały „pa––––––”, „––ss––––”, „––––wo––”, i „––––––rd”. Osoba z 0 udziałami wie tylko, że hasło składa się z ośmiu liter, a więc musiałaby odgadnąć hasło z 26 8 = 208 miliardów możliwych kombinacji. Jednak osoba z jednym udziałem musiałaby odgadnąć tylko sześć liter z 26 6 = 308 milionów kombinacji i tak dalej, w miarę jak więcej osób będzie w zmowie. W związku z tym ten system nie jest „bezpiecznym” schematem udostępniania tajemnic, ponieważ gracz z mniej niż t tajnych udziałów jest w stanie zredukować problem pozyskania tajemnicy wewnętrznej bez konieczności uprzedniego uzyskania wszystkich niezbędnych udziałów.

W przeciwieństwie do tego, rozważ schemat współdzielenia sekretu, w którym X jest sekretem do udostępnienia, P i to publiczne asymetryczne klucze szyfrujące, a Q i odpowiadające im klucze prywatne. Każdy gracz J otrzymuje { P 1 ( P 2 (...( P N ( X )))), Q j }. W tym schemacie każdy gracz z kluczem prywatnym 1 może usunąć zewnętrzną warstwę szyfrowania, gracz z kluczami 1 i 2 może usunąć pierwszą i drugą warstwę i tak dalej. Gracz z mniej niż N kluczami nigdy nie może w pełni dotrzeć do tajnego X bez konieczności uprzedniego odszyfrowania obiektu blob zaszyfrowanego kluczem publicznym, dla którego nie ma odpowiedniego klucza prywatnego – problem, który obecnie uważa się za niewykonalny obliczeniowo. Dodatkowo widzimy, że każdy użytkownik ze wszystkimi N kluczami prywatnymi jest w stanie odszyfrować wszystkie zewnętrzne warstwy, aby uzyskać X , tajemnica, w związku z czym ten system jest bezpiecznym systemem dystrybucji tajemnicy.

Ograniczenia

Mówi się, że kilka schematów udostępniania tajemnic jest teoretycznie bezpiecznych informacji i można to udowodnić, podczas gdy inne rezygnują z tego bezwarunkowego bezpieczeństwa w celu zwiększenia wydajności przy jednoczesnym zachowaniu wystarczającego bezpieczeństwa, aby można je było uznać za równie bezpieczne, jak inne popularne prymitywy kryptograficzne. Na przykład mogą zezwolić na ochronę tajemnic za pomocą udziałów o entropii 128 bitów każdy, ponieważ każdy udział byłby uważany za wystarczający do powstrzymania każdego możliwego współczesnego przeciwnika, co wymagałoby ataku brutalnej siły o średniej wielkości 2 127 .

Wspólne dla wszystkich bezwarunkowo bezpiecznych schematów udostępniania informacji tajnych są ograniczenia:

  • Każda część tajemnicy musi być co najmniej tak duża, jak sama tajemnica. Wynik ten opiera się na teorii informacji , ale można go zrozumieć intuicyjnie. Mając t − 1 udziałów, nie można ustalić żadnych informacji o tajemnicy. Tak więc ostateczny udział musi zawierać tyle informacji, ile sam sekret. Czasami można obejść to ograniczenie, najpierw kompresując klucz tajny przed jego udostępnieniem, ale często nie jest to możliwe, ponieważ wiele sekretów (na przykład kluczy) wygląda jak losowe dane wysokiej jakości i dlatego trudno je skompresować.
  • Wszystkie tajne schematy udostępniania używają losowych bitów do konstruowania udziałów. Aby rozdzielić jednobitowe tajne udziały z progiem t udziałów, potrzeba t − 1 losowych bitów. Aby rozdzielić tajemnicę b bitów, konieczna jest entropia ( t - 1) × b bitów.

Trywialne udostępnianie sekretów

t = 1

t = 1 udostępnianie sekretów jest trywialne. Sekret można po prostu rozesłać do wszystkich n uczestników.

t = n

Istnieje kilka ( t , n ) schematów udostępniania sekretu dla t = n , kiedy wszystkie udziały są niezbędne do odzyskania sekretu:

  1. Zakoduj sekret jako liczbę binarną s o dowolnej długości. Daj każdemu graczowi i oprócz ostatniego losową liczbę binarną pi o tej samej długości co s . Daj ostatniemu graczowi udział obliczony jako p n = s p 1 p 2 ⊕ ... ⊕ p n −1 , gdzie ⊕ oznacza wyłączność bitową lub . Sekret tkwi w bitowej wyłączności wszystkich liczb graczy ( s ja , dla 1 ≤ ja n ).
  2. Zamiast tego (1) można wykonać za pomocą operacji binarnej w dowolnej grupie . Weźmy na przykład cykliczną grupę liczb całkowitych z dodatkiem modulo 2 32 , która odpowiada 32-bitowym liczbom całkowitym z dodawaniem zdefiniowanym przy odrzuceniu przepełnienia binarnego. Tajne s można podzielić na wektor złożony z M 32-bitowych liczb całkowitych, które nazywamy v tajnymi . Następnie ( n - 1) z graczy otrzymuje wektor złożony z M 32-bitowych liczb całkowitych, który jest losowany niezależnie od jednolitego rozkładu prawdopodobieństwa, przy czym gracz otrzymuję v i . _ Pozostały gracz otrzymuje v n = v sekret v 1 v 2 − ... − v n −1 . Tajny wektor można następnie odzyskać, sumując wszystkie wektory graczy.

1 < t < n , a bardziej ogólnie dowolny żądany podzbiór {1, 2, ..., n }

Trudność polega na tworzeniu schematów, które są nadal bezpieczne, ale nie wymagają wszystkich n udziałów. Na przykład wyobraź sobie, że zarząd firmy chciałby chronić swoją tajną formułę. Prezes firmy powinien mieć dostęp do formuły w razie potrzeby, ale w nagłych przypadkach każdy 3 z 12 członków zarządu będzie w stanie wspólnie odblokować tajną formułę. Można to osiągnąć za pomocą tajnego schematu podziału z t = 3 i n = 15 , gdzie 3 akcje są przydzielane prezesowi, a 1 każdemu członkowi zarządu.

Gdy wydajność przestrzenna nie jest problemem, można zastosować trywialne schematy t = n , aby ujawnić tajemnicę dowolnym pożądanym podzbiorom graczy, po prostu stosując schemat dla każdego podzbioru. Na przykład, aby ujawnić sekret s dowolnym dwóm z trzech graczy Alicji, Bobowi i Carol, utwórz trzy ( ) różne t = n = 2 sekret udziały za s , dając trzy zestawy po dwa udziały Alicji i Bobowi, Alicji i Karoli oraz Bobowi i Karolinie.

Efektywne udostępnianie sekretów

Trywialne podejście szybko staje się niepraktyczne, gdy liczba podzbiorów wzrasta, na przykład przy ujawnianiu tajemnicy dowolnym 50 ze 100 graczom, co wymagałoby schematów do utworzenia i utrzymania każdego gracza odrębne zestawy akcji dla każdego programu. W najgorszym przypadku wzrost jest wykładniczy. Doprowadziło to do poszukiwania schematów, które umożliwiają efektywne dzielenie się tajemnicami z progiem graczy.

Schemat Shamira

W tym schemacie do odzyskania tajemnicy można użyć dowolnych t z n udziałów. System opiera się na założeniu, że można dopasować unikalny wielomian stopnia t -1 do dowolnego zestawu punktów t leżących na wielomianie. Potrzeba dwóch punktów, aby zdefiniować linię prostą, trzech punktów, aby w pełni zdefiniować kwadrat, czterech punktów, aby zdefiniować krzywą sześcienną i tak dalej. Oznacza to, że potrzeba t punktów, aby zdefiniować wielomian stopnia t − 1 . Metoda polega na utworzeniu wielomianu stopnia t - 1 z tajemnicą jako pierwszym współczynnikiem, a pozostałe współczynniki wybierane losowo. Następnie znajdź n punktów na krzywej i daj po jednym każdemu z graczy. Kiedy co najmniej t z n graczy ujawni swoje punkty, jest wystarczająco dużo informacji, aby dopasować do nich wielomian ( t − 1) stopnia, przy czym pierwszy współczynnik jest tajemnicą.

Schemat Blakleya

Dwie nierównoległe proste w tej samej płaszczyźnie przecinają się dokładnie w jednym punkcie. Trzy nierównoległe płaszczyzny w przestrzeni przecinają się dokładnie w jednym punkcie. Mówiąc bardziej ogólnie, dowolne n nierównoległych ( n - 1) -wymiarowych hiperpłaszczyzn przecinają się w określonym punkcie. Sekret może być zakodowany jako dowolna pojedyncza współrzędna punktu przecięcia. Jeśli tajemnica jest zakodowana przy użyciu wszystkich współrzędnych, nawet jeśli są one losowe, wówczas insider (ktoś posiadający jedną lub więcej hiperpłaszczyzn wymiarowych ( n - 1 ) ) zdobywa informacje o tajemnicy, ponieważ wie, że musi ona leżeć w jego samolocie. Jeśli osoba z wewnątrz może zdobyć więcej wiedzy na temat tajemnicy niż osoba z zewnątrz, system nie ma już teoretycznego bezpieczeństwa informacji . Jeśli używana jest tylko jedna z n współrzędnych, wówczas osoba z wewnątrz nie wie więcej niż osoba z zewnątrz (tzn. że sekret musi leżeć na osi x dla systemu dwuwymiarowego). Każdy gracz otrzymuje wystarczającą ilość informacji, aby zdefiniować hiperpłaszczyznę; sekret jest odzyskiwany poprzez obliczenie punktu przecięcia płaszczyzn, a następnie pobranie określonej współrzędnej tego przecięcia.

One share Two shares intersecting on a line Three shares intersecting at a point
Schemat Blakleya w trzech wymiarach: każdy udział jest płaszczyzną , a tajemnicą jest punkt, w którym przecinają się trzy udziały. Dwie akcje to za mało, by ustalić tajemnicę, chociaż dostarczają wystarczająco dużo informacji, by zawęzić ją do linii, w której przecinają się obie płaszczyzny.

Schemat Blakleya jest mniej wydajny przestrzennie niż schemat Shamira; podczas gdy udziały Shamira są tylko tak duże, jak oryginalny sekret, udziały Blakleya są t razy większe, gdzie t jest progową liczbą graczy. Schemat Blakleya można zaostrzyć, dodając ograniczenia dotyczące tego, które samoloty mogą być używane jako udziały. Otrzymany schemat jest równoważny systemowi wielomianów Shamira.

Korzystanie z chińskiego twierdzenia o resztach

Chińskie twierdzenie o resztach może być również użyte do dzielenia się tajemnicą, ponieważ dostarcza nam metody jednoznacznego wyznaczania liczby S modulo k wielu par liczb całkowitych względnie pierwszych , biorąc pod uwagę, że . Istnieją dwa tajne schematy udostępniania, które wykorzystują chińskie twierdzenie o resztach, schematy Mignotte'a i schematy Asmutha-Blooma. Są to progowe schematy udostępniania tajemnic, w których udziały są generowane przez redukcję modulo liczb całkowitych układu kongruencji przy użyciu chińskiego twierdzenia o resztach.

Proaktywne udostępnianie tajemnic

Jeśli gracze przechowują swoje udziały na niezabezpieczonych serwerach komputerowych, osoba atakująca może się włamać i ukraść udziały. Jeśli zmiana tajemnicy nie jest praktyczna, bezkompromisowe akcje (w stylu Shamira) można odnowić. Krupier generuje nowy losowy wielomian ze stałym wyrazem zero i oblicza dla każdego pozostałego gracza nową uporządkowaną parę, w której współrzędne x starej i nowej pary są takie same. Następnie każdy gracz dodaje do siebie stare i nowe współrzędne y i zachowuje wynik jako nową współrzędną y sekretu.

Wszystkie niezaktualizowane udziały zgromadzone przez atakującego stają się bezużyteczne. Osoba atakująca może odzyskać tajemnicę tylko wtedy, gdy znajdzie wystarczającą liczbę innych niezaktualizowanych udziałów, aby osiągnąć próg. Taka sytuacja nie powinna mieć miejsca, ponieważ gracze usunęli swoje stare udziały. Ponadto osoba atakująca nie może odzyskać żadnych informacji o oryginalnym kluczu tajnym z plików aktualizacji, ponieważ zawierają one tylko losowe informacje.

Krupier może zmienić liczbę progową podczas dystrybucji aktualizacji, ale musi zawsze zachować czujność wobec graczy przechowujących wygasłe akcje.

Weryfikowalne udostępnianie informacji tajnych

Gracz może kłamać na temat swojego udziału, aby uzyskać dostęp do innych udziałów. Weryfikowalny udostępniania poufnych informacji (VSS) daje graczom pewność, że żaden inny gracz nie kłamie na temat zawartości swoich udziałów, aż do rozsądnego prawdopodobieństwa błędu. Takich schematów nie można obliczyć w sposób konwencjonalny; gracze muszą wspólnie dodawać i mnożyć liczby, tak aby żadna osoba nie wiedziała, co dokładnie jest dodawane i mnożone. Tal Rabin i Michael Ben-Or opracowali przetwarzanie wielopartyjne (MPC) system, który pozwala graczom wykryć nieuczciwość ze strony rozdającego lub ze strony maksymalnie jednej trzeciej progowej liczby graczy, nawet jeśli ci gracze są koordynowani przez atakującego „adaptacyjnego”, który może zmieniać strategie w czasie rzeczywistym w zależności od tego, jakie informacje zostało ujawnione.

Bezpieczne obliczeniowo udostępnianie tajnych informacji

Wadą bezwarunkowo bezpiecznych schematów współdzielenia poufnych jest to, że przechowywanie i przesyłanie udziałów wymaga ilości zasobów pamięci masowej i przepustowości równoważnej wielkości sekretu pomnożonej przez liczbę udziałów. Jeśli wielkość tajemnicy była znacząca, powiedzmy 1 GB, a udziałów było 10, to udziałowcy muszą przechowywać 10 GB danych. Zaproponowano alternatywne techniki w celu znacznego zwiększenia wydajności schematów udostępniania tajemnic, poprzez rezygnację z wymogu bezwarunkowego bezpieczeństwa.

Jedna z tych technik, znana jako dzielenie się tajemnicą w skrócie , łączy algorytm rozpraszania informacji Rabina (IDA) z tajnym udostępnianiem Shamira. Dane są najpierw szyfrowane losowo generowanym kluczem przy użyciu algorytmu szyfrowania symetrycznego. Następnie te dane są dzielone na N części za pomocą IDA Rabina. Ten IDA jest skonfigurowany z progiem, w sposób podobny do tajnych schematów udostępniania, ale w przeciwieństwie do tajnych schematów udostępniania, rozmiar wynikowych danych rośnie o współczynnik (liczba fragmentów / próg). Na przykład, jeśli próg wynosiłby 10, a liczba fragmentów wyprodukowanych przez IDA wynosiła 15, całkowity rozmiar wszystkich fragmentów wyniósłby (15/10) lub 1,5 razy większy niż rozmiar oryginalnego wejścia. W tym przypadku ten schemat jest 10 razy bardziej wydajny niż gdyby schemat Shamira został zastosowany bezpośrednio do danych. Ostatnim krokiem w skróceniu tajnego udostępniania jest wykorzystanie tajnego udostępniania Shamir do tworzenia udziałów losowo generowanego klucza symetrycznego (który zwykle jest rzędu 16–32 bajtów), a następnie przekazanie każdemu udziałowcowi jednego udziału i jednego fragmentu.

Podejście pokrewne, znane jako AONT-RS, stosuje transformację typu „wszystko albo nic” do danych jako krok wstępnego przetwarzania do IDA. Transformacja typu „wszystko albo nic” gwarantuje, że dowolna liczba udziałów mniejsza niż próg jest niewystarczająca do odszyfrowania danych.

Wielotajne i efektywne przestrzennie (wsadowe) udostępnianie tajnych danych

Teoretycznie bezpieczny schemat współdzielenia sekretów k -z- n generuje n udziałów, każdy o rozmiarze co najmniej równym rozmiarowi samego sekretu, co prowadzi do tego, że całkowita wymagana pamięć jest co najmniej n -krotnie większa niż sekret. W udostępnianiu wielu tajemnic zaprojektowanym przez Matthew K. Franklina i Moti Yunga , wiele punktów wielomianowych tajemnic hosta; metoda okazała się przydatna w wielu zastosowaniach, od kodowania po obliczenia wielostronne. Efektywne udostępnianie tajemnic w kosmosie, opracowane przez Abhishek Parakh i Subhash Kak , każdy udział jest w przybliżeniu równy wielkości sekretu podzielonej przez k − 1 .

Schemat ten wykorzystuje powtarzalną interpolację wielomianową i ma potencjalne zastosowanie w bezpiecznym rozpowszechnianiu informacji w sieci iw sieciach czujników . Metoda ta opiera się na partycjonowaniu danych obejmującym pierwiastki wielomianu w ciele skończonym. Później zwrócono uwagę na pewne luki w zabezpieczeniach powiązanych schematów efektywnego udostępniania tajemnic w przestrzeni kosmicznej . Pokazują one, że schemat oparty na metodzie interpolacji nie może być wykorzystany do realizacji schematu ( k , n ) gdy k sekrety do rozdysponowania są z natury generowane z wielomianu stopnia mniejszego niż k − 1 , a schemat nie działa, jeśli wszystkie sekrety do udostępnienia są takie same itp.

Inne zastosowania i zastosowania

Schemat udostępniania poufnych danych może zabezpieczyć poufne dane na wielu serwerach i zachować możliwość ich odzyskania pomimo wielu awarii serwerów. Dealer może działać jako kilku odrębnych uczestników, rozdzielając akcje między uczestników. Każdy udział może być przechowywany na innym serwerze, ale krupier może odzyskać tajemnicę nawet w przypadku awarii kilku serwerów, o ile są w stanie odzyskać co najmniej t udziałów; jednak crackerzy , którzy włamują się na jeden serwer, nadal nie poznaliby sekretu, o ile na każdym serwerze przechowywanych jest mniej niż t udziałów.

Jest to jedna z głównych koncepcji projektu komputerowego Vanish na Uniwersytecie Waszyngtońskim , w którym losowy klucz jest używany do szyfrowania danych, a klucz jest dystrybuowany jako sekret w kilku węzłach w sieci P2P . Aby odszyfrować wiadomość, co najmniej t węzłów w sieci musi być dostępnych; Zasadą tego konkretnego projektu jest to, że liczba węzłów udostępniających sekrety w sieci będzie się naturalnie zmniejszać z czasem, co spowoduje ostatecznie zniknięcie sekretu . Jednak sieć jest podatna na atak Sybil , co sprawia, że ​​Vanish jest niepewny.

Każdy udziałowiec, który ma wystarczającą ilość informacji do odszyfrowania zawartości w dowolnym momencie, może zabrać i przechowywać kopię X. W związku z tym, chociaż narzędzia i techniki, takie jak Vanish, mogą sprawić, że po pewnym czasie dane staną się nieodwracalne w ich własnym systemie, nie jest możliwe aby wymusić usunięcie danych po zobaczeniu ich przez złośliwego użytkownika. Jest to jedna z głównych zagadek zarządzania prawami cyfrowymi .

Dealer może wysłać t akcji, z których wszystkie są niezbędne do odzyskania pierwotnej tajemnicy, do jednego odbiorcy. Osoba atakująca musiałaby przechwycić wszystkie udziały , aby odzyskać tajemnicę, co jest zadaniem trudniejszym niż przechwycenie pojedynczego pliku, zwłaszcza jeśli udziały są wysyłane przy użyciu różnych mediów (np. niektóre przez Internet , niektóre wysyłane pocztą na płytach CD ).

W przypadku dużych sekretów bardziej wydajne może być zaszyfrowanie klucza tajnego, a następnie rozpowszechnienie klucza przy użyciu udostępniania klucza tajnego.

Tajne udostępnianie jest ważnym prymitywem w kilku protokołach służących do bezpiecznych obliczeń wielostronnych . Tajne udostępnianie może być również wykorzystywane do uwierzytelniania użytkowników w systemie.

Zobacz też

Linki zewnętrzne