id: Гость   вход   регистрация
текущее время 13:59 28/03/2024
Владелец: unknown (создано 10/02/2015 11:55), редакция от 10/02/2015 15:55 (автор: unknown) Печать
Категории: криптография, алгоритмы, хэширование
https://www.pgpru.com/Новости/2015/XOR-комбинированиеХэш-функцийСнижаетИхСтойкость
создать
просмотр
редакции
ссылки

10.02 // XOR-комбинирование хэш-функций снижает их стойкость


Проблемы со стойкостью хэш-функций часто приводят к перестраховкам, основанным на комбинировании разных алгоритмов. Наиболее простым и надёжным является объединение выходов двух разных хэшей путём простого присоединения: H1(M) ║ H2(M). Это оказывается неудобным для некоторых протоколов, т.к. приводит к увеличению размера выхода. Долгое время оптимальным и простым решением представлялось XOR-комбинирование: H1(M) ⊕ H2(M). При некоторых оговорках стойкость такого решения была частично доказана. Сами алгоритмы функций при этом должны быть разными и несвязанными, иначе это привело бы к тривиальной атаке: H2(M) := H1(M) ⊕ const. Даже если обе функции идеально безопасны, но связаны через константу, то их XOR-комбинирование привело бы к результату: H1(M) ⊕ H2(M) = const для любого M.


Исследователи Gatan Leurent (государственный институт исследований в информатике и автоматике, Франция) и Lei Wang (Наньянский технологический университет, Сингапур) показали существенные изъяны в стойкости XOR-комбинирования. Большинство n-битовых хэш-функций структуры Дамгарда-Меркла или Хайфа при XOR-комбинировании теряют свою стойкость до 25n/6. Так, для 512-битной комбинации SHA512 ⊕ Whirlpool стойкость будет порядка 426 бит, т.е. стойкость XOR-комбинации двух функций слабее стойкости этих функций по отдельности. Нестойкость к коллизиям для XOR-объединения была известна и раньше, но авторы распространили результат на все хэш-функции структуры narrow pipe, даже заведомо стойкие или те, против которых не известно методов взлома по отдельности.


Расходы памяти на атаку зависят от длины сообщения: при длине n / 2 · 22t расходы памяти описываются этой же формулой, что позволяет вывести оптимальную длину сообщения для проведения атаки.


Атака может быть распространена и на случаи wide-pipe хэшей при размере сообщения, которое меньше размера внутреннего состояния хэш-функции. Так, исследователями был получен результат 2199 при комбинировании SHA-224 ⊕ BLAKE-224 с этим условием.


Исследователям удалось атаковать и более сложную комбинирующую функцию Cryptophia, предложенную Миттельбахом и усовершенствованную Менником и Пренелом. Эта функция использует оптимизированное укороченное сочетание присоединения и XOR. Даже такое комбинирование оказалось слабее исходных функций при комбинации SHA-512 и Whirlpool.


Следует ещё раз подчеркнуть, что исследователи рассматривали функции сжатия внутри хэшей как идеальные в модели случайного оракула, а сами хэши — как стойкие. Даже при таких ограничениях им удалось добиться заметных результатов. В случае обнаружения в какой-либо из функций уязвимости результат такого перестраховочного комбинирования может оказаться ещё более слабым, чем использование хэш-функций по отдельности. Также результат атаки может быть распространён и на попытки XOR-комбинирования более двух хэш-функций.


В работе отмечается, что многие хэш-функции относятся к классу narrow pipe (SHA-1, SHA-256, SHA-512, Whirlpool, RIPEMD, GOST, BLAKE, Skein) и комбинирование их посредством XOR приводит к снижению стойкости. Также отмечается, что XOR-комбинирование всё ещё встречается в протоколах TLS, SSL и алгоритмах KDF (функция получения производных ключей).


Источник: Cryptology ePrint Archive


 
На страницу: 1, 2 След.
Комментарии [скрыть комментарии/форму]
— Гость (10/02/2015 12:06)   <#>

Так а как их тогда комбинировать? Нет вообще надёжных методов? У меня другой вопрос, но похожий: есть несколько ГПСЧ (типа /dev/urandom), но ни один из них не доверен на 100%. Хочется из нескольких псевдослучайных строк для пароля вывести одну, которая будет более надёжной/случайной. Что тогда лучше сделать, поксорить их?
— unknown (10/02/2015 14:14)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Присоединять и сохранять выходы всех хэшей, но не объединять никакой математической операцией в один. Или перейти на Sponge-конструкции.


Можно ксорить, можно использовать более продвинутые экстракторы энтропии поверх, но на практике источник уровня /dev/urandom должен быть доверяем — если не доверяем на 100%, то и самим перестраховкам доверять особо не стоит.
— Гость (10/02/2015 16:31)   <#>
Допустим, мне нужен строго 256-битный пароль для шифрования. Не получится ли так, что я запоминаю 40 печатных символов вместо 20-ти (128 бит), хотя никакого смысла в этом нет: гамма /dev/urandom всё равно растягивается из небольшого зерна вычислительным образом, так что вторые 128 бит связаны с первыми, а зерно (seed) вообще всегда 128 бит. Т.е. даже теоретически /dev/urandom не может дать те самые 256 бит, поэтому нужно ждать выхлопа самого /dev/random — нет ли случайно такой проблемы?
— unknown (10/02/2015 16:44, исправлен 10/02/2015 16:46)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Think about this for a moment: whoever wrote the /dev/random
manual page seems to simultaneously believe that
(1) we can't figure out how to deterministically expand one 256-bit /dev/random output into an endless stream of unpredictable keys (this is what we need from urandom), but
(2) we _can_ figure out how to use a single key to safely encrypt many messages (this is what we need from SSL, PGP, etc.).

For a cryptographer this doesn't even pass the laugh test.

© D.J. Bernstein.


Ответ на ваш вопрос есть в Myths about /dev/urandom, там эта проблема хорошо рассмотрена.

— Гость (10/02/2015 17:38)   <#>
Спасибо. Понял.
— unknown (11/02/2015 11:17, исправлен 11/02/2015 11:20)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Вкратце, новость о том, что из-за определённой структуры хэш-функций вида narrow pipe, которые не проектировались с учётом сильной RO-неразличимости, можно подобрать частичную коллизию в одной функции и независимо частичную коллизию в другой. Эти частичные коллизии будут удовлетворять такому условию, что их XOR даст полную коллизию (и возможно ещё какой-либо подобранный дефект, вплоть до первых прообразов). Подобрать такую пару частичных коллизий на двух разных функциях проще, чем полную коллизию на каждой из них по отдельности. Т.е., абстракция протекает, внутренняя структура функций лезет наружу: поксорили два неполных RO и получили ещё более неполный RO. По отдельности тонкое отличие структуры хэшей от RO несущественно, а при определённом комбинировании — снижает стойкость. Хороший пример того, что любой криптопримитив должен быть как можно ближе к идеалу. Если он неидеален изначально, как асимметричные алгоритмы, то его нужно правильно упаковать в конструкцию, убирающую эту неидеальность, а не снижающую её: оборачивание асимметрики в симметрику. Также было устроено оборачивание симметрики в симметрику: HMAC из narrow-pipe хэшей. И это не перестраховки, а лишь чётко выверенное доведение до ума существующих конструкций.

— Гость (11/02/2015 12:57)   <#>

Что имеется в виду?
— unknown (11/02/2015 13:38)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Подпись и шифрование напрямую чистой асимметрикой не применяются не только из-за малой скорости асимметричных алгоритмов. Если асимметрикой подписывать и шифровать что-попало, а не хэш данных, не случайно сгенерированный сеансовый симметричный ключ (и если ещё делать всё это без правильных режимов дополнения) — то можно нарваться на утечки битов асимметричного ключа и прочие различители.
— Гость (11/02/2015 13:53)   <#>
А, вы про это... Но всё равно фраза

Если он неидеален изначально, как асимметричные алгоритмы, то его нужно правильно упаковать в конструкцию, убирающую эту неидеальность, а не снижающую её: оборачивание асимметрики в симметрику.

плохо понятна. Оборачивать асимметрику в симметрику плохо? А какие тогда альтернативы (в т.ч. в PGP)?
— unknown (11/02/2015 14:00, исправлен 11/02/2015 14:01)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Хорошо, в смысле необходимо исправлять неидеальность асимметрики при помощи симметрики, что в PGP/SSL/etc для асимметрики и сделано штатно. Вам об этом как пользователю думать не надо.

— Гость (21/02/2015 19:24)   <#>

Ну вообще-то крипто проектируется с таким условием, что одним ключом (паролем?) можно шифровать много разных сообщений, и это не ведёт к утечкам, так что цитата про несвязываемость ключей не очень понятна.

Я по-обывательски могу принять максиму «всегда выбирайте urandom и не парьтесь по этому поводу», раз специалисты так считают, но меня смущает то, что кое-что всё-таки использует строго /dev/random, а не urandom. Например, это по умолчанию касается генерации PGP-ключей и, если помню правильно, некоторого ключевого материала в LUKS. Почему там не был выбран urandom? Тоже кулхацкерство? Стоит переопределить дефолты?
— unknown (21/02/2015 22:33, исправлен 21/02/2015 22:34)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

У этой новости было некоторое продолжение, к сожалению не могу вспомнить статью. Там оказалось, что /dev/urandom сразу на старте системы начинал генерировать ключи и сертификаты. При этом он не успевал набрать почти никакой существенной энтропии и не мог подкачать с диска энтропию предыдущего сеанса /var/lib/urandom/random-seed. Это критично, если криптоматериал ключа генерится сразу на старте, если используется бездисковый компьютер, если random-seed восстановлен повторно из бэкапа, расклонирован на множество виртуалок и т.д. Собрав множество асимметричных ключей, сгенерированных таким дефектным образом, исследователям удавалось найти между ними коллизии множителей и ускоренно факторизовать. Также были дефектны и ещё какие-то криптопараметры.


Т.е., вывод можно сделать примерно такой, что если из системы, допустим, выкинуть /dev/random и оставить только /dev/urandom, то его надо тоже блокировать до накопления энтропии, но лишь в момент загрузки системы, а дальше блокирование отключать и пусть он гонит вычисленную псевдоэнтропию. А сколько сможет в процессе работы подкачать из системы энтропии реальной, пусть столько и будет, даже если и мало — не так страшно, главное на старте получить 256 бит, нет смысла особо переживать из-за малого количества последующей системной энтропии, если сам алгоритм вычисления псевдоэнтропии реализован правильно.


Это имеет отношение к тому, что обсуждали начиная с этого комента в другой теме. кстати, там тоже вопрос вброшен без каких-либо объяснений не по теме. Лучше бы создали отдельную тему — насчёт того, где и как (не)нужно усиливать сбор энтропии, где есть смысл с этим заморачиваться, а где — нет. В этой теме вопрос также получился неуместным — перексоривание хэшей не имеет отношения к сбору энтропии. При сборе энтропии противник не может контролировать все хэшируемые источники для подбора сокращённых коллизий, да ещё и в реальном времени. Теперь вопрос про сбор системной энтропии размазан оффтопиком по разным темам, хотя он требовал бы отдельного рассмотрения.

— Гость (02/03/2015 06:28)   <#>

Из общих соображений непонятно, как такое могло получиться. Я могу поверить, что если ГСЧ для двух машин были скоррелированы, то владелец приватных ключей, сгенерированных на одной машине, может ускоренно факторизовать ключи, сгенерированные на второй. Однако, здесь всё ещё хуже: третья сторона, владеющая только публичными ключами с обеих машин, может их факторизовать. Как это так? В пределе должны получаться просто одинаковые ключи на обеих машинах, но всё такие же безопасные для постороннего, кто не имеет доступа к рандому или секретному ключевому материалу на этих машинах.
— unknown (02/03/2015 10:05, исправлен 02/03/2015 10:48)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Пусть открытый ключ Pk = f (X,Y). Например, произведение секретных множителей в RSA, но я точно не помню деталей, пусть это будут абстрактные параметры по которым строится ключ. Пусть Z — совпадающий параметр. Тогда, если в одном случае X = Z, а в другом Y = Z, то могут получиться два открытых ключа вида Pk1 = f (Z,Y) и Pk2 = f (X,Z). Всякие неслучайности и связи — это уже плохо и как-то может помогать найти закрытые ключи по открытым, даже если ключи вообще разные: Pk1Pk2, но при этом связанные по таким параметрам, по которым этого делать нельзя.


Вроде об этом же уже спрашивали. И был ответ.


В подписях вида DSA (а это почти вся эллиптика, в отличии от RSA, сделать там статичные подписи — непростая задача) критична рэндомность определёного параметра для каждой подписи. Если он предсказуем, то закрытый ключ также вычисляется по подписи.

— Гость (07/03/2015 15:49)   <#>

Связи в симметрике ведь тоже опасны?

we can't figure out how to deterministically expand one 256-bit /dev/random output into an endless stream of unpredictable keys (this is what we need from urandom)

Например, я выполнил pwgen -s -y 40 1, получил пароль, использую его для LUKS, а параллельно из этого же пула черпается ещё что-то и для других ключей/шифрования (например, для шифрования трафика через Tor или SSL). Вдруг потом это (шифрованный диск и шифрованный трафик) как-то можно связать, чтобы быстрее сбрутфорсить ключи? Эти опасения беспочвенны? Можно ли доверять /dev/urandom свою жизнь?
На страницу: 1, 2 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3