существует ли реализация OTP для компьютера?
Здравствуйте. Предположим, Алисе и Бобу нужно изредка обмениваться очень конфиденциальными сведениями, которые д.б. конфиденциальны длительное время (например, 50-70 лет). Алиса и Боб опасаются, что их ключи в течении такого срока мокут быть скомпрометированы, или талантливые участники форума PGPRU изобретут таки способ эффективного криптоаналихза PGP и т.д. Более того, Алиса и Боб дошли до такой степени паранои, что опасаются использовать даже Conventional encryption, т.е. чисто симметричный алгоритм. Читая FAQи они узнали, что самый надежный способ шифрования – использование одноразовых блокнотов.
Дальше такая фантазия. Скажем, Боб покупает устройство, генерирующее действительно случайные числа (кажется, Интел выпускал такие для научных применений). Генерирует массив случ. чисел и записывает его на две большие, гигов по 8, флешки (они, кстати, могут быть закриптованы тем же PGP Disk).
Одну флешку Боб передает лично Алисе in privacy and confidence. Дальше, при необходимости отправить по открытым каналам связи секретные сведения, Боб запусти на своем компе (на всякий случай отрезанном от сети) ПО, которое возьмет файл со сведениями, к каждому его байту прибавит очередное случ. число с флешки, использованные числа потом затрет алгоритмом Гутмана с хорошим числом проходов. Алиса сделает обратную операцию и тоже грохнет использованную часть таблицы. Когда флешки закончатся, можно их на всякий пожарный уничтожить – кислота, плавка и т.д.
Или не будем затирать использованную часть таблицы. С шифротекстом будем передавать сдвиг начала использованного для его кодирования массива случ. чисел. Тогда можно будет хранить файлы в закодированном виде, а при необходимости – открывать. Естественно, в ПО предусмотрим контроль "одноразовости" блокнота.
Понятно, что такая процедура крайне неудобна – нужно генерировать таблицы, передать по абс. надежному, закрытому каналу, т.е. лично, ключ (флешку), не забыть потом ее грохнуть. Для каждодневной работы с широким кругом лиц явно не подходит, но зато для обмена небольшими сообщениями между ограниченным числом пользователей (двумя, скорее всего) может применяться.
Как вам такой сценарий в целом? существует ли такое ПО? если бы Вы собирались его написать, какую функциональность Вы бы еще заложили? что нужно предусмотреть в самой процедуре использования таких "электронных" блокнотов? на сколько упадет надежность системы, если будет использоваться програмный датчик случ. чисел, например из PGP? и главное – OTP-действительно идеально надежный шифр?
Заранее благодарю
Ссылки
[link1] http://www.cypherpunks.ca/otr/
[link2] http://en.wikipedia.org/wiki/Off-the-Record_Messaging
[link3] https://www.pgpru.com/novosti/2008/predskazuemyjjgschinebezopasnyekljuchivdebianubuntu
[link4] https://www.pgpru.com/comment23777
[link5] https://www.pgpru.com/comment16549
[link6] http://imotp.sourceforge.net/noise.pdf
[link7] http://warmcat.com/_wp/whirlygig-rng/
[link8] http://leo.yuriev.ru/114
[link9] http://ufn.ru/ru/articles/1998/10/e/
[link10] http://www.ufn.ru/ru/articles/2000/2/m/
[link11] http://noosphere.princeton.edu/
[link12] http://www.koob.ru/arguelles_jose/zond_s_arktura
[link13] http://krypt.cs.uni-sb.de/projects/randy/randy.pdf
[link14] http://www.idquantique.com/products/quantis.htm
[link15] https://www.pgpru.com/biblioteka/statji/analiznadezhnostipgp/analizishodnogokoda/sluchajjnyechisla
Сценарий нормален, но не очень физичен. Скажем так, имхо, стоит ограничить требование невзламываемости крипто сроком в человеческую жизнь (возьмём лет 70 к примеру, полагая что лет 20 вы уже прожили). Тогда можно организовать некий каскадный шифр, который с очень большой вероятностью не будет сломан даже за 70 лет (вы помните, что даже все сообщения, зашифрованные даже слабенькой энигмой, взломаны... до сих пор).
Согласно терминологии, OTR – это зарезервированное слово для соврешенно конкретной криптосхемы, часть которой – симметричный алгоритм. Я не уверен, что OTR не фиксирует даже алгоритм. Соответственно, то, что вы хотите, называется просто "криптопротоколом с компонентами одноразового блокнота", но не OTR. Касаемо надёжности – да, его надёжность ограничена надёжность генератора случайных чисел, насколько же последняя случайна – это уже отдельный вопрос... Так что ограничение сверху на защиту, конечно, есть :)
Скорее всего, такого ПО пока нет, но это его легко написать при необходимости. Емнип, это банальный XOR между блокнотом и текстом + автоматизация.
Совместимость с jabber'ом. Впрочем, если сообщения передавать редко и небольшие, то можно и командной строкой зашифровать а потмо переслать вручную по любому из стандартных каналов (jabber, mail, etc).
Вы писали про заводские генераторы шума. Насколько вероятно наличие закладки в нём? Я бы на вашем месте не доверял бы... при таком уровне требований (ибо пренебрежение малостью членов O(1/x) при погоне за членами O(1/x^2), при x->inf – нефизично), но сам собрал бы подобный генератор, либо заказал бы его у людей, которым доверяю. В крайнем случае, можно генераторы объединить в каскад, чтоб даже если один окажется с закладкой – другие не пострадали.
Зависит от вероятности наличия ошибки в большом-большом куске кода, при условии хорошего его аудита. Ну, скажем так, эта вероятность, оценочно, явно не меньше чем вскрытие всех шифров за 70 лет, так что можно условиться говорить "упадёт ощутимо".
Вообще, по поводу криптографии ну шумах, много чего интересного писал unknown, и в том числе про крипто между двумя участниками, использующими один и тот же природный генератор шума (давно ещё была длинная ветка на pgpru по этой теме). М.б. на природном шуме вам лучше сделать а не на шифроблокноте? (не разбираюсь в теме).
s/взломаны.../не взломаны.../
Вдогонку: не следует пренебрегать вероятностью того, что к вам прийдут домой ранее чем через 70 лет, и заберут флэшку со случайными данными. Если эта вероятность намного выше, чем взлом за 70 лет, заботиться о надёжности шифров не следует... ибо шифроблокнот защищён не лучше, чем совокупность каскадных шифров. Впрочем, флэшку можно хранить где-то далеко и глубоко, нивелировав тем ущерб от "наезда" (опять же, это лишь для случая редких сообщений между участниками, а то устанете каждый раз раскапывать и закапывать :)).
Закладка в шумящих диодах? Ну это уж слишком. К тому же в практических приложениях даже вывод от аппаратного ГСЧ не применяется в одиночку (используется смесь от нескольких аппаратных генераторов и программных источников случайности), без проверки на случайность и криптографического отбеливания.
Дано: вагон простейших полупроводниковых схем, любую из которых можете купить в первом встречном магазине, и кастомное устройство, собранное по спецзаказу. Со статистической точки зрения, где вероятность закладки выше?
Кстати, хранить гамму на флэшке и пытаться удалить её Гутманом — изначальный провал всей затеи. :-)
Для хранения можно использовать пачку CD-R, уничтожать их можно в обычной микроволновой печке. Лучше с грилем :)
При правиьном применении да.
Одноразовый блокнот – One Time Pad. OTR – Off-the-Record Messaging. Разные вещи, разные сокращения.
Это экзотический метод, близкий к квантовой криптографии. Требует аналоговой проводной или радио- линии связи и измерительного оборудования за отслеживанием параметров канала. Широко коммерческого применения не предвидится (хотя попытки были), поэтому открытых исследований мало.
До уровня генератора псевдослучайных чисел, в пределе – до уровня обычного потокового шифра.
Как генерировать гамму? Самое простое оцифровывать и хэшировать (или использовать более сложные алгоритмы экстракции энтропии) шумы. Есть генераторы не на оцифровке аналоговых шумов (они могут иметь нестабильность и войти в малошумящий режим), а на явлении джиттера в цифровых схемах. Тоже можно сделать, скорость будет намного выше, но вероятность всяких неслучайных режимов тоже велика. И то и другое было повторено любителями из простейших деталей.
Критично в OTP отсутствие повторений одного и того же участка гаммы для шифрования.
Бумажные блокноты для этого запечатывались в коверты – было видно что вскрывали, одноразовые перфоленты заправляли в кэртриджи, в которых размотанную перфоленту нельзя засунуть обратно. Использованные части тут же можно было уничтожить.
Как это реализовать на электронных носителях – неясно.
Ещё одна проблема – аутентификация. Если противнику известна часть открытого текста, то он может заменить её другим текстом. Для аутентификации потребуется или ещё одна гамма или какие-то более сложные схемы.
Спасибо за развернутые ответы.
я имел в виду OTP = One Time Pads, т.е. реализацию одноразового блокнота в чистом виде. а что такое OTR? Не дадите ссылку?
Не могли бы Вы прокомментировать, как построены оценки? Или это чисто образное выражение?
генератор я бы с удовольствием собрал, но к сожалению не обладаю должной квалификацией, чтобы его разработать. Мне на ум приходило разве что собрать устройство, регистрирующее какие-то природные явления, например время между падениями капель дождя на пластину, замыкающую сухой контакт.
м.б. существуют проверенные сообществом открытые схемы электронных генераторов, по которым можно было бы его изготовить?
очень интересно. а не дадите ссылочку на ветку?
На счет того, что флешку с блокнотом могут изъять Вы конечно правы. Наверное нужно все-таки затирать использованные куски блокнота. Но как? Господин SATva конечно прав, Гутман не является гарантией, а размагнитить часть флешки не возможно. Вариант – раздробить "блокнот" на "страницы", например CD-R -ки. Кстати, их что действительно можно уничтожать в СВЧ? А измельчение в шредере пойдет?
по любому, держать коробку с дисками очень не удобно, а провозить ее через таможню – вообще беда. Может есть еще варианты?
Господин SATva, а провал – именно в уничтожении использованной страницы Гутманом, или и в хранении блокнота на флэшке в принципе?
Вобщем, наверное я попробую написать такую программу. Открытую, конечно. Может, кому еще будет полезно. Очень нуждаюсь в ваших советах и обсуждении протокола, ТЗ и самого ПО ))
Так уж сложилось, что в русском языке одноразовый блокнот называют именно одноразовым блокнотом, а OTR – OTR'ом, но OTR=ОТР (калька из-за произношения).
Придуман был OTR вот этими[link1] товарищами, есть инфа и в вики[link2].
Скорее образное. Математический частный пример поговорки про "поглощение слона и отцеживание комара". Вы же строете модель угрозы. Идеальная модель (описывающая реальность) непомерно сложна, и потому непостроима, а, значит, вы берёте какое-то к ней приближение, т.е., выражаясь математическим языком, разлагаете по малому параметру и опускаете члены, порядок которых меньше некоторых. Если вы учили когда-то математику в вузе, вам это должно быть очень понятно – сие не более, чем матанализ...
Ну вот выше SATtva
п0ржалпосмеялся над... хотя я не вижу никакой проблемы в изготовлении приборов, дающих "псевдослучайный шум". Конечно, из-за того что их шум всегда будет смешиваться ещё и с программными источниками шума, адже наличие закладки вряд ли даст какие-либо преимущества оппоненту в практическом смысле на данный момент. Вы же опираетесь на то, что вам недостаточен программный источник шума – доселе такие сильные требования не рассматривались. Но если уж их рассмотреть... то пожалуй и генератор стоит свой делать. Возвращаясь же к большей конкретике, я не думаю что вам стоит заморачиваться с отдельным источником шума в принципе. На практие их используют лишь тогда, когда нужно постоянно генерить большие объёмы случайных данных, с чем программные источники шума надёжно не могут справиться (а это не ваш случай), во всех же остальных ситуациях все используют программные датчики... В некоторых из них находили уязвимости – тоже было дело, но так чтобы это позволило скомпрометировать сгенерированные ключи я слышал лишь единственный раз[link3], да и там проблема была не из-за слабого источника шума, а лишь из-за банальной ошибки в программе...Думаю, что существуют, но конкретикой не интересовался, равно как и электроникой.
Я, пожалуй, не найду... я там не флудил, а потому ключевых слов оттуда не помню :) Надо попросить unknown'а – если он смилостивится, то даст.
Здесь дело именно во "внутренней физике" флэш-накопителей. Почитайте начиная с этого[link4] поста весь тот топик, там обсуждалось. А что вам мешает хранить блокнот на жёстком диске, затирая использованные части Шредером? Там таких проблем нет.
Не очень. Каждый мелкий кусочек потом можно будет лазером считать на спецоборудовании. Лучше сжечь, или потереть в порошок :)
Шифроблокнот на криптофс на обычно жёстком диске (можно даже на внешнем USB-диске, но не флэш только!).
XOR делается в одну строку. Всё остальное – автоматизация процесса и интегрирование его с естественным окружением пользователя, включая какие-то протоколы типа jabber.
Лучше всего и то, и другое. :-)
"Метод Гутмана" — это набор паттернов, предложенных Питером Гутманом более десяти лет назад (в 96-м) для уничтожения данных с жёстких дисков. Паттерны были специально подобраны под алгоритмы кодирования данных контроллерами жёстких дисков того времени. Как писал сам Гутман в более поздних дополнениях к той статье, сейчас та методика уничтожения бессмысленна: алгоритмы кодирования теперь другие, а плотность записи такова, что даже простой многократной (3-7 раз) перезаписи псевдослучайным потоком достаточно, чтобы сделать данные невосстановимыми (если не требуются исключительные меры, для которых достаточно только физического уничтожения магнитных пластин).
К флэшкам эта методика принципиально неприменима. Поскольку многократная запись быстро выводить флэш-накопители из строя, их микроконтроллеры производят отложенную запись; так что даже при многократной перезаписи файла реально записан будет только последний проход. Более того, контроллеры оптимизируют запись, распределяя данные по физическим доменам, чтобы все домены проходили примерно равное количество циклов перезаписи; поэтому фактически тот поток, которым Вы пытаетесь перезаписать файл, может быть записан в совершенно другую физическую часть флэш-памяти, а данные файла останутся на прежнем месте.
В более поздней работе "Data Remanence in Semiconductor Devices", посвящённой вопросам остаточных данных в полупроводниковых устройствах хранения данных (флэшки, ОЗУ, EEPROM), Гутман приводит такой способ стирания. Поскольку флэш-память (в отличие от магнитных накопителей) не нуждается в многократной перезаписи, достаточно однократно заполнить всё свободное пространство флэшки случайными данными.
А лучше всего записывать данные на флэшку только в зашифрованном виде, а при необходимости уничтожить их — уничтожать ключ, хранящийся на обычном диске.
Разбираем винчестер, достаём оттуда пластину с использованной частью блокнота и спускаем в шреддер? :-)))
Зачем пластину? Блокнот между пластинами спрятан, его нужно только вытащить и сжечь, а корпус жёсткого диска – лишь как футляр для блокнота.
Noisy Crypto[link5] обсуждалось отсюда и до конца той ветки.
Схемы генераторов шумов:
На полупроводниках:
Random Number Generation with a Simple Transistor. Junction Noise Source[link6]
На эффекте осцилляции в микросхемах:
Whirlygig RNG[link7]
Есть схемы на радиоактивных источниках и доступные для воспроизведения квантово-оптические схемы, но это уже не для любителей, а для исследователей-студентов. Самые перспективные квантовоптические – почти не требуют постобработки данных.
Не следует путать сгенерированные ключи с гаммой одноразового блокнота.
От Джона Калласа ещё поступала такая идея. Взять простейшую, самую дешёвую CMOS-матрицу, какие устанавливали в первые фотокамеры в мобильных телефонах. Направить её на белый лист бумаги. Вывод такой матрицы уже будет результатом квантовых свойств.
А обычная вэб-камера подойдет? Ну, например Genius NB 100K?
Не совсем корректно. Квантовые датчики считают отдельные фотоны, а не интегральный шум, который всегда имеет неравномерное распределение.
В простейшем квантовом детекторе фотоны пролетают через сваренное оптоволокно – в зависимости от поляризации он полетит или по короткому пути или по скрученому в спираль длинному. Микросекундые задержки фиксируются датчиками. И то не всё идеально (постэффекты какие-то, это уже к spinore на эту тему).
В большинстве случаев достаточно и плохого датчика (если не нужны гигансткие скорости генерации), но с хорошей постобработкой.
Звучит как вопрос к продавцу в магазине: "Скажите вот эта модель подойдёт для генерации одноразовых блокнотов"?
"Взвесьте мне грамм семьсот-восемьсот случайных чисел, пожалуйста."
Новая характеристика камер: поток случайных чисел в мегабитах на мегапиксель.
а что, продажа случайных чисел – хорошая бизнес концепция по-моему. Случайные числа, случайные числа! Для научных применений, для Монте-Карло, для крипто... Постоянным покупателям и гос. учреждениям скидка :))) Если бы продавала компания с безупречной репутацией (та же ПГП например), может и нашлись бы желающие.
Перефразируя немецкую поговорку, что знают двое, то уже не случайное число. ;-) Инструменты для их генерации слишком широко доступны и дёшевы, чтобы аутсорсить эту задачу. Проблема передачи, опять же.
Хотя раньше так действительно делали. Пример — известная книга со случайными числами, которую печатал в середине прошлого века... Ранд или Ксерокс? Ну, кто-то там, в общем. В военной сфере выработка шифроключей в специальной надёжной среде тоже практикуется.
ну да, на радиоактивном источнике наверное проще всего собрать. Это, по сути, изотоп + простейший детектор (натрий-йодный например). И мереем интенсивность потока за малый квант времени. главное подобрать интенсивность изотопа и детектор так, чтобы не получилось постоянного среднего значения интенсивности, чтобы разрешение детектора и всей последующей цепи (ФЭУ, АЦП) позволило увидеть дисперсию, и именно временную, а не энергетическую.
В любом случае – радиоактивность это физически "качественный" случайный процесс. я прав?
а есть какие-нибудь сведения об аппаратурном оформлении такого датчика? И еще, какая д.б. постобработка? И как оценить "качество" получаемой последовательности? Для этого достаточно теории и тестов, изложенных у Д. Кнутта?
Уважаемый unknown, я заранее извиняюсь, если задаю вопросы, ответы на которые уже содержатся в указанных Вами описаниях генераторов. Я просто сейчас сижу на очень медленном GPRS канале и еще не смотрел ссылки.
Ну... в нашей вселенной это так :) Другое дело – правильно извлечь эту случайность. Как ещё заметил unknown, есть квантовый шум в оптических приборах – оно из той же категории, но тоже надо уметь правильно извлечь.
Очень смешно, ну просто обхохочешься! Xa-Xa-Xa!
Ну а если серьезно. Если использовать снимки или данные с камеры как случайное число. Камера направлена на белый лист бумаги и в помещение постоянно меняется освещенность, или использовать вспышку – вспомните, как делают нфоцелограмму.
Камера делает снимки с постоянно-изменяемой скоростью; Вспышка моргает с постоянно-изменяемой скоростью; Угол наклона белого листа тоже можно изменять; Можно добавить маятник. А программа выбирает псевдослучайные снимки и тд.
еще_один_гость, дело не в очевидной различности кадров, а в шумах, регистрируемых матрицей. Камера просто "тупо" смотрит на белый (или какой угодно другой) экран, больше ничего не требуется.
Видео(веб) камера наиболее случайно шумит в закрытом состоянии.
Ещё Как то забыли о звуковой карте. Вот[link8] статья Леонида Юрьева. Там же есть хороший генератор на основе звуковой карты, правда без исходников :(
Для обоснования наличия больших массивов случайных данных можно заняться изучением, как бы это поприличнее сказать, реализации дискретных состояний в ходе флуктуаций в макроскопических процессах[link9]! (см. также это замечание[link10] )
Можно участвовать в каком-нибудь таком[link11] проекте.
По этому поводу есть и другие мнения:
http://pavel-znykin.narod.ru/Vorsuhung.html
И вот ещё сборник легенд[link12]...
Нафига засирать форум цитатами из лженауки? Это уже давно не смешно.
со схемой:
RANDy – A True-Random Generator Based On Radioactive Decay.[link13]
Оптический квантовый генератор на одиночных фотонах известен только коммерческий[link14]. Подробных и доступных для простого воспроизведения схем мне не встречалось.
Тестирование случайности – тесты DieHard. У Кнута кажется были описаны не все продвинутые тесты и больше критики PRNG-генераторов, которые вообще не имеют отношения к криптостойкости. (PRNG может пройти все тесты и быть тривиально некриптостойким в отличие от TRNG).
Постобработка – randomness extraction. В простейшем случае: сначала алгоритм фон Неймана. отбрасываем соседние одинаковые биты, а пары разных заменяем на один (первый). Затем хэширование большого объёма недостаточно качественных случайных чисел в малый объём, который используется на выходе. Иногда используется не просто хэширование, а более сложные функции.
Не хотелось бы открывать тут дискуссию о критериях, но вот хотелось бы обратить внимание на манеру выражаться "борцов с лженаукой". Как ни странно, это типичное явление.
А вообще то речь шла о том, как обосновать наличие у вас больших массивов случайных данных. В этом случае, как нетрудно понять, важна не истиннось, а правдоподобность.
Остаётся 0101010101010101010101... ?
Если было что-то вроде 00 01 11 10 11 01 00 10 11 01 00 10, то да.
"Произошла спонтанная связь космического разума со вселенской энтропией", "Бес попутал"...
"Случайность это непознанная закономерность" ©
супер, спасибо. на первый просмотр это прямо инструкция как собрать генератор из подручных средств. Попробую исполнить.
интересно, насколько целесообразной былал бы функция генерации ключа в ПГП с использованием аппаратного генератора? Ну, типа, нет генератора – все происходит поумолчанию, ключи генерируются как сейчас. Есть генератор – поставил в опциях галочку и можно использовать. Это как-то отразилось бы на стойкости шифрования ПГП?
Единственное, на чём может сказаться наличие аппаратного ГСЧ, — это на скорости и объёме выработки случайных чисел. Энтропию можно накапливать и программно (что и делается[link15]), просто в значительно меньших объёмах. Но для тех задач, для которых применяется PGP, и этого достаточно. Реально полезен аппаратный генератор только на сервере, выполняющем множество криптоприложений, и в других очень специфических случаях.
Считайте, что программный генератор не хуже внешнего, если в нём нет ошибок. Но ошибки могут и во внешнем быть :)
TAN$TAAFL Top Secret Crypto Gold (программа есть такая)