2017-11-06 задача

by Vasil Kolev

(по-подробно за феста – като се наспя)

За OpenFest 2017 за щанда на StorPool бях написал една задача, та който я реши, да получи тениска. Задачата звучи измамно просто и аз също не съм се усетил, че не е лесно решима за 10 минути.

Задачата е следната – имате директория с някакво количество файлове, да видите кои от тях са MD5 и кои – SHA1 колизии, и да дадете първите букви от имената им (4 файла за md5 и 4 за sha1). Моето решение беше във временна директория да се направят файлове с имена MD5 (и после – SHA1) сумите, в които да се напишат имената и SHA256 сумите на файловете с тая MD5 сума, и после с един sort на всеки файл лесно се вижда в кой има различни файлове (трябва да са еднакви по принцип). Ако е просто да се види коя е md5 сумата, може да се броят уникалните sha256 суми във всички файлове, да се види къде са колизиите.

Интересно ще ми е наистина ли е толкова трудна задачата (доколкото знам, за два дни само един човек я е решил за 10 минути).

Също така ми е интересно дали някой не е решил да пита google какви са checksum-ите на демонстрационните sha1/md5 колизии и да види дали аз не съм си събрал файловете по тоя начин…

Кодът, който генерира задачата е качен на https://vasil.ludost.net/progs/storpool-of-task.tgz. Вътре има gen.sh, който трябва да се пипне малко къде да прави файловете и който при пускане създава малко файлове и ви дава отговора. Не съм сложил другите неща (това, което се прави на login shell и нещото, което праща отговорите по slack на проверяващия), но те не са толкова интересни.

Tags: ,

2 Responses to “2017-11-06 задача”

  1. Димо Димов Says:

    Първо благодаря за удоволствието :) да чета тук неща, които съм искал да напиша аз, но не съм знаел как!
    До щанда на StorPool, а и до някои други щандове, не можах да стигна, макар че бях планувал да поговоря по 10 мин с представители на всички спонсори. Не ми стигна времето. Иначе задачата е много интересна и аз с удоволствие бих опитал да я реша, но нямаше да успея за 10 минути.
    А освен това задачата е хубава, защото ми напомня за една практическа задача, която възниква на големите “корпоративни” файлови сървъри, където потребителите не са в най-старателното си настроение:
    Дадена е една голяма директория, която съдържа и много еднакви по съдържание файлове, и понякога цели поддървета с еднакво съдържание и само различни имена на директорията (началото) на поддървото. Да се състави списък на всички дублиращи, с по-късна дата, поддървета, както и файлове ако не са част от по-голямо дублиращо поддърво. Няколко файла са тестови на сисадмини и програмисти и са с SHA1 колизии. Еднаквите поддървета с колизии да се изведат отделно (за да се види, кой друг във фирмата работи и по странични, извън официалните си задачи :) ).

  2. Димо Димов Says:

    Поправка. Последното изречение да се чете:
    Поддървета с файлове с колизии, които са еднакви с файлове другаде в директорията, да се изведат отделно.

Leave a Reply