From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.2.5 (2008-06-10) on sa.int.altlinux.org X-Spam-Level: X-Spam-Status: No, score=-0.9 required=5.0 tests=BAYES_00,FUZZY_XPILL autolearn=no version=3.2.5 Date: Sun, 7 Oct 2012 13:29:53 +0300 From: Michael Shigorin To: smoke-room@lists.altlinux.org Message-ID: <20121007102953.GB28064@osdn.org.ua> Mail-Followup-To: smoke-room@lists.altlinux.org Mime-Version: 1.0 Content-Type: text/plain; charset=koi8-r Content-Disposition: inline Content-Transfer-Encoding: 8bit User-Agent: Mutt/1.4.2.1i Subject: [room] =?koi8-r?b?RndkOiD32cLSwc4gxsnOwczYztnKIMHMx8/SydTNIMTM?= =?koi8-r?b?0SBTSEEtMw==?= X-BeenThere: smoke-room@lists.altlinux.org X-Mailman-Version: 2.1.12 Precedence: list Reply-To: shigorin@gmail.com, =?koi8-r?b?69XM2NTV0s7ZyiDPxtTP0MnL?= List-Id: =?koi8-r?b?69XM2NTV0s7ZyiDPxtTP0MnL?= List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 07 Oct 2012 10:29:57 -0000 Archived-At: List-Archive: 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 ------ Linux.Kiev http://www.linux.kiev.ua/