Blowfish (шифр) - Blowfish (cipher)
Общий | |
---|---|
Дизайнеров | Брюс Шнайер |
Впервые опубликовано | 1993 г. |
Преемники | Twofish |
Детали шифра | |
Ключевые размеры | 32–448 бит |
Размеры блоков | 64 бит |
Структура | Сеть Фейстеля |
Раундов | 16 |
Лучший публичный криптоанализ | |
Четыре раунда Blowfish подвержены дифференциальной атаке второго порядка (Rijmen, 1997); для класса слабых ключей 14 раундов Blowfish можно отличить от псевдослучайной перестановки (Vaudenay, 1996). |
Blowfish - это блочный шифр с симметричным ключом , разработанный в 1993 году Брюсом Шнайером и включенный во многие комплекты шифров и продукты для шифрования. Blowfish обеспечивает хорошую скорость шифрования в программном обеспечении, и на сегодняшний день не было найдено никакого эффективного криптоанализа . Однако теперь расширенному стандарту шифрования (AES) уделяется больше внимания, и Шнайер рекомендует Twofish для современных приложений.
Шнайер разработал Blowfish как алгоритм общего назначения, задуманный как альтернативу устаревшему DES и свободный от проблем и ограничений, связанных с другими алгоритмами. На момент выпуска Blowfish многие другие разработки были патентами, коммерческими или государственными секретами. Шнайер заявил, что «Blowfish не запатентован и останется таковым во всех странах. Таким образом, алгоритм становится общественным достоянием и может свободно использоваться кем угодно».
Примечательные особенности дизайна включают зависящие от клавиш S-блоки и очень сложную схему расположения клавиш .
Алгоритм
Blowfish имеет 64-битный размер блока и переменную длину ключа от 32 бит до 448 бит. Это 16- этапный шифр Фейстеля, в котором используются большие зависящие от ключа S-блоки . По структуре он напоминает CAST-128 , в котором используются фиксированные S-блоки.
На следующей диаграмме показана процедура шифрования Blowfish. Каждая строка представляет 32 бита. Существует пять массивов подключей: один P-массив из 18 элементов (обозначен на схеме как K, чтобы избежать путаницы с открытым текстом) и четыре S-блока из 256 элементов (S0, S1, S2 и S3).
Каждый раунд r состоит из 4 действий:
Действие 1 | Выполните XOR левой половины (L) данных с r- й записью P-массива |
Действие 2 | Используйте данные, обработанные методом XOR, в качестве входных данных для F-функции Blowfish. |
Действие 3 | Выполните XOR выхода F-функции с правой половиной (R) данных |
Действие 4 | Поменять местами L и R |
F-функция разделяет 32-битный ввод на четыре 8-битных четверти и использует четверти как ввод для S-блоков. S-блоки принимают 8-битный ввод и производят 32-битный вывод. Выходы складываются по модулю 2 32 и подвергаются операции XOR для получения окончательного 32-битного вывода (см. Изображение в правом верхнем углу).
После 16-го раунда отмените последний обмен и выполните XOR L с K18 и R с K17 (выходное отбеливание).
Расшифровка точно такая же, как и шифрование, за исключением того, что P1, P2, ..., P18 используются в обратном порядке. Это не так очевидно, потому что xor коммутативен и ассоциативен. Распространенным заблуждением является использование обратного порядка шифрования в качестве алгоритма дешифрования (то есть сначала XORing P17 и P18 для блока зашифрованного текста, а затем использование P-записей в обратном порядке).
Ключевое расписание Blowfish начинается с инициализации P-массива и S-блоков значениями, полученными из шестнадцатеричных цифр числа пи , которые не содержат очевидного шаблона ( ничего не вижу в моем номере рукава ). Затем секретный ключ побайтово, циклически повторяя ключ, если необходимо, подвергается операции XOR со всеми P-записями по порядку. Затем 64-битный нулевой блок шифруется алгоритмом в его нынешнем виде. Полученный зашифрованный текст заменяет P 1 и P 2 . Затем тот же зашифрованный текст снова зашифровывается с новыми подключами, и новый зашифрованный текст заменяет P 3 и P 4 . Это продолжается, заменяя весь P-массив и все записи S-блока. В целом алгоритм шифрования Blowfish будет запускаться 521 раз для генерации всех подключей - обрабатывается около 4 КБ данных.
Поскольку P-массив имеет длину 576 бит, а байты ключа подвергаются операции XOR через все эти 576 бит во время инициализации, многие реализации поддерживают размеры ключей до 576 бит. Причина этого - несоответствие между исходным описанием Blowfish, в котором используются 448-битные ключи, и его эталонной реализацией, в которой используются 576-битные ключи. Тестовые векторы для проверки сторонних реализаций также были созданы с 576-битными ключами. Когда его спросили, какая версия Blowfish является правильной, Брюс Шнайер ответил: «Тестовые векторы должны использоваться для определения единственной истинной Blowfish».
Другое мнение состоит в том, что ограничение в 448 бит присутствует, чтобы гарантировать, что каждый бит каждого подключа зависит от каждого бита ключа, поскольку последние четыре значения P-массива не влияют на каждый бит зашифрованного текста. Этот момент следует принимать во внимание для реализаций с другим числом раундов, поскольку, хотя он увеличивает безопасность от исчерпывающей атаки, он ослабляет безопасность, гарантированную алгоритмом. А учитывая медленную инициализацию шифра при каждой смене ключа, ему предоставляется естественная защита от атак грубой силы, что на самом деле не оправдывает размеры ключей, превышающие 448 бит.
Blowfish в псевдокоде
uint32_t P[18];
uint32_t S[4][256];
uint32_t f (uint32_t x) {
uint32_t h = S[0][x >> 24] + S[1][x >> 16 & 0xff];
return ( h ^ S[2][x >> 8 & 0xff] ) + S[3][x & 0xff];
}
void blowfish_encrypt(uint32_t *L, uint32_t *R) {
for (short r = 0; r < 16; r++) {
*L = *L ^ P[r];
*R = f(*L) ^ *R;
swap(L, R);
}
swap(L, R);
*R = *R ^ P[16];
*L = *L ^ P[17];
}
void blowfish_decrypt(uint32_t *L, uint32_t *R) {
for (short r = 17; r > 1; r--) {
*L = *L ^ P[r];
*R = f(*L) ^ *R;
swap(L, R);
}
swap(L, R);
*R = *R ^ P[1];
*L = *L ^ P[0];
}
// ...
// initializing the P-array and S-boxes with values derived from pi; omitted in the example (you can find them below)
// ...
{
/* initialize P box w/ key*/
uint32_t k;
for (short i = 0, p = 0; i < 18; i++) {
k = 0x00;
for (short j = 0; j < 4; j++) {
k = (k << 8) | (uint8_t) key[p];
p = (p + 1) % key_len;
}
P[i] ^= k;
}
/* blowfish key expansion (521 iterations) */
uint32_t l = 0x00, r = 0x00;
for (short i = 0; i < 18; i+=2) {
blowfish_encrypt(&l, &r);
P[i] = l;
P[i+1] = r;
}
for (short i = 0; i < 4; i++) {
for (short j = 0; j < 256; j+=2) {
blowfish_encrypt(&l, &r);
S[i][j] = l;
S[i][j+1] = r;
}
}
}
Blowfish на практике
Blowfish - это быстрый блочный шифр , кроме случаев смены ключей. Каждый новый ключ требует предварительной обработки, эквивалентной шифрованию около 4 килобайт текста, что очень медленно по сравнению с другими блочными шифрами. Это предотвращает его использование в некоторых приложениях, но не является проблемой для других.
В одном приложении медленное изменение ключа Blowfish на самом деле является преимуществом: метод хеширования пароля (crypt $ 2, т.е. bcrypt), используемый в OpenBSD, использует алгоритм, производный от Blowfish, который использует расписание медленных ключей; идея состоит в том, что требуемые дополнительные вычислительные усилия обеспечивают защиту от атак по словарю . См. Растяжку клавиш .
Иглобрюхие имеет объем памяти , чуть более 4 килобайт оперативной памяти . Это ограничение не является проблемой даже для старых настольных и портативных компьютеров , хотя оно препятствует использованию в самых маленьких встроенных системах, таких как ранние смарт-карты .
Blowfish был одним из первых безопасных блочных шифров, не защищенных какими-либо патентами и, следовательно, свободно доступными для всех. Это преимущество способствовало его популярности в криптографическом программном обеспечении.
bcrypt - это функция хеширования паролей, которая в сочетании с переменным числом итераций («стоимость» работы) использует дорогостоящую фазу настройки ключей Blowfish для увеличения рабочей нагрузки и продолжительности хеш-вычислений, дополнительно уменьшая угрозы от атак грубой силы.
bcrypt - это также название кроссплатформенной утилиты для шифрования файлов, разработанной в 2002 году и реализующей Blowfish.
Слабость и преемники
Использование Blowfish 64-битного размера блока (в отличие от, например, 128-битного размера блока AES) делает его уязвимым для атак по случаю дня рождения , особенно в таких контекстах, как HTTPS . В 2016 году атака SWEET32 продемонстрировала, как использовать атаки по случаю дня рождения для восстановления открытого текста (т. Е. Дешифрования зашифрованного текста) для шифров с размером блока 64-бит. Проект GnuPG рекомендует не использовать Blowfish для шифрования файлов размером более 4 ГБ из-за небольшого размера блока.
Вариант Blowfish с уменьшенным числом раундов известен своей восприимчивостью к атакам с использованием известного открытого текста на рефлексивно слабые ключи. Реализации Blowfish используют 16 раундов шифрования и не подвержены этой атаке.
Брюс Шнайер порекомендовал перейти на своего преемника Blowfish Twofish .
Смотрите также
использованная литература
внешние ссылки
- Брюс Шнайер. «Алгоритм шифрования Blowfish» .
- Брюс Шнайер. «Продукты, в которых используется Blowfish» .