W jaki sposób sól hasła pomaga w ataku na tęczowy stół?

220

Mam problem ze zrozumieniem celu hasła do hasła. Rozumiem, że podstawowym zastosowaniem jest powstrzymanie ataku na tęczowy stół. Jednak metody, które widziałem, aby to zaimplementować, nie utrudniają problemu.

Widziałem wiele samouczków sugerujących, że sól powinna być używana w następujący sposób:

$hash =  md5($salt.$password)

Powodem jest to, że skrót obecnie mapuje nie oryginalne hasło, ale kombinację hasła i soli. Ale powiedzieć, $salt=fooi $password=bari $hash=3858f62230ac3c915f300c664312c63f. Teraz ktoś ze stołem tęczowym może odwrócić skrót i wymyślić „foobar”. Następnie mogli wypróbować wszystkie kombinacje haseł (f, fo, foo, ... oobar, obar, bar, ar, ar). Otrzymanie hasła może potrwać kilka milisekund, ale niewiele więcej.

Innym zastosowaniem, które widziałem, jest mój system Linux. W / etc / shadow hashowane hasła są przechowywane razem z solą. Na przykład, sól „foo” i hasło „bar” byłoby hash do tego: $1$foo$te5SBM.7C25fFDu6bIRbX1. Jeśli haker zdołałby jakoś zdobyć ten plik, nie wiem, do czego służy sól, ponieważ te5SBM.7C25fFDu6bIRbXwiadomo , że zwrotny skrót zawiera „foo”.

Dzięki za każde światło, które każdy może rzucić na to.

EDYCJA : Dzięki za pomoc. Podsumowując to, co rozumiem, sól sprawia, że ​​zaszyfrowane hasło jest bardziej złożone, przez co znacznie mniej prawdopodobne jest, że będzie ono istniało we wstępnie obliczonej tabeli tęczy. To, co wcześniej źle zrozumiałem, to to, że zakładałem, że istnieje stół tęczy dla WSZYSTKICH skrótów.

Bogaty
źródło
Również zaktualizowane tutaj - używanie skrótu md5 nie jest już najlepszą praktyką. stackoverflow.com/questions/12724935/salt-and-passwords
StuartLC
Dzięki za edycję. Miałem te same wątpliwości, które zostały wyjaśnione. Tak więc sedno „Soli” naprawdę sprawia, że ​​bardzo mało prawdopodobne jest, aby tablica Rainbow zawierała hash sfałszowanego (solonego) hasła. : D
Vaibhav

Odpowiedzi:

237

Sól publiczna nie utrudni ataków słownikowych podczas łamania jednego hasła. Jak już zauważyłeś, atakujący ma dostęp zarówno do haszowanego hasła, jak i do soli, więc podczas uruchamiania ataku słownikowego może po prostu użyć znanej soli, gdy próbuje złamać hasło.

Sól publiczna robi dwie rzeczy: sprawia, że ​​złamanie dużej listy haseł zajmuje więcej czasu i sprawia, że ​​korzystanie z tęczowej tabeli jest niewykonalne.

Aby zrozumieć pierwszy, wyobraź sobie pojedynczy plik haseł, który zawiera setki nazw użytkowników i haseł. Bez soli mógłbym obliczyć „md5 (próba [0])”, a następnie zeskanować plik, aby sprawdzić, czy ten skrót się gdziekolwiek pojawi. Jeśli sole są obecne, muszę obliczyć „md5 (sól [a]. Próba [0])”, porównać z wpisem A, a następnie „md5 (sól [b]. Próba [0])”, porównać z wpisem B itd. Teraz mam ntyle czasu do zrobienia, gdzie njest liczba nazw użytkowników i haseł zawartych w pliku.

Aby zrozumieć drugi, musisz zrozumieć, czym jest tęczowy stół. Tęczowa tabela to duża lista wstępnie obliczonych skrótów dla często używanych haseł. Wyobraź sobie ponownie plik hasła bez soli. Wszystko, co muszę zrobić, to przejść przez każdą linię pliku, wyciągnąć zaszyfrowane hasło i sprawdzić je w tęczowej tabeli. Nigdy nie muszę obliczać pojedynczego skrótu. Jeśli wyszukiwanie jest znacznie szybsze niż funkcja skrótu (którą prawdopodobnie jest), znacznie przyspieszy to pękanie pliku.

Ale jeśli plik haseł zostanie zasolony, wówczas tablica tęczy będzie musiała zawierać wstępnie „hasłem. Hasło”. Jeśli sól jest wystarczająco losowa, jest to bardzo mało prawdopodobne. Prawdopodobnie będę mieć takie rzeczy jak „hello” i „foobar” i „qwerty” na mojej liście często używanych, wstępnie zaszyfrowanych haseł (tabela tęczy), ale nie będę mieć takich rzeczy jak „jX95psDZhello” lub Obliczono wstępnie „LPgB0sdgxfoobar” lub „dZVUABJtqwerty”. To sprawiłoby, że tęczowy stół byłby zbyt duży.

Zatem sól redukuje atakującego z powrotem do jednego obliczenia na wiersz na próbę, co w połączeniu z wystarczająco długim, wystarczająco losowym hasłem jest (ogólnie mówiąc) niemożliwe do złamania.

Ross
źródło
15
Nie jestem pewien, co powiedziałem w mojej odpowiedzi, aby zasugerować, że tak było?
Ross
2
erickson, myślę, że edycja była myląca - nie sądzę, że większość ludzi uważa atak na tęczową tabelę za rodzaj ataku słownikowego. Daj mi znać, jeśli w mojej odpowiedzi jest coś konkretnego, co może być mylące, a ja postaram się to poprawić.
Ross,
Chciałbym dać więcej niż jeden głos! Zwłaszcza w przypadku pierwszego akapitu. To wszystko podsumowuje IMHO
Cesar
5
Wiem, że to stare, ale twój opis tęczowych tabel jest niepoprawny. Zamiast tego opisujesz tabele skrótów. Na stole tęczy zobaczyć security.stackexchange.com/questions/379/... . Tabela skrótów ma od 1 do 1 mapowania haseł na skróty (jak opisano), ale tabele tęczy wymagają funkcji redukującej, która przekształca skrót z powrotem na tekst jawny, a następnie tysiące razy przechowuje ponownie, przechowując tylko początkowy tekst jawny i końcowy skrót. Wyszukiwanie jest obliczeniowo dłuższe niż tabele skrótów, ale „przechwytuje” wiele tekstów jawnych na skrót.
Mark Fisher
1
W tej odpowiedzi pomija się fakt, że nieużywanie soli (związane z tworzeniem skrótu hasła dla określonego użytkownika) również ujawnia zduplikowane hasła, nawet w wielu tabelach przechowujących te hasła. Przynajmniej będziesz w stanie zidentyfikować hasła ponownie wykorzystane przez daną osobę, ale co gorsza, możesz również zidentyfikować hasła używane przez różne osoby w różnych bazach danych.
Maarten Bodewes
119

Inne odpowiedzi wydają się nie uwzględniać twoich nieporozumień w temacie, więc oto:

Dwa różne zastosowania soli

Widziałem wiele samouczków sugerujących, że sól powinna być używana w następujący sposób:

$hash = md5($salt.$password)

[...]

Innym zastosowaniem, które widziałem, jest mój system Linux. W / etc / shadow hashowane hasła są przechowywane razem z solą.

Ty zawsze masz do przechowywania soli z hasłem, ponieważ w celu sprawdzenia, co użytkownik wszedł przeciwko bazy danych hasłem, trzeba połączyć wejście z solą, hash go i porównać go do przechowywanej hash.

Bezpieczeństwo skrótu

Teraz ktoś ze stołem tęczowym może odwrócić skrót i wymyślić „foobar”.

[...]

ponieważ wiadomo, że skrót mieszający te5SBM.7C25fFDu6bIRbX zawiera „foo”.

Nie można odwrócić skrótu jako takiego (przynajmniej teoretycznie). Hash „foo” i hash „saltfoo” nie mają ze sobą nic wspólnego. Zmiana choćby jednego bitu na wejściu funkcji skrótu kryptograficznego powinna całkowicie zmienić wynik.

Oznacza to, że nie możesz zbudować tęczowej tabeli ze zwykłymi hasłami, a następnie „zaktualizować” ją odrobiną soli. Sól musisz wziąć pod uwagę od samego początku.

To jest właśnie powód, dla którego potrzebujesz stołu tęczowego. Ponieważ nie można dostać się do hasła z skrótu, należy wstępnie obliczyć wszystkie skróty najczęściej używanych haseł, a następnie porównać je z ich skrótami.

Jakość soli

Ale powiedz $salt=foo

„foo” byłoby wyjątkowo złym wyborem soli. Zwykle użyłbyś wartości losowej, zakodowanej w ASCII.

Ponadto każde hasło ma własną sól, inną (miejmy nadzieję) od wszystkich innych soli w systemie. Oznacza to, że atakujący musi atakować każde hasło osobno, zamiast mieć nadzieję, że jeden z skrótów będzie pasował do jednej z wartości w jej bazie danych.

Atak

Jeśli haker zdołałby jakoś zdobyć ten plik, nie wiem, do czego służy sól,

Atak na tęczową tabelę zawsze potrzebuje /etc/passwd(lub jakiejkolwiek bazy danych haseł), a jak byś porównał skróty w tablicy tęczy do skrótów rzeczywistych haseł?

Jeśli chodzi o cel: powiedzmy, że atakujący chce zbudować tęczową tabelę dla 100 000 powszechnie używanych angielskich słów i typowych haseł (myśl „sekret”). Bez soli musiałaby obliczyć 100 000 skrótów. Nawet z tradycyjną solą UNIX złożoną z 2 znaków (każda z nich jest jedną z 64 opcji [a–zA–Z0–9./]:) musiałaby obliczyć i zapisać 4 096 000 000 skrótów ... to znaczna poprawa.

Społeczność
źródło
2
Naprawdę miła odpowiedź. Pomogło mi to zrozumieć wszystko o wiele lepiej. +1
wcm
Jeśli haker miał dostęp do soli i sposobu jej użycia w funkcji haszującej, czy nie mógł po prostu użyć jej do wygenerowania tabeli solonych skrótów i porównania tych skrótów z tabelą tęczy?
Jonny,
5
@Jonny nie ma „soli”. Chodzi o to, że sól jest inna dla każdego hasła.
86

Pomysł z solą polega na tym, że trudniej jest zgadnąć z brutalną siłą niż normalne hasło oparte na znakach. Tęczowe stoły są często budowane z myślą o specjalnych znakach i nie zawsze zawierają wszystkie możliwe kombinacje (choć mogą).

Tak więc dobrą wartością soli byłaby losowa liczba całkowita 128-bitowa lub dłuższa. To powoduje, że ataki na tęczowy stół zawodzą. Używając innej wartości soli dla każdego przechowywanego hasła, zapewniasz również, że tablica tęczy zbudowana dla jednej konkretnej wartości soli (jak w przypadku popularnego systemu z jedną wartością soli) nie daje dostępu do wszystkich hasła na raz.

Carl Seleborg
źródło
1
+1: Sól może być częścią skrótu szesnastkowego jakiegoś losowego ciągu zbudowanego przez generator liczb losowych. Każdy bit jest losowy.
S.Lott,
5
„Tęczowe tabele to jedna z form ataku słownikowego, która rezygnuje z pewnej prędkości, aby zaoszczędzić miejsce na dysku”. - wręcz przeciwnie, dobry tęczowy stół może przejąć GB do przechowywania, aby zaoszczędzić czas, zmieniając wszystkie możliwe wartości.
AviD
2
Zgadzam się - @erickson, myślę, że twoja edycja jest tam błędna. Tęczowy stół wymaga ogromnej ilości miejsca, ale pozwala szybko uzyskać komunikat za skrótem.
Carl Seleborg,
3
Cóż, oboje macie rację. W porównaniu ze standardowym atakiem słownikowym tabele tęczy poświęcają szybkość, aby zaoszczędzić miejsce. Z drugiej strony, w porównaniu z atakiem brutalnej siły, tablice tęczy zużywają (dużo) miejsca na zwiększenie prędkości. Dzisiaj tęczowe tablice są niemal synonimem słownika ...
Rasmus Faber
... ataki, ale nie potrzebujesz tabel tęczy do ataków słownikowych.
Rasmus Faber
35

Kolejne świetne pytanie, z wieloma bardzo przemyślanymi odpowiedziami - +1 do SO!

Jedną drobną kwestią, o której wyraźnie nie wspomniałem, jest to, że dodając losową sól do każdego hasła, praktycznie gwarantujesz, że dwóch użytkowników, którzy wybrali to samo hasło, utworzą różne skróty.

Dlaczego to jest ważne?

Wyobraź sobie bazę danych haseł w dużej firmie programistycznej w północno-zachodnich Stanach Zjednoczonych. Załóżmy, że zawiera on 30 000 wpisów, z których 500 ma niebieskie hasło . Załóżmy ponadto, że hakerowi udało się uzyskać to hasło, powiedzmy, czytając je w wiadomości e-mail od użytkownika do działu IT. Jeśli hasła są niesolone, haker może znaleźć zaszyfrowaną wartość w bazie danych, a następnie po prostu dopasować ją do wzorca, aby uzyskać dostęp do pozostałych 499 kont.

Solenie haseł gwarantuje, że każde z 500 kont ma unikalne (sól + hasło), generując inny skrót dla każdego z nich, a tym samym zmniejszając ryzyko naruszenia jednego konta. I miejmy nadzieję, że z dużym prawdopodobieństwem każdy użytkownik wystarczająco naiwny, aby napisać hasło w postaci zwykłego tekstu w wiadomości e-mail, nie ma dostępu do nieudokumentowanego interfejsu API dla następnego systemu operacyjnego.

Adam Liss
źródło
To samo dotyczy dwóch użytkowników, którzy wybrali inne hasło, i jest prawdopodobne, że mają one takie samo hasło hash zapisane w bazie danych. (Bezużyteczne ... wiem)
Ant
15

Szukałem dobrej metody nakładania soli i znalazłem ten znakomity artykuł z przykładowym kodem:

http://crackstation.net/hashing-security.htm

Autor zaleca używanie losowych soli na użytkownika, aby dostęp do soli nie sprawił, że cała lista skrótów będzie tak łatwa do złamania.

Aby zapisać hasło:

  • Wygeneruj długą losową sól za pomocą CSPRNG.
  • Dodaj sól do hasła i haszuj ją za pomocą standardowej funkcji haszującej kryptograficznej, takiej jak SHA256.
  • Zapisz zarówno sól, jak i skrót w rekordzie bazy danych użytkownika.

Aby zweryfikować hasło:

  • Pobierz sól i skrót użytkownika z bazy danych.
  • Dodaj sól do podanego hasła i haszuj ją za pomocą tej samej funkcji haszującej.
  • Porównaj skrót danego hasła z skrótem z bazy danych. Jeśli są zgodne, hasło jest prawidłowe. W przeciwnym razie hasło jest nieprawidłowe.
MytyMyky
źródło
3
Hashcat może wypróbować prawie 17 miliardów solonych skrótów SHA256 na sekundę przy użyciu jednego komputera. Autor powiązanego artykułu mówi o tym pod nagłówkiem „Utrudnianie łamania haseł: funkcje powolnego mieszania”. scrypt, bcrypt i PBKDF2 to dobry wybór i więcej niż warte dodatkowych cykli procesora na serwerze IMHO. Argon2 jest obecnie najnowocześniejszy, ale nie tak przetestowany w walce, jak inne.
kgriffs,
12

Powodem, dla którego sól może zawieść atak tabeli tęczy, jest to, że dla n-bitów soli, tabela tęczy musi być 2 ^ n razy większa niż rozmiar tabeli bez soli.

Twój przykład użycia „foo” jako soli może zwiększyć tęczowy stół 16 milionów razy większy.

Biorąc pod uwagę przykład Carl 128-bitowej soli, powoduje to, że stół jest 2 ^ 128 razy większy - teraz jest duży - lub inaczej: ile czasu zanim ktoś ma tak duże przenośne miejsce do przechowywania?

quamrana
źródło
8
Nawet jeśli użyjesz jednego elektronu do przechowywania trochę, upłynie sporo czasu, zanim ktokolwiek stworzy przenośną pamięć o takiej pojemności ... chyba że weźmiesz pod uwagę ruch Słońca w galaktyce.
erickson
10

Większość metod przełamywania szyfrowania opartego na haszowaniu polega na atakach siłowych. Atak tęczy jest zasadniczo bardziej wydajnym atakiem słownikowym, ma na celu wykorzystanie niskiego kosztu pamięci cyfrowej, aby umożliwić stworzenie mapy znacznego podzbioru możliwych haseł do skrótów i ułatwić odwrotne mapowanie. Ten rodzaj ataku działa, ponieważ wiele haseł jest albo dość krótkich, albo używa jednego z kilku wzorów formatów opartych na słowach.

Takie ataki są nieskuteczne w przypadku, gdy hasła zawierają znacznie więcej znaków i nie są zgodne z popularnymi formatami opartymi na słowach. Użytkownik z silnym hasłem na początek nie będzie podatny na ten styl ataku. Niestety wiele osób nie wybiera dobrych haseł. Ale istnieje kompromis, możesz poprawić hasło użytkownika, dodając do niego losowe śmieci. Więc teraz zamiast „hunter2” ich hasło może stać się efektywnie „hunter2908! Fld2R75 {R7 /; 508PEzoz ^ U430”, co jest znacznie silniejszym hasłem. Ponieważ jednak musisz teraz przechowywać ten dodatkowy element hasła, zmniejsza to skuteczność silniejszego hasła złożonego. Jak się okazuje, taki program wciąż przynosi korzyści netto, ponieważ teraz każde hasło, nawet słabe, nie są już wrażliwe na ten sam wstępnie obliczony stół mieszający / tęczowy. Zamiast tego każdy wpis skrótu hasła jest wrażliwy tylko na unikalną tabelę skrótu.

Załóżmy, że masz witrynę o słabych wymaganiach dotyczących siły hasła. Jeśli nie użyjesz żadnej soli do hasła, wszystkie skróty są podatne na wstępnie obliczone tabele skrótów, więc ktoś z dostępem do twoich skrótów będzie miał dostęp do haseł dla znacznego odsetka użytkowników (jednak wielu z nich używa haseł narażonych na atak, znaczny procent). Jeśli używasz stałej soli hasła, wówczas wstępnie obliczone tabele skrótów nie są już cenne, więc ktoś musiałby poświęcić czas na obliczenie niestandardowej tabeli skrótów dla tej soli, ale mógł to zrobić stopniowo, obliczając tabele, które obejmują coraz większe permutacje przestrzeni problemowej. Hasła najbardziej wrażliwe (np. Proste hasła oparte na słowach, bardzo krótkie hasła alfanumeryczne) byłyby łamane w ciągu godzin lub dni, hasła mniej wrażliwe byłyby łamane po kilku tygodniach lub miesiącach. Z biegiem czasu atakujący zyskuje dostęp do haseł dla stale rosnącego odsetka użytkowników. Jeśli użyjesz unikalnej soli dla każdego hasła, uzyskanie dostępu do każdego z tych haseł zajmie dni lub miesiące.

Jak widać, kiedy przechodzisz od braku soli do stałej soli do wyjątkowej soli, narzucasz kilka rzędów wielkości wysiłku w celu złamania wrażliwych haseł na każdym kroku. Bez soli najsłabsze hasła użytkowników są trywialnie dostępne, przy stałej soli te słabe hasła są dostępne dla określonego atakującego, a przy unikalnej soli koszt dostępu do haseł jest tak wysoki, że tylko najbardziej zdeterminowany atakujący może uzyskać dostęp do niewielkiej części wrażliwych haseł, a potem tylko kosztem.

Taka właśnie jest sytuacja. Nigdy nie możesz w pełni zabezpieczyć użytkowników przed złym wyborem hasła, ale możesz podnieść koszt złamania haseł użytkowników do poziomu, który sprawia, że ​​złamanie hasła nawet jednego użytkownika jest zbyt drogie.

Klin
źródło
3

Jednym z celów solenia jest pokonanie wstępnie obliczonych tabel skrótów. Jeśli ktoś ma listę milionów wstępnie obliczonych skrótów, nie będzie w stanie wyszukać 1 $ foo $ te5SBM.7C25fFDu6bIRbX1 w swojej tabeli, nawet jeśli zna skrót i sól. Nadal będą musieli brutalnie to zmusić.

Kolejnym celem, jak wspomina Carl S, jest sprawienie, by brutalne zmuszanie listy skrótów było droższe. (daj im wszystkie różne sole)

Oba te cele są nadal osiągane, nawet jeśli sole są publiczne.

rekurencyjny
źródło
1

O ile mi wiadomo, sól ma za zadanie utrudnić ataki słownikowe.

Jest to znany fakt, że wiele osób używa zwykłych słów do haseł zamiast pozornie przypadkowych ciągów.

Haker mógłby więc wykorzystać to na swoją korzyść zamiast brutalnej siły. Nie będzie szukał haseł takich jak aaa, aab, aac ... ale zamiast tego użyje słów i wspólnych haseł (jak imiona władcy pierścieni!;))

Więc jeśli moim hasłem jest Legolas, haker mógłby spróbować tego i odgadnąć za pomocą „kilku” prób. Jeśli jednak słonimy hasło i stanie się ono fooLegolas, skrót będzie inny, więc atak słownikowy zakończy się niepowodzeniem.

Mam nadzieję, że to pomaga!

rgargente
źródło
-2

Zakładam, że używasz funkcji PHP --- md5 (), a zmienne poprzedzone $ --- możesz spróbować poszukać tego artykułu Shadow Password HOWTO Specjalnie 11 akapit.

Ponadto, boisz się używając skrótu wiadomości algorytmy, można spróbować prawdziwych algorytmy szyfr, takie jak te przewidziane przez mcrypt modułu lub silniejsze Message Digest algorytmów, takich jak te, które zapewniają Mhash moduł (SHA1, SHA256 i inne).

Myślę, że silniejszy algorytm podsumowania wiadomości jest koniecznością. Wiadomo, że MD5 i SHA1 mają problemy z kolizją.

Daniel
źródło