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
Так а как их тогда комбинировать? Нет вообще надёжных методов? У меня другой вопрос, но похожий: есть несколько ГПСЧ (типа /dev/urandom), но ни один из них не доверен на 100%. Хочется из нескольких псевдослучайных строк для пароля вывести одну, которая будет более надёжной/случайной. Что тогда лучше сделать, поксорить их?
комментариев: 9796 документов: 488 редакций: 5664
Присоединять и сохранять выходы всех хэшей, но не объединять никакой математической операцией в один. Или перейти на Sponge-конструкции.
Можно ксорить, можно использовать более продвинутые экстракторы энтропии поверх, но на практике источник уровня /dev/urandom должен быть доверяем — если не доверяем на 100%, то и самим перестраховкам доверять особо не стоит.
комментариев: 9796 документов: 488 редакций: 5664
© D.J. Bernstein.
Ответ на ваш вопрос есть в Myths about /dev/urandom, там эта проблема хорошо рассмотрена.
комментариев: 9796 документов: 488 редакций: 5664
Вкратце, новость о том, что из-за определённой структуры хэш-функций вида narrow pipe, которые не проектировались с учётом сильной RO-неразличимости, можно подобрать частичную коллизию в одной функции и независимо частичную коллизию в другой. Эти частичные коллизии будут удовлетворять такому условию, что их XOR даст полную коллизию (и возможно ещё какой-либо подобранный дефект, вплоть до первых прообразов). Подобрать такую пару частичных коллизий на двух разных функциях проще, чем полную коллизию на каждой из них по отдельности. Т.е., абстракция протекает, внутренняя структура функций лезет наружу: поксорили два неполных RO и получили ещё более неполный RO. По отдельности тонкое отличие структуры хэшей от RO несущественно, а при определённом комбинировании — снижает стойкость. Хороший пример того, что любой криптопримитив должен быть как можно ближе к идеалу. Если он неидеален изначально, как асимметричные алгоритмы, то его нужно правильно упаковать в конструкцию, убирающую эту неидеальность, а не снижающую её: оборачивание асимметрики в симметрику. Также было устроено оборачивание симметрики в симметрику: HMAC из narrow-pipe хэшей. И это не перестраховки, а лишь чётко выверенное доведение до ума существующих конструкций.
Что имеется в виду?
комментариев: 9796 документов: 488 редакций: 5664
Подпись и шифрование напрямую чистой асимметрикой не применяются не только из-за малой скорости асимметричных алгоритмов. Если асимметрикой подписывать и шифровать что-попало, а не хэш данных, не случайно сгенерированный сеансовый симметричный ключ (и если ещё делать всё это без правильных режимов дополнения) — то можно нарваться на утечки битов асимметричного ключа и прочие различители.
плохо понятна. Оборачивать асимметрику в симметрику плохо? А какие тогда альтернативы (в т.ч. в PGP)?
комментариев: 9796 документов: 488 редакций: 5664
Хорошо, в смысле необходимо исправлять неидеальность асимметрики при помощи симметрики, что в PGP/SSL/etc для асимметрики и сделано штатно. Вам об этом как пользователю думать не надо.
Ну вообще-то крипто проектируется с таким условием, что одним ключом (паролем?) можно шифровать много разных сообщений, и это не ведёт к утечкам, так что цитата про несвязываемость ключей не очень понятна.
Я по-обывательски могу принять максиму «всегда выбирайте urandom и не парьтесь по этому поводу», раз специалисты так считают, но меня смущает то, что кое-что всё-таки использует строго /dev/random, а не urandom. Например, это по умолчанию касается генерации PGP-ключей и, если помню правильно, некоторого ключевого материала в LUKS. Почему там не был выбран urandom? Тоже кулхацкерство? Стоит переопределить дефолты?
комментариев: 9796 документов: 488 редакций: 5664
У этой новости было некоторое продолжение, к сожалению не могу вспомнить статью. Там оказалось, что /dev/urandom сразу на старте системы начинал генерировать ключи и сертификаты. При этом он не успевал набрать почти никакой существенной энтропии и не мог подкачать с диска энтропию предыдущего сеанса /var/lib/urandom/random-seed. Это критично, если криптоматериал ключа генерится сразу на старте, если используется бездисковый компьютер, если random-seed восстановлен повторно из бэкапа, расклонирован на множество виртуалок и т.д. Собрав множество асимметричных ключей, сгенерированных таким дефектным образом, исследователям удавалось найти между ними коллизии множителей и ускоренно факторизовать. Также были дефектны и ещё какие-то криптопараметры.
Т.е., вывод можно сделать примерно такой, что если из системы, допустим, выкинуть /dev/random и оставить только /dev/urandom, то его надо тоже блокировать до накопления энтропии, но лишь в момент загрузки системы, а дальше блокирование отключать и пусть он гонит вычисленную псевдоэнтропию. А сколько сможет в процессе работы подкачать из системы энтропии реальной, пусть столько и будет, даже если и мало — не так страшно, главное на старте получить 256 бит, нет смысла особо переживать из-за малого количества последующей системной энтропии, если сам алгоритм вычисления псевдоэнтропии реализован правильно.
Это имеет отношение к тому, что обсуждали начиная с этого комента в другой теме. кстати, там тоже вопрос вброшен без каких-либо объяснений не по теме. Лучше бы создали отдельную тему — насчёт того, где и как (не)нужно усиливать сбор энтропии, где есть смысл с этим заморачиваться, а где — нет. В этой теме вопрос также получился неуместным — перексоривание хэшей не имеет отношения к сбору энтропии. При сборе энтропии противник не может контролировать все хэшируемые источники для подбора сокращённых коллизий, да ещё и в реальном времени. Теперь вопрос про сбор системной энтропии размазан оффтопиком по разным темам, хотя он требовал бы отдельного рассмотрения.
Из общих соображений непонятно, как такое могло получиться. Я могу поверить, что если ГСЧ для двух машин были скоррелированы, то владелец приватных ключей, сгенерированных на одной машине, может ускоренно факторизовать ключи, сгенерированные на второй. Однако, здесь всё ещё хуже: третья сторона, владеющая только публичными ключами с обеих машин, может их факторизовать. Как это так? В пределе должны получаться просто одинаковые ключи на обеих машинах, но всё такие же безопасные для постороннего, кто не имеет доступа к рандому или секретному ключевому материалу на этих машинах.
комментариев: 9796 документов: 488 редакций: 5664
Пусть открытый ключ Pk = f (X,Y). Например, произведение секретных множителей в RSA, но я точно не помню деталей, пусть это будут абстрактные параметры по которым строится ключ. Пусть Z — совпадающий параметр. Тогда, если в одном случае X = Z, а в другом Y = Z, то могут получиться два открытых ключа вида Pk1 = f (Z,Y) и Pk2 = f (X,Z). Всякие неслучайности и связи — это уже плохо и как-то может помогать найти закрытые ключи по открытым, даже если ключи вообще разные: Pk1 ≠ Pk2, но при этом связанные по таким параметрам, по которым этого делать нельзя.
Вроде об этом же уже спрашивали. И был ответ.
В подписях вида DSA (а это почти вся эллиптика, в отличии от RSA, сделать там статичные подписи — непростая задача) критична рэндомность определёного параметра для каждой подписи. Если он предсказуем, то закрытый ключ также вычисляется по подписи.
Связи в симметрике ведь тоже опасны?
Например, я выполнил pwgen -s -y 40 1, получил пароль, использую его для LUKS, а параллельно из этого же пула черпается ещё что-то и для других ключей/шифрования (например, для шифрования трафика через Tor или SSL). Вдруг потом это (шифрованный диск и шифрованный трафик) как-то можно связать, чтобы быстрее сбрутфорсить ключи? Эти опасения беспочвенны? Можно ли доверять /dev/urandom свою жизнь?