Avalanche Effect
Читая статью о хэшировании, наткнулся на интересное описание лавинного эффекта, который должен проявляться у хороших хэш-функций и крипто-алгоритмов.
Суть эффекта проста: при изменении одного бита в ключе или шифруемых данных должна изменяться примерно половина всех выходных битов. В русской статье приведены примеры с изменением одного бита во входных данных для популярных алгоритмов: SHA-1, MD5, AES, RC4:
SHA-1(0110 0001 0110 0001 0110 0001 0110 0001) = '70c881d4a26984ddce795f6f71817c9cf4480e79'
SHA-1(0110 0001 0110 0011 0110 0001 0110 0001) = 'c6fdc1a445881de1f33e09cf00420a57b493b96d'
SHA-1(0110 0001 0110 0001 0110 0001 0110 0011) = '00b25f15212ed225d3389b5f75369c82084b3a76'
---
MD5(0110 0001 0110 0001 0110 0001 0110 0001) = '74b87337454200d4d33f80c4663dc5e5'
MD5(0110 0001 0110 0011 0110 0001 0110 0001) = 'ca7de9e17429612452a717a44c36e688'
MD5(0110 0001 0110 0001 0110 0001 0110 0011) = '3963a2ba65ac8eb1c6e2140460031925'
---
AES(key = "aaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaa") = '5188c6474b228cbdd242e9125ebe1d53'
AES(key = "aaaaaaaaaaaaaaaa", "aacaaaaaaaaaaaaa") = 'f7e5c1118f5cb86198e37ff7a29974bc'
AES(key = "aacaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaa") = '2c50b5cac9c755d67aa61b87c26248eb'
AES(key = "aacaaaaaaaaaaaaa", "aacaaaaaaaaaaaaa") = '87c09128de852b990b3dfbd65c7d9094'
---
RC4(key = "aaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaa") = '71ddf97f23b8e42a4f0ccc463d7da4aa'
RC4(key = "aaaaaaaaaaaaaaaa", "aacaaaaaaaaaaaaa") = '3d0feab630a32d1d0654c5481bd9ddd9'
RC4(key = "aacaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaa") = '476266d77453695b6cee682f23b0c51d'
RC4(key = "aacaaaaaaaaaaaaa", "aacaaaaaaaaaaaaa") = '3139d4506185d48e9b9e3dbbd4b57ec2'
Невооруженным глазом даже и не заметно, чем же похожи выходные строки. Но вот если применить инструмент для множественного выравнивания строк (PATL, а именно demos/multi_align), можно автоматически получить интересный результат:
SHA-1(0110 0001 0110 000 1 0110 0001 0110 000 1) = '7 0c 881d4a26984ddce795f6f71817c 9cf4480e79'
SHA-1(0110 0001 0110 00 11 0110 0001 0110 000 1) = 'c6fdc1a445 881d e 1f33e09cf0 04 20a57b493b96d'
SHA-1(0110 0001 0110 000 1 0110 0001 0110 00 11) = '0 0b25f15212ed225d3389b5f7536 9c 8 208 4b3a76 '
^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^ ^^^^^^ ^ ^^^^ ^ ^ ^^^ ^^ ^^ ^ ^ ^ ^
---
MD5(0110 0001 0110 0001 0110 0001 0110 0001 ) = ' 74b873374 5 42 00d4d33f80c4663dc5e5'
MD5(0110 0001 0110 0011 0110 0001 0110 0001 ) = 'ca7de9e 17 429612452a717a44c36e688'
MD5(0110 000 1 0110 0001 0110 0001 0110 0011) = ' 3963a2ba65ac8eb1c6e214046 00 3192 5'
^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^ ^^^^^^ ^ ^ ^ ^ ^^ ^^ ^ ^^
---
AES(key = "aaa aaaaaaaaaaaaa", "aaa aaaaaaaaaaaaa") = ' 5 188c6474b228cbdd242e9125ebe1d 5 3'
AES(key = "aaa aaaaaaaaaaaaa", "aa caaaaaaaaaaaaa") = 'f 7e 5c1118f 5cb8 619 8e37ff7a29974bc'
AES(key = "aa caaaaaaaaaaaaa", "aaa aaaaaaaaaaaaa") = '2c 50b 5cac9c755d67aa 61b87c26248e b '
AES(key = "aa caaaaaaaaaaaaa", "aa caaaaaaaaaaaaa") = '8 7c0 9128 de852b990b3dfbd65c 7d9094'
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^ ^ ^^ ^^^ ^ ^ ^ ^^ ^ ^^ ^^ ^ ^
---
RC4(key = "aaa aaaaaaaaaaaaa", "aaa aaaaaaaaaaaaa") = ' 7 1ddf97f23b8e42a4f0cc c 463 d7da4aa'
RC4(key = "aaa aaaaaaaaaaaaa", "aa caaaaaaaaaaaaa") = ' 3d0feab630a32d1d 0654c5481bd9ddd9 '
RC4(key = "aa caaaaaaaaaaaaa", "aaa aaaaaaaaaaaaa") = '476266d77453695b6cee682f23b0c 5 1d '
RC4(key = "aa caaaaaaaaaaaaa", "aa caaaaaaaaaaaaa") = '3139 d 45 06185d48e9b9e3dbbd4b57ec 2'
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^ ^^^ ^ ^ ^^ ^ ^ ^^ ^ ^ ^ ^ ^ ^
Символом '^' обозначены совпадения в выравненных строках, совпадающие подстроки выравнены с помощью пробелов. Получается что все алгоритмы каким-то образом значительно изменили выходные строки, но в SHA-1 и AES сразу становятся заметны совпадающие подстроки длиной больше двух: "881d", "9cf", "912", которые различаются только позицией в строке.
Я не берусь судить, почему так получается, возможно это следствие неудовлетворительной конфузии (в той же статье: "метод, при котором зависимость ключа и выходных данных делается как можно более сложной"), мне просто показался интересным вариант применения множественного выравнивания в этой области.
UPD. Неплохо бы еще дополнить анализ алгоритмом Longest Common Substring для многих строк, так как нас могут заинтересовать совпадающие подстроки, идущие не по порядку.
Суть эффекта проста: при изменении одного бита в ключе или шифруемых данных должна изменяться примерно половина всех выходных битов. В русской статье приведены примеры с изменением одного бита во входных данных для популярных алгоритмов: SHA-1, MD5, AES, RC4:
SHA-1(0110 0001 0110 0001 0110 0001 0110 0001) = '70c881d4a26984ddce795f6f71817c9cf4480e79'
SHA-1(0110 0001 0110 0011 0110 0001 0110 0001) = 'c6fdc1a445881de1f33e09cf00420a57b493b96d'
SHA-1(0110 0001 0110 0001 0110 0001 0110 0011) = '00b25f15212ed225d3389b5f75369c82084b3a76'
---
MD5(0110 0001 0110 0001 0110 0001 0110 0001) = '74b87337454200d4d33f80c4663dc5e5'
MD5(0110 0001 0110 0011 0110 0001 0110 0001) = 'ca7de9e17429612452a717a44c36e688'
MD5(0110 0001 0110 0001 0110 0001 0110 0011) = '3963a2ba65ac8eb1c6e2140460031925'
---
AES(key = "aaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaa") = '5188c6474b228cbdd242e9125ebe1d53'
AES(key = "aaaaaaaaaaaaaaaa", "aacaaaaaaaaaaaaa") = 'f7e5c1118f5cb86198e37ff7a29974bc'
AES(key = "aacaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaa") = '2c50b5cac9c755d67aa61b87c26248eb'
AES(key = "aacaaaaaaaaaaaaa", "aacaaaaaaaaaaaaa") = '87c09128de852b990b3dfbd65c7d9094'
---
RC4(key = "aaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaa") = '71ddf97f23b8e42a4f0ccc463d7da4aa'
RC4(key = "aaaaaaaaaaaaaaaa", "aacaaaaaaaaaaaaa") = '3d0feab630a32d1d0654c5481bd9ddd9'
RC4(key = "aacaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaa") = '476266d77453695b6cee682f23b0c51d'
RC4(key = "aacaaaaaaaaaaaaa", "aacaaaaaaaaaaaaa") = '3139d4506185d48e9b9e3dbbd4b57ec2'
Невооруженным глазом даже и не заметно, чем же похожи выходные строки. Но вот если применить инструмент для множественного выравнивания строк (PATL, а именно demos/multi_align), можно автоматически получить интересный результат:
SHA-1(0110 0001 0110 000 1 0110 0001 0110 000 1) = '7 0c 881d4a26984ddce795f6f71817c 9cf4480e79'
SHA-1(0110 0001 0110 00 11 0110 0001 0110 000 1) = 'c6fdc1a445 881d e 1f33e09cf0 04 20a57b493b96d'
SHA-1(0110 0001 0110 000 1 0110 0001 0110 00 11) = '0 0b25f15212ed225d3389b5f7536 9c 8 208 4b3a76 '
^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^ ^^^^^^ ^ ^^^^ ^ ^ ^^^ ^^ ^^ ^ ^ ^ ^
---
MD5(0110 0001 0110 0001 0110 0001 0110 0001 ) = ' 74b873374 5 42 00d4d33f80c4663dc5e5'
MD5(0110 0001 0110 0011 0110 0001 0110 0001 ) = 'ca7de9e 17 429612452a717a44c36e688'
MD5(0110 000 1 0110 0001 0110 0001 0110 0011) = ' 3963a2ba65ac8eb1c6e214046 00 3192 5'
^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^ ^^^^^^ ^ ^ ^ ^ ^^ ^^ ^ ^^
---
AES(key = "aaa aaaaaaaaaaaaa", "aaa aaaaaaaaaaaaa") = ' 5 188c6474b228cbdd242e9125ebe1d 5 3'
AES(key = "aaa aaaaaaaaaaaaa", "aa caaaaaaaaaaaaa") = 'f 7e 5c1118f 5cb8 619 8e37ff7a29974bc'
AES(key = "aa caaaaaaaaaaaaa", "aaa aaaaaaaaaaaaa") = '2c 50b 5cac9c755d67aa 61b87c26248e b '
AES(key = "aa caaaaaaaaaaaaa", "aa caaaaaaaaaaaaa") = '8 7c0 9128 de852b990b3dfbd65c 7d9094'
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^ ^ ^^ ^^^ ^ ^ ^ ^^ ^ ^^ ^^ ^ ^
---
RC4(key = "aaa aaaaaaaaaaaaa", "aaa aaaaaaaaaaaaa") = ' 7 1ddf97f23b8e42a4f0cc c 463 d7da4aa'
RC4(key = "aaa aaaaaaaaaaaaa", "aa caaaaaaaaaaaaa") = ' 3d0feab630a32d1d 0654c5481bd9ddd9 '
RC4(key = "aa caaaaaaaaaaaaa", "aaa aaaaaaaaaaaaa") = '476266d77453695b6cee682f23b0c 5 1d '
RC4(key = "aa caaaaaaaaaaaaa", "aa caaaaaaaaaaaaa") = '3139 d 45 06185d48e9b9e3dbbd4b57ec 2'
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^ ^^^ ^ ^ ^^ ^ ^ ^^ ^ ^ ^ ^ ^ ^
Символом '^' обозначены совпадения в выравненных строках, совпадающие подстроки выравнены с помощью пробелов. Получается что все алгоритмы каким-то образом значительно изменили выходные строки, но в SHA-1 и AES сразу становятся заметны совпадающие подстроки длиной больше двух: "881d", "9cf", "912", которые различаются только позицией в строке.
Я не берусь судить, почему так получается, возможно это следствие неудовлетворительной конфузии (в той же статье: "метод, при котором зависимость ключа и выходных данных делается как можно более сложной"), мне просто показался интересным вариант применения множественного выравнивания в этой области.
UPD. Неплохо бы еще дополнить анализ алгоритмом Longest Common Substring для многих строк, так как нас могут заинтересовать совпадающие подстроки, идущие не по порядку.