Iegūt paroli no «hash-summas» kļūs stipri vieglāk

Moderatori: janis.wd, Vecākie lietotāji

User avatar
KaNeiet
Lietpratējs
Atbildes: 234
Pievienojies: 01 Nov 2007, 00:50
Reputācija: 0
Atrodas: Talsi

Post no KaNeiet » 12 Jūn 2009, 13:10

ob1 wrote:1) Jebkuru kriptogrāfijas problēmu var novest uz NP problēmu.
2) Jebkuru NP problēmu var pārvērst par citu NP problēmu.
3) Tātad jebkuru kriptogrāfijas problēmu var pārvērst par subset sum problēmu.
..
to pakāpes rādītāju var dalīt ar 2, ja izmanto pareizo algoritmu

Visi tie pārveidojumi gan prasa laiku (tīrā matemātika).
Par derībām - iedod man 64 bitu problēmu, tad arī apspriedīsim, atsakos vai nē.
Ko ar 64 bitiem ķēpāties, ņemsim ko pavisam triviālu:
Parole ir viens no 4 skaitļiem (2^2). Tā kodējas ar 2 bitiem, klasiskā izpratnē tās uzzināšanai vajag atbildes uz diviem Jā/Nē tipa jautājumiem. Tu apgalvo, ka pakāpi varot samazināt (N/2), tātad pietiks ar vienu jautājumu. Ceru ka tas neprasīs ārprātīgi daudz laika? Kā ar derībām?

User avatar
aoma
Vecākais lietotājs
Atbildes: 2599
Pievienojies: 25 Apr 2007, 12:47
Reputācija: 0
Atrodas: LV

Post no aoma » 12 Jūn 2009, 13:33

ob1 wrote:Hmm, uz krieviem kādreiz strādāju (padomju laikā), bet vairs negribu - maksā ļoti maz. :(
Žēl, ka tevi dzemdību laikā vecmāte ar nabas saiti netīšām nenožņaudza... Būtu zinājusi, kas izaugs, noteikti būtu tā izdarījusi. :mod:

ob1
Reģistrēts lietotājs
Atbildes: 2959
Pievienojies: 23 Mar 2009, 22:01
Reputācija: 0
Atrodas: Sigulda

Post no ob1 » 12 Jūn 2009, 13:49

-> KaNeiet
Tam Tavam uzdevumam nav nekāds sakars ar kriptogrāfiju. Lai runātu par kriptogrāfiju ir jābūt:
1) Izejas ziņojums;
2) Kriptēšanas algoritms (publiski pieejams);
3) Š ifrētais ziņojums.

Kriptoanalīze ne obligāti atkož paroli. Parasti pietiek, ka no šifrētā ziņojuma (3) tiek iegūts izejas ziņojums (1).

User avatar
Crow
E-žurnālists
Atbildes: 5391
Pievienojies: 10 Mai 2009, 14:22
Reputācija: 0
Atrodas: Ir

Post no Crow » 12 Jūn 2009, 14:12

Nez. Es tikko esmu pabeidzis kriptogrāfijas kursu (ar švakiem cīpariem gan), un toč nesaprotu, ko džedaju māsters un citi vietējie speci te betonē :D

Kā man patīk, ka vietējie speci visus vecos, apsūnojušos akadēmiķus saliek vienā setā un par jebkuru iespējamo tēmu zin un praktiski spēj diskutēt daudz plašāk un pamatīgāk :D

Jusis
Reģistrēts lietotājs
Atbildes: 61
Pievienojies: 05 Feb 2009, 08:55
Reputācija: 0
Atrodas: Rīga

Post no Jusis » 12 Jūn 2009, 16:18

Ir speci un ir wanabee speci.
Random.

User avatar
Crow
E-žurnālists
Atbildes: 5391
Pievienojies: 10 Mai 2009, 14:22
Reputācija: 0
Atrodas: Ir

Post no Crow » 12 Jūn 2009, 16:37

Ir spēks un ir spēka tumšā puse :D
Дебилы, бл*ть...

User avatar
marr
Vecākais lietotājs
Atbildes: 569
Pievienojies: 23 Mar 2007, 23:05
Reputācija: 0
Atrodas: Rīga

Post no marr » 12 Jūn 2009, 16:42

Ok, KaNeiet, Tavuprāt raksts nav greizs, taču ob1 argumentācija gan. Pareizi?
KaNeiet wrote:
marr wrote:(pēc manas saprašanas) argumentē par to, ka raksts ir greizs.
Š vaki ar to saprašanu.

Lasi visu vēlreiz un mēģini atrast kurš apgalvo:
"pakāpes rādītāju var dalīt ar 2, ja izmanto pareizo algoritmu, tā ka paliks vien 2^32 vai pat 2^26, kas vispār risinās zibenīgi"
Vēlos norādīt uz postu
ob1 wrote:Citēju:
A better exponential time algorithm is known, which runs in time O(2^N/2N). The algorithm splits arbitrarily the N elements into two sets of N/2 each. For each of these two sets, it calculates sums of all 2^N/2 possible subsets of its elements and stores them in an array of length 2^N/2. It then sorts ....
kur pietiek ar 2-3 pirmajiem teikumiem, lai saprastu, kas ir domāts.
Neviens šeit neargumentē par to, ka 2^64/2 = 2^32, kas ir absolūti nepareizi.

User avatar
KaNeiet
Lietpratējs
Atbildes: 234
Pievienojies: 01 Nov 2007, 00:50
Reputācija: 0
Atrodas: Talsi

Post no KaNeiet » 12 Jūn 2009, 16:50

Pareizi. Ironizēju par to, ka ja
"ob1 rakstīja:
1) Jebkuru kriptogrāfijas problēmu var novest uz NP problēmu.
2) Jebkuru NP problēmu var pārvērst par citu NP problēmu.
3) Tātad jebkuru kriptogrāfijas problēmu var pārvērst par subset sum problēmu.
..
to pakāpes rādītāju var dalīt ar 2, ja izmanto pareizo algoritmu"
un rakstā minētā ir "kriptogrāfijas problēma", tad ob1 apgalvo, ka viņš šī konkrētā algoritma sarežģītības pakāpi spēj reducēt "uz 2^32 vai pat 2^26, kas vispār risinās zibenīgi", a tie nabadziņi plātas ar nožēlojamu ^52.

User avatar
Wuu
E-žurnālists
Atbildes: 2918
Pievienojies: 23 Aug 2008, 10:32
Reputācija: 0

Post no Wuu » 12 Jūn 2009, 17:01

Mazie einšteini beidzat cepties nevienam nevajag jūsu nolāpītas paroles!
Image

User avatar
WerNeo
Lietpratējs
Atbildes: 1802
Pievienojies: 14 Aug 2007, 01:27
Reputācija: 0

Post no WerNeo » 12 Jūn 2009, 17:05

Ha!!! 2^64? Kas tas ir? 2^64 var droši dalīt ar 2^64, ja runājam par paroles iegūšanas algoritmu. :)

ob1
Reģistrēts lietotājs
Atbildes: 2959
Pievienojies: 23 Mar 2009, 22:01
Reputācija: 0
Atrodas: Sigulda

Post no ob1 » 12 Jūn 2009, 17:41

->KaNeiet
Laikam būsi nepareizi mani sapratis. Mēģināšu skaidrot vēlreiz.
1) 2^52 ir problēmas SHA-1 "smagums".
2) 52-bit subset sum problēmas "smagums" arī ir 2^52.
3) To 52-bit Subset sum problēmu var atrisināt laikā, kas proporcionāls 2^26.
4) Tā kā NP problēmas var pārveidot vienu otrā, tad IESPĒJAMS, ka arī SHA-1 problēmu var atrisināt laikā, kas proporcionāls 2^26. Man nav pieejams šāds algoritms (bet pieļauju, ka kādam ir). Lai NP problēmas pārveidotu no vienas uz otru arī ir jāpasvīst.
5) Kas attiecas uz dinamisko programmēšanu (DP), tad ar to šādas problēmas vispār risinās polinomālā laikā. Nelaime tikai tāda, ka ne visu var paņemt ar to DP. Tāpēc arī minēju par problēmas blīvumu. Savulaik tika izmantota viena kriptogrāfijas metode, kas bija bāzēta uz zema blīvuma subset-sum, bet ar DP to lauza zibenīgi, pofig 64, 128 vai 256 biti.

Nu un visbeidzot par 2^52 atrisināšanu nedēļas laikā uz mājas kompja.
- Nedēļā ir 7 dienas, katrā pa 24 stundām, katrā pa 60 minūtēm, katrā pa 60 sekundēm. Tātad nedēļā ir 604800 sekundes.
- 2^52 / 604800 = 7446427955, jeb aptuveni 7G operācijas.
- Moderni kompju taksts frekvence ir virs 3GHz, 4 kodoli dod 12GHz (jo šos uzdevumus var viegli palaist paralēlās plūsmās).
- 7G operācijas pret 12GHz ir samērojami lielumi.
- Modernam mājas kompim ir arī videokarte, kurā var ielādēt uzdevumu. (Reizēm tās videokartes rēķina ātrāk kā CPU.)

Manuprāt ar šiem aprēķiniem pietiek, lai saprastu, ka 2^52 var sarēķināt nedēļas laikā uz mājas kompja ar brute force.

nevertell
Reģistrēts lietotājs
Atbildes: 2885
Pievienojies: 13 Mar 2009, 23:25
Reputācija: 0

Post no nevertell » 12 Jūn 2009, 18:01

ob1 wrote:->KaNeiet
Laikam būsi nepareizi mani sapratis. Mēģināšu skaidrot vēlreiz.
1) 2^52 ir problēmas SHA-1 "smagums".
2) 52-bit subset sum problēmas "smagums" arī ir 2^52.
3) To 52-bit Subset sum problēmu var atrisināt laikā, kas proporcionāls 2^26.
4) Tā kā NP problēmas var pārveidot vienu otrā, tad IESPĒJAMS, ka arī SHA-1 problēmu var atrisināt laikā, kas proporcionāls 2^26. Man nav pieejams šāds algoritms (bet pieļauju, ka kādam ir). Lai NP problēmas pārveidotu no vienas uz otru arī ir jāpasvīst.
5) Kas attiecas uz dinamisko programmēšanu (DP), tad ar to šādas problēmas vispār risinās polinomālā laikā. Nelaime tikai tāda, ka ne visu var paņemt ar to DP. Tāpēc arī minēju par problēmas blīvumu. Savulaik tika izmantota viena kriptogrāfijas metode, kas bija bāzēta uz zema blīvuma subset-sum, bet ar DP to lauza zibenīgi, pofig 64, 128 vai 256 biti.

Nu un visbeidzot par 2^52 atrisināšanu nedēļas laikā uz mājas kompja.
- Nedēļā ir 7 dienas, katrā pa 24 stundām, katrā pa 60 minūtēm, katrā pa 60 sekundēm. Tātad nedēļā ir 604800 sekundes.
- 2^52 / 604800 = 7446427955, jeb aptuveni 7G operācijas.
- Moderni kompju taksts frekvence ir virs 3GHz, 4 kodoli dod 12GHz (jo šos uzdevumus var viegli palaist paralēlās plūsmās).
- 7G operācijas pret 12GHz ir samērojami lielumi.
- Modernam mājas kompim ir arī videokarte, kurā var ielādēt uzdevumu. (Reizēm tās videokartes rēķina ātrāk kā CPU.)

Manuprāt ar šiem aprēķiniem pietiek, lai saprastu, ka 2^52 var sarēķināt nedēļas laikā uz mājas kompja ar brute force.
Reāli, tā ir tukša diršana, ko tu mums te stāsti. Tur, kur cilvēkiem par šito arī maksā, nevis paši paņem, ir jau chipi iekšā ar vajadzīgajām instrukcijām, atlauž minūtēs.

Vispār komēdijas jau labās šeit ir, vajadzētu izveidot sadaļu "Nedēļas pērle", un tad katru mēnesi izvēlēties labāko ar balsošanu un dot balvas. Gada balva varētu arī būt kas nopietns, piemēram diskusija par problemātisko tematu ar d_l.

User avatar
KaNeiet
Lietpratējs
Atbildes: 234
Pievienojies: 01 Nov 2007, 00:50
Reputācija: 0
Atrodas: Talsi

Post no KaNeiet » 12 Jūn 2009, 18:07

ob1 wrote:->KaNeiet
Laikam būsi nepareizi mani sapratis.
Pavisam noteikti.
IESPĒJAMS, ka arī SHA-1 problēmu var atrisināt laikā
Starp sākumā lietoto "jebkuru", attiecinot to uz konkrēto gadījumu, un "Iespējams" ir ļoti būtiska atšķirība.
Iespējams, ka es jebkuru paroli uzminēšu pirmajā piegājienā, taču tam nav nekāda tieša sakara ar tās sarežģitību.

ob1
Reģistrēts lietotājs
Atbildes: 2959
Pievienojies: 23 Mar 2009, 22:01
Reputācija: 0
Atrodas: Sigulda

Post no ob1 » 12 Jūn 2009, 18:17

"jebkuru" - lietoju attiecībā uz NP problēmām un to pārveidošanu.
"Iespējams" - uz konkrēti SHA-1 iespēju atrisināt laikā 2^26

Neredzu es tur pretrunu, neredzu :) Mēģini pameklēt kādu citu manu kļūdu, ja tik ļoti gribi kasīties. :)

User avatar
WerNeo
Lietpratējs
Atbildes: 1802
Pievienojies: 14 Aug 2007, 01:27
Reputācija: 0

Post no WerNeo » 12 Jūn 2009, 18:29

Ar "Makarovu" un "Družbu" var ar pirmo izpildīt jebkuru nuždu. :) Tas, ja par parolēm runājam.

User avatar
KaNeiet
Lietpratējs
Atbildes: 234
Pievienojies: 01 Nov 2007, 00:50
Reputācija: 0
Atrodas: Talsi

Post no KaNeiet » 12 Jūn 2009, 18:41

Kaut kas ar acīm un ar atmiņu?
ob1 wrote:"jebkuru" - lietoju attiecībā uz NP problēmām un to pārveidošanu.
un
ob1 wrote:1) Jebkuru kriptogrāfijas problēmu var novest uz NP problēmu.
2) Jebkuru NP problēmu var pārvērst par citu NP problēmu.
Tur ir ne tikai "Jebkuru NP".

ob1
Reģistrēts lietotājs
Atbildes: 2959
Pievienojies: 23 Mar 2009, 22:01
Reputācija: 0
Atrodas: Sigulda

Post no ob1 » 12 Jūn 2009, 18:46

Viss man pietiks. :)

Vari tagad meklēt, analizēt, kasīties. Varbūt ķirzaks arī Tev palīdzēs...
:)

drunk_lizard
Mr. Positivus
Atbildes: 1892
Pievienojies: 19 Mar 2007, 18:09
Reputācija: 0

Post no drunk_lizard » 12 Jūn 2009, 19:07

ob1 wrote:eb aptuveni 7G operācijas.
- Moderni kompju taksts frekvence ir virs 3GHz, 4 kodoli dod 12GHz (jo šos uzdevumus var viegli palaist paralēlās plūsmās).
peerle peec peerles
turpini tik drukaat

ob1
Reģistrēts lietotājs
Atbildes: 2959
Pievienojies: 23 Mar 2009, 22:01
Reputācija: 0
Atrodas: Sigulda

Post no ob1 » 12 Jūn 2009, 19:08

Paldies, ķirzak, ka pārdomāji par to manu pazušanu no foruma, paldies!
:D

User avatar
Jaunzems
Reģistrēts lietotājs
Atbildes: 3935
Pievienojies: 20 Apr 2008, 12:19
Reputācija: 0

Post no Jaunzems » 12 Jūn 2009, 21:07

http://www.ob1.com/ - tava mājaslapa?

ob1
Reģistrēts lietotājs
Atbildes: 2959
Pievienojies: 23 Mar 2009, 22:01
Reputācija: 0
Atrodas: Sigulda

Post no ob1 » 12 Jūn 2009, 21:09

:D
Nē, bet paldies par ideju. Apsvēršu domu par ob1.lv
:D

Pievienot atbildi

Return to “IT ziņas”