Asp Forum - [kryptografia] protokol bit commitment

mk

8/1/2007 9:59:00 AM

Witam!

Czytam w3a?nie ksi??ke "Applied Cryptography" Bruce'a Schneier'a.
W rozdziale 4.9 opisywany jest jeden ze sposobów realizacji protoko3u
kryptograficznego "bit commitment" (metoda pozwalaj?ca z3o?ya
deklaracje, ?e posiadamy jak?? wiadomo?a jedno-bitow?, bez ujawniania
jej; po pewnym czasie mo?na sprawdzia, czy owa deklaracja by3a prawdziwa)

Oto opis protoko3u z ksi??ki z u?yciem funkcji jednokierunkowych:
(1) Alicja generuje losowo dwie liczby R1 i R2
(2) Alicja tworzy wiadomo?a sk3adaj?c? sie z liczb R1 i R2 oraz bitu b,
wobec którego chce z3o?ya deklaracje; wiadomo?a wiec wygl?da tak:
(R1, R2, b)
(3) Alicja oblicza funkcje jednokierunkow? z (R1,R2,b) i wysy3a wynik
Bobowi wraz z liczb? R1
H(R1, R2, b); R1

Bob nie jest w stanie dowiedziea sie na podstawie takiej wiadomo?ci,
jakie jest b.
Alicja nie jest w stanie zmienia warto?ci b, bo Bob przy sprawdzaniu sie
zorientuje, ?e np. wynik funkcji jednokierunkowej jest inny.

Sprawdzanie wygl?da nastepuj?co:
(4) Alicja wysy3a Bobowi oryginaln? wiadomo?a (R1,R2,b)
(5) Bob oblicza funkcje jednokierunkow? z otrzymanej wiadomo?ci i
porównuje j? z t? otrzyman? w kroku (3); sprawdza równie? zgodno?a R1 z
R1 otrzyman? w kroku (3). Je?li wszystko sie zgadza to, otrzymany bit b
nie zosta3 w miedzyczasie zmieniony.

Mam w?tpliwo?ci, czy ten protokó3 nie jest nazbyt skomplikowany?
Czy ten protokó3 nie móg3by wygl?daa po prostu tak?:
(1) Alicja generuje losowo liczbe R1 i skleja j? z bitem b
(R1, b)
(2) Alicja oblicza funkcje jednokierunkow? z (R1, b) i wysy3a wynik Bobowi:
H(R1, b)

Sprawdzanie:
(3) Alicja wysy3a Bobowi (R1, b)
(4) Bob oblicza H(R1, b) i sprawdza z tym co otrzyma3 w kroku (2); je?li
warto?ci s? zgodne, to znaczy, ?e bit b nie zosta3 miedzy krokami 2, a 3
zmieniony.

Bob nie jest w stanie nic dowiedziea sie o bicie b, bo nie zna R1.
Alicja równie? nie mo?e zmanipulowaa bitu b odk?d Bob ma warto?a funkcji
jednokierunkowej...

Dlaczego wiec w ksi??ce podano bardziej skomplikowany przyk3ad z dwoma
liczbami losowymi?

pzdr
mk

20 Answers

Stachu 'Dozzie' K.

8/1/2007 10:33:00 AM

On 01.08.2007, mk <REVERSE_lp.pw@myzskm.REMOVE> wrote:
> Czytam w3a?nie ksi??ke "Applied Cryptography" Bruce'a Schneier'a.
> W rozdziale 4.9 opisywany jest jeden ze sposobów realizacji protoko3u
> kryptograficznego "bit commitment" (metoda pozwalaj?ca z3o?ya
> deklaracje, ?e posiadamy jak?? wiadomo?a jedno-bitow?, bez ujawniania
> jej; po pewnym czasie mo?na sprawdzia, czy owa deklaracja by3a prawdziwa)
>
> Oto opis protoko3u z ksi??ki z u?yciem funkcji jednokierunkowych:
> (1) Alicja generuje losowo dwie liczby R1 i R2
> (2) Alicja tworzy wiadomo?a sk3adaj?c? sie z liczb R1 i R2 oraz bitu b,
> wobec którego chce z3o?ya deklaracje; wiadomo?a wiec wygl?da tak:
> (R1, R2, b)
> (3) Alicja oblicza funkcje jednokierunkow? z (R1,R2,b) i wysy3a wynik
> Bobowi wraz z liczb? R1
> H(R1, R2, b); R1
>
> Bob nie jest w stanie dowiedziea sie na podstawie takiej wiadomo?ci,
> jakie jest b.
> Alicja nie jest w stanie zmienia warto?ci b, bo Bob przy sprawdzaniu sie
> zorientuje, ?e np. wynik funkcji jednokierunkowej jest inny.
>
> Sprawdzanie wygl?da nastepuj?co:
> (4) Alicja wysy3a Bobowi oryginaln? wiadomo?a (R1,R2,b)
> (5) Bob oblicza funkcje jednokierunkow? z otrzymanej wiadomo?ci i
> porównuje j? z t? otrzyman? w kroku (3); sprawdza równie? zgodno?a R1 z
> R1 otrzyman? w kroku (3). Je?li wszystko sie zgadza to, otrzymany bit b
> nie zosta3 w miedzyczasie zmieniony.
>
>
> Mam w?tpliwo?ci, czy ten protokó3 nie jest nazbyt skomplikowany?

Tradycyjnie podaje sie w3a?nie M = (R1 || b) i przesy3a jedynie H(M).

> Czy ten protokó3 nie móg3by wygl?daa po prostu tak?:
> (1) Alicja generuje losowo liczbe R1 i skleja j? z bitem b
> (R1, b)
> (2) Alicja oblicza funkcje jednokierunkow? z (R1, b) i wysy3a wynik Bobowi:
> H(R1, b)
>
> Sprawdzanie:
> (3) Alicja wysy3a Bobowi (R1, b)
> (4) Bob oblicza H(R1, b) i sprawdza z tym co otrzyma3 w kroku (2); je?li
> warto?ci s? zgodne, to znaczy, ?e bit b nie zosta3 miedzy krokami 2, a 3
> zmieniony.
>
> Bob nie jest w stanie nic dowiedziea sie o bicie b, bo nie zna R1.
> Alicja równie? nie mo?e zmanipulowaa bitu b odk?d Bob ma warto?a funkcji
> jednokierunkowej...

Otó? mo?e próbowaa. Mo?e miea wygenerowan? wcze?niej kolizje ró?ni?c?
sie ostatnim bitem. Chodzi o wyeliminowanie tego w3a?nie przypadku. Tak
naprawde w protokole Bob powinien podes3aa swój losowy ci?g R_b,
a Alicja powinna przedstawia H(R_a || R_b || b).

--
Secunia non olet.
Stanislaw Klekot

mk

8/1/2007 2:36:00 PM

Stachu 'Dozzie' K. pisze:
> Tradycyjnie podaje sie w3a?nie M = (R1 || b) i przesy3a jedynie H(M).

Dzieki za potwierdzenie.

> Otó? mo?e próbowaa. Mo?e miea wygenerowan? wcze?niej kolizje ró?ni?c?
> sie ostatnim bitem. Chodzi o wyeliminowanie tego w3a?nie przypadku. Tak
> naprawde w protokole Bob powinien podes3aa swój losowy ci?g R_b,
> a Alicja powinna przedstawia H(R_a || R_b || b).

A ja mam wra?enie, ?e wygenerowanie kolizji dla dwóch liczb losowych
wcale nie jest trudniejsze ni? dla jednej liczby losowej. Nawet gdyby
jedna z liczb by3a wybierana przez Boba.

Chocia?... je?li Bob wybiera jedn? z liczb losowych i ustalia zasady w
ten sposób, ?e Alicja musi daa odpowied? Bobowi w b. krótkim czasie od
otrzymania od Boba liczby losowej, to Alicja bedzie miea bardzo niewiele
czasu na przeprowadzenia ataku na funkcje jednokierunkow?.

Nie mniej je?li ufaa sile funkcji jednokierunkowej, to takie dzia3ania
wydaj? sie zbedne.

pzdr
mk

Stachu 'Dozzie' K.

8/1/2007 3:15:00 PM

On 01.08.2007, mk <REVERSE_lp.pw@myzskm.REMOVE> wrote:
> Stachu 'Dozzie' K. pisze:
>> Tradycyjnie podaje sie w3a?nie M = (R1 || b) i przesy3a jedynie H(M).
>
> Dzieki za potwierdzenie.
>
>> Otó? mo?e próbowaa. Mo?e miea wygenerowan? wcze?niej kolizje ró?ni?c?
>> sie ostatnim bitem. Chodzi o wyeliminowanie tego w3a?nie przypadku. Tak
>> naprawde w protokole Bob powinien podes3aa swój losowy ci?g R_b,
>> a Alicja powinna przedstawia H(R_a || R_b || b).
>
> A ja mam wra?enie, ?e wygenerowanie kolizji dla dwóch liczb losowych
> wcale nie jest trudniejsze ni? dla jednej liczby losowej. Nawet gdyby
> jedna z liczb by3a wybierana przez Boba.

To nie tak. Przede wszystkim mówi?c "kolizja" mamy na my?li _pare_
ci?gów o tym samym skrócie. A po drugie, znalezienie dwóch dowolnych
koliduj?cych ci?gów jest nietrudniejsze (choa niekoniecznie zaraz
prostsze) ni? znalezienie tekstu koliduj?cego do zadanego ci?gu. Ot,
choaby mo?esz wygenerowaa sobie mnóstwo ci?gów, obliczya ich skróty
i posortowaa takie pary wzgledem skrótu. To sie nazywa "paradoks dnia
urodzin" i powinno bya opisane we wspomnianym przez ciebie Schneierze.

> Chocia?... je?li Bob wybiera jedn? z liczb losowych i ustalia zasady w
> ten sposób, ?e Alicja musi daa odpowied? Bobowi w b. krótkim czasie od
> otrzymania od Boba liczby losowej, to Alicja bedzie miea bardzo niewiele
> czasu na przeprowadzenia ataku na funkcje jednokierunkow?.

I o to w3a?nie chodzi. Alicja nie bedzie mog3a u?ya wcze?niej
przeliczonej bazy kolizji, a znajdowanie kolizji dla dobrej funkcji
hashuj?cej jest trudne.

> Nie mniej je?li ufaa sile funkcji jednokierunkowej, to takie dzia3ania
^^^^^^^^^ to sie pisze 3?cznie
> wydaj? sie zbedne.

Nie komplikuj? protoko3u za bardzo, a pozwalaj? skorzystaa ze s3abszej
(czyli 3atwiej spe3nialnej) w3asno?ci. Choa do celów dydaktycznych
u?y3bym, a nasz profesor u?y3, protoko3u w wersji prostszej.

--
Secunia non olet.
Stanislaw Klekot

mk

8/1/2007 3:53:00 PM

Stachu 'Dozzie' K. pisze:
> On 01.08.2007, mk <REVERSE_lp.pw@myzskm.REMOVE> wrote:
>> Stachu 'Dozzie' K. pisze:
>>> Tradycyjnie podaje sie w3a?nie M = (R1 || b) i przesy3a jedynie H(M).
>> Dzieki za potwierdzenie.
>>
>>> Otó? mo?e próbowaa. Mo?e miea wygenerowan? wcze?niej kolizje ró?ni?c?
>>> sie ostatnim bitem. Chodzi o wyeliminowanie tego w3a?nie przypadku. Tak
>>> naprawde w protokole Bob powinien podes3aa swój losowy ci?g R_b,
>>> a Alicja powinna przedstawia H(R_a || R_b || b).
>> A ja mam wra?enie, ?e wygenerowanie kolizji dla dwóch liczb losowych
>> wcale nie jest trudniejsze ni? dla jednej liczby losowej. Nawet gdyby
>> jedna z liczb by3a wybierana przez Boba.
>
> To nie tak. Przede wszystkim mówi?c "kolizja" mamy na my?li _pare_
> ci?gów o tym samym skrócie.

To samo znaczenie s3owa "kolizja" mia3em na my?li, pisz?c com napisa3.

> A po drugie, znalezienie dwóch dowolnych
> koliduj?cych ci?gów jest nietrudniejsze (choa niekoniecznie zaraz
^^^^^^^^^^^^^^
To sie pisze oddzielnie.
1:1 :-)

> prostsze) ni? znalezienie tekstu koliduj?cego do zadanego ci?gu. Ot,
> choaby mo?esz wygenerowaa sobie mnóstwo ci?gów, obliczya ich skróty
> i posortowaa takie pary wzgledem skrótu. To sie nazywa "paradoks dnia
> urodzin" i powinno bya opisane we wspomnianym przez ciebie Schneierze.

Znam ten sposób ataku na funkcje jednokierunkow?.
W obu przypadkach mo?na atakowaa wykorzystuj?c "paradoks dnia urodzin",
bo nie mamy zadanego ci?gu, ale tylko fragment tego ci?gu jest zadany!

>> Chocia?... je?li Bob wybiera jedn? z liczb losowych i ustalia zasady w
>> ten sposób, ?e Alicja musi daa odpowied? Bobowi w b. krótkim czasie od
>> otrzymania od Boba liczby losowej, to Alicja bedzie miea bardzo niewiele
>> czasu na przeprowadzenia ataku na funkcje jednokierunkow?.
>
> I o to w3a?nie chodzi. Alicja nie bedzie mog3a u?ya wcze?niej
> przeliczonej bazy kolizji, a znajdowanie kolizji dla dobrej funkcji
> hashuj?cej jest trudne.

Tia... dla wielu wspó3cze?nie u?ywanych, w ogóle, na dzien dzisiejszy,
nie s? znalezione kolizje (przynajmniej oficjalnie), a to co jest
znalezione to jakie? przypadkowe ci?gi. Lepiej pój?a w t? strone, by bit
b nie by3 zapisany binarnie, ale np. s3ownie. To samo z liczb? losow?.
W takim przypadku by znale?a kolizje funkcja haszuj?ca musia3a by bya
naprawde dobrze rozpracowana, albo 3amana brutaln? si3?.

>> Nie mniej je?li ufaa sile funkcji jednokierunkowej, to takie dzia3ania
> ^^^^^^^^^ to sie pisze 3?cznie

Przepraszam, postaram sie zapamietaa.

>> wydaj? sie zbedne.
>
> Nie komplikuj? protoko3u za bardzo, a pozwalaj? skorzystaa ze s3abszej
> (czyli 3atwiej spe3nialnej) w3asno?ci. Choa do celów dydaktycznych
> u?y3bym, a nasz profesor u?y3, protoko3u w wersji prostszej.

W praktyce mog? komplikowaa, bo wymagana jest dwukierunkowa 3?czno?a
miedzy Alicj?, a Bobem. Gdy Bob nie podaje liczby losowej wystarcza
3?czno?a jednokierunkowa Alicja->Bob.

pzdr
mk

Stachu 'Dozzie' K.

8/1/2007 5:21:00 PM

On 01.08.2007, mk <REVERSE_lp.pw@myzskm.REMOVE> wrote:
> Stachu 'Dozzie' K. pisze:
>> On 01.08.2007, mk <REVERSE_lp.pw@myzskm.REMOVE> wrote:
>>> Stachu 'Dozzie' K. pisze:
>>>> Tradycyjnie podaje sie w3a?nie M = (R1 || b) i przesy3a jedynie H(M).
>>> Dzieki za potwierdzenie.
>>>
>>>> Otó? mo?e próbowaa. Mo?e miea wygenerowan? wcze?niej kolizje ró?ni?c?
>>>> sie ostatnim bitem. Chodzi o wyeliminowanie tego w3a?nie przypadku. Tak
>>>> naprawde w protokole Bob powinien podes3aa swój losowy ci?g R_b,
>>>> a Alicja powinna przedstawia H(R_a || R_b || b).
>>> A ja mam wra?enie, ?e wygenerowanie kolizji dla dwóch liczb losowych
>>> wcale nie jest trudniejsze ni? dla jednej liczby losowej. Nawet gdyby
>>> jedna z liczb by3a wybierana przez Boba.
>>
>> To nie tak. Przede wszystkim mówi?c "kolizja" mamy na my?li _pare_
>> ci?gów o tym samym skrócie.
>
> To samo znaczenie s3owa "kolizja" mia3em na my?li, pisz?c com napisa3.
>
>> A po drugie, znalezienie dwóch dowolnych
>> koliduj?cych ci?gów jest nietrudniejsze (choa niekoniecznie zaraz
> ^^^^^^^^^^^^^^
> To sie pisze oddzielnie.
> 1:1 :-)

OK. http://so.pwn.pl/zasady.php...
Pomyli3em z http://so.pwn.pl/zasady.php...

>> prostsze) ni? znalezienie tekstu koliduj?cego do zadanego ci?gu. Ot,
>> choaby mo?esz wygenerowaa sobie mnóstwo ci?gów, obliczya ich skróty
>> i posortowaa takie pary wzgledem skrótu. To sie nazywa "paradoks dnia
>> urodzin" i powinno bya opisane we wspomnianym przez ciebie Schneierze.
>
> Znam ten sposób ataku na funkcje jednokierunkow?.
> W obu przypadkach mo?na atakowaa wykorzystuj?c "paradoks dnia urodzin",
> bo nie mamy zadanego ci?gu, ale tylko fragment tego ci?gu jest zadany!

Atak przy cze?ciowo zadanym tek?cie na pewno nie jest 3atwiejszy ni?
atak przy tek?cie zupe3nie dowolnym, a podejrzewam, ?e jest nieco
trudniejszy.

>>> Chocia?... je?li Bob wybiera jedn? z liczb losowych i ustalia zasady w
>>> ten sposób, ?e Alicja musi daa odpowied? Bobowi w b. krótkim czasie od
>>> otrzymania od Boba liczby losowej, to Alicja bedzie miea bardzo niewiele
>>> czasu na przeprowadzenia ataku na funkcje jednokierunkow?.
>>
>> I o to w3a?nie chodzi. Alicja nie bedzie mog3a u?ya wcze?niej
>> przeliczonej bazy kolizji, a znajdowanie kolizji dla dobrej funkcji
>> hashuj?cej jest trudne.
>
> Tia... dla wielu wspó3cze?nie u?ywanych, w ogóle, na dzien dzisiejszy,
> nie s? znalezione kolizje (przynajmniej oficjalnie), a to co jest
> znalezione to jakie? przypadkowe ci?gi. Lepiej pój?a w t? strone, by bit
> b nie by3 zapisany binarnie, ale np. s3ownie.

To powoduje pewne komplikacje natury implementacyjnej (sama zamiana na
forme s3own?, wybór jezyka i tak dalej). Pro?ciej jest co? wylosowaa.

> To samo z liczb? losow?.
> W takim przypadku by znale?a kolizje funkcja haszuj?ca musia3a by bya
> naprawde dobrze rozpracowana, albo 3amana brutaln? si3?.

Zapewne.

>>> wydaj? sie zbedne.
>>
>> Nie komplikuj? protoko3u za bardzo, a pozwalaj? skorzystaa ze s3abszej
>> (czyli 3atwiej spe3nialnej) w3asno?ci. Choa do celów dydaktycznych
>> u?y3bym, a nasz profesor u?y3, protoko3u w wersji prostszej.
>
> W praktyce mog? komplikowaa, bo wymagana jest dwukierunkowa 3?czno?a
> miedzy Alicj?, a Bobem. Gdy Bob nie podaje liczby losowej wystarcza
> 3?czno?a jednokierunkowa Alicja->Bob.

Prawde mówi?c nie znam praktycznie wykorzystywanej sytuacji, gdy mamy
3?czno?a jednokierunkow?, ale argument mi sie podoba.

--
Secunia non olet.
Stanislaw Klekot

Marcin Gabryszewski

8/2/2007 6:58:00 AM

mk pisze:
>
> Tia... dla wielu wspólczesnie uzywanych, w ogóle, na dzien dzisiejszy,
> nie sa znalezione kolizje (przynajmniej oficjalnie), a to co jest
> znalezione to jakies przypadkowe ciagi.

A co niby z md5, wygenerowano dwa calkowicie rózne certyfikaty o tym
samym skrócie!!!
Z sha1 tez ma znalezione kolizje.

I z tego co kojarze to obie funkcje hashujace sa ciagle uzywane.

PS
hmm, kiedys mialem juz starcie ze Stachem na temat "md5 is dead"
wygloszonym wlasnie przez Schneier'a.

--
Regards,
Marcin Gabryszewski
G DATA Software Sp. z o.o.
www.gdata.pl

mk

8/2/2007 8:58:00 AM

Stachu 'Dozzie' K. pisze:
>> W obu przypadkach mo?na atakowaa wykorzystuj?c "paradoks dnia urodzin",
>> bo nie mamy zadanego ci?gu, ale tylko fragment tego ci?gu jest zadany!
>
> Atak przy cze?ciowo zadanym tek?cie na pewno nie jest 3atwiejszy ni?
> atak przy tek?cie zupe3nie dowolnym, a podejrzewam, ?e jest nieco
> trudniejszy.

Nie wiem. Nie znam sie na atakowaniu funkcji jednokierunkowych.
Jednak atak brute-force bedzie w obu wypadkach bardzo podobny: Alicja
zmienia swoj? losow? liczbe, a? wygeneruje dwie kolizyjne wiadomo?ci o
ró?nych tre?ciach. Pracoch3onno?a w obu przypadkach w zasadzie taka
sama. Tak czy siak, w obu przypadkach mo?na stosowaa "atak urodzinowy".

>> W praktyce mog? komplikowaa, bo wymagana jest dwukierunkowa 3?czno?a
>> miedzy Alicj?, a Bobem. Gdy Bob nie podaje liczby losowej wystarcza
>> 3?czno?a jednokierunkowa Alicja->Bob.
>
> Prawde mówi?c nie znam praktycznie wykorzystywanej sytuacji, gdy mamy
> 3?czno?a jednokierunkow?, ale argument mi sie podoba.

Oto przyk3ad:
Terrory?ci og3aszaj? ?wiatu, ?e w ci?gu jakiego? czasu Allah ze?le na
San Francisco wielkie trzesienie ziemi.
"Znamy date, ale za nic jej wam nie powiemy, by nie zosta3a
przeprowadzona ewakuacja ludno?ci itp. Allah jest wielki! Na
potwierdzenie, ?e mamy moc wiedziea o takich rzeczach od Allaha podajemy
skrót SHA-512 wiadomo?ci zawieraj?cej date katastrofy: ... . Allah jest
wielki! Podajemy równie? skróty Whirlpool, RIPEMD, Tiger..."

Po jakim? czasie rzeczywi?cie nastepuje trzesienie ziemi w San
Francisco. Terrory?ci po tym zdarzeniu przypominaj? o sobie i ujawniaj?
wiadomo?a z poprawn? dat? katastrofy, a skrót tej wiadomo?ci zgodny jest
z podanym wcze?niej skrótem - na ?wiecie zaczyna panowaa chaos i anarchia...

Ze wzgledów swojego bezpieczenstwa terrory?ci bed? preferowaa kana3
jednokierunkowy np. media. Odpada równie? ryzyko, ?e zostan?
najzwyczajniej przez reszte ludzko?ci zignorowani i nikt wiarygodny nie
prze?le im warto?ci losowej.

pzdr
mk

mk

8/2/2007 9:24:00 AM

Marcin Gabryszewski pisze:
> mk pisze:
>>
>> Tia... dla wielu wspó3cze?nie u?ywanych, w ogóle, na dzien dzisiejszy,
>> nie s? znalezione kolizje (przynajmniej oficjalnie), a to co jest
>> znalezione to jakie? przypadkowe ci?gi.
>
> A co niby z md5, wygenerowano dwa ca3kowicie ró?ne certyfikaty o tym
> samym skrócie!!!

Chyba ró?ne wiadomo?ci po?wiadczane tym samym certyfikatem...
Ale czy ju? da sie generowaa te wiadomo?ci w taki sposób, by by3y
u?yteczne w wybranych z góry sytuacjach? Np. czy obie wiadomo?ci mog?
bya zwyk3ymi plikami tekstowymi zawieraj?cymi w miare sensowne teksty w
jezyku angielskim?

> Z sha1 te? ma znalezione kolizje.

O tym nie wiedzia3em. Czy mo?na prosia ?ród3a?
Wikipedia podaje o skutecznym ataku na uproszczone modyfikacje SHA-1
oraz przeprowadzonych analizach algorytmu dzieki którym atak nie bedzie
wymaga3 tylu obliczen co atak urodzinowy brute-force. Ale wci?? liczba
wymaganych obliczen jest ogromna.

> I z tego co kojarze to obie funkcje hashuj?ce s? ci?gle u?ywane.

Czesto obie jednocze?nie, co dodatkowo utrudnia atak.

> hmm, kiedy? mia3em ju? starcie ze Stachem na temat "md5 is dead"
> wyg3oszonym w3a?nie przez Schneier'a.

Zale?y do jakich zastosowan. Nie wszedzie mo?na stosowaa atak urodzinowy.
Wci?? 3amanie md5 jest poza zasiegiem PCtów. Wystarczy wiec, ?e koszty
jakie trzeba ponie?a na z3amanie s? wieksze ni? korzy?a wynikaj?ca ze
z3amania protoko3u kryptograficznego w danej sytuacji.

pzdr
mk

Marcin Gabryszewski

8/2/2007 9:34:00 AM

mk pisze:
> Marcin Gabryszewski pisze:
>> mk pisze:
>>>
>>> Tia... dla wielu wspólczesnie uzywanych, w ogóle, na dzien
>>> dzisiejszy, nie sa znalezione kolizje (przynajmniej oficjalnie), a to
>>> co jest znalezione to jakies przypadkowe ciagi.
>>
>> A co niby z md5, wygenerowano dwa calkowicie rózne certyfikaty o tym
>> samym skrócie!!!
>
> Chyba rózne wiadomosci poswiadczane tym samym certyfikatem...
NIE

Dwa rózne certyfikaty !!!
Inny CN, inny klucz a skrót ten sam.

Dwie róze wiadomosci(tekstowe) tez zostaly tak spreparowane by daly kolizje.

Jak czytasz ksiazke B.Sch. to moze odwiedz tez jego blog,
jest tam sporo ciekawych informacji o funkcjach skrótu, atakach na nie i
zupelnie innych rzeczach poswieconych kryptografii, kryptoanalizie i
ogólnie o security.

--
Regards,
Marcin Gabryszewski
G DATA Software Sp. z o.o.
www.gdata.pl

Stachu 'Dozzie' K.

8/2/2007 11:37:00 AM

On 02.08.2007, mk <REVERSE_lp.pw@myzskm.REMOVE> wrote:
> Stachu 'Dozzie' K. pisze:
>>> W obu przypadkach mo?na atakowaa wykorzystuj?c "paradoks dnia urodzin",
>>> bo nie mamy zadanego ci?gu, ale tylko fragment tego ci?gu jest zadany!
>>
>> Atak przy cze?ciowo zadanym tek?cie na pewno nie jest 3atwiejszy ni?
>> atak przy tek?cie zupe3nie dowolnym, a podejrzewam, ?e jest nieco
>> trudniejszy.
>
> Nie wiem. Nie znam sie na atakowaniu funkcji jednokierunkowych.
> Jednak atak brute-force bedzie w obu wypadkach bardzo podobny: Alicja
> zmienia swoj? losow? liczbe, a? wygeneruje dwie kolizyjne wiadomo?ci o
> ró?nych tre?ciach. Pracoch3onno?a w obu przypadkach w zasadzie taka
> sama. Tak czy siak, w obu przypadkach mo?na stosowaa "atak urodzinowy".

Ale w jednym przypadku mo?na go robia offline, zawczasu, w drugim musi
bya przeprowadzony online, podczas dzia3ania protoko3u, przez co
dodatkowo nie da sie wykorzystaa informacji zebranych wcze?niej
przy kolejnym przeprowadzaniu protoko3u.

>>> W praktyce mog? komplikowaa, bo wymagana jest dwukierunkowa 3?czno?a
>>> miedzy Alicj?, a Bobem. Gdy Bob nie podaje liczby losowej wystarcza
>>> 3?czno?a jednokierunkowa Alicja->Bob.
>>
>> Prawde mówi?c nie znam praktycznie wykorzystywanej sytuacji, gdy mamy
>> 3?czno?a jednokierunkow?, ale argument mi sie podoba.
>
> Oto przyk3ad:
> Terrory?ci og3aszaj? ?wiatu, ?e w ci?gu jakiego? czasu Allah ze?le na
> San Francisco wielkie trzesienie ziemi.
> "Znamy date, ale za nic jej wam nie powiemy, by nie zosta3a
> przeprowadzona ewakuacja ludno?ci itp. Allah jest wielki! Na
> potwierdzenie, ?e mamy moc wiedziea o takich rzeczach od Allaha podajemy
> skrót SHA-512 wiadomo?ci zawieraj?cej date katastrofy: ... . Allah jest
> wielki! Podajemy równie? skróty Whirlpool, RIPEMD, Tiger..."
>
> Po jakim? czasie rzeczywi?cie nastepuje trzesienie ziemi w San
> Francisco. Terrory?ci po tym zdarzeniu przypominaj? o sobie i ujawniaj?
> wiadomo?a z poprawn? dat? katastrofy, a skrót tej wiadomo?ci zgodny jest
> z podanym wcze?niej skrótem - na ?wiecie zaczyna panowaa chaos i anarchia...

No dobra. A co? praktycznie wykorzystywanego? Bo, zdaje sie, o to
pyta3em.

--
Secunia non olet.
Stanislaw Klekot

pl.comp.programming

[kryptografia] protokol bit commitment

mk

Stachu 'Dozzie' K.

mk

Stachu 'Dozzie' K.

mk

Stachu 'Dozzie' K.

Marcin Gabryszewski

mk

mk

Marcin Gabryszewski

Stachu 'Dozzie' K.

x Login to ForumsZone