6th Crypto.Sec Day

Monday 18.07.2016

Department of Informatics, University of Athens

Room A56, first floor (conference room)

Schedule

Title. Foundations of Blockchain Protocols

Abstract. The rise of bitcoin and other cryptocurrencies puts forth a wealth of interesting problems in distributed systems and cryptography that relate to building decentralized systems. In this talk, we discuss what is the exact problem that the bitcoin protocol solves and then go on to investigate whether and in what ways the protocol can be improved. The protocol itself will be abstracted in a simple algorithmic form, termed as the bitcoin backbone, and subsequently provable properties like chain quality, common prefix and chain growth will be detailed. The concept of a robust transaction ledger will be defined, as captured by two basic properties, persistence and liveness. Alternatives to the main protocol such as GHOST will be overviewed as well as the relation of the defined properties and protocols to the consensus problem.

10:50 - 11:30 Vasilis Zikas (Rensselaer Polytechnic Institute)

Title. Provably Secure Virus Detection: Using The Observer Effect Against Malware

Abstract. Protecting software from malware injection is one of the biggest challenges of modern computer science. Despite intensive efforts by the scientific and engineering community, the number of successful attacks continues to increase.

This work sets first footsteps towards a provably secure investigation of malware detection. We provide a formal model and cryptographic security definitions of attestation for systems with dynamic memory, and suggest novel provably secure attestation schemes. The key idea underlying our schemes is to use the very insertion of the malware itself to allow for the systems to detect it. This is, in our opinion, close in spirit to the quantum Observer Effect. The attackers, no matter how clever, no matter when they insert their malware, change the state of the system they are attacking. This fundamental idea can be a game changer. And our system does not rely on heuristics; instead, our scheme enjoys the unique property that it is proved secure in a formal and precise mathematical sense and with minimal and realistic CPU modification achieves strong provable security guarantees. We envision such systems with a formal mathematical security treatment as a venue for new directions in software protection.

This is joint work with Richard J. Lipton and Rafail Ostrovsky.

11:30 - 11:45 Break

11:45 - 12:25 Helger Lipmaa (University of Tartu)

Title. Non-interactive Zero-Knowledge Proofs and Applications

Abstract. One way to guarantee security against malicious voting servers is to use NIZK shuffle arguments. Up to now, only two NIZK shuffle arguments

in the CRS model have been proposed. Both arguments are relatively

inefficient compared to known random oracle based arguments. We

propose a new, more efficient, shuffle argument in the CRS model.

Importantly, its online prover's computational complexity is dominated

by only two (n+1) -wide multi-exponentiations, where n is the number

of ciphertexts. Compared to the previously fastest argument by Lipmaa

and Zhang, it satisfies a stronger notion of soundness. We also

discuss some ongoing work.

12:25 - 13:00 Thomas Zacharias

Title. Post DEMOS e-voting: subsequent work and future directions

Abstract. The DEMOS and DEMOS-2 e-voting systems enabled for the first time end-to-end verifiability of the election procedure in the standard model. As a result, the two systems set the bar high for the e-voting security standards. Nonetheless, both DEMOS and DEMOS-2 do not manage to face all technical challenges while their security analysis leads to findings that stimulate further research. In this talk, we discuss at a high level a list of the most interesting topics that emerged from the study of DEMOS and DEMOS-2, focusing on each topic's current resolution status and the prospect of it as future research direction. In particular, we will discuss

(i) end-to-end verifiable fully coercion resistant e-voting

(ii) end-to-end verifiable multi-party computation

(iii) the minimality of assumptions for end-to-end verifiability

(iii) e-voting accountability in the standard model

(v) the boundaries of optimal e-voting security.

13:00 - 14:00 Pizza, Drinks and Coffee

14:00 - 14:30 Katerina Samari

Title. Watermarking Cryptographic Functionalities

Abstract. Watermarking objects like pictures, video etc. is usually achieved by embedding a small piece of information into the object, so that it is difficult for an attacker to remove without damaging the object itself. This idea extends to program/circuit watermarking, where the marking information is embedded in such a way, so that on the one hand it does not alter the behaviour of the program and on the other hand is still difficult to be removed by an adversary without significantly altering the functionality of the program.

The first formal security definitions for watermarking objects were given in Hopper et al.[HMW07]. Barak et al. [BGI+12] considered software watermarking and showed that if a marked circuit has exactly the same functionality as the original one, then under the assumption of indistinguishability obfuscation (iO), watermarking is impossible. Nishimaki in [Nis13], inspired by the work of [HMW07], formalized the properties of watermarking cryptographic functions to be: correctness, preserving functionality, unremovability and unforgeability. Moreover, [Nis13] presented a watermarking scheme for specific lossy-trapdoor functions that unfortunately turned out to be vulnerable to the attack described in [BGI+12] (it requires the marked function to preserve perfectly the functionality of the original one). Recently, Cohen at al. [CHN+16] gave a watermarking scheme for puncturable PRFs which avoids the impossibility result of [BGI+12] by allowing statistical correctness, i.e. the marked PRF is allowed to behave differently in a negligible fraction of inputs, comparing to the initial one. The construction suggested in [CHN+16] is based on iO, allows public key detection and is provably secure against unremovability. However, [CHN+16] left two important open questions: (1) constructing a scheme that is also unforgeable, and (2) removing the admittedly strong iO assumption. In this work, we answer both these questions affirmatively. We start by proposing a new version of watermarking definitions for cryptographic functionalities and we suggest a watermarking scheme for public key encryption. Although in a more relaxed model, our construction avoids using iO and achieves both unremovability and unforgeability based on PRF security and IND-CPA security. Joint work with Foteini Baldimtsi and Aggelos Kiayias.

14:30 - 15:00 Yiannis Tselekounis

Title. Blockchain Mining Games

Abstract. We study the strategic considerations of miners participating in the

bitcoin's protocol. We formulate and study the stochastic game that

underlies these strategic considerations. The miners collectively

build a tree which consists of a long path and potentially short

branches out of it, and they are paid when they create (mine) a node

which will end up in the main path. Since the miners can hide newly

mined nodes, they play a game with incomplete information. Here we

consider two simplified forms of this game in which the miners have

complete information. In the simplest game the miners release every

mined block immediately, but are strategic on which blocks to

mine. In the second more complicated game, when a block is mined it

is announced immediately, but it may not be released so that other

miners cannot continue mining from it. A miner not only decides

which blocks to mine, but also when to release blocks to other

miners. In both games, we show that when the computational power of

each miner is relatively small, their best response matches the

expected behavior of the bitcoin designer. However, when the

computational power of a miner is large, it will deviate from the

expected behavior, and other Nash equilibria arise.

15:00 - 15:15 Short Talks

Title. Short presentations by students preparing their undergraduate or Master’s thesis.

-Christos Kasketis: Stealing your ISP's super weapons.

Abstract. In the growing field of internet-operated devices, services and business worldwide, it is essential to keep control. Modern ISPs use some hidden weapons, which allow them to remotely manage the home networking devices that they provide to their subscribers. In this short presentation we will reveal one of those weapons and will also describe how an attacker can take advantage of it to create a powerful botnet.

-Orfeas Litos: Decentralized trust network

Abstract: Economic trust is a concept that becomes increasingly important in today's connected world. However, until today it has not been quantified, apart from star-based systems. In this project we study a new kind of network in which trust is based on explicitly risking money to friends. The max-flow algorithm is used to calculate indirect trust. The system is inherently decentralized, non Sybil attackable and obviates the need for star or review-based trust.

-Konstantinos Andrikopoulos, Dimitris Kolotouros: Multi-party end-to-end encrypted chat.

Abstract. End-to-end encrypted chat via the off-the-record (OTR) chat platform solves the secure messaging problem in practice. However, end-to-end encrypted chat applications in the group setting have been limited. In

this work, we introduce an open source implementation of a multi-party

extension to the OTR platform (mpOTR) which allows groups to talk

securely end-to-end. We provide a production-grade portable

implementation of Goldberg's et. al. mpOTR for libotr in C and a

plugin for Pidgin which allows the mpOTR protocol to work over any

underlying chat protocol. In this short talk, we present a demo of our

implementation illustrating the key exchange, the group conversation

establishment, the exchange of group messages achieving

confidentiality, authentication, deniability and forward secrecy, and

the conclusion of a conversation.

15:15 - 15:30 Break

15:30 - 16:00 Dimitris Karakostas, Eva Sarafianou, Dionysis Zindros

Title. Compression side-channel attacks

Abstract. When compression is composed with encryption, unexpected

vulnerabilities can arise. Such vulnerabilities have been explored in

practical attacks against TLS such as CRIME, TIME and BREACH. Our

contributions are two-fold. First, we introduce an abstract

theoretical model for such attacks, the adaptive reflection security

model. We discuss what properties common compression functions have,

such as the compression-detectability of predicates, and we show that

all length-preserving encryption schemes are vulnerable when composed

with such functions. Second, we provide a modular scalable open-source

production-grade generic attack framework where these attacks are

implemented in a robust manner. In this talk, we will show an overview

of the theoretical model and present a demo of some live compression

side-channel attacks against TLS.

16:00 - 17:00 George Argyros (Columbia University)

Title. Symbolic Automata Inference: New Algorithms and Applications

Abstract. We tackle the problem of analyzing filter and sanitizer programs remotely, i.e. given only the ability to query the targeted program and observe the output. We focus on two important and widely used program classes: regular expression (RE) filters and string sanitizers. We demonstrate that existing tools from machine learning that are available for analyzing RE filters, namely automata learning algorithms, require a very large number of queries in order to infer real life RE filters. Motivated by this, we develop the first algorithm that infers symbolic representations of automata in the standard membership/equivalence query model. We show that our algorithm provides an improvement of x15 times in the number of queries required to learn real life XSS and SQL filters of popular web application firewall systems such as mod-security and PHPIDS. % Active learning algorithms require the usage of an equivalence oracle, i.e. an oracle that tests the equivalence of a hypothesis with the target machine. We show that when the goal is to audit a target filter with respect to a set of attack strings from a context free grammar, i.e. find an attack or infer that none exists, we can use the attack grammar to implement the equivalence oracle with a single query to the filter. Our construction finds on average 90% of the target filter states when no attack exists and is very effective in finding attacks when they are present. For the case of string sanitizers, we show that existing algorithms for inferring sanitizers modelled as Mealy Machines are not only inefficient, but lack the expressive power to be able to infer real life sanitizers. We design two novel extensions to existing algorithms that allow one to infer sanitizers represented as single-valued transducers. Our algorithms are able to infer many common sanitizer functions such as HTML encoders and decoders. Furthermore, we design an algorithm to convert the inferred models into BEK programs, which allows for further applications such as cross checking different sanitizer implementations and cross compiling sanitizers into different languages supported by the BEK backend. We showcase the power of our techniques by utilizing our black-box inference algorithms to perform an equivalence checking between different HTML encoders including the encoders from Twitter, Facebook and Microsoft Outlook email, for which no implementation is publicly available.

17:00 --- ... Wine, Beer and Cheese.