Обратите внимание, что новости можно получать по RSS.
X
-

Информационные технологии, Infused Bytes - архив

9 ноября 1998, 00:00 (6956 дней назад, №6046)Задачи решаемые криптографическими методами
(Андрей Винокуров, 9/Нбр/98)

< К оглавлению

 

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

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

2. Теперь поговорим о том, что есть нормальное протекание процесса информационного взаимодействия, и о возможных отклонениях от него. Очевидно, что никакого объективного критерия нормы не может существовать, здесь норма - это просто соответствие процесса параметрам его протекания, запланированным тем субъектом или субъектами, которые пытаются выполнить стоящие перед ними задачи посредством этого самого информационного процесса. Соответственно, любое событие, выводящее процесс за рамки предусмотренной для него нормы считается отклонением. Криптография есть дисциплина, которая рассматривает способы борьбы с отклонениями, вызванными целенаправленными действиями злоумышленников. Так как в ней постулируется, что последние действуют наилучшим возможным с точки зрения достижения своих целей образом в рамках имеющихся в их распоряжении данных и имеют все необходимые ресурсы, любое случайное воздействие на информационный процесс не способно отклонить его протекание от нормы больше, чем это сделал бы злоумышленник. Следовательно, криптографические методы годятся для защиты информационных взаимодействий и от случайных отклоняющих факторов, хотя последнее не является их основным назначением.

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

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

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

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

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

2. В соответствии с некоторым регламентом (например, при каждой загрузке системы, или один раз в определенный промежуток времени, или перед запуском программы на выполнение) проверяется соответствие защищаемой единицы контрольному коду.

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

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

Задачи, решаемые криптографическими методами, отличаются друг от друга следующим:

· характером защищаемого информационного взаимодействия;
· целями злоумышленников;
· возможностями злоумышленников.

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

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

1. Угрозы со стороны злоумышленника.
1.1. Ознакомление с содержанием переданного сообщения.
1.2. Навязывание получателю ложного сообщения - как полная его фабрикация, так и внесение искажений в действительно переданное сообщение.
1.3. Изъятие переданного отправителем сообщения из системы таким образом, чтобы получатель не узнал о факте передачи сообщения;
1.4. Создание помех для нормальной работы канала передачи связи, то есть нарушение работоспособности канала связи.

2. Угрозы со стороны законного отправителя сообщения:
2.1. Разглашение переданного сообщения.
2.2. Отказ от авторства в действительности переданного им сообщения.
2.3. Утверждение, что некоторое сообщение отправлено получателю когда в действительности отправка не производилась.

3. Угрозы со стороны законного получателя сообщения:
3.1. Разглашение полученного сообщения.
3.2. Отказ от факта получения некоторого сообщения когда в действительности оно было им получено.
3.3. Утверждение, что некоторое сообщение получено от отправителя когда в действительности предъявленное сообщение сфабриковано самим получателем.

Как правило, угроза работоспособности канала связи (угроза 1.4) наиболее эффективно достигается нарушением физической среды передачи данных (разрушение линий передачи и узлов обработки данных) или созданием помех ("глушение" радиосигнала, бомбардировка системы большим количеством ложных сообщений - "спам", и т.д.). Близко к ней находится угроза 1.3 - изъятие сообщения из канала связи. Эффективной защиты криптографическими средствами от этих угроз не существует, поэтому они обычно не рассматривается в работах по криптографии, проблема решается другими методами. Так, для устранения угрозы 1.3 обычно используется квитирование - высылка получателем отправителю квитанции (подтверждения) на полученное сообщение. Также в рамках криптографии отсутствует решение, которое бы устранило угрозы 2.1 и 3.1 - разглашение секретных данных одной из легальных сторон со "списыванием" этого на другую сторону или на ненадежность канала связи.

Оказалось, что сформулированная выше задача за вычетом угроз 1.3, 1.4, 2.1, 3.1 может быть разделена на три подзадачи, которые решаются независимо друг от друга и характеризуются собственными наборами угроз из приведенного списка:

· "классическая задача криптографии" - защита данных от разглашения и искажения при передаче по открытому каналу связи;
· "подпись электронного документа" - защита от отказа от авторства сообщения;
· "вручение заказного письма" - защита от отказа от факта получения сообщения;

Ниже все три задачи рассмотрены с необходимой степенью подробности.

1. Защита передаваемых и хранимых секретных данных от разглашения и искажения.

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

· отправитель или источник сообщения (О, назовем его Олегом, чтобы избежать фраз типа "отправитель отправляет, а получатель получает");
· получатель или приемник сообщения (П, назовем его Петром);

Между отправителем и получателем сообщения есть взаимное доверие, поэтому в качестве злоумышленника может выступать только субъект, отличный от них обоих (З, назовем его Захаром). Олег отправляет Петру сообщение, при этом Захар может попытаться выполнить одного или нескольких следующих действий:

(1) чтение сообщений;
(2) внесение изменений в реальное переданное сообщение "на лету";
(3) создание нового сообщения и отправка его Петру от имени Олега.
(4) повторная передача ранее переданного сообщения;
(5) уничтожение переданного сообщения;

Каждое из перечисленных выше действий является атакой на наш информационный процесс. Возможности по доступу к каналу передачи, необходимые для их выполнения, различны, и в реальной ситуации может оказаться, что одни атаки осуществимы, а другие - нет. Для реализации атаки №1 необходим доступ к каналу передачи данных на чтение, для атаки №3 - на запись, для атаки №4 - на чтение и запись. Для осуществления атак №№2 и 5 необходим полный контроль над каналом, то есть возможность разорвать его и встроить туда собственные узлы обработки данных, или получить контроль над существующем узлом обработки. Какие из атак доступны злоумышленнику, зависит от конкретных условий протекания информационного процесса - от среды передачи данных, от аппаратуры, которой он располагает, и т.д.. Так, если средой передачи информации служит радиоэфир, осуществление атак №2 и частично №5 (если не рассматривать "глушение") невозможно, доступны только атаки №№1,3,4. При использовании оптоволоконной линии связи злоумышленнику может быть доступна только атака №1 - незаметно "врезаться" в оптоволоконную линию практически невозможно. Некоторые атаки из приведенного списка могут рассматриваться как последовательное осуществление других из того же списка. Так, атака №2 может рассматриваться как последовательное исполнение атак №№1,5,3, а атака № 4 - как исполнение атак №1 и 3, разнесенное по времени.

Подведем итог, постановка "классической" задачи криптографии следующая:

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

· передаваемые данные станут известны кому либо еще помимо законного получателя;
· передаваемые данные будут искажены, то есть получатель получит не то или не в точности то, что отправлено отправителем.

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

2. Задача подтверждения авторства сообщения.

В этой задаче принимаются во внимание угрозы 2.2 и 3.3 из приведенного выше списка - между отправителем и получателем сообщения отсутствует взаимное доверие и возможно возникновение конфликта по поводу переданных данных. Каждый из них может совершать злоумышленные действия, направленные против другой стороны, и по этой причине в системе необходимо наличие инстанции, которая выполняет "арбитражные" функции, то есть в случае конфликта между абонентами решает, кто из них прав, а кто нет - эта сторона по вполне понятным причинам называется в криптографии "независимым арбитражем". Вместе с тем, злоумышленник как отдельный субъект информационного процесса здесь отсутствует. Опишем задачу по той же схеме:

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

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

· отправитель откажется от авторства переданного им сообщения;
· получатель будет утверждать, что некоторое сообщение получено им от отправителя, хотя в действительности тот его не передавал.

3. Между отправителем и получателем отсутствует взаимное доверие, каждый из них может осуществить злоумышленные действия в отношении другого: Олег может попытаться убедить Антона, что он не отправлял сообщения, которое в действительности отправил Петру. Петр, в свою очередь, может попытаться убедить Антона в том, что он получил некоторое сообщение от Олега, хотя тот его в действительности не отправлял.

3. Вручение сообщения под расписку.

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

1. Законные стороны информационного процесса - отправитель и получатель сообщения.

· отправитель или источник сообщения (О, Олег);
· получатель или приемник сообщения (П, Петр);

Задача первого отправить, а второго получить сообщение и понять его содержание.

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

· отправитель будет утверждать, что передал получателю сообщение, хотя в действительности не отправлял его;
· получатель ознакомится с содержанием сообщения, но будет утверждать, что никакого сообщения не получал.

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

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

· Олег получает и читает сообщение;
· Петр получает подтверждение о том, что Олег получил сообщение.

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

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

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

Вот, пожалуй и все наиболее популярные задачи практической криптографии. Конечно, есть и другие, но они или менее известны, или отсутствует их удовлетворительное решение, или это решение есть, но оно не получило заметного практического применения. Кратко перечислим наиболее известные из этих "теоретических" задач:

1. Синхронный обмен сообщениями. Требуется организовать обмен двух субъектов сообщениями таким образом, чтобы ни один из них, получив сообщение другой стороны, не смог отказаться от передачи своего и не смог сформировать свое сообщение в зависимости от сведений из сообщения другой стороны. В качестве дополнительного условия иногда требуется, чтобы передаваемые сообщения удовлетворяли определенным заранее критериям.

2. Как вариант предыдущей задачи - проблема "подписи контракта": есть два документа в электронной форме и есть процедура выработки цифровой подписи под документами. Требуется организовать обмен подписанными документами между двумя субъектами таким образом, чтобы ни один из них не смог отказаться передавать "свой" подписанный документ, получив подписанный документ от другой стороны. Очевидно, что это вариант предыдущей задачи, в котором "определенный критерий" - это корректность подписи документа, то есть соответствие подписи содержанию.

3. "Передача с забыванием" - организовать передачу сообщения одним субъектом другому таким образом, чтобы вероятность получения сообщения была ровно 0.5 и чтобы на эту вероятность никто не мог повлиять.

4. "Бросание монеты по телефону" - организовать такое взаимодействие не доверяющих друг другу субъектов через канал передачи данных, которое позволит выработать один бит информации (значение 0 или 1) таким образом, чтобы он был случайным, несмещенным (вероятность каждого исхода равна 0.5), чтобы на исход "бросания монеты" не мог повлиять никто извне ("третьи лица"), и чтобы в исходе "бросания" можно было убедить независимый арбитраж при возникновении у участников разногласий о результате.

5. "Сравнение с нулевым разглашением" или "проблема двух миллионеров" - два миллионера хотят узнать, кто из них богаче, но при этом никто из них не хочет сообщить другой стороне истинную величину своего состояния. В более общей постановке задача формулируется следующим образом: есть два субъекта, каждый из которых располагает некоторым элементом данных - соответственно a и b, и которые желают совместно вычислить значение некоторой согласованной функции f(a,b). Требуется организовать процедуру вычисления таким образом, чтобы никто из субъектов не узнал значения параметра другого.

6. "(n,k)-пороговая схема" - имеется некоторый ресурс, например - зашифрованный набор данных (файл), также есть n субъектов. Необходимо построить процедуру, разрешающую доступ к ресурсу (дающую возможность расшифровать файл), только если его запросят одновременно не менее k субъектов.

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

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

(Продолжение следует)

Опубликовано: Андрей Винокуров

Случайная заметка

6231 день назад, 02:453 ноября 2000 Все конечно помнят такой компьютер как ZX Spectrum. И многие знают что его пытались развивать (всякие ATM-Turbo, Scorpion, и т.д.) Однако не все, я уверен, слышали о такой любопытной машинке как Sprinter. На Chaos Construction'000 автор пытался сказать о ней пару слов, однако не очень настойчиво, ничего не показав на большом экране, так что толком никто ...далее

Избранное

204 дня назад, 01:575 мая 2017 Часть 1: От четырёх до восьми Я люблю читать воспоминания людей, заставших первые шаги вычислительной техники в их стране. В них всегда есть какая-то романтика, причём какого она рода — сильно зависит от того, с каких компьютеров люди начали. Обычно это определяется обстоятельствами — местом работы, учёбы, а иногда и вовсе — ...далее

1709 дней назад, 00:5922 марта 2013 Прочёл тут книжку - iWoz ( ссылка ) , 2006 года. Это автобиография Стива Возняка. Похоже, что на русский её не переводили (в отличие от книг про Стива Джобса). В этой парочке, как известно, Возняк был инженером (собственно, и спроектировавшим Apple I и II), а Джобс - скорее предпринимателем. В книге есть довольно интересные ...далее

813 дня назад, 23:404 сентября 2015 Небольшое видео про CC'2015 ( версия без фоновой музыки здесь: ссылка )

1181 день назад, 03:121 сентября 2014 Мой семинар на Chaos Constructions'2014 (слайды можно в виде PDF скачать здесь: ссылка ) и несколько интервью с разными людьми: Вячеслав Славинский (svo) о Vectrex: ссылка Вячеслав Славинский (svo) о 3D Imager для Vectrex: ссылка Вячеслав Славинский (svo) о световом пере для Vectrex: ссылка ...далее