Более того, если из приложения выйти не нажатием на back много раз, а кнопкой home, то оно продолжает в фоне что то делать, пожирая процента 4 CPU, — не много, но оно этого делами не должно вообще.
Вообще по хорошему им нужно разделить раздел My Pebble и маркет в два разных приложения.
ЗЗЫ — а вообще, самый главный урок, которому учат профессиональные криптографы: никогда не изобретайте криптографию самостоятельно. С вероятностью 99.9999999% будут сделаны ошибки, ломающие всю защиту. (При этом для профессоров уважаемых эта вероятность будет все равно на уровне 99.9%).
Тут стоит откомментировать, что похоже у систем уравнений существует более чем одно решение, удовлетворяющее всем условиям, и по хорошему нужно брать, искать все решения для нескольких из систем (на разных блоках исходных данных) и находить потом пересечение между множествами решений что-бы найти «самую универсальную мастер матрицу». Мне все это было влом делать, мой код печатает первое попавшееся решение, но проходится последовательно по блокам из 9-ти 2х байтных ushort-ов, и потом я глазками смотрел — каких решений больше всего, то предположительно и самое-самое, — угодал с первой попытки :) (Как я сказал, деление довольно медленное, так что я не стал дожидатся даже окончания обработки файлов).
Так что что-бы сделать «универсальную ломалку» — нужно код еще дорабатывать, но у меня такой задачи не было.
По поводу деления на кольце, сейчас оно сделано очень тупо:
for (int i=0; i<TMAX; i++)
{
if ( ((det0+TMAX*i) % det) == 0)
{
T result = (det0+TMAX*i) / det;
....
Такой подход — довольно медленный, но работает для 16-битных чисел. Для 64-битных чисел — я припас, на всякий случай, уже быстрый вариант — функция ring_div (делит a на b по модулю 2^nbits), — использует расширеный алгоритм Евклида, но находит только одно из возможных решений. Впрочем если есть одно, то все остальные можно найти довольно быстро, добавляя к предыдущему результату 2^nbits и потом вычитая несколько раз b (т.е. то, на что делим), пока снова не получится число влезающее в nbits бита, и потом продолжаем вычитать, пока оно не станет отрицательным. Но т.к. оно оказалось 16-ти битным — решил не усложнять себе жизнь. (Как работает алгоритм евклида — я могу рассказать на пальцах, но как работает та функция — объяснить не смогу — я нашел готовый код в инете, могу сказать — работает она мгновенно, по сравнению с тем, что у меня для 16-ти бит).
Да, отсюда-же можно и оценить, сколько числел в итоге получается у операции деления — по разнице между наименьшим числом вида b*N превышающим 2^nbits и 2^nbits, — если эта разница очень маленькая — чисел будет много, точнее говоря чисел будет примерно 2^nbits / (b*N — 2^nbits), — так что можно сразу отсекать неудачные системы уравнений и рассматривать только те, где решений меньше чем заданное количество. (И да, я там использовал тип __int128_t, — это расширение gcc, не уверен что этот тип есть на других платформах, но для решения 16-ти битного случая — не думаю что он нужен).
Вообще, по поводу решений этих систем — у меня нет уверенности, что я делаю это самым оптимальным образом, возможно есть какой-то математический трюк, позволяющий моментально найти нужную, отсеив все побочные решения. Так что не уверен, что расширение разрябности до 64 или даже 128 бит реально может помочь. Равно как и использование матриц вращения больших размерностей. (Но вообще — я не криптограф по образованию, у меня относительно поверхностные знания криптографии, — я думаю профессиональные криптоаналитики смогли бы ответить куда развернутей, но — их время ужасно дорого ;) )
А что касается доверять профессорам — так я уже писал, в мире криптографии нельзя доверять одному человеку, каким бы авторитетом он не был. Доверять можно только тем случаям, когда код или алгоритмы были выверены сотнями исследователей и разработчиков (как например с AES), и даже в подобных случаях — порой находятся такие уязвимости, которые ломают всю безопасность на корню (как например 2 раза случилось с OpenSSL за последние месяцы).
В общем виде — подход будет совсем другой, работать нужно с отдельными битами, соответственно даже для uchar вместо 9 неизвестных будет 24*24=576 (правда бинарных — каждая будет либо 1 либо 0), и соответственно нужна система из 576 уравнений. Это все решаемо, но кодить и отлаживать — тот ещё гемор. Про подсчет детерминанта я уже писал — пожалуй самая невеселая часть.
Код я использовал практически тот же, что и выложил, с небольшой модификацией: деление на кольце по модулю часто имеет более одного результата, но далеко не все они решают исходную систему уравнений, так что я добавил перебор среди возможных решений, что бы оно находило те значения, которые «подходят». При этом перебрать долго не приходится: если я вижу, что вариантов слишком много, я просто перехожу к следующему блоку. Число вариантов варьировалось от 64 до 16000^3, так что я выбирал только те данные, где 64 или аналогично возможных решений, перебирается это мгновенно.
Возможно если бы вы использовали 64х битные типы — мне пришлось бы подождать пару часов, пока среди миллионов возможных решений найдётся нужное :) но надо сказать, что сама переборная сложность тут не велика, т.к. по сути тут не система из 9 уравнений, а три независимых системы по 3, соответственно перебирать нужно не девятую степень а третью. В случае решения в общем виде, кстати, такой проблемы быть не должно, там детерминант будет либо 0 (вырожденная система не имеющая решения), либо 1, а деление на 1 — всегда однозначная операция :)
Во первых, есть разница между «можно» и я могу. Профессиональные криптографы справятся с этой задачей на раз, а я лишь собирался показать, что ваш алгоритм легко может быть взломан в частном случае, когда известно что у него внутри (впрочем криптогоафы никогда в серьез не занимаются случаями, когда реализация не известна).
Бонально мне лень реализовывать такие вещи, как например подсчет детерминанта матрицы произвольной размерности — я не вижу смысла тратить столько времени на то, что бы доказать не пойми кому простые азбучные истины, изучаемые на первых страницах любого учебника по криптоанализу.
Вы издеваетесь??? Откуда я знаю что значит в вашем понимании «чтоб правильно работало», если я не знаю, в каком виде вы сериализуете например 56-ти битные числа в файл??
Существует более одного способа сериализовать подобное. И я не собираюсь угадывать формат, как я вам писал в самом начале.
1) Вы написали «Чтение файла и запись в файл назад идет через Qt,… можете посмотреть как реализовано»,
а не то, что оно однозначно там в Big Endian
2) Каким образом вы пишите 56-битные числа на диск, при N==7??? Вы можете внятно ответить на этот вопрос? Я понимаю, что в случае N=7, скорее всего работа идет с 64-битным числом, которое обрезается операцией &MASK. Но как вы его потом записываете на диск, вы же сохраняете только 7 байт из 8-ми. Вот опишите этот момент подробно.
ЭЭЭ, т.е. вы сами не знаете, как оно в итоге сериализуется, а я должен угадывать и/или ковыряться в исходниках библиотеки, насчитывающей не один десяток МБ исходников на C++????
2) — каким образом тогда вы работаете с, например, 56-битными числами? Или в формуле 24*N, N не может быть равным 7-ми?
Без подобной информации что-либо делать мне — безсмысленно. Как я сказал — я согласен решать задачу крипто-анализа, а не угадывания вашего формата файла.
Раз уж вы отказываетесь привести подробное техническое описание формата, как я вас просил, буду выуживать по деталям.
Перед тем, как я начал тратить время, ответте на вот эти вопросы, пожалуйста:
1) В каком виде сериализуются N-битные целые числа? Сохраняются ли они как Big Endian, Little Endian, или как-то еще?
2) В случае когда например N=7, т.е. алгоритм работает с группами из трех чисел, каждое по 56 бит, — можете поточнее описать, как эти 56-ти битные числа, в каком формате, сохраняются в файл?
P.S. Я так-же надеюсь вы не мухлевали, и как и обговорено было, просто N раз прогнали один и тот-же алгоритм, каждый раз с новым ключем. Т.е. не примешивая никаких других операций, вроде XOR-ов, применения следующей итерации с небольшим смещением, итп.
ладно, не буду с вами в полемику вступать. Однако я вас спрашивал про детальный формат файла, вы сказали — «как тот kernel», однако из исходных файлов я вижу что это не так — вы указали, что нет никаких заголовков, а они есть.
Не буду спорить, соглашусь на ваши условия, но предполагаю что речь идет о целочисленной арифметике, т.е. что вы не используете float/double-ов. Как я уже писал выше, подобные вещи могут внести нелинейность, но если заранее знать, что оно там есть — от нее можно избавится. Посколько вы не указали ничего такого, и речь о линейности — предполагаем что float-ов не используется, чисто целочисленная арифметика. (Опять-же, в реальном мире детали крипто-алгоритма всегда достоверно известны заранее, никто не пытается строить безопасность основываясь на том, что кто-то не знает деталей реализации — подобные попытки были в прошлом, и показали себя как наименее защищенные системы).
Что про заголовок — впрочем их исходных файлов и так понятно, докуда он.
<<Вообще, если вы предоставите сам код, кодирующий / декодирующий, набор файлов (оригинал + шифрованное), то я берусь попробовать восстановить ключи (которых вы мне не сообщите).
Если исходники предоставить не можете — нужна грамотная техническая, подробная, спецификация, на все форматы. Того, что вы описали — недостаточно.
Конечно, в общем случае — можно все проанализировать и без подобных деталей, но сейчас задача стоит сломать шифрование, а не угодать формат файла. >>
После чего мы договорились о формате файла — «как вы исходниках, что для ядра OpenCL», мы согласились на эти правила игры. Однако вы решили их поменять, после того, как пари было уже заключено.
Повторюсь: без предоставления мне детальной технической информации об алгоритме, я не собираюсь тратить свое время на то, что-бы заниматься угадыванием формата. Криптоанализ не занимается решением подобных вопросов. Этим занимаются хакеры, которые в два счета стащат у вас все исходники, если кому-то будет интересен ваш «алгоритм» ;)
Вообще, конечно можно проанализировать все это и в совсем общем случае, ни зная об алгоритме вообще ничего, используя различные инструменты криптоанализа, однако изначально задача об этом не шла, т.к. повторю свои слова еще раз:
<<Конечно, в общем случае — можно все проанализировать и без подобных деталей, но сейчас задача стоит сломать шифрование, а не угодать формат файла. >>
Так что я возвращаюсь к своим исходным условиям: либо исходники, либо детальное описание формата.
> Прошу заметить что при условно реальном случае KPCA вам никто предоставлять размер блока не будет.
потому что он заранее известен, т.к. известен используемый алгоритм, который, в отличии от вашей поделки, описал до мельчайших деталей, а не только размер блока.
Речь идет о том, что формат заранее известен. Как минимум размер блока. Это очевидное любому криптографу предположение, т.к. криптография занимается анализом заранее известных алгоритмов, а не «я тут накодил, что имеено не скажу, вы сами догадайтесь». Security by obscurity — это не безопасность.
ЗЫ, вот небольшая наброска, как это собственно все будет работать: pastebin.com/fNhPKFgf (код ужасный по стилю, конечно, в реальной жизни я так не напишу, но тут я торопился просто)
поскольку я знаю заранее, что там матрицы 3x3, я не буду опускатся до битового уровня — лишняя головная боль :)
А так, пример демонстрирует, как можно восстановить исходный ключ по 3м парам сообщений.
Правда есть ограничение на эти 3 пары — детерменант матрицы составленной из нешифрованных сообщений не должен быть нулевой, т.е. между векторами исходных сообщений не должно быть линейной зависимости. Что впрочем на случайных данных — практически всегда выполняется, а если где и не выполняется — можно просто взять другой датасет.
Вообще по хорошему им нужно разделить раздел My Pebble и маркет в два разных приложения.
dl.dropboxusercontent.com/u/25074445/code/solve.cpp
И декодирующая утилитка:
dl.dropboxusercontent.com/u/25074445/code/decode.cpp
Тут стоит откомментировать, что похоже у систем уравнений существует более чем одно решение, удовлетворяющее всем условиям, и по хорошему нужно брать, искать все решения для нескольких из систем (на разных блоках исходных данных) и находить потом пересечение между множествами решений что-бы найти «самую универсальную мастер матрицу». Мне все это было влом делать, мой код печатает первое попавшееся решение, но проходится последовательно по блокам из 9-ти 2х байтных ushort-ов, и потом я глазками смотрел — каких решений больше всего, то предположительно и самое-самое, — угодал с первой попытки :) (Как я сказал, деление довольно медленное, так что я не стал дожидатся даже окончания обработки файлов).
Так что что-бы сделать «универсальную ломалку» — нужно код еще дорабатывать, но у меня такой задачи не было.
По поводу деления на кольце, сейчас оно сделано очень тупо:
Такой подход — довольно медленный, но работает для 16-битных чисел. Для 64-битных чисел — я припас, на всякий случай, уже быстрый вариант — функция ring_div (делит a на b по модулю 2^nbits), — использует расширеный алгоритм Евклида, но находит только одно из возможных решений. Впрочем если есть одно, то все остальные можно найти довольно быстро, добавляя к предыдущему результату 2^nbits и потом вычитая несколько раз b (т.е. то, на что делим), пока снова не получится число влезающее в nbits бита, и потом продолжаем вычитать, пока оно не станет отрицательным. Но т.к. оно оказалось 16-ти битным — решил не усложнять себе жизнь. (Как работает алгоритм евклида — я могу рассказать на пальцах, но как работает та функция — объяснить не смогу — я нашел готовый код в инете, могу сказать — работает она мгновенно, по сравнению с тем, что у меня для 16-ти бит).
Да, отсюда-же можно и оценить, сколько числел в итоге получается у операции деления — по разнице между наименьшим числом вида b*N превышающим 2^nbits и 2^nbits, — если эта разница очень маленькая — чисел будет много, точнее говоря чисел будет примерно 2^nbits / (b*N — 2^nbits), — так что можно сразу отсекать неудачные системы уравнений и рассматривать только те, где решений меньше чем заданное количество. (И да, я там использовал тип __int128_t, — это расширение gcc, не уверен что этот тип есть на других платформах, но для решения 16-ти битного случая — не думаю что он нужен).
Вообще, по поводу решений этих систем — у меня нет уверенности, что я делаю это самым оптимальным образом, возможно есть какой-то математический трюк, позволяющий моментально найти нужную, отсеив все побочные решения. Так что не уверен, что расширение разрябности до 64 или даже 128 бит реально может помочь. Равно как и использование матриц вращения больших размерностей. (Но вообще — я не криптограф по образованию, у меня относительно поверхностные знания криптографии, — я думаю профессиональные криптоаналитики смогли бы ответить куда развернутей, но — их время ужасно дорого ;) )
А что касается доверять профессорам — так я уже писал, в мире криптографии нельзя доверять одному человеку, каким бы авторитетом он не был. Доверять можно только тем случаям, когда код или алгоритмы были выверены сотнями исследователей и разработчиков (как например с AES), и даже в подобных случаях — порой находятся такие уязвимости, которые ломают всю безопасность на корню (как например 2 раза случилось с OpenSSL за последние месяцы).
Код я использовал практически тот же, что и выложил, с небольшой модификацией: деление на кольце по модулю часто имеет более одного результата, но далеко не все они решают исходную систему уравнений, так что я добавил перебор среди возможных решений, что бы оно находило те значения, которые «подходят». При этом перебрать долго не приходится: если я вижу, что вариантов слишком много, я просто перехожу к следующему блоку. Число вариантов варьировалось от 64 до 16000^3, так что я выбирал только те данные, где 64 или аналогично возможных решений, перебирается это мгновенно.
Возможно если бы вы использовали 64х битные типы — мне пришлось бы подождать пару часов, пока среди миллионов возможных решений найдётся нужное :) но надо сказать, что сама переборная сложность тут не велика, т.к. по сути тут не система из 9 уравнений, а три независимых системы по 3, соответственно перебирать нужно не девятую степень а третью. В случае решения в общем виде, кстати, такой проблемы быть не должно, там детерминант будет либо 0 (вырожденная система не имеющая решения), либо 1, а деление на 1 — всегда однозначная операция :)
Мастер-матрица, дешифрующая файл (т.е. это уже обратная матрица):
u_int16_t matrix[9] = { 17753, 49212, 16816, 56260, 37849, 28576, 27472, 60448, 24961 };
Сам файл дешифрованный:
dl.dropboxusercontent.com/u/25074445/ohwell.bmp
Бонально мне лень реализовывать такие вещи, как например подсчет детерминанта матрицы произвольной размерности — я не вижу смысла тратить столько времени на то, что бы доказать не пойми кому простые азбучные истины, изучаемые на первых страницах любого учебника по криптоанализу.
А частный случай — пожалуйста, берусь.
Существует более одного способа сериализовать подобное. И я не собираюсь угадывать формат, как я вам писал в самом начале.
а не то, что оно однозначно там в Big Endian
2) Каким образом вы пишите 56-битные числа на диск, при N==7??? Вы можете внятно ответить на этот вопрос? Я понимаю, что в случае N=7, скорее всего работа идет с 64-битным числом, которое обрезается операцией &MASK. Но как вы его потом записываете на диск, вы же сохраняете только 7 байт из 8-ми. Вот опишите этот момент подробно.
2) — каким образом тогда вы работаете с, например, 56-битными числами? Или в формуле 24*N, N не может быть равным 7-ми?
Без подобной информации что-либо делать мне — безсмысленно. Как я сказал — я согласен решать задачу крипто-анализа, а не угадывания вашего формата файла.
Перед тем, как я начал тратить время, ответте на вот эти вопросы, пожалуйста:
1) В каком виде сериализуются N-битные целые числа? Сохраняются ли они как Big Endian, Little Endian, или как-то еще?
2) В случае когда например N=7, т.е. алгоритм работает с группами из трех чисел, каждое по 56 бит, — можете поточнее описать, как эти 56-ти битные числа, в каком формате, сохраняются в файл?
P.S. Я так-же надеюсь вы не мухлевали, и как и обговорено было, просто N раз прогнали один и тот-же алгоритм, каждый раз с новым ключем. Т.е. не примешивая никаких других операций, вроде XOR-ов, применения следующей итерации с небольшим смещением, итп.
Не буду спорить, соглашусь на ваши условия, но предполагаю что речь идет о целочисленной арифметике, т.е. что вы не используете float/double-ов. Как я уже писал выше, подобные вещи могут внести нелинейность, но если заранее знать, что оно там есть — от нее можно избавится. Посколько вы не указали ничего такого, и речь о линейности — предполагаем что float-ов не используется, чисто целочисленная арифметика. (Опять-же, в реальном мире детали крипто-алгоритма всегда достоверно известны заранее, никто не пытается строить безопасность основываясь на том, что кто-то не знает деталей реализации — подобные попытки были в прошлом, и показали себя как наименее защищенные системы).
Что про заголовок — впрочем их исходных файлов и так понятно, докуда он.
<<Вообще, если вы предоставите сам код, кодирующий / декодирующий, набор файлов (оригинал + шифрованное), то я берусь попробовать восстановить ключи (которых вы мне не сообщите).
Если исходники предоставить не можете — нужна грамотная техническая, подробная, спецификация, на все форматы. Того, что вы описали — недостаточно.
Конечно, в общем случае — можно все проанализировать и без подобных деталей, но сейчас задача стоит сломать шифрование, а не угодать формат файла. >>
После чего мы договорились о формате файла — «как вы исходниках, что для ядра OpenCL», мы согласились на эти правила игры. Однако вы решили их поменять, после того, как пари было уже заключено.
Повторюсь: без предоставления мне детальной технической информации об алгоритме, я не собираюсь тратить свое время на то, что-бы заниматься угадыванием формата. Криптоанализ не занимается решением подобных вопросов. Этим занимаются хакеры, которые в два счета стащат у вас все исходники, если кому-то будет интересен ваш «алгоритм» ;)
Вообще, конечно можно проанализировать все это и в совсем общем случае, ни зная об алгоритме вообще ничего, используя различные инструменты криптоанализа, однако изначально задача об этом не шла, т.к. повторю свои слова еще раз:
<<Конечно, в общем случае — можно все проанализировать и без подобных деталей, но сейчас задача стоит сломать шифрование, а не угодать формат файла. >>
Так что я возвращаюсь к своим исходным условиям: либо исходники, либо детальное описание формата.
> Прошу заметить что при условно реальном случае KPCA вам никто предоставлять размер блока не будет.
потому что он заранее известен, т.к. известен используемый алгоритм, который, в отличии от вашей поделки, описал до мельчайших деталей, а не только размер блока.
Так что минимум размер блока в битах в студию.
Ждать — после 24-ого, я вам уже писал.
pastebin.com/fNhPKFgf (код ужасный по стилю, конечно, в реальной жизни я так не напишу, но тут я торопился просто)
поскольку я знаю заранее, что там матрицы 3x3, я не буду опускатся до битового уровня — лишняя головная боль :)
А так, пример демонстрирует, как можно восстановить исходный ключ по 3м парам сообщений.
Правда есть ограничение на эти 3 пары — детерменант матрицы составленной из нешифрованных сообщений не должен быть нулевой, т.е. между векторами исходных сообщений не должно быть линейной зависимости. Что впрочем на случайных данных — практически всегда выполняется, а если где и не выполняется — можно просто взять другой датасет.