Золотой ключик

1757 дней спустя после начала работы, проект по взлому 64-битного ключа RC5 успешно завершен.

Не каждый день представляется возможность рассказать о проекте, рассчитанном на долгие годы работы и успешно завершившемся. Но сегодня - тот самый случай, когда такая возможность есть. Спустя 1757 дней после своего запуска или, говоря проще, почти пять лет спустя после начала, завершил работу проект RC5-64 (также известный под названием "Bovine" - "Бык"), целью которого был подбор 64-битного ключа к зашифрованной алгоритмом RC5 фразе - методом перебора всех возможных кодовых комбинаций (brute force). Нужная была определена руками, а точнее - машиной, жителя Японии - подробная информация о личности которого скрыта от публики по его собственному желанию, но сведения о компьютере дают хорошее представление об аппаратном обеспечении типичного участника проекта: это компьютер на основе P3 450 МГц, работающий под управлением Windows 2000. Ключик, скромно описываемый числом из 16-ти цифр (63DE7DC154F4D039), позволил расшифровать закрытое работниками компании RSA Labs сообщение "The unknown message is: some things are better left unread".

Участники RC5-64 работали не просто так: помимо энтузиазма, многих грела надежда на получение приза. Величина которого, впрочем, не так уж и велика: из 10 тысяч долларов, предоставленных RSA Labs и составивших призовой фонд, лишь тысяча должна была достаться самому победителю - человеку, компьютер которого подберёт нужную кодовую комбинацию. Ещё тысяча достанется той команде, в которую он входил, а шесть тысяч будут перечислены на счёт некоммерческой организации, которую выберут общим голосованием (что любопытно, чем больший объём информации обработал данный участник, тем более весом его голос). Две тысячи долларов получают учредители сайта Distributed.net, которые и организовали весь проект. И деньги им пригодятся - ибо новые вершины уже намечены. Впрочем, об этом чуть позже, пока же стоит вспомнить о разного рода мелочах, проявившихся в ходе поиска ключа.

Прежде всего, общее число кодовых комбинаций, которые можно было проверить в проекте RC5-64, превышало 18 квинтиллионов (2^64). Каждый день обрабатывалось в лучшем случае 0.12% от всего объёма задачи, поэтому комбинационное пространство, в идеале, могло быть полностью просмотрено за 790 дней. Однако, и за 1757 дней были перебраны лишь 85% всех ключей. Более чем двукратное превышение планового порога объясняется тем, что на ранних этапах проекта число участников было относительно невелико и работа шла значительно медленней. Кроме того, время от времени, возникали проблемы на координационных серверах Distributed.net, также сказавшиеся на общей длительности проекта. Впрочем, возникла и ещё одна задержка: на самом деле, ключ был подобран ещё 14-го июля, но из-за ошибки в серверном скрипте, анализировавшем сгенерированные комбинации, администраторам проекта стало известно об этом лишь 12-го августа. Следующий месяц ушёл на отсылку ключа в RSA Labs для подтверждения корректности находки.

Так или иначе, ключ найден, деньги получены и на очереди - новые свершения. А иначе не может и быть: основанный в 1997-м, RC5-64 объединил к своему завершению более 331 тыс. человек, достигнув мощности, эквивалентной 160 тыс. персоналок на PII 266 МГц. В ближайшие недели все эти силы будут брошены на решение очередной задачи: за плечами у RC5 - успешно подобранные 56- и 64-битные ключи, теперь предлагается 72-битный. Дать точную оценку времени, необходимого на решение этой задачи, никто не в состоянии, но примерно её представить можно по статистике прошедших этапов: RC-56 отнял 250 дней, в 256 раз более сложный RC5-64 - 1757 дней. В настоящее время программа-клиент для RC5-72 уже написана (модифицирован старый код), ведётся настройка серверного программного обеспечения.

Ну а какова же практическая польза от работы сотен тысяч компьютеров в течение многих лет? Благодаря тому, что возможность расшифровки фразы, закрытой 64-битным ключом RC5, продемонстрирована практически, использование этого криптографического алгоритма с таким ключом для сокрытия сведений, обещающих остаться актуальными несколько лет, уже не может считаться приемлемым. Кто бы мог подумать…