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

[samurajs]

[imgl]https://notepad.lv/userpix/28_hash_1.jpg[/imgl]Kriptogrāfi (šifrēšanas speciālisti) atklājuši matemātisku paņēmienu, kā atvieglot šifrētas paroles "izvilkšanu" no tās md5-bāzētās kontrolsummas SHA-1-Hash-Codes. Līdz šim mēģināt atšifrēt paroli varēja tikai ar visiem zināmo BruteForce metodi. Vissliktākajā gadījumā paroles atšifrēšanai nāksies pārmalt 2[sup]63[/sup] dažādas iespējamās zīmju kombinācijas.

Zinātnieki šo skaitli tagad samazinājuši līdz 2[sup]52[/sup]. Tas tik un tā ir paliek milzīgs skaitlis. No otras puses - skaitļošanas tehnikas ātrumi nepārtraukti pieaug straujā tempā, un iespējams, ka pēc kāda laiciņa šādus kodus atlauzt vairs nebūs problēma.

Paredzot ka uz md5 veidotais standarts SHA-1-Hash-Codes vairs nebūs drošs, standartizēšanas institūti jau strādā pie jauna, 512 bitu koda līdzšinējo 160 bitu vietā.

Iepazīties ar atklājuma matemātisko principu var PDF dokumentā.

[APOC]

Tas ir tikai teorētiski vai arī praktiski panākts?

[drunk_lizard]

emm
rainbow tables izmantosjana?
kaapeec ne?
tikai - man interesee, kaa tiks biibeles md5 hash desjifreets :>

[Jaunzems]

Labi, labi, ka man vēl kompī mētājas datuvja DB dumps no pagājušā gada vasaras

[azazul]

tikai - man interesee, kaa tiks biibeles md5 hash desjifreets :>

Man domāt, ka tu zini - tas nav iespējams.
Bez tam, meklē jau mazāko īsāko iespējamo kolīziju =P

[nevertell]

Nu, tas ir 2 piecdesmit trešajā ir 4,503,599,627,270,496 ja itelefons nemelo. Cell's varēja ~2 miljardi aprēķinu sekundē, nu tad lai atkostu, vajadzēs 2,251,799.813685248 sekundes.

[izredzētais]

nevertell, no tiem skaitļiem man tagad visa galva griežās

[KaNeiet]

Ir nu gan no kā griezties - pie tam vēl no aplamiem. Grūti kaut google lodziņā 2^53 trāpīt? Tiesa, rakstā bija 2^52.

[ob1]

Hmm, 2^52 nav problēmas salauzt. Nu arī 2^64 nebija nekas īpašs.
Es tak teicu, ka P=NP.

[Jaunzems]

9007199254740992

[ob1]

Hmm, 2^52 - aptuveni nedēļa ar mājas kompi. Tikai parasti to 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. Un ja izmanto dinamisko programmēšanu, tad vispār on-the-fly.

[drunk_lizard]

juus mani salauzaat!
atziistos, ka mana parole visiem saitiem um ibankai ir 1

starp citu, runaajot par paroleem un datu drosjiibu....
smiekliigi ir izmantot dzimsjanas datumus... peedeejaa laikaa populari
patiesiibaa orgjinaalaakaa parole, ko esmu redzeejis ir 1q2w3e4r5t
dafiga atbilst visiem drosjas paroles kriteerijiem :>

[Jaunzems]

Bet ja izmanto obivena superkompi (tuned&optimised by... you Know Who...), vienā sekundē visu var izdarīt - iegūt paroles, ielogoties iegūtajos akkontos un piespamot pilnu datuvi ar atlauztajiem akkontiem par jaunajiem datorpasaules piedāvājumiem.
NOTTA BENE!!!! Vienā sekundē!!!!

[drunk_lizard]

Hmm, 2^52 - aptuveni nedēļa ar mājas kompi. Tikai parasti to 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. Un ja izmanto dinamisko programmēšanu, tad vispār on-the-fly.

aizver vienreiz muti!

[ob1]

http://en.wikipedia.org/wiki/Cryptographic
http://en.wikipedia.org/wiki/P_%3D_NP_problem
http://en.wikipedia.org/wiki/Subset_sum_problem
http://en.wikipedia.org/wiki/Dynamic_programming

Palasi, sapratīsi. (Tikai saites jāierauga, bet to jau laikam spēj tikai indigo?)

-> e.j.
Nē, daudz ātrāk, kā sekundē.

[KaNeiet]

parasti to 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

Komplektā ar saitēm, kas liek domāt, ka rakstīts nopietni, tas jau patiešām ir tā kā par traku un velk uz diagnozi.

[ob1]

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 each of these two arrays, which can be done in time O(2^N/2N). When arrays are sorted, the algorithm can check if an element of the first array and an element of the second array sum up to s in time O(2^N/2). To do that, the algorithm passes through the first array in decreasing order (starting at the largest element) and the second array in increasing order (starting at the smallest element). Whenever the sum of the current element in the first array and the current element in the second array is more than s, the algorithm moves to the next element in the first array. If it is less than s, the algorithm moves to the next element in the second array. If two elements with sum s are found, it stops. No better algorithm has been found since Horowitz and Sahni first published this algorithm in 1974[1].

Ja vēl nav skaidrības, tad prasi atpakaļ naudu no sava algoritmu teorijas pasniedzēja.

[KaNeiet]

slišal zvon...

Pielietojot rekursīvi (varbūt esi šo terminu dzirdējis) pietiekami daudz reižu iegūsim nevis reālo sarežģītības samazinājumu, bet kroku skaitu rakstītāja smadzenēs.


Negribi derības - došu jau minēto nedēļu laika mājas kompim, varēsi neiespringt uz dinamisko programmēšanu un citiem makaroniem, ko lētticīgajiem mēģini uz ausīm sakarināt? Vienkāršs rar arhīviņš. Izlasīsi tajā esošo tekstu - būsi uzvarējis.

[ob1]

Cik gara atslēga tam raram?

[KaNeiet]

Dafiga. Protams nekautrēšos izmantot arī dažādus alfabētus un simbolus.
Vispār kāda starpība - ja apgalvo, ka jebkura algoritma "pakāpes rādītāju var dalīt ar 2", pielieto to vairākkārtīgi un iegūsi 2^1.
Vienīgais kas mulsina - kā tie rakstā minēti nelaimīgie no 2^63 tikai līdz ^52 nonākuši - tak jau laikam neko no algoritmiem un dinamiskās programmēšanas nav jēguši un pie sliktiem pasniedzējiem mācijušies.

[drunk_lizard]

Cik gara atslēga tam raram?

18 centimetri

[ob1]

Pagaidām vairākkārtīgi to dalīšanu nasanāk izmantot, t.i. nav rekursīva algoritma uz pakāpi. (Bet es ticu ka būs kādreiz, strādāju pie tā.)

Savālēsi tam raram garo atslēgu, tad nebūs tur ne 2^32, ne 2^64, bet kādi 2^256 vai pat vairāk. Tad bez ķīniešu televizoriem neiztikt. (Kas kaut ko jēdz no kriptogrāfijas, tas sapratīsīs par tiem televizoriem.)

[drunk_lizard]

pa daudziem gadiem, attiistoties latvijas internetam, esmu daudz klaunus redzeejis. tomeer sjis... es nez...
bija reiz liidziigs - snake5 sevi deeveeja..
tiesa jams atzinaas, ka ir 13 gadus vecs...
tamponpuika, tas esi tu?

[ob1]

Piebildīšu vēl, ka jebkuru 64 bit subset sum problēmu uz 800MHz kompja varēja salauzt 22 stundās izmantojot to pakāpes dalīšanu. Ar dinamisko programmēšanu tas prasīja sekundes, ja vien netrāpījās smagā problēma ar augstu blīvumu.

[Jaunzems]

snake5 sevi dēvēja par uuuberkruto geimeri woot, bet šis - par optimizaizeri...

[KaNeiet]

Iespējams, taču kāds tam sakars ar rakstā apskatīto?

Cik saprotu, no derībām atsakies. Principā jau pareizi - bezcerīgi, jo arī šis gadījums ir no pavisam citas operas, ko, atšķirībā no sākotnējās putrošanās, laikam jau saproti.

[ob1]

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.
4) Subset sum 64 bit salaužās, kā jau minēju max 22 stundās uz 800MHz kompja.

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ē.

[ob1]

Hmm, visi kaut kur pazuduši.
Laikam studē algoritmu teoriju.
Iešu gulēt.

[drunk_lizard]

Jebkuru NP problēmu var pārvērst par citu NP problēmu.

iesaku pie sjii punkta arii palikt :> tas ir neapgaazjams kaa heopsa piramiida.
zini ko?
ej prom, vienkaarsji pazuudi
varbuut pieregjistree sevi ar citu segvaardu un vienkaarsji lasi
varbuut seedi un raksti savus "python" kodus
varbuut reklamee sevi ieksj siirupa, twittera, raibaa sunja...
varbuut saskrienaties ar sandi piereem..
es nezinu...
dari visu, ko gribi, bet beidz vienreiz gvelzt stulbiibas. tu traumee jau taa praataa vaajo jauno paaudzi.

[Mr.Death]

patiesiibaa orgjinaalaakaa parole, ko esmu redzeejis ir 1q2w3e4r5t
dafiga atbilst visiem drosjas paroles kriteerijiem :>

otrā oriģinālākā aiz paša qwerty

un attiecībā uz tēmu - kas par uztraukumu? ja nav curve_hands.dll vai kā tur viņ, tad jau var uztaisīt arī tā, ka sīkie ahūni krutie hakeri nemaz netiek pie tiem hashiem.

[Mr.Death]

Piebildīšu vēl, ka jebkuru 64 bit subset sum problēmu uz 800MHz kompja varēja salauzt 22 stundās izmantojot to pakāpes dalīšanu. Ar dinamisko programmēšanu tas prasīja sekundes, ja vien netrāpījās smagā problēma ar augstu blīvumu.

Lūdzu man dumjajam paskaidro, kas ir:

1) 64 bit subset sum
2) augsts blīvums (par šo es it īpaši gribētu dzirdēt skaidrojumu :>)

[ob1]

1) -> ķirzakam
NP-complete problems are studied because the ability to quickly verify solutions to a problem (NP) seems to correlate with the ability to quickly solve that problem (P). It is not known whether every problem in NP can be quickly solved—this is called the P = NP problem. But if any single problem in NP-complete can be solved quickly, then every problem in NP can also be quickly solved, because the definition of an NP-complete problem states that every problem in NP must be quickly reducible to every problem in NP-complete (that is, it can be reduced in polynomial time). Because of this, it is often said that the NP-complete problems are harder or more difficult than NP problems in general.
avots: http://en.wikipedia.org/wiki/NP-complete

2) -> Edgaram - kas ir 64 bit subset sum.
In computer science, the subset sum problem is an important problem in complexity theory and cryptography. The problem is this: given a set of integers, does the sum of some non-empty subset equal exactly zero? For example, given the set { −7, −3, −2, 5, 8}, the answer is YES because the subset { −3, −2, 5} sums to zero. The problem is NP-Complete.

64-bitu Subset sum problēma nozīmē, ka tiek dots 64 dimensiju vektors.
vaitāk šeit: http://en.wikipedia.org/wiki/Subset_sum_problem

3) -> Edgaram - augsts blīvums (Subset sum)
Angliski tas ir high density. Uzprasi gūgles tantei "subset sum density" un redzēsi, ka low density problēmas risinās salīdzinoši viegli.

Definīcija:
Definition 2.3 (Density). The density D of a subset sum instance with set A = {a1, . . . , an} is the ratio of
the size of the set A and the size of the largest element in it. D = n/ log2 (maxA), where maxA = maxi(ai).
Avots: http://www.cacr.math.uwaterloo.ca/techr ... 007-26.pdf

Iesaku arī palasīt programmētāju bībeli - The Art of Computer Programming.

Sorry, džeki, šodien būšu aizņemts, varēšu pieslēgties varbūt rīt.

P.S. Ķirzak, ir viens veids kā no manis tikt vaļā. Uztaisi aptauju. Ja vismaz 50% nobalsos, ka man ir jāaiziet, tad aiziešu.

[Morpheus]

imao, tatad ob1 saka ka var atlauzt md5? ooookeeei, man katram lietotajam parole tiek maksligi pagarinaata, un ne visiem vienaadi bet ar dazhadiem simboliem, piemeram princips pec niku lidzibas - ja niks ar S beidzas tad tads salts ja ar Z, tad cits. Saltā tiek izmantoti visi iespējamie simboli un cita draza, kas vien pieļaujama SQL pieprasijumos, salt sastāda 512b~ jeb simbolus + parole , nu tad atkod man tadu paroli ja ta parole pec atkoshanas neizskatisies pec paroles bet pec hashsumas kautka neloģiskā miksā


tobish ja tev sakuma bus 90487249732947283428
un beigas 298742784294298347 tu nepadomasi ka ta ir kļūda ne ka gala parole? gala parole vismaz tava galaa

[ob1]

"tatad ob1 saka ka var atlauzt md5?"
Tas tiek apgalvots rakstā. Es tikai veicu dažas matemātiskas manipulācijas, lai parādītu, ka 2^52 ir viegli atlaužams.

Ja vēlies, varu pastrādāt pie šīs problēmas dziļāk, bet tas būs dārgi. Bez 10kLs nav jēgas sākt.

[marr]

Vienīgais kas mulsina - kā tie rakstā minēti nelaimīgie no 2^63 tikai līdz ^52 nonākuši - tak jau laikam neko no algoritmiem un dinamiskās programmēšanas nav jēguši un pie sliktiem pasniedzējiem mācijušies.

Ja reiz esi Mr.Guru, kas mācījies pie tiem ūberkrutajiem pasniedzējiem, kas visu rubī, pastāsti mums, kur šajā akadēmiskajā rakstā ir problēma, uzraksti tam kritiku. Ja Tu nesaproti kā tieši šis rezultāts ir iegūts, tas nenozīmē, ka cilvēki neko nerubī no algoritmiem, gluži pretēji, iespējams tieši Tu esi tas, kurš sliktu pasniedzēju ietekmē esi pieņēmis, ka ir viena konkrēta patiesība un nekas cits nav iespējams. Un dinamiskā programmēšana šādu problēmu risināšanā ir vienīgais piegājiens tieši kāpēc?

[ob1]

1) Neesmu mācījies algoritmu teoriju pie pasniedzējiem, to apguvu pašmācības ceļā.
2) Vai tad es teicu, ka šajā rakstā ir problēma? Es tikai parādīju, ka 2^52 ir viegli salaužams.
3) Es nerakstīju, ka dinamiskā programmēšana ir VIENĪGAIS piegājiens. Doma bija tāda, ka, ja dinamiskā programmēšana nostrādās, tad uzlauzt var ļoti ātri. Š ajā gadījumā daudz kas ir atkarīgs no density, bet lai to (density) novērtētu, jāpatērē zināms laiks kura man šobrīd nav.

P.S. Taisnības cīnītāj! Kad būs atsaukums? (pats zini kam)
P.P.S. ok, ok, marr, jo vairāk mēs paskaidrosim, jo lielāka varbūtība, ka viņam pieleks.

[marr]

ob1, mans posts nebija adresēts Tev, bet gan KaNeiet (ko es mēģināju norādīt ar citātu sākumā ), kurš (pēc manas saprašanas) argumentē par to, ka raksts ir greizs.

[Morpheus]

Ob1 Es ceru ka tu saproti ka md5 hash ir vienādības rezultāts ar kuru vice-versa var iegūt tikai :P neko. Jo salīdzināt iespējams tikai 2 līdzvērtigas heshsummas. Bet iedomājies, cik daudz dažādu informacijas vienību ir pasaules alfabetā. Par ķīniešu rakstzimem nav nemaz runa. tas 2^62 ir tikai angļu alfabets un tur daži simboli, bet kas bus ar latviešu hešiem? pec manam domām tur variācija stipri jo stipri un ļoti ļoti talu parsniedz 2^62.


Un kā tad ar AES (64/128/256)? Kads izmanto?

[ob1]

-> Morpheus.
1) Ja kriptoanalīze parāda, ka problēma risinās 2^52, tad pofig ko Tu tur lieto, ķīniešu hieroglifus vai šumeru alfabētu.
2) Nav jau tā, ka jebkurš tagad varēs tos hešus lauzt, tas tomēr maksā samērā dārgi. Bet ir organizācijas, kam ir nauda un sēž džeki uz šādiem uzdevumiem. Man nosaukt vārdā šīš organizācijas vai pats sapratīsi?

[KaNeiet]

(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"

[drunk_lizard]

-> Morpheus.
Man nosaukt vārdā šīš organizācijas vai pats sapratīsi?

prieksj kam? visi taapat jau ir sapratusji, jo

Hmm, 2^52 - aptuveni nedēļa ar mājas kompi. Un ja izmanto dinamisko programmēšanu, tad vispār on-the-fly.

siguldas datorpasaulei ar taas Hiperionu drosji vien slaidi uzspljaut uz hesju dekripteesjanu.
iesaku piedaavaat savus pakalpojumus cip, fib, fdd un mossadam! it seviskji peedeejam, varbuut tev pat piedaavaas paarvaakties uz turieni....

[ob1]

Hmm, uz krieviem kādreiz strādāju (padomju laikā), bet vairs negribu - maksā ļoti maz.

[Morpheus]

muahahahahahahhaaa

ob1 tu gadijuma nesedi ložu necaursitamā konservu kārba un neesi viegli kontuzēts? no offense, tikai draudzigs jautajums

[ob1]

Kontūzija nav bijusi.
Par "ložu necaursitamā konservu kārba" nesapratu.

Jā, tagad jau par to drīkst runāt, noilgums pagājis un valsts ir cita ...

[drunk_lizard]

samuraj, luudzu nomaini man zemnika titulu dauzjebko iznjemot Lietpratējs. domaaju, ka neesmu pelniijis atrasties vienaa lietotaaju grupaa ar gjeeniju.

[ob1]

Paldies, ķirzak! Beidzot!

[Jaunzems]

d_l, pie e-žurnaļugām viena vakance vēl brīva

[karass]

Domāju šodien aiziet uz kino teātri kādu komēdīju pačolēt, bet izskatās ka tepat palikšu

[ob1]

Hmm, Varbūt ar Samuraju var sarunāt, lai uztaisa jaunu zemlinka titulu - "Jedi" ? Tad ķirzakam nekas nebūs jāmaina.

[M]

salt sastāda 512b~ jeb simbolus + parole

Un kāda no tā ir jēga? Tik pat labi tu tur vēl hd filmu vari piehešot klāt, bet vari paskaidrot, kā tas uzlabo drošību?