bit commitment

Základní přehled o problematice ochrany informací. Diskutovány budou možné zdroje ohrožení, metody ochrany proti těmto nebezpečím, způsob návrhu globální bezpečnostní strategie.
df
Matfyz(ák|ačka) level III
Příspěvky: 194
Registrován: 5. 6. 2006 11:55

bit commitment

Příspěvek od df »

Zdravicko panove, damy

Mel bych otazku na Bit Commitment:

handouty rikaji toto:

A dokazuje strane B bit X
jsou tu tri kroky
1) B posle entite A nahodny retezec R
2) A spoji X s R a vymysli klic K a udela E(K,X+R)
3) overovani = A prozradi B klick K

otazka zni, proc nefunguje toto:
1) A vymysli K, spocte E(K,X) a posle to B
2) overovani = A prozradi B klic K

aneb - k cemu je tam to R? zkusil sem si pripomenout prednasku z nahravky, ale tam tonda povida jen "R je dulezite, zvazte proc", tudiz mi to moc nepomohlo :)

stejny problem mam i v druhem pripade - kdyz se pouziva one-way funkce
nevim proc tam je dulezite mit R1 a R2 a pak R1 publikovat, ja bych si vystacil s R2, ktery bych nezverejnoval
Keleen
Matfyz(ák|ačka) level II
Příspěvky: 90
Registrován: 19. 1. 2005 22:20

Re: bit commitment

Příspěvek od Keleen »

Ja si nejsem jistej, ale kdyz jsem zapremejslel, vylezlo zhruba tohle:

Duvod - aby A nemohla podvadet (jak maj zensky ve zvyku:)

Proc - kdyby bylo pouzito E(K1,X)=C a odeslana jen C, lze najit K2 tze. E(K2,Y)=C (treba tim ze vyzkousim nahodny klic K2 a provedu D(K2,C)=Y (dobre, smysluplnost takhle nalezeneho Y bude divna, ale A muze smele tvrdit ze prave tohle Y poslala) a tim padem by mila A mohla sklidem fixlovat a poslat podle potreby bud K1 nebo K2 coz by znamenalo zfalsovani zpravy X ( protoze nevedomy B udela D(K co dostal od A, C)= bud X nebo Y, podle toho jaky z klicu mu nakonec poslala). Tomuto se ovsem pribalenim neznameho retezce R zamezi, bo B vybira retezec R, tim padem vi, jak bude vypadat a A musi provest E(K1,R+X) = C. Tady by samozrejme A mohla zkusit najit K2 tze. E(K2,R+Y)=C, ale pokud je pouzity sifrovaci algoritmus rozumny(bezpecny z pohledu confussion and defussion) a R neni prilis kratka, je sance takoveho nalezeni nekde v nedohlednu;).

A s tim pouzitim one-way funkce to podle me bude to same...kdyby se pouzilo jen R misto dvojice R1 a R2 a R se nezverejnovalo, dostal by nebohy B pouze hash te zpravy, tedy H(R|X) a pak pro overeni by dostal zpravu (R|X), udelal by H(R|X) a provedl porovnani, ale nikdo nezaruci, ze by A nenasla zpravu tze. H(Q|Y)=H(R|X) a pak neposlala misto (R|X) pro overeni (Q|Y)...cimz by neboheho B zase podvedla, mrcha:).

Snad jsem uplne nesesel z cesty a to co jsem napsal dava smysl, pripadne me nekdo prosim vyvedte z omylu. Jo a sexistickych narazek si nevsimejte, to jen tak, ze ten priklad k tomu proste vybizi:D.
Uživatelský avatar
Tuetschek
Supermatfyz(ák|ačka)
Příspěvky: 657
Registrován: 15. 6. 2005 13:54
Typ studia: Nestuduji ale učím na MFF
Kontaktovat uživatele:

Re: bit commitment

Příspěvek od Tuetschek »

Ja myslim, ze to je presne tak ... a konecne jsem to diky tomu pochopil, takze diky :).
Plug 'n' Pray.
df
Matfyz(ák|ačka) level III
Příspěvky: 194
Registrován: 5. 6. 2006 11:55

Re: bit commitment

Příspěvek od df »

Diky za odpoved. Jenomze ...

Toho, co popisujes, jsem si byl vedom, ale proste mi neprijde realny, aby se tak stalo. V prvnim pripade, kdyz si vemu, ze fixuju bit X, ktery je bud 0 nebo 1, vymyslim klic K, hodim AES(X,K) tak dostanu nejakej nesmysl N o velikosti bloku AES. Necht jsem zvolil X=1. Ted po letech se me zepta protistrana, at prokazu mnou zvolene X. Tak ja budu chtit podvadet a budu potrebovat, abych nasek klic L tak aby N=AES(Y,L), kde Y=0. No neni mi vubec jasny, jak chces hledat takovej klic L. Proste kdyz je ta sifra rozumna, tak by melo byt tezke nalezt klic L tak aby mi to po sifrovani nuly dalo to N. Kdyz mi mala zmena vstupu rozhazi celej vystup, kdyz mi mala zmena klice rozhazi celej vystup, tak jak to najdes?

U toho hashovani jde o to jake ma vlastnosti ta hashovaci funkce. Pokud je tezky najit kolizi, tak by to zase nemelo jit. Proste to nevidim, proc je tam to random.

Jako ano, kdyz mu dam jinej klic, tak ono mu z toho neco vyleze, ale to neco bude velmi velkej nesmysl, nikoliv srozumitelna odpoved. Jestli todle se da oznacit za to, ze podvadim, to uz je vec druha, imho to ten druhej pozna, pokud nebudu mit uzasny stesti, ze se to zrovna trefi, coz ale se mu muze podarit pri takovym stesti i s tim random seedem.

Takze furt nevim :/
Uživatelský avatar
Tuetschek
Supermatfyz(ák|ačka)
Příspěvky: 657
Registrován: 15. 6. 2005 13:54
Typ studia: Nestuduji ale učím na MFF
Kontaktovat uživatele:

Re: bit commitment

Příspěvek od Tuetschek »

No asi to je tim, ze ten protokol je ponekud paranoidni :P ... a hlavne vetsinou nefixujes jeden bit, ne?
Plug 'n' Pray.
df
Matfyz(ák|ačka) level III
Příspěvky: 194
Registrován: 5. 6. 2006 11:55

Re: bit commitment

Příspěvek od df »

Tuetschek píše:No asi to je tim, ze ten protokol je ponekud paranoidni :P ... a hlavne vetsinou nefixujes jeden bit, ne?
No jednak v "Bit" Commitment fixujes jeden bit, ale prave tim spise v pripade, ze fixujes velky smysluplny text, tak mas o to mensi sanci se do nej trefit.
Ale prave i v pripade jednoho bitu, kdyz ti to sifra zarovna na blok - tak uz pri velikosti bloku 64 bitu je tvoje sance na falsovani velmi mala. na 32 bitech na blok bych uznal, ze to je potreba roztahnout na vic bloku tu zpravu tim nahodnym seedem, ale jinak - a specialne pro dlouhe zpravy - to nedava mi furt smysl.
Keleen
Matfyz(ák|ačka) level II
Příspěvky: 90
Registrován: 19. 1. 2005 22:20

Re: bit commitment

Příspěvek od Keleen »

Ja nevim, me prijde, ze mas spatny predpoklady...ja se snazim to udelat tak, aby to bylo formalne nezfalsovatelny...cili dava smysl i to, ze tvrdim, ze zprava byla xflghrvt a ten decrypt mi vykopne ze byla kosdiuenvccs a ja pak teda B snadno presvedcim, ze to skutecne bylo kosdiuenvccs tim, ze mu zaslu chybnej klic...a prave tomu zabrani ten retezec vybranej druhou stranou. Jestli je to realny, surrealny nebo jiny, mi je celkem sumak, formalne je to problem a protokol mu musi zamezit a to prave ten pripad, kde kdybych vynechal ten retezec vybranej druhou stranou, ten lightweight protokol nesplnuje. S hashovaci funkci totez..."za predpokladu ze nema moc kolizi"...nemuzu predpokladat, musim se snazit tomu zamezit a tim ze pouziju R1, R2 a R1 poslu rovnou presne tomu zamezim.

Ten realnej nahled na pripad AES a prave jeden bit je podle me prave problem chybnyho predpokladu, kdy si vyberu misto, kde to zrejme realne dosahnout nejde a obhajuju, ze ten algoritmus s vypustenim posloupnosti druhy strany je "stejne spatnej" pro danej konkretni pripad. Me je danej konkretni pripad opet volnej, ja to potrebuju obecne.

Takhle nejak to vidim ja...netvrdim, ze je to dobre, ale nic vic me nenapada:). Jinak myslim ze tenhle bit commitment protokol je realne "odlehcenej", kdyz jsem trochu brouzdal, nasel jsem treba tohle http://www.cs.mcgill.ca/~crepeau/CRYPTO ... tocol.html a tam maji trochu slozitejsi bit commitment prave pro pripad konkretniho bitu...ale je to dost dlouhy a na prvni pohled dost slozity tak jsem moc nekoumal...nicmene ma to i konkretni matematicky dukazy s hodnotama psti zfalsovani za podminek atd.
df
Matfyz(ák|ačka) level III
Příspěvky: 194
Registrován: 5. 6. 2006 11:55

Re: bit commitment

Příspěvek od df »

Ok, myslim, ze tato argumentace me presvedcila. Jde tam o teoretickou nepopiratelnost. Takze souhlasim a diky!

BTW: Ty slozitejsi BC jsem taky studoval, ale proste mas pravdu.
Odpovědět

Zpět na „SWI071 Ochrana informace II“