Что я упускаю в своих рассуждениях?
Две вещи:
Существуют и другие стратегии поиска столкновений, кроме сортировки; один из очевидных — построить огромную хеш-таблицу. Теперь на практике сортировка, вероятно, пойдет быстрее (поскольку такая огромная хеш-таблица будет непрактичной), но теоретически хеш-таблица позволит $O(1)$ доступа, которые этот анализ сложности неявно предполагает.
$O(n\logn)$ на самом деле не оптимальное время сортировки. Это если единственными операциями, которые вы можете выполнять с данными, являются сравнения и перемещение данных; однако на самом деле мы не ограничены таким образом. Одним из очевидных подходов было бы использование метода сортировки по основанию, который может иметь значительно лучшую временную сложность.
Теперь, если честно, мы обычно игнорируем время, затрачиваемое на эти некриптографические операции (такие как поиск и сортировка), если только они не занимают действительно большую часть общего времени. Откровенно говоря, когда вы спускаетесь на этот уровень, может быть много деталей (например, сложность работы с $О(2^{56})$ данные), и вместо этого мы просто считаем оценки DES.
На самом деле мы не пытаемся взломать 2DES; вместо этого мы показываем, что взлом 2DES действительно может быть достижим на практике. Если бы мы на самом деле пытались сломать его, мы могли бы вместо этого использовать лямбда-поиск, который имел бы постоянное увеличение сложности и не гарантируется, было бы легче реализовать (поскольку лямбда-поиск будет использовать гораздо меньше памяти и все еще легко распараллелить).
