Cyber Security Cryptography and Machine Learning

Shlomi Dolev

Sachin Lodha (Eds.)

123

LNCS 10332

First International Conference, CSCML 2017

Beer-Sheva, Israel, June 29–30, 2017

Proceedings

Cyber Security

Cryptography and

Machine Learning

Lecture Notes in Computer Science 10332

Commenced Publication in 1973

Founding and Former Series Editors:

Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen

Editorial Board

David Hutchison

Lancaster University, Lancaster, UK

Takeo Kanade

Carnegie Mellon University, Pittsburgh, PA, USA

Josef Kittler

University of Surrey, Guildford, UK

Jon M. Kleinberg

Cornell University, Ithaca, NY, USA

Friedemann Mattern

ETH Zurich, Zurich, Switzerland

John C. Mitchell

Stanford University, Stanford, CA, USA

Moni Naor

Weizmann Institute of Science, Rehovot, Israel

C. Pandu Rangan

Indian Institute of Technology, Madras, India

Bernhard Steffen

TU Dortmund University, Dortmund, Germany

Demetri Terzopoulos

University of California, Los Angeles, CA, USA

Doug Tygar

University of California, Berkeley, CA, USA

Gerhard Weikum

Max Planck Institute for Informatics, Saarbrücken, Germany

More information about this series at http://www.springer.com/series/7410

Shlomi Dolev • Sachin Lodha (Eds.)

Cyber Security Cryptography

and Machine Learning

First International Conference, CSCML 2017

Beer-Sheva, Israel, June 29–30, 2017

Proceedings

123

Editors

Shlomi Dolev

Ben-Gurion University of the Negev

Beer-Sheva

Israel

Sachin Lodha

Tata Consultancy Services (India)

Pune, Maharashtra

India

ISSN 0302-9743 ISSN 1611-3349 (electronic)

Lecture Notes in Computer Science

ISBN 978-3-319-60079-6 ISBN 978-3-319-60080-2 (eBook)

DOI 10.1007/978-3-319-60080-2

Library of Congress Control Number: 2017943048

LNCS Sublibrary: SL4 – Security and Cryptology

© Springer International Publishing AG 2017

This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the

material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation,

broadcasting, reproduction on microfilms or in any other physical way, and transmission or information

storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now

known or hereafter developed.

The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication

does not imply, even in the absence of a specific statement, that such names are exempt from the relevant

protective laws and regulations and therefore free for general use.

The publisher, the authors and the editors are safe to assume that the advice and information in this book are

believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors

give a warranty, express or implied, with respect to the material contained herein or for any errors or

omissions that may have been made. The publisher remains neutral with regard to jurisdictional claims in

published maps and institutional affiliations.

Printed on acid-free paper

This Springer imprint is published by Springer Nature

The registered company is Springer International Publishing AG

The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland

Preface

CSCML, the International Symposium on Cyber Security Cryptography and Machine

Learning, is an international forum for researchers, entrepreneurs, and practitioners in

the theory, design, analysis, implementation, or application of cyber security, cryp￾tography, and machine-learning systems and networks, and, in particular, of concep￾tually innovative topics in this area. Information technology has become crucial to our

everyday life in indispensable infrastructures of our society and therefore is also a

target of attacks by malicious parties. Cyber security is one of the most important fields

of research today because of these phenomena. The two, sometimes competing, fields

of research, cryptography and machine learning, are the most important building blocks

of cyber security, as cryptography hides information by avoiding the possibility to

extract any useful information pattern while machine learning searches for meaningful

information patterns. The subjects covered by the symposium include cyber security

design; secure software development methodologies; formal methods, semantics, and

verification of secure systems; fault tolerance, reliability, availability of distributed

secure systems; game-theoretic approaches to secure computing; automatic recovery

self-stabilizing, and self-organizing systems; communication, authentication, and

identification security; cyber security for mobile and Internet of Things; cyber security

of corporations; security and privacy for cloud, edge, and fog computing; cryptogra￾phy; cryptographic implementation analysis and construction; secure multi-party

computation; privacy-enhancing technologies and anonymity; post-quantum cryptog￾raphy and security; machine learning and big data; anomaly detection and malware

identification; business intelligence and security; digital forensics, digital rights man￾agement; trust management and reputation systems; and information retrieval, risk

analysis, DoS.

The first edition of CSCML took place during June 29–30, 2017, in Beer-Sheva,

Israel.

This volume contains 17 contributions selected by the Program Committee and four

brief announcements. All submitted papers were read and evaluated by Program

Committee members, assisted by external reviewers. We are grateful for the EasyChair

system in assisting the reviewing process.

The support of Ben-Gurion University of the Negev (BGU), in particular the BGU

Lynne and William Frankel Center for Computer Science, the BGU Cyber Security

Research Center, and BGN, also the support of IBM, DELLEMC, JVP, Deutsche

Telekom Capital Partners, Glilot, Magma, Pitango, and BaseCamp, is also gratefully

acknowledged.

April 2017 Shlomi Dolev

Sachin Lodha

Organization

CSCML, the International Symposium on Cyber Security Cryptography and Machine

Learning, is an international forum for researchers, entrepreneurs, and practitioners in

the theory, design, analysis, implementation, or application of cyber security,

cryptography, and machine-learning systems and networks, and, in particular, of

conceptually innovative topics in this field.

Founding Steering Committee

Orna Berry DELLEMC, Israel

Shlomi Dolev (Chair) Ben-Gurion University, Israel

Yuval Elovici Ben-Gurion University, Israel

Ehud Gudes Ben-Gurion University, Israel

Jonathan Katz University of Maryland, USA

Rafail Ostrovsky UCLA, USA

Jeffrey D. Ullman Stanford University, USA

Kalyan Veeramachaneni MIT, USA

Yaron Wolfsthal IBM, Israel

Moti Yung Columbia University and Snapchat, USA

Organizing Committee

Program Chairs

Shlomi Dolev Ben-Gurion University of the Negev, Israel

Sachin Lodha Tata Consultancy Services, India

Organizing Chair

Timi Budai Ben-Gurion University of the Negev, Israel

Program Committee

Ran Achituv Magma Ventures, Israel

Yehuda Afek Tel-Aviv University, Israel

Adi Akavia Tel-Aviv Yaffo Academic College, Israel

Amir Averbuch Tel-Aviv University, Israel

Roberto Baldoni Università di Roma “La Sapienza”, Italy

Michael Ben-Or Hebrew University, Israel

Anat Bremler-Barr IDC Herzliya, Israel

Yves-Alexandre de Montjoye Imperial College London, UK

Itai Dinur Ben-Gurion University, Israel

Shlomi Dolev (Co-chair) Ben-Gurion University, Israel

Karim ElDefrawy SRI International, USA

Yuval Elovici Ben-Gurion University, Israel

Felix Freiling Friedrich-Alexander-Universität, Germany

Ben Gilad Tata Consultancy Services, Israel

Niv Gilboa Ben-Gurion University, Israel

Shafi Goldwasser Weizmann Institute of Science and MIT, USA

Rachel Greenstadt Drexel University, USA

Ehud Gudes Ben-Gurion University, Israel

Yaniv Harel DELLEMC, Israel

Danny Hendler Ben-Gurion University, Israel

Amir Herzberg Bar-Ilan University, Israel

Yona Hollander Fortscale, Israel

Guy Horowitz Deutsche Telekom Capital Partners, Israel

Stratis Ioannidis Northeastern University, USA

Yuval Ishai Technion, Israel

Ayal Itzkovitz Pitango Venture Capital, Israel

Arik Kleinstein Glilot Capital Partners, Israel

Vladimir Kolesnikov Bell Labs, USA

Mark Last Ben-Gurion University, Israel

Wenke Lee Georgia Institute of Technology, USA

Sachin Lodha (Co-chair) Tata Consultancy Services, India

Oded Margalit IBM, Israel

Aikaterini Mitrokosta Chalmers University of Technology, Sweden

Kobbi Nissim Georgetown University, USA

Rita Osadchy University of Haifa, Israel

Ely Porat Bar-Ilan University, Israel

Michael Rodeh Permira and Land & Expand, Israel

Alon Rosen IDC Herzliya, Israel

Benjamin I.P. Rubinstein The University of Melbourne, Australia

Galina Schwartz UC Berkeley, USA

Gil Segev Hebrew University, Israel

Yossi Shavit Inno-Negev, Israel

Hans Simon Ruhr-Universität Bochum, Germany

Doug Tygar UC Berkeley, USA

Yoav Tzruya JVP Cyber Labs, Israel

Yael Villa CISCO, Israel

Michael Waidner Fraunhofer SIT and TU Darmstadt, Germany

Avishai Wool Tel-Aviv University, Israel

Moti Yung Columbia University and Snapchat, USA

Uzy Zwebner ATP and BaseCamp, Israel

VIII Organization

Additional Reviewers

Vijayanand Banahatti Tata Consultancy Services, India

Silvia Bonomi Università di Roma “La Sapienza”, Italy

Antonella Del Pozzo Università di Roma “La Sapienza”, Italy

Manish Shukla Tata Consultancy Services, India

Ajeet Kumar Singh Tata Consultancy Services, India

Sponsors

Organization IX

X Organization

Contents

Efficient, Reusable Fuzzy Extractors from LWE . . . . . . . . . . . . . . . . . . . . . 1

Daniel Apon, Chongwon Cho, Karim Eldefrawy, and Jonathan Katz

GENFACE: Improving Cyber Security Using Realistic Synthetic Face

Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

Margarita Osadchy, Yan Wang, Orr Dunkelman, Stuart Gibson,

Julio Hernandez-Castro, and Christopher Solomon

Supervised Detection of Infected Machines Using Anti-virus

Induced Labels (Extended Abstract) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

Tomer Cohen, Danny Hendler, and Dennis Potashnik

Building Regular Registers with Rational Malicious Servers and

Anonymous Clients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

Antonella Del Pozzo, Silvia Bonomi, Riccardo Lazzeretti,

and Roberto Baldoni

On the Optimality of the Exponential Mechanism . . . . . . . . . . . . . . . . . . . . 68

Francesco Aldà and Hans Ulrich Simon

On Pairing Inversion of the Self-bilinear Map on Unknown

Order Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

Hyang-Sook Lee, Seongan Lim, and Ikkwon Yie

Brief Announcement: Anonymous Credentials Secure to

Ephemeral Leakage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

Łukasz Krzywiecki, Marta Wszoła, and Mirosław Kutyłowski

The Combinatorics of Product Scanning Multiplication and Squaring . . . . . . 99

Adam L. Young and Moti Yung

Stylometric Authorship Attribution of Collaborative Documents . . . . . . . . . . 115

Edwin Dauber, Rebekah Overdorf, and Rachel Greenstadt

A Distributed Investment Encryption Scheme: Investcoin . . . . . . . . . . . . . . . 136

Filipp Valovich

Physical Layer Security over Wiretap Channels

with Random Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

Ziv Goldfeld, Paul Cuff, and Haim H. Permuter

Assisting Malware Analysis with Symbolic Execution: A Case Study . . . . . . 171

Roberto Baldoni, Emilio Coppa, Daniele Cono D’Elia,

and Camil Demetrescu

Brief Announcement: A Consent Management Solution for Enterprises . . . . . 189

Abigail Goldsteen, Shelly Garion, Sima Nadler, Natalia Razinkov,

Yosef Moatti, and Paula Ta-Shma

Brief Announcement: Privacy Preserving Mining of Distributed

Data Using a Trusted and Partitioned Third Party . . . . . . . . . . . . . . . . . . . . 193

Nir Maoz and Ehud Gudes

Brief Announcement: A Technique for Software Robustness

Analysis in Systems Exposed to Transient Faults and Attacks. . . . . . . . . . . . 196

Sergey Frenkel and Victor Zakharov

Symmetric-Key Broadcast Encryption: The Multi-sender Case . . . . . . . . . . . 200

Cody Freitag, Jonathan Katz, and Nathan Klein

A Supervised Auto-Tuning Approach for a Banking Fraud

Detection System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215

Michele Carminati, Luca Valentini, and Stefano Zanero

Scalable Attack Path Finding for Increased Security . . . . . . . . . . . . . . . . . . 234

Tom Gonda, Rami Puzis, and Bracha Shapira

Learning Representations for Log Data in Cybersecurity . . . . . . . . . . . . . . . 250

Ignacio Arnaldo, Alfredo Cuesta-Infante, Ankit Arun, Mei Lam,

Costas Bassias, and Kalyan Veeramachaneni

Attack Graph Obfuscation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269

Hadar Polad, Rami Puzis, and Bracha Shapira

Malware Triage Based on Static Features and Public APT Reports . . . . . . . . 288

Giuseppe Laurenza, Leonardo Aniello, Riccardo Lazzeretti,

and Roberto Baldoni

Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307

XII Contents

Efficient, Reusable Fuzzy Extractors from LWE

Daniel Apon2(B)

, Chongwon Cho1, Karim Eldefrawy1, and Jonathan Katz2

1 Information and Systems Science Laboratory, HRL Laboratories,

Los Angeles, USA

[email protected] 2 University of Maryland, College Park, USA

{dapon,jkatz}@cs.umd.edu

Abstract. A fuzzy extractor (FE) enables reproducible generation of

high-quality randomness from noisy inputs having sufficient min-entropy.

FEs have been proposed for deriving cryptographic keys from biomet￾ric data. FEs rely in their operation on a public “helper string” that is

guaranteed not to leak too much information about the original input.

Unfortunately, this guarantee may not hold when multiple independent

helper strings are generated from correlated inputs; reusable FEs are

needed in that case. Although the notion of reusable FEs was intro￾duced in 2004, it has received little attention since then.

In this paper, we first analyze an FE proposed by Fuller et al.

(Asiacrypt 2013) based on the learning-with-errors (LWE) assumption,

and show that it is not reusable. This is interesting as the first natural

example of a non-reusable FE. We then show how to adapt their con￾struction to obtain reusable FEs. Of independent interest, we show a

generic technique for strengthening the notion of reusability achieved by

an FE in the random-oracle model.

1 Introduction

Consider using biometric data as a source for generating cryptographic keys. For

example, assume Alice wants to use her biometric data (e.g., fingerprint) w to

generate a cryptographic key that she will then use to encrypt her data before

storing it on a public server. In a naive approach, Alice could use w itself as

the key to encrypt the data. There are two problems with this approach: first,

when Alice re-scans her biometric data at a later point in time, it is likely she

will recover a value w that is close, but not equal, to the initial value w. Alice

will be unable to recover her original data with such a noisy key if she uses a

This research is based upon work supported in part by the Office of the Director

of National Intelligence (ODNI), Intelligence Advanced Research Projects Activ￾ity (IARPA). The views and conclusions contained herein are those of the authors

and should not be interpreted as necessarily representing the official policies, either

expressed or implied, of ODNI, IARPA, or the U.S. Government. The U.S. Govern￾ment is authorized to reproduce and distribute reprints for governmental purposes

notwithstanding any copyright annotation therein.

K. Eldefrawy—Currently at SRI International: [email protected].

c Springer International Publishing AG 2017

S. Dolev and S. Lodha (Eds.): CSCML 2017, LNCS 10332, pp. 1–18, 2017.

DOI: 10.1007/978-3-319-60080-2 1

2 D. Apon et al.

standard encryption scheme. Second, w is not a uniform string, and thus it is

unclear what security is obtained when using w as a key.

Fuzzy extractors. Fuzzy Extractors (FEs) provide a solution to the above

challenges. An FE, first formally introduced by Dodis et al. [6], consists of a pair

of algorithms (Gen, Rec) that work as follows: the generation algorithm Gen takes

as input a value (e.g., biometric data) w, and outputs a pair of values (pub, r),

where the first of these is called the “helper string.” The recovery algorithm Rec

takes as input pub along with a value w

, and outputs r if w is “sufficiently

close” to the original value w. The security guarantee, roughly speaking, is that

r is uniform—or at least computationally indistinguishable from uniform—for

an adversary who is given pub, as long as the original input (i.e., w) comes from

a distribution with sufficiently high min-entropy.

FEs can address the scenario described earlier. Alice can run Gen on the

initial scan of her biometric data to compute (pub, r) ← Gen(w); she will use

r to encrypt her data, and send the resulting ciphertext along with pub to the

server. When she wishes to recover her data at some later point in time, she will

obtain a fresh scan w of her biometric data and the server will send to Alice the

ciphertext and pub; Alice will compute r = Rec(pub, w

) and use r to decrypt

the ciphertext. This ensures security, even from the server, since the key used

for encryption (i.e., r) is uniform even conditioned on pub.

Reusability. One might hope that a FE would remain “secure” even if used on

multiple, related input strings w1,.... Concretely, consider a setting in which a

user relies on different scans w1,...,w of their biometric data when interact￾ing with servers such that each server (independently) computes (pubi, ri) ←

Gen(wi) as above. (We stress that even though the same underlying biometric

feature is used every time, the {wi} represent independent scans of that feature;

thus, the elements in {wi} will be close to each other but will not necessarily be

identical.) Each of the public values pubi may become known to an adversary,

and the original definition of FE does not provide any guarantees in this case.

Boyen [4] was the first to highlight this issue, and he showed (contrived) con￾structions of FEs that are secure when used once, but that completely leak the

underlying values w1,...,w if used multiple times. On the positive side, Boyen

defined a notion of reusability for FEs (called outsider security) and showed that

the code-based construction of Dodis et al. [6] is reusable when a linear code is

used. (We discuss definitions of reusability in further detail in Sect. 2.2.)

Somewhat surprisingly, there was no subsequent progress on reusable FEs

until the recent work of Canetti et al. [5]. The primary advantage of their

scheme is that it achieves reusability under very weak assumptions on the dif￾ferent scans w1,...,w. (In contrast, Boyen assumed that wi = w ⊕ δi for a

small shift δi known to the adversary.) The scheme of Canetti et al. can also

be used for sources of lower entropy rate than prior work, if the distribution

of the {wi} satisfies a certain assumption. For completeness, however, we note

that their scheme also has several disadvantages relative to the reusable scheme

Efficient, Reusable Fuzzy Extractors from LWE 3

analyzed by Boyen: it tolerates a lower error rate, has computational—rather

than information-theoretic—security, and relies on the random-oracle model.1

1.1 Our Contributions

In this work, we propose a new, indistinguishability-based definition for FEs,

which can be viewed as adopting aspects of the definitions of reusability given by

Boyen [4] and Canetti et al. [5]. Informally, our definition says that if (pubi, ri) ←

Gen(wi) are computed as above, then an adversary cannot distinguish r1 from a

uniform string even given pub1 and {(pubi, ri)}i>1.

We then show that the recent computational FE proposed by Fuller et al. [8]

(the FMR-FE) is not reusable in a very strong sense: from the public information

pub1 and pub2 of two instances of the scheme, an attacker can learn the original

input data w1 and w2.

2 Fuller et al. do not claim reusability in their paper, but

our result is nevertheless interesting as it gives the first natural example of an

FE that is not reusable. On the other hand, we observe that their construction

can achieve a weaker form of reusability if a common random string is available

that can be used by the generation algorithm.

We then show several constructions of reusable FEs. First, we show a generic

approach that can be used to convert any FE that achieves “weak” reusability

to one that achieves our stronger notion of reusability, in the random-oracle

model.3 This approach can, in particular, be applied to the variant of the FMR￾FE scheme described above (that assumes a common random string), which leads

to an efficient construction achieving our strong notion of reusability based on the

decisional learning-with-errors (LWE) assumption in the random-oracle model.

Finally, we show a construction of a (strongly) reusable FE that does not

rely on the random-oracle model. It also relies on the LWE assumption, though

with a super-polynomial modulus. Although we view this construction as being

mainly of theoretical interest, we remark that it is more efficient than the scheme

proposed by Canetti et al. [5], and achieves better parameters than the reusable

scheme analyzed by Boyen [4].

1.2 Paper Organization

In Sect. 2 we review existing definitions of reusable FEs and introduce our new

definition of reusability. We analyze the reusability of the FE proposed by Fuller

et al. [8] in Sect. 3. We show how to modify their construction so that it achieves

1 Technically, Canetti et al. rely on the assumption that “digital lockers” exist. All

known constructions of digital lockers without random oracles require non-standard

assumptions; in practice, digital lockers would most likely be instantiated with a

hash function modeled as a random oracle. 2 Huth et al. [10, Theorem 5] claim that the construction of Fuller et al. is reusable,

but their proof is incorrect. 3 Alam´elou et al. [2] show a transformation with a similar goal, but it only applies to

FEs for the set-difference metric on sets over exponential-size universes.