Давайте сделаем шаг назад.Прежде всего, что мы подразумеваем под H(k|m)?И для чего это?
Цель здесь следующая.Алиса и Боб имеют секретный ключ.Как они это делят, мы не знаем.Каким-то образом Алиса и Боб договорились о секретном ключе, и никто больше не знает его.
Алиса хочет отправить сообщение Бобу.Алисе все равно, сможет ли кто-нибудь прочитать сообщение, но Алисе очень важно, чтобы Боб знал, что Алиса написала сообщение.
Они придумали следующую схему.Алиса создаст сообщение, состоящее из секретного ключа, за которым следует остальная часть сообщения.Затем она все хеширует.Затем она передает сообщение без секретного ключа Бобу вместе с хешем.
Боб пытается проверить, пришло ли сообщение от Алисы.Он помещает секретный ключ перед сообщением и хэширует его.Если Боб получает тот же хеш, то Боб знает, что тот, кто сделал сообщение, обладает секретным ключом.Он знает, что это был не он, так что, должно быть, это была Алиса.
Эта схема небезопасна.Мэллори хочет отправить ложное сообщение Бобу и обмануть его, думая, что это от Алисы.
Однажды Алиса берет свой секретный ключ «123SesameStreet» и сообщение «Дорогой Боб, я люблю тебя!», И добавляет их вместе к «123SesameStreetDear Bob, я люблю тебя!»Она хэширует это на «398942358092» и отправляет хэш и сообщение «Дорогой Боб, я люблю тебя!»Бобу
Мэллори перехватывает сообщение, прежде чем оно попадает к Бобу.Мэллори не знает секретный ключ, но она знает сообщение и хэш.Мэллори настраивает алгоритм SHA1 для получения состояния 398942358092, а затем запускает символы «Шучу, я тебя ненавижу!» И получает хэш 92358023934. Теперь Мэллори отправляет новый хэш и сообщение «Дорогой Боб, я люблю тебя».Шучу, я тебя ненавижу!Бобу.
Насколько точно это работает?Вот сделка.По сути, SHA1 работает как этот упрощенный эскиз:
int hash = 0;
foreach(char c in message)
hash = MakeNextHash(hash, c);
То есть вы начинаете с нуля.Затем вы хешируете первый символ и число 0. Затем вы хешируете этот хеш со вторым символом .Это создает новый хэш.Затем вы хешируете , что с третьим символом, чтобы создать третий хеш.Продолжайте делать это, пока у вас не закончатся персонажи;последний хеш, который вы сделали, - это хеш всего сообщения.
Реальный алгоритм SHA1 использует блоки размером больше одного символа и состояние больше целого, но в основном так и происходит.Он преобразует группу состояний по одному блоку за раз, используя предыдущее состояние в качестве входных данных для следующего состояния.
Так что, если я скажу вам «Вот строка M. Кроме того, строка KM имеет хэш H (K | M) «.тогда, очевидно, вы можете вычислить хеш H (K | M | Z) KMZ для любого Z, , даже если вы не знаете K .Вы просто говорите:
int hash = HKM;
foreach(char c in Z)
hash = MakeNextHash(hash, c);
, и в результате получается H (K | M | Z), даже если вы не знаете K.
Итак, вы видите, как это происходит.Боб добавляет секретный ключ к сообщению и запускает его по алгоритму SHA1, и он возвращает правильный хеш.Таким образом, он подтвердил, что сообщение пришло от Алисы, хотя на самом деле половина сообщения от Мэллори.
Вот почему ключ должен идти последним.Вы должны поставить ключ после сообщения, а не до.Вы бы подумали.Оказывается, что хотя атака теперь не является тривиальной , как это происходит со схемой «ключ-в-первых», она все же не является безопасной.Схема H(m|k) также не годится.
Почему бы и нет?
Предположим, Мэллори перехватила сообщение M и хэш H, который является H (M | K), где K является секретом.ключ.Она предотвращает поступление сообщения.
Мэллори достаточно легко вычисляет H (M).Трудная часть состоит в том, что Мэллори выводит вредоносное сообщение N, такое что H (N) = H (M).Как она это делает, мы пока не знаем, но широко распространено мнение, что такая техника существует, мы просто еще не нашли ее.
Мэллори знает, что H (N | K) - это то же самое, что и H (M | K), по тем же рассуждениям, что и раньше - потому что для вычисления H (N | K) мы собираемся сделать:
int hash = HN;
foreach(char c in key)
....
для выработки H (N | K).Мэллори не нужно знать K, чтобы сделать сообщение N таким, что H (N | K) есть H (M | K).
Так что теперь Мэллори отправляет N и H (M | K) / H (N| К) - это одно и то же - для Боба.Боб добавляет К к N и проверяет, что сообщение пришло от Алисы, хотя на самом деле оно пришло от Мэллори.
Становится хуже.Предположим, Мэллори захватила миллион сообщений M1, M2, ... и миллион хешей H (M1 | K), H (M2 | K), ... которые прошли между Алисой и Бобом.Мэллори необходимо составить сообщение N так, чтобы H (N) соответствовало любому из H (M1), H (M2), H (M3), ... Ее работа стала в миллион раз легче.Она находит такое сообщение N, что H (N) соответствует, скажем, H (M1234), а затем отправляет N и H (M1234 | K) Бобу.Боб не замечает, что он видел этот хэш раньше, и считает, что это сообщение от Алисы.
Становится хуже.Давайте немного изменим схему, чтобы увидеть, как она ухудшается.У Кэрол есть сообщение, которое она хотела бы отправить Бобу через Алису.Сообщение М: «Привет, Боб, это Кэрол. Давай мы с Алисой вместе пообедаем вместе на следующей неделе. Если Алиса согласится, она отправит тебе это сообщение со своим аутентификатором».Кэрол не знает секретного ключа K, но Алиса знает.Алиса соглашается с сообщением M, поэтому она вычисляет H (M | K) и отправляет M и H (M | K) Бобу.
Теперь Мэллори хочет вызвать проблемы, поэтому она ищет два сообщения B (для доброкачественных) и D (для опасных), таких, что H (B) равно H (D), и таких, что Алиса согласится с B, но не согласится с D. Это намного проще, чем поиск сообщения N, которое соответствует данное сообщение от Алисы, потому что теперь Мэллори выбирает оба сообщения.Задача поиска столкновения на несколько порядков проще.
Мэллори находит эти два сообщения и отправляет B Алисе.Алиса соглашается с сообщением, вычисляет H (B | K) и отправляет H (B | K) и B Бобу.Мэллори перехватывает сообщение B и заменяет его на D. H (B | K) и H (D | K) те же самые рассуждения, что и раньше.Боб получает сообщение D и проверяет, что H (D | K) совпадает с хэшем, который он послал, поэтому он знает, что Алиса одобрила сообщение, хотя она этого не сделала.
Никто еще не нашел способзаставить SHA1 надежно создавать подобные коллизии, но почти все считают, что мы решим эту проблему.
Первая мораль этой истории состоит в том, что не используйте ни один из этих методов в качестве средства проверки сообщений ,Первое тривиально нарушено, а второе, скорее всего, будет сломано в нашей жизни.
Второй принцип: никогда не позволяйте потенциальному злоумышленнику выбрать сообщение, которое вы собираетесь обработать, с помощью своего секретного ключа.