Skip to main content

2018 | Buch

Information Security and Cryptology

13th International Conference, Inscrypt 2017, Xi'an, China, November 3–5, 2017, Revised Selected Papers

insite
SUCHEN

Über dieses Buch

This book constitutes the thoroughly refereed post-conference proceedings of the 13th International Conference on Information Security and Cryptology, Inscrypt 2017, held in Xi'an, China, in November 2017.
The 27 revised full papers presented together with 5 keynote speeches were carefully reviewed and selected from 80 submissions. The papers are organized in the following topical sections: cryptographic protocols and algorithms; digital signatures; encryption; cryptanalysis and attack; and applications.

Inhaltsverzeichnis

Frontmatter

Keynote Speeches

Frontmatter
Security and Privacy in the IoT
Abstract
Deploying existing data security solutions to the Internet of Things (IoT) is not straightforward because of device heterogeneity, highly dynamic and possibly unprotected environments, and large scale. In this paper, we first outline IoT security and privacy risks and critical related requirements in different application domains. We then discuss aspects of a roadmap for IoT security and privacy with focus on access control, software and firmware, and intrusion detection systems. We conclude the paper by outlining a few challenges.
Elisa Bertino
On Crossroads of Privacy Protection
Abstract
The privacy protection has recently become a hot topic because of the increase in cyber-crime (using personal data for mounting attacks) as well as legal obligations for parties controlling personal data (eg. GDPR regulation of European Union). This creates a big market for pragmatic technical solutions.
In this paper we discuss a few general issues related to these problems, focused on current challenges and the necessity of paradigm shifting in the construction of IT systems, which should be secure-by-design in a demonstrable way.
Mirosław Kutyłowski
The Dual Role of Smartphones in IoT Security
Abstract
The world is entering the era of Internet of Things (IoT), where the interconnected physical devices of various forms, often embedded with electronics, software, sensors, actuators, etc., jointly perform sophisticated sensing and computing tasks and provide unprecedented services. Centering around this new paradigm is the ubiquitous smartphone. Equipped with abundant sensing, computing and networking capabilities, the smartphone is widely recognised as one of the key enablers towards IoT and the driving force that brings a great many innovative services under the way.
Despite the promising aspects, along with the rise of IoT is the increasing concerns on cybersecurity. The smartphone in this new context, however, plays a very intriguing dual role, due to the fact that it is deeply interleaved into almost every aspect of our daily living. On the one hand, it could be used as a low-cost attacking device, trying to penetrate into the scenarios that have never been considered before. On the other hand, it is also the first line of defense in the security forefront. In both cases, we need to carefully study and comprehensively understand the capability of smartphones, as well as their security implications. In this talk, we will use two examples to illustrate this observation and hopefully promote further researches along this line.
Kui Ren

Cryptographic Protocols and Algorithms

Frontmatter
Implementing Indistinguishability Obfuscation Using GGH15
Abstract
Obfuscation is an extraordinarily powerful object that has been shown to enable a whole set of new cryptographic possibilities. Because of the impossibility of the general-purpose virtual black-box (VBB) obfuscation, Barak et al. suggested to implement a weak variant which is called the indistinguishability obfuscation (iO). The iO is the substrate of various cryptographic primitives such as the universal function encryption, the self-bilinear map and so on. However, current obfuscation is too cumbersome to implement in practice.
In this paper, we implement an obfuscation for NC1 circuits by using the GGH15 multilinear map. Several techniques are proposed to improve the efficiency and adaptability of the implementation. We reduce the matrix dimension and the depth of encoding graph to increase the speed of confusion. Splitting the matrix into block matrix and encoding each block instead of using the entire matrix will reduce the size of matrix effectively. The plaintext matrix will be one block of the matrix. Besides, we put matrices into groups and encode one group on path \(u\,\rightsquigarrow \,v\). Then the depth of the graph depends on the number of groups rather than the number of matrices. Those methods have led to a significant reduction in the rate of obfuscation.
Zheng Zhang, Fangguo Zhang, Huang Zhang
From Attack on Feige-Shamir to Construction of Oblivious Transfer
Abstract
Following the work of [Deng, Eurocrypt 2017], under the assumption of the existence of injective one way function, we prove that at least one of the following statements is true:
  • (Infinitely-often) Oblivious transfer exists.
  • For every inverse polynomial \(\epsilon \), the 4-round Feige-Shamir protocol is \(\epsilon \)-distributional concurrent zero knowledge for any hard distribution over sparse OR-relation.
Both these statements have been shown to be unprovable [Gertner et al. FOCS 2000; Canetti et al. STOC 2001] via black-box reductions.
We show how to transform the magic adversary who breaks the \(\epsilon \)-distributional concurrent zero knowledge of the classic Feige-Shamir protocols into oblivious transfer under the existence of injective one way function. As a key ingredient, we introduce the concept of distributional witness encryption to achieve the encryption scheme in which “public keys” can be sampled separately of “private keys”, and show that if there exists a magic adversary breaking the \(\epsilon \)-distributional concurrent zero knowledge of Feige-Shamir protocols over a hard distribution, it can be transformed to an (infinitely-often) distributional witness encryption based on injective one way function.
Jingyue Yu, Yi Deng, Yu Chen
A New Lattice Sieving Algorithm Base on Angular Locality-Sensitive Hashing
Abstract
Currently, the space requirement of sieving algorithms to solve the shortest vector problem (SVP) grows as \(2^{0.2075n+o(n)}\), where n is the lattice dimension. In high dimensions, the memory requirement makes them uncompetitive with enumeration algorithms. Shi Bai et al. presents a filtered triple sieving algorithm that breaks the bottleneck with memory \( 2^{0.1887n+o(n)}\) and time \( 2^{0.481n+o(n)}\).
Benefiting from the angular locality-sensitive hashing (LSH) method, our proposed algorithm runs in time \(2^{0.4098n+o(n)}\) with the same space complexity \(2^{0.1887n+o(n)}\) as the filtered triple sieving algorithm. Our experiment demonstrates that the proposed algorithm achieves the desired results. Furthermore, we use the proposed algorithm to solve the closest vector problem (CVP) with the lowest space complexity as far as we know in the literature.
Ping Wang, Dongdong Shang
A Simpler Bitcoin Voting Protocol
Abstract
Recently, Zhao and Chan proposed a Bitcoin voting protocol where n voters could fund Bitcoins to one of two candidates determined by majority voting. Their protocol preserves the privacy of individual ballot while they cast ballots by Bitcoin transactions. However, their protocol supports only two candidates and relies on a threshold signature scheme. We extend their method to produce a ballot by a voter selecting at least \(k_{min}\), at most \(k_{max}\) from L candidates. We also redesign a vote casting protocol without threshold signatures to reduce transaction numbers and protocol complexities. We also introduce new polices to make the Bitcoin Voting protocol more fair.
Haibo Tian, Liqing Fu, Jiejie He
Post-Quantum Secure Remote Password Protocol from RLWE Problem
Abstract
Secure Remote Password (SRP) protocol is an augmented Password-based Authenticated Key Exchange (PAKE) protocol based on discrete logarithm problem (DLP) with various attractive security features. Compared with basic PAKE protocols, SRP does not require server to store user’s password and user does not send password to server to authenticate. These features are desirable for secure client-server applications. SRP has gained extensive real-world deployment, including Apple iCloud, 1Password etc. However, with the advent of quantum computer and Shor’s algorithm, classic DLP-based public key cryptography algorithms are no longer secure, including SRP. Motivated by importance of SRP and threat from quantum attacks, we propose a RLWE-based SRP protocol (RLWE-SRP) which inherit advantages from SRP and elegant design from RLWE key exchange. We also present parameter choice and efficient portable C++ implementation of RLWE-SRP. Implementation of our 209-bit secure RLWE-SRP is more than 3x faster than 112-bit secure original SRP protocol, 5.5x faster than 80-bit secure J-PAKE and 14x faster than two 184-bit secure RLWE-based PAKE protocols with more desired properties.
Xinwei Gao, Jintai Ding, Jiqiang Liu, Lin Li
Hashing into Twisted Jacobi Intersection Curves
Abstract
By generalizing Jacobi intersection curves introduced by D. V. Chudnovsky and G. V. Chudnovsky, Feng et al. proposed twisted Jacobi intersection curves, which contain more elliptic curves. Twisted Jacobi intersection curves own efficient arithmetics with regard to their group law and are resistant to timing attacks. In this paper, we proposed two hash functions indifferentiable from a random oracle, mapping binary messages to rational points on twisted Jacobi intersection curves. Both functions are based on deterministic encodings from \(\mathbb {F}_q\) to twisted Jacobi intersection curves. There are two ways to construct such encodings: (1) utilizing the algorithm of computing cube roots on \(\mathbb {F}_q\) when \(3\,|q+1\); (2) using Shallue-Woestijne-Ulas algorithm when \(4\,|q+1\). In both cases, our encoding methods are more efficient than existed ones. Moreover, we estimate the density of images of both encodings by Chebotarev theorem.
Xiaoyang He, Wei Yu, Kunpeng Wang

Digital Signatures

Frontmatter
Identity-Based Key-Insulated Aggregate Signatures, Revisited
Abstract
Identity-based key-insulated cryptography is a cryptography which allows a user to update an exposed secret key by generating a temporal secret key as long as the user can keep any string as its own public key. In this work, we consider the following question; namely, can we construct aggregate signatures whereby individual signatures can be aggregated into a single signature in an identity-based key-insulated setting? We call such a scheme identity-based key-insulated aggregate signatures (IBKIAS), and note that constructing an IBKIAS scheme is non-trivial since one can aggregate neither each signer’s randomness nor components depending on the temporal secret keys. To overcome this problem, we utilize the synchronized technique proposed by Gentry and Ramzan (PKC’06) for both aas state information and a partial secret key generated by a secure device. We then show that the proposed scheme is still provably secure under an adaptive security model of identity-based aggregate signatures.
Nobuaki Kitajima, Naoto Yanai, Takashi Nishide
A New Constant-Size Accountable Ring Signature Scheme Without Random Oracles
Abstract
Accountable ring signature (ARS), introduced by Xu and Yung (CARDIS 2004), combines many useful properties of ring and group signatures. In particular, the signer in an ARS scheme has the flexibility of choosing an ad hoc group of users, and signing on their behalf (like a ring signature). Furthermore, the signer can designate an opener who may later reveal his identity, if required (like a group signature). In 2015, Bootle et al. (ESORICS 2015) formalized the notion and gave an efficient construction for ARS with signature-size logarithmic in the size of the ring. Their scheme is proven to be secure in the random oracle model. Recently, Russell et al. (ESORICS 2016) gave a construction with constant signature-size that is secure in the standard model. Their scheme is based on q-type assumptions (q-SDH).
In this paper, we give a new construction for ARS having the following properties: signature is constant-sized, secure in the standard model, and based on indistinguishability obfuscation \((\mathcal {\textit{i}O})\) and one-way functions. To the best of our knowledge, this is the first \(\mathcal {\textit{i}O}\)-based ARS scheme. Independent of this, our work can be viewed as a new application of puncturable programming and hidden sparse trigger techniques introduced by Sahai and Waters (STOC 2014) to design \(\mathcal {\textit{i}O}\)-based deniable encryption.
Sudhakar Kumawat, Souradyuti Paul
A Universal Designated Multi-Verifier Transitive Signature Scheme
Abstract
A Universal Designated Verifier Transitive Signature (\(\mathrm {UDVTS}\)) scheme is designed for the graph-based big data system. Specifically, it allows a transitive signature holder to convince the designated verifier with a transitive signature. Nevertheless, existing \(\mathrm {UDVTS}\) schemes cannot be directly employed in the scenarios when multi-verifier are involved. Thus, in this paper, we extend the notion to the Universal Designated Multi-Verifier Transitive Signature (\(\mathrm {UDMVTS}\)) scheme. Namely, our new scheme allows a transitive signature holder to designate the signature to multi-verifier. Furthermore, for the proposed scheme, we formalize its security notions and prove its security in the random oracle model. We also analyse the performance of our scheme to demonstrate its efficiency.
Fei Zhu, Yuexin Zhang, Chao Lin, Wei Wu, Ru Meng
Cryptanalysis and Improvement of a Strongly Unforgeable Identity-Based Signature Scheme
Abstract
Recently, Tsai et al. constructed an efficient identity-based signature (IBS) scheme and claimed that it was strongly unforgeable in the standard model. Unfortunately, we find that their scheme is insecure. By giving concrete attack, we show that their scheme does not meet the requirement of strong unforgeability. Meanwhile, we demonstrate that there are serious flaws in their security proof. The simulator cannot correctly answer the signing query in the security model. Furthermore, we propose an improved strongly unforgeable IBS scheme without random oracles. Compared with other strongly unforgeable IBS schemes in the standard model, our scheme is more efficient in terms of computation cost and signature size.
Xiaodong Yang, Ping Yang, Faying An, Shudong Li, Caifen Wang, Dengguo Feng

Encryption

Frontmatter
Parallel Long Messages Encryption Scheme Based on Certificateless Cryptosystem for Big Data
Abstract
In big data environment, the quantity of generated and stored data is huge, and the size is larger than before. A general solution to encrypt large messages is to adopt the hybrid encryption method, that is, one uses an asymmtric cryptosystem to encrypt the symmetric key, and needs a symmetric cryptosystem to encrypt the real message. To eliminate this requirement for an additional cryptosystem, a parallel long message encryption scheme based on certificateless cryptosystem is proposed, which eliminates the needs for public key certificates, and avoids the key escrow problem. In combination with parallel computer hardware, we further improve the performance. The simulation results show that it can make full use of CPU resources and has high efficiency advantages. In the random oracle model, the presented scheme is secure in a One-Way Encryption (OWE) model.
Xuguang Wu, Yiliang Han, Minqing Zhang, Shuaishuai Zhu
Constant Decryption-Cost Non-monotonic Ciphertext Policy Attribute-Based Encryption with Reduced Secret Key Size (and Dynamic Attributes)
Abstract
Attribute-based encryption, especially ciphertext policy attribute based encryption (CP-ABE), is a standard method for achieving access control using cryptography. The access control policy is determined by access structure in a CP-ABE scheme. If negative permission is required in the access control model, which is a quite common setting, then non-monotonic access structures must be allowed in the CP-ABE scheme.
In 2011, Chen et al. proposed a CP-ABE scheme with non-monotonic access structures that has constant decryption cost. However, it requires a secret key size linear to the number of total attributes, which is hard to implement when the resources are limited for both computation and storage. In this paper, we improve this scheme to get a CP-ABE scheme where access structure is non-monotonic AND-gate, while the secret key size is only linear to the number of attributes held by a user, without increasing the decryption cost. This scheme will be useful if the total attributes are much more than attributes for each user. Our scheme is provably secure for selective CPA-security under the decision n-BDHE assumption. We also show that our scheme can be naturally extended to supporting attribute addition and revocation, where the attribute set of each user can be updated dynamically, without any complicated proxy re-encryption or decryption procedure.
Geng Wang, Xiao Zhang, Yanmei Li
Fully Homomorphic Encryption Scheme Based on Public Key Compression and Batch Processing
Abstract
Fully homomorphic encryption is a type of encryption technique that allows arbitrary complex operations to be performed on the ciphertext, thus generating an encrypted result that, when decrypted, matches the results of those operations performed on the plaintext. The DGHV scheme over the integers is one of the key schemes in fully homomorphic encryption research field, but the incredible size of the public key and the low computational efficiency are the main challenges. Based on the original DGHV encryption structure and parameters’ design, the idea of batch processing was introduced in this paper. With the combination of the quadratic parameter-based public key compression mechanism, a complete public key compression and batch processing fully homomorphic encryption (PKCB-FHE) scheme was presented. Like those in the original DGHV scheme, the parameter restriction of the proposed scheme was presented. Further analysis and simulation of the proposed scheme indicate that the required storage space of the public key is immensely reduced and that the overall length of the public key is compressed. Furthermore, the total processing time of the proposed scheme is reduced, which makes it much more efficient than those existing schemes.
Liquan Chen, Ming Lim, Muyang Wang
Leveled FHE with Matrix Message Space
Abstract
Up to now, almost all fully homomorphic encryption (FHE) schemes can only encrypt bit or vector. In PKC 2015, Hiromasa et al. [12] constructed the only leveled FHE scheme that encrypts matrices and supports homomorphic matrix addition and multiplication. But the ciphertext size of their scheme is somewhat large and the security of their scheme depends on some special kind of circular security assumption.
We propose a leveled FHE scheme that encrypts matrices and supports homomorphic matrix addition, multiplication and Hadamard product. It can be viewed as matrix-packed FHE, and has much smaller ciphertext size. Its security is only based on LWE assumption. In particular, the advantages of our scheme are:
1.
Supporting homomorphic matrix Hadamard product. All entries in plaintext matrices can be viewed as plaintext slots. While the scheme in [12] doesn’t support this homomorphic operation and only the diagonal entries of plaintext matrix can be viewed as plaintext slots.
 
2.
Small ciphertext size. For a plaintext matrix \(\varvec{M} \in \{0,1\}^{r\times r}\), the size of ciphertext matrix is \(r\times (n+r)\), in contrast to \((n+r)\times (n+r)\lceil \log q\rceil \) in [12].
 
3.
Standard assumption. The security is based on LWE assumption merely, while the security of scheme in [12] depends additionally on some special kind of circular security assumption.
 
As Brakerski’s work [3] in CRYPTO 2012, our scheme can be improved in efficiency by using ring-LWE (RLWE).
Biao Wang, Xueqing Wang, Rui Xue
Predicate Fully Homomorphic Encryption: Achieving Fine-Grained Access Control over Manipulable Ciphertext
Abstract
With the popularity of cloud computing, there is an increasing demand for enforcing access control over outsourced files and performing versatile operations on encrypted data. To meet this demand, a novel primitive called predicate fully homomorphic encryption (PFHE) is introduced and modeled in this work, which can provide the security guarantee that neither cloud computing server nor invalid cloud users can acquire any extra information about the processed data, while the server can still process the data correctly. We give a generic construction for PFHE, from any predicate key encapsulation mechanism (PKEM) and any LWE-based multi-key fully homomorphic encryption (MFHE). Compared with previously proposed generic construction for attribute-based fully homomorphic encryption (ABFHE), which can naturally be extended to one for PFHE, our construction has advantages in both time for encryption and space for encrypted data storage. In addition, our construction can achieve CCA1-secure. Thus it directly implies approaches for CCA1-secure FHE, CCA1-secure PFHE and CCA1-secure MFHE. The latter two have not been touched in previous work. In addition, we give a conversion which results a CCA1-secure PFHE scheme from a CPA-secure one, drawing on the techniques for CCA2-secure PE schemes.
Hanwen Feng, Jianwei Liu, Qianhong Wu, Weiran Liu

Cryptanalysis and Attack

Frontmatter
NativeSpeaker: Identifying Crypto Misuses in Android Native Code Libraries
Abstract
The use of native code (ARM binary code) libraries in Android apps greatly promotes the execution performance of frequently used algorithms. Nonetheless, it increases the complexity of app assessment since the binary code analysis is often sophisticated and time-consuming. As a result, many defects still exist in native code libraries and potentially threat the security of users. To assess the native code libraries, current researches mainly focus on the API invoking correctness and less dive into the details of code. Hence, flaws may hide in internal implementation when the analysis of API does not discover them effectively.
The assessment of native code requires a more detailed code comprehension process to pinpoint flaws. In response, we design and implement NativeSpeaker, an Android native code analysis system to assess native code libraries. NativeSpeaker provides not only the capability of recognizing certain pattern related to security flaws, but also the functionality of discovering and comparing native code libraries among a large-scale collection of apps from non-official Android markets. With the help of NativeSpeaker, we analyzed 20,353 dynamic libraries (.so) collected from 20,000 apps in non-official Android markets. Particularly, our assessment focuses on searching crypto misuse related insecure code pattern in those libraries. The analyzing results show even for those most frequently used (top 1%) native code libraries, one third of them contain at least one misuse. Furthermore, our observation indicates the misuse of crypto is often related to insecure data communication: about 25% most frequently used native code libraries suffer from this flaw. Our conducted analysis revealed the necessity of in-depth security assessment against popular native code libraries, and proved the effectiveness of the designed NativeSpeaker system.
Qing Wang, Juanru Li, Yuanyuan Zhang, Hui Wang, Yikun Hu, Bodong Li, Dawu Gu
A Game-Based Framework Towards Cyber-Attacks on State Estimation in ICSs
Abstract
The security issue on remote state estimation process against false data injection (FDI) attacks in Industrial Control Systems (ICSs) is considered in this paper. To be practically, it is more reasonable to assume whether or not a meter measurement could be compromised by an adversary does depend on the defense budget deployed on it by the system defender. Based on this premise, this paper focuses on designing the defense budget strategy to protect state estimation process in ICSs against FDI attacks by applying a game-based framework. With resource-constraints for both the defender and the attacker side, the decision making process of how to deploy the defending budget for defenders and how to launch attacks on the meters for an attacker are investigated. A game-based framework is formulated and it has been proved that the Nash equilibrium is existed. For practical computation convenience, an on-line updating algorithm is proposed. What’s more, the simulation of the game-based framework described in this paper is demonstrated to verify its validity and efficiency. The experimental results have shown that the game-based framework could improve performance of the decision making and estimation process and mitigate the impact of the FDI attack. This may provide a novel and feasible perspective to protect the state estimation process and improve the intrusion tolerance in ICSs.
Cong Chen, Dongdai Lin, Wei Zhang, Xiaojun Zhou
Cryptanalysis of Acorn in Nonce-Reuse Setting
Abstract
Acorn is a third-round candidate of the CAESAR competition. It is a lightweight authenticated stream cipher. In this paper, we show how to recover the initial state of Acorn when one pair of Key and IV is used to encrypt three messages. Our method contains two main steps: (1) gathering different states; (2) retrieving linear equations. At the first step, we demonstrate how to gather the relation between states when two different plaintexts are encrypted under the same nonce. And at the second step, we exploit how to retrieve a system of linear equations with respect to the initial state, and how to recover the initial state from this system of equations. We apply this method to both Acorn v2 and Acorn v3. The time complexity to recover the initial state of Acorn v2 is \(2^{78} c\), where c is the time complexity of solving linear equations. It is lower than that of the previous methods. For Acorn v3, we can recover the initial state with the time complexity of \(2^{120.6}c\), lower than that of the exhaustion attack. We also apply it on shrunk ciphers with similar structure and properties of Acorn v2 and Acorn v3 to prove the validity of our method. This paper is the first time to analyze Acorn v3 when a nonce is reused and our method provides some insights into the diffusion ability of such stream ciphers.
Xiaojuan Zhang, Dongdai Lin
An Improved Method to Unveil Malware’s Hidden Behavior
Abstract
Sandbox technique is widely used in automated malware analysis. However, it can only see one path during its analysis. This is fatal when meeting the targeted malware. The challenge is how to unleash the hidden behaviors of targeted malware. Many works have been done to mitigate this problem. However, these solutions either use limited and fixed sandbox environments or introduce time and space consuming multi-path exploration. To address this problem, this paper proposes a new hybrid dynamic analysis scheme by applying function summary based symbolic execution of malware. Specifically, by providing Windows APIs’ summary stub and using unicorn CPU emulator, we can effectively extract malware’s hidden behavior which are not shown in sandbox environment. Without the usage of full system emulation, our approach achieve much higher speed than existing schemes. We have implemented a prototype system, and evaluated it with typical real-world malware samples. The experiment results show that our system can effectively and efficiently extract malware’s hidden behavior.
Qiang Li, Yunan Zhang, Liya Su, Yang Wu, Xinjian Ma, Zeming Yang
BotTokenizer: Exploring Network Tokens of HTTP-Based Botnet Using Malicious Network Traces
Abstract
Nowadays, malicious software and especially botnets leverage HTTP protocol as their communication and command (C&C) channels to connect to the attackers and control compromised clients. Due to its large popularity and facility across firewall, the malicious traffic can blend with legitimate traffic and remains undetected. While network signature-based detection systems and models show extraordinary advantages, such as high detection efficiency and accuracy, their scalability and automatization still need to be improved.
In this work, we present BotTokenizer, a novel network signature-based detection system that aims to detect malicious HTTP C&C traffic. BotTokenizer automatically learns recognizable network tokens from known HTTP C&C communications from different botnet families by using words segmentation technologies. In essence, BotTokenizer implements a coarse-grained network signature generation prototype only relying on Uniform Resource Locators (URLs) in HTTP requests. Our evaluation results demonstrate that BotTokenizer performs very well on identifying HTTP-based botnets with an acceptable classification errors.
Biao Qi, Zhixin Shi, Yan Wang, Jizhi Wang, Qiwen Wang, Jianguo Jiang
Improved Cryptanalysis of an ISO Standard Lightweight Block Cipher with Refined MILP Modelling
Abstract
Differential and linear cryptanalysis are two of the most effective attacks on block ciphers. Searching for (near) optimal differential or linear trails is not only useful for the security evaluation of block ciphers against these attacks, but also indispensable to the cryptanalysts who want to attack a cipher with these techniques. In recent years, searching for trails automatically with Mixed-Integer Linear Programming (MILP) gets a lot of attention. At first, Mouha et al. translated the problem of counting the minimum number of differentially active S-boxes into an MILP problem for word-oriented block ciphers. Subsequently, in Asiacrypt 2014, Sun et al. extended Mouha et al.’s method, and presented a technique which can find actual differential or linear characteristics of a block cipher in both the single-key and related-key models. In this paper, we refine the constraints of the 2-XOR operation in order to reduce the overall number of variables and constraints. Experimental results show that MILP models with the refined constraints can be solved more efficiently. We apply our method to HIGHT (an ISO standard), and we find differential (covering 11 rounds) or linear trails (covering 10 rounds) with higher probability or correlation. Moreover, we find so far the longest differential and linear distinguishers of HIGHT.
Jun Yin, Chuyan Ma, Lijun Lyu, Jian Song, Guang Zeng, Chuangui Ma, Fushan Wei
Meet in the Middle Attack on Type-1 Feistel Construction
Abstract
We provide a key recovery attack on type-1 Feistel construction based on the meet-in-the-middle technique. This construction is described by Zheng, Matsumoto, and Imai in CRYPTO 1989. Type-1 Feistel structure is a well-known construction used to construct ciphers and hash functions, such as CAST-256 and Lesamnta. For Type-1 Feistel construction with n-bit blocks and d sub-blocks, we launch a \(3d-1\) rounds distinguisher by using a special truncated differential. We present an attack on \(5d-3\) rounds with the data complexity \({{2}^{\frac{3}{d}n}}\) chosen plaintexts, the memory complexity \({{2}^{\frac{d-1}{d}n}}\) blocks, each block is n bits, and the time complexity \({{2}^{\frac{d-1}{d}n}}\) encryptions, which is the best known generic key recovery attack on Type-1 Feistel construction. The attack is valid if the key length \(k\ge n\).
Yuanhao Deng, Chenhui Jin, Rongjia Li

Applications

Frontmatter
Influence of Error on Hamming Weights for ASCA
Abstract
Algebraic Side-Channel Attack (ASCA) models the cryptographic algorithm and side-channel leakage from the system as a set of equations and solves for the secret key. The attack has low data complexity and can succeed in unknown plaintext/ciphertext scenarios. However, it is susceptible to error and the complexity of the model may drastically increase the runtime as well as the memory consumption. In this paper, we explore the attack by examining the importance of various Hamming weights in terms of success of the attack, which also allows us to gain insights into possible areas of focus for countermeasures, as well as successfully launch ASCA on AES with a larger error tolerance.
Chujiao Ma, John Chandy, Laurent Michel, Fanghui Liu, Waldemar Cruz
State-of-the-Art: Security Competition in Talent Education
Abstract
Security competitions have become increasingly popular events for recruitment, training, evaluation, and recreation in the field of computer security. And among these various exercises, Capture the flag (CTF) competitions have the widest audience. Participants in CTF of Jeopardy style focus on solving several specific challenges independently while participants in CTF of attack-defense mode concentrate on vulnerable service maintenance and vulnerability exploitation on an end-target box. However, according to a report published by TREND MICRO Corporation, there are six stages of a typical Targeted Attack: (1) Intelligence Gathering (2) Point of Entry (3) Command and Control Communication (4) Lateral Movement (5) Asset Discovery and (6) Data Exfiltration. Further, Lateral Movement is the key stage where threat actors move deeper into the network. Because of the lack of large-scale complex network environment, CTF cannot simulate a complete network penetration of the six stages, especially the Lateral Movement. It is indispensable to perform the Lateral Movement the skill of Network Exploring which is not included by security competitions at present. So we create Explore-Exploit which is an attack-defense mode competition that models the network penetration scenario, and promotes the participant’s skill of Network Exploring. This paper is trying to convey a better methodology for teaching practical attack-defense techniques to participants through an alternative to CTF.
Xiu Zhang, Baoxu Liu, Xiaorui Gong, Zhenyu Song
A Modified Fuzzy Fingerprint Vault Based on Pair-Polar Minutiae Structures
Abstract
Biometrics-based cryptosystems are helpful tools facilitating our daily life. Examples are that people use their biometrics to identify themselves in clouds or protect passwords as well as other privacy information in mobile phones connected to Internet-of-Things. Among various biometrics, fingerprints are one used most widely. A promising type of secure cryptosystems based on fingerprints is the so called fuzzy fingerprint vaults which can bind a secret key to one fingerprint template and release the same key later with the help of a similar but not necessarily fully identical fingerprint template. However, some aspects such as the security and matching accuracy of existing fingerprint-based fuzzy vaults are still not satisfactory due to troublesome issues such as the alignment of fingerprints and minutiae quantization.
In this paper we propose a modified fuzzy fingerprint vault based on pair-polar minutiae structures, aiming at achieving better performance. Recall that Li et al. (2016) presented a fuzzy vault based on pair-polar minutiae structures with two-level secure sketch in recovering the secret key. Unlike their scheme, we compress the two-level structure into one level in which minutia descriptors are exploited to match a vault and thus lower the time complexity of decoding. Our experiment evaluation shows that the proposed fuzzy fingerprint vault achieves high matching accuracy. Importantly, our vault is of strong security against existing attacks such as the brute-force attack, false-accept attack and correlation attack. Also this vault adopts the polynomial representation introduced by Dodis and Reyzin (2006) which is thus able to reduce the storage complexity.
Xiangmin Li, Ning Ding, Haining Lu, Dawu Gu, Shanshan Wang, Beibei Xu, Yuan Yuan, Siyun Yan
NOR: Towards Non-intrusive, Real-Time and OS-agnostic Introspection for Virtual Machines in Cloud Environment
Abstract
Cloud platforms of large enterprises are witnessing increasing adoption of the Virtual Machine Introspection (VMI) technology for building a wide range of VM monitoring applications including intrusion detection systems, virtual firewall, malware analysis, and live memory forensics. In our analysis and comparison of existing VMI systems, we found that most systems suffer one or more of the following problems: intrusiveness, time lag and OS-dependence, which are not well suited to clouds in practice. To address these problems, we present NOR, a non-intrusive, real-time and OS-agnostic introspection system for virtual machines in cloud environment. It employs event-driven monitoring and snapshot polling cooperatively to reconstruct the memory state of guest VMs. In our evaluation, we show NOR is capable of monitoring activities of guest VMs instantaneously with minor performance overhead. We also design some case studies to show that NOR is able to detect kernel rootkits and mitigate transient attacks for different Linux systems.
Chonghua Wang, Zhiyu Hao, Xiaochun Yun
A Method to Enlarge the Design Distance of BCH Codes and Some Classes of Infinite Optimal Cyclic Codes
Abstract
Cyclic codes are a meaningful class of linearcodes due to their effective encoding and decoding algorithms. As a subclass of cyclic codes, Bose-Ray-Chaudhuri-Hocquenghem (BCH) codes have good error-correcting capability and are widely used in communication systems. As far as the design of cyclic codes is concerned, it is difficult to determine the minimum distance. It is well known that the minimum distance of a cyclic code of designed distance d is at least d. In this paper, by adjusting the generator polynomial slightly and using a concatenation technique, we present a method to enlarge the designed distance of cyclic codes and obtain two classes of \([pq,q-1,2p]\) cyclic codes and \([pq,p-1,2q]\) cyclic codes over GF(2). As a consequence, a class of infinite optimal [3p, 2, 2p] cyclic codes, where \(p\equiv {-1}\pmod 8\), with respect to the Plotkin bound over GF(2) is presented.
Shanding Xu, Xiwang Cao, Chunming Tang
Backmatter
Metadaten
Titel
Information Security and Cryptology
herausgegeben von
Xiaofeng Chen
Dongdai Lin
Moti Yung
Copyright-Jahr
2018
Electronic ISBN
978-3-319-75160-3
Print ISBN
978-3-319-75159-7
DOI
https://doi.org/10.1007/978-3-319-75160-3

Premium Partner