Helmholtz Center for Information Security
CISPA – Helmholtz-Zentrum für InformationssicherheitNot a member yet
3406 research outputs found
Sort by
(Nondeterministic) Hardness vs. Non-Malleability
Get PDFWe present the first truly explicit constructions of non-malleable codes against tampering by bounded polynomial size circuits. These objects imply unproven circuit lower bounds and our con- struction is secure provided E requires exponential size nondeterministic circuits, an assumption from the derandomization literature.
Prior works on NMC for polysize circuits, either required an untamperable CRS [Cheraghchi, Gu- ruswami ITCS’14; Faust, Mukherjee, Venturi, Wichs EUROCRYPT’14] or very strong cryptographic assumptions [Ball, Dachman-Soled, Kulkarni, Lin, Malkin EUROCRYPT’18; Dachman-Soled, Komar- godski, Pass CRYPTO’21]. Both of works in the latter category only achieve non-malleability with respect to efficient distinguishers and, more importantly, utilize cryptographic objects for which no provably secure instantiations are known outside the random oracle model. In this sense, none of the prior yields fully explicit codes from non-heuristic assumptions. Our assumption is not known to imply the existence of one-way functions, which suggests that cryptography is unnecessary for non-malleability against this class.
Technically, security is shown by non-deterministically reducing polynomial size tampering to split- state tampering. The technique is general enough that it allows us to to construct the first seedless non-malleable extractors [Cheraghchi, Guruswami TCC’14] for sources sampled by polynomial size circuits [Trevisan, Vadhan FOCS’00] (resp. recognized by polynomial size circuits [Shaltiel CC’11]) and tampered by polynomial size circuits. Our construction is secure assuming E requires exponential size Σ4-circuits (resp. Σ3-circuits), this assumption is the state-of-the-art for extracting randomness from such sources (without non-malleability).
We additionally observe that non-malleable codes and non-malleable secret sharing [Goyal, Kumar STOC’18] are essentially equivalent with respect to polynomial size tampering. In more detail, assuming E is hard for exponential size nondeterministic circuits, any efficient secret sharing scheme can be made non-malleable against polynomial size circuit tampering.
Unfortunately, all of our constructions only achieve inverse polynomial (statistical) security. Extending a result from [Applebaum, Artemenko, Shaltiel, Yang CC’16] we show it is impossible to do better using black-box reductions. However, we extend the notion of relative error from [Applebaum, Artemenko, Shaltiel, Yang CC’16] to non-malleable extractors and show that they can be constructed from similar assumptions. We additionally observe that relative-error non-malleable extractors can be utilized to render a broad class of cryptographic primitives tamper and leakage resilient, while preserving negligible security guarantees
Discovering Invariant and Changing Mechanisms from Data
Get PDFWhile invariance of causal mechanisms has inspired recent work in both robust machine learning and causal inference, causal mech- anisms often vary over domains due to, for example, population- specific differences, the context of data collection, or intervention. To discover invariant and changing mechanisms from data, we pro- pose extending the algorithmic model for causation to mechanism changes and instantiating it via Minimum Description Length. In essence, for a continuous variable ???? in multiple contexts C, we identify variables ???? as causal if the regression functions ???? : ???? → ???? have succinct descriptions in all contexts. In empirical evaluations we show that our method, Vario, reveals mechanism changes, dis- covers causal variables by invariance, and finds causal networks, such as on real-world data that gives insight into the signaling pathways in human immune cells
Robust and Scalable Process Isolation against Spectre in the Cloud
Get PDFIn the quest for efficiency and performance, edge-computing providers replace process isolation with sandboxes, to support a high number of tenants per machine. While secure against software vulnerabilities, microarchitectural attacks can bypass these sandboxes. In this paper, we present a Spectre attack leaking secrets from co-located tenants in edge computing. Our remote Spectre attack, using amplification techniques and a remote timing server, leaks 2 bit/min. This motivates our main contribution, DyPrIs, a scalable process-isolation mechanism that only isolates suspicious worker scripts following a lightweight detection mechanism. In the worst case, DyPrIs boils down to process isolation. Our proof-of-concept implementation augments real-world cloud infrastructure used in production at large scale, Cloudflare Workers. With a false-positive rate of only 0.61 %, we demonstrate that DyPrIs outperforms strict process isolation while statistically maintaining its security guarantees, fully mitigating cross-tenant Spectre attacks
Sample Compression Schemes for Balls in Graphs
Get PDFOne of the open problems in machine learning is whether any set-family of VC-dimension d admits
a sample compression scheme of size O(d). In this paper, we study this problem for balls in graphs.
For balls of arbitrary radius r, we design proper sample compression schemes of size 4 for interval
graphs, of size 6 for trees of cycles, and of size 22 for cube-free median graphs. We also design
approximate sample compression schemes of size 2 for balls of δ-hyperbolic graphs
Randomized Message-Interception Smoothing: Gray-box Certificates for Graph Neural Networks
Get PDFRandomized smoothing is one of the most promising frameworks for certifying the adversarial robustness of machine learning models, including Graph Neural Networks (GNNs). Yet, existing randomized smoothing certificates for GNNs are overly pessimistic since they treat the model as a black box, ignoring the underlying architecture. To remedy this, we propose novel gray-box certificates that exploit the message-passing principle of GNNs: We randomly intercept messages and carefully analyze the probability that messages from adversarially controlled nodes reach their target nodes. Compared to existing certificates, we certify robustness to much stronger adversaries that control entire nodes in the graph and can arbitrarily manipulate node features. Our certificates provide stronger guarantees for attacks at larger distances, as messages from farther-away nodes are more likely to get intercepted. We demonstrate the effectiveness of our method on various models and datasets. Since our gray-box certificates consider the underlying graph structure, we can significantly improve certifiable robustness by applying graph sparsification
Smooth Transition of Vehicles' Maximum Speed for Lane Detection based on Computer Vision
Get PDFThis paper presents a prototype electric scooter designed to detect the driving lane via computer vision and automatically set the vehicular configuration. The electric scooter can drive on the pedestrian, bicycle, or car lanes. The government enforces maximum speeds on each lane for the electric scooter.
Our prototype scooter would apply those regulations securely, with the help of a computer vision component. However, the safety of such a system is still part of the concern and research is going on the security and safety aspects of such vehicular systems. The maximum speed changes while the driver is riding the vehicle at the fastest possible speed could cause a safety hazard. To prevent that, we proposed to use the logarithmic speed reduction or acceleration. The results show that such an algorithm will smooth the transition between the maximum of the vehicle
Rapid Prototyping for Microarchitectural Attacks
Get PDFIn recent years, microarchitectural attacks have been demonstrated to be a powerful attack class. However, as our empirical analysis shows, there are numerous implementation challenges that hinder discovery and subsequent mitigation of these vulnerabilities. In this paper, we examine the attack development process, the features and usability of existing tools, and the real-world challenges faced by practitioners. We propose a novel approach to microarchitectural attack development, based on rapid prototyping, and present two open-source software frameworks, libtea and SCFirefox, that improve upon state-of-the-art tooling to facilitate rapid prototyping of attacks.
libtea demonstrates that native code attacks can be abstracted sufficiently to permit cross-platform implementations while retaining fine-grained control of microarchitectural behavior. We evaluate its effectiveness by developing proof-of-concept Foreshadow and LVI attacks. Our LVI prototype runs on x86-64 and ARMv8-A, and is the first public demonstration of LVI on ARM. SCFirefox is the first tool for browser-based microarchitectural attack development, providing the functionality of libtea in JavaScript. This functionality can then be used to iteratively port a prototype to unmodified browsers. We demonstrate this process by prototyping the first browser-based ZombieLoad attack and deriving a vanilla JavaScript and WebAssembly PoC running in an unmodified recent version of Firefox. We discuss how libtea and SCFirefox contribute to the security landscape by providing attack researchers and defenders with frameworks to prototype attacks and assess their feasibility
Repurposing Segmentation as a Practical LVI-NULL Mitigation in SGX
Get PDFLoad Value Injection (LVI) uses Meltdown-type data flows in Spectre-like confused-deputy attacks. LVI has been demonstrated in practical attacks on Intel SGX enclaves, and consequently, mitigations were deployed that incur tremendous overheads of factor 2 to 19. However, as we discover, on fixed hardware LVI-NULL leakage is still present. Hence, to mitigate LVI-NULL in SGX enclaves on LVI-fixed CPUs, the expensive mitigations would still be necessary.
In this paper, we propose a lightweight mitigation focused on LVI-NULL in SGX, LVI-NULLify. We systematically analyze and categorize LVI-NULL variants. Our analysis reveals that previously proposed mitigations targeting LVI-NULL are not effective. Our novel mitigation addresses this problem by repurposing segmentation, a fast legacy hardware mechanism that x86 already uses for every memory operation. LVI-NULLify consists of a modified SGX-SDK and a compiler extension which put the enclave in control of LVI-NULL-exploitable memory locations. We evaluate LVI-NULLify on the LVI-fixed Comet Lake CPU and observe a performance overhead below 10% for the worst case, which is substantially lower than previous defenses with a prohibitive overhead of 1220% in the worst case. We conclude that LVI-NULLify is a practical solution to protect SGX enclaves against LVI-NULL today
An open door may tempt a saint: Examining situational and individual determinants of privacy-invading behavior
Get PDFDigital life enables situations where people invade other’s privacy -- sometimes with harmful intentions but often also without such. Given negative effects on victims of privacy invasions, research has examined technical options to prevent privacy-invading behavior (PIB). However, little is known about the sociotechnical environment where PIB occurs. Therefore, our study N=95) examined possible situational (effort necessary to invade privacy) and individual determinants (e.g., personality) of PIB in a three-phase experiment. 1) Laboratory phase: participants were immersed into the scenario; 2) privacy-invasion-phase at home: automatically and covertly capturing participants’ PIB; 3) debriefing-phase at home: capturing whether participants admit PIB. Our results contribute to understanding the sociotechnical environment in which PIB occurs showing that most participants engaged in PIB, that the likelihood of PIB increased when it required less effort, that participants less likely admitted PIB for more sensitive information, and that individual characteristics affected whether participants admitted PIB. We discuss implications for privacy research and design
IBE with Incompressible Master Secret and Small Identity Secrets
No full textSide-stepping the protection provided by cryptography, exfiltration attacks are becoming a considerable real-world threat. With the goal of mitigating the exfiltration of cryptographic keys, big-key cryptosystems have been developed over the past few years. These systems come with very large secret keys which are thus hard to exfiltrate. Typically, in such systems, the setup time must be large as it generates the large secret key. However, subsequently, the encryption and decryption operations, that must be performed repeatedly, are required to be efficient. Specifically, the encryption uses only a small public key and the decryption only accesses small ciphertext-dependent parts of the full secret key. Nonetheless, these schemes require decryption to have access to the entire secret key. Thus, using such big-key cryptosystems necessitate that users carry around large secret-keys on their devices, which can be a hassle and in some cases might also render exfiltration easy.
With the goal of removing this problem, in this work, we initiate the study of big-key identity-based encryption (bk-IBE). In such a system, the master secret-key is allowed to be large but we require that the identity-based secret keys are short. This allows users to use the identity-based short keys as the ephemeral secret keys that can be more easily carried around and allow for decrypting ciphertexts matching a particular identity, e.g. messages that were encrypted on a particular date. In particular:
We build a new definitional framework for bk-IBE capturing a range of applications. In the case when the exfiltration is small our definition promises stronger security—namely, an adversary can break semantic security for only a few identities, proportional to the amount of leakage it gets. In contrast, in the catastrophic case where a large fraction of the master secret key has been ex-filtrated, we can still resort to a guarantee that the ciphertexts generated for a randomly chosen identity (or, an identity with enough entropy) remain protected. We demonstrate how this framework captures the best possible security guarantees.
We show the first construction of such a bk-IBE offering strong security properties. Our construction is based on standard assumptions on groups with bilinear pairings and brings together techniques from seemingly different contexts such as leakage resilient cryptography, reusable two-round MPC, and laconic oblivious transfer. We expect our techniques to be of independent interest