Effective cryptographic protocols on devices with limited computational power and memory

Jednym z najbardziej rozpowszechnionych i zarazem najmocniejszych modeli w kryptografii odpornej na wycieki jest tzw. Bounded Retrieval Model (BRM). Niestety, zastosowanie BRM wymaga poswiecenia duzej przestrzeni dyskowej na samo przechowywanie klucza kryptograficznego. Ze wzgledów bezpieczenstwa, tajny klucz w tym modelu musi by wiekszy niz przyjety parametr wycieku (tj. górne ograniczenie ilosci informacji jakie przeciwnik moze pozyskac na temat klucza). Chcac zastosowac model BRM w praktyce, parametr ten musi byc rzedu kilku gigabajtów. Zazwyczaj klucz kryptograficzny to losowy ciag binarny, który nie ma innego, poza kryptografia, zastosowania. Oczywiscie, mozna stwierdzic, ze przeznaczenie kilku gigabajtów przestrzeni dyskowej w celu zapewnienia bezpieczenstwa nie stanowi wiekszego problemu dla współczesnych komputerów. Z drugiej jednak strony, kilka gigabajtów wolnej przestrzeni jest iloscia bardzo duza dla urzadzen mobilnych, takich jak smartfony czy tablety. W tej pracy pokazujemy jak mozna obejsc te przeszkode poprzez wygenerowanie bezpiecznego klucza BRM-owego ze zmiennej losowej o niejednostajnym rozkładzie. Pokazujemy równiez, ze taka zmienna losowa moga byc dane przechowywane przez uzytkownika urzadzenia. W pracy pokazujemy jak pozyskac bezpieczny klucz kryptograficzny (w modelu BRM) z danych uzytkownika takich jak zdjecia z wakacji, nagrane filmy, czy przechowywane dokumenty. Takie podejscie ma zasadnicza zalete – nie musimy juz przeznaczac gigabajtów przestrzeni dyskowej na klucz kryptograficzny, mozemy go wygenerowac z tego, co i tak przechowujemy na dysku. Przedstawiona w pracy procedura pozyskiwania klucza zapewnia prywatnosc danych w bardzo mocnym sensie. Pokazujemy, ze nawet ktos, kto zna cały klucz, nie moze powiedziec nic o danych, które posłuzyły do jego wygenerowania (poza informacjami pozyskanymi w ramach wycieku). Ponadto, zaproponowana procedura działa dla wielu schematów w modelu BRM poprzez zwykłe podmienienie jednostajnego klucza na klucz pozyskany za pomoca kdf. Oczywiscie, klucz pozyskany z danych niejednostajnych nie jest tak bezpieczny jak klucz pozyskany z rozkładu jednostajnego. Pokazujemy jednak, ze strata bezpieczenstwa jest zaniedbywalna (w stosunku do parametru bezpieczenstwa). Podobnie jak w Dodis i in., nazywamy nasza procedure key derivation function (kdf). W odróznieniu jednak od Dodisa i in., zapewniamy nie tylko bezpieczny klucz kryptograficzny z niejednostajnej zmiennej losowej, ale takze prywatnosc danych słuzacych do jego wygenerowania. Mozliwosc generowania klucza z danych prywatnych jest zasadniczym wkładem przedstawianej pracy. W pracy pokazujemy konkretny przykład kdf oparty na grafach tzw. disperserach (w zwiazku z tym nazywamy nasza funkcje Disperse). Zaproponowana funkcja posiada bardzo istotna własnosc, mianowicie jest lokalna. Protokoły kryptograficzne w modelu BRM zwykle nie uzywaja całego dostepnego klucza. Poniewaz jest on bardzo duzy, próba operowania na jego całosci byłaby skazana na całkowita porazke z punktu widzenia wydajnosci. W zamian, za kazdym razem, kiedy klucz jest potrzebny, losowana jest pewna jego czesc, która zostaje nastepnie uzyta. W celu zapewnienia funkcji Disperse wydajnosci, zaprojektowana została ona w sposób, który pozwala na obliczenie tylko wybranego fragmentu klucza, bez potrzeby generowania go w całosci. Ponadto, obliczenie czesci klucza nie wymaga dostepu do całosci danych dyskowych a tylko pewnego ich fragmentu. Po zaproponowaniu przykładu funkcji kdf, pokazujemy pewne jej zastosowania praktyczne. Pokazujemy protokoły uwierzytelniania i podpisu cyfrowego oparte na tzw. drzewach Merkla. Choc protokoły te sa znane od dłuzszego czasu, dowodzimy, ze sa one bezpieczne nawet w obecnosci wycieku. Zaznaczmy, protokoły, które nadaja sie do stosowania w modelu BRM z funkcja kdf musza spełnic pewne warunki. Po pierwsze, protokół musi działac w modelu kryptografii asymetrycznej. W przypadku protokołu symetrycznego, kazda z osób bioraca udział w obliczeniach musi współdzielic prywatny klucz z kazda inna osoba. Poniewaz prywatne klucze w modelu BRM maja wielkosc kilku gigabajtów, oznacza to, ze kazda ze stron musi przechowywac wiele kilkugigabajtowych kluczy. Niewydajnosc pamieciowa takiego rozwiazania skazuje go na porazke. Po drugie, w przypadku kryptografii klucza publicznego, klucz publiczny musi byc istotnie mniejszy od klucza prywatnego. Wynika to z tego, ze w protokole asymetrycznym kazda ze stron bioraca udział w obliczeniach musi przechowywac wszystkie klucze publiczne. Jesli sa one duze, schemat jest pamieciowo niewydajny i skazany na porazke. W pracy pokazujemy, ze zaproponowane schematy zapewniaja obie własnosci. Czesc rozprawy (definicja i własnosci funkcji Disperse) powstała na podstawie pracy autorstwa Konrada Durnogi, Stefana Dziembowskiego, Tomasza Kazany, Michała Zajaca i Macieja Zdanowicza Bounded-Retrieval Model with Keys Derived from Private Data.

One of the most important and powerful leakage resiliency model, the Bounded Retrieval Model (BRM) comes with inevitable space inefficiency caused by a requirement on a cryptographic secret key to be huge, multiple times larger than a leakage bound. Since practical applications demand amount of leakage to be counted in gigabytes, the secret key has to be that large as well. A cryptographic key is usually a long bitstring taken from a uniform distribution. This bitstring occupies gigabytes of disk space and has no other than cryptographic application whatsoever. Although sacrificing such a big amount of memory for sake of security is acceptable for computers, it is usually too much for mobile devices, like tablets or smartphones. In this thesis we show how to omit this obstacle by deriving a secure cryptographic key in BRM directly from a random variable picked from a non-uniform distribution. We claim that user’s private data can be viewed as such random variable. More precisely, we derive a secure cryptographic key from data the user already store on her device. This approach comes with a great advantage — (almost) no additional space is needed to keep the key. Moreover, we ensure that the data remains private in a very strong sense. That is, even someone equipped with the derived key, can say nothing about the underlying data, except information she learnt through leakage. We claim that the delivered procedure fits many known BRM schemes with no modification to the scheme at all. We call our primitive key derivation function (kdf), exactly as in Dodis et al.. However, we point out that kdf-s as proposed in Dodis et al. allow only to construct a key from non-uniform data, but do not ensure data privacy, what is the major contribution of this thesis. We show an exemplary instantiation of kdf based on disperser graphs (hence we call our function Disperse). The proposed function has an important additional property, called locality. Since a BRM key is large, BRM primitives usually do not use the entirety of it, but some (randomly) picked parts.. To assure efficiency of our function, we designed it in a way that allows to compute only some required part of the key. Furthermore, to compute a part of the key, it is enough to use only a part of the disk data. Having kdf proposed, we show some of its applications. We deliver identification and signature schemes based on Merkle trees. Although constructions based on Merkle trees are well known, we show that they remain secure even under leakage. We point out here that the proposed schemes have to fulfill two requirements. Firstly, they have to be asymmetric. In symmetric primitives, all parties participating in the protocol have to share with each other secret keys. Since BRM keys are a few gigabytes large, that would mean a huge disk-space inefficiency. Secondly, even if we use asymmetric scheme, we have to guarantee that public keys are short compared to secret keys. Otherwise, the problem with disk space arises again, because the parties has to keep each others large public keys. We show in this work that the proposed schemes fulfill both requirements. Part of this thesis (definition of Disperse and its properties) is based on article Bounded- Retrieval Model with Keys Derived from Private Data by Konrad Durnoga, Stefan Dziembowski, Tomasz Kazana, Michał Zajac, and Maciej Zdanowicz.