Strong code obfuscation algorithms and their applications  Page description

Help  Print 
Back »

 

Details of project

 
Identifier
116675
Type K
Principal investigator Buttyán, Levente
Title in Hungarian Erős kód obfuszkációs algoritmusok és alkalmazásaik
Title in English Strong code obfuscation algorithms and their applications
Keywords in Hungarian VBB obfuszkáció, iO obfuszkáció, statikus program analízis, attribútum alapú rejtjelezés, bizonyítható biztonság
Keywords in English VVB obfuscation, iO obfuscation, static program analysis, attribute based encryption, provable security
Discipline
Information Technology (Council of Physical Sciences)100 %
Ortelius classification: Informatics
Panel Informatics and Electrical Engineering
Department or equivalent Department of Networked Systems and Services (Budapest University of Technology and Economics)
Participants Horváth, Máté
Vajda, István
Starting date 2015-09-01
Closing date 2019-12-31
Funding (in million HUF) 28.256
FTE (full time equivalent) 5.22
state closed project
Summary in Hungarian
A kutatás összefoglalója, célkitűzései szakemberek számára
Itt írja le a kutatás fő célkitűzéseit a témában jártas szakember számára.

Az obfuszkászkáció egy lehetséges formális megközelítése a "megkülönböztethetetlenség obfuszkáció" (iO). Informálisan egy obfuszkátort akkor nevezünk iO-nak, ha 1) megőrzi a program eredeti funkcionalitását, 2) a futásidő az eredeti polinomja marad, 3) két közel azonos méretű, funkcionalitásukban ekvivalens program obfuszkált változata egymástól megkülönböztethetetlen lesz. Garg et al. [GGH+13] adta az első lehetséges konstrukciót általános célú iO-ra, ami ezután az érdeklődés középpontjába került 3 fő kutatási iránnyal: a biztonság falszifikálható és példány-független feltevésre helyezése, a hatékonyság növelése és alkalmazások keresése. A lehetséges kriptográfiai alkalmazásokon belül, amik primitívként használják az iO-t, elsősorban felhasználó visszavonást is lehetővé tevő attribútum alapú kódolás érdekel minket. A kriptoszövegek újra generálásának terhét csökkenthetné, ha a kódolási eljárásban elkülöníthető és obfuszkálható lenne a visszavonást kezelő paraméterek számítása, így visszavonás után elég lenne ennek a résznek az újraszámolása az egész kriptoszöveg helyett.
Elképzelésünk szerint az iO hatékonysága növelhető lenne különböző feladatokra optimalizálás segítségével.
További kutatási irány annak a kérdésnek a megválaszolása, hogy miként használható iO praktikus számítógépprogramok obfuszkációjára? Ezen a téren az elméleti kutatást és a gyakorlatban felmerülő kérdéseket mindenképen össze kell kapcsolni, mert a jelenleg alkalmazott megoldások nem képesek jól definiált biztonsági garanciákat adni.

Mi a kutatás alapkérdése?
Ebben a részben írja le röviden, hogy mi a kutatás segítségével megválaszolni kívánt probléma, mi a kutatás kiinduló hipotézise, milyen kérdéseket válaszolnak meg a kísérletek.

Az obfuszkáció célja, a programkódban lévő információ elrejtése, oly módon, hogy a program megtartsa eredeti funkcionalitását, vagy más szavakkal a programkód visszafejtésének megakadályozása. A kriptográfiai obfuszkáció kutatásának alapkérdése, hogy kielégíthető-e az obfuszkáció valamely szigorú és praktikus szempontok alapján is értelmes biztonság definíciója. Majd 40 évvel a kérdés felmerülése után, a kérdés máig nyitott, bár az elmúlt 2 év váratlan fejlődést hozott. Sürgető lenne egy konstruktív, pozitív válasz, mert a problémára adott jelenlegi megoldások biztonsága azok titkosságán múlik, ami messze van az elfogadható szinttől. Ha az általános célú obfuszkáció megvalósítható, ahogy ez ma sejthető a „megkülönböztethetetlenség obfuszkációról”, az rengeteg olyan alkalmazás előtt nyithatja meg az utat, mint szoftverek és algoritmusok szerzői jogi védelme, szoftverek vízjelezése, biztonságos szoftverfrissítés stb. A kriptográfiai alkalmazások jelentősége legalább ilyen fontos. Az első pozitív eredmények 2013-as megjelenése óta számos nyitott kérdést válaszoltak meg "megkülönböztethetetlenség obfuszkáció" kriptográfiai primitívként való alkalmazásával. Ilyenek a funkcionális titkosítás, valamint a letagadható és tanú titkosítás első megvalósításai. Kutatásunkal az attribútum alapú kódolást, felhasználó visszavonást, a hatékonyság növelést valamint az eredmények nem-kriptográfiai felhasználását szeretnénk fejleszteni.

Mi a kutatás jelentősége?
Röviden írja le, milyen új perspektívát nyitnak az alapkutatásban az elért eredmények, milyen társadalmi hasznosíthatóságnak teremtik meg a tudományos alapját. Mutassa be, hogy a megpályázott kutatási területen lévő hazai és a nemzetközi versenytársaihoz képest melyek az egyediségei és erősségei a pályázatának!

A szoftverek szerzői jogi védelme az első számítógép program megjelenése óta kérdéseket vet fel. A legnagyobb akadályt az jelenti, hogy a program működését nem szükséges érteni ahhoz, hogy valaki lemásolhassa annak részeit vagy akár a teljes egészet. Ezért a szoftverfejlesztőkre jelentősen nagyobb feladat hárul ezen a téren, mint például a hardware gyártókra, akik kevésbé vannak kitéve ilyen jellegű támadásoknak (bár ők sem teljesen védettek). A programok magas szintű összekapcsolhatósága és a direkt hozzáférés lehetősége különösen sérülékennyé teszik őket rosszindulatú módosításokkal és különféle egyéb támadásokkal szemben. Emiatt nem csak a szoftverfejlesztők, hanem a felhasználók sem érezhetik biztonságban magukat és személyes tartalmaikat. Az obfuszkáció általános megoldást jelentene e problémákra, mivel a programkódokat érthetetlenné tudnánk transzformálni, elfogadható teljesítménycsökkenés mellett, anélkül, hogy az eredeti funkcionalitást megváltoztatnánk. Az obfuszkáció elméleti megalapozásának nehézségei miatt azonban a gyakorlatban különböző heurisztikák terjedtek el, amik az eljárás titkossága mellet próbálnak biztonságot garantálni. Célunk az obfuszkáció stabil elméleti megalapozására épülő, praktikusan is használható obfuszkációs eljárások fejlesztése, melyek kriptográfiai primitívkén használhatók gyakorlati alkalmazásokbnan. Ezek közül kiemeljük a szoftvervédelmet és a biztonságos felhő alapú adattárolást lehetővé tévő az attribútum alapú kódolást.

A kutatás összefoglalója, célkitűzései laikusok számára
Ebben a fejezetben írja le a kutatás fő célkitűzéseit alapműveltséggel rendelkező laikusok számára. Ez az összefoglaló a döntéshozók, a média, illetve az érdeklődők tájékoztatása szempontjából különösen fontos az NKFI Hivatal számára.

Az információ elrejtése az ókor óta foglalkoztatja az embert. Az üzenetek titkosítása sokat kutatott probléma, rengeteg lehetséges megoldással, amik széleskörű alkalmazási lehetőségeket fednek le. Ugyanakkor tudásunk a programkódokban rejlő információ elrejtéséről (amit obfuszkációnak nevezünk) körülbelül az üzenettitkosítás 19. századi szintjén van.
Aki próbált már más által írt forráskódot megérteni, tudja, hogy komoly erőfeszítést igényel, bár ennek mértéke függ a háttérismeretektől. Amikor obfuszkált programot vizsgálunk, azt várjuk, hogy minden egyéb ismerettől függetlenül legyen értelmezhetetlen az olvasó számára. Ennek a követelménynek nem csak kielégítése, de még a formális megfogalmazása is problémát jelent. Az elmúlt évtizedekben, egy bizonyítottan biztonságos eszköz hiánya ellenére is, hatalmas igény jelentkezett, mert a lehetséges alkalmazások olyan fontos területeket érintenek, mint a szerzői jogok és szoftverek védelme vagy kriptográfiai protokollok tervezése. Emiatt különböző heurisztikák váltak elterjedté, amik azonban nem rendelkeznek biztonsági garanciákkal és kivétel nélkül ismert módon sebezhetőek. 2013-ban áttörést jelentett az első pozitív eredmény az általános célú obfuszkátor létezéséről. Habár ez a megvalósítás közvetlenül még nem alkalmazható valós problémák megoldására, nem elég hatékony és a biztonságát sem értjük még kellőképpen, egyértelmű kutatási irányokat határoz meg. Ehhez a kutatáshoz szeretnénk csatlakozni és hozzájárulni a jól definiált biztonságos obfuszkáció fejlődéséhez, valamint alkalmazásához olyan területeken, mint például a biztonságos felhő alapú adattárolás.
Summary
Summary of the research and its aims for experts
Describe the major aims of the research for experts.

A possible formal approach towards obfuscation, is called "indistinguishability obfuscation" (iO). Informally speaking, a compiler is an iO if it 1) preserves the functionality of the program, 2) causes only a polynomial slowdown, and 3) the obfuscation of two functionally equivalent programs of similar size are indistinguishable from each other. The first candidate construction for general purpose iO was given by Garg et al. [GGH+13], which then became the center of interest with three main lines of research: to base the security on a falsifiable and instance independent assumption, to increase efficiency and to find applications. Within the possible cryptographic applications, that use iO as a primitive, our interest is attribute-based encryption with user revocation feature, in which the ciphertex re-generation burden could be significantly decreased by dividing and obfuscating that part of encryption which computes revocation related values, making it possible to regenerate only this small part, instead of the whole. We also envision the improvement of iO’s efficiency, by customizing it to specific tasks. An other direction of our research is to answer the question: how can we make use of iO outside cryptography, for obfuscating practical computer programs? In this area, we need to connect the theoretical research with the practical questions, as the currently used techniques cannot guarantee well defined security.

What is the major research question?
Describe here briefly the problem to be solved by the research, the starting hypothesis, and the questions addressed by the experiments.

The goal of obfuscation is to hide information, necessarily embedded in a program code, such that the program
keeps its original functionality or with other words obfuscation aims to make reverse engineering impossible. The basic question of research on cryptographic obfuscation is whether it is possible to satisfy a rigorous, but at the same time meaningful definition of obfuscation security. Almost 40 years after the question has arisen, it is still open, although the past 2 years, brought unexpected advances. A constructive, positive answer, is compelling, as current solutions for the problem can only offer security via obscurity that is a far cry from the acceptable level of security. If general purpose obfuscation is achievable, as we suspect it now for a specific definition, namely "indistinguishability obfuscation", than it could open the way for plenty of applications as intellectual property protection for software and algorithms, watermarking of software, secure software patching etc. The importance of cryptographic applications are at least as big as the previous one's. Since the the first positive result in 2013, several open problems were answered, using indistinguishability obfuscation as a primitive, such as the first realization of functional encryption, deniable encryption and witness encryption. Our research aims at promoting attribute-based encryption, user revocation, efficiency of different schemes and non-cryptographic exploitation of theoretic results.

What is the significance of the research?
Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field.

Protection of intellectual property rights related to software have been an issue since the appearance of the first computer program. The main obstacle is that in case of a software, one does not need to understand the operation of a product in order to be able to copy parts of it or even the whole. This turns out to be a serious drawback in the protection of products and serious efforts have to made by software engineering, in contrast to hardware manufacturers who are less exposed to (although not free from) these kind of attacks. Together with the high level of connectivity, direct accessibility of computer programs makes them extremely vulnerable of malicious modification and various other attacks. It follows that not only software developers, but even the users cannot feel safe, because their private contents are also exposed to attack. One potential solution to the problem is obfuscating software before its distribution. However, because of the difficulties of the theoretical foundations of obfuscation, in practice, various heuristics spread, which only provide low level of security. We aim at following firm theoretical foundations, and on top of them, proposing affordable practical implementations for obfuscation that can help to improve software protection and cloud based services.

Summary and aims of the research for the public
Describe here the major aims of the research for an audience with average background information. This summary is especially important for NRDI Office in order to inform decision-makers, media, and others.

Hiding information has always been important in various applications. To hide the content of messages is a well-studied problem, for which we have enormous amount of possible solutions which fit in a wide range of application scenarios. At the same time, our knowledge about hiding information embedded in program codes (i.e. code obfuscation), is still on the level of 19th century message encryption methods. Whoever once tried to understand a program code of someone else, knows that it always require effort from the code reader, although this effort is is not equal for readers with different knowledge. However, when we obfuscate a program, we expect it to be unintelligible, independently from background knowledge. This requirement turned out to be hard, not only to satisfy, but also to capture formally. In spite of the lack of a provably secure tool, in the last decades the demand for obfuscation became huge, because of applications such as intellectual property and software protection or building secure cryptographic protocols. That is why in practice, various heuristics became widespread, which fail to achieve certain security guarantees. Finally in 2013, a breakthrough happened, when the first positive result appeared about general purpose obfuscation. Although this solution cannot be applied directly to real-word problems, as it is not yet efficient enough, it determines a clear line of research. We intend to join this research line and contribute to the improvement of obfuscation with well-defined security, and apply our results, among other things, to secure cloud-based data sharing and storage.





 

Final report

 
Results in Hungarian
A projektben azt vizsgáltuk, hogy a programok obfuszkációjával kapcsolatos legújabb elméleti eredményeket lehetővé tévő módszerek mennyiben használhatók fel gyakorlati problémák megoldására is. Munkánk során összegyűjtöttük és rendszereztük ezeket a módszereket, majd az egyik alapvető fontosságú technika, a funkcionális titkosítás alkalmazhatóságával foglalkoztunk. Eredményeink két terület köré csoportosultak. Adatpiacok biztonságához kapcsolódóan olyan protokollokat (és a biztonságuk értékelését szolgáló keretrendszert) dolgoztunk ki, melyek lehetővé teszik két fél–egy adatokat áruló bróker és egy, a saját algoritmusához (pl. gépi tanulási modellhez) adatot vásárló szolgáltató–számára a függvény közös kiértékelését. Mindezt úgy, hogy a résztvevőknek nem szükséges felfedniük egymás előtt a függvényt valamint az inputot, sőt annak esetleg érzékeny részinformációit sem. Egy teljesítmény és biztonság közti praktikus kompromisszum segítségével egyes esetekben jelentős hatékonyság növelést értünk el a korábbi, részinformációkat nem védő protokollokhoz képest. A biztonságos felhőszolgáltatások területén elért fő eredményünk, egy olyan rejtjelező eljárás, mely a tikosított adatbázisban kulcsszavak korlátozott kereshetőségét teszi lehetővé. Amikor valamely publikus metaadat ismerete miatt a teljes adatbázis helyett elegendő annak egy részhalmazában keresni, módszerünk lehetővé teszi a titkosított adatbázis, általában komplex bővítésének drasztikus leegyszerűsítését és felgyorsítását.
Results in English
The goal of the project was to investigate the practical applicability of the immense number of new ideas that emerged from the recent theoretical investigation of the problem of program obfuscation. We gathered and systematized the relevant results and concentrated on the applications of a key ingredient of obfuscator constructions, namely functional encryption (FE). Our results are concentrated around two problems: the security of data markets and the flexibility of secure data storage. For data markets, we devised protocols (and a framework to assess their security) that enable two parties – a broker who is selling data and an owner of some function or algorithm (e.g. a machine learning model) seeking after input data – to jointly evaluate the function on the given input(s) while maintaining the privacy of both the function and any sensitive partial information about the input data. Some of our protocols introduce a new efficiency—security trade-offs leading to significant performance improvements over solutions that cannot hide partial information about the data. Regarding the other field, our main result is a searchable symmetric encryption algorithm that was designed for restricted search, i.e. when some public metadata can narrow the database in which we search. In these scenarios, our solution eliminates the complex methods of other solutions for adding new elements to the database.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=116675
Decision
Yes





 

List of publications

 
Máté Horváth, Levente Buttyán: Cryptographic Obfuscation: A Survey, Springer Briefs in Computer Science, ISBN 978-3-319-98040-9, 2020
Máté Horváth, Levente Buttyán, Gábor Székely, Dóra Neubrandt: There Is Always an Exception: Controlling Partial Information Leakage in Secure Computation, J. H. Seo (Ed.): Information Security and Cryptology - ICISC 2019, LNCS 11975, pp. 1–17, 2020
Máté Horváth, Levente Buttyán, Gábor Székely, Dóra Neubrandt: There Is Always an Exception: Controlling Partial Information Leakage in Secure Computation, Under review, 2019
Máté Horváth, István Vajda: Searchable Symmetric Encryption for Restricted Search, Journal of Communications Software and Systems, 14(1):104–111, 2018, 2018
Máté Horváth: Programok titkai - A kriptográfiai obfuszkáció születése, Élet és Tudomány, ISSN 0013-6077, 2018. (73. évf.), 34. sz., 1065-1067. p., 2018
Máté Horváth, Levente Buttyán: Controlled Private Function Evaluation from Functional Encryption, Technical report, 2018
Horváth Máté, Buttyán Levente: The Birth of Cryptographic Obfuscation - a survey, online working paper, 2016
Máté Horváth, István Vajda: Searchable Symmetric Encryption: Sequential Scan Can Be Practical, The 25th International IEEE Conference on Software, Telecommunications and Computer Networks - Symposium on Security and Digital Forensics, 2017
Horváth Máté, Buttyán Levente: The Birth of Cryptographic Obfuscation - a survey, submitted to ACM Computing Surveys, 2017
Máté Horváth, István Vajda: Searchable Symmetric Encryption for Restricted Search, Journal of Communications Software and Systems, Volume 14, No 1, 2018
Máté Horváth, Levente Buttyán: Problem Domain Analysis of IoT-Driven Secure Data Markets, Gelenbe E. et al. (eds) Security in Computer and Information Sciences. Euro-CYBERSEC 2018. CCIS, vol. 821 (pp 57-67), Springer., 2018
Máté Horváth: Programok titkai - A kriptográfiai obfuszkáció születése, Élet és Tudomány, ISSN 0013-6077, 2018. (73. évf.), 34. sz., 1065-1067. p., 2018
Máté Horváth, Levente Buttyán: Controlled Private Function Evaluation from Functional Encryption, (under review), 2018
Horváth Máté, Buttyán Levente: Cryptographic Obfuscation: A Survey, SpringerBriefs in Computer Science, ISBN 978-3-319-98040-9, 2019





 

Events of the project

 
2015-08-25 20:00:07
Résztvevők változása




Back »