Неотслеживаемая электронная почта, обратные адреса и цифровые псевдонимы

Перевод статьи Дэвида Чаума (David Chaum): Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms

От переводчика: Первая статья о mix-сетях — ныне уже довольно очевидной технологии — описывает луковую маршрутизацию и идеи, близкие к garlic-подходу. Статья стала отправной точкой для последующих систем анонимной связи. Автор исходно предполагает, что способы защиты содержимого сообщений (в основном — криптография с открытым ключом) уже существуют; встает другой вопрос — как скрыть сам факт обмена сообщениями и кто с кем общается. Решение — пропускать сообщение через цепочку серверов (mix-ов), которые не знают ни исходного отправителя, ни финального получателя: каждый узел знает только предшествующий и последующий хоп. Если сообщение предназначено узлу, он обрабатывает его и добавляет на выход пустышку (padding), чтобы нельзя было сопоставить входы и выходы.

Естественной проблемой такого подхода являются задержки. Одно дело — когда нужно передать лишь e-mail, и совсем другое — когда таким методом маршрутизируется весь пользовательский трафик, особенно в условиях постоянного роста объемов потребляемой информации. Кроме того, нельзя исключать “обычных” пользователей с ограниченными возможностями по обработке и передаче трафика, потому что эффективность метода опирается на большое число независимых mix-серверов. Чем меньше mix-серверов и чем ниже их независимость, тем выше риск корреляционного или сговорного анализа: если в цепочке окажется большинство скомпрометированных узлов, анонимность будет нарушена.

Аннотация

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

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

Введение

Криптология — это наука о секретной коммуникации. Методы криптографии обеспечивают секретность содержания сообщений на протяжении тысячелетий [3]. Недавно были предложены [2,4] несколько новых решений проблемы распределения ключей (то есть задачи предоставления каждому участнику секретного ключа), получившие название “криптография с открытым ключом”. Другая криптографическая задача — проблема анализа трафика (задача сохранения в тайне того, кто с кем и когда общается) — будет приобретать всё большее значение по мере роста использования электронной почты. В этой статье предлагается решение проблемы анализа трафика, основанное на криптографии с открытым ключом. Баран предложил решение задачи анализа трафика для сетей [1], но оно требует, чтобы каждый участник доверял одному и тому же доверенному органу. В отличие от этого, системы, основанные на предлагаемом здесь решении, могут быть скомпрометированы только в случае заговора всех доверенных ораганов. В идеале каждый участник сам является таким ораганом доверия. В следующих двух разделах вводятся обозначения и допущения. Затем основные концепции рассматриваются на ряде частных случаев, включающих цепочку из одного или нескольких доверенных органов. В заключительном разделе рассматриваются сети электронной почты общего назначения.

Обозначения

Чтобы стать пользователем криптосистемы с открытым ключом (например, системы RSA [5]), необходимо сгенерировать пару ключей K и Inv(K) на основе случайно сгенерированного начального значения. Открытый ключ K становится известен другим пользователям или любому, кто пожелает его узнать; закрытый ключ Inv(K) никогда не раскрывается. Шифрование X ключом K обозначается как K(X), где K(X) есть результат преобразования X криптографическим алгоритмом, использующим ключ K. Повышенная практическая ценность этих алгоритмов по сравнению с традиционными алгоритмами обусловлена тем, что два ключа являются взаимно обратными, в том смысле, что: 

Inv(K)(K(X)) = K(Inv(K)(X)) = X.

Сообщение X зашифровывается открытым ключом K так, что только владелец закрытого ключа Inv(K) может узнать его содержание. Если X просто зашифровать ключом K, то любой сможет проверить догадку о том, что Y = X, проверив, выполняется ли равенство K(Y) = K(X). Эта угроза может быть устранена, если перед шифрованием добавить к X длинную последовательность случайных битов R. Шифрование X ключом K обозначается как K(R, X). Пользователь подписывает некоторые данные X, добавляя к ним большую константу C (например, все нули) и затем шифруя их своим закрытым ключом; это обозначается как Inv(K)(C, X) = Y. Любой может убедиться, что сообщение Y было подписано владельцем закрытого ключа Inv(K), и определить подписанные данные X, вычислив K(Y) = C, X и проверив наличие C.

Допущения

Метод, рассматриваемый здесь, основывается на двух важных допущениях: (1) Никто не в состоянии установить какие-либо соответствия между набором зашифрованных сообщений и соответствующим набором незашифрованных сообщений, а также никто не сможет создать подделки без последовательности случайных битов R или без закрытого ключа. (2) Любой может узнать источник, получателя и внешнее представление всех сообщений в базовой телекоммуникационной системе, и любой может внедрять, удалять или изменять сообщения.

Система электронной почты

Пользователями криптосистемы будут не только участники переписки, но и специальный компьютер, называемый mix-сервером, который обрабатывает каждое письмо перед его доставкой. Участник готовит сообщение M для отправки по адресу A следующим образом: сначала шифрует его открытым ключом Ka получателя, затем добавляет адрес A и, наконец, шифрует результат открытым ключом mix-сервера K1. Левая часть следующего выражения обозначает это сообщение, поступающее mix-серверу: 

K1( R1, Ka( R0, M ), A ) --> Ka( R0, M ), A.

Обозначение --> показывает преобразование входных данных mix-сервера в выходные, представленные справа. mix-сервер расшифровывает входное сообщение своим закрытым ключом, отбрасывает R1 и выдаёт оставшуюся часть. Можно представить себе механизм, который пересылает зашифрованные сообщения Ka(R0, M), полученные на выходе, адресатам, и те затем расшифровывают их своими закрытыми ключами.

Назначение mix-сервера — скрыть соответствие между входом и выходом. Чтобы скрыть порядок поступления сообщений, на выход выдаются сообщения одинакового размера, сгруппированные в лексикографически упорядоченные пакеты. Согласно допущению (1), нет причин опасаться атаки, которая выявит соответствие между зашифрованными сообщениями на входе и их расшифрованными выходами — если сообщения не повторяются. Однако если хотя бы одно сообщение повторится на входе и будет допущено к повторению на выходе, то для этого сообщения соответствие раскроется.

Таким образом, важной функцией mix-сервера является обеспечение того, чтобы ни одно сообщение не было обработано более одного раза. Для одного пакета достаточно удалить дубликаты перед выходом. Если пакетов будет несколько, то дубликаты между пакетами можно выявлять, ведя учёт всех обработанных сообщений. Такие записи можно удалить, как только mix-сервер поменяет свой открытый ключ, например, объявив новый ключ в сообщении, подписанном своим старым закрытым ключом. Смысл учета отпадает, если R1 содержит нечто — например, временную метку, — что действительно только для конкретного пакета.

Если участник, отправляющий сообщения mix-серверу, получает от него подтверждение получения, то он может предоставить веские доказательства того, что mix-сервер не выдал сообщение на выход. Только пострадавший участник может предъявить Y (= Inv(K1)( C, K1( R1, Ka( R0, M ), A ))), пропавшее сообщение X (= Ka( R0, M ), A ) и сохранённую строку R1 так, что выполняется равенство K1( Y ) = C, K1( R1, X ). Поскольку mix-сервер подписывает каждый пакет целиком, отсутствие X в пакете может быть доказано с помощью копии этого подписанного пакета.

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

Kn( Rn, K<n-1>( R<n-1>, ... , K2( R2, K1( R1, Ka( R0, M ), A ))...)) -->.

Первый mix-сервер формирует лексикографически упорядоченные пакеты из сообщений. Каждое сообщение имеет вид:

K<n-1>( R<n-1>, ... , K2( R2, K1( R1, Ka( R0, M ), A ))...) -->

Сообщения в последнем пакете цепочки имеют вид Ka(R0, M), A, такой же, как в случае одного mix-сервера.

Обратные адреса

Описанные выше техники позволяют участнику x отправлять анонимные сообщения участнику y. Теперь нужен механизм, позволяющий y отвечать x, не раскрывая при этом личность x. Решение состоит в том, что x формирует неотслеживаемый обратный адрес:

K1( R1, Ax), Kx

где Ax — это настоящий адрес x, Kx — открытый ключ. После этого x может отправить этот обратный адрес y как часть сообщения, сформированного с помощью описанных ранее техник. Два участника могут обменяться такими обратными адресами через цепочку других участников, где хотя бы один участник каждой соседней пары знает личность другого. Следующее выражение показывает, как y может использовать неотслеживаемый обратный адрес, чтобы сформировать ответ x, применяя новый тип mix-сервера: 

K1( R1, Ax ), Kx( R0, M ) --> Ax, R1( Kx( R0, M )).

Этот mix-сервер использует R1, полученный после расшифрования K1(R1, Ax), в качестве ключа для повторного шифрования Kx(R0, M). Только x может расшифровать результат, так как именно он создал и R1, и Kx. mix-сервер не должен допускать повторного использования адреса — по той же причине, по которой недопустимо повторение сообщений. Это означает, что x обязан предоставлять y обратный адрес для каждого сообщения, на которое он хочет получить ответ. Так же, для всех этапов шифрования M можно использовать симметричную криптографию, а не криптографию с открытым ключом.

Для цепочек mix-серверов сообщения обрабатываются так же как и для одного mix-сервера, а адресная часть имеет вид, показанный во входных данных ниже:

K1( R1, K2( R2, ..., K<n-1>( R<n-1>, Kn( Rn, Ax ))...)), Kx( R0, M ) -->

Результат первого mix-сервера в цепочке:

K2( R2, ..., K<n-1>( R<n-1>, Kn( Rn, Ax ))...), R1( Kx( R0, M )) -->

и последний результат оставшихся n-1 mix-серверов:

Ax, Rn( R<n-1> ... R2( R1( Kx( R0, M )))...)

Неотслеживаемые обратные адреса позволяют реализовать подтверждение доставки: они могут предоставить отправителю анонимного письма подтвеждение, что письмо в неизменном виде доставлено получателю. Адрес A, встроенный в такое письмо, расширяется: он включает не только адрес получателя, но и неотслеживаемый обратный адрес отправителя. Когда письмо доходит до получателя, обратный адрес используется для отправки отправителю подписанного подтверждения, которое включает само сообщение и адрес, на который оно было доставлено. Это подтверждение может быть подписано каждым mix-сервером в цепочке.

Цифровые псевдонимы

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

Каждая заявка, поступающая в доверенный центр, содержит всю необходимую информацию для принятия решения, а также специальное безадресное цифровое письмо, содержащее открытый ключ K — предлагаемый псевдоним заявителя. В случае одного mix-сервера такое письмо имеет вид K1(R1, K). Для цепочки из n mix-серверов оно имеет вид Kn(Rn, ..., K2(R2, K1(R1, K))...). Доверенный центр формирует входной пакет, включающий только безадресные письма из заявок, которые он принял. Этот пакет передаётся в специальную цепочку mix-серверов, последний выходной пакет которой становится публично доступным. Так как каждая запись в последнем выходном пакете цепочки — это открытый ключ K из принятой заявки, то подписанный выход последнего mix-сервера представляет собой реестр цифровых псевдонимов.

Оповещение заявителей можно осуществить, сформировав также список непринятых заявок и затем, с помощью техники подтверждённой доставки, вернуть единый пакет подтверждений для обеих групп заявителей (принятых и непринятых). Разумеется, повторения не должны допускаться ни внутри одного пакета, ни между пакетами.

Если для определённого реестра допускаются только зарегистрированные избиратели, то его можно использовать для проведения выборов. Для одного mix-сервера каждый избиратель отправляет бюллетень вида K1( R1, K, Inv(K)( C, V )), где K — псевдоним избирателя, а V — его голос. Для цепочки из n mix-серверов бюллетень имеет вид Kn( Rn, …, K2( R2, K1( R1, K, Inv(K)( C, V )))…). Все бюллетени должны быть обработаны как единый пакет, так же, как ранее формировались письма для создания реестров. Элементы последнего упорядоченного по лексикографическому порядку выходного пакета имеют вид K, Inv(K)( C, V ). Поскольку реестр зарегистрированных избирателей также отсортирован по K, то любой может подсчитать голоса, сделав один проход по обоим спискам одновременно. Каждый бюллетень засчитывается только после проверки, что псевдоним K, который стоит в его начале, содержится в реестре, и что подпись действительно корректно расшифровывается этим K.

Клиент может быть известен организации только по псевдониму, который присутствует в реестре допустимых клиентов. Клиенты могут общаться с организацией через неотслеживаемую почту, а организация может отвечать клиентам с помощью неотслеживаемых обратных адресов. Если заявители указывают свою личность в заявках или подписывают их псевдонимами, включёнными в реестр, то организация получает уверенность, что один и тот же клиент не сможет обращаться под разными псевдонимами. В особых случаях — например, при неуплате — можно показать, что конкретный псевдоним соответствует определённой заявке (не раскрывая другие соответствия), если каждый mix-сервер предоставит своё число Rn.

Системы электронной почты общего назначения

Один из способов построить неотслеживаемую почтовую систему — требовать, чтобы каждое сообщение проходило через цепочку mix-серверов. Разумеется, mix-сервера могут работать непрерывно или периодически; длинные сообщения предварительно шифруются, а затем разбиваются на несколько сообщений. Чтобы скрыть число отправленных сообщений, каждый участник формирует пакеты с одинаковым количеством сообщений (часть которых может быть фиктивными сообщениями, случайно адресованными). Чтобы скрыть число полученных сообщений, каждый участник приватно просматривает весь выходной пакет в поиске сообщений, адресованных ему.

Такая система может оказаться слишком дорогостоящей для некоторых участников. Один из способов сократить затраты — позволить адресовать почту подмножествам участников, например локальной сети. Участникам, использующим такие схемы, требуется просматривать лишь те сообщения, которые адресованы соответствующей подсети. Другой способ экономии — отправлять в каждом пакете случайное количество фиктивных сообщений, вместо того чтобы всегда посылать максимальное число сообщений. Это может существенно сократить объём трафика и, соответственно, размер выходных пакетов. Хотя такие приёмы могут открыть путь для некоторых видов статистического анализа, тот размер системы, который вынудил их применять, может снизить эффективность таких атак.

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

Здесь представлен новый тип mix-сервера, который позволяет для каждого сообщения выбирать последовательность серверов. Он также: (a) скрывает количество и идентичность mix-серверов, через которые проходит сообщение; (b) позволяет выявить mix-сервер, который некорректно перенаправляет сообщения; (c) не делает различий между обычным сообщением и сообщением, отправленным с использованием неотслеживаемого обратного адреса. В основе лежит идея о том, что каждое сообщение состоит из одинакового количества блоков фиксированного размера.

Операции этого mix-сервера всегда выполняются одинаково. Сначала он удаляет первый блок и добавляет случайный фиктивный блок J в конец, чтобы сохранить длину сообщения равной l блокам. Затем, используя свой закрытый ключ, расшифровывает блок, удалённый на первом шаге. В результате он получает ключ R, которым шифрует каждый из l блоков сообщения (с использованием либо криптографии с открытым ключом, либо симметричной). Кроме того, он извлекает адрес A (либо получателя, либо другого mix-сервера), которому сообщение будет переслано.

В левой части следующего выражения показано, как подготавливается сообщение для прохождения через один mix-сервер:

A1: [K<A1>( R<A1>, A )], [Inv(R<A1>)( M1 )], [Inv(R<A1>)( M2 )], ...
    [Inv(R<A1>)( M<l-1> )] --> A: [M1],...[M<l-1], [R<A1>( J<A1> )].

Квадратные скобки показывают границы каждого блока, а зашифрованное сообщение Ka( R0, M ) разбивается на части Mi, так что Ka( R0, M ) = M1, M2, ..., M<l-n>. Обозначение A1 указывает, что левая часть выражения доставляется на mix-сервер A1, тогда как A означает, что правая часть доставляется по адресу A. Сообщения с одинаковым первым блоком следует рассматривать как повторы.

Сообщение, которое должно пройти через миксы A1 ... An, имеет следующий вид:

A1: [K<A1>( R<A1>, A2 )], [Inv(R<A1>)( K<A2>( R<A2>, A3 ))], ...,
    [Inv(R<A1>)( Inv(R<A2>) ... Inv(R<A<n-1>>)( K<An>( R<An, A )) ... )],
    [Inv(R<A1>)( Inv(R<A2>) ... Inv(R<An>)( M1 )...)], ...,
    [Inv(R<A1>)( Inv(R<A2>) ... Inv(R<An>)( M<l-n> )...)] -->.

Результат после прохождения через A1:

A2: [K<A2>( R<A2, A3 )], [Inv(R<A2>)( K<A3>( R<A3>, A4 ))], ...,
    [Inv(R<A2>)( Inv(R<A3>) ... Inv(R<A<n-1>>)( K<An>( R<An, A )) ... )],
    [Inv(R<A2>)( Inv(R<A3>) ... Inv(R<An>)( M1 )...)], ...,
    [Inv(R<A2>)( Inv(R<A3>) ... Inv(R<An>)( M<l-n> )...)],
    [R<A1>( J<A1> )] -->,

и конечный результит после прохождения An:

A: [M1], [M2], ..., [M<l-n>],
   [R<An>( R<A<n-1>> ... R<A1>( J<A1> )...)], ..., [R<An>( J<An> )].

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

Неотслеживаемый обратный адрес, который x отправляет y, содержит ключ Kx, который y использует для шифрования части сообщения. В случае одного mix-сервера он также включает блок, который y будет использовать в качестве первого блока сообщения, отправляемого mix-серверу: 

A1: [K<A1>( R<A1>, Ax )], [M1], ..., [M<l-1>] -->
Ax: [R<A1>( M1 )], ..., [R<A1>( M<l-1> )], [R<A1>( J<A1> )],

где Kx( R0, M ) = M1, M2, …, M<l–n>. Только x может расшифровать полученное сообщение, так как именно он создал R<A1> и Kx. Когда сообщение должно пройти через n mix-серверов, неотслеживаемый обратный адрес содержит первые n блоков: 

A1: [K<A1>( R<A1>, A2 )], [Inv(R<A1>)( K<A2>( R<A2>, A3 ))], ...,
    [Inv(R<A1>)( Inv(R<A2>) ... Inv(R<A<n-1>>)( K<An>( R<An>, Ax ))...)],
    [M1], [M2], ..., [M<l-n>] -->.

После обработки mix-сервером A1 примет следующий вид:

A2: [K<A2>( R<A2>, A3 )], ...,
    [Inv(R<A2>)( Inv(R<A3>) ... Inv(R<A<n-1>>)( K<An>( R<An>, Ax ))...)],
    [R<A1>( M1 )], [R<A1>( M2 )], ..., [R<A1>( M<l-n> )],
    [R<A1>( J<A1> )] -->,

и конечный результат после обработки An:

Ax: [R<An>( R<A<n-1>> ... R<A1>( M1 )...)], ...,
    [R<An>( R<A<n-1>> ... R<A1>( M<l-n> )...)],
    [R<An>( R<A<n-1>> ... R<A1>( J<A1> )...)], ..., [R<An>( J<An> )].

Заключение

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

Список литературы

  1. Baran, P. On distributed communications: IX security secrecy and tamper-free considerations. Memo RM-3765-PR, Rand Corp., Santa Monica, CA, Aug. 1964.
  2. Diffie, W. and Hellman, M.E. New directions in cryptography. IEEE Trans. Information Theory IT-22, 6 (Nov. 1976), 644-654.
  3. Kahn, D. The Code Breakers, The Story of Secret Writing. Macmillan, New York, 1967.
  4. Merkle, R.C. Secure communications over insecure channels. Comm. ACM 21, 4 (Apr. 1978), 294-299.
  5. Rivest, R.L., Shamir, A., and Adleman, L. A method for obtaining digital signatures and public-key cryptosystems. Comm. ACM 21, 2 (Feb. 1977), 120-126.