TWIMC ----- Forwarded message from solardiz ----- Date: Sat, 6 Oct 2012 20:19:24 +0600 (YEKT) Subject: Выбран финальный алгоритм для SHA-3 Новое сообщение от 'solardiz' в форуме 'Разговоры, обсуждение новостей' Посмотреть: http://www.opennet.ru/openforum/vsluhforumID3/86742.html#66 Тема: Выбран финальный алгоритм для SHA-3 >Аппаратная реализация Keccak оказалась наиболее быстрой из всех >представленных на конкурс работ. Вот что самое важное для спец служб. Ведь >им потом придётся с ним мучаться. Это сейчас очень обсуждаемая тема, и даже такой уважаемый и знающий человек как Ben Laurie допустил, с нужными оговорками, подобный блог-пост: http://www.links.org/?p=1283 Мое мнение, что у нас на данный момент недостаточно данных для корректного сравнения эффективности будущих оптимизированных для атаки реализаций SHA-1, SHA-2, SHA-3 (причем в случае SHA-2 и SHA-3 надо сравнивать еще и по нескольку вариантов из них). Из аппаратных, оптимальными для атаки обычно оказываются fully-pipelined реализации. Идем на http://cryptography.gmu.edu/athenadb/fpga_hash/table_view и пытаемся сравнить pipelined реализации SHA-2 и Keccak. Мне не удалось из этой таблицы получить для них однозначный результат - получается во-первых сравнение apples/oranges (отличаются поля Arch Type и Max Streams), а во-вторых Keccak не оказывается однозначно меньше. (С точки зрения спецслужб, актуальнее было бы сравнивать ASIC, а не FPGA реализации, но по ним у нас данных еще меньше.) Для оптимизированных по размеру аппаратных реализаций, да, Keccak сильно выигрывает, и это хорошо - смарт-карты и т.п. Что касается оптимизированных для атаки программных реализаций, то SIMD можно использовать (именно при атаке) и для SHA-1 и SHA-2 тоже. SHA-3, в отличие от SHA-1 и SHA-2, позволяет делать более эффективные bitslice реализации, но актуальность их сомнительна при том что распространенные ныне процессоры позволяют SIMD-реализации всех этих хешей (увы, только при наличии параллелизма уровнем выше, т.е. как при атаке) и без необходимости bitslicing'а. Вот если бы у нас, например, 256-битные операции в реализациях первого AVX'а были бы быстрее, чем 128-битные, в расчете на один бит, тогда да - это что-то дало бы. Но на существующих процессорах это не так (я проверял на Sandy Bridge и Bulldozer), а с AVX2 у нас будет возможность не-bitslice реализаций под 256-бит. Да, bitslice позволяет избавиться от затрат на перестановку битов (операции rotate в Keccak), но мы за это платим использованием L1 cache вместо регистров - так что в целом эффект не очевиден. На GPU тем более потребность в памяти будет играть бОльшую роль, чем количество операций. Какие реализации окажутся эффективнее и как они будут сравниваться с SHA-2 и SHA-1, пока не очевидно. Почти наверняка SHA-3 окажется быстрее для атак, чем SHA-512, но будет ли он быстрее для атак, чем SHA-256 и SHA-1, мне на данный момент не очевидно. Посмотрим. ----- End forwarded message ----- -- ---- WBR, Michael Shigorin <mike@altlinux.ru> ------ Linux.Kiev http://www.linux.kiev.ua/