Алгоритм дешифрования данных нарисованными штрихами - PullRequest
13 голосов
/ 24 октября 2009

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

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

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

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

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

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

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

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

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

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

Спасибо

Ответы [ 8 ]

3 голосов
/ 24 октября 2009

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

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

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

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

EDIT:

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

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

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

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

2 голосов
/ 24 октября 2009

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

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

1 голос
/ 24 октября 2009

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

Допустим, что с любым символом или «узором» кто-то рисует. Единственная жизнеспособная вещь, которую вы можете проанализировать - это все точки в шаблоне, сгенерированные в событиях 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.

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

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

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

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

1 голос
/ 24 октября 2009

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

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

1 голос
/ 24 октября 2009

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

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

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

0 голосов
/ 24 октября 2009

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

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

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

0 голосов
/ 24 октября 2009

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

0 голосов
/ 24 октября 2009

Жесты.

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

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

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

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

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

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

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