32-битные Short-ID окончательно дискредитированы

free@turing ~$ gpg --keyserver pgp.mit.edu --recv-keys 10000001

gpg: requesting key 10000001 from hkp server pgp.mit.edu
gpg: key 10000001: public key "Linus Torvalds" imported
gpg: key 10000001: public key "Linus Torvalds" imported
gpg: Total number processed: 2
gpg:            imported: 2  (RSA: 2)

Давно известно, что PGP уязвим к атакам на короткий идентификатор (short-ID). Относительно несложно сгенерировать пару совместимых с GnuPG 4096-битных RSA-ключей с заранее заданным коротким (32-битным) идентификатором short-ID, именем владельца и адресом электронной почты. Процедура поиска коллизии занимает буквально 10-20 минут на обычном компьютере, что демонстрировалось неоднократно. На современном GPU она занимает 4 секунды при использовании программы Scallion.

Раньше атака рассматривалась чисто теоретически, но с начиная с июня 2016 года разработчики начали сообщать о реальных случаях подделки их коротких идентификаторов — фальшивые ключи размещались на серверах криптографических ключей. А сейчас дело дошло до Линуса Торвальдса и ведущих разработчиков ядра Linux.

Среди пострадавших — Линус Торвальдс, Грег Кроа-Хартман (Greg Kroah-Hartman) и другие известные разработчики.

Поисковый результат для 0x00411886: https://pgp.mit.edu/pks/lookup?search=0x00411886&op=index
Фальшивый Линус Торвальдс: 0F6A 1465 32D8 69AE E438 F74B 6211 AA3B [0041 1886]
Настоящий Линус Торвальдс: ABAF 11C6 5A29 70B1 30AB E3C4 79BE 3E43 [0041 1886]

Поисковый результат для 0x6092693E: pgp.mit.edu/pks/lookup?search=0x6092693E&op=index
Фальшивый Грег Кроа-Хартман: 497C 48CE 16B9 26E9 3F49 6301 2736 5DEA [6092 693E]
Настоящий Грег Кроа-Хартман: 647F 2865 4894 E3BD 4571 99BE 38DB BDC8 [6092 693E]

В первом случае совпадает короткий идентификатор 0041 1886, имя и адрес электронной почты (Linus Torvalds <torvalds@linux-foundation.org>).

Во втором случае совпадает короткий идентификатор 6092 693E (Greg Kroah-Hartman (Linux kernel stable release signing key) <greg@kroah.com>).

Теоретически, коллизию можно найти не только для 32-битного, но даже для 64-битного короткого идентификатора. Пусть не за несколько секунд, а за несколько дней или недель на обычном GPU. Хотя, на кластере ASIC это будет на порядок быстрее. Скажем, современные биткоин-майнеры ASIC работают с хешрейтом 14 терахешей в секунду. А если задаться такой целью и задействовать кластер?

Есть мнение, что все поддельные ключи попали на сервер криптографических ключей из базы Evil 32. Там уже давно накапливается база клонированных ключей (примерно 24 тыс.). Видимо, недавно какой-то шутник решил залить их на публичный сервер криптографических ключей.

Даже если ребята с Evil 32 удалят свою базу поддельных ключей, кто угодно может повторить атаку.

Вывод очевиден: лучше вообще прекратить использовать Short-ID, нигде их не указывать, а использовать только полные отпечатки открытого ключа. Тем более последняя версия GPG 2.1 уже показывает полные отпечатки по умолчанию.