Polskie Forum Bitcoin

Każdy system kryptograficzny można złamać...
Dlaczego my sądzimy, że SHA256 jest nie do złamania?
LINK:
http://apenwarr.ca/log/?m=201105#08



Jeśli SHA256 padnie to banki po prostu wyłączą na parę dni swoje systemy ONLINE i zmienią sposób szyfrowania.

A co zrobi Bitcoin?

Czekam na Wasze opinie

Jeśli jest pewien swej teorii, najwyższa pora wziąć się do pracy. Nietrudno zgadnąć, iż osoba, która pierwsza złamie szyfr, po puszczeniu takich fałszywych bitcoinów na rynek prawdopodobnie już nigdy do końca swych dni nie będzie musiała pracować. Nic prostrzego chyba więc.

vestas pisze:Każdy system kryptograficzny można złamać...
Dlaczego my sądzimy, że SHA256 jest nie do złamania?

Bitcoin to eksperyment. Nikt nie daje gwarancji, że jest pozbawiony wad projektowych i że będzie udany.

To powiedziawszy, takie rzeczy jak funkcje skrótu nie padają z dnia na dzień. Przeciwnie - zajmuje to raczej długie lata; historycznie mają tendencję do bardzo powolnego osłabiania się. Powinno być wystarczająco dużo czasu na zmianę funkcji skrótu używanej w klientach.

o, sam sir Kimono mnie uraczył odpowiedzią

mam coś jeszcze:
http://konradkubiec.com/rozwoj-osobisty ... ieniadzem/

ale przyznajcie się, nie czytaliście tego "wywodu" wcześniej?

qertoip pisze:takie rzeczy jak funkcje skrótu nie padają z dnia na dzień. Przeciwnie - zajmuje to raczej długie lata

Z tego co wiem to tak właśnie jest. Najpierw powstaja podejrzenia ze w jakis tam matematyczny sposob da sie to zrobic, potem dlugie miesiace testow a w miedzyczasie powstaje kolejna funkcja skrotu i zanim ktos zdolal wykorzystac funkcje podatna na atak to najwazniejsze systemy dzialaly jzu na nowej. W kazdej chwili w bitcoinie mozna sie przepiac na inna funkcje jesli taka powstanie.
Poza tym z tego co wiem wszelkie wady innych funkcji skrotu polegaja na mozliwosci wywolania kolizji, czyli podaniu takiego ciagu znakow, ktorego skrot jest taki sam jak skrot calego bloku w bitcoinie. Nikt chyba nie zlamal zadnej funkcji skrotu w takim sensie, ze potrafil poznac ciag znakow ktorego klucz wynikowy jest skrotem.
Czyli de facto nawet kiedy ktos bedzie potrafil wywolac kolizje sha256 to nie bedzie mogl poznac kluczy prywatnych z portfela i tym samym podpisac prawidlowo transakcji [?] Poprawcie sie jesli sie myle, nie mam dzisiaj glowy.

Kolejna sprawa to taka, ze jesli ktos namieszalby w blokach to mozna zrobic rollback

http://hacking.pl/pl/news-4727-SHA_1_zlamany.html

tutaj więcej o złamaniu SHA-1 oraz o kolizjach

aczkolwiek z tego co zauważyłem to nawet złamanie szyfru nie wyklucza jego zastosowania

pytanie tylko, czy w Klientach Bitcoin można w łatwy sposób przejść z SHA256 na jakiś nowy szyfr jak np BLAKE (jeden z kandydatów aby zostać nazwanym SHA-3)
http://en.wikipedia.org/wiki/BLAKE_%28hash_function%29
http://en.wikipedia.org/wiki/NIST_hash_ ... ompetition

"złamanie szyfru" to pojęcie względne, tutaj jest wszędzie mow atylko o kolizjach, ktore w niektorych systemach zabezpieczen sa nieistotne, nie wiem jak w bitcoinie.
Co do zastosowania nowej funkcji skrotu to mysle ze sie da, wystarczy podpisywac nowe bloki nowa funkcja i tyle, lub klienty po aktualizacji przepisaly by baze danych calkowicie przez nowa funkcje. Poza tym dam sobie palca uciac, ze Satoshi zdawal sobie sprawe z tego ze aktualizacja funkcji skrotu bedzie istotna i zapewne da sie to zrobic.
Mozna by w zasadzie zastosowac obie funkcje i wynikowe hashe sklejac razem jako wynik, wtedy chyba trzeba by zlamac obie aby cokolwiek namieszac.
Niech sie tu jakis ekspert wypowie

Sa nawet trendy zycia funkcji skrotu: http://valerieaurora.org/hash.html Z tego wynika, ze SHA-2 ma jeszcze wiele lat swietnosci, jest czas na update funkcji i klientow

jeżeli ktoś złamie SHA256 (np. złamie matematycznie) to na pewno nie będzie tego robił dla bitcoina. To, że będzie bogaty(z powodu BTC) mozna wsadziś sobie między bajki. Złamanie i okradzenie innych z BTC spowoduje tylko tyle na dzień dzisiejszy, że nikt tego od niego nie kupi i nikt nie będzie chciał przyjąc BTC jako płatności.

To czy SHA256 straci swe bezpieczeństwo czy nie, nie ulega wątpliwości...straci z czasem, bardziej własnie zaczął bym się zastanawiać jak szybko jest możliwość podmiany sposobu szyfrowania. Wbrew pozorom to nie jest tak hop siup.(albo coś przegapiam) Zatrzymać się tego nie da, da się ściągnąć nowego klienta, no ale co w styuacji kiedy jeszcze większość nie sciągnie, nowi nie będą mogli przecież już tworzyć transakcji. Przejście dla wszystkich musiało by być bardzo szybkie. Nie jest to takie łatwe do skoordynowania.(ale możliwe oczywiście)

Co do przejścia to wg. mnie należałoby wypuścić klienta który zawierałby obie funkcję starą i nową, a przejście na nowy algorytm odłożyć w czasie np. odczekać 1000 bloków

Myślę, że algorytm i tak trzeba będzie zmieniać od czasu do czasu, jeżeli bitcoin ma przetrwać próbę bezpieczeństwa (a przetrwać takową musi), choćby z uwagi na przyszłe ASICi (niekoniecznie dostępne dla wszystkich).
Jedna stacja, czy to prywatna czy rządowa, oparta o zaledwie 5000 takich średnio nawet wypasionych procków (40 pipelines taktowanych 1Gh) to 200 THash/s, czyli ponad 15x więcej, niż cała obecna moc sieci.

Dzsiejsze "łamanie" algorytmów kryptograficznych (jak SHA, MD5, czy RSA) polega w zasadzie na ujawnianiu jego słabości w jakims punkcie, co w rezultacie doprowadza do zmniejszenia czasu potrzebnego do "odszyfrowania" (albo odwrócenia skrótu). Takie zmnieszenia czasu są rzędu 5-50 razy, w stosunku do przeszukiwania wszystkich możliwych kombinacji.

SHA-256 ma złożoność czasową 2^256, ale znane ataki zmniejszyły tę złożoność do 2^250 (czyli 64 razy - ale policzcie sobie ile ma cyfr ta liczba...). Dopiero złożoność rzędu 2^128 (jak miało MD5) zapewnia możliwość złamania konkretnego hasha po miesiącach obliczeń (powiedzmy że dniach, dla wielkich organizacji typu NSA czy rządy). Ale i to by nie złamało protokołu bitcoin, ponieważ hashe zmieniają się z każdym blokiem (czyli co ok 10 minut), a dodatkowo wszędzie SHA jest liczone dwa razy (czyli SHA z kolejnego SHA jest dopiero tym docelowym SHA), zatem moc potrzebna do złamania musiałaby być jeszcze dwukrotnie większa.

Wszystkie słabości w algorytmach wcześniej czy później są przedstawiane na konferencjach kryptograficznych. Zatem mozna szacować, o ile spada trudność złamania jakiegoś algorytmu. (BTW: na ostatniej konferencji pokazano "poważny" błąd w AESie, uznawanym za standard szyfrowania. Błąd zmniejsza złożoność czasową 8 krotnie. To tylko znak, że AESa trzeba będzie wymienić w ciągu... najbliższych 15 lat ).

Suma sumarum: kryptografia w tym systemie trzyma się świetnie, i to jest najmniejszy problem Bitcoina.

Rozmowa jest bez sensu jeżeli osoba która zaczyna pieprzyć takie głupoty nie pozna jak działa na prawdę protokół Bitcoin. Ale po kolei.

Po pierwsze, złamanie SHA-256 nie zaszkodzi bankowości online, bo ona z niego nie korzysta, korzysta z niego bitcoin. Bankowość online korzysta z TLS, czyli szyfrowania SSL dla protokołu HTTP. Jeżeli złamią klucze długości 2048bitów to banki przejdą na 2x dłuższe i tak będą ciągle przechodzić. A to, że stare algorytmy są już „złamane” to sprawa naturalna. Oprócz hakerów złamaniem zaczynają się zajmować również matematycy. Dochodzą do tego algorytmy probalistyczne oraz rozwój technologii. Jeszcze 2 lata temu cały brutal force był robiony za pomocą CPU, dzisiaj wiadomo, że GPU jest do tego lepszy i wydaje się że jest to wiedza powszechna.

Czy zmiana SHA-256 spowoduje złamanie Bitcoin? A czy złamanie MD5 spowodowało, że przestał być on stosowany w internecie? To, że w algorytmie znaleziono luki umożliwiające generować kolizje nie oznacza, że algorytm należy się pozbyć. Po pierwszym „pomyślnym” złamaniu SHA-256 minie jeszcze z 5 lat zanim algorytmy będą wystarczająco wydajne by móc tworzyć w efektywnym czasie kolizje.

Inna sprawa to to, że należy się zastanowić gdzie jest wykorzystywane SHA-256, a ma ono z tego co pamiętam tylko jedno zastosowanie. Podczas generowania nowych bloków musi on osiągać cel! A dokładniej być poniżej niego. Więc sama możliwość generowania dowolnych kolizji nam nic nie daje, bo my musimy wygenerować blok, którego SHA-256 jest poniżej określonej wartości. SHA-256 został specjalnie wybrany do tego celu, bo daje on w miarę losowe, ale przewidywalne wyniki. Więc można oszacować ile czasu jest potrzeba do wygenerowania odpowiedniej ilości bloków. Inna sprawa to to, że należy pamiętać, że nagłówek bloku ma określony format! Jedyne co można w nim modyfikować dowolnie to zmienną nonce! Więc jedyne co by nam się przydało to możliwość oszacowania jakiej wartości powinien być nonce, tak aby blok znalazł się poniżej celu, bez każdorazowego liczenia hasha! Jak dojdziemy do takiego złamania funkcji skrótu SHA-256 to bloki przestaną generować 50BTC nagrody, a pozostanie jedynie nagroda za wykonane transakcje. A wtedy takie algorytmy bardzo by się przydały.

Dlaczego nasze pieniądze są niezagrożone? A w jaki sposób wydajemy je? Przy pomocy transakcji. Co potrzebne jest do stworzenia transakcji? Priwatny klucz z naszego portfela! Co jeżeli klucz będzie za krótki w przyszłości? Nastąpi ta sama zasada co w wypadku bankowości online, czyli zostanie on zwiększony. Ale w zależności od długości klucza prywatnego zależy długość klucza publicznego, a na jego podstawie powstaje adres. Czy więc zwiększy się długość adresu? Na pewno nie, bo adres to odpowiednie złożenie wielu SHA-256 w odpowiedni sposób, a nawet jeżeli będzie konieczne przejść na dłuższe adresy to można po prostu zmienić początek adresu z 1 na np. 2, po to stworzono tą możliwość, aby można było wyróżnić adresy różnych sieci. Obrazek jak powstaje adres

Coś jeszcze?

@washuu: Funkcji skrótu nie da się nigdy odwrócić. Ale da się znaleźć obejścia, które albo ułatwiają zgadnąć co mogło się tam znaleźć lub ułatwić obliczenia.

zwierzak pisze: @washuu: Funkcji skrótu nie da się nigdy odwrócić. Ale da się znaleźć obejścia, które albo ułatwiają zgadnąć co mogło się tam znaleźć lub ułatwić obliczenia.

Wiadomo, że jest nieskończenie wiele wiadomości dających jeden konkretny i ten sam skrót. "Odwrócić" oznacza znaleźć dowolną z takich wiadomości, będącą zarazem sensowną w wykorzystaniu (np. do kolejnego bloku).

BTW: cały SSL/TLS opiera się bardzo mocno na RSA, który za to bazuje na trudności w rozkładaniu duzych liczb na iloraz liczb pierwszych (faktoryzacji). Jak do tej pory udało się rozłożyć liczbę 768-bitową, po wielu miesiącach rozproszonych obliczeń. Zatem jeżeli Bitcoin korzysta z RSA-2048, to wróżę mu lata spokoju.

washuu pisze:Wiadomo, że jest nieskończenie wiele wiadomości dających jeden konkretny i ten sam skrót. "Odwrócić" oznacza znaleźć dowolną z takich wiadomości, będącą zarazem sensowną w wykorzystaniu (np. do kolejnego bloku).

Tak, ale nas nie interesuje dowolna wiadomość, tylko konkretna wiadomość o konkretnym kształcie. A coś podejrzewam, że mając nawet tak rozpracowanego SHA256, że kolizję będziemy w stanie wygenerować w ciągu 2sec to nic nam nie da, skoro nie dopasuje się do dobrych danych. Inna sprawa, że przy takim stanie wiedzy będziemy w stanie spokojnie wyliczać, a nie zgadywać wartość nonce, który jest jedyną zmienną w tym równaniu.

washuu pisze:BTW: cały SSL/TLS opiera się bardzo mocno na RSA, który za to bazuje na trudności w rozkładaniu duzych liczb na iloraz liczb pierwszych (faktoryzacji). Jak do tej pory udało się rozłożyć liczbę 768-bitową, po wielu miesiącach rozproszonych obliczeń. Zatem jeżeli Bitcoin korzysta z RSA-2048, to wróżę mu lata spokoju.

Nie wiem jakiej jest wielkości klucz w Bitcoin. I z tego co pamiętam nie bazuje on na RSA, tylko algorytmie jemu pochodnemu. Co nie zmienia, że nikt nie wyda naszych pieniędzy bez naszej wiedzy.

washuu pisze: BTW: cały SSL/TLS opiera się bardzo mocno na RSA, który za to bazuje na trudności w rozkładaniu duzych liczb na iloraz liczb pierwszych (faktoryzacji). Jak do tej pory udało się rozłożyć liczbę 768-bitową, po wielu miesiącach rozproszonych obliczeń. Zatem jeżeli Bitcoin korzysta z RSA-2048, to wróżę mu lata spokoju.

Ja bym się nie martwił jak duża liczbę aktualnie rozłożyli i jaką w przyszłości będą technicznie w stanie obliczyć. Bardziej bał bym się tego, ze ktoś rozpracuje sama faktoryzacje. Oczywiście to nie jest problem samego BTC, ale wielu zabezpieczeń. Ale spokojnie, zawsze wymyślą coś lepszego . Dlatego jeżeli BTC będzie miało mechanizm(nie wiem czy taki ma) w miarę płynnego przechodzenia z jednego sposobu szyfrowania do innego. To w ogólnie nie ma większego problemu.

Kazik pisze:Bardziej bał bym się tego, ze ktoś rozpracuje sama faktoryzacje

Faktoryzacji nikomu nie udalo sie rozpracowac w przeszlosci dla zadnej z istniejacych funkcji skrotu, znajdywano jedynie bledy, ktore umozliwialy skrocenie czasu ataku brute force, jednak nie oznacza to "rozpracowania"

Faktoryzacja (rozkład liczb na czynniki pierwsze) i funkcje skrótu (mieszające) nie mają prawie nic wspólnego (no chyba że "kryptografia").

W faktoryzacji niewiele się zmienia od lat, algorytmy są tylko nieco poprawiane ale są te same od wielu lat. Jedyną szansą na jakiś przełom jest stworzenie jakiegoś sporego komputera kwantowego, i zastosowanie w nim algorytmu Shore'a (algorytmu znanego od lat 90tych).

Natomiast w funkcjach skrótu sporo się dzieje, znajdowane są kolejne "słabości", co kilka lat są konkursy na nowe standardy, etc.

Jedno i drugie w bitcoinie można będzie wymienić, wypuszczając klienta, który od któregoś tam bloku w przyszłości zacznie stosować nowe funkcje zamiast starych. Jedyny problem jest taki, że w momencie wygenerowania pierwszego bloku z nowym standardem znaczna większość klientów w sieci powinna to już obsługiwać, zatem czas na wymianę klientów powinien być możliwie duży. Ale, jak już było mówione, takie funkcje nie padają z dnia na dzień, tylko po prostu skraca się czas potrzebny na ich złamanie.

PS. Czy cały ten wątek nie powinien być raczej w dziale "Bezpieczeństwo", "Media", albo "Hyde-park"? ;-)

Zawsze można użyć Rainbow Tables, choć wiadomo, że przy takiej wielkości skrótu plik tablic byłby kolosalnie ciężki.

dublet pisze:Zawsze można użyć Rainbow Tables, choć wiadomo, że przy takiej wielkości skrótu plik tablic byłby kolosalnie ciężki.

Masz rację, że pliki tablic byłyby kolosalnie ciężkie - pliki dla HASEŁ dziesięcioznakowych ze znakami specjalnymi ważą gigabajty, a tu mamy kilobajty BINARNYCH danych.

Ale nie można ich użyć z jeszcze innego powodu. Rainbow Tables są dobre tylko do krótkich ciągów znakowych, takich jak hasła (wyszukiwanie w ciągach łańcuchów), a po za tym Rainbow Tables są statyczne, a w blokach co chwila zmienia się suma kontrolna (i w zasadzie cała reszta zawartości), nie wspominając o znacznikach czasu.

Zawsze mozna uzyc komputerow kwantowych lub magii albo skorzystac z pomocy inteligencji pozaziemskiej. Jest tylko taki problem, ze praktycznie to jest niemozliwe