реализация шифра Вернама


Хочу представить сообществу свою программу – реализацию шифра Вернама (одноразовый блокнот)[link1] с дополнительными функциями. Программа написана на Python и может:
Контрольная сумма нужна для зашиты от подмены в случае, когда злоумышленнику известна часть ключа/сообщения. Контрольная сумма и сжатие опциональны, по умолчанию программа добавляет контрольную сумму, если использовать сжатие, то sha1 добавляться уже не будет. При необходимости можно отключить оба варианта или использовать их вместе. Прилагается документация на русском и английском.
Размер – меньше 400 (четырехсот) строк.
Лицензия – MIT.
https://github.com/anton-tsyganenko/otppy
При привильном использовании и отсутствии закладок в ОС и интерпритаторе взлом абсолютно невозможен.

Комментарии
— unknown (01/06/2014 20:36)   

urandom не является источником экстрагированной физической энтропии, а является источником растянутой из коротких значений псевдоэнтропии → программа не является реализацией шифра Вернама.
— Anton_Tsyganenko (01/06/2014 21:08)   
urandom не является источником экстрагированной физической энтропии, а является источником растянутой из коротких значений псевдоэнтропии

А насколько это надежно? Если его заменять, то на что? (радиоактивный распад не предлагать)
программа не является реализацией шифра Вернама.

Так вроде же нет спецификиций.
— unknown (01/06/2014 21:18, исправлен 01/06/2014 21:19)   

Насколько надёжно что? urandom? Он дёргает мелкие куски энтропии и растягивает их в большую гамму. Поскольку гамма наверняка генерится за один раз, то она вся будет растянута из одного внутреннего состояния, образованного мелким фрагментов энтропии. Это надёжно, примерно как некий потоковый шифр, хотя и с большим внутренним состоянием и зависит от того, какой алгоритм реализован в os.urandom. В пределе это должно быть надёжно, как обычный 256-512-битовый шифр. Истинная случайность экстрагируется только постобработкой данных физических процессов.

Гость (01/06/2014 21:35)   
os.urandom в unix-системах берет случайные данные из /dev/urandom, в винде – CryptGenRandom(). Пост-обработка физических процессов недоступна большинству пользователей.
— Anton_Tsyganenko (01/06/2014 21:37)   
Кстати, если ключ не очень случайный, сжатие поможет?
Гость (01/06/2014 21:50)   
Нет:

C[link3]ontrary to a view in the I&C community, compression does not render data random, as can be seen from the case of votes, where the message space has very low entropy.


Да даже если б у вас стоял QRNG[link4], дальше-то что? Нужно, чтоб одна и та же гамма была на обоих концах связи, а как вы её туда доставите? Добро пожаловать в QKD.
— Anton_Tsyganenko (01/06/2014 22:12)   
Нужно, чтоб одна и та же гамма была на обоих концах связи, а как вы её туда доставите? Добро пожаловать в QKD.

Передать можно при личной встрече или в сейф-пакете. Только не надо говорить, что при личной встрече можно сразу передать и данные – передача ключа может осуществляться тогда, когда данных еще нет.
Гость (01/06/2014 22:43)   

Ну, если только так...
— ZAS (01/06/2014 22:59)   
os.urandom в unix-системах берет случайные данные из /dev/urandom, в винде – CryptGenRandom().


Использование системной функции создает удобную универсальную лазейку. Достаточно перехватить вызов, и сразу видно сами случайные числа, а также какому процессу, в какой момент и в какой точке они понадобились.

http://www.zas-comm.ru
— Anton_Tsyganenko (01/06/2014 23:18)   
Использование системной функции создает удобную универсальную лазейку. Достаточно перехватить вызов, и сразу видно сами случайные числа, а также какому процессу, в какой момент и в какой точке они понадобились.

Понятно, что если в системе есть закладки, трояны, кейлогеры и т.д., то каким бы не был хорошим алгоритм, он не спасет. Даже если получать случайные числа другим образом, троян может сделать дамп памяти. Предполагается, что используемая система надежна и в ваш монитор посторонние не смотрят.
— SATtva (02/06/2014 09:29)   
Вообще, реализация OTP (даже если это именно OTP, а не непонятно что, как в данном случае) — это что-то типа hello world: столь же элементарно, сколь и бессмысленно. То есть как абстрактная задача сойдёт, но выкладывать это в паблик по меньшей мере пошло.
— Anton_Tsyganenko (02/06/2014 13:15)   
Да, изначально было just for fun. Хотя чем проще алгоритм и меньше программа, тем проще ее проверить. Понятно, что пока есть pgp, она вряд-ли будет пользоваться популярностью, но квантовый суперкомпютер рано или поздно будет сделан, и тогда расшифровка pgp-сообщений не составит труда.
В данном случае это OTP, хоть там и куча отсебятины, ключи используются только один раз.
— SATtva (02/06/2014 13:44)   
unknown выше написал, в чём главная проблема: источник материала для ключей — ГПСЧ, что превращает Вашу реализацию в тыкву. Хотя бы берите энтропию из /dev/random — даже с учётом всех его проблем и блокируемости чтения, такой вариант будет выглядеть более вменяемо.
— Anton_Tsyganenko (02/06/2014 16:32)   
Можете объяснить разницу между /dev/random и /dev/urandom? А если для генерации ключей 2 раза использовать os.urandom, а потом xor-ить их между собой?
— unknown (02/06/2014 16:56)   
Будет XOR соседних учатков гаммы, развёрнутой из одного и того же фрагмента энтропии, условного ключа.
— SATtva (02/06/2014 16:57)   
/dev/random накапливает "чистую" энтропию от физических источников случайности, имеющихся в конкретной системе (от традиционных, типа тайминга нажатия клавиш, дельт перемещений мыши, задержек чтения с HDD из-за турбулентных процессов, и до более специфических, типа аппаратных ГСЧ в интеловских процессорах), иными словами, это генератор случайных чисел (ГСЧ) в общепринятом понимании, который только и может использоваться для выработки одноразовых блокнотов, поскольку в этом случае их стойкость является безусловной.

/dev/urandom, напротив, не получает энтропию непосредственно из источников случайности. Это обычный генератор псевдослучайных последовательностей, периодически ресидируемый от ввода /dev/random. Таким образом, стойкость полученных из него одноразовых блокнотов будет опираться на стойкость самого генератора и используемых в его основе криптопримитивов, которые могут быть уязвимы к различным классам атак (в том числе и помянутому Вами КК). Нельзя для OTP использовать PRNG, иначе теряется весь смысл OTP. С тем же успехом можете юзать обычный блочный шифр.


Без разницы.
— Anton_Tsyganenko (02/06/2014 17:07)   
Хорошо, попробую заменить /dev/urandom на /dev/random, только как быть с виндой?
— SATtva (02/06/2014 17:30)   
С виндой лучше не быть никак, но используйте там хотя бы Crypto.Random (Fortuna RNG) из pycrypto.
— Anton_Tsyganenko (02/06/2014 17:33)   
Все-таки тыква получается, попытался сделать генератор, использующий /dev/random, так он несколько минут 100 байт генерировал. На такое заменять не получится.
— SATtva (02/06/2014 18:00)   

/dev/random блокирует чтение, если в нём недостаточно энтропии. Подключайте быстрые источники энтропии (timer_entropyd, audio_entropyd, haveged[link5]), а не компрометируйте требования к генератору. Медленное поступление энтропии — проблема пользователя, а не OTP.
— Anton_Tsyganenko (02/06/2014 18:06)   
Хотел бы уточнить, я правильно понимаю, что нужен Криптографически стойкий генератор псевдослучайных чисел[link6]
— SATtva (02/06/2014 18:45)   
Нет, нужен генератор истинно случайных чисел. Ничего "псевдо" для OTP не годится.
Гость (02/06/2014 20:15)   
Вообще, по поводу использования urandom вместо random есть естественно возникающие вопросы: раз всё разворачивается с одного seed'а, значит, если я сгенерил несколько ключей для шифрования, не надо брутфорсить их по отдельности — вместо этого достаточно брутфорсить seed. Затем, если противник получил кусок трафика разных типов и знает, что в этот же момент я генерировал ключи, то ему, опять же, не надо по отдельности ломать всё из перечисленных (шифрование ssh, tor, LUKS) — вместо этого достаточно брутфорсить всё тот же единственный seed, который был использованы в данный момент.

Есть некоторая надежда на техническую сложность — противник не всегда знает, когда сидируется urandom, и потому не знает, ключи каких процессов связаны между собой одним seed'ом, но чисто теоретически уязвимость остаётся. Например, в ситуации, когда злонамеренный процесс запущен в той же ОС, что и критичные к безопасности, это может играть роль: зная, что другие процессы черпают энтропию из urandom, зловред тоже оттуда извлекает какой-то кусок, и теперь он знает, что всё, что наполучали втечение некоторого промежутка другие процессы, покрывается одним seed'ом. В некотором смысле из-за этого получается, что один процесс может знать, какие случайные данные получил из пула другой процесс (modulo 128-битная стойкость или какой там размер seed'а?).

Кстати, есть ли возможность более частого сидирования urandom? Можно ли сделать так, чтоб urandom сидировался (осеменялся) сразу же, как только в random появляется достаточное количество энтропии, а не так как сейчас (кажется, не чаще, чем раз в несколько минут?). Или это чем-то плохо для безопасности?
— Anton_Tsyganenko (02/06/2014 21:12)   
Вот еще идея для генерации ключей: пользователь создает папку и кладет туда кучу разных файлов: фотографий, видео, записей с диктофона, текстов, желательно – собственного производства. Затем программа читает содержимое каждого их них, складывает все в общую кучу и разбивает на куски длиной, равной количеству необходимых случайных данных (один кусок может получиться короче). потом xor-ит их между собой и результат xor-ит c данными, полученными из urandom.
— SATtva (02/06/2014 21:23)   
Вы начинаете изобретать RNG, это дурной знак. :)
— Anton_Tsyganenko (02/06/2014 21:28)   
Почему же сразу дурной знак? Если /dev/random слишком медленный, /dev/urandom не годится, а аппаратный ГСЧ на основе радиоактивного распада есть не у всех, то почему бы не изобрести велосипед RNG?
— onix_ (02/06/2014 21:46)   
Если в системе, есть выход в интернет, может проще собирать энтропию с различных сайтов с часто изменяющейся 1-й страничкой, тк: новостные, биржевые, погодных и др.

типа md5("http://site1.xxx") ^ md5("http://site2.xxx") ^ ...
Гость (02/06/2014 22:03)   
facepalm.jpg
— Anton_Tsyganenko (02/06/2014 22:03)   
Во первых, с помощью списка сайтов можно получить немного энтропии.
Во вторых, вы где собираетесь держать список сайтов? если вшить в генератор, то злоумышленник тоже сможет получить этот-же результат
— Anton_Tsyganenko (03/06/2014 13:53)   
Сделал такой RNG, как описывал. По идее, если ему скормить несколько файлов, таких как фотографии, видео, аудио, то должно быть достаточно надежно. Какие у него могут быть уязвимости?
— SATtva (03/06/2014 14:04)   
Такие, что противник может постфактум получить эти данные и восстановить состояние генератора. Надёжные источники случайности трансиентны.
— Anton_Tsyganenko (03/06/2014 14:34)   
противник может постфактум получить эти данные

После генерации данные удаляются.
— SATtva (03/06/2014 14:52)   
Удаляются откуда? С диска? You gotta be kidding.
— Anton_Tsyganenko (03/06/2014 15:45)   
Да, удаляются с диска, просто удаляются, не затираясь, скорее для того, чтобы пользователь не использовал их 2 раз для генерации ключей.

Ссылки
[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/Криптографически_стойкий_генератор_псевдослучайных_чисел