Комментарии 60
Число секунд с начала эпохи дает нам 32 бита энтропии
Нет. Значительно меньше.
Known-plaintext attack: приведите сообщение (хотя бы 128 байт) и зашифрованное сообщение и посмотрим, получится ли у нас восстановить ключ.
(Если этот режим атаки кажется неправдоподобным, приведите первые 128 байт сообщения и зашифрованное сообщение целиком, и посмотрим, получится ли восстановить вторую половину.)
Это отличная мысль!
$ hd /tmp/in
00000000 4e 61 74 75 72 65 27 73 20 66 69 72 73 74 20 67 |Nature's first g|
00000010 72 65 65 6e 20 69 73 20 67 6f 6c 64 2c 0a 48 65 |reen is gold,.He|
00000020 72 20 68 61 72 64 65 73 74 20 68 75 65 20 74 6f |r hardest hue to|
00000030 20 68 6f 6c 64 2e 0a 48 65 72 20 65 61 72 6c 79 | hold..Her early|
00000040 20 6c 65 61 66 27 73 20 61 20 66 6c 6f 77 65 72 | leaf's a flower|
00000050 3b 0a 42 75 74 20 6f 6e 6c 79 20 73 6f 20 61 6e |;.But only so an|
00000060 20 68 6f 75 72 2e 0a 54 68 65 6e 20 6c 65 61 66 | hour..Then leaf|
00000070 20 73 75 62 73 69 64 65 73 20 74 6f 20 6c 65 61 | subsides to lea|
00000080 66 2e 0a 53 6f 20 45 64 65 6e 20 73 61 6e 6b 20 |f..So Eden sank |
00000090 74 6f 20 67 72 69 65 66 2c 0a 53 6f 20 64 61 77 |to grief,.So daw|
000000a0 6e 20 67 6f 65 73 20 64 6f 77 6e 20 74 6f 20 64 |n goes down to d|
000000b0 61 79 2e 0a 4e 6f 74 68 69 6e 67 20 67 6f 6c 64 |ay..Nothing gold|
000000c0 20 63 61 6e 20 73 74 61 79 2e 0a | can stay..|
000000cb
$ PASSWORD=... ./crypt-pcg -i /tmp/in -o /tmp/out -e && hd /tmp/out
00000000 3b bc f8 ee e8 ea 67 e0 54 af d5 ca ef 30 2f ba |;.....g.T....0/.|
00000010 a0 74 1d 3e d0 c2 04 98 03 8c 87 8d 72 cf d0 95 |.t.>........r...|
00000020 97 d5 6f a1 c9 08 1f fa c2 c7 ed 37 e9 90 45 ab |..o........7..E.|
00000030 7c aa b1 2e 96 e5 f5 ad 0c be 62 8f 79 1a 7b 6a ||.........b.y.{j|
00000040 ee 9c 2c 16 ed 20 aa b7 d5 74 9e 0c 42 b3 e1 97 |..,.. ...t..B...|
00000050 50 77 78 11 fc f2 94 58 2c 5f b2 e8 45 83 3a 65 |Pwx....X,_..E.:e|
00000060 17 50 fe 75 20 23 1b 1a d1 68 3d 6f 89 7a f8 a5 |.P.u #...h=o.z..|
00000070 c6 90 4a 35 84 33 14 44 9a d4 21 a0 14 c8 bf 89 |..J5.3.D..!.....|
00000080 20 50 40 5c 25 26 8e f0 c2 33 40 00 d8 63 a1 be | P@\%&...3@..c..|
00000090 8a ba 13 ad 82 97 0a 32 0a d1 34 36 d1 97 be 04 |.......2..46....|
000000a0 75 e1 09 12 f6 04 0a 36 8e 55 0c 0f 91 d5 65 f5 |u......6.U....e.|
000000b0 5f 42 c6 f4 05 b4 ea 9e 7b f6 28 3d aa 20 5f c5 |_B......{.(=. _.|
000000c0 7b e5 d7 ba 66 42 13 17 79 f4 fa 5f 70 ce 15 60 |{...fB..y.._p..`|
000000d0 0f 37 6d bf b4 94 5e 39 29 7b 59 5d 6f 80 57 56 |.7m...^9){Y]o.WV|
000000e0 3e 39 02 85 0b c9 d1 d6 0a 6b ce c3 6d 84 2d a5 |>9.......k..m.-.|
000000f0 25 da 2b 72 ec 68 cf cd d8 a7 5d 89 36 b0 8a a1 |%.+r.h....].6...|
00000100 36 b7 16 d5 27 75 f7 |6...'u.|
00000107
$ PASSWORD=... ./crypt-pcg -i /tmp/out -o /tmp/dec -d && hd /tmp/dec
00000000 4e 61 74 75 72 65 27 73 20 66 69 72 73 74 20 67 |Nature's first g|
00000010 72 65 65 6e 20 69 73 20 67 6f 6c 64 2c 0a 48 65 |reen is gold,.He|
00000020 72 20 68 61 72 64 65 73 74 20 68 75 65 20 74 6f |r hardest hue to|
00000030 20 68 6f 6c 64 2e 0a 48 65 72 20 65 61 72 6c 79 | hold..Her early|
00000040 20 6c 65 61 66 27 73 20 61 20 66 6c 6f 77 65 72 | leaf's a flower|
00000050 3b 0a 42 75 74 20 6f 6e 6c 79 20 73 6f 20 61 6e |;.But only so an|
00000060 20 68 6f 75 72 2e 0a 54 68 65 6e 20 6c 65 61 66 | hour..Then leaf|
00000070 20 73 75 62 73 69 64 65 73 20 74 6f 20 6c 65 61 | subsides to lea|
00000080 66 2e 0a 53 6f 20 45 64 65 6e 20 73 61 6e 6b 20 |f..So Eden sank |
00000090 74 6f 20 67 72 69 65 66 2c 0a 53 6f 20 64 61 77 |to grief,.So daw|
000000a0 6e 20 67 6f 65 73 20 64 6f 77 6e 20 74 6f 20 64 |n goes down to d|
000000b0 61 79 2e 0a 4e 6f 74 68 69 6e 67 20 67 6f 6c 64 |ay..Nothing gold|
000000c0 20 63 61 6e 20 73 74 61 79 2e 0a | can stay..|
000000cb
$
И номер процесса дает реально всего несколько бит.
И микросекунды дают не более единиц бит, потому что генератор шифрует данные, получая последовательные метки времени.
Было бы неплохо нарисовать функциональную схему шифратора.
Вы начальное состояние передаёте открыто. Для преодоления этого недостатка можно использовать двойное шифрование. В этом случае внутреннее шифрование - то, что Вы описали, а внешнее - надо разрабатывать. Внешнее шифрование закроет параметры внутреннего и, заодно, шифр-текст.
В библиотеке std:: есть способ получить энтропию, который комбинирует возможности платформы (не только системное время): std::random_device{}.
То, что я передаю открыто, не состояние генератора, а затравка, из которой при помощи ключа формируется состояние генератора.
Это начальное состояние, из которого формируется начальное состояние генератора. Фактически это некий seed в дополнение к ключу. Раскрывать seed тоже не очень хорошо. Зависит от размеров ключа и сида.
seed в данном случае 64 бита. Ключ - зависит только от вас. Можно попросить вас раскрыть мысль какие риски несет открытый seed?
Смысл сида - увеличить неопределенность (энтропию), то есть усложнить жизнь атакующему. В идеале итоговая энтропия шифра равна сумме энтропий ключа и сида. Если сид открыт, то это равнозначно обнулению его энтропии и уменьшению итоговой энтропии.
При неизвестном сиде атакующий должен его перебирать (помимо перебора ключа), а при известном - нет. Всё довольно таки тривиально.
Мне кажется вы не совсем правы. Если вы посмотрите на мехнизм парольной авторизации в юниксе вы увидите, что в /etc/shadow хранится хеш пароля и соль, котоая была использована для генерации этого хеша. Я всего лишь воспользовался тем же подходом.
У Вас не механизм парольной авторизации, в том-то и дело. Для хеширования паролей это нормально, потому что идеальная хэш-функция необратима. В вашем случае это шифрование, которое естественно обратимо.
В моем коде seed преобразуется при помощи ключа шифрования в состояние генератора случайных чисел. Так что знание seed при разумной длине ключа не помогает взлому. Особенно с учтом того, что добавление одного символа к ключу шифрования удваивает время инициализации генератора.
Я говорил, естественно, об идеальном преобразовании ключа и сида в начальное состояние ГСЧ. С Вашим надо ещё разбираться. А так да, при идеальном преобразовании и при размере ключа много большем размера сида, открытостью сида можно пренебречь. Но тогда зачем он вообще нужен?.. Можно просто инициализировать генератор ключом, прогреть его и этого достаточно. Правда ещё зависит от качества генератора... В общем, это комплексное дело писать свою криптографию...
Если не будет сида, то как обеспечить разные случайные последовательности при использовании одного и того же ключа?
Да, нужен сид, но его надо прикрывать внешним шифрованием, которое должно отличаться от внутреннего по своей природе.
как бы вы предложили поменять код?
Дело ваше, тем более код. Ладно бы на блок схеме чего поменять, а тут код... Нет уж)
У меня есть проект парольного менеджера (смотри в профиле гитхаб проектAllPass), там есть блок схема шифратора. Но там я заморочился по полной и с нуля, решив выжать из регистров сдвига LFSR по максимуму тем самым реабилитируя их). По отдельности эти регистры слабы, поэтому делал разные навороты.
Если вывести за скобки открытй сид есть ли у вас замечания по остальной логике?
В детали я не залезал, поэтому замечаний нет)
Если у вас будет время был бы вам очень благодарен если бы вы оценили детали :).
За криптоанализ платят деньги, и это коллективная работа. Я не криптоаналитик, просто немного разбираюсь в криптографии.
А вам вообще зачем это? Какой то реальный проект? Если нет, то никто и не возьмётся за детальный анализ...
Может конечно будет время, но не гарантирую. Я там особенно нового и оригинального ничего не вижу
По странной причине поиск на гитхабе не выдал мне этот проект, пришлось посмотреть ссылки из других статей профиля. Оставлю тут ссылку чтобы, возможно кому-то сэкономить время https://github.com/nawww83/AllPass
Не сказывается ли на качестве шифрования 64 битное переполнение в state[0] = oldstate * 6364136223846793005ULL + (state[1]|1); ?
Насколько безопасен унарный минус для беззнакового целого ((-rot)) без указания целевой платформы, используемого компилятора, и версии стандарта?
В данном случае я доверяю автору алгоритма. Вот статья, описывающая детали реализации: https://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf Вот кртикка алгоритма от автора главного кокурента: https://pcg.di.unimi.it/pcg.php А вот обсуждение на реддите: https://www.reddit.com/r/programming/comments/8jbkgy/the_wrapup_on_pcg_generators/
Для беззнакового фиксированной ширины безопасно.
если начальное состояние 64 бита, то за счет атаки дней рождения через сотню миллионов зашифрованных одним ключом сообщений мы с шансом 1% найдем два с одинаковым состоянием и поксорим. А через пять миллиардов - найдем с вероятностью 50%.
И это считая что там честные 64 бита - я правильно понял что оно генерируется умножением случайных чисел, т.е. младшие биты будут с большей вероятностью нулевыми? Если один из сомножителей четный то и произведение будет четным, ну и так далее.
Прошу прощения за путаницу в названиях, надо переименовать. То, что в тексте называется "начальное состояние" это seed, из которого при помощи ключа шифрования строится начальное состояние генератора случайных чисел. Состояние генератора 256 бит, так что атака дней рождений скорее всего не будет эффективной.
если ключ одинаковый и seed (начальное состояние) одинаковое, то и 256-битное состояние гсч будет одинаковым, разве нет?
Вы правы, состояние будет одинаковым. Понять, что seed одинаков в исходной реализации легко. Но я добавил шифрование сида по совету sci_nov. Т.е. если будет 2 сообщения, с одинаковым зашифрованным seed, это не является гарантией, что seed и ключ у обоих сообщений одинаков. Правильно ли я вас понимаю, что вы предлагаете увеличить размер сида?
да, 64 бита для nonce считается мало если он случайный а не последовательно увеличивается. И конечно он должен получаться из нормального источника - что-то типа
On BSD-based systems and macOS/Darwin, it uses arc4random, on Linux getrandom, on Windows RtlGenRandom, and falls back to reading from /dev/urandom on UNIX systems.
потому что брать не очень случайные числа да еще и перемножать - решение мягко говоря так себе.
А так - останется еще заменить pcg32 на ChaCha20 (пгсч с исследованной криптостойкостью), добавить HMAC чтоб отличать измененные файлы (если злоумышленник догадывается о содержимом файла то сейчас он может даже не зная ключа изменить в нем байты так чтобы получить в нем требуемое содержимое) и получится почти что monocypher.
Понял, спасибо.
Детали работы pcg32 раскрыты вот в этой статье: https://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf Можете ли вы выделить явные недостатки pcg32 по сравнению с ChaCha20?
Про PCG32 я знаю. Да что там, я сам когда-то сделал PR и теперь это дефолтный рандом в языке Crystal. Недостаток только в том что автор не позиционирует его как криптостойкий, поэтому по-серьезному его не исследовали. Несколько лет назад была опубликована атака на него (https://hal.science/hal-02700791), после чего насколько я помню автор опубликовал PCG с другой хеш-функцией.
Подумав над вашими комментариями я переключился на функцию clock_gettime и теперь с ее помощью генерирую 256 бит состояния: https://github.com/kt97679/misc/commit/4f1157c15cd0d5df9bb8163e7c8ea1c1d80e7836
Вы совершенно правы, и я долго думал, что еще можно использовать в качестве источника случайных данных для seed, но так ничего и не придумал. Какой рандом от ОС вы предлагаете использовать? На юникс подобных ОС можно прочитать /dev/urandom, но как тогда быть на Windows?
Спасибо за добрые слова :)!
У меня основная ос - линукс. Windows вообще в доступе нет. Так что увы MSDN мне особо не поможет. Но буду думать дальше, возможно на базе позикса можно что-то будет придумать.
Про безопасников и их театр - раделяю вашу боль, тоже имел очень странный опыт взаимодействия.
А чем std random_device не устраивает?
Мой код на си, там я могу использовать long random(void) из stdlib. Но для инициализации генератора надо использовать void srandom(unsigned int seed) при том, что как минимум на моей системе sizeof(unsigned int) это 4. Таким образом сид оказывается 32 бита, что на мой взгляд мало.
На Windows использовать WSL :)
Посмотрел репозиторий. Нарисовать диаграмму шифрования очень стоит. Будет легче анализировать уязвимости стороннему человеку, да и Вам тоже
Добавил: https://github.com/kt97679/misc/blob/master/crypt/diagram.txt Пожалуйста дайте знать если что-то надо уточнить.
У Вас система ограничена тем, что фактически это просто гаммирование. Можно хотя бы добавить нелинейность: делать циклический сдвиг входного байта перед его ксором. При этом величина сдвига будет зависеть от байта гаммы (по модулю 8).
Но лучше всё-таки двойное гаммирование: первое обычное, второе - с циклическим сдвигом, потому что при сообщении из нулей на выходе будет голая гамма. Первое гаммирование при этом фактически будет неким скремблером, защищающим от детерминированных данных (известных паттернов).
Это отличный совет, спасибо! Добавлю в ближайшее время.
Добавил: https://github.com/kt97679/misc/commit/03df053af10e615c606a360b0bef03abb02d77f6 Еще раз огромное спасибо!
Пишем собственное симметричное шифрование