Kirjautuminen
Tehtävät
Kilpailu
5. kierros:
28.11. klo 18 – 30.11. klo 23
Ensimmäinen Putkaposti julkaistiin vuonna 2005. Viisi vuotta myöhemmin ongelmia oli jo 42 (plus kolme b-tehtävää) ja Antti listasi Putkapostin avoimia ongelmia. Jotkut ratkovat näitä vielä tänäkin päivänä ja päätin tehdä 20v-juhlavuoden kunniaksi päivitetyn listan, jossa on Antin listaamien ongelmien nykyinen tilanne (omien tietojeni mukaan) ja muutama aiemman listan jälkeen julkaistu tehtävä.
15: Kielitiedettä (avoin)
Ennätystä pystynee vielä parantamaan.
19: Älykäs robotti (ratkaistu)
Tuloksen 29 voi osoittaa optimaaliseksi yllättävän pienellä laskentamäärällä. Ratkaisin muistaakseni myös 4x5-ruudukon, mutta 5x5 oli vanhalle koodilleni liian vaikea.
29: Käänteislauseke (avoin)
Nykyinen 111 tuskin on paras mahdollinen.
Algoritmi-ideoita voi testata ratkomalla helpompia versioita. SL-haasteen tehtävä 5.8 on samantapainen ja isashkar ja zebraze paransivat sen ennätystä ihan hiljattain!
30b: Ahdas ruudukko 2 (avoin)
Hakuavaruus on valtava eikä ole mitään syytä olettaa, että 112 olisi viimeinen sana.
Avoin kysymys on myös, onko 116 = 4x29 mahdollinen.
35: Peilauskomento (ratkaistu)
Tämän voi varmaan ratkaista alle sekunnissa. Paras tietämäni aikakompleksisuus on O(N * log(N) * 2^N).
37: Kaulaketju (ratkaistu)
Tulosta 72 ei voi parantaa ja oleellisesti erilaisia ratkaisuja on 5.
Jos kaulaketjun pituus olisi 50 merkkiä, optimaalinen tulos olisi 90 sanaa.
Jos kaulaketjun pituus olisi 56 merkkiä, siihen mahtuisi jo 100 sanaa.
Seuraavat tehtävät julkaistiin vasta Antin listan jälkeen:
45: Lottovoitto (avoin?)
En tiedä, tai ainakaan en osaa itse todistaa, onko tulos optimaalinen.
47: Lukulauseke (avoin)
Yllättyisin, jos tätä voisi parantaa, mutta regexit ovat yllättäneet ennenkin.
48: Triplatulkinta (avoin)
Käytin heuristista hakualgoritmia.
Lupaan tarjota pullakahvit sille joka ratkaisee MD5 tehtävän 20merkkisen sanan.
wy5vn kirjoitti:
Lupaan tarjota pullakahvit sille joka ratkaisee MD5 tehtävän 20merkkisen sanan.
Aika riskitön lupaus :D
Itse laskeskelin niitä silloin 2011 silloisen tietokoneeni GPU:lla (joka oli ajan nopein kuluttaja-GPU tiivisteiden laskentaan), ja 11 merkin salasanassa kesti 40 tuntia. Eli jos ajatellaan että nykyiset näytönohjaimet (tai muut käytössä olevat välineet) olisi 26 kertaa nopeampia niin 12 merkkisen murtamiseen menisi 40 tuntia ja 20 merkkisen murtamiseen n. miljardi vuotta.
Toki jos keksisi bruteforcausta tehokkaamman algoritmin, niin tilanne voisi muuttua, mutta tällaista ei tietääkseni ole ainakaan julkisesti tunnettu.
Kyllä. Tiedettävästi edes kvanttitietokoneella tuota ei alle 100miljoonassa vuodessa saisi ratkaistua. Sen perusteella mitä niiden laskentatehosta tällä hetkellä tiedetään.
Kiitos raportista! Näissä riittää vielä ratkomista ja kiinnostavaa nähdä, miten tehtävien tilanne kehittyy tulevaisuudessa.
jlaire kirjoitti:
Algoritmi-ideoita voi testata ratkomalla helpompia versioita. SL-haasteen tehtävä 5.8 on samantapainen ja isashkar ja zebraze paransivat sen ennätystä ihan hiljattain!
Kiinnostavaa, en ollut huomannut tätä. Hienoa, että myös SL-haasteen tuloksissa tapahtuu kehitystä.
wy5vn kirjoitti:
Lupaan tarjota pullakahvit sille joka ratkaisee MD5 tehtävän 20merkkisen sanan.
Tässä tehtävässä kehitys on ollut hidasta. Voin parantaa tarjousta ja tarjota pullakahvit sille, joka saa ensimmäisenä tuloksen 12.
jlaire kirjoitti:
30b: Ahdas ruudukko 2 (avoin)
Hakuavaruus on valtava eikä ole mitään syytä olettaa, että 112 olisi viimeinen sana.
Avoin kysymys on myös, onko 116 = 4x29 mahdollinen.
En ole näitä enää jaksanut miettiä. Mitenkähän toimisi, jos tuosta tekisi sopivan SAT-ongelman ja koettaisi pistää sen johonkin ratkaisijaan? Sätkäpeten mukaan tämän voisi ratkaista viikossa tai kuukausista, jos optimoisi rajoitteita ja laittaisi tehokkaan ratkaisijan jauhamaan.
Pienempi tapaus, esimerkiksi lukujen 1–25 neliöiden pakkaaminen, onnistuu SAT- tai SMT-ratkaisijalta helposti. Omien kokeilujeni mukaan 1–100 on kuitenkin aivan liian suuri ongelma sellaisenaan SMT-ratkojalle syötettäväksi, mutta ehkäpä en osannut optimoida rajoitteita tarpeeksi hyvin.
Parhaatkaan kielimallit eivät kuulemma osaa ratkaista edes Kaulaketjua, vaikka se on huomattavasti helpompi tehtävä kuin Ahdas ruudukko 2.
MD5 -tehtävä on kestänyt hyvin ajan kulun. Jopa tekoäly kieltäytyy auttamasta tässä tehtävässä. Sain siltä c++ koodin, joka kuitenkin osottautui huomattavasti hitaammaksi kuin vastaava Java -koodi! Hashcat -ohjelmaa en saanut pelaamaan, mistäköhän löytyy manuaali oikeiden parametrien keksimiseksi?
Itse testasin John the Ripperiä ja hashcattia. Toki c++ toimii kanssa mutta vaatisi hiukan opettelua että saisi sen bruteforce algoritmin pyörimään näytönohjaimella. Nuo edellämainitut ohjelmat toimivat hyvin, hascatilla tosin oli ainakin ongelmia ääkkösten kanssa. toisaalta niitä ei ainakaan 0-7 merkkisissä salasanoissa ollut niin ehkä laitain sen jauhamaan tuota 12merkkistä jossain vaiheessa kun sähkö on halpaa.
Tehtävään md5h oikea hashcat-komento on:
hashcat --potfile-path=md5h-tulokset.txt -m0 -O -a3 tiiviste kaava
Tässä tiiviste on yksittäinen tiiviste tiedostosta (ei kannata hakea kaikkia tiivisteitä samaan aikaan, koska niissä on tunnetusti eripituiset salasanat), ja kaavassa ?l tarkoittaa yhtä merkkiä a-z, eli kaava on ratkaistavan salasanan pituuden mukaan ?l?l?l?l?l...
Netistä löytyy, että esimerkiksi GeForce RTX 4090 laskee noin 150 miljardia tiivistettä sekunnissa, jolloin 12-merkkinen salasana (merkeistä a-z) löytyy alle 8 päivässä. Jos siis sattuu omistamaan hyvän pelikoneen ja lämmittämään kotia muutenkin sähköpattereilla, tuon 12-merkkisen voi ratkaista talvipakkasilla käytännössä ilmaiseksi. NVIDIA L40S on aika samoissa nopeuksissa, joten pilvipalvelussa 12 pisteen ratkaisu maksaa keskimäärin 200 euroa ja huonolla tuurilla 400 euroa, riippuen, missä kohti hakua osuma tulee.
Metabolix kirjoitti:
kaavassa ?l tarkoittaa yhtä merkkiä a-z, eli kaava on ratkaistavan salasanan pituuden mukaan ?l?l?l?l?l...
Sillä olettamalla ettei ole ääkkösiä. Ei nyt liity tähän välttämättä mutta ihan mielenkiinnosta, onko tuossa hascatissa mahdollista ottaa ääkköset mukaan?
wy5vn kirjoitti:
ihan mielenkiinnosta, onko tuossa hascatissa mahdollista ottaa ääkköset mukaan?
Siinä on mahdollista määritellä ihan mikä tahansa haluttu merkkijoukko haettavaksi.
Metabolix kirjoitti:
Netistä löytyy, että esimerkiksi GeForce RTX 4090 laskee noin 150 miljardia tiivistettä sekunnissa, jolloin 12-merkkinen salasana (merkeistä a-z) löytyy alle 8 päivässä. Jos siis sattuu omistamaan hyvän pelikoneen ja lämmittämään kotia muutenkin sähköpattereilla, tuon 12-merkkisen voi ratkaista talvipakkasilla käytännössä ilmaiseksi. NVIDIA L40S on aika samoissa nopeuksissa, joten pilvipalvelussa 12 pisteen ratkaisu maksaa keskimäärin 200 euroa ja huonolla tuurilla 400 euroa, riippuen, missä kohti hakua osuma tulee.
Hämmentävän kallista toi pilvilaskenta.
Geforce RTX 4090:llä menisi siis noin 115 kWh eli parin kympin edestä sähköä (siirrot ja verot mukana) niin miksi pilvilaskenta maksaa 10 kertaa enemmän :o
Itsellä meni 14vuotta sitten siloisella näytönohjaimella noin 12 kWh sähköä eli noin 2 euroa 11 pisteen ratkaisuun, eli eipä oo Hash/W hirveästi kasvanut noin 12 vuodessa, jos kerran vain n. 2,5 kertaiseksi.
wy5vn kirjoitti:
(24.11.2025 18:59:46): ”– –” Sillä olettamalla ettei ole ääkkösiä. Ei nyt...
Se on hyvä oletus tehtävänannon huomioiden. Ääkkösissä on merkistökysymyksiä ja näyttää, että hashcat ei käsittele niitä kaikissa muodoissaan ainakaan ihan helposti.
Grez kirjoitti:
Hämmentävän kallista toi pilvilaskenta.
Pilvessä hintaan sisältyy myös massiivisesti muistia ja levytilaa. Ainakaan omalta tarjoajalta ei löydy "pelkkää" GPU:ta.
Metabolix kirjoitti:
(24.11.2025 20:02:46): ”– –” Se on hyvä oletus tehtävänannon huomioiden...
Vahvistaa käsitystä siitä että kannattaa laittaa niitä salasanoihin🤔
wy5vn kirjoitti:
Vahvistaa käsitystä siitä että kannattaa laittaa niitä salasanoihin🤔
Hashcatin käytölle on tosielämässä tehokkaampia ja edullisempia vaihtoehtoja, joihin salasanan pituus tai merkistö ei auta.
Metabolix kirjoitti:
Tehtävään md5h oikea hashcat-komento on:
hashcat --potfile-path=md5h-tulokset.txt -m0 -O -a3 tiiviste kaava...
Kiitokset! Nyt lähti pelittämään! 8 merkin pituinen salasana ratkesi brutal forcella 7:ssä sekunnissa. Ja minulla on vaan GeForce RTX 3050 Mobile käytössä. Lämpötila vaan alkaa kohoamaan (63°C -> 68°C tämän ajon aikana).