Алгоритм расшифровки данных с помощью нарисованных штрихов

Question

Допустим, у меня есть зашифрованный файл на iPhone, и каждый раз, когда я хочу его расшифровать, я хочу "нарисовать" символ расшифровки вместо того, чтобы вводить его с клавиатуры.

Если вы запрашиваете у пользователя нарисовать символ для расшифровки файла каждый раз, когда это необходимо (напримеркаждый раз, когда они запускают ваше приложение), они, вероятно, предпочли бы это необходимости вводить пароль из 20 символов или около того на крошечной клавиатуре, и они все равно получили бы защиту, которую им дал бы пароль из 20 символов (в зависимости от того, насколько сложна фигура / символ, который они рисуют).

Символ, который они нарисовали бы, скорее всего, был бы одним штрихом (напримерэто заканчивается, как только вы поднимаете палец), но может быть очень сложным, таким, что кому-то другому будет трудно повторить это, даже если они увидят, как вы это рисуете.Вроде того, как подпись каждого человека уникальна, и ее трудно воспроизвести.На самом деле, это может просто чрезмерно усложнить его, если нужно было предотвратить дублирование, так что пока это можно проигнорировать, и мы можем предположить, что символ не будет замечен кем-то другим, и, следовательно, не имеет значения, может ли он быть повторен ими или нет.

Я предполагаю, что реальный вопрос заключается в том, как бы вы последовательно преобразовали один и тот же (разумный) штрих в одну и ту же клавишу (напримерхэш-значение).Очевидно, что в алгоритме должен быть некоторый порог прощения, потому что нельзя ожидать, что пользователь повторит удар с точностью до 100%.

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

Хорошим примером штриха, который пользователь может использовать в качестве символа расшифровки, является символ "&".Представьте, что пользователь рисует этот символ на своем iPhone каждый раз, когда ему нужно расшифровать файл.Размер символа может быть разным при каждом его рисовании.Кроме того, вращение символа может отличаться в зависимости от того, как пользователь держит свое устройство.В идеале, в обоих случаях, поскольку символ был нарисован относительно пользовательских штрихов одинаково, он должен иметь возможность генерировать одно и то же хэш-значение и, таким образом, расшифровывать файл.

Я думал, что что-то вроде распознавания формы или символов - это аналогичный алгоритм.Где пользователь рисует что-то (разумно представляющее фигуру), а затем фиксирует это до правильной формы, которая будет иметь одно и то же хэш-значение каждый раз, когда она рисуется.Однако для чего-то подобного вам, скорее всего, понадобится база данных фигур, которые можно нарисовать, и если вы выберете что-то вроде "все буквы алфавита", вы получите только 26 букв.И если предположить, что пользователю нужно нарисовать только один символ для расшифровки файла, у вас есть крайне небезопасный пароль, имеющий всего 26 возможностей.

Еще одна вещь, о которой я подумал, - это то, что вы могли бы разбить нарисованный символ на крошечные сегменты, а затем запустить распознавание символов на них.Итак, представьте, что у вас есть 4 символа в базе данных:вертикальная линия, горизонтальная линия и диагональ в обоих направлениях.Теперь, когда пользователь рисует, каждый сегмент распознается как один из них, а затем все они объединяются, образуя некоторое хэш-значение.Итак, представьте, что пользователь выбрал в качестве символа расшифровки строчную букву "r".Таким образом, они начинали с рисования вертикальной линии вниз, за которой следовала вертикальная линия вверх, за которой следовала диагональная линия вверх и вправо.Одна из проблем, связанных с этим методом, заключается в том, как вы узнаете, когда нужно разделить штрих на отдельные сегменты?Вероятно, вы также хотели бы принять во внимание приблизительную длину каждого отдельного сегмента (напримерс шагом в 40 пикселей).Таким образом, если кто-то нарисовал деформированную букву "r" там, где горб выходит ближе к нижней части, он не распознается как тот же символ и, следовательно, не расшифрует файл.

Третий метод может заключаться в разделении экрана на сетку (пока не уверен, какого размера) и простом просмотре того, в каких ячейках нарисован штрих, и использовании этих данных каким-то образом для генерации строки.

Есть какие-нибудь другие идеи о том, как это можно было бы реализовать?Вы когда-нибудь слышали о чем-то подобном?Существуют ли какие-либо фундаментальные недостатки, которые могли бы помешать работе подобной системы?

Спасибо

Answer 1

Проблема шифрования данных с помощью ключевого материала, в котором могут быть небольшие ошибки, достаточно подробно изучена. В частности, существует ряд предложений по защите данных с использованием биометрических данных (например, отпечатков пальцев или сканирования сетчатки) в качестве ключа. Типичный подход состоит в том, чтобы использовать соответствующий код исправления ошибок, взять исходный ключевой материал K, вычислить его синдром и сохранить только этот синдром. Как только вы получите второе прочтение ключевого материала K ', синдром можно использовать для восстановления K из K', если K и K 'достаточно близки (где «достаточно близко», конечно, зависит от схемы исправления ошибок).

Чтобы начать, вот документ, предлагающий схема нечеткого хранилища . Это общее предложение для схемы шифрования с использованием «нечеткого» ключ. Конечно, вам все еще нужно изучить, как извлечь характеристики из чертежей, которые достаточно стабильны для использования такой схемы исправления ошибок. Вам также нужно будет проверить, сколько энтропии вы можете извлечь из таких рисунков. Какими бы плохими ни были пароли в отношении энтропии, их все равно сложно победить.

Answer 2

Я бы попробовал вариант сегментации:Распознавать простые узоры - для этого я буду придерживаться прямых и диагональных линий, но теоретически вы также могли бы добавить круги, дуги и, возможно, другие элементы.

Вы можете быть совершенно уверены, когда заканчивается одна строка и начинается другая, поскольку существует 8 направлений, и вы можете обнаружить изменение направления (или для более простого подхода просто определите pen up и pen down и используйте их в качестве разделителей строк).Первая строка задает масштабный коэффициент, поэтому длина любой другой строки может быть представлена в виде коэффициента (например, в обычной форме L первая вертикальная строка будет давать "базовую длину" b, а другая строка тогда будет иметь длину примерно 0,5 * b).После того, как пользователь закончит, вы можете использовать наименьший коэффициент s для "округления" длин, так что у вас будет массив целых длин, таких как [1 * s, 2 * s, 4 * s, 5 * s].Это предотвратит чрезмерную точность системы, а использование базовой длины делает систему устойчивой к масштабированию.

Теперь каким-то образом преобразуйте эту информацию (длины и направления) в строку (или хэш-значение, как вам угодно), и оно будет одинаковым для одних и тех же штрихов, даже если символ переведен или масштабирован.

Кроме того, вы можете сохранить значение смещения 2D (конечно, тоже "округленное") для каждой строки после второй строки, так что строки также должны будут находиться в одном и том же положении, если вы этого не сделаете, L и T, скорее всего, получат одну и ту же строку (1 строка вверх-вниз, 1 строка влево-вправо длиной 0,5).Таким образом, сохранение позиций немного усиливает все это, но является необязательным.

Редактировать:

Если вы возьмете угол первой линии за базовый угол, вы даже можете сделать его устойчивым к вращению.

Пожалуйста, обратите внимание, что этот алгоритм выдает только 3 бита на штрих, если все строки одинаковой длины, и максимум, возможно, до 6-8 бит на штрих, немного больше, если вы также сохраняете позиции.Это означает, что вам понадобится довольно сложный символ примерно из 20-40 штрихов, чтобы получить 128 бит безопасности.

Простым способом добавить больше вариативности / безопасности было бы позволить пользователю использовать разные цвета из заданной палитры.

Чтобы уменьшить риск того, что кто-то за вами наблюдает, вы могли бы сделать так, чтобы каждая линия исчезла после того, как она была нарисована, или изменить цвет на цвет с очень низким контрастом к фону.

Answer 3

При распознавании почерка часто учитывается продолжительность обводки, а не фактическая длина и т. д.

Хотя это относится к чувствительности к давлению, я думаю, что вы, возможно, сможете увидеть некоторые концептуальные фрагменты того, о чем вы здесь думаете ... jdadesign.net/safelock/

Это не совсем та же тема, но это самая близкая вещь, которая приходит на ум в данный момент.

Answer 4

Я не думаю, что вы могли бы получить достаточно " битов " от нарисованного от руки символа для безопасного шифрования. Как вы заметили, вы должны допускать достаточный уклон в понимании того, что естественные изменения в чертеже будут терпимы. Другими словами, вы должны отбрасывать шум в мазках, сглаживая их в воспроизводимый сигнал. Но шум (высокая энтропия) делает лучше криптографические ключи.

Думай об этом так. Если вы разложите жест на сегменты вверх, вниз, влево и вправо, каждый сегмент будет представлять 2 бита информации. Для ключа AES символу потребуется 64 таких сегмента. Это довольно сложный жест для запоминания. И если его упростить, повторяя много сегментов подряд (" право, право, право, ... "), то получится паршивый (предсказуемый, неслучайный) ключ.

Answer 5

У меня была еще одна мысль об этом. Я не специалист по компьютерным технологиям, но хотел бы что-то вроде этой работы.

Допустим, что с любым символом или "шаблоном" кто-то рисует. Единственная жизнеспособная вещь, которую вы можете проанализировать - это все точки в шаблоне, сгенерированные в событиях touchBegan, touchMoved и touchEnded.

Итак ... давайте возьмем все полученные баллы, будь то 100 или 1 000 000, это не имеет значения.

Разделите их на группы, на сколько угодно. Чем больше, тем лучше я предполагаю, но для этого примера давайте разберем их по 4 группам. В группе из 100 баллов группа 1 будет содержать баллы 1 > 25, группа 2 содержит 26 > 50 и тд.

Для каждой группы используйте все точки для расчета средней позиции.

Может быть лучше, если пространства холста разделены на сетку, а «средние позиции» нанесены на их ближайшую координату.

Затем проверьте относительное расстояние между всеми группами. Так что между 1,2 1,3 1,4 2,3 2,4 3,4.

Теперь у вас есть как можно больше разных точек и информации об этих точках для генерации ключа. Средние значения и сетка должны помочь сгладить некоторую, если не всю энтропию.

Возможно, вам придется попросить пользователя нарисовать их схему несколько раз и сравнить каждую группу с группами из предыдущих попыток. Таким образом, вы можете определить, какие группы пользователи могут строить последовательно. Это имеет дополнительное преимущество в обучении пользователей рисованию их шаблонов.

Я подозреваю, что чем больше у вас очков и групп, тем точнее это будет.

На самом деле, я собираюсь попробовать сам.

Answer 6

Жесты.

http://depts.washington.edu/aimgroup/proj/dollar/

Вы можете определить свои собственные алгоритмы для определенных жестов.НАПРИМЕР, круг,

1. Найдите начальную точку 2.найдите самые левые, самые правые и самые дальние точки и получите приблизительный радиус.3.сверьте все точки с радиусом с погрешностью (25%?) 4.Если радиус совпадает, у вас есть окружность.

Вертикальная Прямая линия:1.Проверьте положение начальной и конечной точек X и Y.2.Сравните промежуточные точки с точками x и y начала и конца.3.Если они расположены примерно в одной и той же координате X, но в восходящей или нисходящей координатах Y, у вас получится вертикальная линия.

И так далее, усложняясь для более сложных жестов.

Вы даже можете комбинировать жесты.Итак, предположим, у вас есть алгоритм для 6 жестов.Вы можете комбинировать их, образуя разные символы.Порядок, в котором создаются жесты, может быть важным, добавляя дополнительный уровень безопасности.

Answer 7

что если вы взяли все координаты x, y штриха и предварительно выполнили какую-то линейную двустороннюю операцию над ними? Затем вы можете вычислить «приблизительный» хеш, и если число, вычисленное, когда штрих находится в пределах ... скажем, 10% от вашего приближения, то вы предоставляете доступ.

Answer 8

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

Например, метод андроида с 9-клеточной разблокировкой может дать вам около 16 бит энтропии. Предположим, вы используете 5 секунд процессорного времени для расчета ключа шифрования. Затем в среднем ПК требуется 5 * 2 ** 16/20 секунд или около 4,5 часов для взлома. Любая потеря энтропии на входе или неэффективность настройки ключа и шифрования быстро приведут к потере минут, не говоря уже о том, используются ли кластеры компьютеров.

Честно говоря, это будет не намного лучше, чем просто хранить файл в неизвестном формате и надеяться, что никто не поймет его