Since its inception, Rowhammer exploits have rapidly evolved into increasingly sophisticated threats compromising data integrity and the control flow integrity of victim processes. Nevertheless, it remains a challenge for an attacker to identify vulnerable targets (i.e., Rowhammer gadgets), understand the outcome of the attempted fault, and formulate an attack that yields useful results.In this paper, we present a new type of Rowhammer gadget, called a LeapFrog gadget, which, when present in the victim code, allows an adversary to subvert code execution to bypass a critical piece of code (e.g., authentication check logic, encryption rounds, padding in security protocols). The LeapFrog gadget manifests when the victim code stores the Program Counter (PC) value in the user or kernel stack (e.g., a return address during a function call) which, when tampered with, repositions the return address to a location that bypasses a security-critical code pattern.This research also presents a systematic process to identify LeapFrog gadgets. This methodology enables the automated detection of susceptible targets and the determination of optimal attack parameters. We first show the attack on a decision tree algorithm to show the potential implications. Secondly, we employ the attack on OpenSSL to bypass the encryption and reveal the plaintext. We then use our tools to scan the Open Quantum Safe library and report on the number of LeapFrog gadgets in the code. Lastly, we demonstrate this new attack vector through a practical demonstration in a client/server TLS handshake scenario, successfully inducing an instruction skip in a client application. Our findings extend the impact of Rowhammer attacks on control flow and contribute to developing more robust defenses against these increasingly sophisticated threats.

In the past decade, many vulnerabilities were discovered in microarchitectures which yielded attack vectors and motivated the study of countermeasures. Further, architectural and physical imperfections in DRAMs led to the discovery of Rowhammer attacks which give an adversary power to introduce bit flips in a victim's memory space. Numerous studies analyzed Rowhammer and proposed techniques to prevent it altogether or to mitigate its effects.

Bitslicing is a software implementation technique that treats an N -bit processor datapath as N parallel single-bit datapaths. Bitslicing is particularly useful to implement data-parallel algorithms, algorithms that apply the same operation sequence to every element of a vector. Indeed, a bit-wise processor instruction applies the same logical operation to every single-bit slice. A second benefit of bitsliced execution is that the natural spatial redundancy of bitsliced software can support countermeasures against fault attacks. A k -redundant program on an N -bit processor then runs as N/k parallel redundant slices. In this contribution, we combine these two benefits of bitslicing to implement a fault countermeasure for the number-theoretic transform (NTT) . The NTT efficiently implements a polynomial multiplication. The internal symmetry of the NTT algorithm lends itself to a data-parallel implementation, and hence it is a good candidate for the redundantly bitsliced implementation. We implement a redundantly bitsliced NTT on an advanced 667MHz ARM Cortex-A9 processor, and study the fault coverage for the protected NTT under optimized electromagnetic fault injection (EMFI) . Our work brings two major contributions. First, we show for the first time how to develop a redundantly bitsliced version of the NTT. We integrate the protected NTT into a full Dilithium signature sequence. Second, we demonstrate an EMFI analysis on a prototype implementation of the Dilithium signature sequence on ARM Cortex-M9. We perform a detailed EM fault-injection parameter search to optimize the location, intensity and timing of injected EM pulses. We demonstrate that, under optimized fault injection parameters, about 10% of the injected faults become potentially exploitable. However, the redundantly bitsliced NTT design is able to catch the majority of these potentially exploitable faults, even when the remainder of the Dilithium algorithm as well as the control flow is left unprotected. To our knowledge, this is the first demonstration of a bitslice-redundant design of the NTT that offers distributed fault detection throughout the execution of the algorithm.

Hardware peripherals such as GPUs and FPGAs are commonly available in server-grade computing to accelerate specific compute tasks, from database queries to machine learning. CSPs have integrated these accelerators into their infrastructure and let tenants combine and configure these components flexibly, based on their needs. Securing I/O interfaces is critical to ensure proper isolation between tenants in these highly complex, heterogeneous, yet shared server systems, especially in the cloud, where some peripherals may be under control of a malicious tenant.

State-of-the-art deep neural networks (DNNs) have been proven to be vulnerable to adversarial manipulation and backdoor attacks. Backdoored models deviate from expected behavior on inputs with predefined triggers while retaining performance on clean data. Recent works focus on software simulation of backdoor injection during the inference phase by modifying network weights, which we find often unrealistic in practice due to restrictions in hardware. In contrast, in this work for the first time, we present an end-to-end backdoor injection attack realized on actual hardware on a classifier model using Rowhammer as the fault injection method. To this end, we first investigate the viability of backdoor injection attacks in real-life deployments of DNNs on hardware and address such practical issues in hardware implementation from a novel optimization perspective. We are motivated by the fact that vulnerable memory locations are very rare, device-specific, and sparsely distributed. Consequently, we propose a novel network training algorithm based on constrained optimization to achieve a realistic backdoor injection attack in hardware. By modifying parameters uniformly across the convolutional and fully-connected layers as well as optimizing the trigger pattern together, we achieve state-of-the-art attack performance with fewer bit flips. For instance, our method on a hardware-deployed ResNet-20 model trained on CIFAR-10 achieves over 89% test accuracy and 92% attack success rate by flipping only 10 out of 2.2 million bits.

Digital Signature Schemes such as DSA, ECDSA, and RSA are widely deployed to protect the integrity of security protocols such as TLS, SSH, and IPSec. In TLS, for instance, RSA and (EC)DSA are used to sign the state of the agreed upon protocol parameters during the handshake phase. Naturally, RSA and (EC)DSA implementations have become the target of numerous attacks, including powerful side-channel attacks. Hence, cryptographic libraries were patched repeatedly over the years.Here we introduce Jolt, a novel attack targeting signature scheme implementations. Our attack exploits faulty signatures gained by injecting faults during signature generation. By using the signature verification primitive, we correct faulty signatures and, in the process deduce bits of the secret signing key. Compared to recent attacks that exploit single bit biases in the nonce that require 245signatures, our attack requires less than a thousand faulty signatures for a 256-bit (EC)DSA. The performance improvement is due to the fact that our attack targets the secret signing key, which does not change across signing sessions. We show that the proposed attack also works on Schnorr and RSA signatures with minor modifications.We demonstrate the viability of Jolt by running experiments targeting TLS handshakes in common cryptographic libraries such as WolfSSL, OpenSSL, Microsoft SymCrypt, LibreSSL, and Amazon s2n. On our target platform, the online phase takes less than 2 hours to recover 192 bits of a 256-bit ECDSA key, which is sufficient for full key recovery. We note that while RSA signatures are protected in popular cryptographic libraries, OpenSSL remains vulnerable to double fault injection. We have also reviewed their Federal Information Processing Standard (FIPS) hardened versions which are slightly less efficient but still vulnerable to our attack. We found that (EC)DSA signatures remain largely unprotected against software-only faults, posing a threat to real-life deployments such as TLS, and potentially other security protocols such as SSH and IPSec. This highlights the need for a thorough review and implementation of faults checking in security protocol implementations.

Motivated by the rise of quantum computers, existing public-key cryptosystems are expected to be replaced by post-quantum schemes in the next decade in billions of devices. To facilitate the transition, NIST is running a standardization process which is currently in its final Round. Only three digital signature schemes are left in the competition, among which Dilithium and Falcon are the ones based on lattices. Besides security and performance, significant attention has been given to resistance against implementation attacks that target side-channel leakage or fault injection response. Classical fault attacks on signature schemes make use of pairs of faulty and correct signatures to recover the secret key which only works on deterministic schemes. To counter such attacks, Dilithium offers a randomized version which makes each signature unique, even when signing identical messages. In this work, we introduce a novel Signature Correction Attack which not only applies to the deterministic version but also to the randomized version of Dilithium and is effective even on constant-time implementations using AVX2 instructions. The Signature Correction Attack exploits the mathematical structure of Dilithium to recover the secret key bits by using faulty signatures and the public-key. It can work for any fault mechanism which can induce single bit-flips. For demonstration, we are using Rowhammer induced faults. Thus, our attack does not require any physical access or special privileges, and hence could be also implemented on shared cloud servers. Using Rowhammer attack, we inject bit flips into the secret key s1 of Dilithium, which results in incorrect signatures being generated by the signing algorithm. Since we can find the correct signature using our Signature Correction algorithm, we can use the difference between the correct and incorrect signatures to infer the location and value of the flipped bit without needing a correct and faulty pair. To quantify the reduction in the security level, we perform a thorough classical and quantum security analysis of Dilithium and successfully recover 1,851 bits out of 3,072 bits of secret key$s_{1}$for security level 2. Fully recovered bits are used to reduce the dimension of the lattice whereas partially recovered coefficients are used to to reduce the norm of the secret key coefficients. Further analysis for both primal and dual attacks shows that the lattice strength against quantum attackers is reduced from 2128to 281while the strength against classical attackers is reduced from 2141 to 289. Hence, the Signature Correction Attack may be employed to achieve a practical attack on Dilithium (security level 2) as proposed in Round 3 of the NIST post-quantum standardization process.

Several techniques have been proposed to detect vulnerable Spectre gadgets in widely deployed commercial software. Unfortunately, detection techniques proposed so far rely on hand-written rules which fall short in covering subtle variations of known Spectre gadgets as well as demand a huge amount of time to analyze each conditional branch in software. Moreover, detection tool evaluations are based only on a handful of these gadgets, as it requires arduous effort to craft new gadgets manually. In this work, we employ both fuzzing and deep learning techniques to automate the generation and detection of Spectre gadgets. We first create a diverse set of Spectre-V1 gadgets by introducing perturbations to the known gadgets. Using mutational fuzzing, we produce a data set with more than 1 million Spectre-V1 gadgets which is the largest Spectre gadget data set built to date. Next, we conduct the first empirical usability study of Generative Adversarial Networks (GANs) in the context of assembly code generation without any human interaction. We introduce SpectreGAN which leverages masking implementation of GANs for both learning the gadget structures and generating new gadgets. This provides the first scalable solution to extend the variety of Spectre gadgets. Finally, we propose FastSpec which builds a classifier with the generated Spectre gadgets based on a novel high dimensional Neural Embeddings technique (BERT). For the case studies, we demonstrate that FastSpec discovers potential gadgets with a high success rate in OpenSSL libraries and Phoronix benchmarks. Further, FastSpec offers much greater flexibility and time-related performance gain compared to the existing tools and therefore can be used for gadget detection in large-scale software.

Homomorphic sorting is an operation that blindly sorts a given set of encrypted numbers without decrypting them (thus, there is no need for the secret key). In this article, we propose a new, efficient, and scalable method for homomorphic sorting of numbers: polynomial rank sort algorithm. To put the new algorithm in a comparative perspective, we provide an extensive survey of classical sorting algorithms and networks that are not directly suitable for homomorphic computation. We also include, in our discussions, two of our previous algorithms specifically designed for homomorphic sorting operation: direct and greedy sort, and explain how they evolve from classical sorting networks. We theoretically show that the new algorithm is superior in terms of multiplicative depth when compared with all other algorithms. When batched implementation is used, the number of comparisons is reduced from O(N2) to O(N) provided that the number of slots is larger than or equal to the number of elements in the set. Our software implementation results confirm that the new algorithm is several orders of magnitude faster than many methods in the literature. Also, the polynomial sort algorithm scales better than the fastest algorithm in the literature to the best our knowledge although for small sets the execution times are comparable. The proposed algorithm is amenable to parallel implementation as most time consuming operations in the algorithm can naturally be performed concurrently.

Post-quantum schemes are expected to replace existing public-key schemes within a decade in billions of devices. To facilitate the transition, the US National Institute for Standards and Technology (NIST) is running a standardization process. Multivariate signatures is one of the main categories in NIST's post-quantum cryptography competition. Among the four candidates in this category, the LUOV and Rainbow schemes are based on the Oil and Vinegar scheme, first introduced in 1997 which has withstood over two decades of cryptanalysis. Beyond mathematical security and efficiency, security against side-channel attacks is a major concern in the competition. The current sentiment is that post-quantum schemes may be more resistant to fault-injection attacks due to their large key sizes and the lack of algebraic structure. We show that this is not true. We introduce a novel hybrid attack, QuantumHammer, and demonstrate it on the constant-time implementation of LUOV currently in Round 2 of the NIST post-quantum competition. The QuantumHammer attack is a combination of two attacks, a bit-tracing attack enabled via Rowhammer fault injection and a divide and conquer attack that uses bit-tracing as an oracle. Using bit-tracing, an attacker with access to faulty signatures collected using Rowhammer attack, can recover secret key bits albeit slowly. We employ a divide and conquer attack which exploits the structure in the key generation part of LUOV and solves the system of equations for the secret key more efficiently with few key bits recovered via bit-tracing. We have demonstrated the first successful in-the-wild attack on LUOV recovering all 11K key bits with less than 4 hours of an active Rowhammer attack. The post-processing part is highly parallel and thus can be trivially sped up using modest resources. QuantumHammer does not make any unrealistic assumptions, only requires software co-location (no physical access), and therefore can be used to target shared cloud servers or in other sandboxed environments.

The recent Spectre attack first showed how to inject incorrect branch targets into a victim domain by poisoning microarchitectural branch prediction history. In this paper, we generalize injection-based methodologies to the memory hierarchy by directly injecting incorrect, attacker-controlled values into a victim's transient execution. We propose Load Value Injection (LVI) as an innovative technique to reversely exploit Meltdown-type microarchitectural data leakage. LVI abuses that faulting or assisted loads, executed by a legitimate victim program, may transiently use dummy values or poisoned data from various microarchitectural buffers, before eventually being re-issued by the processor. We show how LVI gadgets allow to expose victim secrets and hijack transient control flow. We practically demonstrate LVI in several proof-of-concept attacks against Intel SGX enclaves, and we discuss implications for traditional user process and kernel isolation. State-of-the-art Meltdown and Spectre defenses, including widespread silicon-level and microcode mitigations, are orthogonal to our novel LVI techniques. LVI drastically widens the spectrum of incorrect transient paths. Fully mitigating our attacks requires serializing the processor pipeline with lfence instructions after possibly every memory load. Additionally and even worse, due to implicit loads, certain instructions have to be blacklisted, including the ubiquitous x86 ret instruction. Intel plans compiler and assembler-based full mitigations that will allow at least SGX enclave programs to remain secure on LVI-vulnerable systems. Depending on the application and optimization strategy, we observe extensive overheads of factor 2 to 19 for prototype implementations of the full mitigation.

Meltdown and Spectre enable arbitrary data leakage from memory via various side channels. Short-term software mitigations for Meltdown are only a temporary solution with a significant performance overhead. Due to hardware fixes, these mitigations are disabled on recent processors. In this paper, we show that Meltdown-like attacks are still possible on recent CPUs which are not vulnerable to Meltdown. We identify two behaviors of the store buffer, a microarchitectural resource to reduce the latency for data stores, that enable powerful attacks. The first behavior, Write Transient Forwarding forwards data from stores to subsequent loads even when the load address differs from that of the store. The second, Store-to-Leak exploits the interaction between the TLB and the store buffer to leak metadata on store addresses. Based on these, we develop multiple attacks and demonstrate data leakage, control flow recovery, and attacks on ASLR. Our paper shows that Meltdown-like attacks are still possible, and software fixes with potentially significant performance overheads are still necessary to ensure proper isolation between the kernel and user space.

Over the past years, literature has shown that attacks exploiting the microarchitecture of modern processors pose a serious threat to user privacy. This is because applications leave distinct footprints in the processor, which malware can use to infer user activities. In this work, we show that these inference attacks can greatly be enhanced with advanced AI techniques. In particular, we focus on profiling the activity in the last-level cache (LLC) of ARM processors. We employ a simple Prime+Probe based monitoring technique to obtain cache traces, which we classify with deep learning methods including convolutional neural networks. We demonstrate our approach on an off-the-shelf Android phone by launching a successful attack from an unprivileged, zero-permission app in well under a minute. The app detects running applications, opened websites, and streaming videos with up to 98% accuracy and a profiling phase of at most 6 seconds. This is possible, as deep learning compensates measurement disturbances stemming from the inherently noisy LLC monitoring and unfavorable cache characteristics. In summary, our results show that thanks to advanced AI techniques, inference attacks are becoming alarmingly easy to execute in practice. This once more calls for countermeasures that confine microarchitectural leakage and protect mobile phone applications, especially those valuing the privacy of their users.

Microarchitectural side channels expose unprotected software to information leakage attacks where a software adversary is able to track runtime behavior of a benign process and steal secrets such as cryptographic keys. As suggested by incremental software patches for the RSA algorithm against variants of side-channel attacks within different versions of cryptographic libraries, protecting security-critical algorithms against side channels is an intricate task. Software protections avoid leakages by operating in constant time with a uniform resource usage pattern independent of the processed secret. In this respect, automated testing and verification of software binaries for leakage-free behavior is of importance, particularly when the source code is not available. In this work, we propose a novel technique based on Dynamic Binary Instrumentation and Mutual Information Analysis to efficiently locate and quantify memory based and control-flow based microarchitectural leakages. We develop a software framework named MicroWalk for side-channel analysis of binaries which can be extended to support new classes of leakage. For the first time, by utilizing MicroWalk, we perform rigorous leakage analysis of two widely-used closed-source cryptographic libraries: Intel IPP and Microsoft CNG. We analyze 15 different cryptographic implementations consisting of 112 million instructions in about 105 minutes of CPU time. By locating previously unknown leakages in hardened implementations, our results suggest that MicroWalk can efficiently find microarchitectural leakages in software binaries.

Microarchitectural attacks have gained popularity lately for the threat they pose and for their stealthiness. They are stealthy as they only exploit common harmless resources accessible at lowest privilege level, e.g. timed memory and cache accesses. Microarchitectural attacks have proven successful on shared cloud instances across VMs, on smartphones with sandboxing, and on numerous embedded platforms. Further they have shown to have catastrophic consequences such as critical data recovery or memory isolation bypassing. Due to the rise of malicious code, app store operators such as Microsoft, Apple and Google are already vetting apps before releasing them. Microarchitectural attacks however still bypass such detection mechanisms as they mainly utilize standard resources and look harmless. Given the rise of malicious code in app stores and in online repositories it becomes essential to scan applications for such stealthy attacks to prevent their distribution.

In this paper, we report on our implementation of a lattice-based key-policy attribute-based encryption (KP-ABE) scheme, which uses short secret keys. The particular KP-ABE scheme can be used directly for attribute-based access control applications, as well as a building block in more involved applications and cryptographic schemes, such as audit log encryption, targeted broadcast encryption, functional encryption, and program obfuscation. We adapt a recently proposed KP-ABE scheme based on the learning with errors (LWE) problem to a more efficient scheme based on the ring learning with errors (RLWE) problem, and demonstrate an implementation that can be used in practical applications. Our state-of-the-art implementation on graphics processing units shows that the homomorphic public key and ciphertext evaluation operations, which dominate the execution time of the KP-ABE scheme, can be performed in a reasonably short amount of time. Our practicality results also hold when scaled to a relatively large number of attributes. To the best of our knowledge, this is the first KP-ABE implementation that supports both ciphertext and public key homomorphism, and the only experimental practicality results reported in this paper.

Cross-VM attacks have emerged as a major threat on commercial clouds. These attacks commonly exploit hardware level leakages on shared physical servers. A co-located machine can readily feel the presence of a co-located instance with a heavy computational load through performance degradation due to contention on shared resources. Shared cache architectures such as the last level cache (LLC) have become a popular leakage source to mount cross-VM attack. By exploiting LLC leakages, researchers have already shown that it is possible to recover fine grain information such as cryptographic keys from popular software libraries. This makes it essential to verify implementations that handle sensitive data across the many versions and numerous target platforms, a task too complicated, error prone and costly to be handled by human beings. Here we propose a machine learning based technique to classify applications according to their cache access profiles. We show that with minimal and simple manual processing steps feature vectors can be used to train models using support vector machines to classify the applications with a high degree of success. The profiling and training steps are completely automated and do not require any inspection or study of the code to be classified. In native execution, we achieve a successful classification rate as high as 98% (L1 cache) and 78\% (LLC) over 40 benchmark applications in the Phoronix suite with mild training. In the cross-VM setting on the noisy Amazon EC2 the success rate drops to 60\% for a suite of 25 applications. With this initial study we demonstrate that it is possible to train meaningful models to successfully predict applications running in co-located instances.

Mobile apps need optimal performance and responsiveness to rise amongst numerous rivals on the market. Further, some apps like media streaming or gaming apps cannot even function properly with a performance below a certain threshold. In this work, we present the first performance degradation attack on Android OS that can target rival apps using a combination of logical channel leakages and low-level architectural bottlenecks in the underlying hardware. To show the viability of the attack, we design a proof-of-concept app and test it on various mobile platforms. The attack runs covertly and brings the target to the level of unresponsiveness. With less than 10% CPU time in the worst case, it requires minimal computational effort to run as a background service, and requires only the UsageStats permission from the user. We quantify the impact of our attack using 11 popular benchmark apps, running 44 different tests.} The measured QoS degradation varies across platforms and applications, reaching a maximum of 90\% in some cases. The attack combines the leakage from logical channels with low-level architectural bottlenecks to design a malicious app that can covertly degrade Quality of Service (QoS) of any targeted app. Furthermore, our attack code has a small footprint and is not detected by the Android system as malicious. Finally, our app can pass the Google Play Store malware scanner, Google Bouncer, as well as the top malware scanners in the Play Store.

After the introduction of first fully homomorphic encryption scheme in 2009, numerous research work has been published aiming at making fully homomorphic encryption practical for daily use. The first fully functional scheme and a few others that have been introduced has been proven difficult to be utilized in practical applications, due to efficiency reasons. Here, we propose a custom hardware accelerator, which is optimized for a class of reconfigurable logic, for Lopez-Alt, Tromer and Vaikuntanathan's somewhat homomorphic encryption based schemes. Our design is working as a co-processor which enables the operating system to offload the most compute-heavy operations to this specialized hardware. The core of our design is an efficient hardware implementation of a polynomial multiplier as it is the most compute-heavy operation of our target scheme. The presented architecture can compute the product of very-large polynomials in under 6.25 ms which is 102 times faster than its software implementation. In case of accelerating homomorphic applications; we estimate the per block homomorphic AES as 442 ms which is 28.5 and 17 times faster than the CPU and GPU implementations, respectively. In evaluation of Prince block cipher homomorphically, we estimate the performance as 52 ms which is 66 times faster than the CPU implementation.

Multi-processor systems are becoming the de-facto standard across different computing domains, ranging from high-end multi-tenant cloud servers to low-power mobile platforms. The denser integration of CPUs creates an opportunity for great economic savings achieved by packing processes of multiple tenants or by bundling all kinds of tasks at various privilege levels to share the same platform. This level of sharing carries with it a serious risk of leaking sensitive information through the shared microarchitectural components. Microarchitectural attacks initially only exploited core-private resources, but were quickly generalized to resources shared within the CPU. We present the first fine grain side channel attack that works across processors. The attack does not require CPU co-location of the attacker and the victim. The novelty of the proposed work is that, for the first time the directory protocol of high efficiency CPU interconnects is targeted. The directory protocol is common to all modern multi-CPU systems. Examples include AMD's HyperTransport, Intel's Quickpath, and ARM's AMBA Coherent Interconnect. The proposed attack does not rely on any specific characteristic of the cache hierarchy, e.g. inclusiveness. Note that inclusiveness was assumed in all earlier works. Furthermore, the viability of the proposed covert channel is demonstrated with two new attacks: by recovering a full AES key in OpenSSL, and a full ElGamal key in libgcrypt within the range of seconds on a shared AMD Opteron server.

In this work we show how the Lucky 13 attack can be resurrected in the cloud by gaining access to a virtual machine co-located with the target. Our version of the attack exploits distinguishable cache access times enabled by VM deduplication to detect dummy function calls that only happen in case of an incorrectly CBC-padded TLS packet. Thereby, we gain back a new covert channel not considered in the original paper that enables the Lucky 13 attack. In fact, the new side channel is significantly more accurate, thus yielding a much more effective attack. We briefly survey prominent cryptographic libraries for this vulnerability. The attack currently succeeds to compromise PolarSSL, GnuTLS and CyaSSL on deduplication enabled platforms while the Lucky 13 patches in OpenSSL, Mozilla NSS and MatrixSSL are immune to this vulnerability. We conclude that, any program that follows secret data dependent execution flow is exploitable by side-channel attacks as shown in (but not limited to) our version of the Lucky 13 attack.

Dividing last level caches into slices is a popular method to prevent memory accesses from becoming a bottleneck on modern multicore processors. In order to assess and understand the benefits of cache slicing in detail, a precise knowledge of implementation details such as the slice selection algorithm are of high importance. However, slice selection methods are mostly unstudied, and processor manufacturers choose not to publish their designs, nor their design rationale. In this paper, we present a tool that allows to recover the slice selection algorithm for Intel processors. The tool uses cache access information to derive equations that allow the reconstruction of the applied slice selection algorithm. Thereby, the tool enables further exploration of the behavior of modern caches. The tool is successfully applied to a range of Intel CPUs with different slices and architectures. Results show that slice selection algorithms have become more complex over time by involving an increasing number of bits of the physical address. We also demonstrate that among the most recent processors, the slice selection algorithm depends on the number of CPU cores rather than the processor model.

The cloud computing infrastructure relies on virtualized servers that provide isolation across guest OS's through sand boxing. This isolation was demonstrated to be imperfect in past work which exploited hardware level information leakages to gain access to sensitive information across co-located virtual machines (VMs). In response virtualization companies and cloud services providers have disabled features such as deduplication to prevent such attacks. In this work, we introduce a fine-grain cross-core cache attack that exploits access time variations on the last level cache. The attack exploits huge pages to work across VM boundaries without requiring deduplication. No configuration changes on the victim OS are needed, making the attack quite viable. Furthermore, only machine co-location is required, while the target and victim OS can still reside on different cores of the machine. Our new attack is a variation of the prime and probe cache attack whose applicability at the time is limited to L1 cache. In contrast, our attack works in the spirit of the flush and reload attack targeting the shared L3 cache instead. Indeed, by adjusting the huge page size our attack can be customized to work virtually at any cache level/size. We demonstrate the viability of the attack by targeting an Open SSL1.0.1f implementation of AES. The attack recovers AES keys in the cross-VM setting on Xen 4.1 with deduplication disabled, being only slightly less efficient than the flush and reload attack. Given that huge pages are a standard feature enabled in the memory management unit of OS's and that besides co-location no additional assumptions are needed, the attack we present poses a significant risk to existing cloud servers.

Abstract Software updates and security patches have become a standard method to fix known and recently discovered security vulnerabilities in deployed software. In server applications, outdated cryptographic libraries allow adversaries to exploit weaknesses and launch attacks with significant security results. The proposed technique exploits leakages at the hardware level to first, determine if a specific cryptographic library is running inside (or not) a co-located virtual machine (VM) and second to discover the IP of the co-located target. To this end, we use a Flush+Reload cache side-channel technique to measure the time it takes to call (load) a cryptographic library function. Shorter loading times are indicative of the library already residing in memory and shared by the VM manager through deduplication. We demonstrate the viability of the proposed technique by detecting and distinguishing various cryptographic libraries, including MatrixSSL, PolarSSL, GnuTLS, OpenSSL and CyaSSL along with the IP of the VM running these libraries. In addition, we show how to differentiate between various versions of libraries to better select an attack target as well as the applicable exploit. Our experiments show a complete attack setup scenario with single-trial success rates of up to 90% under light load and up to 50% under heavy load for libraries running in KVM.

We present a custom architecture for realizing the Gentry-Halevi fully homomorphic encryption (FHE) scheme. This contribution presents the first full realization of FHE in hardware. The architecture features an optimized multi-million bit multiplier based on the Schonhage Strassen multiplication algorithm. Moreover, a number of optimizations including spectral techniques as well as a precomputation strategy is used to significantly improve the performance of the overall design. When synthesized using 90 nm technology, the presented architecture achieves to realize the encryption, decryption, and recryption operations in 18.1 msec, 16.1 msec, and 3.1 sec, respectively, and occupies a footprint of less than 30 million gates.

In 2010, Gentry and Halevi presented the first FHE implementation. FHE allows the evaluation of arbitrary functions directly on encrypted data on untrusted servers. However, even for the small setting with 2048 dimensions, the authors reported a performance of 1.8 s for a single bit encryption and 32 s for recryption on a high-end server. Much of the latency is due to computationally intensive multi-million-bit modular multiplications. In this paper, we introduce two optimizations coupled with a novel precomputation technique. In the first optimization called partial FFT, we adopt Strassen’s FFT-based multiplication algorithm along with Barret reduction to speedup modular multiplications. For the encrypt primitive, we employ a window-based evaluation technique along with a modest degree of precomputation. In the full FFT optimization, we delay modular reductions and change the window algorithm, which allows us to carry out the bulk of computations in the frequency domain. We manage to eliminate all FFT conversion except the final inverse transformation drastically reducing the computation latency for all FHE primitives. We implemented the GH FHE scheme on two GPUs to further speedup the operations. Our experimental results with small parameter setting show speedups of 174, 7.6, and 13.5 times for encryption, decryption, and recryption, respectively, when compared to the Gentry–Halevi implementation. The speedup is enhanced in the medium setting. However, in the large setting, memory becomes the bottleneck and the speedup is somewhat diminished.

Cloud computing technology has rapidly evolved over the last decade, offering an alternative way to store and work with large amounts of data. However data security remains an important issue particularly when using a public cloud service provider. The recent area of homomorphic cryptography allows computation on encrypted data, which would allow users to ensure data privacy on the cloud and increase the potential market for cloud computing. A significant amount of research on homomorphic cryptography appeared in the literature over the last few years; yet the performance of existing implementations of encryption schemes remains unsuitable for real time applications. One way this limitation is being addressed is through the use of graphics processing units (GPUs) and field programmable gate arrays (FPGAs) for implementations of homomorphic encryption schemes. This review presents the current state of the art in this promising new area of research and highlights the interesting remaining open problems.

In this work we present the first full and complete evaluation of a very large multiplication scheme in custom hardware. We designed a novel architecture to realize a million-bit multiplication architecture based on the Schönhage-Strassen Algorithm and the Number Theoretical Transform (NTT). The construction makes use of an innovative cache architecture along with processing elements customized to match the computation and access patterns of the FFT-based recursive multiplication algorithm. When synthesized using a 90nm TSMC library operating at a frequency of 666 MHz, our architecture is able to compute the product of integers in excess of a million bits in 7.74 milliseconds. Estimates show that the performance of our design matches that of previously reported software implementations on a high-end 3 Ghz Intel Xeon processor, while requiring only a tiny fraction of the area.

The authors propose applying systematic non-linear error-detection codes to protect elliptic curve point addition and doubling operations against active fault attacks. These codes provide nearly perfect error-detection capability (except with exponentially small probability) at reasonable overhead. The proposed technique is applied to secure point addition and doubling operations for both Weierstrass and Edwards curves using different coordinate systems (i.e. affine and projective). The authors observe that the Weierstrass-based elliptic curve systems can be protected with reasonable area overhead. However, due to its balanced normal form, Edwards formulation is more appropriate for the non-linear error-detection technique proposed here. In addition, the proposed technique is compared with the method discussed by Gaubatz et al. (2006), where an error-detection technique is proposed for robust public key arithmetic. When compared with their method, the proposed technique provides approximately the same level of security with much less overhead. For Edwards curves, the overhead of the proposed scheme is less than half (42–46%) of the overhead of scheme proposed by Gaubatz et al. (2006). In addition, the overhead of the proposed scheme is 52–81% of the overhead of scheme proposed by Gaubatz et al. (2006) for different versions of the Weierstrass curves.

Driven by strong economic incentives the globalization of the semiconductor design and fabrication industries has given rise to numerous vulnerabilities in the manufacturing chain. From design to production countless hands contribute until fabrication is completed. An adversary can introduce a Trojan designed to disable and/or destroy a system at some future time or the Trojan may leak confidential information and secret keys covertly to the adversary. These vulnerabilities have raised serious concerns regarding possible threats to financial infrastructures, transportation security systems, and military systems. Clearly there is a strong motivation to classify and study adversarial hardware design modifications, i.e. hardware Trojan horses. Here we very briefly summarize types of hardware Trojans and refer the reader to relevant works.

Elliptic curve cryptosystems (ECCs) are utilised as an alternative to traditional public-key cryptosystems, and are more suitable for resource-limited environments because of smaller parameter size. In this study, the authors carry out a thorough investigation of side-channel attack aware ECC implementations over finite fields of prime characteristic including the recently introduced Edwards formulation of elliptic curves. The Edwards formulation of elliptic curves is promising in performance with built-in resiliency against simple side-channel attacks. To our knowledge the authors present the first hardware implementation for the Edwards formulation of elliptic curves. The authors also propose a technique to apply non-adjacent form (NAF) scalar multiplication algorithm with side-channel security using the Edwards formulation. In addition, the authors implement Joye's highly regular add-always scalar multiplication algorithm both with the Weierstrass and Edwards formulation of elliptic curves. Our results show that the Edwards formulation allows increased area–time performance with projective coordinates. However, the Weierstrass formulation with affine coordinates results in the simplest architecture, and therefore has the best area–time performance as long as an efficient modular divider is available.

A ring oscillator-based true-random number generator design (Rings design) was introduced in Sunar et al. [2007]. The design was rigorously analyzed under a simple mathematical model and its performance characteristics were established. In this article we focus on the practical aspects of the Rings design on a reconfigurable logic platform and determine their implications on the earlier analysis framework. We make recommendations for avoiding pitfalls in real-life implementations by considering ring interaction, transistor-level effects, narrow signal rejection, transmission line attenuation, and sampler bias. Furthermore, we present experimental results showing that changing operating conditions such as the power supply voltage or the operating temperature may affect the output quality when the signal is subsampled. Hence, an attacker may shift the operating point via a simple noninvasive influence and easily bias the TRNG output. Finally, we propose modifications to the design which significantly improve its robustness against attacks, alleviate implementation-related problems, and simultaneously improve its area, throughput, and power performance.

We propose an efficient technique for the detection of errors in cryptographic circuits introduced by strong adversaries. Previously a number of linear and non-linear error detection schemes were proposed. Linear codes provide protection only against primitive adversaries which no longer represents practice. On the other hand non-linear codes provide protection against strong adversaries, but at the price of high overhead. Here we propose a novel error detection technique, based on the random selection of linear codes. Under mild assumptions the proposed construction achieves near non-linear code error detection performance at much lower cost due to the fact that no non-linear operations are needed for the encoder and decoder.

The lack of robust tamper-proofing techniques in security applications has provided attackers the ability to virtually circumvent mathematically strong cryptographic primitives by directly attacking the hardware. Consequently, physical tamper-proofing has emerged as an essential element in secure system design. To this end, physical unclonable functions (PUF) have been proposed to build tamper proof hardware and thereby create secure data storages. A delay based PUF scheme was proposed which uses the intrinsic process variations to randomize switches and thereby implement a pseudorandom function family. When tampered with, the device experiences a change in its internal physical parameters. This will alter the pseudorandom function family. Therefore, rendering an attack unsuccessful. In this paper, we propose a delay based PUF circuit that is constructed from tristate buffers. The proposed PUF circuit consumes less power and requires less area. Furthermore, we develop a linear delay model which turns out to be identical to that of switch based PUFs. Hence, the nonlinearization techniques proposed to secure switch based PUFs can directly be applied to secure tristate PUFs as well.

Low cost devices such as RFIDs, sensor network nodes, and smartcards are crucial for building the next generation pervasive and ubiquitous networks. The inherent power and footprint limitations of such networks, prevent us from employing standard cryptographic techniques for authentication which were originally designed to secure high end systems with abundant power. Furthermore, the sharp increase in the number, diversity and strength of physical attacks which directly target the implementation may have devastating consequences in a network setting creating a single point of failure. A compromised node may leak a master key, or may give the attacker an opportunity for injecting faulty messages. In this paper we present a lightweight challenge response authentication scheme based on noisy physical unclonable functions (PUF) that allows for extremely efficient implementations. Furthermore, the inherent properties of PUFs provide cryptographically strong tamper resilience. In a network setting this means that a tampered device will no longer authenticate and in a sense will be isolated from the network.

In the relatively young field of fault tolerant cryptography the main research effort has focused exclusively on the protection of the data-path of cryptographic circuits. To date, however, we have not found any work that aims at protecting the control logic of these circuits against fault attacks, which thus remained as Achilles' proverbial heel. Motivated by an example of a hypothetical attack on an otherwise protected modular exponentiation engine we set out to close this remaining gap. In this paper we present guidelines for the design of t-fault resilient sequential control logic based on Error Detecting Codes (EDC). Our method allows to trade area overhead against fault resilience, and has the added benefit that the detection circuit does not add to the critical path.

Hardware manufacturers are increasingly outsourcing their IC fabrication work overseas due to their much lower cost structure. This poses a significant security risk for ICs used for critical military and business applications. Attackers can exploit this loss of control to substitute Trojan ICs for genuine ones or insert a Trojan circuit into the design or mask used for fabrication. We show that a technique borrowed from side-channel cryptanalysis can be used to mitigate this problem. Our approach uses noise modeling to construct a set of fingerprints/or an IC family utilizing side- channel information such as power, temperature, and electromagnetic (EM) profiles. The set of fingerprints can be developed using a few ICs from a batch and only these ICs would have to be invasively tested to ensure that they were all authentic. The remaining ICs are verified using statistical tests against the fingerprints. We describe the theoretical framework and present preliminary experimental results to show that this approach is viable by presenting results obtained by using power simulations performed on representative circuits with several different Trojan circuitry. These results show that Trojans that are 3-4 orders of magnitude smaller than the main circuit can be detected by signal processing techniques. While scaling our technique to detect even smaller Trojans in complex ICs with tens or hundreds of millions of transistors would require certain modifications to the IC design process, our results provide a starting point to address this important problem.

The Kasumi block cipher provides integrity and confidentiality services for 3G wireless networks, but it also forms a bottleneck due to its computational overhead. Especially in infrastructure equipment with data streams from multiple connections entering and leaving the network processor the critical performance issue needs to be addressed. In this paper we present a highly scalable bit sliced implementation of the Kasumi block cipher for the Intel IXP 28xx family of network processors. It can achieve a maximum theoretical encryption rate of up to 2 Gb/s when run in parallel on all 16 on-chip microengines

Message authentication codes (MACs) are valuable tools for ensuring the integrity of messages. MACs may be built around a universal hash function (NH) which was explored in the construction of UMAC. In this paper, we use a variation on NH called WH. WH reaches optimally in the sense that it is universal with half the hash length of NH and it achieves perfect serialization in hardware implementation. We achieved substantial power savings of up to 59 percent and a speedup of up to 7.4 times over NH. Moreover, we show how the technique of multihashing and the Toeplitz approach can be combined to reduce the power and energy consumption even further while maintaining the same security level with a very slight increase in the amount of the key material. At low frequencies, the power and energy reductions are achieved simultaneously while keeping the hashing time constant. We developed formulae for estimation of the leakage and dynamic power consumptions as well as the energy consumption based on the frequency and the Toeplitz parameter t. We introduce a powerful method for scaling WH according to specific energy and power consumption requirements. Our implementation of WH-16 consumes only 2.95 /spl mu/W at 500 kHz. It can therefore be integrated into a self-powered device.

We describe an efficient method for constructing the basis conversion matrix between two given finite field representations where one is composite. We are motivated by the fact that using certain representations, e.g., low-Hamming weight polynomial or composite field representations, permits arithmetic operations such as multiplication and inversion to be computed more efficiently. An earlier work by Paar defines the conversion problem and outlines an exponential time algorithm that requires an exhaustive search in the field. Another algorithm by Sunar et al. provides a polynomial time algorithm for the limited case where the second representation is constructed (rather than initially given). The algorithm we present facilitates existing factorization algorithms and provides a randomized polynomial time algorithm to solve the basis conversion problem where the two representations are initially given. We also adapt a fast trace-based factorization algorithm to work in the composite field setting which yields a subcubic complexity algorithm for the construction of the basis conversion matrix.

We introduce a new tower field representation, optimal tower fields (OTFs), that facilitates efficient finite field operations. The recursive direct inversion method we present has significantly lower complexity than the known best method for inversion in optimal extension fields (OEFs), i.e., Itoh-Tsujii's inversion technique. The complexity of our inversion algorithm is shown to be O(m/sup 2/), significantly better than that of the Itoh-Tsujii algorithm, i.e., O(m/sup 2/(log/sub 2/m.)). This complexity is further improved to O(m/sup log//sub 2//sup 3/) by utilizing the Karatsuba-Ofman algorithm. In addition, we show that OTFs may be converted to OEF representation via a simple permutation of the coefficients and, hence, OTF operations may be utilized to achieve the OEF arithmetic operations whenever a corresponding OTF representation exists. While the original OTF multiplication and squaring operations require slightly more additions than their OEF counterparts, due to the free conversion, both OTF operations may be achieved with the complexity of OEF operations.

We introduce a generalized method for constructing subquadratic complexity multipliers for even characteristic field extensions. The construction is obtained by recursively extending short convolution algorithms and nesting them. To obtain the short convolution algorithms, the Winograd short convolution algorithm is reintroduced and analyzed in the context of polynomial multiplication. We present a recursive construction technique that extends any d point multiplier into an n=d/sup k/ point multiplier with area that is subquadratic and delay that is logarithmic in the bit-length n. We present a thorough analysis that establishes the exact space and time complexities of these multipliers. Using the recursive construction method, we obtain six new constructions, among which one turns out to be identical to the Karatsuba multiplier. All six algorithms have subquadratic space complexities and two of the algorithms have significantly better time complexities than the Karatsuba algorithm.

We propose a new unified architecture that utilizes the Montgomery multiplication algorithm to perform a modular multiplication for both integers and binary polynomials and NTRU's polynomial multiplications. The unified design is capable of supporting a majority of public-key cryptosystems such as NTRU, RSA, Diffie-Hellman key exchange, and elliptic curve schemes, among others. Furthermore, the architecture is highly efficient in terms of area and speed.

We describe a method of construction of a composite field representation from a given binary field representation. We derive the conversion (change of basis) matrix. The special case of when the degree of the ground field is relatively prime to the extension degree, where the irreducible polynomial generating the composite field has its coefficients from the binary prime field rather than the ground field, is also treated. Furthermore, certain generalizations of the proposed construction method, e.g., the use of nonprimitive elements and the construction of composite fields with special irreducible polynomials, are also discussed. Finally, we give storage-efficient conversion algorithms between the binary and composite fields when the degree of the ground field is relatively prime to the extension degree.

This paper presents a new parallel multiplier for the Galois field GF(2/sup m/) whose elements are represented using the optimal normal basis of type II. The proposed multiplier requires 1.5(m/sup 2/-m) XOR gates, as compared to 2(m/sup 2/-m) XOR gates required by the Massey-Omura multiplier. The time complexities of the proposed and the Massey-Omura multipliers are similar.

An efficient algorithm for the multiplication in GF(2/sup m/) was introduced by Mastrovito. The space complexity of the Mastrovito multiplier for the irreducible trinomial x/sup m/+x+1 was given as m/sup 2/-1 XOR and m/sup 2/ AND gales. In this paper, we describe an architecture based on a new formulation of the multiplication matrix and show that the Mastrovito multiplier for the generating trinomial x/sup m/+x/sup n/+1, where m/spl ne/2n, also requires m/sup 2/-1 XOR and m/sup 2/ AND gates, However, m/sup 2/-x/sup m/2/ XOR gates are sufficient when the generating trinomial is of the form x/sup m/+x/sup m/2/+1 for an even m. We also calculate the time complexity of the proposed Mastrovito multiplier and give design examples for the irreducible trinomials x/sup 7/+x/sup 4/+1 and x/sup 6/+x/sup 3/+1.

We present a new low-complexity bit-parallel canonical basis multiplier for the field GF(2m) generated by an all-one-polynomial. The proposed canonical basis multiplier requires m/sup 2/-1 XOR gates and m/sup 2/ AND gates. We also extend this canonical basis multiplier to obtain a new bit-parallel normal basis multiplier.