nedoPC.org

Community of electronics hobbyists established in 2002

...
Atom Feed | View unanswered posts | View active topics It is currently 25 Mar 2017 05:37



Reply to topic  [ 10 posts ] 
Найдена коллизия SHA-1 
Author Message
Admin
User avatar

Joined: 09 Jan 2003 02:22
Posts: 15224
Location: New York
Reply with quote
Вчера появилась информация, что нескольким исследователям удалось найти коллизию в SHA-1 (алгоритм хеширования, который выдаёт 160-битный ключ по содержимому файла) и даже более того - предоставить алгоритм создания таких коллизий!

http://thehackernews.com/2017/02/sha1-collision-attack.html

Приаттачиваю два PDF-файла (взято с http://shattered.io) - любой может проверить, что файлы разные, но тем не менее имеют один и тот же SHA1 хэш:

Code:
> ls -l
-rw-r--r-- 1 shaos shaos  422435 Feb 23 16:37 shattered-1.pdf
-rw-r--r-- 1 shaos shaos  422435 Feb 23 16:37 shattered-2.pdf

> sha1sum shattered-1.pdf
38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-1.pdf
> sha1sum shattered-2.pdf
38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-2.pdf

> md5sum shattered-1.pdf
ee4aa52b139d925f8d8884402b0a750c  shattered-1.pdf
> md5sum shattered-2.pdf
5bd9d8cabc46041579a311230539b8d1  shattered-2.pdf

Для примера я выше привёл также и MD5 (коллизии для которого показали ещё в 1996), чтобы продемонстрировать, что файлы таки разные. Вот собственно чем они отличаются:
Code:
< 000000c0  73 46 dc 91 66 b6 7e 11  8f 02 9a b6 21 b2 56 0f  |sF..f.~.....!.V.|
< 000000d0  f9 ca 67 cc a8 c7 f8 5b  a8 4c 79 03 0c 2b 3d e2  |..g....[.Ly..+=.|
< 000000e0  18 f8 6d b3 a9 09 01 d5  df 45 c1 4f 26 fe df b3  |..m......E.O&...|
< 000000f0  dc 38 e9 6a c2 2f e7 bd  72 8f 0e 45 bc e0 46 d2  |.8.j./..r..E..F.|
< 00000100  3c 57 0f eb 14 13 98 bb  55 2e f5 a0 a8 2b e3 31  |<W......U....+.1|
< 00000110  fe a4 80 37 b8 b5 d7 1f  0e 33 2e df 93 ac 35 00  |...7.....3....5.|
< 00000120  eb 4d dc 0d ec c1 a8 64  79 0c 78 2c 76 21 56 60  |.M.....dy.x,v!V`|
< 00000130  dd 30 97 91 d0 6b d0 af  3f 98 cd a4 bc 46 29 b1  |.0...k..?....F).|
---
> 000000c0  7f 46 dc 93 a6 b6 7e 01  3b 02 9a aa 1d b2 56 0b  |.F....~.;.....V.|
> 000000d0  45 ca 67 d6 88 c7 f8 4b  8c 4c 79 1f e0 2b 3d f6  |E.g....K.Ly..+=.|
> 000000e0  14 f8 6d b1 69 09 01 c5  6b 45 c1 53 0a fe df b7  |..m.i...kE.S....|
> 000000f0  60 38 e9 72 72 2f e7 ad  72 8f 0e 49 04 e0 46 c2  |`8.rr/..r..I..F.|
> 00000100  30 57 0f e9 d4 13 98 ab  e1 2e f5 bc 94 2b e3 35  |0W...........+.5|
> 00000110  42 a4 80 2d 98 b5 d7 0f  2a 33 2e c3 7f ac 35 14  |B..-....*3....5.|
> 00000120  e7 4d dc 0f 2c c1 a8 74  cd 0c 78 30 5a 21 56 64  |.M..,..t..x0Z!Vd|
> 00000130  61 30 97 89 60 6b d0 bf  3f 98 cd a8 04 46 29 a1  |a0..`k..?....F).|

P.S. Это значит, что git, а также много чего ещё, использующего SHA1-ключ как уникальный идентификатор объекта, идут лесом...

P.P.S. Про тоже самое по русски на хабре - https://habrahabr.ru/post/322478/


Attachments:
shattered-1.pdf [412.53 KiB]
Downloaded 4 times
shattered-2.pdf [412.53 KiB]
Downloaded 4 times

_________________
:eugeek: https://twitter.com/Shaos1973
24 Feb 2017 13:36
Profile WWW
Admin
User avatar

Joined: 09 Jan 2003 02:22
Posts: 15224
Location: New York
Reply with quote
Пока спасает лишь то, что для генерации таких файлов-"близнецов" первоначальный файл, точнее его содержимое, должен обладать некими свойствами, упрощающими такую атаку, а это возможно далеко не для каждого файла (и вроде как относительно легко детектируемо - код опубликуют) ну и плюс ко всему:
Quote:
This attack required over 9,223,372,036,854,775,808 SHA1 computations. This took the equivalent processing power as 6,500 years of single-CPU computations and 110 years of single-GPU computations.

Что возможно по цене в пределах $100K (для амазоновского облака)

_________________
:eugeek: https://twitter.com/Shaos1973


24 Feb 2017 13:52
Profile WWW
Maniac

Joined: 08 Apr 2013 07:04
Posts: 246
Location: 213.247.249.139
Reply with quote
А вроде как это атака дней рождения (одновременно генерятся 2 файла с разным содержимым но одинаковым хешем), а не тупо генерация заданного хеша, что сделали для мд5.
Атака дней рождения для мд5 это вообще перебор 2^32, и чо-то никто панику не поднимал по этому поводу никогда.

Да и опять же, всего в 100 тыщ раз меньше расчётов, чем для брутфорса такой атаки (2^63 вместо 2^80), так что какбэ раздувают из мухи слона, как обычно делают журналажники, а доверчивые ведутся :)


24 Feb 2017 19:31
Profile
Maniac

Joined: 08 Apr 2013 07:04
Posts: 246
Location: 213.247.249.139
Reply with quote
вот ещё: http://habrahabr.ru/post/322622/, http://plus.google.com/+LinusTorvalds/posts/7tp2gYWQugL
Quote:
(1) First off - the sky isn't falling. There's a big difference between using a cryptographic hash for things like security signing, and using one for generating a "content identifier" for a content-addressable system like git.

(2) Secondly, the nature of this particular SHA1 attack means that it's actually pretty easy to mitigate against, and there's already been two sets of patches posted for that mitigation.

(3) And finally, there's actually a reasonably straightforward transition to some other hash that won't break the world - or even old git repositories.


27 Feb 2017 01:42
Profile
Admin
User avatar

Joined: 09 Jan 2003 02:22
Posts: 15224
Location: New York
Reply with quote
SVN кстати тоже ломается от такой коллизии т.к. он коммиты по SHA-1 различает:

https://it.slashdot.org/story/17/02/26/2020222/apache-subversion-fails-sha-1-collision-test-exploit-moves-into-the-wild

_________________
:eugeek: https://twitter.com/Shaos1973


27 Feb 2017 19:25
Profile WWW
Maniac

Joined: 08 Apr 2013 07:04
Posts: 246
Location: 213.247.249.139
Reply with quote
Не коммиты а файлы, для дедупликации, вроде как.
В любом случае, кто в сруктурах рядом с хешем не положил 1 байтик, показывающий используемый алго, тот ссзб...


28 Feb 2017 05:18
Profile
Admin
User avatar

Joined: 09 Jan 2003 02:22
Posts: 15224
Location: New York
Reply with quote
angry_troll wrote:
Не коммиты а файлы, для дедупликации, вроде как.
В любом случае, кто в сруктурах рядом с хешем не положил 1 байтик, показывающий используемый алго, тот ссзб...

Ну скажем какой SHA используется можно просто тупо по длине ключа понять ;)
Да и MD5 туда же - он чуть короче, чем SHA-1

_________________
:eugeek: https://twitter.com/Shaos1973


28 Feb 2017 11:00
Profile WWW
Maniac

Joined: 08 Apr 2013 07:04
Posts: 246
Location: 213.247.249.139
Reply with quote
Shaos wrote:
Ну скажем какой SHA используется можно просто тупо по длине ключа понять ;)


Низя. Например sha-2 vs sha-3


28 Feb 2017 13:20
Profile
Admin
User avatar

Joined: 09 Jan 2003 02:22
Posts: 15224
Location: New York
Reply with quote
angry_troll wrote:
Shaos wrote:
Ну скажем какой SHA используется можно просто тупо по длине ключа понять ;)


Низя. Например sha-2 vs sha-3

Ну SHA-3 ещё нигде не используется, как я понял, так что видимо остаётся пока только семейство SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)

_________________
:eugeek: https://twitter.com/Shaos1973


28 Feb 2017 13:26
Profile WWW
Maniac

Joined: 08 Apr 2013 07:04
Posts: 246
Location: 213.247.249.139
Reply with quote
Shaos wrote:
Ну SHA-3 ещё нигде не используется, как я понял, так что видимо остаётся пока только семейство SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)


ВНЕЗАПНАЯ новость о том, что кто-то, насчитав мульён мипсо-лет, смог таки сузить пространство поиска атаки дней рождения на ША-1 в целых сто тысяч раз какбэ намекает всем, чтобы они в своих поделках, форматах и алгоритмах предусматривали возможность оперативной замены или добавления других хешь-функций. :)


28 Feb 2017 14:45
Profile
Display posts from previous:  Sort by  
Reply to topic   [ 10 posts ] 

Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software.