Крипто-форум crprogram.16mb.com

Програмування на Object Pascal, Lazarus, криптографія, криптоаналіз, шифри, вихідні коди, вирішення задач, приклади програм

Часовий пояс: UTC десь + 2 години




Розпочати нову тему Відповісти  [ 53 повідомлень ]  На сторінку 1, 2, 3  Наст.
Автор Повідомлення
 Заголовок повідомлення: KGV
СообщениеДодано: 20 лют 2015, 12:07 
Не в мережі

Повідомлень: 24
Доброго дня.
Назва аглоритму - скорочення KeyGeneratedVernam (алгоритм Вернама з генерованим ключем).
В мене немає достатніх знань і часу на детальну перевірку, тому прошу знавців проаналізувати на профпридатність.

Алгоритм симетричний.
На вхід подається (у вигляді динамічно завантажуваних бібліотек):
1) Набір функцій виду y=f(x). Область визначення і область значень - будь-яке допустиме число для типу double (дійсне з плаваючої точкою, 8 байт). Єдина умова - неперервність на всій області визначення. В бібліотеці має бути 16 різних функцій.
2) Хеш-функцію. Це може бути будь-який з вже існуючих, або авторський неопублікований. Мінімальний розмір дайджесту залежить від розміру файлу, який обробляється. Загалом 128-бітний хеш цілком підходить.
3) Файл достатньої довжини з набором реально (не псевдо) випадкових даних. Дані можна взяти з якогось фізичного датчика випадкових професів (того ж лічильника радіоактивного розпаду, чи флуктуацій електронного газу).
4) Ну і пароль сеансу.

Перед кожним шифруванням до даних додаюється невеликий набір псевдовипадкових даних (щоб шифротекст на кожному сеансу був іншим, навіть при однакових вхідних параметрах).
Обробка здійснюється поблочно, розмір блоку залежить від розміру вхідного файлу (16 байт для [0..64Kb], 32 для (64Kb..1Mb], 64 для (1Mb..16Mb], 128 для (16Mb..256Mb], 256 для (256Mb..4Gb] і 512 для більших 4Gb.
Ключ для поточного блоку створюється залежно від результатів роботи на попередньому кроці.
Окрім цього, використовується не лише єдиний xor.
Є чотири оборотні операції, що приймають 2 біти на вхід і 1 біт на вихід. x або not(x) або (x xor y) або not(x xor y). Тип операції для кожного біту визначається також залежно від результатів роботи на попередньому кроці, але по іншому ніж для ключа.
При розшифруванні попередніх вставок у дані немає, натомість є видалення після завершення обробки попередньо доданих перед шифруванням псевдовипадкових даних.


Вкладення:
Коментарій до файла: Вихідний код для аналізу
QKGV.rar [4.85 KiB]
Скачали: 105
Повернутися наверх
  
 
 Заголовок повідомлення: Re: KGV
СообщениеДодано: 20 лют 2015, 12:45 
Не в мережі

Повідомлень: 282
Це добре що з'являються нові алгоритми.

Будемо розбирати. (Також пам'ятайте що це потребує деякого часу.)


Повернутися наверх
  
 
 Заголовок повідомлення: Re: KGV
СообщениеДодано: 22 лют 2015, 08:37 
Не в мережі

Повідомлень: 282
Може є у вас цей алгоритм на Object Pascal?

Я C++ трохи знаю, але не достатньо.


Повернутися наверх
  
 
 Заголовок повідомлення: Re: KGV
СообщениеДодано: 22 лют 2015, 08:40 
Не в мережі

Повідомлень: 282
Або опишіть алгоритм мат.формулами та детальним прикладом.

Код:
Наприклад, є рядок 000...000, ключ 111...111,
і т.д. і т.п.
В результаті отримаємо 0435F4A9...F988.


Повернутися наверх
  
 
 Заголовок повідомлення: Re: KGV
СообщениеДодано: 23 лют 2015, 17:31 
Не в мережі

Повідомлень: 24
Нажаль, на Object Pascal немає. Проект розроблявся на Qt з огляду на його кросплатформенність.
Боюсь з теорією важко буде. Я скоріше практик і не сильно задумувався над строгим математичним описом описом :(
Гаразд, попробую за кілька днів скласти пристойний опис. Поки що є дебаг записи.

Приклади шифрування:
Вхідний файл flower.jpg, пароль кожного шифрування yarko, файл випадкових даних data.qkgvkey, набір функцій.
На виході результати 4 сеансів шифрування з однаковими вхідними параметрами.
В мому алгоритмі немає ключа в класичному розумінні (який треба подавати на вхід). Тут ключ і номери побітових операцій визначається на ходу.


Вкладення:
kgv_example.rar [124.56 KiB]
Скачали: 84
Повернутися наверх
  
 
 Заголовок повідомлення: Re: KGV
СообщениеДодано: 23 лют 2015, 23:09 
Не в мережі

Повідомлень: 282
Напишіть як можете - будемо розбиратись.


Повернутися наверх
  
 
 Заголовок повідомлення: Re: KGV
СообщениеДодано: 02 бер 2015, 18:48 
Не в мережі

Повідомлень: 24
Нарешті дійшли руки.
Що ще потрібно для аналізу?


Вкладення:
Опис алгоритму шифрування QKGV.rar [7.24 KiB]
Скачали: 143
Повернутися наверх
  
 
 Заголовок повідомлення: Re: KGV
СообщениеДодано: 03 бер 2015, 18:43 
Не в мережі

Повідомлень: 282
Перепишу алгоритм як я його розумію.

На вході маємо "пароль" та текст.

Вираховуємо 2 хеш-суми:
THash=хеш("пароль")
KHash=хеш("парольпароль")

Заповнюємо масив T байти(8 біт) з THash
Заповнюємо масив K бітами з KHash

Масив Т записані байти, (припустимо це буде значення d7). Тоді в T[і] буде записано значення 12-тої функції з набору (d=12) з аргументом функції «7».
(з QKGVFormula. Містить 16 формул виду y=f(x). Тип вхідного параметра і вихідного значення double (дійсне число з плаваючою крапкою, 8 байт).)

Також на вході маємо QKGVKey, набір випадкових даних з:
Цитата:
2. Плагін, що реалізує інтерфейс QKGVKey. Містить в собі файл з реально випадковими даними (наприклад з датчика радіоактивності чи флуктуацій густини електронного газу тощо).


З випадкових даних беремо змінну tables, яка рівна 32 байтам.
З випадкових даних беремо змінну text, яка рівна 32 байтам.

Змінна blocks вказує на поточний блок даних, який буде за/розшифровано.

Шифруємо блок.
Беремо по k-тий біт із змінних tables («v») і text («t»), а також 2 біти, починаючи з k*2 із змінної tables («op»). Отримуємо щось типу v=0, t=1, op=2. Результатом буде
op=0 => v;
op=1 => not(v);
op=2 => v xor t;
op=3 => not(v xor t).

Можлbво, я не до кінця зрозумів алгоритм, але з того що я бачу:
всі ці "танці з бубном" а саме функції, додаткові масиви не потрібні, адже якщо ви заповнюєте вхідні масиви випадковими числами, по суті отримуєте варіант одноразового шифрувального блокнота.(див topic-t84.html)
Тобто, якщо ви використовуєте масив QKGVKey один раз, то достатньо було б вирахувати текст xor QKGVKey = шифртекст.

Тобто стійкість буде залежати тільки від того скільки разів ви використаєте дані "із змінних tables («v») і text («t»)", які по суті є випадковими даними. Але в двох таблицях немає сенсу, достатньо однієї.

Далі, ідея щодо вибору функцій шифрування для певного і-го символа(байта, біта) залежно від попередніх даних, байта(біта) ключа, номера позиції символа(байта) далеко не нова.
Ще до 2000 року я вивчав види впливів на байт при шифруванні. Таких видів є декілька десятків. Деякі з них придумали ще в Середньовіччі, деякі в 19-му, деякі в 20-му столітті.

Якщо, припустити що файл випадкових даних стане відомим - весь алгоритм руйнується як картковий будинок.


Що б я радив вам:

візьміть лист паперу, напишіть на ньому послідовність байт(біт, слів - не важливо) і почніть до нього "додавати" найпростіші операції шифрування, які ви тут використовуєте. Подумайте над тим яка користь від кожної з них, скільки комбінації і т.д.
А загалом і т.д. і т.п. - цілі курси вчать цьому, і не завжди є результат.


Загальний висновок: поки ви використовуєте випадкові числа у якості ключового матеріалу - аналізувати нема чого. Це те саме що аналізувати
Код:
P xor K = C
, де K - випадковий ключ.


Повернутися наверх
  
 
 Заголовок повідомлення: Re: KGV
СообщениеДодано: 04 бер 2015, 18:12 
Не в мережі

Повідомлень: 282
Я ні в якому разі не хочу вас відговорити створювати алгоритми.

Але краще почніть з такої задачі:
є ключ довжиною 128,256, чи 512, чи більше біт, і текст.
Отримати шифртекст який можливо буде прочитати виконавши скажімо 10^40 операцій.

Без випадкових файлів, допускається додавання до тексту послідовності випадкових біт, скажімо довжиною до 256 байт на один текст.


Повернутися наверх
  
 
 Заголовок повідомлення: Re: KGV
СообщениеДодано: 05 бер 2015, 18:00 
Не в мережі

Повідомлень: 24
Поясніть будь-ласка детальніше, як саме алгоритм ламається, якщо файл з випадковими даними стане відомим. Якщо його викрадуть в однієї з сторін, то в такому випадку жоден алгоритм не допоможе вберегти дані (бо вкрадуть все).

Файл випадкових даних передається лише один раз, і в кожної з сторін не лише один єдиний такий. Для кожного адресата може бути інший. Крім того набори формул, які також можуть бути різні для кожного адресата. І за потреби новий набір непомітно передати набагато простіше, аніж порівняно великий файл випадкових даних.
Вернам абсолютно стійкий, але він не використовується через випадковий пароль, який треба кожен раз передавати.
Власне я алгоритм тому так і назвав, бо ключ тут формується по ходу процесу і відразу знищується. Можна звичайно з випадкових даних брати не блоками, а байтами.
Якщо хочете - можете вважати це ще однією реалізацією "одноразового блокнота" :)

Чи стійкий на Вашу думку сам мій принцип формування ключа з набору випадкових даних з використанням набору формул?


Повернутися наверх
  
 
 Заголовок повідомлення: Re: KGV
СообщениеДодано: 07 бер 2015, 12:01 
Не в мережі

Повідомлень: 24
Уточню на всякий випадок.
QKGVKey (випадкові дані), QKGVLib (набір формул) і QKGVHash (хеш алгоритм) зберігається в обох сторін і нікуди не передається. Думаю про пароль пояснювати не треба. Передається лише зашифрований матеріал.
Також у передаючої сторони (яка шифрує дані) необхідна наявність вбудованого "генератора псевдовипадкових чисел" (такий є на будь-якому компютері). У приймаючої сторони такого може і не бути. Параметри цього генератора для приймаючої сторони не мають жодного значення. Тобто передавальна сторона може підключити навіть лічильник Гейгера. якщо зможе знайти драйвера до нього :).
Дайте знати, якщо можете довести на прикладі, що втрата таємності QKGVKey (а також паролю і QKGVHash) є фатальною? Я підготую інший набір формул і скину сюди якесь простеньке зашифроване прислів'я.

Прошу вибачення, якщо я завдав Вам багато клопоту цією темкою.


Повернутися наверх
  
 
 Заголовок повідомлення: Re: KGV
СообщениеДодано: 08 бер 2015, 09:37 
Не в мережі

Повідомлень: 6
Для повідрмлення довжиною 5кб -яка довжина файла з випадковими даними? Якщо я передаю наступні 5кб - новий файл з випадковими даними потрібен?


Повернутися наверх
  
 
 Заголовок повідомлення: Re: KGV
СообщениеДодано: 09 бер 2015, 09:57 
Не в мережі

Повідомлень: 24
Розмір QKGVKey і розміри повідомлень, які шифруються з його допомогою діяк не пов'язані.
Новий QKGVKey потрібен лише у випадку, якщо обидві сторони погодяться на необхідності заміни діючого.


Повернутися наверх
  
 
 Заголовок повідомлення: Re: KGV
СообщениеДодано: 09 бер 2015, 16:15 
Не в мережі

Повідомлень: 282
На жаль, опис алгоритму більш ніж туманний.

Цитата:
– шифруємо блок. Лічильник «k» від 0 до blockSize*8-1. Беремо по k-тий біт із змінних tables («v») і text («t»), а також 2 біти, починаючи з k*2 із змінної tables («op»). Отримуємо щось типу v=0, t=1, op=2. Результатом буде
op=0 => v;
op=1 => not(v);
op=2 => v xor t;
op=3 => not(v xor t).



Ймовірно помилка в описі - малось на увазі що "v" це не випадкові дані, а біти відкритого тексту.
Тоді,
якщо ми знаємо файл випадкових даних, ми знаємо "t", "op" - і з тих формул легко знайти "v".


п.с.: опишіть алгоритм більш зрозуміло. Не потрібно описувати звідки яка бібліотека завантажується, чи які у вас лічильники у циклах.

Див приклад опису:
post643.html

чи схемою, як тут:
3-t183.html



Код:
void QKGV::encrypt(byte *value, byte *tables, byte *text, uint blockSize) {
    byte temp;
    unsigned short temp2;
    byte temp3;
    byte res;
    byte v;
    byte op;
    byte t;
    for (uint i = 0; i < blockSize; ++i) {
        temp = value[i];
        temp2 = (tables[i*2] << 8) + tables[i*2+1];
        temp3 = text[i];
        res = 0;
        for (int j = 7; j >= 0; --j) {
            v = (temp >> j) & 1;
            op = (temp2 >> (j*2)) & 3;
            t = (temp3 >> j) & 1;
            switch (op) {
                case 0: v = v & 1; break; //a
                case 1: v = ~v & 1; break; //not a
                case 2: v = (v ^ t) & 1; break; //a xor b
                case 3: v = ~(v ^ t) & 1; break; // not (a xor b)
            }
            res = res | (v << j);
        }
        value[i] = res;
    }
}


value - масив випадкових даних?
tables -?
text - відкритий текст?


Повернутися наверх
  
 
 Заголовок повідомлення: Re: KGV
СообщениеДодано: 10 бер 2015, 11:41 
Не в мережі

Повідомлень: 24
Перепрошую. І справді переплутав.
v - 1 біт відкритого тексту,
op - 2 біти із змінної tables. Задає тип операції.
t - 1 біт згенерованого ключа, який накладається на відкритий текст.

На вхід функції encrypt йде
value - блок відкритого тексту (розмір = значення змінної blockSize)
tables - куски з QKGVKey (розмір = blockSize*2)
text - інші куски з QKGVKey (розмір = blockSize). Це власне ключ.
Можливо змінні варто було б по іншому назвати, але в кожного програміста свої смаки.

Olgerd писал(а):
Тоді, якщо ми знаємо файл випадкових даних, ми знаємо "t", "op" - і з тих формул легко знайти "v".

Якщо ви знаєте QKGVKey, але не знаєте QKGLib, то Ви знайдете, але зовсім не відкритий текст, а нечитабельну крякозябру.
Лише якщо знати QKGVKey, QKGVLib, QKGVHash і пароль - можна правильно відтворити відкритий текст з шифротексту.
Окрім того, якщо при передачі зміниться хоча б 1 біт - пиши пропало.

Просто розробка велася з припущення, що уразливий лише канал передачі, а не передавальна/приймальна машина. Якщо вдастся отримати доступ до одної з сторін - ніщо не врятує (підсадять хоча б кейлогера і привіт).

Сорці http://replace.org.ua/misc.php?action=pun_attachment&item=774&download=1


Повернутися наверх
  
 
 Заголовок повідомлення: Re: KGV
СообщениеДодано: 10 бер 2015, 18:49 
Не в мережі

Повідомлень: 282
Алгоритми випробовують на "міцність" якраз за умови що зловмиснику відомий повністю алгоритм та відкритий текст, не відомий лише ключ, який і потрібно знайти. Сучасні алгоритми якраз і стійкі проти таких атак.

Тобто, якщо стійкість алгоритму ґрунтується на тому що невідомий ключ - алгоритм уже вважається не стійким.

Й до цих пір не зовсім зрозуміло що і звідки береться.

Цитата:
v - 1 біт відкритого тексту,
op - 2 біти із змінної tables. Задає тип операції.
t - 1 біт згенерованого ключа, який накладається на відкритий текст.

Отже, v - відкритий текст ми знаємо, op - дані з випадкової послідовності ми теж знаємо, адже маємо для аналізу файл з випадковими даними, тоді з цих даних знаходимо t, наприклад:
з
Код:
v xor t


Взагалі кажучи я починаю думати що ви вважаєте вибір формули з допомогою певного параметра стійкою операцією.
Це не зовсім так:
наприклад
для xor
v=0 xor 0 = 0
v=0 xor 1 = 1
v=1 xor 0 = 1
v=1 xor 1 = 0

для not
v=1 => 0
v=0 => 1

Припустімо ми не знаємо яку формулу застосовано, але знаємо v=1, і результат 0: тоді або not v, або біт ключа рівний 1.

Тобто в половині випадків навіть якщо ми помилково визначимо операцію - отримаємо все одно вірний результат.

І т.д. і т.п.

На даному етапі досить важко робити висновки - методів зламу і аналізу вистачає. Який конкретно застосувати залежить від повного опису алгоритму.

Я вам знову ж пропоную : опишіть для одного блоку даних, для одного ключа і випадкового файла послідовно що і як виконується, тоді я зможу зробити висновки.

Поки що, за зовнішніми ознаками я не бачу стійкого шифру.


Повернутися наверх
  
 
 Заголовок повідомлення: Re: KGV
СообщениеДодано: 11 бер 2015, 10:23 
Не в мережі

Повідомлень: 24
Ок. Для одного блоку. Для опису припустимо blockSize = 64 (байти), subBlockCount = blockSize/16 = 4.

а) Копіюємо 4 куски по 32 байти з QKGVKey, починаючи з позицій "модуль від округлити T[j] до цілого", j = від 0 до subBlockCount-1 включно. Отримаємо змінну tables довжиною 128 байт.
Копіюємо інші 4 куски по 16 байт з QKGVKey, починаючи з позицій "модуль від округлити K[j] до цілого", j = від 0 до subBlockCount-1 включно. Отримаємо змінну text довжиною 64 байт.
Беремо 64 байти відкритого тексту. Отримаємо змінну block.
б) Вираховуємо хеш від block. Якщо операція "шифрування", то записуємо це в масив THash, інакше в масив KHash.
в) Подаємо block, tables і text в функцію encrypt. На виході отримаємо шифротекст розміром 64 байти (змінна block).
г) Вираховуємо хеш від block. Якщо операція "шифрування", то записуємо це в масив KHash, інакше в масив THash.
д) Оновлюємо значення масиву T. Цикл по j від 0 до subBlockCount-1 включно. Беремо j-тий байт з змінної THash. Старші 4 біти вказують номер функції з QKGVLib. Викликаємо цю функцію з аргументом T[j]. Записуємо результат в T[j].
Аналогічно оновлюємо масив K, використовуючи KHash.
е) Переходимо до обробки наступного блоку відкритого тексту.

Також не забувайте, що до відкритого тексту перед шифруванням додаються зовсім інші випадкові дані, ніяк не пов'язані з QKGVKey. Вони залежать виключно від комп'ютера, на якому виконуєтсья поточний процес шифрування. Взнати їх наперед в ідеалі немає жодної можливості. Тому для малих повідомлень власне відкритий текст піде не в першому блоці, а в 2-3. Ці допоміжні дані можна очистити лише після повного коректного дешифрування шифротексту на приймальній стороні.

Ну а чому я виходив з припущення, що уразливий лише канал - запам'ятайте наприклад 30 і більше символів ключа традиційних алгоритмів (якщо це не осмислена фраза звичайно). Все одно доводиться зберігати такий ключ десь в пам'яті машини або на папері. Якщо папір вкрадуть - здогадайтесь самі.


Повернутися наверх
  
 
 Заголовок повідомлення: Re: KGV
СообщениеДодано: 11 бер 2015, 11:09 
Не в мережі

Повідомлень: 2
yarko, напишіть послідовний приклад для blockSize = 16 (байт) з конкретними даними:
тобто, наприклад,
на вході
234A4F67B723323D4C56A37810984B11
і послідовно біт в біт опишіть що звідки і як береться.

Як вас уже просили:
Olgerd писал(а):
Або опишіть алгоритм мат.формулами та детальним прикладом.

Код:
Наприклад, є рядок 000...000, ключ 111...111,
і т.д. і т.п.
В результаті отримаємо 0435F4A9...F988.


без фраз
Цитата:
д) Оновлюємо значення масиву T. Цикл по j від 0 до subBlockCount-1 включно.


Повернутися наверх
  
 
 Заголовок повідомлення: Re: KGV
СообщениеДодано: 11 бер 2015, 11:32 
Не в мережі

Повідомлень: 2
З "опису":
Отримаємо змінну tables довжиною 128 байт. випадкова (відома)
тримаємо змінну text довжиною 64 байт. випадкова (відома)
Отримаємо змінну block. 64 байти відкритого тексту. (відома)

подаємо block, tables і text в функцію encrypt. На виході отримаємо шифротекст розміром 64 байти (змінна block).
(звертаю увагу що THash не бере участі в функції шифрування, використовуються тільки 3 таблиці - 2 випадкові, та 1- відкритий текст.)

Тобто якщо відомий ключовий файл (а вище було сказано що QKGVKey - це випадкові дані з флуктуацій густини електронного газу) то що тоді знайти?
Номер позиції у випадковому файлі?


Повернутися наверх
  
 
 Заголовок повідомлення: Re: KGV
СообщениеДодано: 11 бер 2015, 15:01 
Не в мережі

Повідомлень: 24
Ок. Приклад
Відкритий текст 1.txt
QKGVKey - файл data.kgvkey (є у викладених сорцях)
QKGVLib - файл qkgvlib1.cpp (в сорцях)
QKGVHash - звичайний MD5 (теж є в сорцях)
пароль - yarko

Значення змінних при покроковому виконанні - в файлі debug.txt
Шифротекст - в файлі 1.txt.kgv1
Шифротексти чотирьох інших сеансів при тих самих вхідних параметрах - в файлах 1.txt.kgv2 1.txt.kgv3 1.txt.kgv4 1.txt.kgv5

Якщо і це не допоможе зрозуміти алгоритм, тоді я не знаю що допоможе >>:(
Хіба стукнути в аську і я по кожному рядку поясню. 415331848
Строгі математичні описи складати це не моє.


Вкладення:
debug.rar [2.42 KiB]
Скачали: 87
Повернутися наверх
  
 
Показати повідомлення за:  Сортувати по:  
Розпочати нову тему Відповісти  [ 53 повідомлень ]  На сторінку 1, 2, 3  Наст.

Часовий пояс: UTC десь + 2 години



cron
Роwеrеd bу рhрВB® аnd Hostinger web hosting