Cryptology and Network Security

Current signature and encryption schemes secure against continual leakage fail completely if the key in any time period is fully exposed. We suggest forward security as a second line of defense, so that in the event of full exposure of the current secret key, at least uses of keys prior to this remain secure, a big benefit in practice. (For example if the signer is a certificate authority, full exposure of the current secret key would not invalidate certificates signed under prior keys.) We provide definitions for signatures and encryption that are forward-secure under continual leakage. Achieving these definitions turns out to be challenging, and we make initial progress with some constructions and transforms.

We present a security reduction for the PAK protocol instantiated over Gap Diffie-Hellman Groups that is tighter than previously known reductions. We discuss the implications of our results for concrete security. Our proof is the first to show that the PAK protocol can provide meaningful security guarantees for values of the parameters typical in today’s world.

Order-preserving encryption (OPE) is an encryption scheme with the property that the ordering of the plaintexts carry over to the ciphertexts. This primitive is particularly useful in the setting of encrypted databases because it enables efficient range queries over encrypted data. Given its practicality and usefulness in the design of databases on encrypted data, OPE’s popularity is growing. Unfortunately, nearly all computationally efficient OPE constructions are vulnerable against ciphertext frequency-leakage, which allows for inferring the underlying plaintext frequency. To overcome this weakness, Kerschbaum recently proposed a security model, designed a frequency-hiding OPE scheme, and analyzed its security in the programmable random oracle model (CCS 2015).

In this work, we demonstrate that Kerschbaum’s definition is imprecise and using its natural interpretation, we describe an attack against his scheme. We generalize our attack and show that his definition is, in fact, not satisfiable. The basic idea of our impossibility result is to show that any scheme satisfying his security notion is also IND-CPA-secure, which contradicts the very nature of OPE. As a consequence, no such scheme can exist. To complete the picture, we rule out the imprecision in the security definition and show that a slight adaption of Kerschbaum’s tree-based scheme fulfills it.

By secure outsourcing via secure multi-party computation (SMPC), we enable privacy-preserving genomic database queries that protect sensitive data contained in the queries and their respective responses. At the same time, we allow for multiple genomic databases to combine their datasets to achieve a much larger search space, without revealing the actual databases’ contents to third parties. SMPC is generic and allows to apply further processing like aggregation to query results.

We measure the performance of our approach for realistic parameters and achieve convincingly fast runtimes that render our protocol applicable to real-world medical data integration settings. Our prototype implementation can process a private query with 5 genetic variant conditions against a person’s exome with 100,000 genomic variants in less than 180 ms online runtime, including additional range and equality checks for auxiliary data.

Matrix multiplication is one of the most basic and useful operations in statistical calculations and machine learning. When the matrices contain sensitive information and the computation has to be carried out in an insecure environment, such as a cloud server, secure matrix multiplication computation (MMC) is required, so that the computation can be outsourced without information leakage. Dung et al. apply the Ring-LWE-based somewhat public key homomorphic encryption scheme to secure MMC [TMMP2016], whose packing method is an extension of Yasuda et al.’s methods [SCN2015 and ACISP2015] for secure inner product. In this study, we propose a new packing method for secure MMC from Ring-LWE-based secure inner product and show that ours is efficient and flexible.

In this work we introduce the notion of Subset Predicate Encryption, a form of attribute-based encryption (ABE) in which a message is encrypted with respect to a set \(s'\) and the resulting ciphertext can be decrypted by a key that is associated with a set \(s\) if and only if \(s\subseteq s'\). We formally define our primitive and identify several applications. We also propose two new constructions based on standard assumptions in bilinear groups; the constructions have very efficient decryption algorithms (consisting of one and two pairing computations, respectively) and small keys: in both our schemes, private keys contain only two group elements. We prove selective security of our constructions without random oracles. We demonstrate the usefulness of Subset Predicate Encryption by describing several black-box transformations to more complex primitives, such as identity-based encryption with wildcards and ciphertext-policy ABE for DNF formulas over a small universe of attributes. All of the resulting schemes are as efficient as the base Subset Predicate Encryption scheme in terms of decryption and key generation.

We propose the first multi-client predicate-only encryption scheme capable of efficiently testing the equality of two encrypted vectors. Our construction can be used for the privacy-preserving monitoring of relations among multiple clients. Since both the clients’ data and the predicates are encrypted, our system is suitable for situations in which this information is considered sensitive. We prove our construction plaintext and predicate private in the generic bilinear group model using random oracles, and secure under chosen-plaintext attack with unbounded corruptions under the symmetric external Diffie–Hellman assumption. Additionally, we provide a proof-of-concept implementation that is capable of evaluating one thousand predicates defined over the inputs of ten clients in less than a minute on commodity hardware.

Biometric Authentication Protocols (\(\mathsf {BAP}\)s) have increasingly been employed to guarantee reliable access control to places and services. However, it is well-known that biometric traits contain sensitive information of individuals and if compromised could lead to serious security and privacy breaches. Yasuda et al. [23] proposed a distributed privacy-preserving \(\mathsf {BAP}\) which Abidin et al. [1] have shown to be vulnerable to biometric template recovery attacks under the presence of a malicious computational server. In this paper, we fix the weaknesses of Yasuda et al.’s \(\mathsf {BAP}\) and present a detailed instantiation of a distributed privacy-preserving \(\mathsf {BAP}\) which is resilient against the attack presented in [1]. Our solution employs Backes et al.’s [4] verifiable computation scheme to limit the possible misbehaviours of a malicious computational server.

Attribute-based credentials (ABCs, sometimes also anonymous credentials) are a core cryptographic building block of privacy-friendly authentication systems, allowing users to obtain credentials on attributes and prove possession of these credentials in an unlinkable fashion. Thereby, users have full control over which attributes the user wants to reveal to a third party while offering high authenticity guarantees to the receiver. Unfortunately, up to date, all known ABC systems require access to all attributes in the clear at the time of proving possession of a credential to a third party. This makes it hard to offer privacy-preserving identity management systems “as a service,” as the user still needs specific key material and/or dedicated software locally, e.g., on his device.

This is achieved by carefully integrating proxy re-encryption with structure-preserving signatures and zero-knowledge proofs of knowledge. The user obtains credentials on his attributes (encrypted under his public key) and uploads them to the wallet, together with a specific re-encryption key. To prove a possession, the wallet re-encrypts the ciphertexts to the public key of the receiving third party and proves, in zero-knowledge, that all computations were done honestly. Thereby, the wallet never sees any user attribute in the clear.

We show the practical efficiency of our scheme by giving concrete benchmarks of a prototype implementation.

An Unlinkable Sanitizable Signature scheme (USS) allows a sanitizer to modify some parts of a signed message in such away that nobody can link the modified signature to the original one. A Verifiable Ring Signature scheme (VRS) allows the users to sign messages anonymously within a group where a user can prove a posteriori to a verifier that it is the author of a given signature. In this paper, we first revisit the notion of VRS: we improve the proof capabilities of the users, we give a complete security model for VRS and we give an efficient and secure scheme called \(\mathrm {EVeR}\). Our main contribution is \(\mathrm {GUSS}\), a Generic USS based on a VRS scheme and an unforgeable signature scheme. We show that \(\mathrm {GUSS}\) instantiated with \(\mathrm {EVeR}\) and Schnorr’s signature is twice as efficient as the best USS scheme of the literature. Moreover, we propose a stronger definition of accountability: an USS is accountable when the signer can prove whether a signature is sanitized. We formally define the notion of strong accountability where the sanitizer can also prove the origin of a signature. We show that the notion of strong accountability is important in practice. Finally, we prove the security properties of \(\mathrm {GUSS}\) (including strong accountability) and \(\mathrm {EVeR}\) under the Decisional Diffie-Hellman (DDH) assumption in the random oracle model.

Web applications use trustworthy events consciously triggered by a human user (e.g., a left mouse click) to authorize security-critical changes. Clickjacking and UI redressing (UIR) attacks trick the user into triggering a trustworthy event unconsciously. A formal model of Clickjacking was described by Huang et al. and was later adopted by the W3C UI safety specification. This formalization did not cover the target of these attacks, the trustworthy events.

We provide the first extensive investigation on this topic and show that the concept is not completely understood in current browser implementations. We show major differences between widely-used browser families, even to the extent that the concept of trustworthy events itself becomes unrecognizable. We also show that the concept of trusted events as defined by the W3C is somehow orthogonal to trustworthy events, and may lead to confusion in understanding the security implications of both concepts. Based on these investigations, we were able to circumvent the concept of trusted events, introduce three new UIR attack variants, and minimize their visibility.

Mounting deanonymization attacks on the unreachable Bitcoin nodes – these nodes do not accept incoming connections – residing behind the NAT is a challenging task. Such an attack was first given by Biryukov, Khovratovich and Pustogarov based on their observation that a node can be uniquely identified in a single session by their directly-connected neighbouring nodes (ACM CCS’15). However, the BKP15 attack is less effective across multiple sessions. To address this issue, Biryukov and Pustogarov later on devised a new strategy exploiting certain properties of address-cookies (IEEE S&P’15). Unfortunately, the BP15 attack is also rendered ineffective by the present modification to the Bitcoin client.

In this paper, we devise an efficient method to link the sessions of unreachable nodes, even if they connect to the Bitcoin network over the Tor. We achieve this using a new approach based on organizing the block-requests made by the nodes in a Bitcoin session graph. This attack also works against the modified Bitcoin client. We performed experiments on the Bitcoin main network, and were able to link consecutive sessions with a precision of 0.90 and a recall of 0.71. We also provide counter-measures to mitigate the attacks.

Code update is a very useful tool commonly used in low-end embedded devices to improve the existing functionalities or patch discovered bugs or vulnerabilities. If the update protocol itself is not secure, it will only bring new threats to embedded systems. Thus, a secure code update mechanism is required. However, existing solutions either rely on strong security assumptions, or result in considerable storage and computation consumption, which are not practical for resource-constrained embedded devices (e.g., in the context of Internet of Things). In this work, we first propose to use intrinsic device characteristics (i.e., Physically Unclonable Functions or PUF) to design a practical and lightweight secure code update scheme. Our scheme can not only ensure the freshness, integrity, confidentiality and authenticity of code update, but also verify that the update is installed correctly on a specific device without any malicious software. Cloned or counterfeit devices can be excluded as the code update is bound to the unpredictable physical properties of underlying hardware. Legitimate devices in an untrustworthy software state can be restored by filling suspect memory with PUF-derived random numbers. After update installation, the initiator of the code update is able to obtain the verifiable software state from device, and the device can maintain a sustainable post-update secure check by enforcing a secure call sequence. To demonstrate the practicality and feasibility, we also implement the proposed scheme on a low-end MCU platform (TI MSP430) by using onboard SRAM and Flash resources.

This paper presents the design and implementation of a low-power privacy-preserving device tracking system based on Internet of Things (IOT) technology. The system consists of low-power nodes and a set of dedicated beacons. Each tracking node broadcasts pseudonyms and encrypted versions of observed beacon identifiers over a Low-Power Wide-Area Network (LPWAN). Unlike most commercial systems, our solution ensures that the device owners are the only ones who can locate their devices. We present a detailed design and validate the result with a prototype implementation that considers power and energy consumption as well as side-channel attacks. Our implementation uses Physically Unclonable Function (PUF) technology for secure key-storage in an innovative way. We build and evaluate a complete demonstrator with off-the-shelf IoT nodes, Bluetooth Low Energy (BLE) beacons, and LoRa long distance communication (LPWAN). We validate the setup for a bicycle tracking application and also estimate the requirements for a low-cost ASIC node.

Free VPN apps have gained popularity among millions of users due to their convenience, and have been massively used for accessing blocked sites and preventing network eavesdropping. As a popular open-source VPN solution, OpenVPN is widely used by developers to implement their own VPN services. Despite the prevalence of OpenVPN, it can be insecurely customized and deployed by developers in lack of security guide.

In this paper, we perform a systematic security analysis of 84 popular OpenVPN-based apps on the Google Play store. We analyze the deployment security of OpenVPN on Android from the aspects of client profile, code implementation, and permission management. Our experiment reveals three types of misconfigurations that exist in several apps: insecure customized protocols, weak authentication at the client side, and incorrect file permissions on Android. The misconfigurations found by us can lead to some serious attacks, such as VPN traffic decryption and Man-in-the-Middle attacks, endangering millions of users’ privacy. Our work shows that, although OpenVPN protocol itself has withstood security analysis, insecure custom modification and configuration can still compromise the security of VPN apps. We then discuss potential causes of these misconfigurations and make practical recommendations for developers to securely deploy OpenVPN services.

We introduce the Anonymous Post-Office Protocol (AnonPoP), a practical strongly-anonymous messaging system. Its design effectively combines known techniques such as (synchronous) mix-cascade and constant sending rate, with several new techniques including request-pool, bad-server isolation and per-epoch mailboxes. AnonPoP offers strong anonymity against strong, globally-eavesdropping adversaries, that may also control multiple servers, including all-but-one servers in a mix-cascade. Significantly, AnonPoP’s anonymity holds even when clients may occasionally disconnect, which is essential for supporting mobile clients.

AnonPoP is affordable, with monthly costs of 2 cents per client. It is also efficient with respect to latency, communication, and energy, making it suitable for mobile clients. We developed an API that allows other applications to use AnonPoP for adding strong anonymity. We evaluated AnonPoP in several experiments, including a ‘double-blinded’ usability study, a cloud-based deployment, and simulations.

In this work, we compare the performance of a passive eavesdropper in 802.11b/n/ac WLAN networks. In particular, we investigate the downlink of 802.11 networks in infrastructure mode (e. g. from an access point to a terminal) using Commercial-Of-The-Shelf (COTS) devices. Recent 802.11n/ac amendments introduced several physical and link layer features, such as MIMO, spatial diversity, and frame aggregation, to increase the throughput and the capacity of the channel. Several information theoretical studies state that some of those 802.11n/ac features (e. g. beamforming) should provide a degradation of performance for a passive eavesdropper. However, the real impact of those features has not yet been analyzed in a practical context and experimentally evaluated. We present a theoretical discussion and a statistical analysis (using path loss models) to estimate the effects of such features on a passive eavesdropper in 802.11n/ac, using 802.11b as a baseline. We use Signal-to-Noise-Ratio (SNR) and Packet-Error-Rate (PER) as our main metrics. We compute lower and upper bounds for the expected SNR difference between 802.11b and 802.11n/ac using high-level wireless channel characteristics. We show that the PER in 802.11n/ac increases up to 98% (compared to 802.11b) at a distance of 20 m between the sender and the eavesdropper. To obtain a PER of 0.5 in 802.11n/ac, the attacker’s maximal distance is reduced by up to 129.5 m compared to 802.11b. We perform an extensive set of experiments, using COTS devices in an indoor office environment, to verify our theoretical estimations. The experimental results validate our predicted effects and show that every amendment add extra resiliency against passive COTS eavesdropping.

The extreme asymmetry of passive backscatter communications systems such as passive Wi-Fi, while allowing significant reduction of node power consumption for communications, imposes severe resource limitations on implementing secure communications. Target applications for this technology are typically driven by the promise of low power consumption, up to four orders of magnitude lower than commercial Wi-Fi chipsets. Industry standard security approaches using encryption technology are problematic in this power regime, particularly as the potential low complexity and size of passive nodes will encourage application to high-density networks of very small, energy-poor devices. Generation of shared symmetric keys through reciprocal channel measurements, for example of received signal strength (RSS), is a natural approach in this situation. However previous work in this area has focused on the symmetric case where base station and nodes communicate at the same radio frequency. Backscatter communications uses two frequencies, typically a pilot beacon transmitted by a base station on one frequency, and response on a shifted frequency. This paper describes a protocol for RSS-based shared key generation for this architecture and reports the results of an experimental implementation using software radio emulation of backscatter communication.

Proxy re-encryption (PRE) enables delegation of decryption rights by entrusting a proxy server with special information, that allows it to transform a ciphertext under one public key into a ciphertext of the same message under a different public key, without learning anything about the underlying plaintext. In Africacrypt 2010, the first PKI-based collusion resistant CCA secure PRE scheme without pairing was proposed in the random oracle model. In this paper, we point out an important weakness in the security proof of the scheme. We also present a collusion-resistant pairing-free unidirectional PRE scheme which meets CCA security under a variant of the computational Diffie-Hellman hardness assumption in the random oracle model.

In CANS 2016, Chen, Laing, and Martin proposed an ideal (t, n)-threshold secret sharing scheme (the CLM scheme) based on random linear code. However, in this paper we show that this scheme is essentially same as the one proposed by Karnin, Greene, and Hellman in 1983 (the KGH scheme) from privacy perspective. Further, the authors did not analyzed memory or XOR operations required to either store or calculate an inverse matrix needed for recovering the secret. In this paper, we analyze computational aspects of the CLM scheme and discuss various methods through which the inverse matrix required during the secret recovery can be obtained. Our analysis shows that for \(n \le 30\) all the required inverse matrices can be stored in memory whereas for \(30 \le n < 9000\) calculating the inverse as and when required is more appropriate. However, the CLM scheme becomes impractical for \(n > 9000\). Another method which we discuss to recover the secret in KGH scheme is to obtain only the first column of the inverse matrix using Lagrange’s interpolation however, as we show, this method can not be used with the CLM scheme. Some potential application of the secret sharing schemes are also discussed. From our analysis we conclude that the CLM scheme is neither novel nor as practical as has been suggested by Chen et al. whereas the KGH scheme is better suited for practical applications with large n.

Fully Homomorphic Encryption (FHE) schemes operate over finite fields while many use cases call for real numbers, requiring appropriate encoding of the data into the scheme’s plaintext space. However, the choice of encoding can tremendously impact the computational effort on the encrypted data. In this work, we investigate this question for applications that operate over integers and rational numbers using p-adic encoding and the extensions p’s Complement and Sign-Magnitude, based on three natural metrics: the number of finite field additions, multiplications, and multiplicative depth. Our results are partly constructive and partly negative: For the first two metrics, an optimal choice exists and we state it explicitly. However, for multiplicative depth the optimum does not exist globally, but we do show how to choose this best encoding depending on the use-case.

In this paper, we present a new and efficient construction of an Attribute-Based Authenticated Key Exchange (ABAKE) protocol, providing fine-grained access control over data. The state-of-the-art constructions of ABAKE protocols rely on extensive pairing and exponentiation operations (both polynomial in the size of the access policies) over appropriate groups equipped with bilinear maps. Our new construction of ABAKE protocol reduces the number of pairing operations to be constant (to be precise only 7) and the number of exponentiations to be linear in the number of clauses in the disjunctive normal form representing the general access policies. The main workhorse of our ABAKE construction is an Attribute-Based Signcryption (ABSC) scheme with constant number of pairings (only 7), which we construct. This also gives the first construction of ABSC schemes with constant number of pairings for general purpose access policies in the standard model. Our ABAKE protocol is also round-optimal, i.e., it is a single round protocol consisting of only a single message flow among the parties involved, and is asynchronous in nature, i.e., the message sent by one party does not depend on the incoming message from the other party. The security of our ABAKE protocol is proved under a variant of the Bilinear Diffie-Hellman Exponent assumption, in the Attribute-Based extended Canetti-Krawzyck (ABeCK) model, which is an extension of the extended Canetti-Krawzyck (eCK) model for attribute-based framework.

Group communication facilitates efficient data transmission to numerous receivers by reducing data replication efforts both at the sender and in the network. Group communication is used in today’s communication networks in many ways, such as broadcasting in cellular networks, IP multicast on the network layer, or as application layer multicast. Despite many efforts in providing data origin authentication for specific application areas in group communication, no efficient and secure all-purpose solution has been proposed so far.

In this paper, we analyze data origin authentication schemes from 25 years of research. We distinguish three general approaches to address the challenge and assign six conceptually different classes to these three approaches. We show that each class comprises trade-offs from a specific point of view that prevent the class from being generally applicable to group communication. We then propose to add a new class of schemes based on recent high-performance digital signatures. We argue that the high-speed signing approach is secure, resource efficient, and can be applied with acceptable communication overhead. This new class therefore provides a solution that is generally applicable and should be the foundation of future research on data origin authentication for group communication.

The threat of attacks on Home Automation Systems (HASs) is increasing. Research has shown that passive adversaries can detect user habits and interactions. Despite encryption and other measures becoming a standard, traffic analysis remains an unsolved problem. In this paper, we show that existing solutions from different research areas cannot be applied to this scenario. We establish a model for traffic analysis in Home Automation Systems which allows the analysis and comparison of attacks and countermeasures. We also take a look at legal aspects, highlighting problem areas and recent developments.

Mobile payment systems are pervasive; their design is driven by convenience and security. In this paper, we identify five common problems in existing systems: (i) specialist hardware requirements, (ii) no reader-to-user authentication, (iii) use of invisible channels, (iv) dependence on a client-server connection, and (v) no inherent fraud detection. We then propose a novel system which overcomes these problems, so as to mutually authenticate a user, a point-of-sale reader, and a verifier over a visual channel, using an embedded image token to transport information, while providing inherent unauthorised usage detection. We show our system to be resilient against replay and tampering attacks.