SHA: дизайн для параллельной архитектуры?

Католический университет Леувена

antoon.bosselaers@esat.kuleuven.ac.be

25 февраля 1997

Тезисы. Для увеличения производительности в компьютерных архитектурах появилась тенденция увеличивать число параллельно выполняющихся команд Эта статья показывает, что новое поколение специализированных хэш-функций, базирующихся на MD4 (RIPEMD-128, RIPEMD-160, SHA-1) содержит намного больше программного параллелизма, чем способна обеспечить любая из существующих в настоящее время архитектур вычислительной системы. Это связано с тем, что существующий в SHA-1 параллелизм был заложен при его проектировании. Критический путь SHA-1 в два раза короче, чем у его ближайшего преследователя RIPEMD-160, но реализация ее требует 7-поточной архитектуры выдачи. В статье также будет показано, что поскольку в RIPEMD-160 организованы два независимых потока, то, вероятно, в будущих архитектурах будет проще использовать этот программный параллелизм.

Ключевые слова. Криптографические хеш-функции, параллелизм командного уровня, архитектуры многократной выдачи, исследование критического пути

В настоящее время в компьютерном проектировании присутствует тенденция включать в поток все большее число параллельно выполняющихся единиц, с целью увеличения работоспособности системы. Однако доступный параллелизм аппаратных средств приводит к увеличению только программной нагрузки в случае, если исполняемый код содержит достаточно программного параллелизма для использования потенциальных возможностей многопоточной архитектуры. Криптографические алгоритмы чаще всего организованы как итерация обычных последовательностей операций, называемых раундом. Типичным примером такой техники является итерация блока шифров и специализированных хэш-функций, базирующихся на MD4. Во многих приложениях шифрование и/или хеширование является узким местом, и увеличение скорости выполнения этих основных криптографических примитивов, часто приводит к непосредственному усовершенствованию работы всей системы.

Для увеличения производительности раундовых криптографических примитивов, достаточно сконцентрировать усилия на оптимизации функций раунда, учитывая, что всякая выгода, достигнутая в оптимизации этих функций, отражается на полной работе примитивов, умноженных на число раундов. Обычно число раундов колеблется от 8 до 32.

Эта статья сопоставляет один класс криптографических примитивов, а именно, специализированных хэш-функций, базирующихся на MD4, с самыми популярными компьютерными архитектурами, используемыми сегодня и прогнозируемых к использованию в ближайшем будущем. Хотя в дальнейшем будут рассматриваться только MD4-подобные хэш-функции, большая часть этой статьи обращена и к другим классам, работающим с итеративными криптографическими примитивами. Основная цель этой статьи заключается в том, чтобы исследовать степень параллелизма различных членов семейства MD4, и понять, насколько в настоящее время CISC- и RISC-процессоры способны использовать этот параллелизм. Этот подход отличается от [BGV96] тем, что из всех известных сейчас алгоритмов, мы рассмотрим алгоритмы хеширования как отправную точку, исследуем степень параллелизма, доступного в специфических суперскалярных процессорах, и изучим степень использования возможностей архитектуры в алгоритмах хеширования.

В следующем разделе рассматривается основные требования, которым должен удовлетворять процессор, чтобы обеспечить эффективное выполнение MD4-подобных хеш-функций. В разделе 3 дается краткий обзор доступных в настоящее время архитектур процессоров, и приводится список интересующих нас характеристик. В разделе 4 вводится понятие критического пути. Доступная степень параллелизма уровня команд в MD4- подобных алгоритмах определено в разделе 5, и дано противопоставление доступным аппаратным средствам раздела 3. И, наконец, в разделе 6 формулируется вывод.

Специализированные хэш-функции, основанные на MD4, включают MD4 [Riv92a], MD5 [Riv92b], SHA-1 [FIPS180-1], RIPEMD [RIPE95], RIPEMD-128 и RIPEMD- 160 [DBP96]. Это основные итерационные хэш-функции, использующие функции сжатия, как их основные строительные блоки, входные параметры которых состоят из 128 или 160-битной переменной сцепления и 512-битного блока сообщения. Выход – обновленная переменная сцепления. Внутри функция сжатия работает с 32-разрядным словом. Для преобразования внешних битовых строк во внутренний массив слов используется обратный порядок байт для SHA-1 и прямой для всех других хэш-функций. В зависимости от алгоритма, функция сжатия состоит из 3 - 5, возможно параллельных, раундов, каждый из которых состоит из 20 (SHA-1) или 16 (все остальные) шагов. В конце полученное значение добавляется к начальному значению переменной сцепления. Каждый раунд использует специфическую нелинейную функцию, и на каждом шагу изменяется одно слово переменной сцепки, и, возможно, производится циклический сдвиг другой. Определения раундов и пошаговых функций приведены в таблицах 1 и 2 соответственно.

Таблица 1. Определение булевых функций раунда семейства MD4.

Этот краткий обзор позволяет нам заключить, что выполнение MD4-подобных хеш-функций будет продуктивно при работе с процессором, который:

1. поддерживает 32-разрядные операции.

Таблица 2. Пошаговые функции, используемые алгоритмами семейства MD4. Все сложения по модулю 2³². Сдвиг влево x на s бит обозначен как x<<<s. A;B;C;D;E – слова переменной сцепления, K, s – константы, Xi – слово из сообщения или их комбинация, а f() – одна из функций из Табл 1. Последние 4 столбца поясняют, в каком раунде используются эти функции и в левом (L) или правом (R) параллельном потоке.

2. может обрабатывать данные с прямым (big-endian) и обратной (little-endian) порядком байт;

3. имеет команду циклического сдвига и в дополнение к стандартным командам: AND, OR, XOR команды NAND (НЕ-И), NOR (НЕ-ИЛИ), NXOR (НЕ-XOR), AND-NOT (И-НЕ), и OR-NOT (ИЛИ-НЕ), где последние две определены, как И и ИЛИ первого операнда, соответственно, и дополнение второго. Отметим, что XOR – NOT (XOR-НЕ) равносильно NOT -XOR (НЕ–XOR);

4. имеет возможность хранить локальные переменные в регистрах: 16 слов сообщения, 5 сформированных цепочек слов, и 2 вспомогательных слова. Семейство RIPEMD, имея два параллельных канала, требует двух копий последних двух элементов. Таким образом, всего требуется до 30 регистров;

5. поддерживает параллельное выполнение арифметических или логических операций. (Этот пункт будет рассматриваться в следующем разделе.)

3. Аппаратный параллелизм

Основной метод, направленный на улучшение работы центрального процессора, применяемый в настоящее время всеми процессорами, - конвейерная обработка. Конвейер организован в несколько стадий, каждая из которых выполняет часть команд центрального процессора. Многопоточные команды могут накладываться при выполнении, позволяя каждой стадии конвейера закончить часть другой команды. Следовательно, этот метод позволяет различным частям последовательных команд выполняться параллельно. Как следствие, конвейерная обработка увеличивает производительность центрального процессора. Время выполнения каждой команды обычно немного увеличивается из-за конвейерного управления наверху, но это более, чем компенсируется увеличением производительности процессора.

Результатом является существенное уменьшение числа тактовых циклов на команду, в идеале приводя к ускорению, равному числу конвейерных стадий. Для дальнейшего увеличения работоспособности существует еще два подхода: увеличение числа конвейерных стадий, или использование множество параллельных конвейеров. В прежних архитектурах, называемых суперконвейерными, подчеркивают временный параллелизм, в то время как последние архитектуры основываются на пространственном параллелизме и делятся на две разновидности: суперскалярные или очень длинного командного слова (VLIW). Цель этих методик - еще большее увеличение производительности суперконвейерных архитектур, посредством сокращения времени тактового цикла, в то время как суперскалярные/VLIW архитектуры пробуют выполнить более 1 команды в тактовый цикл. Однако, существует предел производительности, который может быть достигнут. Этот предел определен двумя факторами: программным обеспечением и аппаратными средствами. Фактор программного обеспечения - количество параллелизма в командном потоке, то есть, количество данных, связанных с параллельно выполняющимися командами. В следующем разделе доступный параллелизм уровня команд в командном потоке будет охарактеризован его критическим путем. Фактор аппаратных средств - воздействие увеличения числа конвейерных стадий или конвейеров на время тактового цикла.

В случае суперконвейерной архитектуры, ограниченной параллелизмом в команде потоке, в конечном счете, приведет к так называемой остановке конвейерной обработки из-за зависимых данных: выполнение команды должно быть остановлено, пока необходимые данные не станут доступными. Но даже в отсутствии зависимости, суперконвейерная обработка, в конечном счете, исчерпает себя. Время тактового цикла никогда не может быть ниже, чем время конвейерной обработки, которой подвержена каждая стадия: расфазировка тактовых сигналов и конвейерная регистрация наверху [HePa96]. Поэтому, увеличивая число конвейерных стадий, вне критической точки, приведет к деградации работы, а не увеличению производительности.

Дальнейшее увеличение производительности может быть получено любым продвижением суперскаляра или использованием VLIW.

- Суперскалярный процессор имеет динамическую возможность выдачи (issue): переменное число команд, выданных в каждый тактовый цикл. Аппаратные средства динамически решают, какие команды выданы одновременно и в какие конвейеры, основываясь на критериях выдачи и, возможно, зависимости данных.

- Процессор VLIW имеет фиксированную возможность выдачи: каждый тактовый цикл выдается фиксированное количество команд, форматированных как одна большая команда (отсюда название).

Программное обеспечение (то есть компилятор) полностью отвечает за созданный пакет команд, которые могут быть одновременно выданы. Никакие решения о динамическом многопоточном выдачи не принимаются аппаратными средствами. Преимущество VLIW в суперскалярном процессоре состоит в том, что количество необходимых аппаратных средств может быть уменьшено выбором команд, выданных одновременно, во время компиляции, а не во времени выполнения. Однако, суперскалярные процессоры имеют два главные преимущества: их плотность кода немного затрагивает доступный параллелизм командного потока, и его объектный код совместим с большим семейством непараллельных процессоров. Главный недостаток суперскалярного процессора состоит в том, что он должен ограничивать воздействие на время тактового цикла выдачи и выполнения мультипликативных команд в цикле. Это объясняется тем фактом, что до настоящего времени значение тактовой частоты колеблется от 1.5 до 2, последовательно отделил процессоры с самой высокой тактовой частотой и самые сложные процессоры многократного выпуска [HePa96].

Последняя универсальная методика, предназначенная для эксплуатирования параллелизма, встроенного во многие алгоритмы, является механизм одна команда – много данных (SIMD), вначале этот термин использовался только в контексте многопроцессорных сред [Fly66]. Команда SIMD выполняет ту же самую операцию, распараллеливая на множество элементов данных, упакованных в одно процессорное слово. Предназначенные для ускорения мультимедийного и коммуникационного программного обеспечения, эти команды могут быть найдены в большем количестве в универсальной архитектуре процессора. Примеры - MMX Intel [PeWe96], VIS UltraSPARC [TONH96], и PA-RISC 2.0 архитектуры MAX[Lee96]. MMH [HaKr97] является примером извлечения выгоды при оптимизации, с использованием новых технологий, - криптографических хеш-функций. Отметим, что комбинация многопоточной выдачи и технологии SIMD создают своего рода параллелизм многопоточный выпуск – много данных (MIMD), также названный параллелизмом SIMD-MIMD [Lee95].

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

- В архитектуре типа регистр-память можно получить доступ к памяти, как к части любой

команды, в то время как в архитектуре регистр-регистр доступ к памяти может быть получен только при загрузке или хранении команд, по этой причине последняя архитектура также называется архитектурой загрузки-хранения.

- Максимальное число операндов АЛУ - 2 или 3. Трехоперандовая команда содержит один операнд адресата и два источника, в то время как в команде с двумя операндами один из двух операнд - источника, а другой – адресат операции.

- Максимальное число операндов команды арифметико-логического устройства (АЛУ) может варьироваться от одного до максимального числа операндов (2 или 3).

Оказывается, что двух¹ классов достаточно, чтобы классифицировать все центральные процессоры, которые будут рассмотрены:

класс 1 – трехоперандовая архитектура хранения-записи (операнды без памяти в команде АЛУ): MIPS, Precision архитектура (PA-RISC), PowerPC, SPARC, Alpha.

класс 2 – двухоперандовая архитектура регистр-память (максимально один операнд памяти в команде АЛУ): 80x86 (включая Pentium и PentiumPro), 680x0.

Отметим, что то же разделение классифицирует процессоры RISC (класс 1) и процессоры CISC процессоры (класс 2).

Таблица 3 суммирует характеристики архитектур, относительно которых были сформулированы требования в конце предыдущего раздела, включая доступный параллелизм аппаратных средств команд АЛУ [Sta96, HePa96, Bha96].

Там приведены самые новые процессоры для каждой архитектуры. Что касается процессоров RISC, то все они являются 64-битовыми, хотя совместимы с их 32-разрядныеми предшественниками. С тех пор как было разработано 64-битовое устройство Alpha, поддержка 32-разрядных операций ограничилась. Вся архитектура RISC поддерживает прямой и обратный порядок байтов, но особенные PA-RISC и Alpha архитектуры не нуждаются в поддержки обоих режимов адресации. Alpha процессорам даже не обязательно поддерживать последовательность соглашений в процессе выполнения программы, а только в процессе загрузки [Dig96].

Другие процессоры RISC могут использовать любой формат, выбираемый или программным обеспечением или аппаратными средствами. Немногие архитектуры являются более чем 2-х потоковыми суперскалярными, но ни одна архитектура не может выпускать параллельно более 2-х команд из интересующего нас подмножества АЛУ: add, логические операции, rotate/shift.

_________

Таблица 3. Краткий обзор последних моделей самых популярных архитектур вычислительных систем. В списке перечислены только те архитектуры, которые реализуют MD4-подобные хеш-функции.

a PA-RISC 2.0 команда shrpw r1, r2, x, t сдвигает конкатенацию r1 и r2 вправо на x бит, и помещает результат в t. Если взять r1 = r2 = t, получим сдвиг.

b R4000 – суперконвейерный (но не суперскалярный), и его конвейерные часы вдвое быстрей частоты его внешних часов, для того, чтобы 2 команды могли быть выпущены в 1 тактовый цикл.

c R10000 является суперскалярным, но не суперконвейерным.

d Архитектура Alpha имеет только 3 32-разрядных целочисленных операции: добавить, вычесть, умножить. Кроме этого, она имеет ряд манипуляций в регистрах 32-разрядных команд, такие как, extract, insert, and mask.

Из таблицы видно, что требования раздела 2, все перечисленные архитектуры RISC выполняют четвертое требование, в то время как первым 3-м требованиям отвечает только PowerPC, и в различной степени другие RISC. Самая серьезная проблема для множества RISC – это, конечно, отсутствие команды сдвига, в то время как у компьютеров со сложным набором системных команд сильные ограничения из-за небольшого набора регистров. В разделе 5 исследован вопрос: предназначена ли такая двунаправленная суперскалярная архитектура для эксплуатации всего параллелизма, доступного в MD4-подобных алгоритмах, используя анализ ограниченного MD5 в [Tou95], как отправную точку.

Пока были рассмотрены только суперконвейерные и/или суперскалярные процессоры.

В настоящее время большинство многопоточных процессоров является суперскалярным, но процессор VLIW вернул свою былую популярность. Пример, последний - недавно выпущенный 32-разрядный VLIW процессор TM-1 of Philips Trimedia [SRD96]. До 5 операций может быть упаковано в одну VLIW-команду и выполниться за один тактовый цикл. Хотя процессор предназначен для обработки мультимедиа-информации, он способен выполнять 5 АЛУ операций, параллельно разрабатываются технологии для возможности быстрого выполнения существующих и проектирующихся криптографических алгоритмов [Cla97].

Для определения объема доступного параллелизма уровня команды в MD4-подобных хеш-функциях, используется анализ критического пути. Алгоритмы представляются как так называемая сеть «активности на дугах», которая является ориентированным графом со взвешенными дугами.

Геометрически граф G определен как набор V (G) вершины v_i связанный набором E (G) дуг e_i. В ориентированном графе дуга e_i – определяется парой <υ_i , υ _j> и рисуется как стрелка от хвоста υ_i к голове υ_j. Направление пути от υ_p до υ_q - последовательность вершин υ_p , υ_i1 , υ_i2 , …., υ_in , υ_q подобные < υ_p, υ_i1>,<υ_i1 , υ_i2>,…< υ_in , υ_q > - дугам в E (G).

Сеть – это граф со взвешенными дугами, то есть, каждой дуге e назначается вес ω (e). В сети «активности на дугах» (АНД-сеть) задачи, которые должны быть выполнены, представлены дугами. Вершина в сети представляет событие, сообщающее о завершении определенных действий. Действия представлены дугами. Вершина не может быть покинута, пока событие в той вершине не произошло. Событие считается свершившимся только, когда все действия, вводящие в событие, были закончены. Вес ω(e), назначенный дуге e, представляет время, необходимое для того, чтобы закончить действия, связанные с e.

Таким образом, длина пути определяется как Σ_eω (e), где e проходит все дуги пути. Это время, которое требуется, чтобы закончить задачи, представленные графом. Действия в сети АНД могут выполняться параллельно, минимальное время, необходимое для выполнения задачи целиком - длина самого длинного пути от начальной вершины до конечной. Такой путь называют критическим путем.

Вычисление арифметических выражений может быть смоделировано как сеть АНД. Начальная вершина соответствует наличию входных данных, действия, представленные дугами, соответствуют арифметическим операциям в выражении, и конечная вершина соответствуют результату выражения. Вес дуг показывает время, которое требуется для завершения соответствующей арифметической операции. Максимальная производительность в вычисляемом арифметического выражении определяется возможностью сделапть критический путь этого выражения как можно более коротким, при этом необходимо использовать максимально возможное количество параллельно выполняющихся отдельных арифметических операции. Однако мы должны принять во внимание, что в конечном счете вычисление выражения будет происходить в архитектуре с многократной выдачей, описанной в предыдущем разделе, то есть, все параллельно выполняемые единицы являются конвейерными, и все вычисляются с одной скоростью. Если не поддерживаются выполнение инструкций в случайном порядке (out-of-order), все операции, выполняющиеся параллельно, передают свои результаты мгновенно, и поэтому вычисление произойдет не быстрее, чем закончится самая медленная операция. По этой причине длина критического пути будет выражена в терминах определенных конвейерной стадией, а не в тактовых циклах. Мера, подобная длине критического пути - глубина, используется при анализе параллельных алгоритмов [Ble96].

Длина критического пути (ДКП) функций сжатия семейства MD4 главным образом определяется ДКП индивидуальных раундов: длина критического пути упреждения максимально равна 2. ДКП каждого раунда равна сумме ДКП каждого шага, таким образом, ДКП функции сжатия может быть получена из ДКП шагов. На каждом шаге обновляется одна из переменных сцепления, и она становится входным параметром следующего шага. Это основная зависимость, которая существует между шагами, которая будет определять их ДКП. Изучение двух последовательных шагов каждого члена семейства MD4 (см. Приложение A) показывает, что, за исключением SHA-1, переменная сцепления, обновленная на текущем шаге, будет входным параметром для булевой функции на следующем шаге. Переменная сцепления, обновленная на текущем шаге, становится доступной только после получения результата булевой функции; сдвига полученной сумма, и, в случае MD5 и RIPEMD-160, сложения к другой переменной сцепки. SHA-1, напротив, делает сдвиг обновленной переменной сцепления, и следующая переменная сцепления становится доступной после всего одного сложения. Минимальные значения ДКП шага приведены в Таблице 4.

SHA-1 использует тот же вид и то же количество операций, что и MD5 и RIPEMD-160, чтобы обновить последовательную переменную: 1 вычисление булевой функции, 4 сложения и 1 сдвиг. Однако, минимальное значение ДКП SHA-1 в два раза меньше ДКП MD5 и RIPEMD-160. Это происходит из-за существенно отличия в организации функций SHA-1 по сравнению со всеми другими:

1. Не применяется сдвиг к сумме промежуточных результатов, но он применяется к индивидуальным последовательным переменным.

2. Ни один из параметров булевой функции, за исключением сдвига, не обновляется на предыдущем шаге, но обновляется за шаг до предыдущего.

Это может быть совпадением, но оказывается, что минимальное значение ДКП фактически равно значению ДКП каждого шага SHA-1, в то время как у других хеш-функций дело обстоит иначе, это будет рассмотрено в дальнейшем. Это кажущееся совпадение, возможно, являлось принципом проектирования. Для других хеш-функций булева функция составляет часть ДКП. Это приводит к увеличению ДКП, если результат не может быть вычислен в пределах 1 стадии, что предполагается для наименьшего результата. Примером служит случай функции «мультиплексор»: , используемого во всех MD4-подобных хеш-функциях. Казалось бы, что x станет доступным только после выполнения and, or и xor, а это занимает еще три стадии [Tou95]. Однако, использование математически эквивалентного выражения [McC94, NMVR95], дает нам использование всего две стадии. Но так как это все еще на 1 больше, чем предложенное наименьшее значение в нижней границе, этот мультиплексор удлиняет ДКП всех шагов, использующих его, на 1, за исключением SHA-1, где булева функция - не обязательная часть критического пути. Отметем, что использование эквивалентного выражения для мультиплексора не всегда окупается с точки зрения ДКП. Рассмотрим альтернативное мультиплексорную функцию ие , используемую в MD5, RIPEMD-128, и RIPEMD-160, и у которой критический путь проходит через y. Не используя перезаписи, оно занимает только 2 стадии, чтобы доставить результат из точки y, ставшей доступной, но использование эквивалентного выражения увеличивает ДКП до 3.

Результаты проведенного анализа ДКП для хеш-функций семейства MD4 приведены в Таблице 5. Анализ сделан, используя и 3-х и 2-х операндовые команды. За исключением первого и третьего шагов округления SHA-1, самый короткий критический путь одинаков для обоих форматов операндов. Однако, для одинаковых ДКП реализация на архитектуре с 2 операндами требует большего количества параллельных единиц, чем на архитектуре с командами с 3 операндами. Этот вывод можно сделать, изучив последние 4 колонки, где дается для обоих форматов необходимое число параллельных единиц и их эффективность. Эффективность вычисляется, как:

и как мера среднего использования параллельных единиц выполнения.

В таблице 5 также показано, что, если используются трехоперандовые команды, самый короткий критический путь всех шагов SHA-1 равен наименьшему значению Таблицы 4 - двум. Этот случай показан на самом ярком примере в Рисунке 1: шаговая функция третьего раунда использует функцию «majority». В результате ДКП функции сжатия у SHA-1 самая короткая из всех хеш-функций семейства MD4, как это показано в Таблице 6. Чтобы получить ДКП, равную двум, в раунде 1 и 3 SHA-1, требуется два параллельных сдвига одной переменной (Рисунок 1). Однако, операция сдвига является унарной операцией, и следовательно ее двухоперандовый формат имеет одинаковый источник и приемник, делая параллельное выполнение над одной переменной невозможным. Сравнение требований Таблицы 6 с ресурсами Таблицы 3 показывает, что существующие суперскалярные архитектуры в состоянии эксплуатировать весь доступный параллелизм командного уровня только для MD4 и MD5, а эти два алгоритма нестойки к коллизиям и поэтому их нельзя рассматривать в дальнейшем, как безопасные [Dob96a, Dob96b, Rob96].

Естественный вопрос, который возникает: насколько реалистичны перспективы выпуска универсального процессора, выдающего 7 команд АЛУ параллельно? Выдавать большое число за такт трудно, так как все более и более сложная логика выдачи оказывает негативное воздействия на время тактового цикла. Поэтому, высокая выдающая способность окупится, если параллельно выполняемые единицы будут достаточно занятыми, так, чтобы увеличение времени цикла было более чем компенсировано увеличением производительности. Анализ ДКП SHA-1 показывает, что некоторые алгоритмы, конечно, содержат достаточно параллелизма командного уровня, необходимого для того, чтобы выдержать такое увеличенное нормы выпуска, но сомнительно, будет ли это иметь место для средней последовательности команд.

Семейство RIPEMD имеет, в отличие от SHA-1, два полностью независимых потока, оставляя участок памяти для того, чтобы использовать параллелизм других уровней: использование многопроцессорной системы, где возможность многократной выдачи каждого процессора ограничена, а не однопроцессорной система с единственным, очень сложным процессором, способный предоставить весь необходимый параллелизм самостоятельно. В этом отношении [HePa96, Раздел 4.10] заявляется, что «до настоящего времени, компьютерные архитекторы не знают, как спроектировать процессоры, которые смогут эффективно эксплуатировать параллелизм командного уровня в многопроцессорной конфигурации». Возможность размещения двух полностью сформированных процессоров на один кристалл, который должен стать реальным в наступающем веке, может привести к новому типу архитектуры, позволяющей процессорам быть более параллельными, чем прежде, и в то же время позволит им достичь очень высокой индивидуальной работоспособности. Поэтому, эксплуатация параллелизма командного уровня семейства RIPEMD в ближайшем будущем кажется намного более вероятным, тогда как каждый из независимых потоков требуют двухсторонней суперскалярной архитектуры, которая уже стала стандартной для большинства процессоров. Алгоритмы с большим параллелизмом командного уровня, чем аппаратные средства могут обеспечить, будет неизбежно приводить к увеличению ДКП. Это можно наглядно показать на примере первого шага раунда 2 MD4. Используя команду с 3 операндами и два параллельных потока, удовлетворяет доступному параллелизму командного уровня, как показано в левой диаграмме рисунка 2. Отметим, что достигается эффективность, равная 100 %. Используя команду с 2 операндами, будет увеличиваться число команд, как операции вида A←B операции C будет требовать двух команд: A←B и A←A операции C. Из-за уже 100%-ой эффективности трехоперандового командного потока, 3 параллельных единицы теперь должны реализовать ту же ДКП=4. Поэтому исполнение, используя только 2 параллельных единицы будет неизбежно приводить к более длинному критическому пути. Это показано в правой диаграмме того же самого рисунка, показывая увеличение ДКП на первой стадии. Левую диаграмму можно рассмотреть на примере PowerPC 604 [SDC94] или PA 7100LC [BKQW95], в то время как правая диаграмма напоминает ситуацию процессора Pentium, за исключением того, что Pentium не может выполнить сдвиг более, чем 1 бита параллельно с любой другой командой, приводя к дальнейшему увеличению ДКП.

Новое поколение специализированных хеш-функций, основанных на MD4 (RIPEMD-128, RIPEMD-160, SHA-1), содержит больше параллелизма командного уровня, чем в состоянии обеспечить используемые в настоящее время универсальные архитектуры. Критический путь SHA-1 короче, чем любой другой MD4-подобной хеш-функции, но для их использования требуется архитектуры с 7 потоками выдачиа. Использование параллелизма уровня команд семейства RIPEMD в ближайшее время выглядит более вероятным, из-за организации в два независимых потока, каждый из которых требует двухпотоковую суперскалярную архитектуру. Недавняя разработка нового пятипотокового процессора VLIW, открывает перспективы, прежде всего направленные на обработку мультимедиа информации.

[BKQW95] M. Bass, P. Knebel, D.W. Quint, W.L. Walker, “The PA 7100LC microprocessor: a case study of IC design decisions in a competitive environment,” HP Journal, Vol. 46, No. 2, April 1995, pp. 12–22.

[Bha96] D.P. Bhandarkar, Alpha implementations and architecture, Digital Press, Boston, MA, 1996.

[Ble96] G.E. Blelloch, “Programming parallel algorithms,” Communications of the ACM, Vol. 39, No. 3, 1996, pp. 85–97.

[BGV96] A. Bosselaers, R. Govaerts, J. Vandewalle, “Fast hashing on the Pentium,” Advances in Cryptology, Proceedings Crypto’96, LNCS 1109, N. Koblitz, Ed., Springer-Verlag, 1996, pp. 298–312.

[Cla97] C. Clapp, “Optimizing a fast stream cipher for VLIW, SIMD, and superscalar processors,” Fast Software Encryption, LNCS, E. Biham, Ed., Springer-Verlag, 1997, to appear.

[Dig96] Alpha architecture handbook, Version 3, Digital Equipment Corp., Maynard, MA, 1996.

[Dob96a] H. Dobbertin, “Cryptanalysis of MD4,” Fast Software Encryption,LNCS 1039, D. Gollmann, Ed., Springer-Verlag, 1996, pp. 53–69. 13

[Dob96b] H. Dobbertin, “The status of MD5 after a recent attack,” CryptoBytes,Vol. 2, No. 2, 1996, pp. 1–6.

[DBP96] H. Dobbertin, A. Bosselaers, B. Preneel, “RIPEMD-160: A Strengthened Version of RIPEMD,” Fast Software Encryption, LNCS 1039, D. Gollmann, Ed., Springer-Verlag, 1996, pp. 71–82. Final version available via ftp at ftp.esat.kuleuven.ac.be/pub/COSIC/bosselae/ripemd/.

[FIPS180-1] FIPS 180-1, “Secure hash standard,” US Department of Commerce/NIST, Washington D.C., April 1995.

[Fly66] M. Flynn, “Very high-speed computing systems,” Proceedings of the IEEE, Vol. 54, No. 12, 1966, pp. 1901–1909.

[HaKr97] S. Halevi and H. Krawczyk, “MMH: Software message authentication in the Gbit/second rates,” Fast Software Encryption, LNCS, E. Biham, Ed., Springer-Verlag, 1997, to appear.

[HePa96] J.L. Hennessy and D.A. Patterson, Computer architecture: a quantitative approach, 2nd edition, Morgan Kaufmann Publishers, San Francisco, 1996.

[Lee95] R. Lee, “Accelerating multimedia with enhanced microprocessors,” IEEE Micro, Vol. 15, No. 2, April 1995, pp. 22–32.

[Lee96] R. Lee, “Subword parallelism with MAX-2,” IEEE Micro, Vol. 16, No. 4, August 1996, pp. 51–59.

[NMVR95] D. Naccache, D. M’RaЁıhi, S. Vaudenay, D. Raphaeli, “Can DSA be improved? Complexity trade-offs with the Digital Signature Standard,” Advances in Cryptology, Proceedings Eurocrypt’94, LNCS 950, A. De Santis, Ed., Springer-Verlag, 1995, pp. 77–85.

[McC94] K.S. McCurley, “A fast portable implementation of the secure hash algorithm, III,” Technical Report SAND93-2591, Sandia National Laboratories, 1994.

[PeWe96] A. Peleg and U. Weiser, “MMX technology extension to the Intel architecture,” IEEE Micro, Vol. 16, No. 4, August 1996, pp. 42–50.

[RIPE95] RIPE, “Integrity Primitives for Secure Information Systems. Final Report of RACE Integrity Primitives Evaluation (RIPE-RACE 1040),” LNCS 1007, A. Bosselaers and B. Preneel, Eds., Springer-Verlag, 1995.

[Riv92a] R.L. Rivest, “The MD4 message-digest algorithm,” Request for Comments (RFC) 1320, Internet Activities Board, Internet Privacy Task Force, April 1992.

[Riv92b] R.L. Rivest, “The MD5 message-digest algorithm,” Request for Comments (RFC) 1321, Internet Activities Board, Internet Privacy Task Force, April 1992.

[Rob96] M. Robshaw, “On recent results for MD2, MD4 and MD5,” Bulletin No. 4, RSA Laboratories, November 1996.

[SRD96] G.A. Slavenburg, S. Rathnam, H. Dijkstra, “The Trimedia TM-1 PCI VLIW media processor,” Hot Chips VIII Conference, Stanford University, Palo Alto, CA, 1996.

[SDC94] S.P. Song, M. Denman, J. Chang, “The PowerPc 604 RISC microprocessor,” IEEE Micro, Vol. 14, No. 5, October 1994, pp. 8–17.

[Sta96] P.H. Stakem, A practitioner’s guide to RISC microprocessor architecture, John Wiley & Sons, New York, 1996.

[Tou95] J. Touch, “Performance analysis of MD5,” Proceedings of ACM SIGCOMM’ 95, Comp. Comm. Review, Vol. 25, No. 4, 1995, pp. 77-86.

[TONH96] M. Tremblay, J.M. O’Connor, V. Narayanan, L. He, “VIS speeds new media processing,” IEEE Micro, Vol. 16, No. 4, August 1996, pp. 10–20.