Если множество ключей криптоалгоритма замкнуто относительно композиции, то есть для любых ключей z i и z j найдется ключ zk такой,что результат шифрования любого текста последовательно на z i и z j равен шифрограмме этого же числа на zk , то есть F(z j ,F(z i , x))= F(z k , x), то можно воспользоваться этим свойством. Пусть нам нужно найти ключ zk. Тогда для нахождения ключа zk, необходимо найти эквивалентную ему пару ключей zi , zj. Данный метод криптоанализа основан на "парадоксе дней рождения". Известно, что если считать, что дни рождения распределены равномерно, то в группе из 24 человек с вероятностью 0,5 у двух человек дни рождения совпадут.В общем виде этот парадокс формулируется так: если a Ц n предметов выбираются с возвращением из некоторой совокупности размером n, то вероятность того что два из них совпадут, равна 1-exp(-a2 / 2)

Пусть известен открытый текст x и его шифрограмма y. Для текста x строим базу данных, содержащую случайное множество ключей z| и соответствующих шифрограмм w=F(z| , x), и упорядочиваем ее по шифрограммам w. Объем базы данных выбираем О( Ц # {z} ). Затем подбираем случайным образом ключи z| | для расшифровки текстов y и результат расшифровани v = F(z| | , y) сравниваем с базой данных. Если текст v окажется равным одной из шифрограмм w, то ключ z| z| | эквивалентен искомому ключу z. Временная сложность метода составляет О( Ц # {z} log#{z}). Множитель log#{z} учитывает сложность сортировки. Требуемая память равна О( Ц # {z} log#{z}) бит или ОЦ # {z}) блоков ( предполагается, что длина блока и длина ключа различаются на ограниченную константу ).

Этот же метод применим, если множество ключей содержит достаточно большое подмножество, являющееся полугруппой.

Другое применение этого метода для множества, не являющегося полугруппой, можно продемонстрировать на хэш-функциях. Например, для подделки подписи надо найти два текста, обладающих одним хэш-образом. После этого можно подписанное сообщение заменить на другое, обладающее таким же хэш-образом. Поиск двух таких сообщений можно выполнить с использованием метода "встречи посередине". Сложность поиска равна О(Ц #{h}), где #{h} - число всевозможных хэш-образов

Этот алгоритм является вероятностным. Однако существуют и детерминированный аналог этого алгоритма "giant step - baby step" с такой же сложностью, предложенный американским математиком Д.Шенксом