funkcja haszujaca
-
- Użytkownik
- Posty: 852
- Rejestracja: 23 paź 2004, o 10:17
- Płeć: Mężczyzna
- Lokalizacja: Lublin
- Pomógł: 28 razy
funkcja haszujaca
witam
wlasnie tworze pewiem programik i potrzebuje w nim zastosowac funkcje haszujaca. cel podstawowy musi byc ona latwa do zaimplementowania przy uzyciu podstawowych operacji bitowych. dane wejsciowe beda rzedu 10 bajtow a na wyjsciu 4. mam w glowe pare takich funkcji lecz niestety nie spelniaja one wymagan dotyczacych asymetrycznosci a co za tym idzie kolizji.
bylbym wdzieczny za roznego rodzaju wskazowki
wlasnie tworze pewiem programik i potrzebuje w nim zastosowac funkcje haszujaca. cel podstawowy musi byc ona latwa do zaimplementowania przy uzyciu podstawowych operacji bitowych. dane wejsciowe beda rzedu 10 bajtow a na wyjsciu 4. mam w glowe pare takich funkcji lecz niestety nie spelniaja one wymagan dotyczacych asymetrycznosci a co za tym idzie kolizji.
bylbym wdzieczny za roznego rodzaju wskazowki
funkcja haszujaca
pierwsze primo:
Zapewne tak sobie przetłumaczyłeś angielskie 'hash function'.
Tylko że po polsku, w zależności od kontekstu, używa się terminów 'funkcja mieszająca' lub 'funkcja skrótu'. To są różne rzeczy, niestety. Wnioskując z całości twojego postu, chodzi ci o funkcję skrótu. Trzymaj się tego, bo taka jest Polska Norma w tej dziedzinie.
(Musiałem umieścić tę uwagę, bo niesamowicie irytują mnie podobne pseudoterminy.)
drugie primo:
No ale może w jakimś stopniu to ci pomoże:
A co to jest ta funkcja haszująca? Hę?arigo pisze:potrzebuje w nim zastosowac funkcje haszujaca.
Zapewne tak sobie przetłumaczyłeś angielskie 'hash function'.
Tylko że po polsku, w zależności od kontekstu, używa się terminów 'funkcja mieszająca' lub 'funkcja skrótu'. To są różne rzeczy, niestety. Wnioskując z całości twojego postu, chodzi ci o funkcję skrótu. Trzymaj się tego, bo taka jest Polska Norma w tej dziedzinie.
(Musiałem umieścić tę uwagę, bo niesamowicie irytują mnie podobne pseudoterminy.)
drugie primo:
Hmm. 4 bajty, czyli 32 bity. No a 32-bitowa funkcja skrótu, nawet jakaś najlepsza, jest, że tak powiem, 'z natury' bardzo kolizyjna. Więc nic dobrego, moim zdaniem, i tak nie osiągniesz.arigo pisze:a na wyjsciu 4.
No ale może w jakimś stopniu to ci pomoże:
-
- Użytkownik
- Posty: 852
- Rejestracja: 23 paź 2004, o 10:17
- Płeć: Mężczyzna
- Lokalizacja: Lublin
- Pomógł: 28 razy
funkcja haszujaca
po 1 jak nie masz zamiaru odpowiadac na temat i wniesc czegos do dyskusji to sie nie wypowiadaj
po 2 tlumaczenia na jezyk polski sa bardzo rozne i tak kazdy wie o co dokladnie chodzi wiec dyskusje na tematy humanistyczne mozesz sobie darowac
po 3 logiczne ze skoro uzylem slowa 10 bajtow a potem pojawia sie sama cyfra to wiadomo ze musi ona dotyczyc bajtow to jest tzw. unikanie zbednych powtorzen wyrazow tak ad. Twej wielkiej poprawnosci humanistycznej postow
po 4 nie rozumiesz o co mi chodzi. to ze funkcje skrotu (pisze tak zebys nie mial problemow ze zrozumieniem o czym mowimy) sa z natury kolizyjne to wie kazdy, ja wyraznie zaznaczylem ze szukam algorytmu asymetrycznego, zeby znajac wyjscie nie mozna bylo otworzyc wejscia. wtedy sama kolizyjnosc juz nie jest az tak wielkim problemem dla tego zastosowania co robie. dodatkowo kolizyjnosc zmiejszam przez filtrowanie wejscia tylko do znakow alfanumerycznych
po 5 wyraznie zaznaczylem ze ten algorytm ma byc prosty do zaimplementowania z wykorzystaniem podstawowych operatorow bitowych. to ze w C sa piekne funkcje skrotu kazdy wie, problem sie pojawia tutaj ze ja ta funkcje pisze w asm i nie moze ona bardzo duzo rozkazow zajmowac.
po 6 ten post napisany jest takim tonem jakim odpowiedz na moje zapytanie
po 2 tlumaczenia na jezyk polski sa bardzo rozne i tak kazdy wie o co dokladnie chodzi wiec dyskusje na tematy humanistyczne mozesz sobie darowac
po 3 logiczne ze skoro uzylem slowa 10 bajtow a potem pojawia sie sama cyfra to wiadomo ze musi ona dotyczyc bajtow to jest tzw. unikanie zbednych powtorzen wyrazow tak ad. Twej wielkiej poprawnosci humanistycznej postow
po 4 nie rozumiesz o co mi chodzi. to ze funkcje skrotu (pisze tak zebys nie mial problemow ze zrozumieniem o czym mowimy) sa z natury kolizyjne to wie kazdy, ja wyraznie zaznaczylem ze szukam algorytmu asymetrycznego, zeby znajac wyjscie nie mozna bylo otworzyc wejscia. wtedy sama kolizyjnosc juz nie jest az tak wielkim problemem dla tego zastosowania co robie. dodatkowo kolizyjnosc zmiejszam przez filtrowanie wejscia tylko do znakow alfanumerycznych
po 5 wyraznie zaznaczylem ze ten algorytm ma byc prosty do zaimplementowania z wykorzystaniem podstawowych operatorow bitowych. to ze w C sa piekne funkcje skrotu kazdy wie, problem sie pojawia tutaj ze ja ta funkcje pisze w asm i nie moze ona bardzo duzo rozkazow zajmowac.
po 6 ten post napisany jest takim tonem jakim odpowiedz na moje zapytanie
-
- Użytkownik
- Posty: 852
- Rejestracja: 23 paź 2004, o 10:17
- Płeć: Mężczyzna
- Lokalizacja: Lublin
- Pomógł: 28 razy
funkcja haszujaca
hmmm tzn jak opisac problem jakiego slownictwa nie znasz ??
problemem jest znalezienie funkcji skrotu ktora spelnia warunki postawione w pierwszym poscie
problemem jest znalezienie funkcji skrotu ktora spelnia warunki postawione w pierwszym poscie
funkcja haszujaca
CRC32? 32 bity to jednak troszke malo. Dlaczego nie poswiecisz wiecej bitow na hash?
Pozdrawiam, GNicz
Pozdrawiam, GNicz
funkcja haszujaca
Hehe, to żeś se ulżył. Ale to dobrze, przynajmniej będziesz spał spokojniej. Niestety, w żadnym punkcie nie masz racji.
Rozumiem o co ci chodzi. (Nie mam problemów ze zrozumieniem o czym mówimy.) Tak, są kolizyjne, tylko czasami trudno to udowodnić.
Algorytmu asymetrycznego? O, w tym miejscu mnie zaskoczyłeś trochę. Bo skoro użyłeś słowa 'asymetryczność' względem funkcji (algorytmu) skrótu, to myślisz lub przypuszczasz, że istnieją również symetryczne f. skrótu. Tylko, że to jest bezsens. Bo f. skrótu są z definicji jednokierunkowe i nie ma możliwości ich odwrócenia, niezależnie od tego, ile by nie powodowały kolizji. Bo kolizje z tym akurat nie mają nic wspólnego.
Co do zmniejszania kolizyjności. W jaki sposób filtrujesz to wejście? Usuwając z niego znaki nie alfanumeryczne? Np. tak dla wejścia trójbajtowego: a#b daje ab? I wejście masz blokowe? Bo jeśli tak, to ty tym kolizyjność zwiększasz nie zmniejszasz. Jakie masz wejście, blokowe czy strumieniowe?
A, i pewnie tego kodu który ci w linku zapodałem nie przeczytałeś, no nie?
W tym miejscu kończy się część pierwsza pod tytułem "Odpowiedzi na odpowiedzi" i zaczyna druga pod tytułem "Moje własne wypociny". Serdecznie zapraszam do lektury.
Może w rozwiązaniu twojego problemu pomoże ci funkcja VMPC. Wymyślił ją Polak i ponoć jest rewelacyjna (ponoć, bo osobiście nie sprawdzałem, ale sprawdzali inni).
Strona domowa:
Opis funkcji: i http://www.vmpcfunction.com/vmpc.pdf
Powyższe strony są w j. angielskim, ale na pewno nie będziesz miał z tym problemu.
Nie jest to typowa f. skrótu. Dlaczego, to już sobie poczytaj.
Krótki polski tekst o niej możesz przeczytać tu: http://hacking.pl/news.php?id=3434 bo hacking.pl zimą o niej donosił.
Zanim mi odpowiesz na cokolwiek, zapoznaj się chociaż z niusem z hacking.pl.
Pozdrawiam wesoło, pogodnie i radośnie, czyli w tonie tej wypowiedzi.
.
Ależ mam zamiar i, wbrew pozorom, odpowiedź była na temat. Nawet jakiegoś linka zarzuciłem dla zachęty (32 bity i te sprawy...).arigo pisze:po 1 jak nie masz zamiaru odpowiadac na temat i wniesc czegos do dyskusji to sie nie wypowiadaj
Nie wiesz, jak bardzo się mylisz. Nomenklatura w niektórych przypadkach jest niesamowicie istotna. Bo termin funkcji 'haszującej' w j. polskim nie istnieje, przynajmniej jeśli idzie o kryptografię (mimo to w domu możesz sobie tak wołać). A funkcja skrótu i mieszająca to dwie zupełnie różne rzeczy, terminologicznie poprawne. I wcale kontekst wypodziedzi cię nie usprawiedliwia. I nie są to żadne wywody humanistyczne. Musisz się po prostu przyzwyczaić do pewnych rzeczy, takich, jak używanie poprawnej terminologii. Wyobraź sobie np. sytuację, gdy ktoś tłumaczy słowo 'field' w kontekście matematycznym z angielskiego na polski jako 'pole'. I co, nie zwróciłbyś uwagi? Oczywiście, bo po polsku nie ma 'pola' tylko jest 'ciało'. Widzisz, termin to termin.arigo pisze:po 2 tlumaczenia na jezyk polski sa bardzo rozne i tak kazdy wie o co dokladnie chodzi wiec dyskusje na tematy humanistyczne mozesz sobie darowac
A tego to zupełnie nie rozumiem, bo się wcale do tego nie czepiałem. Czytaj ze zrozumieniem.arigo pisze:po 3 logiczne ze skoro uzylem slowa 10 bajtow a potem pojawia sie sama cyfra to wiadomo ze musi ona dotyczyc bajtow to jest tzw. unikanie zbednych powtorzen wyrazow tak ad. Twej wielkiej poprawnosci humanistycznej postow
O, to jest ciekawy kawałek. Ale po kolei.arigo pisze:po 4 nie rozumiesz o co mi chodzi. to ze funkcje skrotu (pisze tak zebys nie mial problemow ze zrozumieniem o czym mowimy) sa z natury kolizyjne to wie kazdy, ja wyraznie zaznaczylem ze szukam algorytmu asymetrycznego, zeby znajac wyjscie nie mozna bylo otworzyc wejscia. wtedy sama kolizyjnosc juz nie jest az tak wielkim problemem dla tego zastosowania co robie. dodatkowo kolizyjnosc zmiejszam przez filtrowanie wejscia tylko do znakow alfanumerycznych
Rozumiem o co ci chodzi. (Nie mam problemów ze zrozumieniem o czym mówimy.) Tak, są kolizyjne, tylko czasami trudno to udowodnić.
Algorytmu asymetrycznego? O, w tym miejscu mnie zaskoczyłeś trochę. Bo skoro użyłeś słowa 'asymetryczność' względem funkcji (algorytmu) skrótu, to myślisz lub przypuszczasz, że istnieją również symetryczne f. skrótu. Tylko, że to jest bezsens. Bo f. skrótu są z definicji jednokierunkowe i nie ma możliwości ich odwrócenia, niezależnie od tego, ile by nie powodowały kolizji. Bo kolizje z tym akurat nie mają nic wspólnego.
Co do zmniejszania kolizyjności. W jaki sposób filtrujesz to wejście? Usuwając z niego znaki nie alfanumeryczne? Np. tak dla wejścia trójbajtowego: a#b daje ab? I wejście masz blokowe? Bo jeśli tak, to ty tym kolizyjność zwiększasz nie zmniejszasz. Jakie masz wejście, blokowe czy strumieniowe?
Hmm. To może wytłumacz, które operatory bitowe uważasz za podstawowe.arigo pisze:po 5 wyraznie zaznaczylem ze ten algorytm ma byc prosty do zaimplementowania z wykorzystaniem podstawowych operatorow bitowych. to ze w C sa piekne funkcje skrotu kazdy wie, problem sie pojawia tutaj ze ja ta funkcje pisze w asm i nie moze ona bardzo duzo rozkazow zajmowac.
A, i pewnie tego kodu który ci w linku zapodałem nie przeczytałeś, no nie?
Heh. A skąd wiesz jakim tonem go pisałem? Zapewniam cię, że pisałem go tonem wesołym, radosnym i pogodnym. W również ten sam sposób przeczytałem obie twoje wypowiedzi. A to, że ty go inaczej przeczytałeś, to już nie miej do mnie pretensji.arigo pisze:po 6 ten post napisany jest takim tonem jakim odpowiedz na moje zapytanie
W tym miejscu kończy się część pierwsza pod tytułem "Odpowiedzi na odpowiedzi" i zaczyna druga pod tytułem "Moje własne wypociny". Serdecznie zapraszam do lektury.
Może w rozwiązaniu twojego problemu pomoże ci funkcja VMPC. Wymyślił ją Polak i ponoć jest rewelacyjna (ponoć, bo osobiście nie sprawdzałem, ale sprawdzali inni).
Strona domowa:
Kod: Zaznacz cały
http://www.vmpcfunction.com/
Opis funkcji:
Kod: Zaznacz cały
http://www.vmpcfunction.com/function.htm
Powyższe strony są w j. angielskim, ale na pewno nie będziesz miał z tym problemu.
Nie jest to typowa f. skrótu. Dlaczego, to już sobie poczytaj.
Krótki polski tekst o niej możesz przeczytać tu: http://hacking.pl/news.php?id=3434 bo hacking.pl zimą o niej donosił.
Zanim mi odpowiesz na cokolwiek, zapoznaj się chociaż z niusem z hacking.pl.
Pozdrawiam wesoło, pogodnie i radośnie, czyli w tonie tej wypowiedzi.
.
-
- Użytkownik
- Posty: 852
- Rejestracja: 23 paź 2004, o 10:17
- Płeć: Mężczyzna
- Lokalizacja: Lublin
- Pomógł: 28 razy
funkcja haszujaca
hehehe pozno jakos juz (dochodzi druga w nocy) i nie bede mial tyle weny zeby na kazdy podpunkt odpisac ))
pod pojeciem asymetryczna funkcja skrotu rozumiem funkcje skrotu gdzie po znajomosci wyjscia nie jestesmy w stanie okreslic jakie stany wejsciowe powoduja jego stan.
natomiast symetryczna funkcja skrotu daje nam (przy mniejszym lub wiekszym wysilku) mozliwosc odtowrzenia wszystkich danych wejsciowych ktore powoduja zadany stan wyjscia
a co do zmniejszania kolizji przez filtrowanie to sposrod wszystkich danych wejsciowych ktore powoduja wygenerowanie danego skrotu nalezy odrzucic wszystkie ktore nie spelniaja kryterium alfanumerycznosci co imho zmiejsza ich ilosc
dane mam strumieniowe
podstawowe operatory bitowe: xor and or not shl shr
no i nie bitowe inc i dec poniewaz po 1 bajcie zajmuja wiec to nie jest duzo
linka ktorego mi dales czytalem ale tego w sposob krotki i malo zajmujacy w asm raczej sie nie zaimplementuje
o funkcji VMPC slyszalem ale jeszcze sobie doczytam tylko juz nie teraz gdyz jest pozno
do gnicza:
z tego powodu ze wejscie bedzie mialo ok 15 znakow wiec taki duzy skrot mija sie z celem
dzieki Hrabii za pomoc ))
jednak chyba zakoduja ta moja wlasna funkcje za genialna ona nie jest lecz ma wiele zalet po 1 nie jest znana wiec ktos kto to bedzie chcial obejsc bedzie musial uzyc mozgu i wiedzy i nie wystarczy odpalenie progsa napisanego przez kogos innego po 2 trzeba przyznac ze warunki stawiane tej funkcji sa bardzo specyficzne (prosta implementacja w asm oraz bardzo male dane wejsciowe i wyjscie ok 2-3 raza mniejsze od wejscia)
pozdrawiam
pod pojeciem asymetryczna funkcja skrotu rozumiem funkcje skrotu gdzie po znajomosci wyjscia nie jestesmy w stanie okreslic jakie stany wejsciowe powoduja jego stan.
natomiast symetryczna funkcja skrotu daje nam (przy mniejszym lub wiekszym wysilku) mozliwosc odtowrzenia wszystkich danych wejsciowych ktore powoduja zadany stan wyjscia
a co do zmniejszania kolizji przez filtrowanie to sposrod wszystkich danych wejsciowych ktore powoduja wygenerowanie danego skrotu nalezy odrzucic wszystkie ktore nie spelniaja kryterium alfanumerycznosci co imho zmiejsza ich ilosc
dane mam strumieniowe
podstawowe operatory bitowe: xor and or not shl shr
no i nie bitowe inc i dec poniewaz po 1 bajcie zajmuja wiec to nie jest duzo
linka ktorego mi dales czytalem ale tego w sposob krotki i malo zajmujacy w asm raczej sie nie zaimplementuje
o funkcji VMPC slyszalem ale jeszcze sobie doczytam tylko juz nie teraz gdyz jest pozno
do gnicza:
z tego powodu ze wejscie bedzie mialo ok 15 znakow wiec taki duzy skrot mija sie z celem
dzieki Hrabii za pomoc ))
jednak chyba zakoduja ta moja wlasna funkcje za genialna ona nie jest lecz ma wiele zalet po 1 nie jest znana wiec ktos kto to bedzie chcial obejsc bedzie musial uzyc mozgu i wiedzy i nie wystarczy odpalenie progsa napisanego przez kogos innego po 2 trzeba przyznac ze warunki stawiane tej funkcji sa bardzo specyficzne (prosta implementacja w asm oraz bardzo male dane wejsciowe i wyjscie ok 2-3 raza mniejsze od wejscia)
pozdrawiam
-
- Użytkownik
- Posty: 55
- Rejestracja: 27 lis 2004, o 22:24
- Płeć: Mężczyzna
- Lokalizacja: Hrabia is out there
funkcja haszujaca
E tam późno. Właśnie, że wcześnie!arigo pisze:hehehe pozno jakos juz (dochodzi druga w nocy)
W takim razie chyba źle rozumiesz. Funkcji skrótu nie dzielimy na symetryczne i asymetryczne, bo tak po prostu się nie da. W pewnym stopniu f. skrótu mają cechy obu rodzajów, które ty wyróżniasz.arigo pisze:pod pojeciem asymetryczna funkcja skrotu rozumiem funkcje skrotu gdzie po znajomosci wyjscia nie jestesmy w stanie okreslic jakie stany wejsciowe powoduja jego stan.
natomiast symetryczna funkcja skrotu daje nam (przy mniejszym lub wiekszym wysilku) mozliwosc odtowrzenia wszystkich danych wejsciowych ktore powoduja zadany stan wyjscia
Mając skrót wiadomości nie ma matematycznej możliwości znaleźć choćby jednej wiadomości, dającej dany skrót. Natomiast generując odpowiednią liczbę skrótów (kłania się paradoks dnia urodzin) jesteśmy niemal pewni znalezienia kolizji. A wszystkich wiadomości nigdy nie znajdziemy, bo dla każdej f. skrótu jest ich nieskończenie wiele. Natomiast znalezienie wiadomości dających określony skrót jest możliwe np. metodą brute-force. W twoim przypadku 10 bajtów do 4 bajtów, to jak mrugnięcie okiem. Niezależnie od jakości f. skrótu.
Pokaż przykład, jeśli możesz.arigo pisze:a co do zmniejszania kolizji przez filtrowanie to sposrod wszystkich danych wejsciowych ktore powoduja wygenerowanie danego skrotu nalezy odrzucic wszystkie ktore nie spelniaja kryterium alfanumerycznosci co imho zmiejsza ich ilosc
dane mam strumieniowe
Co prawda nie do mnie, ale coś wtrącę. Duży skrót nigdy nie mija się z celem, bo im większy tym lepiej. Oczywiście w granicach wymagań bezpieczeństwa. Gdy długość skrótu masz mniejszą od ustalonej długości wiadomości, to masz pewne kolizje. Natomiast przy równej lub większej długości skrótu od wiadomości, w zależności od jakości f. skrótu, kolizji nie powinno być lub będzie ich niewiele.arigo pisze:do gnicza:
z tego powodu ze wejscie bedzie mialo ok 15 znakow wiec taki duzy skrot mija sie z celem
Do gnicza jeszcze: crc nie jest bezpieczne kryptograficznie.
Hrabiemuarigo pisze:dzieki Hrabii za pomoc ))
Przy funkcjach skrótu, zwłaszcza tak krótkich, nie jest to szczególna zaleta.arigo pisze:jednak chyba zakoduja ta moja wlasna funkcje za genialna ona nie jest lecz ma wiele zalet po 1 nie jest znana
Mam jakieś takie wrażenie, że to chyba nie najszczęśliwszy pomysł 32-bitowa funkcja skrótu na wiadomości o określonej (tylko 10 bajtów!) długości. Może opisz do czego to ma służyć (no chyba, że robisz to dla wojska, to wtedy nie ryzykuj ), a może znajdzie się lepsze rozwiązanie.arigo pisze:wiec ktos kto to bedzie chcial obejsc bedzie musial uzyc mozgu i wiedzy i nie wystarczy odpalenie progsa napisanego przez kogos innego po 2 trzeba przyznac ze warunki stawiane tej funkcji sa bardzo specyficzne (prosta implementacja w asm oraz bardzo male dane wejsciowe i wyjscie ok 2-3 raza mniejsze od wejscia)
.
funkcja haszujaca
Wiem, lecz implementacja jest bardzo prosta i daje na wyjsciu 32-bity, jak wymagal Arigo.Hrabia pisze:Do gnicza jeszcze: crc nie jest bezpieczne kryptograficznie..
Czyzby Hrabia Drakula?Hrabia pisze:E tam późno. Właśnie, że wcześnie!
Zamiast skrotu mozna zaszyfrowac ta wiadomosc. Aczkolwiek mozesz probowac napisac wlasna funkcje chyba ze masz co do niej duze wymagania.
Pozdrawiam, GNicz
-
- Użytkownik
- Posty: 852
- Rejestracja: 23 paź 2004, o 10:17
- Płeć: Mężczyzna
- Lokalizacja: Lublin
- Pomógł: 28 razy
funkcja haszujaca
hehehe wiem ze 2a.m. jest obiektywnie wczesna godzina lecz akurat wtedy dla mnie to bylo bardzo poznoHrabia pisze: E tam późno. Właśnie, że wcześnie!
w moim przypadku mozna znalezc wszystkie mozliwosci wejsciowe dajace ten sam skrot poniewaz wejscie jest ograniczone do okreslonej liczby znakowHrabia pisze: W takim razie chyba źle rozumiesz. Funkcji skrótu nie dzielimy na symetryczne i asymetryczne, bo tak po prostu się nie da. W pewnym stopniu f. skrótu mają cechy obu rodzajów, które ty wyróżniasz.
Mając skrót wiadomości nie ma matematycznej możliwości znaleźć choćby jednej wiadomości, dającej dany skrót. Natomiast generując odpowiednią liczbę skrótów (kłania się paradoks dnia urodzin) jesteśmy niemal pewni znalezienia kolizji. A wszystkich wiadomości nigdy nie znajdziemy, bo dla każdej f. skrótu jest ich nieskończenie wiele. Natomiast znalezienie wiadomości dających określony skrót jest możliwe np. metodą brute-force. W twoim przypadku 10 bajtów do 4 bajtów, to jak mrugnięcie okiem. Niezależnie od jakości f. skrótu.
(...)
Pokaż przykład, jeśli możesz.
(...)
Przy funkcjach skrótu, zwłaszcza tak krótkich, nie jest to szczególna zaleta.
(...)
Mam jakieś takie wrażenie, że to chyba nie najszczęśliwszy pomysł 32-bitowa funkcja skrótu na wiadomości o określonej (tylko 10 bajtów!) długości. Może opisz do czego to ma służyć (no chyba, że robisz to dla wojska, to wtedy nie ryzykuj ), a może znajdzie się lepsze rozwiązanie.
mam teraz troche czasu i pisze programik typu crackme gdyz chce sie znalezc po "drugiej stronie"
i w jednym z poziomow na podane haslo mialbyc generowany skrot i porownywany ze skrotem wzorcowym - teraz juz powinno byc jasne dlaczego nie chce uzywac jakiegos ogolnie znanego algorytmu poniewaz ktos kto sie bedzie w to bawil ma sie wykazac wlasnymi umiejetnosciami a nie tylko odpalaniem czyis programow lamiacych. i wlasnie z zalozenia osoba to lamiaca mialaby napisac programik co by robil atak typu brute-force na ten algorytm. tylko ze niestety nie moge w prostyu sposob uzyskac efektu "asymetrycznosci" teraz moze wyjasnie na jakims banalnym przykladzie (zamieniajacym 2 bajty w 1) o co mi chdzilo w tym pojeciu
kod w skladni intela
mov al, ARG1
mov ah,ARG2
and al,ah
not al
zakladamy ze ARG1="a"(61h) oraz ARG2="o"(6fh)
01100001 and
01101111 =
01100001 (61h)
not 01100001 =
10011110 =9Eh
teraz stawiamuy sie w roli atakujacego ten algorytm wartosc 9Eh negujemy otrzymujemy wartosc 61h
01100001 widzimy ze jest to wynik iloczynu dwoch bajtow wiec tam gdzie sa "1" tam musza byc jedynki a tam gdzie sa "0" tam musi byc conajmniej jedno zero wiec
x11xxxx1
x11xxxx1
co daje nam 3*5=15 kombinacji wejsciowych dla ktorych generowany jest identyczny skrot
to rozumialem pod pojeciem "symetrycznosci" skrotu
teraz wyjasnie o co mi chodzilio ze zmnieszaniem kolozji dzieki wpuszczaniu na wejscie tylko danych alfanumerycznnych
w powyzszym przykladzie np
11100001
01100001
te 2 liczby spelniaja postawione przez nas wczesniej warunki lecz dzieki filtracji na wejsciu to by nie zadzialalo
chyba teraz stalo sie jasne czego szukam (generalnie chodzi o to by zmusic kogos do napisania sofu lamiacego ten skrot metoda brute-force a nie metoda inzynierii wstecznej)
pozdrawiam
-
- Użytkownik
- Posty: 55
- Rejestracja: 27 lis 2004, o 22:24
- Płeć: Mężczyzna
- Lokalizacja: Hrabia is out there
funkcja haszujaca
No widzisz. I tu jest nieścisłość. Bo chcesz, żeby to było łamane brute-forcem. Ale jednocześnie algorytm jest niejawny. No to jak ktoś ma się wykazać umiejętnościami pisząc kod łamiący dla algorytmu, którego nie zna? W takim przypadku pozostaje tylko inżynieria odwrotna i metody matematyczne.arigo pisze:i w jednym z poziomow na podane haslo mialbyc generowany skrot i porownywany ze skrotem wzorcowym - teraz juz powinno byc jasne dlaczego nie chce uzywac jakiegos ogolnie znanego algorytmu poniewaz ktos kto sie bedzie w to bawil ma sie wykazac wlasnymi umiejetnosciami a nie tylko odpalaniem czyis programow lamiacych. i wlasnie z zalozenia osoba to lamiaca mialaby napisac programik co by robil atak typu brute-force na ten algorytm.
Primo: raczej 3^5=243 kombinacji.arigo pisze:tylko ze niestety nie moge w prostyu sposob uzyskac efektu "asymetrycznosci" teraz moze wyjasnie na jakims banalnym przykladzie (zamieniajacym 2 bajty w 1) o co mi chdzilo w tym pojeciu
/ciach przykład/
teraz stawiamuy sie w roli atakujacego ten algorytm wartosc 9Eh negujemy otrzymujemy wartosc 61h
01100001 widzimy ze jest to wynik iloczynu dwoch bajtow wiec tam gdzie sa "1" tam musza byc jedynki a tam gdzie sa "0" tam musi byc conajmniej jedno zero wiec
x11xxxx1
x11xxxx1
co daje nam 3*5=15 kombinacji wejsciowych dla ktorych generowany jest identyczny skrot
to rozumialem pod pojeciem "symetrycznosci" skrotu
Co do przykładu. W twoim rozumowaniu symetryczności każda funkcja skrótu jest asymetryczna, ponieważ zmiana choćby jednego bitu na wejściu powoduje diametralną zmianę skrótu wiadomości. Jest to nieodłączna cecha funkcji skrótu i każdy taki algorytm jest projektowany z, między innymi, myślą o niej. Weźmy jako przykład znaną wszystkim MD5:
wiadomość: binarnie = skrót
bbbb: 1100010 1100010 1100010 1100010 = 65BA841E01D6DB7733E90A5B7F9E6F80
bbcb: 1100010 1100010 1100011 1100010 = 11CE37A7A62B156AC004AE7DF64D7D8D
W twoim przykładzie i również, wnioskując z całości dyskusji, w twoim aktualnym algorytmie ten warunek nie jest zachowany. Dlatego też trudno to nazwać funkcją skrótu. Bardziej bym się skłaniał do określenia "pewnego rodzaju szyfrowanie/kompresja stratne/a" lub może generowanie jakiegoś klucza z wiadomości.
Hmm. W takim razie o tym, czy zmniejszasz, czy też zwiększasz tym kolizyjność swojego algorytmu nie można się wypowiedzieć, nie znając algorytmu. Ponieważ usunięcie pewnego zbioru danych wejściowych może powodować usunięcie ze zbioru wyników tych elementów, które się powtarzają (wówczas osiągasz swój cel), ale równiez może zachodzić sytuacja, że usuniesz właśnie te, które się nie powtarzają (i wówczas masz efekt odwrotny do zamierzonego). Zostawmy to nierozstrzygnięte.arigo pisze:teraz wyjasnie o co mi chodzilio ze zmnieszaniem kolozji dzieki wpuszczaniu na wejscie tylko danych alfanumerycznnych
w powyzszym przykladzie np
11100001
01100001
te 2 liczby spelniaja postawione przez nas wczesniej warunki lecz dzieki filtracji na wejsciu to by nie zadzialalo
Inna sprawa to to, że, z tego co widzę, ułatwiasz tym lekko zadanie atakującemu. Bo:
Liter i cyfr mamy łącznie 36. Zatem możliwości mamy 36^10. Ale to nie wszystko. Ponieważ, na zdrowy rozum, można również podać na wejście ciąg np. 8-znakowy. W takim razie zastosujmy sumę ciągu geometrycznego: S=36*(36^10-1)/35 (mam nadzieję, że nie skopałem). S=3760620109779060=3.76e15. Może dużo, może nie, zależy od mocy sprzętu i złożoności algorytmu. Ale abcdabcd i abcd##abcd będą dawać ten sam wynik, prawda? A gdybyś pozwolił na znaki inne niż alfanumeryczne, utrudniłbyś lekko zadanie. Lekko, bo by to była kwestia tylko dłuższego czasu. Bo główny problem tkwi w napisaniu programu.
No jasne. Tylko musisz przy tym opisać swój algorytm. Bo inaczej to pozostaje deasemblacja i potem brute-force. Zauważ, że w takim przypadku niejawność algorytmu nie jest żadnym utrudnieniem. Natomiast mając algorytm (w ten czy inny sposób) nie jest wielkim wyzwaniem napisać prosty program szukający metodą brute-force zadanego wyniku. Jaki z tego wniosek? Taki, że to ty masz najtrudniejsze zadanie, bowiem algorytm powinien być taki, aby jego słowny opis (klarowny, nie ściemniany na siłę) wymagał jakichś (jakich - to już ty stawiasz zadanie) umiejętności do jego zaimplementowania. Bo gdy już mamy gotowy program, to wtedy brute-force i wio... jutro gotowe.arigo pisze:chyba teraz stalo sie jasne czego szukam (generalnie chodzi o to by zmusic kogos do napisania sofu lamiacego ten skrot metoda brute-force a nie metoda inzynierii wstecznej)
Pozdrawiam.
.