Просторово-часовий компроміс

Просторово-часова домовленість (англ. space–time, time–memory tradeoff, TMTO) — ситуація в інформатиці, коли можна зменшити використання пам'яті ціною вповільнення швидкості виконання програми (і, навпаки, можна зменшити час обчислення за рахунок використання більшого об'єму пам'яті).

Приклади використання

Таблиці пошуку

Багато задач пошуку, таких як задача пакування рюкзака, задача про дискретний логарифм або задача обернення односторонньої функції, що розв'язуються, по суті, перебором, одночасно дозволяють використання так званих таблиць пошуку. Ідея така: замість того, щоб, без використання додаткової пам'яті, перебрати всі можливі значення, зробити певні попередні обчислення і зберегти їх у таблиці, яку потім використовувати під час розв'язання задач.

Стиснуті замість нестиснутих даних

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

Повторне промальовування замість збереження зображень

Збереження лише LaTeX-сирців і відтворення зображення кожний раз при запиті сторінки було б виграшем пам'яті за ціну збільшення часу обробки. Відтворення зображення при зміні сторінки і збереження його було б виграшем в швидкості обробки запитів за ціну пам'яті.

Менший код замість розмотування циклу

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

Криптографія

В цьому розділі розглянемо класичний приклад використання підходу просторово-часової домовленості в криптографії — застосування таблиць пошуку в розв'язанні криптографічної проблеми обернення криптографічної геш-функції.

Криптоаналітичний перебір вимагає значних обчислювальних затрат. У випадку, якщо потрібне багаторазове злам криптосистеми, логічно було б заздалегідь виконати вичерпний перебір і зберігати обчислені значення в пам'яті. Тоді, в подальшому, можна здійснювати перебір практично миттєво. Втім, цей метод не застосовується в дійсності через надвеликі затрати пам'яті.

Метод, запропонований Геллманом

1980, Мартін Геллман запропонував компромісний підхід до проблеми криптоаналізу, що дозволяв аналіз криптосистеми, яка мала ${\displaystyle N}$ ключів, за ${\displaystyle N^{2/3}}$ операцій, із затратами по пам'яті також ${\displaystyle N^{2/3}}$. Це стає можливим по тому, як одноразово буде виконане попереднє отримання можливих ключів, яке потребує ${\displaystyle O(n)}$ операцій.

Ідея полягає в наступному.

Нехай в алгоритмі шифрування використовується одностороння функція ${\displaystyle ~S_{k_{i}}(P)}$. За властивостями односторонньої функції отримання використаного ключа ${\displaystyle ~k_{i}}$ по відомій парі ${\displaystyle ~P_{0},C_{0}}$ — складна задача, в той час як обчислення функції від певного відкритого тектсу — проста.

Криптоаналітик застосовує атаку на основі підібраного відкритого тексту і отримує один шифротекст ${\displaystyle ~C_{0}}$, відповідний відкритому тексту ${\displaystyle ~P_{0}}$:

${\displaystyle ~C_{0}=S_{k}(P_{0})}$

Задача — знайти ключ ${\displaystyle ~k}$, за допомогою якого здійснювалось шифрування. Для цього треба знайти спосіб обчислення можливих ключів. Введемо функцію редукції ${\displaystyle ~R(C)}$, яка ставить у відповідність шифротексту ${\displaystyle ~C_{i}}$ деякий ключ ${\displaystyle k_{i+1}}$ (довжина ключа, як правило, менша довжини шифртексту, звідси й термін):

${\displaystyle ~R(C_{i})=k_{i+1}}$

Обчислення функції редукції — проста операція. У випадку DES це редукція від 64 до 56 біт, така як відкидання останніх 8 біт шифротексту.

Функція ${\displaystyle ~f=R[S_{k_{i}}(P_{0})]}$ ставить у відповідність ключу ${\displaystyle ~k_{i}}$ інший ключ ${\displaystyle ~k_{i+1}}$. Якщо алгоритм шифрування безпечний, то ${\displaystyle ~f}$ також одностороння функція. Тепер ми можемо отримати як завгодно довгий ланцюжок ключів:

${\displaystyle ~k_{i}{\stackrel {f}{\longrightarrow }}k_{i+1}{\stackrel {f}{\longrightarrow }}k_{i+2}{\stackrel {f}{\longrightarrow }}...}$

Для того, щоб побудувати таблицю пошуку, криптоаналітик вибирає ${\displaystyle ~m}$ випадкових елементів ${\displaystyle SP_{1},SP_{2},...,SP_{m}}$ із простору ключів ${\displaystyle \{1,2,...,N\}}$. З кожного ключа за описаним вище способом отримуємо ланцюжок ключів довжини ${\displaystyle ~t}$. Останній елемент ${\displaystyle i}$-го ланцюжку позначаємо як ${\displaystyle EP_{i}}$, тоді очевидно ${\displaystyle EP_{i}=f^{t}(SP_{i})}$. В пам'ять записуємо лише початковий і кінцевий ключі кожного ланцюжка ${\displaystyle \{SP_{i},EP_{i}\}}$ (пари сортуємо за кінцевим ключем). Таким чином, готова таблиця займає ${\displaystyle O(m)}$ комірок пам'яті.

${\displaystyle {\begin{bmatrix}SP_{1}&=X_{10}{\overset {\underset {\mathrm {f} }{}}{\to }}X_{11}{\overset {\underset {\mathrm {f} }{}}{\to }}X_{12}{\overset {\underset {\mathrm {f} }{}}{\to }}\cdots {\overset {\underset {\mathrm {f} }{}}{\to }}X_{1t}=&EP_{1}\\SP_{2}&=X_{20}{\overset {\underset {\mathrm {f} }{}}{\to }}X_{21}{\overset {\underset {\mathrm {f} }{}}{\to }}X_{22}{\overset {\underset {\mathrm {f} }{}}{\to }}\cdots {\overset {\underset {\mathrm {f} }{}}{\to }}X_{2t}=&EP_{2}\\\vdots &&\vdots \\SP_{m}&=X_{m0}{\overset {\underset {\mathrm {f} }{}}{\to }}X_{m1}{\overset {\underset {\mathrm {f} }{}}{\to }}X_{m2}{\overset {\underset {\mathrm {f} }{}}{\to }}\cdots {\overset {\underset {\mathrm {f} }{}}{\to }}X_{mt}=&EP_{m}\\\end{bmatrix}}}$

Утворення таблиці вимагає ${\displaystyle ~mt}$ операцій.

По отриманні шифротексту кріптоаналітик може застосувати функцію редукції для отримання ${\displaystyle Y_{1}=R(C_{0})=f(K)}$, тоді він може перевірити чи присутній ${\displaystyle Y_{1}}$ серед ${\displaystyle SP}$. ${\displaystyle \{SP_{i},EP_{i}\}}$ зберігаються відсортованими, отже ця операція займе ${\displaystyle log(m)}$, а з використанням геш-таблиці складність можна звести майже до константного часу.

Якщо ${\displaystyle Y_{1}}$ не серед ${\displaystyle EP}$, тоді ${\displaystyle K}$ не в стовпчику ${\displaystyle X_{it}}$. Якщо ${\displaystyle Y_{1}=EP_{i}}$, тоді ${\displaystyle K=X_{i,t-1}}$ або ${\displaystyle EP}$ має більш як один першовзір. Ми називатимемо таку ситуацію хибною тривогою (англ. false alarm). Якщо ${\displaystyle Y_{1}=EP_{i}}$, тоді криптоаналітик обчислює ${\displaystyle X_{i,t-1}}$ і перевіряє чи це ключ, наприклад, через обчислення чи дешифрує він ${\displaystyle C_{0}}$ в ${\displaystyle P_{0}}$. Всі проміжні стовпчики в таблиці були відкинуті для збереження пам'яті, тому криптоаналітик мусить почати в ${\displaystyle SP}$ і переобчислити ${\displaystyle X_{i,1},X_{i,2},\cdots }$ доки він не досягне ${\displaystyle X_{i,t-1}}$.

Якщо ${\displaystyle Y_{1}}$ не кінцева точка або сталась хибна тривога, криптоаналітик обчислює ${\displaystyle Y_{2}=f(Y_{1})}$ і перевіряє на кінцевість її. Якщо це не так, ключ не в ${\displaystyle t-2}$ стовпчику, якщо ж так, тоді криптоаналітик перевіряє чи ключ ${\displaystyle X_{i,t-2}}$. І так далі до 0 стовпчика.

Віднайдення ключа таким чином займає ${\displaystyle ~O(t\cdot log(m))}$; нехтуючи логаріфмічним множником, маємо ${\displaystyle ~O(t)}$. При цьому затрати пам'яті на збереження таблиці становлять ${\displaystyle ~O(m)}$.

Якщо всі елементи в таблиці різні, тоді ймовірність успіху становить ${\displaystyle P(S)=mt/N.}$ Але така ситуація не реалістична через можливість злиття ланцюжків. Якщо ${\displaystyle f}$ є випадковою функцією, що відображає множину ${\displaystyle \{1,2,\cdots ,N\}}$ в себе, і якщо ключ ${\displaystyle K}$ вибрали рівномірно випадково з цієї множини (втім якісна криптосистема повинна бути псевдовипадковим генератором), тоді ймовірність успіху можна обмежити знизу як

${\displaystyle ~P(S)\geq {\frac {1}{N}}\sum \limits _{i=1}^{m}\sum \limits _{j=0}^{t-1}(1-{\frac {it}{N}})^{j+1}}$

Оцінка цього виразу призводить до наступного висліду: добуток ${\displaystyle mt^{2}}$ не варто брати більшим від ${\displaystyle N}$ інакше, швидко падає нижня межа ймовірності успіху.

За ${\displaystyle mt^{2}=N}$ отримаємо

${\displaystyle P(S)\geq 0.8{\frac {mt}{N}}={\frac {1}{t}}}$

Ланцюжки обчислені із різними функціями редукції можуть перетинатись, але не зіллються

Криптоаналітик тепер може утворити не одну, а ${\displaystyle ~l}$ таблиць, в кожній він може вибрати свою функцію редукції (що дозволить уникнути злиття ланцюжків з різних таблиць). При цьому межа успішності розшифрування становитиме:

${\displaystyle ~P(S,l)\geq 1-[{\frac {1}{N}}\sum \limits _{i=1}^{m}\sum \limits _{j=0}^{t-1}(1-{\frac {it}{N}})^{j+1}]^{l}}$

Очікувана кількість хибних тривог на таблицю обмежена

${\displaystyle E(F)\leq mt(t+1)/2N}$

Вибрав ${\displaystyle l=t}$, криптоаналітик отримає затрати ${\displaystyle mt}$ по пам'яти і ${\displaystyle t^{2}}$ по часу (у кожній таблиці використана своя функція редукції, тому при розшифруванні необхідно отримувати свій ланцюжок для кожної таблиці) при ймовірності успіху близької до одиниці. Взяв ${\displaystyle t=m=N^{1/3}}$, отримаємо потрібні затрати ${\displaystyle N^{2/3}}$ по часу і пам'яті.

Примітки

1. Martin E. Hellman. A Cryptanalytic Time-Memory Trade-Off. // Transactions on Information Theory. — July 1980. — № 4.
2. Philippe Oechslin. Making a Faster Cryptanalytic Time-Memory Trade-Off. // .

Посилання

• Martin Hellman — A Cryptanalytic Time-Memory Trade-Off [ 4 березня 2016 у Wayback Machine.]
• Philippe Oechslin — Making a Faster Cryptanalytic Time-Memory Trade-Off [Архівовано 27 лютого 2012 у WebCite]
• Mark Stamp — Once Upon a Time-Memory Tradeoff. [ 5 жовтня 2021 у Wayback Machine.]