Re: lug-bg: md5 digest + openssl

[Vesselin Kolev <vlk@xxxxxxxxxxxxxxxxx>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Nick Angelow wrote:

| Vesselin Kolev wrote:
|
| не знам дали си го видял това -- брус шнайер твърди, че sha1 вече е
|  пробита ("SHA-1 has been broken. Not a reduced-round version. Not
| a simplified version. The real thing."). публикувано е на 15
| февруари тази година.
| http://www.schneier.com/blog/archives/2005/02/sha1_broken.html
|
| така, че май ще е най-добре да се следва съвета ти, описан малко
| по-надолу.
|

Големи буквалисти са хората.

Най-редовно следя блога на Шнайер. Даже имам и копие от статията на
въпросните китайци, които са извършили пробива. Да, SHA-1 е счупена,
защото е намерен начин за редукция на броя търсения за намиране на
колизия. При това тази редукция е направена алгоритмична. Обаче, защо
всеки не вникне и не разбере, че не става дума за смислена колизия?
Реагирате като читатели на вестник "24 часа".

Пак ще се наложи да обяснявам за да няма повече подобни паники.
Накратко и схематично за да го разбере всеки.


Какво е хеш функция?

Хеш функцията е такава функция, която съпоставя на блок с информация с
произволна дължина (до някаква горна граница) еднозначно число с
фиксирана (постоянна) дължина. Това число е известно като хеш. За
какво служи този хеш. Най-образно си представете файл. Пресметнали сте
хеша на информацията в този файл и сте си го записали някъде. След
известно време искате да проверите файла (дали е променян). Отново
изчислявате хеша и го ставнявате с предишния. Ако всичко е наред,
двата хеша трябва да са едни и същи (по-правилно е да се каже, че са
равни, защото те са числа).


Какво е колизия?

Няма хеш функция без колизия. Два блока с информация са в колизия, ако
те се различават по съдържание, но имат един и същи хеш. Не е
задължително блоковете да са два - може да са и повече. Една хеш
функция е под заплаха (но все още тази заплаха може да не е голяма,
чети следващия абзац), ако се намери начин за контролирано намиране на
колизия (т.е. да се намери алгоритъм, който е повторим и по зададен
изходен блок от информация и неговия хеш, той да позволява да се
изчисли друг блок информация, който има същия хеш). Не да се намери
случайно колизия и да се каже "алгоритъма е разбит" - това е като да
спечелиш на тото. Досега колизии се търсеха почти на принципа на
атаката с груба сила - генерираш докато получиш. Такива търсения не са
алгоритмични. Те разчитат напълно на случайни процеси и затова са
ужасно енергоемки и бавни. В статията, която Шнайер цитира, се показва
алгоритъм (наблегнете на думата "алгоритъм", това не е случайно
търсене), с който броят търсения могат да бъдат намалени драстично
(макар и не достатъчно). За това той казва, че SHA-1 е разбита -
защото е намерен алгоритъм за редукция.


Кога една колизия е смислена?

Много внимателно прочетете това. То именно касае това, което се нарича
"реална заплаха" за всеки потребител. В нея става дума за смислената
колизия, която е различна от произволната колизия.

Какво значи двата блока да са в смислената колизия? Това означава
двата (или повече) блока, които са в колизия, да си приличат или
казано по друг начин, имайки един блок, вие да намерите друг (в
колизия с първия), който да прилича на първия по някакъв признак -
например по дължина. Да се върнем на файловете за да видите какво
значи смисленост на колизията. В него пише "проба 1 2 3". Смислена
колизия може да е тази, която примерно да ви позволи да генерирате
друг файл, в който "проба 1 2 3" да е заменено с "проба 2 3 4".


Кое е податливо и кое не на смислена колизия?

Давам ви реална представа защо не може да има колизия в системата за
удостоверяване базирана на MD5 хеширащата функция (и която се използва
в UNIX и Linux). Вие въвеждате парола с произволен брой символи
(разбира се до някаква горна граница). След това инструмент, подобен
на md5sum, изчислява MD5 хеша на тази парола и я слага във файла
/etc/shadow. Когато вие са удостоверявате впоследствие, един модул
кешира паролата, която сте подали в паметта на машината, изчислява
хеша й и го сравнява с този във файла. Ако има съвпадение, то се
приема, че вие сте въвели правилната парола и получавате права за достъп.

Ако сега някой успее само по информация за хеша, да пресметне само
един блок от информация, който да съответства на хеша, той е успял да
извърши атака на грубата сила върху хеша и да намери паролата.
Забележете обаче, че това още не е колизия, защото той няма
оригиналния блок от който е произведен хеша и не знае дали не е
намерил втори блок, който е в колизия с оригиналния (и не знае дали
има колизия). Това е като някой да ви е завел с пещера със завързани
очи, да ви пусне и вие да намерите един изход - вие не знаете дали има
още изходи, защото не знаете през кой изход сте влязли.

Съгласете се и с факта, че ако някой търси колизия на парола от 6
символа и намерената колизия е от 345678 символа, то тя е напълно
неизползваема. Същото е и с файл. Ако търсите колизия на изпълним
файл, вие ще намерите колизия, която няма да може изобщо да се
изпълни. За какво ви е тогава тя?

MAC и по-специално модификацията му HMAC е неподатлив на колизия
алгоритъм. Пак обяснявам защо, съвсем схематично и нагледно. При HMAC
вие имате ключ и блок информация и хеширащ алгоритъм. Действате по
следната схема (силно опростена, който се интересува за повече
детайли, да погледне RFC2104). Конкатенирате по някакъв алгоритъм
ключа с блока и пресмятате хеша (примерно с MD5). После пращате блока
+ хеша по някой и той проверява блока по същата схема, но имайки при
себе си ключа (сравнява дали двата хеша са равни). И защо не можем да
имаме колизия. Колизия не можем да имаме, защото не знаем изходния
блок (нали сме го конкатенирали с ключа, който знаят само подателя и
получателя на блока+хеша) и имаме неопределеност. Следователно можем
да провеждаме само атака на груба сила, но не и алгоритмична атака за
колизия. Примерно PKCS#12 форматните файлове, произвеждани от
по-старите версии на Interne Exploret и други MS софтуери  (за работа
с MAC към формата PKCS#12 се използва същия симетричен ключ, който
защитава частния RSA или DSA ключ)  и това е доста слаба страна на
формата. За да се избегне това се ползват итерации, които MS не
ползваха въпреки слабия симетричен криптоалгоритъм RC-40. В новите
версии това е оправено (най-накрая!!!). Това не засяга HMAC
(забележете това).


Какво още трябва да знаем?

Трябва да знаем, че поне досегашните изследвания показват, че не във
всеки блок информация има колизия и че колизията е функция на блока с
информация. Това още повече усложнява използването на колизиите за атака.


Това е. Преди да кажем нещо по темата, трябва да сме много сигурни в
казаното, а не да всяваме паника във вестникарски стил.


~   Поздрави
~      Весо


PS Лично аз, за последен път се опитвам да обясня тези проблеми.
Писмото стои в архива. Който иска го чете. Който не, дори и да пита,
няма да му отговарям.


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.6 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iQIVAwUBQiS2PLafyWmgOHdbAQKFog//UPOKszntl/3RbmJlbj6qe2GiE9kTb9lD
Sql96GEKKeJJUp3RM538K7JimDzWpTWPyU5E4+0qaEcZQ3aHx+uljhbOZoPXLqdH
aVjeeIxUeqUz+yO+78R3nfn4Rbv9b4QiDnz6hwYkSmSr7lL8Sy+H1ZXpaUIi8iYO
dHHiBIhO2o+5YQ1AdMrHJmMln1r1KCFKYPigkwxESRxJpaCWK8JHLhEgzVueD1Qt
xXJ+/nhAhYqaUKHOzCcVjqGhEJjuXK0WKuinIljU1/sQPM913vNLeqy2EljT0TpH
x3B62hQn4PIhvj4bvJvpY876X3cZMQd+9mqWbMTuuEMlIKlMPWdx12vfOI88v058
WQoSIbNOsazvc1Tmd3eyaFL2LvYPkZkirtOVNca6bnsteWtW3LZGR77V/GHxzgRL
c82T6MVuvzFQuJYbibuFps+afeVN6appE45MiwBoi2Ox1uPN/faN3t/1N616bl7C
JlgXSqtvg6ANO/311q191TpjKTPsJNoz7Ob3TBH/ZwK50mlczU689/nMp9paQ8De
Wkjo6WkWpbl99tztQQonwsfEuq3WlaxO5whLW+zrlqTDvdn80er8PyT/H67cKZy9
ZKBP+tjIPKhZgd21cqhhnNwuLE0onQoXPTZtA3bZVGQfi/hgqxkWFuYqJ8HUaQYD
tfOv/eP+rSc=
=dypS
-----END PGP SIGNATURE-----

============================================================================
A mail-list of Linux Users Group - Bulgaria (bulgarian linuxers).
http://www.linux-bulgaria.org - Hosted by Internet Group Ltd. - Stara Zagora
To unsubscribe: http://www.linux-bulgaria.org/public/mail_list.html
============================================================================