[room] Fwd: Выбран финальный алгоритм для SHA-3

[Michael Shigorin <mike@osdn.org.ua>]

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/