Введение
Тип криптографической атаки
A birthday attack is a bruteforce collision attack that exploits the mathematics behind the birthday problem in probability theory. This attack can be used to abuse communication between two or more parties. The attack depends on the higher likelihood of collisions found between random attack attempts and a fixed degree of permutations (pigeonholes). With a birthday attack, it is possible to find a collision of a hash function with chance in , There is a general (though disputed) result that quantum computers can perform birthday attacks, thus breaking collision resistance, in
Although there are some digital signature vulnerabilities associated with the birthday attack, it cannot be used to break an encryption scheme any faster than a brute force attack.
Атака на день рождения — это метод перебора, направленный на поиск коллизий, который использует математические принципы, лежащие в основе задачи о днях рождения в теории вероятностей. Эта атака может быть использована для нарушения обмена данными между двумя или более сторонами. Атака основана на более высокой вероятности обнаружения коллизий при случайных попытках и фиксированном количестве возможных вариантов (ячеек). При атаке на день рождения можно найти коллизию хеш-функции с вероятностью в . Существует общепринятый (хотя и оспариваемый) результат, согласно которому квантовые компьютеры могут выполнять атаки на день рождения, тем самым обходя устойчивость к коллизиям, за . Несмотря на то, что атака на день рождения связана с некоторыми уязвимостями цифровых подписей, она не позволяет взломать схему шифрования быстрее, чем методом полного перебора.
A birthday attack is a bruteforce collision attack that exploits the mathematics behind the birthday problem in probability theory. This attack can be used to abuse communication between two or more parties. The attack depends on the higher likelihood of collisions found between random attack attempts and a fixed degree of permutations (pigeonholes). With a birthday attack, it is possible to find a collision of a hash function with chance in , There is a general (though disputed) result that quantum computers can perform birthday attacks, thus breaking collision resistance, in
Although there are some digital signature vulnerabilities associated with the birthday attack, it cannot be used to break an encryption scheme any faster than a brute force attack.
Понимание проблемы
В качестве примера рассмотрим сценарий, в котором учитель с классом из 30 учеников (n = 30) спрашивает дату рождения каждого (для простоты, игнорируя високосные годы), чтобы определить, есть ли у двух учеников одинаковая дата рождения (что соответствует коллизии хэша, как описано далее). Интуитивно, эта вероятность может показаться небольшой. Однако, контринтуитивно, вероятность того, что хотя бы у двух учеников совпадает день рождения, составляет около 70% (при n = 30), согласно формуле. Если бы учитель выбрал конкретную дату (например, 16 сентября), то вероятность того, что хотя бы один ученик родился в этот день, составила бы около 7,9%. При атаке на день рождения злоумышленник подготавливает множество различных вариантов безобидных и вредоносных контрактов, каждый из которых имеет цифровую подпись. Ищется пара безобидного и вредоносного контрактов с одинаковой подписью. В этом вымышленном примере предположим, что цифровая подпись строки – это первый байт ее SHA 256 хэша. Найденная пара выделена зеленым цветом – обратите внимание, что поиск пары безобидных контрактов (синий) или пары вредоносных контрактов (красный) не имеет смысла. После того, как жертва принимает безобидный контракт, злоумышленник заменяет его на вредоносный и утверждает, что жертва подписала его, что доказывается цифровой подписью.
If the teacher had picked a specific day (say, 16 September), then the chance that at least one student was born on that specific day is , about 7.9%. In a birthday attack, the attacker prepares many different variants of benign and malicious contracts, each having a digital signature. A pair of benign and malicious contracts with the same signature is sought. In this fictional example, suppose that the digital signature of a string is the first byte of its SHA 256 hash. The pair found is indicated in green – note that finding a pair of benign contracts (blue) or a pair of malicious contracts (red) is useless. After the victim accepts the benign contract, the attacker substitutes it with the malicious one and claims the victim signed it, as proven by the digital signature.
Чувствительность цифровой подписи
Цифровые подписи могут быть уязвимы к атаке «день рождения» или, точнее, к атаке на коллизии с выбранным префиксом. Сообщение обычно подписывается путем вычисления , где – криптографическая хеш-функция, а затем с использованием некоторого секретного ключа для подписи. Предположим, Малли хочет обмануть Боба, заставив его подписать мошеннический контракт. Малли подготавливает честный контракт и мошеннический, а затем находит ряд позиций, которые можно изменить, не меняя смысла, например, вставку запятых, пустых строк, одного или двух пробелов после предложения, замену синонимов и т. д. Комбинируя эти изменения, она может создать огромное количество вариаций честного контракта. Аналогичным образом, Малли также создает огромное количество вариаций мошеннического контракта. Затем она применяет хеш-функцию ко всем этим вариациям, пока не найдет версию честного контракта и версию мошеннического контракта, которые имеют одинаковое хеш-значение. Она представляет честную версию Бобу для подписания. После того, как Боб подписал, Малли берет подпись и прикрепляет ее к мошенническому контракту. Эта подпись затем «доказывает», что Боб подписал мошеннический контракт. Вероятности немного отличаются от исходной задачи о дне рождения, поскольку Малли не получит выгоды от нахождения двух честных или двух мошеннических контрактов с одинаковым хешем. Стратегия Малли состоит в генерации пар, состоящих из одного честного и одного мошеннического контракта. Для заданной хеш-функции – это количество возможных хешей. Уравнения задачи о дне рождения здесь не применимы в полной мере, количество хешей, которые Малли фактически генерирует для вероятности , вдвое больше, чем требуется для простой коллизии, что соответствует .
Чтобы избежать этой атаки, выходную длину хеш-функции, используемой в схеме подписи, можно выбрать достаточно большой, чтобы атака «день рождения» стала вычислительно невозможной, то есть примерно вдвое больше битов, чем необходимо для предотвращения обычной атаки полным перебором. Помимо использования большей длины битов, подписывающий (Боб) может защитить себя, внося некоторые случайные, незначительные изменения в документ перед подписанием, и сохраняя копию подписанного контракта у себя, чтобы он мог хотя бы продемонстрировать в суде, что его подпись соответствует именно этому контракту, а не только мошенническому. Алгоритм Полларда ρ для логарифмов является примером алгоритма, использующего атаку «день рождения» для вычисления дискретных логарифмов.
To avoid this attack, the output length of the hash function used for a signature scheme can be chosen large enough so that the birthday attack becomes computationally infeasible, i. e. about twice as many bits as are needed to prevent an ordinary brute force attack. Besides using a larger bit length, the signer (Bob) can protect himself by making some random, inoffensive changes to the document before signing it, and by keeping a copy of the contract he signed in his own possession, so that he can at least demonstrate in court that his signature matches that contract, not just the fraudulent one. Pollard's rho algorithm for logarithms is an example for an algorithm using a birthday attack for the computation of discrete logarithms.
Обратная атака
То же самое мошенничество возможно, если подписывающимся является Мэллори, а не Боб. Боб может предложить Мэллори контракт для подписи. Мэллори может найти как незначительно измененную версию этого честного контракта, имеющую ту же подпись, что и мошеннический контракт, и предоставить эту измененную честную версию контракта и подпись Бобу. Позже Мэллори может предъявить мошенническую копию. Если у Боба нет незначительно измененной версии контракта (возможно, он обнаружил только свое первоначальное предложение), мошенничество Мэллори будет безупречным. Если же у Боба она есть, Мэллори сможет, по крайней мере, заявить, что мошенник – Боб.