Uusi putkaposti on aiheeltaan ajankohtainen:
https://www.ohjelmointiputka.net/postit/tehtava.
Tehtävään liittyy myös vaikeampi erikoisputkaposti:
https://www.ohjelmointiputka.net/postit/tehtava.
putkaposti kirjoitti:
Uolevi ei pidä MD5-funktiosta, koska se tuottaa yleensä rumia tiivisteitä: numeroita ja kirjaimia on niissä sekaisin vailla esteettisiä arvoja.
On ne ihan puhtaasti lukuja, heksajärjestelmässä.
Tehtävässä pitäisi kertoa, mitä merkkejä salasana saa sisältää. Ilmeisesti ainakaan välilyönnit eivät kelpaa.
Periaatteessa kaikki merkit kelpaavat, mutta sanan ympärillä olevat välilyönnit poistetaan.
Viikko on kulunut, mutta pelkistä kirjaimista muodostuva tiiviste on vielä löytämättä. Tehtävä vaikuttaa olevan haastava, vaikka sopivia tiivisteitä on 6^32 = 7958661109946400884391936.
Vaikka sopivia tiivisteitä onkin noin paljon, niin yhteensähän tiivisteitä on vielä moninkertaisesti enemmän. 6^32/16^32 on noin 2,3*10^(-14), joten sopivat tiivisteet muodostavat vain hyvin pienen osan kaikista tiivisteitä.
Edelleen voidaan laskea, että jokaista pelkästään kirjaimista koostuvaa tiivistettä kohden on siis noin 4,3*10^13 tiivistettä, jotka eivät koostu pelkästään kirjaimista. Läpikäytävää siis riittää, jotta olisi edes tilastollisesti todennäköistä löytää sopiva osuma.
Itse odottelen, että milloin piinkovassa salasanassa joku saavuttaa 32 pistettä :D En tosin pidätä hengitystä.
Jo piin yhdettätoista numeroa saadaan odotella teoriassa lähes yhtä kauan kuin pelkistä kirjaimista koostuvaa tiivistettä, joten täydelliseen ratkaisuun lienee matkaa. :)
Millaisia ideoita käytätte? Oma optimoitu hakualgoritmini käyttää GNU-työkalujen md5-toteutuksesta muokattua versiota, josta on poistettu turhat funktiokutsut ja jossa datan koko on rajoitettu yhteen blokkiin eli salasana on enintään 55 tavua. Kohta on 627 eli 3521614606208 eli 3,5 biljoonaa salasanaa kokeiltu, tosin nykyiset tulokset tulivat jo aikoja sitten. Tuskinpa jaksan tuosta enää jatkaa.
Minulla on myös ohjelma, joka osaa muodostaa kullekin tiivisteen bitille lausekkeen, jossa käytetään syötteen bittejä ja loogisia operaattoreita (supistettavissa operaatioiksi "ei" ja "ja"). Jollain tällaisten lausekkeiden loogiseen optimointiin kykenevällä systeemillä voisi saada jopa jonkinlaisia tuloksia aikaan; lauseke näytti sisältävän jonkin verran osia, joiden tuloksen voi jopa arvata ennalta ("a tai ei a" ja mutkikkaampia vastaavia) tai joita ainakin voisi lyhentää huomattavasti. Käsin käsiteltäväksi dataa on kuitenkin aivan liikaa.
Täälläkin päin optimoitu md5-algoritmia yhtä pakettia varten, inspiraationa GNU:n sijaan tosin OpenSSL-toteutus (melko samaltahan nuo näyttävät, nyt kun tuli molempia vilkaistua).
Saavutettu nopeushyöty raakalaskennassa noin 33 %. Suorituskyvyn parannus oli kyllä ennakoitavissa, mutta ei oman toteutuksen pääasiallinen motivaattori – itse on tässä nimittäin pitänyt jo pidemmän aikaa kokeilla GPGPU-laskentaa, mutta täytyy myöntää etten ole saanut juuri mitään aikaiseksi; osittain ehkäpä siksi että tietyistä syistä tässä tulisi turvautua Windows-ympäristöön. Joka tapauksessa sinänsä mielenkiintoista nähdä, minkälaisia suorituskykyetuja GPU tarjoaa ongelmassa, joka on hyvin parallelisoituva mutta ei toisaalta käpistele epätarkkoja liukulukuja. Ehkä minä vielä jonain päivänä...
Jos tulokset eivät parane nykyisestä, harkinnassa on tiivisteen etsiminen yhteisvoimin SETI@home-projektin tapaan. Tällöin halukkaiden putkalaisten koneet käyvät tiivisteitä läpi järjestyksessä. Jos esim. sata henkilöä osallistuu projektiin, tiiviste löytyy sata kertaa nopeammin.
Antti Laaksonen kirjoitti:
Jos tulokset eivät parane nykyisestä, harkinnassa on tiivisteen etsiminen yhteisvoimin SETI@home-projektin tapaan. Tällöin halukkaiden putkalaisten koneet käyvät tiivisteitä läpi järjestyksessä. Jos esim. sata henkilöä osallistuu projektiin, tiiviste löytyy sata kertaa nopeammin.
Mulla on kaksi konetta, jotka voin luovuttaa 24/7 tähän projektiin. oon intissä ja lomilla muualla, niin eivät ole käytössä lähes ollenkaan. Toisessa E8400 ja toisessa Q9550 ;). Täällä intis ois pino missä on 10kpl jotain pena4 koneita. nekin voin laittaa verkkoon pienellä varauksella jos on tarvetta.
i7 ilmoittautuu :)
Vanha 8800GTS raksuttaa parhaillaan 137MHash/s. Katsotaan josko toi alpha hashi löytyisi viikon sisällä. Pitäisi varmaan käydä ostamassa pari uutta fermiä :)
Itsellä kaksi konetta annettavana Intel i7 ja Intel Atom N330 prossuilla varustettuna, vaikkakaan kaikkia tehoja en noista voi antaa yhtäjaksoisesti käyttöön, viikonloppuina taas voivat raksuttaa yhteenputkeen tätä.
Jos herroilla valmista koodia niin jakamaan alueita ja koodia. ;) toki joku taitavampi voi tehdä seti @ home tyyppisen ratkaisun meille?
eddebbedbfbedacbbddcabfddfaedeaf
Multakin saa phenom 2:sen tehoja lainaan tarvittaessa... :)
FooBat + 8800GTS ehti sitten edelle, ei ole vielä löytynyt edes 10 mittaista, vaikka Athlon II X4 onkin jauhanut tasaisen tappavaa 20 MHash/s (5 MHash/s/ydin) nopeutta jo toista päivää... Kyllä nuo GPGPU-laskentayksiköt ovat (liian) eteviä...
PS. FooBatilla piti mennä tuohon odotusarvoisesti melkein neljä päivää, minulla noin kuukausi joten tulos ei liene yllätys. Pitäisiköhän suunnata kaupan kautta...
FooBat kirjoitti:
eddebbedbfbedacbbddcabfddfaedeaf
Hieno suoritus!
Kiitos myös kaikille laskutehoa luvanneille. Yksi mahdollinen projekti voisi olla etsiä palindromitiiviste (tiiviste on sama alusta loppuun ja lopusta alkuun luettuna).
Antti Laaksonen kirjoitti:
FooBat kirjoitti:
eddebbedbfbedacbbddcabfddfaedeaf
Hieno suoritus!
Kiitos myös kaikille laskutehoa luvanneille. Yksi mahdollinen projekti voisi olla etsiä palindromitiiviste (tiiviste on sama alusta loppuun ja lopusta alkuun luettuna).
Onhan meillä vielä se piinkova suoritus tekemättä.
tkok kirjoitti:
Onhan meillä vielä se piinkova suoritus tekemättä.
Sen voi jättää yksin yritettäväksi ja keskittää yhteinen ponnistus johonkin muuhun, vaikka tuohon Antin mainitsemaan palindromiin. Ehkä joku vielä keksii MD5:n teoriasta keinon, jolla löytyy paljon nykyisiä parempi vastaus.
Tai voidaan tehdä vastaavaa vaikeammilla tiivitefunktioilla kuten SHA:lla. elämänSisältö++
L2-K2 kirjoitti:
PS. FooBatilla piti mennä tuohon odotusarvoisesti melkein neljä päivää, minulla noin kuukausi joten tulos ei liene yllätys. Pitäisiköhän suunnata kaupan kautta...
Noin kanssa laskeskelin, löytyi lopulta noin 22 tunnissa.
Antti Laaksonen kirjoitti:
FooBat kirjoitti:
eddebbedbfbedacbbddcabfddfaedeaf
Hieno suoritus!
Oma kontribuutio jäi kyllä aika vähäiseksi. Valitsin vain oikeat työkalut ja modasin jonkun muun tekemää CUDA md5 crack ohjelmaa tehtävään sopivaksi. Tämä oli sinänsä ihan kiva tehtävä, että tuli nyt ensimmäisen kerran tarve asentaa CUDA ympäristö ja tutkia miten se toimii. Nopeusetu on sen verran merkittävä, että pitää varmaan tutustua paremmin ja jatkossakin käyttää.
96892653410635380397243618793891 eli täydet, löyty aika nopeesti, ehkä 10min meni. Kirjaimet odottaa löytämistään.
ac0eeeefaadf1ad1daeeebebd2cadafe, 28 merkkiä
Koneena on tällä hetkellä rupunen 1.5 gigahertsin läppäri joten kovin nopeaa numeronmurskausta tällä ei tehdä.
Kun ei ole tehokasta NV-näyttistä, pitää turvautua muihin menetelmiin: arvioin FooBatin antamista tiedoista (hakunopeus ja käytetty aika), mihin salasana suunnilleen voisi sijoittua, ja sieltähän se ratkaisu aika nopeasti löytyikin. :)
Masfonos kirjoitti:
löyty aika nopeesti, ehkä 10min meni
Oikealla strategialla (ja kunnollisella C-toteutuksella) pelkistä numeroista koostuva tiiviste löytyy helposti parissa sekunnissa huonollakin koneella. Näitä tiivisteitä on sentään 12,6 miljoonaa kertaa niin paljon kuin pelkistä kirjaimista koostuvia, mistä taas voidaan arvioida, että jos ensimmäinen numerotiiviste löytyy sekunnissa, kirjaintiivistettä saa ehkä odotella viitisen kuukautta.
Metabolix kirjoitti:
Kun ei ole tehokasta NV-näyttistä, pitää turvautua muihin menetelmiin: arvioin FooBatin antamista tiedoista (hakunopeus ja käytetty aika), mihin salasana suunnilleen voisi sijoittua, ja sieltähän se ratkaisu aika nopeasti löytyikin. :)
Pitäisiköhän itsekin suunnata samoille apajille... pitäisi vain keksiä minkä muotoisten salasanojen joukosta FooBat niitä etsi... itse löysin vasta ensimmäisen 10 desimaalia piistä antavan hashin, odotusarvoisesti niitä olisi pitänyt löytyä jo 3...
Otin samalla haasteeksi palindromi-hashin löytämisen.
326b502ee1af952c562d4025f205b623 - 7 merkkiä puoleen toiseen.
Taisi käydä tuuri, kun ensimmäinen löytämäni 11 desimaalin pii olikin 12 desimaalin yksilö. Taidan lopettaa tähän, kun 13 desimaalin hashin löytämiseen pitäisi mennä puolisen vuotta.
Sarjassamme turhia numeroita, jatkan edelleen tätä höpsöä juttua. Palindromi-hash: 0048b869e91e21330cc87d3e968b8400. Edellisestä parannettu 2 merkkiä, yhteensä siis 9.
Hei,
tuli tuossa "vähän" yritettyä tätä ongelmaa ratkaista. Tarkalleen ottaen sellaiset vähän vajaa kahdeksan biljoonaa yritystä.
Havaintoja tästä otoksesta:
Yksi prosessoriydin pystyy noin 4 - 5 miljoonaan hajautukseen sekunnissa.
8 piin desimaalia sisältäviä löytyi 1669, odotusarvo näiden määrälle oli noin 1700.
9 piin desimaalia sisältäviä löytyi 101, odotusarvo oli noin 100.
10 piin desimaalia sisältäviä löytyi 6, odotusarvo oli noin 7.
11 piin desimaalia sisältäviä löytyi 2, odotusarvo oli noin 0,4.
12 tai useamman desimaalin sisältäviä ei löytynyt, odotusarvo oli noin 0,03.
31 kirjaimen hajautuksia löytyi 8, odotusarvo oli noin 10.
32 kirjaimen hajautuksia ei löytynyt, odotusarvo oli noin 0,2.
Aihe on jo aika vanha, joten et voi enää vastata siihen.