Lira2

Lyra2 to schemat mieszania haseł (PHS), który może również działać jako funkcja wyprowadzania klucza (KDF). Otrzymała ona specjalne wyróżnienie podczas Konkursu Hasła Hashującego w lipcu 2015 roku, który wygrała firma Argon2 . Oprócz tego, że jest używany do swoich pierwotnych celów, jest również rdzeniem algorytmów proof-of-work, takich jak Lyra2REv2, przyjętych przez Vertcoin, MonaCoin, między innymi kryptowaluty Lyra2 została zaprojektowana przez Marcosa A. Simplicio Jr., Leonardo C. Almeida, Ewerton R. Andrade, Paulo CF dos Santos i Paulo SLM Barreto z Escola Politécnica da Universidade de São Paulo . Jest to ulepszenie w stosunku do Lyry, proponowanej wcześniej przez tych samych autorów. Lyra2 zachowuje bezpieczeństwo, wydajność i elastyczność swojego poprzednika, w tym: (1) możliwość skonfigurowania żądanej ilości pamięci, czasu przetwarzania i równoległości do wykorzystania przez algorytm; oraz (2) zdolność zapewniania wysokiego wykorzystania pamięci przy czasie przetwarzania podobnym do uzyskiwanego za pomocą skryptu . Ponadto wprowadza następujące ulepszenia w porównaniu do swojego poprzednika:

pozwala na wyższy poziom bezpieczeństwa przed miejscami ataków obejmującymi kompromisy w zakresie czasu i pamięci
pozwala uprawnionym użytkownikom na bardziej efektywne korzystanie z możliwości równoległości ich własnych platform
zawiera poprawki zwiększające koszty związane z budową dedykowanego sprzętu do ataku na algorytm
równoważy odporność na zagrożenia z kanału bocznego i ataki oparte na tańszych, a więc wolniejszych urządzeniach pamięci masowej
Lyra2 jest udostępniana w domenie publicznej i zawiera dwa główne rozszerzenia:
Lyra2-δ, daje użytkownikowi lepszą kontrolę nad wykorzystaniem pasma przez algorytm
Lyra2 p wykorzystuje możliwości równoległości na platformie uprawnionego użytkownika

Algorytm ten umożliwia parametryzację pod kątem:

czas wykonania (koszt czasu ${\ displaystyle T}$ )
$do$ pamięć (liczba wierszy $i$ liczba )
stopień równoległości (liczba wątków ${\ displaystyle p}$ )
podstawowa funkcja permutacji (może być postrzegana jako główny prymityw kryptograficzny)
liczba bloków używanych przez podstawową funkcję permutacji ( szybkość transmisji )
liczba rund wykonanych dla podstawowej funkcji $)$ (
$)$ bitów do wykorzystania w obrotach (
długość wyjściowa ( ${\ Displaystyle \ kappa}$ )

Silne strony

Główne mocne strony algorytmu to:

Wysoka odporność na kompromisy dotyczące pamięci przetwarzania: szacowane koszty przetwarzania ataków z niskim zużyciem pamięci obejmują czynnik, który rośnie wykładniczo wraz z kosztem czasu z powodu ponownych obliczeń
Koszty pamięci i czasu można oddzielić, co pozwala na precyzyjne dostosowanie wykorzystania zasobów
Szybki dzięki zastosowaniu w rdzeniu algorytmu funkcji gąbki o zredukowanej okrągłej gąbce
Może dostarczać dane wyjściowe o dowolnej długości, zachowując się jak funkcja wyprowadzania klucza (KDF)
Projekt łączy w sobie odporność na ataki typu side-channel (podczas całej fazy konfiguracji) oraz na ataki z udziałem tanich (a więc wolnoobrotowych) urządzeń pamięciowych , mając na celu zrównoważenie takich sprzecznych wymagań
Uwzględnia szeroki zakres konfiguracji ochrony przed atakami na platformy przy jednoczesnej optymalizacji wykonywania na legalnej platformie, takich jak:
- Wsparcie dla równoległości, dla platform wielordzeniowych , bez dawania większej przewagi atakom opartym na GPU
- Możliwość korzystania z różnych podstawowych funkcji gąbki w zależności od platformy docelowej (np. BLAKE2b dla implementacji oprogramowania; Keccak dla implementacji sprzętu; BlaMka dla dodatkowej odporności na platformy sprzętowe itp.)
- Możliwość zwiększenia wykorzystania przepustowości pamięci przez algorytm (uwaga: oczekuje się, że oryginalna specyfikacja maksymalizuje przepustowość w obecnych komputerach, ale funkcja może być przydatna w przyszłym sprzęcie)

Projekt

Jak każdy PHS, Lyra2 przyjmuje jako dane wejściowe sól i hasło , tworząc pseudolosowe dane wyjściowe, które można następnie wykorzystać jako kluczowy materiał dla algorytmów kryptograficznych lub jako ciąg uwierzytelniający . ^{[ nieudana weryfikacja ]}^{[ potrzebne źródło ]}

Wewnętrznie pamięć schematu jest zorganizowana jako macierz, która powinna pozostać w pamięci podczas całego procesu mieszania hasła: ponieważ jej komórki są iteracyjnie odczytywane i zapisywane, odrzucanie komórki w celu oszczędzania pamięci prowadzi do konieczności jej ponownego obliczania za każdym razem, gdy jest dostępna jeszcze raz, aż do momentu ostatniej modyfikacji.

Konstruowanie i odwiedzanie matrycy odbywa się za pomocą stanowej kombinacji operacji pochłaniania, ściskania i dupleksu leżącej pod spodem gąbki ( tj. jej stan wewnętrzny nigdy nie jest resetowany do zera), zapewniając sekwencyjny charakter całego procesu.

Ponadto użytkownik określa, ile razy komórki macierzy są ponownie odwiedzane po inicjalizacji, co pozwala dostosować czas wykonania Lyra2 do zasobów platformy docelowej.

Funkcje/symbole

|| Połącz dwa łańcuchy ^ Bitowo XOR [+] Operacja dodawania słownego (tj. ignorowanie przenoszenia między słowami) % Moduł W Rozmiar słowa maszyny docelowej (zwykle 32 lub 64) omega Liczba bitów używanych w rotacjach (zalecane: wielokrotność rozmiar słowa maszyny, W) >>> obrót w prawo rho Liczba rund dla zredukowanych operacji wyciskania lub dupleksu blen Rozmiar bloku Sponge'a w bajtach H lub H_i Sponge o rozmiarze bloku blen (w bajtach) i permutacji bazowej f H.absorb(input) Operacja pochłaniania Sponge'a na wejściu H.squeeze(len) Operacja ściskania Sponge'a na len bajtach H.squeeze_{rho}(len) Operacja ściskania Sponge'a na len bajtów przy użyciu rho rund f H.duplexing(input,len) Operacja dupleksu Sponge'a na wejściu , wytwarzając len bajtów H.duplexing_{rho}(input,len) Operacja dupleksu Sponge'a na wejściu, używając rho rund f, wytwarzając len bajtów pad(string) Dopasowuje łańcuch do wielokrotności blen bajtów (reguła dopełnienia: 10*1 ) lsw(input) Najmniej znaczące słowo wejścia len(string) Długość łańcucha, w bajtach syncThreads() Synchronizacja wątków równoległych swap(input1,input2) Zamień wartość dwóch wejść C Liczba kolumn na macierzy pamięci (zwykle , 64, 128, 256, 512 lub 1024) P Stopień równoległości (P >= 1 i (m_koszt/2) % P = 0)

Wejścia

hasło
sól
t_koszt
m_koszt
outlen

Algorytm bez równoległości

** Faza ładowania początkowego: inicjuje stan gąbki i zmienne lokalne # Reprezentacja bajtów parametrów wejściowych (inne można dodać) params = outlen || len(hasło) || len(sól) || t_koszt || m_koszt || C # Inicjuje stan gąbki (potem hasło może zostać nadpisane) H.absorb( pad(hasło || salt || params) ) # Inicjuje krok wizyty, okno i pierwsze wiersze, które będą zasilać gap = 1 stp = 1 wnd = 2 sqrt = 2 prev0 = 2 row1 = 1 prev1 = 0 ** Faza konfiguracji: Inicjuje macierz pamięci (m_cost x C), której komórki mają komórki o szerokości jednego bajtu # Inicjalizuje M[0], M[1] i M[2 ] dla col = 0 do C-1 M[0][C-1-col] = H.squeeze_{rho}(blen) for col = 0 to C-1 M[1][C-1-col] = H.duplexing_{rho}( M[0][col], blen) for col = 0 to C-1 M[2][C-1-col] = H.duplexing_{rho}( M[1][col ], blen) # Filling Loop: inicjuje pozostałe wiersze dla row0 = 3 do m_cost-1 # Columns Loop: M[wiersz0] jest inicjowany i M[wiersz1] jest aktualizowany dla col = 0 do C-1 rand = H.duplexing_{ rho}( M[wiersz1][kolumna] [+] M[poprzednia0][kolumna] [+] M[poprzednia1][kolumna], mieszana) M[wiersz0][C-1-kolumna] = M[poprzednia0][ col] ^ rand M[wiersz1][kol] = M[wiersz1][kol] ^ ( rand >>> omega ) # Wiersze do ponownego odwiedzenia w następnej pętli prev0 = wiersz0 prev1 = wiersz1 wiersz1 = (wiersz1 + stp) % wnd # Okno w pełni ponownie odwiedzane, jeśli (wiersz1 = 0) # Podwaja okno i dostosowuje krok wnd = 2 * wnd stp = sqrt + gap gap = -gap # Podwaja sqrt co drugą iterację, jeśli (gap = -1) sqrt = 2 * sqrt ** Faza wędrówki: iteracyjne nadpisywanie pseudolosowych komórek macierzy pamięci ) % m_cost row1 = lsw( rand >>> omega ) % m_cost # Columns Loop: aktualizuje zarówno M[wiersz0] jak i M[wiersz1] dla col = 0 do C-1 # Wybiera pseudolosowe kolumny col0 = lsw( ( rand >> > omega ) >>> omega ) % C col1 = lsw( ( ( rand >>> omega ) >>> omega ) >>> omega ) % C rand = H.duplexing_{rho}( M[wiersz0][kolumna] [+] M[wiersz1][kolumna] [+] M[poprzednia0][kol0] [+] M[poprzednia1][kolumna1], mieszana) M[wiersz0][kolumna] = M[wiersz0][kolumna] ^ rand M[row1][col] = M[row1][col] ^ ( rand >>> omega ) # Następna iteracja ponownie odwiedza ostatnio zaktualizowane wiersze prev0 = row0 prev1 = row1 ** Faza podsumowania: obliczenia wyjściowe # Absorbuje ostateczną kolumna z okrągłą gąbką H.absorb( M[row0][0] ) # Wyciska outlen bity z pełnookrągłym wyjściem gąbki = H.squeeze(outlen) # Udostępnia outlen-long bitstring jako wyjście return output

Algorytm z równoległością

dla każdego i w [0..P] ** Faza ładowania początkowego: Inicjuje stan gąbki i zmienne lokalne # Reprezentacja bajtów parametrów wejściowych (inne można dodać) params = outlen || len(hasło) || len(sól) || t_koszt || m_koszt || C || P || i # Inicjuje stan gąbki (potem hasło może zostać nadpisane) H_i.absorb( pad(hasło || salt || params) ) # Inicjuje krok wizyty, okno i pierwsze wiersze, które będą zasilać gap = 1 stp = 1 wnd = 2 sqrt = 2 sync = 4 j = i prev0 = 2 rowP = 1 prevP = 0 ** Faza konfiguracji: Inicjuje macierz pamięci (m_cost x C), której komórki mają komórki o długości jednego bajtu # Inicjalizuje M_i[0], M_i[ 1] i M_i[2] dla col = 0 do C-1 M_i[0][C-1-col] = H_i.squeeze_{rho}(blen) dla col = 0 do C-1 M_i[1][C -1-col] = H_i.duplexing_{rho}( M_i[0][col], blen) for col = 0 to C-1 M_i[2][C-1-col] = H_i.duplexing_{rho}( M_i[1][col], blen) # Wypełnianie pętli: inicjuje pozostałe wiersze dla wiersza0 = 3 do ((m_cost / P) - 1) # Kolumny Pętla: M_i[wiersz0] jest inicjowany, a M_j[wiersz1] jest aktualizowany dla kol = 0 do C-1 rand = H_i.duplexing_{rho}( M_j[wierszP][kol] [+] M_i[prev0][kol] [+] M_j[prevP][kolumna], blen) M_i[wiersz0][ C-1-col] = M_i[prev0][col] ^ rand M_j[wierszP][col] = M_j[wierszP][col] ^ ( rand >>> omega ) # Wiersze do ponownego odwiedzenia w następnej pętli prev0 = row0 prevP = rowP rowP = (wierszP + stp) % wnd # Całkowite ponowne odwiedzenie okna if (rowP = 0) # Podwaja okno i dostosowuje krok wnd = 2 * wnd stp = sqrt + gap gap = -gap # Podwaja sqrt co drugą iterację if ( gap = -1) sqrt = 2 * sqrt # Punkt synchronizacji if (row0 = sync) sync = sync + (sqrt / 2) j = (j + 1) % P syncThreads() syncThreads() ** Faza wędrująca: nadpisuje iteracyjnie pseudolosowe komórki macierzy pamięci wnd = m_cost / (2 * P) sync = sqrt off0 = 0 offP = wnd # Pętla odwiedzin: (2 * m_cost * t_cost / P) ponownie odwiedzane wiersze w sposób pseudolosowy dla wCount = 0 do ( ( ( m_cost * t_cost) / P) - 1) # Wybiera pseudolosowe wiersze i wycinki (j) row0 = off0 + (lsw(rand) % wnd) rowP = offP + (lsw( rand >>> omega ) % wnd) j = lsw ( ( rand >>> omega ) >>> omega ) % P # Kolumny Pętla: aktualizacja M_i[wiersz0] dla col = 0 do C-1 # Wybiera kolumnę pseudolosową col0 = lsw( ( ( rand >>> omega ) >> > omega ) >>> omega ) % C rand = H_i.duplexing_{rho}( M_i[row0][col] [+] M_i[prev0][col0] [+] M_j[rowP][col], blen) M_i [row0][col] = M_i[row0][col] ^ rand # Następna iteracja powraca do ostatnio zaktualizowanych wierszy prev0 = row0 # Punkt synchronizacji if (wCount = sync) sync = sync + sqrt swap(off0,offP) syncThreads() syncThreads() ** Faza końcowa: obliczenia wyjściowe # Pochłania ostatnią kolumnę za pomocą okrągłej gąbki H_i.absorb( M_i[row0][0] ) # Wyciska pozostałe bity za pomocą okrągłej gąbki output_i = H_i.squeeze (outlen) # Dostarcza ciąg bitów o długości outlen jako wyjście return output_0 ^ ... ^ output_{P-1}

Analiza bezpieczeństwa

${\ Displaystyle O (2 ^ {2nT} R ^ {3})}$ $ilość$ koszt przetwarzania ataków wykorzystujących pamięci wykorzystywanej przez uprawnionego i ${\ Displaystyle O (2 ^ {2nT} R ^ {n + 2})}$ , przy czym to drugie jest lepszym oszacowaniem dla ${\ Displaystyle n \ gg 1}$ zamiast ${\ Displaystyle O (R)}$ osiągniętego, gdy ilość pamięci wynosi ${\ Displaystyle O (R)}$ , gdzie $T$ to parametr zdefiniowany przez użytkownika do definiowania czasu przetwarzania.

To dobrze porównuje się do scrypt , który wyświetla koszt ${\ Displaystyle O (R ^ {2})}$ , gdy użycie pamięci wynosi ${\ Displaystyle O (1)}$ i innymi rozwiązaniami w literaturze, dla której wyniki są zwykle ${\ Displaystyle O (R ^ {T + 1})}$ .

$)$ jednak w praktyce rozwiązania te zwykle wiążą się z wartością (zużycia pamięci niższą niż te osiągane w Lyra2 dla tego samego czasu przetwarzania.

Wydajność

Wydajność Lyra2 z obsługą SSE, dla C = 256, ρ = 1, p = 1 i różnych ustawień T i R, w porównaniu z finalistami PHC z włączoną obsługą SSE i finalistami PHC z twardą pamięcią przy minimalnych parametrach.

Czas przetwarzania uzyskany przy jednordzeniowej implementacji SSE Lyra2 jest przedstawiony na poniższym rysunku. Ta liczba została wyodrębniona z testów porównawczych innych firm przeprowadzonych w kontekście PHC i jest bardzo podobna.

Przedstawione $_$ średniemu $($ $tj$ z _ stan wewnętrzny ma 256 bitów) oraz różne ustawienia i $R} , dające ogólne wyobrażenie$ $displaystyle$ możliwych kombinacjach parametrów i odpowiednim wykorzystaniu zasobów.

Jak pokazano na tym rysunku, Lyra2 jest w stanie wykonać w: mniej niż 1 s przy użyciu do 400 MB (z ${\ displaystyle R = 2 ^ {14}}$ i ${\ displaystyle T = 5 }$ ) lub do 1 GB pamięci (przy czym ${\ Displaystyle R \ około 4,2 \ cdot 10 ^ {4}}$ i ${\ Displaystyle T = 1}$ ); lub w mniej niż 5 s z 1,6 GB (z ${\ Displaystyle R = 2 ^ {16}}$ i ${\ Displaystyle T = 6}$ ).

Wszystkie testy przeprowadzono na procesorze Intel Xeon E5-2430 (2,20 GHz z 12 rdzeniami, 64 bity) wyposażonym w 48 GB pamięci DRAM , z systemem Ubuntu 14.04 LTS 64 bity, a kod źródłowy skompilowano przy użyciu gcc 4.9.2.

Linki zewnętrzne