Интернет остался без криптографии. Прощайте, VPN и HTTPS!

Так, а как быть с 2048- и 4096-битными ключами?

К счастью (нашему, не АНБ) все упирается в соразмерность затрат и получаемой выгоды от прослушивания конкретного соединения. Приведу цитату комментария к топику на хабре, где обсуждалась эта тема:

К сожалению, для протокола Диффи — Хеллмана в поле вычетов по модулю (mod p) размером 512 (1024) бита возможно слишком много различных пар ключей (более чем порядка 2^500 и 2^1000 пар). Подобные объемы информации находятся далеко за физическими пределами хранения информации (Limits to computation) и за пределами вычислимости (Transcomputational problem — более 2^310 операций).

В частности, заметно более простая задача полного перебора 2^256 ключей (для симметричного 256-битного алгоритма, например, AES-256) потребовала бы по принципу Ландауэра (при необратимых вычислениях) потребления энергии, превышающей энерговыделение нескольких миллионов сверхновых: everything2.com/title/Thermodynamics+limits+on+cryptanalysis

...brute force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space". ---Bruce Schneier in Applied Cryptography
… Even sucking all the energy from a supernova would be just enough to pass through all states of a 219-bit counter… As long as computers are made of matter, 256-bit keys will be secure against brute-force. Except of course… if we break the second law of thermodynamics :-).

В обсуждаемой же работе imperfect-forward-secrecy-ccs15.pdf Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice
речь идет о намного более практичной атаке на проблему дискретного логарифирования (дано ключ y = g^a mod p; заранее известны g и p, получен y, найти a) с помощью лучших методов решета числового поля (number field sieve, GNFS). В данных методах требуется очень большой объем вычислений для каждого модуля p, но большая часть вычислений не зависит от конкретных ключей (см precomputation из Figure 1 статьи):

With state-of-the-art number field sieve algorithms, computing a single discrete log is more difficult (примерно в 10 раз сложнее) than factoring an RSA modulus of the same size. However, an adversary who performs a large precomputation for a prime p can then quickly calculate arbitrary discrete logs in that group, amortizing the cost over all targets that share this parameter. Although this fact is well known among mathematical cryptographers, it seems to have been lost among practitioners deploying cryptosystems.

Авторами статьи был проведен предварительный расчет для трех 512-битных простых модулей (в т.ч. два из набора DHE_EXPORT), на что потребовалось 7 дней: выбор и просеивание полиномов на 2-3 тысячах ядер Sandy Bridge (8+21 тыс ядро-часов; 3 + 15 часов, идеально распараллеливается) и решение линейной системы (60 тысяч ядро-часов; пять суток на кластере из 36 машин с 2x8-core E5-2650 + Infiniband FDR, с параллельностью уже хуже). Результатом расчета для каждого модуля стали 2.5 ГБ чисел.
Затем авторы продемонстрировали решение задачи логарифмирования для ключей в этих полях на машине с 2-мя 18-ядерными Intel Xeon E5-2699 и 128 ГБ ОЗУ, в среднем за 70 секунд на ключ (от 34 до 206 секунд).

Для 768- и 1024-битного модуля они оценивают время предварительных вычислений в 8 тысяч ядро-лет и 10 миллионов ядро-лет соответственно, а время логарифмирования отдельных ключей — в 2 и 30 суток. При этом линейная система будет уже не из 2 миллионов строк как для 512 бит, а уже из 150 миллионов для 768 бит и 5.2 миллиардов для 1024 бит. Столь большие системы еще не решали, и по самым грубым оценкам их решение может потребовать сотен лет работы крупнейших суперкомпьютеров США (Titan имеет 300 тыс ядер и стоил ~$100 млн).

Сам я ярый противник теории неуловимого Джо (когда подавляющее большинство пользователей считает себя абсолютно никому не интересными с точки зрения взлома), однако в данном случае, я сомневаюсь, что "ядро-годы" работы суперкомпьютеров, стоящих в датацентрах АНБ будут тратиться (по крайней мере в ближайшем обозримом будущем) для прослушивания защищенных соединений, впрямую не связанных с нацбезопасностью США.
В этом смысле мы можем продолжать считать наши SSH-и и VPN-ы неуязвимыми.

Сильнейшие криптоаналитики мира только сейчас узнали про Rainbow Table, с помощью которых хэши пытались подбирать как бы не в 90е ещё? Обнять и плакать.