самом крайнем случае в разных системах предусмотрительные пользователи должны использовать различные пароли.

Рассмотренная выше угроза может быть легко предотвращена на практике [167, 291, 358, 272, и т.д.]. Ключевая мысль заключается в том, что компьютеру в такой ситуации совершенно не обязательно знать действительные пароли пользователей - для него необходима лишь способность подтверждения данных паролей. Это может быть реализовано посредством использования однонаправленных функций. Компьютеру достаточно хранить лишь образы пользовательских паролей, являющиеся результатами вычисления некоторой фиксированной однонаправленной функции от каждого пароля как аргумента. Поскольку функция однонаправленна, то хранить в секрете ее саму совершенно не обязательно. Тогда всякий раз, как только какой-нибудь пользователь захочет доказать свою подлинность, он сообщает свой истинный пароль, а компьютер сразу же вычисляет от него значение этой однонаправленной функции. Затем результат вычислений сверяется с хранящейся в компьютере таблицей. Очевидно, что в данном случае противник в силу своей неспособности вычислять прообразы значений соответствующей однонаправленной функции будет вынужден признать бесполезным для определения истинных паролей пользователей распечатку такой преобразованной таблицы.

Эта схема может оказаться довольно слабой, если пользователи склонны употреблять пароли, которые можно легко угадать. В такой ситуации с помощью кого-то, кто имеет доступ к таблице (преобразованных) паролей и к алгоритму вычисления однонаправленной функции, может, зачастую довольно успешно, применяться следующая атака. Задавшись, скажем, тысячью предположительно наиболее употребимых паролей и вычислив значения однонаправленной функции от них, этот «кто-то» может затем эффективно сравнить полученные результаты с преобразованной таблицей паролей (используя при этом технику хеширования или сортировки). Тогда каждое такое успешное сравнение предоставит ему в распоряжение некоторый истинный пользовав тельский пароль. Ясно, что подобная атака не позволяет нарушителю раскрыть все пароли, которые он хотел бы узнать, но тем не менее она очень продуктивна в нахождении некоторых из них[176].

Хотя и не делая ничего дополнительного для защиты индиви-дугильных паролей, тк называемая случайная добавка является той техникой, которая почти исключает описанные выше коллективные угрозы. При формировании таблицы паролей с каждым именем пользователя связывается некоторая случайным образом сгенерированная битовая строка (в открытом виде), а хранящееся значение однонаправленной функции вычисляется от конкатенции истинного пароля каждого пользователя и этой его случайной строки. В результате оказывается, что два различных пользователя, которые могли бы случайно выбрать одинаковые пароли, будут иметь разные записи в преобразованной системной таблице.

Несмотря на такое улучшение, остается одна основная сла-бост!. Всякий раз, когда пользователь захочет, чтобы была подтверждена его подлинность, он должен вводить свой настоящий пароль в компьютер. Пароль в этом случае становится уязвимым к перехвату либо тогда, когда он проходит по линии связи к компьютеру, либо внутри самого компьютера вплоть до того момента, пока он не будет преобразован посредством вычисления соответствующей однонаправленной функции.

Для того чтобы избавиться от подобной угрозы, необходимо, чтобы компьютер не только не имел паролей в памяти, но и вообще не выдавал бы их ни при каких обстоятельствах. Это требование кажется парадоксальным. Тем не менее оно может быть удовлетворено посредством комбинации одной идеи времен второй мировой войны - системы идентификации типа «друг-или-враг» (I.F.F.) [228] - с понятием однонаправленной функции с потайным ходом. Для этого требуется, чтобы пользователи имели в распоряжении свои собственные интеллектуальные терминалы или, что предпочтительнее, персональные smart-карточки [264, 116, 209].

Для того чтобы решить проблему идентификации пользователей какой-нибудь системы, каждый ее пользователь вырабатывает случайным образом личный (секретный) ключ в соответствии с некоторой криптосхемой с открытым ключом. Этот ключ он использует для конкретизации собственной согласованной пары алгоритмов: шифрования и дешифрования. Затем алгоритм шифрования-он предоставляет в распоряжение центрального компьютера системы, а на своем терминале программирует алгорттм

дешифровалия. Всякий раз, когда нужно убедиться в подлинности (того, кто, быть может, только действует от имени легального) пользователя системы, центральный компьютер вырабатывает случайное сообщение, вычисляет от него, как от аргумента, значение функции шифрования этого пользователя, и посылает результат на его терминал в качестве опроса. Пользователь в ответ на опрос запускает свою хранящуюся в секрете от всех программу дешифрования и вычисляет само исходное (случайное) сообщение, которое в качестве удостоверения пересылает назад в компьютер. Как следует непосредственно из определения однонаправленных функций с потайным ходом, только законный пользователь способен пройти подобные опросы эффективно, даже если его функция шифрования (программа которой хранится внутри центрального компьютера) известна нарушителю. Как и было объявлено ранее, при таком механизме работы системы по типу «опрос-ответ» личный пароль пользователя, который фактически является его эффективным алгоритмом дешифрования, никогда не пересылается в центральный компьютер.

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

С другой стороны, истинный пользователь системы, очевидно, не должен доверять компьютеру в том, что запросы и в самом деле формируются случайным образом. Из этого следует, что криптографическая схема, на которой основывается предлагаемый выше механизм работы системы, должна быть стойкой против атак на основе выбранного шифртекста (см. § 4.3). Поэтому здесь нельзя использовать криптосхему вероятностного шифрования Блюма-Гольдвассер (см. § 4.6).

В действительности для того чтобы получить ргьботоспособ-ную систему идентификахщи пользователей, нужно принять во внимание все нюансы теории однонаправленных функций с потайным ходом. Предположим, например, что в некоторой кри-птрсхеме любое достаточно короткое сообщение, если иметь в