Advances in Information and Computer Security

In this paper, we propose a new leakage-resilient identity-based encryption (IBE) scheme that is secure against chosen-ciphertext attacks (CCA) in the bounded memory leakage model. It is the first CCA-secure leakage-resilient IBE scheme which does not depend on \(\mathtt {q}\)-type assumptions. More precisely, it is secure under the DLIN assumption for symmetric bilinear groups and under the XDLIN assumption for asymmetric bilinear groups, respectively.

At ASIACRYPT 2018, Castryck, Lange, Martindale, Panny and Renes proposed CSIDH, which is a key-exchange protocol based on isogenies between elliptic curves, and a candidate for post-quantum cryptography. However, the implementation by Castryck et al. is not constant-time. Specifically, a part of the secret key could be recovered by the side-channel attacks. Recently, Meyer, Campos, and Reith proposed a constant-time implementation of CSIDH by introducing dummy isogenies and taking secret exponents only from intervals of non-negative integers. Their non-negative intervals make the calculation cost of their implementation of CSIDH twice that of the worst case of the standard (variable-time) implementation of CSIDH. In this paper, we propose a more efficient constant-time algorithm that takes secret exponents from intervals symmetric with respect to the zero. For using these intervals, we need to keep two torsion points on an elliptic curve and calculation for these points. We implemented our algorithm by extending the implementation in C of Meyer et al. (originally from Castryck et al.). Then our implementation achieved 152.8 million clock cycles, which is about 29.03% faster than that of Meyer et al.

The multivariate public key cryptosystem (MPKC) is a potential post-quantum cryptosystem. Its safety depends on the hardness of solving systems of algebraic equations over finite fields. In particular, the multivariate quadratic (MQ) problem is that of solving such a system consisting of quadratic polynomials and is regarded as an important research subject in cryptography. In the Fukuoka MQ challenge project, the hardness of the MQ problem is discussed, and the algorithms used for the MQ problem and the computational results obtained by these algorithms are reported. The algorithms to compute Gröbner basis for the polynomial set given by the MQ problem are for solving the MQ problem. For example, the \(F_4\) algorithm and M4GB algorithm have succeeded in solving several MQ problems provided by the project. In this paper, based on the \(F_4\)-style algorithm, we present an efficient algorithm to solve the MQ problems with dense polynomials generated in the Fukuoka MQ challenge project. We experimentally show that our algorithm requires less computational time and memory for these MQ problems than the \(F_4\) algorithm and M4GB algorithm. We succeeded in solving Type II problems using our algorithm when the numbers of variables are 36 and 37.

Let \(\mathbb {G}\) be a group of prime order p with a generator g. It is known that one can find \(x_1, \ldots , x_L\) from \(g^{x_1}, \ldots , g^{x_L}\) in time \(O(\sqrt{Lp})\). On the other hand, suppose that \(0 \le x < w\). Then Pollard’s kangaroo algorithm (or Pollard’s lambda algorithm) can find x from \(g^x\) in time \(O(\sqrt{w})\). It is used in the decryption algorithm of the homomorphic encryption scheme of Boneh, Goh and Nissim. Now suppose that \(0 \le x_i < w\) for \(i=1, \ldots , L\). This paper shows that we can find \(x_1, \ldots , x_L\) from \(g^{x_1}, \ldots , g^{x_L}\) in time \(O(\sqrt{Lw})\). We further show an application of our algorithm to the model of preprocessing.

This paper presents the first recursive secure multiparty computation protocol for matrix multiplication, based on Strassen-Winograd algorithm. We focus on the setting in which any given player knows only one row of both input matrices and learns the corresponding row of the resulting product matrix. Neither the player initial data, nor the intermediate values, even during the recurrence part of the algorithm, are ever revealed to other players. We use a combination of partial homomorphic encryption schemes and additive masking techniques together with a novel schedule for the location and encryption layout of all intermediate computations that preserves privacy. Compared to state of the art protocols, the asymptotic communication volume and computational time is reduced from \(O(n^3)\) to \(O(n^{2.81})\). This improvement in terms of communication volume arises with matrices of dimension as small as \(n=96\) which is confirmed by experiments.

To enhance the user’s privacy in electronic ID, anonymous credential systems have been researched. In the anonymous credential system, a trusted issuing organization first issues a certificate certifying the user’s attributes to a user. Then, in addition to the possession of the certificate, the user can anonymously prove only the necessary attributes. Previously, an anonymous credential system was proposed, where CNF (Conjunctive Normal Form) formulas on attributes can be proved. The advantage is that the attribute proof in the authentication has the constant size for the number of attributes that the user owns and the size of the proved formula. Thus, various expressive logical relations on attributes can be efficiently verified. However, the previous system has a limitation: the proved CNF formulas cannot include any negation. Therefore, in this paper, we propose an anonymous credential system with constant-size attribute proofs such that the user can prove CNF formulas with negations. For the proposed system, we extend the previous accumulator for the limited CNF formulas to verify CNF formulas with negations.

At the FSE conference of ToSC 2018, Kranz et al. presented their results on shortest linear programs for the linear layers of several well known block ciphers in literature. Shortest linear programs are essentially the minimum number of 2-input xor gates required to completely describe a linear system of equations. In the above paper the authors showed that the commonly used metrics like d-xor/s-xor count that are used to judge the “lightweightedness” do not represent the minimum number of xor gates required to describe a given MDS matrix. In fact they used heuristic based algorithms of Boyar/Peralta and Paar to find implementations of MDS matrices with even fewer xor gates than was previously known. They proved that the AES mixcolumn matrix can be implemented with as little as 97 xor gates. In this paper we show that the values reported in the above paper are not optimal. By suitably including random bits in the instances of the above algorithms we can achieve implementations of almost all matrices with lesser number of gates than were reported in the above paper. As a result we report an implementation of the AES mixcolumn matrix that uses only 95 xor gates.

In the second part of the paper, we observe that most standard cell libraries contain both 2 and 3-input xor gates, with the silicon area of the 3-input xor gate being smaller than the sum of the areas of two 2-input xor gates. Hence when linear circuits are synthesized by logic compilers (with specific instructions to optimize for area), most of them would return a solution circuit containing both 2 and 3-input xor gates. Thus from a practical point of view, reducing circuit size in presence of these gates is no longer equivalent to solving the shortest linear program. In this paper we show that by adopting a graph based heuristic it is possible to convert a circuit constructed with 2-input xor gates to another functionally equivalent circuit that utilizes both 2 and 3-input xor gates and occupies less hardware area. As a result we obtain more lightweight implementations of all the matrices listed in the ToSC paper.

Tweakable block cipher (TBC) is an extension of conventional block cipher. We study how to build a TBC based on generalized Feistel structure (GFS), a classical block cipher construction. While known dedicated TBC proposals are based on substitution-permutation network (SPN), GFS has not been used for building TBC. In particular, we take 64-bit GFS block cipher TWINE and try to make it tweakable with a minimum change. To find a best one from a large number of candidates, we performed a comprehensive search with a help of mixed integer linear programming (MILP) solver. As a result, our proposal Tweakable TWINE is quite efficient, has the same number of rounds as TWINE with extremely simple tweak schedule.

Malware brings constant threats to the services and facilities used by modern society. In order to perform and improve anti-malware defense, there is a need for methods that are capable of malware categorization. As malware grouped into categories according to its functionality, dynamic malware analysis is a reliable source of features that are useful for malware classification. Different types of dynamic features are described in literature [5, 6, 13]. These features can be divided into two main groups: high-level features (API calls, File activity, Network activity, etc.) and low-level features (memory access patterns, high-performance counters, etc). Low-level features bring special interest for malware analysts: regardless of the anti-detection mechanisms used by malware, it is impossible to avoid execution on hardware. As hardware-based security solutions are constantly developed by hardware manufacturers and prototyped by researchers, research on low-level features used for malware analysis is a promising topic. The biggest problem with low-level features is that they don’t bring much information to a human analyst. In this paper, we analyze potential correlation between the low- and high-level features used for malware classification. In particular, we analyze n-grams of memory access operations found in [6] and try to find their relationship with n-grams of API calls. We also compare performance of API calls and memory access n-grams on the same dataset as used in [6]. In the end, we analyze their combined performance for malware classification and explain findings in the correlation between high- and low-level features.

Targeted email attacks are one of main threats for organizations of all sizes and across every field. In targeted email attacks, malicious VBA (Visual Basic for Applications) macros are often contained in the attachment files to exploit the target computers. These malicious VBA macros are obfuscated in several ways to evade detection. Hence, pattern-based detection has a limitation in detecting these new malicious VBA macros. To detect new malicious VBA macros, some methods with machine learning techniques have been proposed. A method extracts words from the source code, and constructs a language model to represent VBA macros for machine learning techniques. This method, however, constructs a language model from all the extracted words. Therefore, this model might contain unnecessary words to classify. To construct an efficient language model, we focus on LSI (Latent Semantic Indexing). LSI is one of the foundational techniques in topic modeling, and calculates similarity of documents. Our method uses LSI to construct an efficient language model, which produces more accuracy and efficiency. To the best of our knowledge, our method is the first method to detect new malicious VBA macros with LSI. Our method extracts words from the source code and converts into feature vectors with some Natural Language Processing techniques. Our method trains a classifier with benign and malicious VBA macros and detects new malicious VBA macros. Several thousands of samples for evaluation are obtained from Virus Total. The experimental result shows that our method can detect new malicious VBA macros more accurately and efficiently. The best F-measure achieves 0.95.

With the increase in the variety of devices connected to the Internet, each with their own vulnerabilities, we are currently observing an explosion of cyber attacks patterns. Furthermore, the overwhelming number of alerts from security sensors, such as intrusion detection systems (IDSs), makes it impossible to take appropriate countermeasures against attacks. A method to prioritize IDS alerts is therefore required for the next generation of security operation centers (SOCs). To this end, we have developed an IDS alert priority determination method that combines IDS alert information with traffic behavior and uses the difference in the distribution of traffic behavior to determine the priority of the alerts. We performed experiments with 2 million IDS alerts and 20 billion traffic flows in a real large-scale environment over two months and found that our method could identify 553 IDS alerts out of 2 million as high priority, which is a small enough number for SOC analysts to investigate them in detail.

DDoS attack detection using entropy-based features in network traffic has become a popular approach among researchers in the last five years. The use of traffic distribution features constructed using entropy measures has been proposed as a better approach to detect Distributed Denial of Service (DDoS) attacks compared to conventional volumetric methods, but it still lacks in the generality of detecting various intensity DDoS attacks accurately. In this paper, we focus on identifying effective entropy-based features to detect both high- and low-intensity DDoS attacks by exploring the effectiveness of entropy-based features in distinguishing the attack from normal traffic patterns. We hypothesise that using different entropy measures, window sizes, and entropy-based features may affect the accuracy of detecting DDoS attacks. This means that certain entropy measures, window sizes, and entropy-based features may reveal attack traffic amongst normal traffic better than the others. Our experimental results show that using Shannon, Tsallis and Zhou entropy measures can achieve a clearer distinction between DDoS attack traffic and normal traffic than Rényi entropy. In addition, the window size setting used in entropy construction has minimal influence in differentiating between DDoS attack traffic and normal traffic. The result of the effectiveness ranking shows that the commonly used features are less effective than other features extracted from traffic headers.

The rise of quantum computers poses a threat to asymmetric cryptographic schemes. With their continuing development, schemes such as DSA or ECDSA are likely to be broken in a few years’ time. We therefore must begin to consider the use of different algorithms that would be able to withstand powerful quantum computers. Among the considered algorithms are hash-based signature schemes, some of which, including XMSS, are stateful. In comparison to stateless algorithms, these stateful schemes pose additional implementation challenges for developers, regarding error-free usage and integration into IT systems. As the correct use of cryptographic algorithms is the foundation of a secure IT system, mastering these challenges is essential.

This work proposes an easy-to-use API design for stateful signature schemes, using XMSS(MT) as an example. Our design is based on findings from literature as well as on a series of interviews with software developers. It has been prototypically implemented and evaluated in small-scale user-studies. Our results show that the API can manage the stateful keys in a way that is transparent to the user. Furthermore, a preliminary online-study has shown that the API’s documentation and applicability are comprehensible. However, due to the transparent state management, many of the study’s participants were unaware of using a stateful scheme. This might lead to possible obstacles. Our current API design will serve as the basis for a larger user-study in order to review our preliminary findings in the next step.

WebView is commonly used by applications on the Android OS. Given that WebView is used as a browsing component on applications, they can be attacked via the web. Existing security mechanisms mainly focus on web browsers; hence, securing WebView is an important challenge. We proposed and implemented a method for preventing suspicious web access in Android WebView. Attackers distribute their malicious content including malicious applications, potentially unwanted programs, and coin miners, by inserting contents into a web page. Because loading malicious content involves HTTP communication, our proposed method monitors HTTP communication by WebView and blocks suspicious web accesses. To apply the proposed method to widely used applications, we implemented our method inside WebView. We also evaluated the proposed method with some popular applications and confirmed that the method can block designated web content without impeding the functionality of applications.

Replayable chosen ciphertext (RCCA) security was introduced by Canetti, Krawczyk, and Nielsen (CRYPTO 03) in order to handle an encryption scheme that is “non-malleable except tampering which preserves the plaintext”. RCCA security is a relaxation of CCA security and a useful security notion for many practical applications such as authentication and key exchange. Canetti et al. defined non-malleability against RCCA (NM-RCCA), indistinguishability against RCCA (IND-RCCA), and universal composability against RCCA (UC-RCCA). Moreover, they proved that these three security notions are equivalent when considering a PKE scheme whose plaintext space is super-polynomially large. Among these three security notions, NM-RCCA seems to play the central role since RCCA security was introduced in order to capture “non-malleability except tampering which preserves the plaintext.” However, their definition of NM-RCCA is not a natural extension of that of classical non-malleability, and it is not clear whether their NM-RCCA captures the requirement of classical non-malleability. In this paper, we propose definitions of indistinguishability-based and simulation-based non-malleability against RCCA by extending definitions of classical non-malleability. We then prove that these two notions of non-malleability and IND-RCCA are equivalent regardless of the size of plaintext space of PKE schemes.

Identity-based encryption (IBE) is an attractive primitive in modern cryptography. Cocks first gave an elegant construction of IBE under Quadratic Residuosity (\(\mathsf {QR}\)) assumption. Unfortunately, its security works only in the Random Oracle (RO) model. In this work, we aim at providing Cock’s scheme with provable security in the standard model. Specifically, we modify Cocks’ scheme by explicitly instantiating the hash function using indistinguishability obfuscation in two different ways which yield two variants of Cocks’ scheme. Their security are promised under well-defined selective-ID and adaptive-ID model respectively. As an additional contribution, we adapt the same method into the Boneh, LaVigne, Sabin (BLS) \(e^{th}\) residuosity based IBE cryptosystem and obtain an adaptive chosen-ID secure scheme under Modified \(e^{th}\) Residuosity (\(\mathsf {MER}\)) assumption.

In this paper, we introduce an alternative method to find ordinary cube variables for Keccak-MAC by making full use of the key-independent bit conditions. First, we select some potential candidates for ordinary cube variables by properly adding key-independent bit conditions, which do not multiply with the chosen conditional cube variables in the first two rounds. Then, we carefully determine the ordinary cube variables from the candidates to establish the conditional cube tester. Finally, based on our new method to recover the 128-bit key, the conditional cube attack on 7-round Keccak-MAC-128/256/384 is improved to \(2^{71}\) and 6-round Keccak-MAC-512 can be attacked with at most \(2^{40}\) calls to 6-round Keccak internal permutation. It should be emphasized that our new approach does not require sophisticated modeling. As far as we know, it is the first time to clearly reveal how to utilize the key-independent bit conditions to select ordinary cube variables for Keccak-MAC.

Troika is a recently proposed sponge-based hash function for IOTA’s ternary architecture and platform, which is developed by CYBERCRYPT. In this paper, we introduce the preimage attack on 2 and 3 rounds of Troika with a divide-and-conquer approach. Instead of directly matching a given hash value, we propose equivalent conditions to determine whether a message is the preimage before computing the complete hash value. As a result, for the two-round hash value that can be generated with one block, we can search the preimage only in a valid space and efficiently enumerate the messages which can satisfy most of the equivalent conditions with a guess-and-determine technique. For the three-round preimage attack, an MILP-based method is applied to separate the one-block message space into two parts in order to obtain the best advantage over brute force. Our experiments show that the time complexity of the preimage attack on 2 (out of 24) rounds of Troika can be improved to \(3^{79}\), which is \(3^{164}\) times faster than the brute force. For the preimage attack on 3 (out of 24) rounds of Troika, we can obtain an advantage of \(3^{25.7}\) over brute force. In addition, how to construct the second preimage for two-round Troika in seconds is presented as well. Our attacks do not threaten the security of Troika.

Verifiable secret sharing (VSS) allows honest parties to ensure consistency of their shares even if a dealer and/or a subset of parties are corrupt. We focus on perfect VSS, i.e., those providing perfect privacy, correctness and commitment with zero error, in the unconditional (information-theoretic) security setting where no assumption on the computational power of the participants is imposed.

Our study is motivated by both practical and theoretical considerations. For the practical side, MPC with perfect security is now being implemented. Multi-cloud storage has been implemented by IBM. Modern users rely on smartphones with limited internet connectivity, limited battery power, etc. We focus on such a user outsourcing her data to multi-clouds with the capability to have these multi-clouds participate on her behalf in MPC protocols. We show that in the case of VSS based on the replicated secret sharing scheme, there is no need for that user to be involved in any interaction. In addition, this scheme has an optimal number of rounds. This construction is derived from Maurer’s VSS based on the replicated secret sharing scheme.

A disadvantage of the replicated scheme is that it generally requires a considerable amount of randomness. We address this issue by showing a VSS scheme based on Shamir’s secret sharing, where the dealer does not need any randomness at all.

Following up mass surveillance and privacy issues, modern secure communication protocols now seek more security such as forward secrecy and post-compromise security. They cannot rely on an assumption such as synchronization, predictable sender/receiver roles, or online availability. Ratcheting was introduced to address forward secrecy and post-compromise security in real-world messaging protocols. At CSF 2016 and CRYPTO 2017, ratcheting was studied either without zero round-trip time (0-RTT) or without bidirectional communication. At CRYPTO 2018, ratcheting with bidirectional communication was done using heavy key-update primitives. At EUROCRYPT 2019, another protocol was proposed. All those protocols use random oracles. Furthermore, exchanging messages has complexity in general.

In this work, we define the bidirectional asynchronous ratcheted key agreement ( ) with formal security notions. We provide a simple security model and design a secure scheme using no key-update primitives, no random oracle, an with complexity. It is based on a public-key cryptosystem, a signature scheme, one-time symmetric encryption, and a collision-resistant hash function family. We further show that (even unidirectional) implies public-key cryptography, meaning that it cannot solely rely on symmetric cryptography.

A new hash-based, server-supported digital signature scheme was proposed recently in [7]. We decompose the concept into forward-resistant tags and a generic cryptographic time-stamping service. Based on the decomposition, we propose more tag constructions which allow efficient digital signature schemes with interesting properties to be built. In particular, the new schemes are more suitable for use in personal signing devices, such as smart cards, which are used infrequently. We define the forward-resistant tags formally and prove that (1) the discussed constructs are indeed tags and (2) combining such tags with time-stamping services gives us signature schemes.

The continuous decrease in the price of Unmanned Aerial Vehicles (UAVs), more commonly known as drones, has pushed their adoption from military-oriented to a wide range of civilian and business applications. Nevertheless, the many features that they offer have started being maliciously exploited. The latter coupled with the fact that accidents or malicious acts may occur to drones has sparked the interest towards drones forensics.

Distributed code injection is a new type of malicious code injection technique. It makes existing forensics techniques for injected code detection infeasible by splitting a malicious code into several code snippets, injecting them into multiple running processes, and executing them in each process spaces. In spite of the impact of it on practical forensics fields, there was no discussion on countermeasures against this threat. In this paper, we present a memory forensics method for finding all code snippets distributively injected into multiple processes to defeat distributed code injection attacks. Our method is designed on the following observation for distributed code injection attacks. Even though malicious code is split and distributed in multiple processes, the split code snippets have to synchronize each other at runtime to maintain the order of the execution of the original malicious code. We exploit this characteristic of distributed code injection attacks with our method. The experimental results showed that our method successfully found all distributed code snippets and assisted to reconstruct the original code from them. We believe that we are the first to present a countermeasure against distributed code injection attacks. We also believe that our method is able to improve the efficiency of forensics especially for a host compromised with distributed code injection attacks.