реализация шифра Вернама
Хочу представить сообществу свою программу – реализацию шифра Вернама (одноразовый блокнот)[link1] с дополнительными функциями. Программа написана на Python и может:
- Генерировать ключи, используя функцию os.urandom()[link2]
- Шифровать и расшифровывать данные
- При шифровании добавлять в конец данных контрольную сумму (sha1) и проверять ее при расшифровании
- Сжимать данные с помощью gzip или bzip2
Размер – меньше 400 (четырехсот) строк.
Лицензия – MIT.
https://github.com/anton-tsyganenko/otppy
При привильном использовании и отсутствии закладок в ОС и интерпритаторе взлом абсолютно невозможен.
Ссылки
[link1] http://ru.wikipedia.org/wiki/Шифр_Вернама
[link2] https://docs.python.org/3/library/os.html#os.urandom
[link3] http://www.pgpru.com/comment65563
[link4] http://www.pgpru.com/comment68173
[link5] http://www.pgpru.com/novosti/2013/havegealjternativnyjjsposobpoluchenijakriptostojjkojjentropiiizprocessorov
[link6] http://ru.wikipedia.org/wiki/Криптографически_стойкий_генератор_псевдослучайных_чисел
urandom не является источником экстрагированной физической энтропии, а является источником растянутой из коротких значений псевдоэнтропии → программа не является реализацией шифра Вернама.
А насколько это надежно? Если его заменять, то на что? (радиоактивный распад не предлагать)
Так вроде же нет спецификиций.
Насколько надёжно что? urandom? Он дёргает мелкие куски энтропии и растягивает их в большую гамму. Поскольку гамма наверняка генерится за один раз, то она вся будет растянута из одного внутреннего состояния, образованного мелким фрагментов энтропии. Это надёжно, примерно как некий потоковый шифр, хотя и с большим внутренним состоянием и зависит от того, какой алгоритм реализован в os.urandom. В пределе это должно быть надёжно, как обычный 256-512-битовый шифр. Истинная случайность экстрагируется только постобработкой данных физических процессов.
os.urandom в unix-системах берет случайные данные из /dev/urandom, в винде – CryptGenRandom(). Пост-обработка физических процессов недоступна большинству пользователей.
Кстати, если ключ не очень случайный, сжатие поможет?
Нет:
Да даже если б у вас стоял QRNG[link4], дальше-то что? Нужно, чтоб одна и та же гамма была на обоих концах связи, а как вы её туда доставите? Добро пожаловать в QKD.
Передать можно при личной встрече или в сейф-пакете. Только не надо говорить, что при личной встрече можно сразу передать и данные – передача ключа может осуществляться тогда, когда данных еще нет.
Ну, если только так...
Использование системной функции создает удобную универсальную лазейку. Достаточно перехватить вызов, и сразу видно сами случайные числа, а также какому процессу, в какой момент и в какой точке они понадобились.
http://www.zas-comm.ru
Понятно, что если в системе есть закладки, трояны, кейлогеры и т.д., то каким бы не был хорошим алгоритм, он не спасет. Даже если получать случайные числа другим образом, троян может сделать дамп памяти. Предполагается, что используемая система надежна и в ваш монитор посторонние не смотрят.
Вообще, реализация OTP (даже если это именно OTP, а не непонятно что, как в данном случае) — это что-то типа hello world: столь же элементарно, сколь и бессмысленно. То есть как абстрактная задача сойдёт, но выкладывать это в паблик по меньшей мере пошло.
Да, изначально было just for fun. Хотя чем проще алгоритм и меньше программа, тем проще ее проверить. Понятно, что пока есть pgp, она вряд-ли будет пользоваться популярностью, но квантовый суперкомпютер рано или поздно будет сделан, и тогда расшифровка pgp-сообщений не составит труда.
В данном случае это OTP, хоть там и куча отсебятины, ключи используются только один раз.
unknown выше написал, в чём главная проблема: источник материала для ключей — ГПСЧ, что превращает Вашу реализацию в тыкву. Хотя бы берите энтропию из /dev/random — даже с учётом всех его проблем и блокируемости чтения, такой вариант будет выглядеть более вменяемо.
Можете объяснить разницу между /dev/random и /dev/urandom? А если для генерации ключей 2 раза использовать os.urandom, а потом xor-ить их между собой?
Будет XOR соседних учатков гаммы, развёрнутой из одного и того же фрагмента энтропии, условного ключа.
/dev/random накапливает "чистую" энтропию от физических источников случайности, имеющихся в конкретной системе (от традиционных, типа тайминга нажатия клавиш, дельт перемещений мыши, задержек чтения с HDD из-за турбулентных процессов, и до более специфических, типа аппаратных ГСЧ в интеловских процессорах), иными словами, это генератор случайных чисел (ГСЧ) в общепринятом понимании, который только и может использоваться для выработки одноразовых блокнотов, поскольку в этом случае их стойкость является безусловной.
/dev/urandom, напротив, не получает энтропию непосредственно из источников случайности. Это обычный генератор псевдослучайных последовательностей, периодически ресидируемый от ввода /dev/random. Таким образом, стойкость полученных из него одноразовых блокнотов будет опираться на стойкость самого генератора и используемых в его основе криптопримитивов, которые могут быть уязвимы к различным классам атак (в том числе и помянутому Вами КК). Нельзя для OTP использовать PRNG, иначе теряется весь смысл OTP. С тем же успехом можете юзать обычный блочный шифр.
Без разницы.
Хорошо, попробую заменить /dev/urandom на /dev/random, только как быть с виндой?
С виндой лучше не быть никак, но используйте там хотя бы Crypto.Random (Fortuna RNG) из pycrypto.
Все-таки тыква получается, попытался сделать генератор, использующий /dev/random, так он несколько минут 100 байт генерировал. На такое заменять не получится.
/dev/random блокирует чтение, если в нём недостаточно энтропии. Подключайте быстрые источники энтропии (timer_entropyd, audio_entropyd, haveged[link5]), а не компрометируйте требования к генератору. Медленное поступление энтропии — проблема пользователя, а не OTP.
Хотел бы уточнить, я правильно понимаю, что нужен Криптографически стойкий генератор псевдослучайных чисел[link6]
Нет, нужен генератор истинно случайных чисел. Ничего "псевдо" для OTP не годится.
Вообще, по поводу использования urandom вместо random есть естественно возникающие вопросы: раз всё разворачивается с одного seed'а, значит, если я сгенерил несколько ключей для шифрования, не надо брутфорсить их по отдельности — вместо этого достаточно брутфорсить seed. Затем, если противник получил кусок трафика разных типов и знает, что в этот же момент я генерировал ключи, то ему, опять же, не надо по отдельности ломать всё из перечисленных (шифрование ssh, tor, LUKS) — вместо этого достаточно брутфорсить всё тот же единственный seed, который был использованы в данный момент.
Есть некоторая надежда на техническую сложность — противник не всегда знает, когда сидируется urandom, и потому не знает, ключи каких процессов связаны между собой одним seed'ом, но чисто теоретически уязвимость остаётся. Например, в ситуации, когда злонамеренный процесс запущен в той же ОС, что и критичные к безопасности, это может играть роль: зная, что другие процессы черпают энтропию из urandom, зловред тоже оттуда извлекает какой-то кусок, и теперь он знает, что всё, что наполучали втечение некоторого промежутка другие процессы, покрывается одним seed'ом. В некотором смысле из-за этого получается, что один процесс может знать, какие случайные данные получил из пула другой процесс (modulo 128-битная стойкость или какой там размер seed'а?).
Кстати, есть ли возможность более частого сидирования urandom? Можно ли сделать так, чтоб urandom сидировался (осеменялся) сразу же, как только в random появляется достаточное количество энтропии, а не так как сейчас (кажется, не чаще, чем раз в несколько минут?). Или это чем-то плохо для безопасности?
Вот еще идея для генерации ключей: пользователь создает папку и кладет туда кучу разных файлов: фотографий, видео, записей с диктофона, текстов, желательно – собственного производства. Затем программа читает содержимое каждого их них, складывает все в общую кучу и разбивает на куски длиной, равной количеству необходимых случайных данных (один кусок может получиться короче). потом xor-ит их между собой и результат xor-ит c данными, полученными из urandom.
Вы начинаете изобретать RNG, это дурной знак. :)
Почему же сразу дурной знак? Если /dev/random слишком медленный, /dev/urandom не годится, а аппаратный ГСЧ на основе радиоактивного распада есть не у всех, то почему бы не изобрести
велосипедRNG?Если в системе, есть выход в интернет, может проще собирать энтропию с различных сайтов с часто изменяющейся 1-й страничкой, тк: новостные, биржевые, погодных и др.
типа md5("http://site1.xxx") ^ md5("http://site2.xxx") ^ ...
facepalm.jpg
Во первых, с помощью списка сайтов можно получить немного энтропии.
Во вторых, вы где собираетесь держать список сайтов? если вшить в генератор, то злоумышленник тоже сможет получить этот-же результат
Сделал такой RNG, как описывал. По идее, если ему скормить несколько файлов, таких как фотографии, видео, аудио, то должно быть достаточно надежно. Какие у него могут быть уязвимости?
Такие, что противник может постфактум получить эти данные и восстановить состояние генератора. Надёжные источники случайности трансиентны.
После генерации данные удаляются.
Удаляются откуда? С диска? You gotta be kidding.
Да, удаляются с диска, просто удаляются, не затираясь, скорее для того, чтобы пользователь не использовал их 2 раз для генерации ключей.