91 results sorted by ID
STORM — Small Table Oriented Redundancy-based SCA Mitigation for AES
Yaacov Belenky, Hennadii Chernyshchyk, Oleg Karavaev, Oleh Maksymenko, Valery Teper, Daria Ryzhkova, Itamar Levi, Osnat Keren, Yury Kreimer
Attacks and cryptanalysis
Side-channel-analysis (SCA) resistance with cost optimization in AES hardware implementations remains a significant challenge. While traditional masking-based schemes offer provable security, they often incur substantial resource overheads (latency, area, randomness, performance, power consumption). Alternatively, the RAMBAM scheme introduced a redundancy-based approach to control the signal-to-noise ratio, and achieves exponential leakage reduction as redundancy increases. This method...
Towards Quantum-Safe Blockchain: Exploration of PQC and Public-key Recovery on Embedded Systems
Dominik Marchsreiter
Applications
Blockchain technology ensures accountability,
transparency, and redundancy in critical applications, includ-
ing IoT with embedded systems. However, the reliance on
public-key cryptography (PKC) makes blockchain vulnerable to
quantum computing threats. This paper addresses the urgent
need for quantum-safe blockchain solutions by integrating Post-
Quantum Cryptography (PQC) into blockchain frameworks.
Utilizing algorithms from the NIST PQC standardization pro-
cess, we aim to fortify...
A Formal Treatment of End-to-End Encrypted Cloud Storage
Matilda Backendal, Hannah Davis, Felix Günther, Miro Haller, Kenneth G. Paterson
Applications
Users increasingly store their data in the cloud, thereby benefiting from easy access, sharing, and redundancy. To additionally guarantee security of the outsourced data even against a server compromise, some service providers have started to offer end-to-end encrypted (E2EE) cloud storage. With this cryptographic protection, only legitimate owners can read or modify the data. However, recent attacks on the largest E2EE providers have highlighted the lack of solid foundations for this...
Consolidated Linear Masking (CLM): Generalized Randomized Isomorphic Representations, Powerful Degrees of Freedom and Low(er)-cost
Itamar Levi, Osnat Keren
Implementation
Masking is a widely adopted countermeasure against side-channel analysis (SCA) that protects cryptographic implementations from information leakage. However, current masking schemes often incur significant overhead in terms of electronic cost. RAMBAM, a recently proposed masking technique that fits elegantly with the AES algorithm, offers ultra-low latency/area by utilizing redundant representations of finite field elements. This paper presents a comprehensive generalization of RAMBAM and...
Chocobo: Creating Homomorphic Circuit Operating with Functional Bootstrapping in basis B
Pierre-Emmanuel Clet, Aymen Boudguiga, Renaud Sirdey
Applications
The TFHE cryptosystem only supports small plaintext space, up to 5 bits with usual parameters. However, one solution to circumvent this limitation is to decompose input messages into a basis B over multiple ciphertexts. In this work, we introduce B-gates, an extension of logic gates to non binary bases, to compute base B logic circuit. The flexibility introduced by our approach improves the speed performance over previous approaches such as the so called tree-based method which requires an...
Efficient Implementations of Square-root Vélu's Formulas
Jianming Lin, Weize Wang, Chang-An Zhao, Yuhao Zheng
Implementation
In the implementation of isogeny-based schemes, V\'{e}lu's formulas are essential for constructing and evaluating odd degree isogenies.
Bernstein et al. proposed an approach known as $\surd$elu, which computes an $\ell$-isogeny at a cost of $\tilde{\mathcal{O}}(\sqrt{\ell})$ finite field operations. This paper presents two key improvements to enhance the efficiency of
the implementation
of
$\surd$\'{e}lu from two aspects: optimizing the partition involved in $\surd$\'{e}lu and speeding...
Leakage-Resilient Attribute-Based Encryption with Attribute-Hiding
Yijian Zhang, Yunhao Ling, Jie Chen, Luping Wang
Public-key cryptography
In this work, we present two generic frameworks for leakage-resilient attribute-based encryption (ABE), which is an improved version of ABE that can be proven secure even when part of the secret key is leaked. Our frameworks rely on the standard assumption ($k$-Lin) over prime-order groups. The first framework is designed for leakage-resilient ABE with attribute-hiding in the bounded leakage model. Prior to this work, no one had yet derived a generic leakage-resilient ABE framework with...
Combined Threshold Implementation
Jakob Feldtkeller, Jan Richter-Brockmann, Pascal Sasdrich, Tim Güneysu
Implementation
Physical security is an important aspect of devices for which an adversary can manipulate the physical execution environment. Recently, more and more attention has been directed towards a security model that combines the capabilities of passive and active physical attacks, i.e., an adversary that performs fault-injection and side-channel analysis at the same time. Implementing countermeasures against such a powerful adversary is not only costly but also requires the skillful combination of...
Fault-Resistant Partitioning of Secure CPUs for System Co-Verification against Faults
Simon Tollec, Vedad Hadžić, Pascal Nasahl, Mihail Asavoae, Roderick Bloem, Damien Couroussé, Karine Heydemann, Mathieu Jan, Stefan Mangard
Implementation
Fault injection attacks are a serious threat to system security, enabling attackers to bypass protection mechanisms or access sensitive information. To evaluate the robustness of CPU-based systems against these attacks, it is essential to analyze the consequences of the fault propagation resulting from the complex interplay between the software and the processor. However, current formal methodologies combining hardware and software face scalability issues due to the monolithic approach...
Small Stretch Problem of the DCT Scheme and How to Fix It
Yuchao Chen, Tingting Guo, Lei Hu, Lina Shang, Shuping Mao, Peng Wang
Secret-key cryptography
DCT is a beyond-birthday-bound~(BBB) deterministic authenticated encryption~(DAE) mode proposed by Forler et al. in ACISP 2016, ensuring integrity by redundancy. The instantiation of DCT employs the BRW polynomial, which is more efficient than the usual polynomial in GCM by reducing half of the multiplication operations. However, we show that DCT suffers from a small stretch problem similar to GCM. When the stretch length $\tau$ is small, choosing a special $m$-block message, we can reduce...
Optimizing S-box Implementations Using SAT Solvers: Revisited
Fuxin Zhang, Zhenyu Huang
Implementation
We propose a new method to encode the problems of optimizing S-box implementations into SAT problems. By considering the inputs and outputs of gates as Boolean functions, the fundamental idea of our method is representing the relationships between these inputs and outputs according to their algebraic normal forms. Based on this method, we present several encoding schemes for
optimizing S-box implementations according to various criteria, such as multiplicative complexity, bitslice gate...
Leaky McEliece: Secret Key Recovery From Highly Erroneous Side-Channel Information
Marcus Brinkmann, Chitchanok Chuengsatiansup, Alexander May, Julian Nowakowski, Yuval Yarom
Attacks and cryptanalysis
The McEliece cryptosystem is a strong contender for post-quantum schemes, including key encapsulation for confidentiality of key exchanges in network protocols.
A McEliece secret key is a structured parity check matrix that is transformed via Gaussian elimination into an unstructured public key. We show that this transformation is a highly critical operation with respect to side-channel leakage.
We assume leakage of the elementary row operations during Gaussian elimination, motivated by...
A Novel Mathematical Formal Proof in Unreliability Protocol with XOR in Two's Complement System
Chenglian Liu, Sonia Chien-I Chen
Attacks and cryptanalysis
Exclusive OR (XOR), a common Boolean logical operation, is an operation on two factors where the result is true if and only if one operand is true and the other is false. A simple way to state this is ``one or the other, but not both''. Using this logical operation, a text string can be encrypted by applying the XOR operator to every character using a ``key''. If you want to decrypt the output, simply reapply the key and the resulting output will be the original message.
Comment on Enhanced DNA and ElGamal cryptosystem for secure data storage and retrieval in cloud
Chenglian Liu, Sonia Chien-I Chen
Attacks and cryptanalysis
Thangavel and Varalakshmi proposed an enhanced DNA and ElGamal cryptosystem for secure data storage and retrieval in cloud. They modified ElGamal algorithm which it calls enhanced ElGamal cryptosystem. We prove that their enhanced ElGamal scheme, which does not require two random numbers by data owner. Although the attacker is unable to find out what message the data owner gave to the data user. However, the attackers can still confuse the issue of sending messages to data users. On the...
PMNS revisited for consistent redundancy and equality test
Fangan Yssouf Dosso, Alexandre Berzati, Nadia El Mrabet, Julien Proy
Public-key cryptography
The Polynomial Modular Number System (PMNS) is a non-positional number system for modular arithmetic. A PMNS is defined by a tuple $(p, n, \gamma, \rho, E)$, where $p$, $n$, $\gamma$ and $\rho$ are positive non-zero integers and $E\in\mathbb{Z}_{n}[X]$ is a monic polynomial such that $E(\gamma) \equiv 0 \pmod p$.
The PMNS is a redundant number system. This redundancy property has already been used to randomise the data during the Elliptic Curve Scalar Multiplication (ECSM).
In this paper,...
From Unbalanced to Perfect: Implementation of Low Energy Stream Ciphers
Jikang Lin, Jiahui He, Yanhong Fan, Meiqin Wang
Implementation
Low energy is an important aspect of hardware implementation. For energy-limited battery-powered devices, low energy stream ciphers can play an important role. In \texttt{IACR ToSC 2021}, Caforio et al. proposed the Perfect Tree energy model for stream cipher that links the structure of combinational logic circuits with state update functions to energy consumption. In addition, a metric given by the model shows a negative correlation with energy consumption, i.e., the higher the balance of...
Muckle : End-to-End Hybrid Authenticated Key Exchanges
Sonja Bruckner, Sebastian Ramacher, Christoph Striecks
Cryptographic protocols
End-to-end authenticity in public networks plays a significant role. Namely, without authenticity, the adversary might be able to retrieve even confidential information straight away by impersonating others. Proposed solutions to establish an authenticated channel cover pre-shared key-based, password-based, and certificate-based techniques. To add confidentiality to an authenticated channel, authenticated key exchange (AKE) protocols usually have one of the three solutions built in. As an...
SPDH-Sign: towards Efficient, Post-quantum Group-based Signatures
Christopher Battarbee, Delaram Kahrobaei, Ludovic Perret, Siamak F. Shahandashti
Cryptographic protocols
In this paper, we present a new diverse class of post-quantum group-based Digital Signature Schemes (DSS). The approach is significantly different from previous examples of group-based digital signatures and adopts the framework of group action-based cryptography: we show that each finite group defines a group action relative to the semidirect product of the group by its automorphism group, and give security bounds on the resulting signature scheme in terms of the group-theoretic...
PEO-Store: Practical and Economical Oblivious Store with Peer-to-Peer Delegation
Wenlong Tian, Jian Guo, Zhiyong Xu, Ruixuan Li, Weijun Xiao
Applications
The growing popularity of cloud storage has brought attention to critical need for preventing information leakage from cloud access patterns. To this end, recent efforts have extended Oblivious RAM (ORAM) to the cloud environment in the form of Oblivious Store. However, its impracticality due to the use of probability encryption with fake accesses to obfuscate the access pattern, as well as the security requirements of conventional obliviousness designs, which hinder cloud interests in...
On Protecting SPHINCS Against Fault Attacks
Aymeric Genêt
Attacks and cryptanalysis
SPHINCS is a hash-based digital signature scheme that was selected by NIST in their post-quantum cryptography standardization process. The establishment of a universal forgery on the seminal scheme SPHINCS was shown to be feasible in practice by injecting a fault when the signing device constructs any non-top subtree. Ever since the attack has been made public, little effort was spent to protect the SPHINCS family against attacks by faults. This paper works in this direction in the context...
IsoLock: Thwarting Link-Prediction Attacks on Routing Obfuscation by Graph Isomorphism
Shaza Elsharief, Lilas Alrahis, Johann Knechtel, Ozgur Sinanoglu
Applications
Logic locking/obfuscation secures hardware designs from untrusted entities throughout the globalized semiconductor supply chain. Machine learning (ML) recently challenged the security of locking: such attacks successfully captured the locking-induced, structural design modifications to decipher obfuscated gates. Although routing obfuscation eliminates this threat, more recent attacks exposed new vulnerabilities, like link formation, breaking such schemes. Thus, there is still a need for...
Nonce- and Redundancy-encrypting Modes with Farfalle
Seth Hoffert
Secret-key cryptography
Nonces are a fact of life for achieving semantic security. Generating a uniformly random nonce can be costly and may not always be feasible. Using anything other than uniformly random bits can result in information leakage; e.g., a timestamp can deanonymize a communication and a counter can leak the quantity of transmitted messages. Ideally, we would like to be able to efficiently encrypt the nonce to 1) avoid needing uniformly random bits and 2) avoid information leakage. This paper...
Avoiding Lock Outs: Proactive FIDO Account Recovery using Managerless Group Signatures
Sunpreet S. Arora, Saikrishna Badrinarayanan, Srinivasan Raghuraman, Maliheh Shirvanian, Kim Wagner, Gaven Watson
Cryptographic protocols
Passwords are difficult to remember, easy to guess and prone to hacking. While there have been several attempts to solve the aforementioned problems commonly associated with passwords, one of the most successful ones to date has been by the Fast Identity Online (FIDO) alliance. FIDO introduced a series of protocols that combine local authentication on a user device with remote validation on relying party servers using public-key cryptography.
One of the fundamental problems of FIDO...
ORTOA: One Round Trip Oblivious Access
Sujaya Maiyya, Yuval Steinhart, Divyakant Agrawal, Prabhanjan Ananth, Amr El Abbadi
Applications
Many applications relying on cloud storage services typically encrypt their data to ensure data privacy. However, reading or writing the encrypted data to serve client requests reveals the type of client operation to a potentially untrusted cloud. An adversary can exploit this information leak to compromise a user’s privacy by tracking read/write access patterns. Existing approaches such as Oblivious RAM (ORAM) schemes hide the type of client access by always reading and then writing the...
FPGA Design Deobfuscation by Iterative LUT Modification at Bitstream Level
Michail Moraitis, Elena Dubrova
Implementation
Hardware obfuscation through redundancy addition is a well-known countermeasure against reverse engineering. For FPGA designs, such a technique can be implemented with a small overhead, however, its effectiveness is heavily dependent on the stealthiness of the redundant elements. Hardware opaque predicates can provide adequately stealthy constant values that can be used for obfuscation. However, in this report, we show that such obfuscation schemes can be defeated by ensuring the full...
Partial Key Exposure Attacks on BIKE, Rainbow and NTRU
Andre Esser, Alexander May, Javier Verbel, Weiqiang Wen
Attacks and cryptanalysis
In a so-called partial key exposure attack one obtains some information about the secret key, e.g. via some side-channel leakage. This information might be a certain fraction of the secret key bits (erasure model) or some erroneous version of the secret key (error model). The goal is to recover the secret key from the leaked information.
There is a common belief that, as opposed to e.g. the RSA cryptosystem, most post-quantum cryptosystems are usually resistant against partial key...
On Regenerating Codes and Proactive Secret Sharing: Relationships and Implications
Karim Eldefrawy, Nicholas Genise, Rutuja Kshirsagar, Moti Yung
Foundations
We look at two basic coding theoretic and cryptographic mechanisms developed separately and investigate relationships between them and their implications. The first mechanism is Proactive Secret Sharing (PSS), which allows randomization and repair of shares using information from other shares. PSS enables constructing secure multi-party computation protocols that can withstand mobile dynamic attacks.
This self-recovery and the redundancy of uncorrupted shares allows a system to overcome...
Impeccable Circuits III
Shahram Rasoolzadeh, Aein Rezaei Shahmirzadi, Amir Moradi
As a recent fault-injection attack, SIFA defeats most of the known countermeasures. Although error-correcting codes have been shown effective against SIFA, they mainly require a large redundancy to correct a few bits. In this work, we propose a hybrid construction with the ability to detect and correct injected faults at the same time. We provide a general implementation methodology which guarantees the correction of up to $t_c$-bit faults and the detection of at most $t_d$ faulty bits....
Resistance of Isogeny-Based Cryptographic Implementations to a Fault Attack
Élise Tasso, Luca De Feo, Nadia El Mrabet, Simon Pontié
Public-key cryptography
The threat of quantum computers has sparked the development of a new kind of cryptography to resist their attacks. Isogenies
between elliptic curves are one of the tools used for such cryptosystems. They are championed by SIKE (Supersingular isogeny key encapsulation), an "alternate candidate" of the third round of the NIST Post-Quantum Cryptography Standardization Process. While all candidates are believed to be mathematically secure, their implementations may be vulnerable to hardware...
Blind Side-Channel SIFA
Melissa Azouaoui, Kostas Papagiannopoulos, Dominik Zürner
Secret-key cryptography
Statistical Ineffective Fault Attacks (SIFA) have been recently proposed as very powerful key-recovery strategies on symmetric cryptographic primitives' implementations. Specically, they have been shown to bypass many common countermeasures against faults such as redundancy or infection, and to remain applicable even when side-channel countermeasures are deployed. In this work, we investigate combined side-channel and fault attacks and show that a profiled, SIFA-like attack can be applied...
How to Share and Own a Secret
Victor Ermolaev, Gamze Tillem
Cryptographic protocols
Custodian service is a service safeguarding a firm's or individual's financial assets or secret information. Such services often present a user with security versus ownership dilemma. The user does not wish to pass full control over their asset to the custodian to facilitate safeguarding. A control sharing mechanism allowing the custodian to hold enough information and keeping the user as the owner of the asset is required. For the assets being secret information, cryptographic protocols...
Fault Injection as an Oscilloscope: Fault Correlation Analysis
Albert Spruyt, Alyssa Milburn, Lukasz Chmielewski
Implementation
Fault Injection (FI) attacks have become a practical threat to modern cryptographic implementations. Such attacks have recently focused more on exploitation of implementation-centric and device-specific properties of the faults. In this paper, we consider the parallel between SCA attacks and FI attacks; specifically, that many FI attacks rely on the data-dependency of activation and propagation of a fault, and SCA attacks similarly rely on data-dependent power usage. In fact, these are so...
Machine Learning of Physical Unclonable Functions using Helper Data - Revealing a Pitfall in the Fuzzy Commitment Scheme
Emanuele Strieder, Christoph Frisch, Michael Pehl
Cryptographic protocols
Physical Unclonable Functions (PUFs) are used in various key-generation schemes and protocols. Such schemes are deemed to be secure even for PUFs with challenge-response behavior, as long as no responses and no reliability information about the PUF are exposed. This work, however, reveals a pitfall in these constructions: When using state-of-the-art helper data algorithms to correct noisy PUF responses, an attacker can exploit the publicly accessible helper data and challenges. We show that...
Custom Instruction Support for Modular Defense against Side-channel and Fault Attacks
Pantea Kiaei, Darius Mercadier, Pierre-Evariste Dagand, Karine Heydemann, Patrick Schaumont
Implementation
The design of software countermeasures against active and passive adversaries is a challenging problem that has been addressed by many authors in recent years. The proposed solutions adopt a theoretical foundation (such as a leakage model) but often do not offer concrete reference implementations to validate the foundation. Contributing to the experimental dimension of this body of work, we propose a customized processor called SKIVA that supports experiments with the design of...
Turbo-Aggregate: Breaking the Quadratic Aggregation Barrier in Secure Federated Learning
Jinhyun So, Basak Guler, A. Salman Avestimehr
Cryptographic protocols
Federated learning is gaining significant interests as it enables model training over a large volume of data that is distributedly stored over many users, while protecting the privacy of the individual users. However, a major bottleneck in scaling federated learning to a large number of users is the overhead of secure model aggregation across many users. In fact, the overhead of state-of-the-art protocols for secure model aggregation grows quadratically with the number of users. We propose a...
On Perfect Correctness in (Lockable) Obfuscation
Rishab Goyal, Venkata Koppula, Satyanarayana Vusirikala, Brent Waters
Public-key cryptography
In a lockable obfuscation scheme a party takes as input a program $P$, a lock value $\alpha$, a message $m$ and produces an obfuscated program $\tilde{P}$. The obfuscated program can be evaluated on an input $x$ to learn the message $m$ if $P(x)= \alpha$. The security of such schemes states that if $\alpha$ is randomly chosen (independent of $P$ and $m$), then one cannot distinguish an obfuscation of $P$ from a ``dummy'' obfuscation.
Existing constructions of lockable obfuscation achieve...
Table Redundancy Method for Protecting against Fault Attacks
Seungkwang Lee, Nam-su Jho, Myungchul Kim
Secret-key cryptography
Fault attacks (FA) intentionally inject some fault into the encryption process for analyzing a secret key based on faulty intermediate values or faulty ciphertexts. One of the easy ways for software-based countermeasures is to use time redundancy. However, existing methods can be broken by skipping comparison operations or by using non-uniform distributions of faulty intermediate values. In this paper, we propose a secure software-based redundancy, aptly named table redundancy, applying...
SKIVA: Flexible and Modular Side-channel and Fault Countermeasures
Pantea Kiaei, Darius Mercadier, Pierre-Evariste Dagand, Karine Heydemann, Patrick Schaumont
Implementation
We describe SKIVA, a customized 32-bit processor enabling the design of software countermeasures for a broad range of implementation attacks covering fault injection and side-channel analysis of timing-based and power-based leakage. We design the countermeasures as variants of bitslice programming. Our protection scheme is flexible and modular, allowing us to combine higher-order masking -- fending off side-channel analysis -- with complementary spatial and temporal redundancy -- protecting...
One Fault is All it Needs: Breaking Higher-Order Masking with Persistent Fault Analysis
Jingyu Pan, Shivam Bhasin, Fan Zhang, Kui Ren
Implementation
Persistent fault analysis (PFA) was proposed at CHES 2018 as a novel fault analysis technique. It was shown to completely defeat standard redundancy based countermeasure against fault analysis. In this work, we investigate the security of masking schemes against PFA. We show that with only one fault injection, masking countermeasures can be broken at any masking order. The study is performed on publicly available implementations of masking.
Toward RSA-OAEP without Random Oracles
Nairen Cao, Adam O'Neill, Mohammad Zaheri
Public-key cryptography
We show new partial and full instantiation results under chosen-ciphertext security for the widely implemented and standardized RSA-OAEP encryption scheme of Bellare and Rogaway (EUROCRYPT 1994) and two variants. Prior work on such instantiations either showed negative results or settled for ``passive'' security notions like IND-CPA.
More precisely, recall that RSA-OAEP adds redundancy and randomness to a message before composing two rounds of an underlying Feistel transform, whose round...
Compressive Sensing based Leakage Sampling and Reconstruction: A First Study
Changhai Ou, Chengju Zhou, Siew-Kei Lam
Implementation
An important prerequisite for Side-channel Attack (SCA) is leakage sampling where the side-channel measurements (e.g. power traces) of the cryptographic device are collected for further analysis. However, as the operating frequency of cryptographic devices continues to increase due to advancing technology, leakage sampling will impose higher requirements on the sampling equipment. This paper undertakes the first study to show that effective leakage sampling can be achieved without relying on...
Improved Quantum Multicollision-Finding Algorithm
Akinori Hosoyamada, Yu Sasaki, Seiichiro Tani, Keita Xagawa
Foundations
The current paper improves the number of queries of the previous quantum multi-collision finding algorithms presented by Hosoyamada et al. at Asiacrypt 2017. Let an $l$-collision be a tuple of $l$ distinct inputs that result in the same output of a target function. In cryptology, it is important to study how many queries are required to find $l$-collisions for random functions of which domains are larger than ranges. The previous algorithm finds an $l$-collision for a random function by...
Error-Detecting in Monotone Span Programs with Application to Communication Efficient Multi-Party Computation
Nigel P. Smart, Tim Wood
Cryptographic protocols
Recent improvements in the state-of-the-art of MPC for non-full-threshold access structures introduced the idea of using a collision-resistant hash functions and redundancy in the secret-sharing scheme to construct a communication-efficient MPC protocol which is computationally-secure against malicious adversaries, with abort. The prior work is based on replicated secret-sharing; in this work we extend this methodology to {\em any} multiplicative LSSS implementing a $Q_2$ access structure. ...
Statistical Ineffective Fault Attacks on Masked AES with Fault Countermeasures
Christoph Dobraunig, Maria Eichlseder, Hannes Gross, Stefan Mangard, Florian Mendel, Robert Primas
Secret-key cryptography
Implementation attacks like side-channel and fault attacks are a threat to deployed devices especially if an attacker has physical access. As a consequence, devices like smart cards and IoT devices usually provide countermeasures against implementation attacks, such as masking against side-channel attacks and detection-based countermeasures like temporal or spacial redundancy against fault attacks. In this paper, we show how to attack implementations protected with both masking and...
SIFA: Exploiting Ineffective Fault Inductions on Symmetric Cryptography
Christoph Dobraunig, Maria Eichlseder, Thomas Korak, Stefan Mangard, Florian Mendel, Robert Primas
Since the seminal work of Boneh et al., the threat of fault attacks has been widely known and techniques for fault attacks and countermeasures have been studied extensively. The vast majority of the literature on fault attacks focuses on the ability of fault attacks to change an intermediate value to a faulty one, such as differential fault analysis (DFA), collision fault analysis, statistical fault attack (SFA), fault sensitivity analysis, or differential fault intensity analysis (DFIA)....
CAMFAS: A Compiler Approach to Mitigate Fault Attacks via Enhanced SIMDization
Zhi Chen, Junjie Shen, Alex Nicolau, Alex Veidenbaum, Nahid Farhady Ghalaty, Rosario Cammarota
Public-key cryptography
The trend of supporting wide vector units in general purpose microprocessors suggests opportunities for developing a new and elegant compilation approach to mitigate the impact of faults to cryptographic implementations, which we present in this work.
We propose a compilation flow, CAMFAS, to automatically and selectively introduce vectorization in a cryptographic library
- to translate a vanilla library into a library with vectorized code that is resistant to glitches. Unlike in traditional...
Efficient and Universally Composable Protocols for Oblivious Transfer from the CDH Assumption
Eduard Hauck, Julian Loss
Oblivious Transfer (OT) is a simple, yet fundamental primitive which suffices to achieve almost every cryptographic application. In a recent work (Latincrypt `15), Chou and Orlandi (CO) present the most efficient, fully UC-secure OT protocol to date and argue its security under the CDH assumption. Unfortunately, a subsequent work by Genc et al. (Eprint `17) exposes a flaw in their proof which renders the CO protocol insecure. In this work, we make the following contributions: We first point...
Thwarting Fault Attacks using the Internal Redundancy Countermeasure (IRC)
Benjamin Lac, Anne Canteaut, Jacques J. A. Fournier, Renaud Sirdey
Cryptographic protocols
A growing number of connected objects, with their high performance and low-resources constraints, are embedding lightweight ciphers for protecting the confidentiality of the data they manipulate or store. Since those objects are easily accessible, they are prone to a whole range of physical attacks, one of which are fault attacks against for which countermeasures are usually expensive to implement, especially on off-the-shelf devices. For such devices, we propose a new generic software...
Lightweight Fault Attack Resistance in Software Using Intra-Instruction Redundancy
Conor Patrick, Bilgiday Yuce, Nahid Farhady Ghalaty, Patrick Schaumont
Implementation
Fault attack countermeasures can be implemented by storing or computing sensitive data in redundant form, such that the faulty data can be detected and restored. We present a class of lightweight, portable software countermeasures for block ciphers. Our technique is based on redundant bit-slicing, and it is able to detect faults in the execution of a single instruction. In comparison to earlier techniques, we are able to intercept data faults as well as instruction sequence faults using a...
ParTI -- Towards Combined Hardware Countermeasures against Side-Channel and Fault-Injection Attacks
Tobias Schneider, Amir Moradi, Tim Güneysu
Implementation
Side-channel analysis and fault-injection attacks are known as major threats to any cryptographic implementation.
Hardening cryptographic implementations with appropriate countermeasures is thus essential before they are deployed in the wild.
However, countermeasures for both threats are of completely different nature: Side-channel analysis is mitigated by techniques that hide or mask key-dependent information while resistance against fault-injection attacks can be achieved by redundancy in...
Optimized quantization in Zero Leakage Helper Data Systems
Taras Stanko, Fitria Nur Andini, Boris Skoric
Helper Data Systems are a cryptographic primitive that allows for the reproducible extraction of secrets from noisy measurements. Redundancy data called Helper Data makes it possible to do error correction while leaking little or nothing ("Zero Leakage") about the extracted secret string.
We study the case of non-discrete measurement outcomes. In this case a quantization step is required. Recently de Groot et al described a generic method to perform the quantization in a Zero Leakage manner....
Pseudorandom Functions in Almost Constant Depth from Low-Noise LPN
Yu Yu, John Steinberger
Secret-key cryptography
Pseudorandom functions (PRFs) play a central role in symmetric cryptography. While in principle they can be built from any one-way functions by going through the generic HILL (SICOMP 1999) and GGM (JACM 1986) transforms, some of these steps are inherently sequential and far from practical. Naor, Reingold (FOCS 1997) and Rosen (SICOMP 2002) gave parallelizable constructions of PRFs in NC\(^2\) and TC\(^0\) based on concrete number-theoretic assumptions such as DDH, RSA, and factoring....
Automated key setup and recovery from key exposure for power networks
Amir Herzberg, Yehonatan Kfir
Power networks are built with inherent redundancy, including in the communication channels.
In this work, we show that this redundancy can increase the cyber security resiliency to key exposure.
Specifically, we present CrypTop, a novel protocol for the {\em key setup and refresh} problem in power networks.
CrypTop uses multipath communication and already-keyed devices, to setup keys in other devices, and to recover from key exposures.
We evaluate CrypTop in realistic power network...
Lightweight CRC-based Authentication
Elena Dubrova, Mats Näslund, Göran Selander, Fredrik Lindqvist
Secret-key cryptography
Low-cost resource-constrained devices can allocate very limited resources for implementing security. At the same time, they still require some level of protection. In this paper, we present a lightweight message authentication scheme based on Cyclic Redundancy Check (CRC). The presented CRC inherits the implementation simplicity of the conventional CRC checksum except that the LFSR implementing its encoding and decoding is made re-programmable. Similarly to previously proposed cryptographic...
Robust Authenticated Encryption and the Limits of Symmetric Cryptography
Christian Badertscher, Christian Matt, Ueli Maurer, Phillip Rogaway, Björn Tackmann
Secret-key cryptography
Robust authenticated encryption (RAE) is a primitive for symmetric encryption that allows to flexibly specify the ciphertext expansion, i.e., how much longer the ciphertext is compared to the plaintext. For every ciphertext expansion, RAE aims at providing the best-possible authenticity and confidentiality. To investigate whether this is actually achieved, we characterize exactly the guarantees symmetric cryptography can provide for any given ciphertext expansion. Our characterization...
Fault Space Transformation: A Generic Approach to Counter Differential Fault Analysis and Differential Fault Intensity Analysis on AES-like Block Ciphers
Sikhar Patranabis, Abhishek Chakraborty, Debdeep Mukhopadhyay, P. P. Chakrabarti
Classical fault attacks such as Differential Fault Analysis~(DFA) as well as biased fault attacks such as the Differential Fault Intensity Analysis~(DFIA) have been a major threat to cryptosystems in recent times. DFA uses pairs of fault-free and faulty ciphertexts to recover the secret key. DFIA, on the other hand, combines principles of side channel analysis and fault attacks to try and extract the key using faulty ciphertexts only. Till date, no effective countermeasure that can thwart...
Ciphertext-only attack on d*d Hill in O(d13^d)
Shahram Khazaei, Siavash Ahmadi
Secret-key cryptography
Hill is a classical cipher which is generally believed to be resistant against ciphertext-only attack. In this paper, by using a divide-and-conquer technique, it is first shown that Hill with d*d key matrix over Z_26 can be broken with computational complexity of O(d26^d), for the English language. This is much less than the only publicly known attack, i.e., the brute-force with complexity of O(d^3(26)^(d^2)). Then by using the Chinese Remainder Theorem, it is shown that the computational...
Cryptographically Secure CRC for Lightweight Message Authentication
Elena Dubrova, Mats Näslund, Göran Selander, Fredrik Lindqvist
Foundations
A simple and practical hashing scheme based on Cyclic Redundancy Check (CRC) is presented. Similarly to previously proposed cryptographically secure CRCs, the presented one detects both, random and malicious, errors without increasing bandwidth. However, we use a product of irreducible polynomials instead of a single irreducible polynomial for generating the CRC. This is an advantage since smaller irreducible polynomials are easier to compute. The price we pay is that the probability that...
Reversed Genetic Algorithms for Generation of Bijective S-boxes with Good Cryptographic Properties
Georgi Ivanov, Nikolay Nikolov, Svetla Nikova
Secret-key cryptography
Often S-boxes are the only nonlinear component in a block cipher and as such play an important role in ensuring its resistance to cryptanalysis. Cryptographic properties and constructions of S-boxes have been studied for many years. The most common techniques for constructing S-boxes are: algebraic constructions, pseudo-random generation and a variety of heuristic approaches. Among the latter are the genetic algorithms. In this paper, a genetic algorithm working in a reversed way is...
Protecting Encrypted Cookies from Compression Side-Channel Attacks
Janaka Alawatugoda, Douglas Stebila, Colin Boyd
Cryptographic protocols
Compression is desirable for network applications as it saves bandwidth; however, when data is compressed before being encrypted, the amount of compression leaks information about the amount of redundancy in the plaintext. This side channel has led to successful CRIME and BREACH attacks on web traffic protected by the Transport Layer Security (TLS) protocol. The general guidance in light of these attacks has been to disable compression, preserving confidentiality but sacrificing bandwidth....
Optimal Contracts for Outsourced Computation
Viet Pham, MHR. Khouzani, Carlos Cid
Applications
While expensive cryptographically verifiable computation aims at defeating malicious agents, many civil purposes of outsourced computation tolerate a weaker notion of security, i.e., ``lazy-but-honest'' contractors. Targeting this type of agents, we develop optimal contracts for outsourcing of computational tasks via appropriate use of rewards, punishments, auditing rate, and ``redundancy''. Our contracts provably minimize the expense of the outsourcer (principal) while guaranteeing correct...
Impossible differential cryptanalysis of LBlock with concrete investigation of key scheduling algorithm
Jiageng Chen, Yuichi Futa, Atsuko Miyaji, Chunhua Su
Secret-key cryptography
Impossible differential cryptanalysis has been proved to be one of the most powerful techniques to attack block ciphers. Based on the impossible differential paths, we can usually add several rounds before or after to launch the key recovery attack. Impossible differential cryptanalysis is powerful not only because the number of rounds it can break is very competitive compared to other attacks, but also unlike differential attacks which are statistical attacks in the essential, impossible...
Enhancing Oblivious RAM Performance Using Dynamic Prefetching
Xiangyao Yu, Ling Ren, Christopher Fletcher, Albert Kwon, Marten van Dijk, Srinivas Devadas
Cryptographic protocols
Oblivious RAM (ORAM) is an established technique to hide the access pattern to an untrusted storage system.
With ORAM, a curious adversary cannot tell what data address the user is accessing when observing the bits moving between the user and the storage system.
All existing ORAM schemes achieve obliviousness by adding redundancy to the storage system, i.e., each access is turned into multiple random accesses.
Such redundancy incurs a large performance overhead.
Though traditional data...
A Full Characterization of Completeness for Two-party Randomized Function Evaluation
Daniel Kraschewski, Hemanta K. Maji, Manoj Prabhakaran, Amit Sahai
Foundations
We settle a long standing open problem which has pursued a full characterization of completeness of (potentially randomized) finite functions for 2-party computation that is secure against active adversaries. Since the first such complete function was discovered [Kilian, FOCS 1988], the question of which finite 2-party functions are complete has been studied extensively, leading to characterization in many special cases. In this work, we completely settle this problem.
We provide a...
Distributed Key Generation for Secure Encrypted Deduplication
Yitao Duan
Cryptographic protocols
Large-scale storage systems often attempt to achieve two seemingly conflicting goals: (1) the systems need to reduce the copies of redundant data to save space, a process called deduplication; and (2) users demand encryption of their data to ensure privacy. Conventional encryption makes deduplication on ciphertexts ineffective, as it destroys data redundancy. A line of work, originated from Convergent
Encryption [28], and evolved into Message Locked Encryption [12], strives to solve this...
Formal verification of a software countermeasure against instruction skip attacks
Nicolas Moro, Karine Heydemann, Emmanuelle Encrenaz, Bruno Robisson
Fault attacks against embedded circuits enabled to define many new attack paths against secure circuits. Every attack path relies on a specific fault model which defines the type of faults that the attacker can perform. On embedded processors, a fault model consisting in an assembly instruction skip can be very useful for an attacker and has been obtained by using several fault injection means. To avoid this threat, some countermeasure schemes which rely on temporal redundancy have been...
Detection of Algebraic Manipulation in the Presence of Leakage
Hadi Ahmadi, Reihaneh Safavi-Naini
Foundations
We investigate the problem of algebraic manipulation detection (AMD) over a communication channel that partially leaks information to an adversary. We assume the adversary is computationally unbounded and there is no shared key or correlated randomness between the sender and the receiver. We introduce leakage-resilient (LR)-AMD codes to detect algebraic manipulation in this model.
We consider two leakage models. The first model, called \emph{linear leakage}, requires the adversary's...
Smashing MASH-1
Vladimir Antipkin
MASH-1 is modular arithmetic based hash function. It is presented in Part 4 of ISO/IEC 10118
standard for one and a half decade. Cryptographic strength of MASH-1 hash function is based on
factorization problem of an RSA modulus along with redundancy in the input blocks of compression
functions. Despite of this, we are able to introduce two large classes of moduli which allow
practical time collision finding algorithm for MASH-1. In one case even multicollisions of
arbitrary length can be constructed.
For an EPC-C1 G2 RFID compliant Protocol, CRC with Concatenation : No; PRNG with Concatenation : Yes
Masoumeh Safkhani, Nasour Bagheri
Cryptographic protocols
In this paper we present new constraints to EPCglobal Class 1 Generation 2 (EPC-C1 G2) standard which if they have been considered in the design of EPC-C1 G2 complaint authentication protocols, lead to prevent predecessor's protocols' weaknesses and also present the secure ones. Also in this paper as an example, we use Pang \textit{et al.} EPC-C1 G2-friendly protocol which has been recently proposed, to show our proposed constraints in EPC-C1 G2 standard. Pang \textit{et al.}'s protocol...
Verified Security of Redundancy-Free Encryption from Rabin and RSA
Gilles Barthe, David Pointcheval, Santiago Zanella-Béguelin
Public-key cryptography
Verified security provides a firm foundation for cryptographic proofs
by means of rigorous programming language techniques and verification
methods. EasyCrypt is a framework that realizes the verified security
paradigm and supports the machine-checked construction and
verification of cryptographic proofs using state-of-the-art SMT
solvers, automated theorem provers and interactive proof assistants.
Previous experiments have shown that EasyCrypt is effective for a
posteriori validation of...
The n-Diffie-Hellman Problem and its Applications
Liqun Chen, Yu Chen
Public-key cryptography
The main contributions of this paper are twofold. On the one hand, the twin Diffie-Hellman (twin DH) problem proposed by Cash, Kiltz and Shoup is extended to the $n$-Diffie-Hellman ($n$-DH) problem for an arbitrary integer $n$, and this new problem is shown to be at least as hard as the ordinary DH problem. Like the twin DH problem, the $n$-DH problem remains hard even in the presence of a decision oracle that recognizes solution to the problem. On the other hand, observe that the...
Efficient Methods for Exploiting Faults Induced at AES Middle Rounds
Chong Hee Kim
Secret-key cryptography
Faults occurred during the operations in a hardware device cause many problems such as performance deterioration, unreliable output, etc. If a fault occurs in a cryptographic hardware device, the effect can be even serious because an adversary may exploit it to find the secret information stored in the device. More precisely, the adversary can find the key of a block cipher using differential information between correct and faulty ciphertexts obtained by inducing faults during the...
Outline of a proposal responding to E.U. and U.S. calls for trustworthy global-scale IdM and CKM designs
Benjamin Gittins
Secret-key cryptography
In 2007, the E.U. FP6 SecurIST called for trustworthy international identity management (IdM) that was user-centric. In 2009, the U.S. Department of Homeland Security (DHS) called for trustworthy global-scale IdM and the U.S. National Institute of Standards and Technology (NIST) called for new cryptographic key management (CKM) designs. In this paper we outline the core architecture for (apparently) the first globally scalable, post quantum secure, symmetric key based platform for...
Applications of SAT Solvers to AES key Recovery from Decayed Key Schedule Images
Abdel Alim Kamal, Amr M. Youssef
Cold boot attack is a side channel attack which exploits the data remanence property of random access memory (RAM) to retrieve its contents which remain readable shortly after its power has been removed. Given the nature of the cold boot attack, only a corrupted image of the memory contents will be available to the attacker. In this paper, we investigate the use of an off-the-shelf SAT solver, CryptoMinSat, to improve the key recovery of the AES-128 key schedules from its corresponding...
On Key Authentic Degree of Cryptosystem
WANG Yong, WANG Huangdeng
Against such attacks as rubber-hose attack, key authentic degree of cryptosystem is expatiated in detail, and the important significance of key authentic degree of cryptosystem is pointed out. And the key authentic degrees of modern cryptosystem under different conditions are given. Research shows that under most realistic situations, the key authentic degree of modern cryptosystem is high, this means that modern cryptosystem is threatened by such as rubber-hose attack and so on. Feasibility...
Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures
Jean-Sebastien Coron, David Naccache, Mehdi Tibouchi, Ralf-Philipp Weinmann
Public-key cryptography
In 1999, Coron, Naccache and Stern discovered an existential signature forgery for two popular RSA signature standards, ISO/IEC 9796-1 and 2. Following this attack ISO/IEC 9796-1 was withdrawn. ISO/IEC 9796-2 was amended by increasing the message digest to at least 160 bits. Attacking this amended version required at least 2^61 operations.
In this paper, we exhibit algorithmic refinements allowing to attack the amended (currently valid) version of ISO/IEC 9796-2 for all modulus sizes. A...
Secure Certificateless Public Key Encryption without Redundancy
Yinxia Sun, Futai Zhang
Public-key cryptography
Certificateless public key cryptography was introduced to solve the
key escrow problem in identity based cryptography while enjoying the
most attractive {\em certificateless} property. In this paper, we
present the first {\em secure} certificateless public key encryption
(CLPKE) scheme {\em without redundancy}. Our construction provides
optimal bandwidth and a quite efficient decryption process among all
the existing CLPKE schemes. It is provably secure against adaptive
chosen ciphertext...
Double-Base Number System for Multi-Scalar Multiplications
Christophe Doche, David R. Kohel, Francesco Sica
Applications
The Joint Sparse Form is currently the standard representation system to perform multi-scalar multiplications of the form $[n]P m[Q]$. We introduce the concept of Joint Double-Base Chain, a generalization of the Double-Base Number System to represent simultaneously $n$ and $m$. This concept is relevant because of the high redundancy of Double-Base systems, which ensures that we can
find a chain of reasonable length that uses exactly the same terms to compute both $n$ and $m$. Furthermore,...
2007/481
Last updated: 2008-05-06
MAC-free variant of KD04
Xianhui Lu, Xuejia Lai, Dake He
Kurosawa and Desmedt proposed an efficient hybrid encryption scheme(KD04) which is secure
against adaptive chosen ciphertext attacks(IND-CCA) although the underlying KEM(key
encapsulation mechanism) is not IND-CCA secure\cite{Kurosawa2004}. We show a variant of
KD04 which is IND-CCA secure when the the underlying DEM part is IND-CCA secure. We need
a DEM built from one-time symmetric encryption scheme and a MAC in the security reduction
to check if the KEM part of a ciphertext is valid....
Improvement on a Digital Signature Scheme without using One-way Hash and Message Redundancy
Jie Liu, Jianhua Li
Cryptographic protocols
Digital signature schemes based on public-key cryptosystems generally permit existential forgery, except the schemes are equipped with some message formatting mechanisms, such as using hash functions or padding redundancies. In 2004, Chang et al. proposed a new digital signature scheme, and claimed the scheme without using any hash function or padding any redundancy can resist forgery attacks. However, many attacks on Chang et al.'s scheme were presented. Kang et al. also gave an effective...
2007/072
Last updated: 2007-06-05
A Hybrid Approach to Concurrent Error Detection for a Compact ASIC Implementation of the Advanced Encryption Standard
Namin Yu, Howard M. Heys
Implementation
In this paper, we investigate the application of concurrent error detection circuitry to a compact application-specific integrated circuit (ASIC) implementation of the Advanced Encryption Standard (AES). The specific objective of the design is to develop a method suitable for compact ASIC implementations targeted to embedded systems such that the system is resistant to fault attacks. To provide the error detection, recognizing that previously proposed schemes are not well suited to compact...
Redundancy of the Wang-Yu Sufficient Conditions
Yuto Nakano, Hidenori Kuwakado, Masakatu Morii
Wang and Yu showed that MD5 was not collision-resistant, but it is known that their sufficient conditions for finding a collision of MD5 includes some mistakes. In this paper, we examine the sufficient conditions by computer simulation. We show that the Wang-Yu conditions include 16 unnecessary conditions for making a collision. Sasaki et al. claimed that modifying one condition made it possible to remove eleven conditions. However, the result of our computer simulation shows that their...
Decoding Interleaved Gabidulin Codes and Ciphertext-Security for GPT variants
R. Overbeck
Public-key cryptography
In this paper we view interleaved Gabidulin codes and describe how to correct errors up to a rank equal to the amount of redundancy of the code with high probability. We give a detailed proof for our estimation of the probability of correct decoding.
In a second part, we view the application to variants of the GPT cryptosystem. For GGPT this leads to an efficient attack on the remaining secure instances, whereas it allows to derive at least partial information of the plaintext in the case of RRC-GPT.
Chosen-Ciphertext Secure Identity-Based Encryption in the Standard Model with short Ciphertexts
Eike Kiltz
Public-key cryptography
We describe a practical identity-based encryption scheme that is secure in the standard model against chosen-ciphertext (CCA2) attacks. Security is based on an assumption comparable to (but slightly stronger than) Bilinear Decisonal Diffie-Hellman (BDDH).
A comparison shows that our construction outperforms all known identity-based encryption schemes in the standard model and its performance is even comparable with the one from the random-oracle based Boneh/Franklin IBE scheme.
Our proposed...
Multivariate Quadratic Polynomials in Public Key Cryptography
Christopher Wolf
Public-key cryptography
This thesis gives an overview of Multivariate Quadratic polynomial equations and their use in public key cryptography.
In the first chapter, some general terms of cryptography are introduced.
In particular, the need for public key cryptography and alternative
schemes is motivated, i.e., systems which neither use factoring (like RSA, Rivest-Shamir-Adleman)
nor the discrete logarithm (like ECC, elliptic curve cryptography).
This is followed by a brief introduction of finite fields and a...
The topology of covert conflict
Shishir Nagaraja, Ross Anderson
Applications
Often an attacker tries to disconnect a network by destroying nodes or edges, while the defender counters using various resilience mechanisms. Examples include a music industry body attempting to close down a peer-to-peer file-sharing network; medics attempting to halt the spread of an infectious disease by selective vaccination; and a police agency trying to decapitate a terrorist organisation. Albert, Jeong and Barabasi famously analysed the static case, and showed that vertex-order...
The Mundja Streaming MAC
Philip Hawkes, Michael Paddon, Gregory G. Rose
Secret-key cryptography
Mundja is a MAC generation algorithm that has been designed for use
together with a stream cipher. Mundja accumulates the message onto
two independent registers: the first is a Cyclic Redundancy Checksum (CRC) that uses linear feedback; the second is a strengthened version of the SHA-256 register that uses nonlinear feedback. Mundja is fast (asymptotically about 4 times the speed of HMAC-SHA-256), and can generate MACs of any desired length. Mundja is designed to be secure at the equivalent...
Forgery Attacks on Chang et al.'s signature scheme with message recovery
FU Xiaotong, XU Chunxiang, XIAO Guozhen
Cryptographic protocols
It is found that Chang et al.'s signature scheme with message recovery is not as secure as they claimed, in fact. In this letter, two forgery attacks is proposed to show that the signature can be forged on any uncontrolled messages. To overcome these attacks, the one-way hash functions and the message redundancy schemes may be still used.
Cryptanalysis of Chang et al.'s Signature Scheme with Message Recovery
Fangguo Zhang
Public-key cryptography
Recently, Chang \textit{et al}. \cite{Chang} proposed a new
digital signature scheme with message recovery and claimed that
neither one-way hash functions nor message redundancy schemes were
employed in their scheme. However, in this letter, two forgery
attacks are proposed to show that Chang \textit{et al.}'s
signature scheme is not secure. To resist these attacks, the
message redundancy schemes may be still used.
Commitment Capacity of Discrete Memoryless Channels
Andreas Winter, Anderson C. A. Nascimento, Hideki Imai
Foundations
In extension of the bit commitment task and following work initiated by Crepeau and Kilian, we introduce and solve the problem of characterising the optimal rate at which a discrete memoryless channel can be used for bit commitment. It turns out that the answer is very intuitive: it is the maximum equivocation of the channel (after removing trivial redundancy), even when unlimited noiseless bidirectional side communication is allowed.
By a well-known reduction, this result provides a lower...
On Linear Redundancy in the AES S-Box
Joanne Fuller, William Millan
We show the existence of a previously unknown linear redundancy
property of the only nonlinear component of the AES block cipher.
It is demonstrated that the outputs of the 8*8 Rijndael s-box
(based on inversion in a finite field) are all equivalent under
affine transformation. The method used to discover these affine
relations is novel and exploits a new fundamental result on the
invariance properties of local connection structure of affine
equivalence classes. As well as increasing...
Side-channel-analysis (SCA) resistance with cost optimization in AES hardware implementations remains a significant challenge. While traditional masking-based schemes offer provable security, they often incur substantial resource overheads (latency, area, randomness, performance, power consumption). Alternatively, the RAMBAM scheme introduced a redundancy-based approach to control the signal-to-noise ratio, and achieves exponential leakage reduction as redundancy increases. This method...
Blockchain technology ensures accountability, transparency, and redundancy in critical applications, includ- ing IoT with embedded systems. However, the reliance on public-key cryptography (PKC) makes blockchain vulnerable to quantum computing threats. This paper addresses the urgent need for quantum-safe blockchain solutions by integrating Post- Quantum Cryptography (PQC) into blockchain frameworks. Utilizing algorithms from the NIST PQC standardization pro- cess, we aim to fortify...
Users increasingly store their data in the cloud, thereby benefiting from easy access, sharing, and redundancy. To additionally guarantee security of the outsourced data even against a server compromise, some service providers have started to offer end-to-end encrypted (E2EE) cloud storage. With this cryptographic protection, only legitimate owners can read or modify the data. However, recent attacks on the largest E2EE providers have highlighted the lack of solid foundations for this...
Masking is a widely adopted countermeasure against side-channel analysis (SCA) that protects cryptographic implementations from information leakage. However, current masking schemes often incur significant overhead in terms of electronic cost. RAMBAM, a recently proposed masking technique that fits elegantly with the AES algorithm, offers ultra-low latency/area by utilizing redundant representations of finite field elements. This paper presents a comprehensive generalization of RAMBAM and...
The TFHE cryptosystem only supports small plaintext space, up to 5 bits with usual parameters. However, one solution to circumvent this limitation is to decompose input messages into a basis B over multiple ciphertexts. In this work, we introduce B-gates, an extension of logic gates to non binary bases, to compute base B logic circuit. The flexibility introduced by our approach improves the speed performance over previous approaches such as the so called tree-based method which requires an...
In the implementation of isogeny-based schemes, V\'{e}lu's formulas are essential for constructing and evaluating odd degree isogenies. Bernstein et al. proposed an approach known as $\surd$elu, which computes an $\ell$-isogeny at a cost of $\tilde{\mathcal{O}}(\sqrt{\ell})$ finite field operations. This paper presents two key improvements to enhance the efficiency of the implementation of $\surd$\'{e}lu from two aspects: optimizing the partition involved in $\surd$\'{e}lu and speeding...
In this work, we present two generic frameworks for leakage-resilient attribute-based encryption (ABE), which is an improved version of ABE that can be proven secure even when part of the secret key is leaked. Our frameworks rely on the standard assumption ($k$-Lin) over prime-order groups. The first framework is designed for leakage-resilient ABE with attribute-hiding in the bounded leakage model. Prior to this work, no one had yet derived a generic leakage-resilient ABE framework with...
Physical security is an important aspect of devices for which an adversary can manipulate the physical execution environment. Recently, more and more attention has been directed towards a security model that combines the capabilities of passive and active physical attacks, i.e., an adversary that performs fault-injection and side-channel analysis at the same time. Implementing countermeasures against such a powerful adversary is not only costly but also requires the skillful combination of...
Fault injection attacks are a serious threat to system security, enabling attackers to bypass protection mechanisms or access sensitive information. To evaluate the robustness of CPU-based systems against these attacks, it is essential to analyze the consequences of the fault propagation resulting from the complex interplay between the software and the processor. However, current formal methodologies combining hardware and software face scalability issues due to the monolithic approach...
DCT is a beyond-birthday-bound~(BBB) deterministic authenticated encryption~(DAE) mode proposed by Forler et al. in ACISP 2016, ensuring integrity by redundancy. The instantiation of DCT employs the BRW polynomial, which is more efficient than the usual polynomial in GCM by reducing half of the multiplication operations. However, we show that DCT suffers from a small stretch problem similar to GCM. When the stretch length $\tau$ is small, choosing a special $m$-block message, we can reduce...
We propose a new method to encode the problems of optimizing S-box implementations into SAT problems. By considering the inputs and outputs of gates as Boolean functions, the fundamental idea of our method is representing the relationships between these inputs and outputs according to their algebraic normal forms. Based on this method, we present several encoding schemes for optimizing S-box implementations according to various criteria, such as multiplicative complexity, bitslice gate...
The McEliece cryptosystem is a strong contender for post-quantum schemes, including key encapsulation for confidentiality of key exchanges in network protocols. A McEliece secret key is a structured parity check matrix that is transformed via Gaussian elimination into an unstructured public key. We show that this transformation is a highly critical operation with respect to side-channel leakage. We assume leakage of the elementary row operations during Gaussian elimination, motivated by...
Exclusive OR (XOR), a common Boolean logical operation, is an operation on two factors where the result is true if and only if one operand is true and the other is false. A simple way to state this is ``one or the other, but not both''. Using this logical operation, a text string can be encrypted by applying the XOR operator to every character using a ``key''. If you want to decrypt the output, simply reapply the key and the resulting output will be the original message.
Thangavel and Varalakshmi proposed an enhanced DNA and ElGamal cryptosystem for secure data storage and retrieval in cloud. They modified ElGamal algorithm which it calls enhanced ElGamal cryptosystem. We prove that their enhanced ElGamal scheme, which does not require two random numbers by data owner. Although the attacker is unable to find out what message the data owner gave to the data user. However, the attackers can still confuse the issue of sending messages to data users. On the...
The Polynomial Modular Number System (PMNS) is a non-positional number system for modular arithmetic. A PMNS is defined by a tuple $(p, n, \gamma, \rho, E)$, where $p$, $n$, $\gamma$ and $\rho$ are positive non-zero integers and $E\in\mathbb{Z}_{n}[X]$ is a monic polynomial such that $E(\gamma) \equiv 0 \pmod p$. The PMNS is a redundant number system. This redundancy property has already been used to randomise the data during the Elliptic Curve Scalar Multiplication (ECSM). In this paper,...
Low energy is an important aspect of hardware implementation. For energy-limited battery-powered devices, low energy stream ciphers can play an important role. In \texttt{IACR ToSC 2021}, Caforio et al. proposed the Perfect Tree energy model for stream cipher that links the structure of combinational logic circuits with state update functions to energy consumption. In addition, a metric given by the model shows a negative correlation with energy consumption, i.e., the higher the balance of...
End-to-end authenticity in public networks plays a significant role. Namely, without authenticity, the adversary might be able to retrieve even confidential information straight away by impersonating others. Proposed solutions to establish an authenticated channel cover pre-shared key-based, password-based, and certificate-based techniques. To add confidentiality to an authenticated channel, authenticated key exchange (AKE) protocols usually have one of the three solutions built in. As an...
In this paper, we present a new diverse class of post-quantum group-based Digital Signature Schemes (DSS). The approach is significantly different from previous examples of group-based digital signatures and adopts the framework of group action-based cryptography: we show that each finite group defines a group action relative to the semidirect product of the group by its automorphism group, and give security bounds on the resulting signature scheme in terms of the group-theoretic...
The growing popularity of cloud storage has brought attention to critical need for preventing information leakage from cloud access patterns. To this end, recent efforts have extended Oblivious RAM (ORAM) to the cloud environment in the form of Oblivious Store. However, its impracticality due to the use of probability encryption with fake accesses to obfuscate the access pattern, as well as the security requirements of conventional obliviousness designs, which hinder cloud interests in...
SPHINCS is a hash-based digital signature scheme that was selected by NIST in their post-quantum cryptography standardization process. The establishment of a universal forgery on the seminal scheme SPHINCS was shown to be feasible in practice by injecting a fault when the signing device constructs any non-top subtree. Ever since the attack has been made public, little effort was spent to protect the SPHINCS family against attacks by faults. This paper works in this direction in the context...
Logic locking/obfuscation secures hardware designs from untrusted entities throughout the globalized semiconductor supply chain. Machine learning (ML) recently challenged the security of locking: such attacks successfully captured the locking-induced, structural design modifications to decipher obfuscated gates. Although routing obfuscation eliminates this threat, more recent attacks exposed new vulnerabilities, like link formation, breaking such schemes. Thus, there is still a need for...
Nonces are a fact of life for achieving semantic security. Generating a uniformly random nonce can be costly and may not always be feasible. Using anything other than uniformly random bits can result in information leakage; e.g., a timestamp can deanonymize a communication and a counter can leak the quantity of transmitted messages. Ideally, we would like to be able to efficiently encrypt the nonce to 1) avoid needing uniformly random bits and 2) avoid information leakage. This paper...
Passwords are difficult to remember, easy to guess and prone to hacking. While there have been several attempts to solve the aforementioned problems commonly associated with passwords, one of the most successful ones to date has been by the Fast Identity Online (FIDO) alliance. FIDO introduced a series of protocols that combine local authentication on a user device with remote validation on relying party servers using public-key cryptography. One of the fundamental problems of FIDO...
Many applications relying on cloud storage services typically encrypt their data to ensure data privacy. However, reading or writing the encrypted data to serve client requests reveals the type of client operation to a potentially untrusted cloud. An adversary can exploit this information leak to compromise a user’s privacy by tracking read/write access patterns. Existing approaches such as Oblivious RAM (ORAM) schemes hide the type of client access by always reading and then writing the...
Hardware obfuscation through redundancy addition is a well-known countermeasure against reverse engineering. For FPGA designs, such a technique can be implemented with a small overhead, however, its effectiveness is heavily dependent on the stealthiness of the redundant elements. Hardware opaque predicates can provide adequately stealthy constant values that can be used for obfuscation. However, in this report, we show that such obfuscation schemes can be defeated by ensuring the full...
In a so-called partial key exposure attack one obtains some information about the secret key, e.g. via some side-channel leakage. This information might be a certain fraction of the secret key bits (erasure model) or some erroneous version of the secret key (error model). The goal is to recover the secret key from the leaked information. There is a common belief that, as opposed to e.g. the RSA cryptosystem, most post-quantum cryptosystems are usually resistant against partial key...
We look at two basic coding theoretic and cryptographic mechanisms developed separately and investigate relationships between them and their implications. The first mechanism is Proactive Secret Sharing (PSS), which allows randomization and repair of shares using information from other shares. PSS enables constructing secure multi-party computation protocols that can withstand mobile dynamic attacks. This self-recovery and the redundancy of uncorrupted shares allows a system to overcome...
As a recent fault-injection attack, SIFA defeats most of the known countermeasures. Although error-correcting codes have been shown effective against SIFA, they mainly require a large redundancy to correct a few bits. In this work, we propose a hybrid construction with the ability to detect and correct injected faults at the same time. We provide a general implementation methodology which guarantees the correction of up to $t_c$-bit faults and the detection of at most $t_d$ faulty bits....
The threat of quantum computers has sparked the development of a new kind of cryptography to resist their attacks. Isogenies between elliptic curves are one of the tools used for such cryptosystems. They are championed by SIKE (Supersingular isogeny key encapsulation), an "alternate candidate" of the third round of the NIST Post-Quantum Cryptography Standardization Process. While all candidates are believed to be mathematically secure, their implementations may be vulnerable to hardware...
Statistical Ineffective Fault Attacks (SIFA) have been recently proposed as very powerful key-recovery strategies on symmetric cryptographic primitives' implementations. Specically, they have been shown to bypass many common countermeasures against faults such as redundancy or infection, and to remain applicable even when side-channel countermeasures are deployed. In this work, we investigate combined side-channel and fault attacks and show that a profiled, SIFA-like attack can be applied...
Custodian service is a service safeguarding a firm's or individual's financial assets or secret information. Such services often present a user with security versus ownership dilemma. The user does not wish to pass full control over their asset to the custodian to facilitate safeguarding. A control sharing mechanism allowing the custodian to hold enough information and keeping the user as the owner of the asset is required. For the assets being secret information, cryptographic protocols...
Fault Injection (FI) attacks have become a practical threat to modern cryptographic implementations. Such attacks have recently focused more on exploitation of implementation-centric and device-specific properties of the faults. In this paper, we consider the parallel between SCA attacks and FI attacks; specifically, that many FI attacks rely on the data-dependency of activation and propagation of a fault, and SCA attacks similarly rely on data-dependent power usage. In fact, these are so...
Physical Unclonable Functions (PUFs) are used in various key-generation schemes and protocols. Such schemes are deemed to be secure even for PUFs with challenge-response behavior, as long as no responses and no reliability information about the PUF are exposed. This work, however, reveals a pitfall in these constructions: When using state-of-the-art helper data algorithms to correct noisy PUF responses, an attacker can exploit the publicly accessible helper data and challenges. We show that...
The design of software countermeasures against active and passive adversaries is a challenging problem that has been addressed by many authors in recent years. The proposed solutions adopt a theoretical foundation (such as a leakage model) but often do not offer concrete reference implementations to validate the foundation. Contributing to the experimental dimension of this body of work, we propose a customized processor called SKIVA that supports experiments with the design of...
Federated learning is gaining significant interests as it enables model training over a large volume of data that is distributedly stored over many users, while protecting the privacy of the individual users. However, a major bottleneck in scaling federated learning to a large number of users is the overhead of secure model aggregation across many users. In fact, the overhead of state-of-the-art protocols for secure model aggregation grows quadratically with the number of users. We propose a...
In a lockable obfuscation scheme a party takes as input a program $P$, a lock value $\alpha$, a message $m$ and produces an obfuscated program $\tilde{P}$. The obfuscated program can be evaluated on an input $x$ to learn the message $m$ if $P(x)= \alpha$. The security of such schemes states that if $\alpha$ is randomly chosen (independent of $P$ and $m$), then one cannot distinguish an obfuscation of $P$ from a ``dummy'' obfuscation. Existing constructions of lockable obfuscation achieve...
Fault attacks (FA) intentionally inject some fault into the encryption process for analyzing a secret key based on faulty intermediate values or faulty ciphertexts. One of the easy ways for software-based countermeasures is to use time redundancy. However, existing methods can be broken by skipping comparison operations or by using non-uniform distributions of faulty intermediate values. In this paper, we propose a secure software-based redundancy, aptly named table redundancy, applying...
We describe SKIVA, a customized 32-bit processor enabling the design of software countermeasures for a broad range of implementation attacks covering fault injection and side-channel analysis of timing-based and power-based leakage. We design the countermeasures as variants of bitslice programming. Our protection scheme is flexible and modular, allowing us to combine higher-order masking -- fending off side-channel analysis -- with complementary spatial and temporal redundancy -- protecting...
Persistent fault analysis (PFA) was proposed at CHES 2018 as a novel fault analysis technique. It was shown to completely defeat standard redundancy based countermeasure against fault analysis. In this work, we investigate the security of masking schemes against PFA. We show that with only one fault injection, masking countermeasures can be broken at any masking order. The study is performed on publicly available implementations of masking.
We show new partial and full instantiation results under chosen-ciphertext security for the widely implemented and standardized RSA-OAEP encryption scheme of Bellare and Rogaway (EUROCRYPT 1994) and two variants. Prior work on such instantiations either showed negative results or settled for ``passive'' security notions like IND-CPA. More precisely, recall that RSA-OAEP adds redundancy and randomness to a message before composing two rounds of an underlying Feistel transform, whose round...
An important prerequisite for Side-channel Attack (SCA) is leakage sampling where the side-channel measurements (e.g. power traces) of the cryptographic device are collected for further analysis. However, as the operating frequency of cryptographic devices continues to increase due to advancing technology, leakage sampling will impose higher requirements on the sampling equipment. This paper undertakes the first study to show that effective leakage sampling can be achieved without relying on...
The current paper improves the number of queries of the previous quantum multi-collision finding algorithms presented by Hosoyamada et al. at Asiacrypt 2017. Let an $l$-collision be a tuple of $l$ distinct inputs that result in the same output of a target function. In cryptology, it is important to study how many queries are required to find $l$-collisions for random functions of which domains are larger than ranges. The previous algorithm finds an $l$-collision for a random function by...
Recent improvements in the state-of-the-art of MPC for non-full-threshold access structures introduced the idea of using a collision-resistant hash functions and redundancy in the secret-sharing scheme to construct a communication-efficient MPC protocol which is computationally-secure against malicious adversaries, with abort. The prior work is based on replicated secret-sharing; in this work we extend this methodology to {\em any} multiplicative LSSS implementing a $Q_2$ access structure. ...
Implementation attacks like side-channel and fault attacks are a threat to deployed devices especially if an attacker has physical access. As a consequence, devices like smart cards and IoT devices usually provide countermeasures against implementation attacks, such as masking against side-channel attacks and detection-based countermeasures like temporal or spacial redundancy against fault attacks. In this paper, we show how to attack implementations protected with both masking and...
Since the seminal work of Boneh et al., the threat of fault attacks has been widely known and techniques for fault attacks and countermeasures have been studied extensively. The vast majority of the literature on fault attacks focuses on the ability of fault attacks to change an intermediate value to a faulty one, such as differential fault analysis (DFA), collision fault analysis, statistical fault attack (SFA), fault sensitivity analysis, or differential fault intensity analysis (DFIA)....
The trend of supporting wide vector units in general purpose microprocessors suggests opportunities for developing a new and elegant compilation approach to mitigate the impact of faults to cryptographic implementations, which we present in this work. We propose a compilation flow, CAMFAS, to automatically and selectively introduce vectorization in a cryptographic library - to translate a vanilla library into a library with vectorized code that is resistant to glitches. Unlike in traditional...
Oblivious Transfer (OT) is a simple, yet fundamental primitive which suffices to achieve almost every cryptographic application. In a recent work (Latincrypt `15), Chou and Orlandi (CO) present the most efficient, fully UC-secure OT protocol to date and argue its security under the CDH assumption. Unfortunately, a subsequent work by Genc et al. (Eprint `17) exposes a flaw in their proof which renders the CO protocol insecure. In this work, we make the following contributions: We first point...
A growing number of connected objects, with their high performance and low-resources constraints, are embedding lightweight ciphers for protecting the confidentiality of the data they manipulate or store. Since those objects are easily accessible, they are prone to a whole range of physical attacks, one of which are fault attacks against for which countermeasures are usually expensive to implement, especially on off-the-shelf devices. For such devices, we propose a new generic software...
Fault attack countermeasures can be implemented by storing or computing sensitive data in redundant form, such that the faulty data can be detected and restored. We present a class of lightweight, portable software countermeasures for block ciphers. Our technique is based on redundant bit-slicing, and it is able to detect faults in the execution of a single instruction. In comparison to earlier techniques, we are able to intercept data faults as well as instruction sequence faults using a...
Side-channel analysis and fault-injection attacks are known as major threats to any cryptographic implementation. Hardening cryptographic implementations with appropriate countermeasures is thus essential before they are deployed in the wild. However, countermeasures for both threats are of completely different nature: Side-channel analysis is mitigated by techniques that hide or mask key-dependent information while resistance against fault-injection attacks can be achieved by redundancy in...
Helper Data Systems are a cryptographic primitive that allows for the reproducible extraction of secrets from noisy measurements. Redundancy data called Helper Data makes it possible to do error correction while leaking little or nothing ("Zero Leakage") about the extracted secret string. We study the case of non-discrete measurement outcomes. In this case a quantization step is required. Recently de Groot et al described a generic method to perform the quantization in a Zero Leakage manner....
Pseudorandom functions (PRFs) play a central role in symmetric cryptography. While in principle they can be built from any one-way functions by going through the generic HILL (SICOMP 1999) and GGM (JACM 1986) transforms, some of these steps are inherently sequential and far from practical. Naor, Reingold (FOCS 1997) and Rosen (SICOMP 2002) gave parallelizable constructions of PRFs in NC\(^2\) and TC\(^0\) based on concrete number-theoretic assumptions such as DDH, RSA, and factoring....
Power networks are built with inherent redundancy, including in the communication channels. In this work, we show that this redundancy can increase the cyber security resiliency to key exposure. Specifically, we present CrypTop, a novel protocol for the {\em key setup and refresh} problem in power networks. CrypTop uses multipath communication and already-keyed devices, to setup keys in other devices, and to recover from key exposures. We evaluate CrypTop in realistic power network...
Low-cost resource-constrained devices can allocate very limited resources for implementing security. At the same time, they still require some level of protection. In this paper, we present a lightweight message authentication scheme based on Cyclic Redundancy Check (CRC). The presented CRC inherits the implementation simplicity of the conventional CRC checksum except that the LFSR implementing its encoding and decoding is made re-programmable. Similarly to previously proposed cryptographic...
Robust authenticated encryption (RAE) is a primitive for symmetric encryption that allows to flexibly specify the ciphertext expansion, i.e., how much longer the ciphertext is compared to the plaintext. For every ciphertext expansion, RAE aims at providing the best-possible authenticity and confidentiality. To investigate whether this is actually achieved, we characterize exactly the guarantees symmetric cryptography can provide for any given ciphertext expansion. Our characterization...
Classical fault attacks such as Differential Fault Analysis~(DFA) as well as biased fault attacks such as the Differential Fault Intensity Analysis~(DFIA) have been a major threat to cryptosystems in recent times. DFA uses pairs of fault-free and faulty ciphertexts to recover the secret key. DFIA, on the other hand, combines principles of side channel analysis and fault attacks to try and extract the key using faulty ciphertexts only. Till date, no effective countermeasure that can thwart...
Hill is a classical cipher which is generally believed to be resistant against ciphertext-only attack. In this paper, by using a divide-and-conquer technique, it is first shown that Hill with d*d key matrix over Z_26 can be broken with computational complexity of O(d26^d), for the English language. This is much less than the only publicly known attack, i.e., the brute-force with complexity of O(d^3(26)^(d^2)). Then by using the Chinese Remainder Theorem, it is shown that the computational...
A simple and practical hashing scheme based on Cyclic Redundancy Check (CRC) is presented. Similarly to previously proposed cryptographically secure CRCs, the presented one detects both, random and malicious, errors without increasing bandwidth. However, we use a product of irreducible polynomials instead of a single irreducible polynomial for generating the CRC. This is an advantage since smaller irreducible polynomials are easier to compute. The price we pay is that the probability that...
Often S-boxes are the only nonlinear component in a block cipher and as such play an important role in ensuring its resistance to cryptanalysis. Cryptographic properties and constructions of S-boxes have been studied for many years. The most common techniques for constructing S-boxes are: algebraic constructions, pseudo-random generation and a variety of heuristic approaches. Among the latter are the genetic algorithms. In this paper, a genetic algorithm working in a reversed way is...
Compression is desirable for network applications as it saves bandwidth; however, when data is compressed before being encrypted, the amount of compression leaks information about the amount of redundancy in the plaintext. This side channel has led to successful CRIME and BREACH attacks on web traffic protected by the Transport Layer Security (TLS) protocol. The general guidance in light of these attacks has been to disable compression, preserving confidentiality but sacrificing bandwidth....
While expensive cryptographically verifiable computation aims at defeating malicious agents, many civil purposes of outsourced computation tolerate a weaker notion of security, i.e., ``lazy-but-honest'' contractors. Targeting this type of agents, we develop optimal contracts for outsourcing of computational tasks via appropriate use of rewards, punishments, auditing rate, and ``redundancy''. Our contracts provably minimize the expense of the outsourcer (principal) while guaranteeing correct...
Impossible differential cryptanalysis has been proved to be one of the most powerful techniques to attack block ciphers. Based on the impossible differential paths, we can usually add several rounds before or after to launch the key recovery attack. Impossible differential cryptanalysis is powerful not only because the number of rounds it can break is very competitive compared to other attacks, but also unlike differential attacks which are statistical attacks in the essential, impossible...
Oblivious RAM (ORAM) is an established technique to hide the access pattern to an untrusted storage system. With ORAM, a curious adversary cannot tell what data address the user is accessing when observing the bits moving between the user and the storage system. All existing ORAM schemes achieve obliviousness by adding redundancy to the storage system, i.e., each access is turned into multiple random accesses. Such redundancy incurs a large performance overhead. Though traditional data...
We settle a long standing open problem which has pursued a full characterization of completeness of (potentially randomized) finite functions for 2-party computation that is secure against active adversaries. Since the first such complete function was discovered [Kilian, FOCS 1988], the question of which finite 2-party functions are complete has been studied extensively, leading to characterization in many special cases. In this work, we completely settle this problem. We provide a...
Large-scale storage systems often attempt to achieve two seemingly conflicting goals: (1) the systems need to reduce the copies of redundant data to save space, a process called deduplication; and (2) users demand encryption of their data to ensure privacy. Conventional encryption makes deduplication on ciphertexts ineffective, as it destroys data redundancy. A line of work, originated from Convergent Encryption [28], and evolved into Message Locked Encryption [12], strives to solve this...
Fault attacks against embedded circuits enabled to define many new attack paths against secure circuits. Every attack path relies on a specific fault model which defines the type of faults that the attacker can perform. On embedded processors, a fault model consisting in an assembly instruction skip can be very useful for an attacker and has been obtained by using several fault injection means. To avoid this threat, some countermeasure schemes which rely on temporal redundancy have been...
We investigate the problem of algebraic manipulation detection (AMD) over a communication channel that partially leaks information to an adversary. We assume the adversary is computationally unbounded and there is no shared key or correlated randomness between the sender and the receiver. We introduce leakage-resilient (LR)-AMD codes to detect algebraic manipulation in this model. We consider two leakage models. The first model, called \emph{linear leakage}, requires the adversary's...
MASH-1 is modular arithmetic based hash function. It is presented in Part 4 of ISO/IEC 10118 standard for one and a half decade. Cryptographic strength of MASH-1 hash function is based on factorization problem of an RSA modulus along with redundancy in the input blocks of compression functions. Despite of this, we are able to introduce two large classes of moduli which allow practical time collision finding algorithm for MASH-1. In one case even multicollisions of arbitrary length can be constructed.
In this paper we present new constraints to EPCglobal Class 1 Generation 2 (EPC-C1 G2) standard which if they have been considered in the design of EPC-C1 G2 complaint authentication protocols, lead to prevent predecessor's protocols' weaknesses and also present the secure ones. Also in this paper as an example, we use Pang \textit{et al.} EPC-C1 G2-friendly protocol which has been recently proposed, to show our proposed constraints in EPC-C1 G2 standard. Pang \textit{et al.}'s protocol...
Verified security provides a firm foundation for cryptographic proofs by means of rigorous programming language techniques and verification methods. EasyCrypt is a framework that realizes the verified security paradigm and supports the machine-checked construction and verification of cryptographic proofs using state-of-the-art SMT solvers, automated theorem provers and interactive proof assistants. Previous experiments have shown that EasyCrypt is effective for a posteriori validation of...
The main contributions of this paper are twofold. On the one hand, the twin Diffie-Hellman (twin DH) problem proposed by Cash, Kiltz and Shoup is extended to the $n$-Diffie-Hellman ($n$-DH) problem for an arbitrary integer $n$, and this new problem is shown to be at least as hard as the ordinary DH problem. Like the twin DH problem, the $n$-DH problem remains hard even in the presence of a decision oracle that recognizes solution to the problem. On the other hand, observe that the...
Faults occurred during the operations in a hardware device cause many problems such as performance deterioration, unreliable output, etc. If a fault occurs in a cryptographic hardware device, the effect can be even serious because an adversary may exploit it to find the secret information stored in the device. More precisely, the adversary can find the key of a block cipher using differential information between correct and faulty ciphertexts obtained by inducing faults during the...
In 2007, the E.U. FP6 SecurIST called for trustworthy international identity management (IdM) that was user-centric. In 2009, the U.S. Department of Homeland Security (DHS) called for trustworthy global-scale IdM and the U.S. National Institute of Standards and Technology (NIST) called for new cryptographic key management (CKM) designs. In this paper we outline the core architecture for (apparently) the first globally scalable, post quantum secure, symmetric key based platform for...
Cold boot attack is a side channel attack which exploits the data remanence property of random access memory (RAM) to retrieve its contents which remain readable shortly after its power has been removed. Given the nature of the cold boot attack, only a corrupted image of the memory contents will be available to the attacker. In this paper, we investigate the use of an off-the-shelf SAT solver, CryptoMinSat, to improve the key recovery of the AES-128 key schedules from its corresponding...
Against such attacks as rubber-hose attack, key authentic degree of cryptosystem is expatiated in detail, and the important significance of key authentic degree of cryptosystem is pointed out. And the key authentic degrees of modern cryptosystem under different conditions are given. Research shows that under most realistic situations, the key authentic degree of modern cryptosystem is high, this means that modern cryptosystem is threatened by such as rubber-hose attack and so on. Feasibility...
In 1999, Coron, Naccache and Stern discovered an existential signature forgery for two popular RSA signature standards, ISO/IEC 9796-1 and 2. Following this attack ISO/IEC 9796-1 was withdrawn. ISO/IEC 9796-2 was amended by increasing the message digest to at least 160 bits. Attacking this amended version required at least 2^61 operations. In this paper, we exhibit algorithmic refinements allowing to attack the amended (currently valid) version of ISO/IEC 9796-2 for all modulus sizes. A...
Certificateless public key cryptography was introduced to solve the key escrow problem in identity based cryptography while enjoying the most attractive {\em certificateless} property. In this paper, we present the first {\em secure} certificateless public key encryption (CLPKE) scheme {\em without redundancy}. Our construction provides optimal bandwidth and a quite efficient decryption process among all the existing CLPKE schemes. It is provably secure against adaptive chosen ciphertext...
The Joint Sparse Form is currently the standard representation system to perform multi-scalar multiplications of the form $[n]P m[Q]$. We introduce the concept of Joint Double-Base Chain, a generalization of the Double-Base Number System to represent simultaneously $n$ and $m$. This concept is relevant because of the high redundancy of Double-Base systems, which ensures that we can find a chain of reasonable length that uses exactly the same terms to compute both $n$ and $m$. Furthermore,...
Kurosawa and Desmedt proposed an efficient hybrid encryption scheme(KD04) which is secure against adaptive chosen ciphertext attacks(IND-CCA) although the underlying KEM(key encapsulation mechanism) is not IND-CCA secure\cite{Kurosawa2004}. We show a variant of KD04 which is IND-CCA secure when the the underlying DEM part is IND-CCA secure. We need a DEM built from one-time symmetric encryption scheme and a MAC in the security reduction to check if the KEM part of a ciphertext is valid....
Digital signature schemes based on public-key cryptosystems generally permit existential forgery, except the schemes are equipped with some message formatting mechanisms, such as using hash functions or padding redundancies. In 2004, Chang et al. proposed a new digital signature scheme, and claimed the scheme without using any hash function or padding any redundancy can resist forgery attacks. However, many attacks on Chang et al.'s scheme were presented. Kang et al. also gave an effective...
In this paper, we investigate the application of concurrent error detection circuitry to a compact application-specific integrated circuit (ASIC) implementation of the Advanced Encryption Standard (AES). The specific objective of the design is to develop a method suitable for compact ASIC implementations targeted to embedded systems such that the system is resistant to fault attacks. To provide the error detection, recognizing that previously proposed schemes are not well suited to compact...
Wang and Yu showed that MD5 was not collision-resistant, but it is known that their sufficient conditions for finding a collision of MD5 includes some mistakes. In this paper, we examine the sufficient conditions by computer simulation. We show that the Wang-Yu conditions include 16 unnecessary conditions for making a collision. Sasaki et al. claimed that modifying one condition made it possible to remove eleven conditions. However, the result of our computer simulation shows that their...
In this paper we view interleaved Gabidulin codes and describe how to correct errors up to a rank equal to the amount of redundancy of the code with high probability. We give a detailed proof for our estimation of the probability of correct decoding. In a second part, we view the application to variants of the GPT cryptosystem. For GGPT this leads to an efficient attack on the remaining secure instances, whereas it allows to derive at least partial information of the plaintext in the case of RRC-GPT.
We describe a practical identity-based encryption scheme that is secure in the standard model against chosen-ciphertext (CCA2) attacks. Security is based on an assumption comparable to (but slightly stronger than) Bilinear Decisonal Diffie-Hellman (BDDH). A comparison shows that our construction outperforms all known identity-based encryption schemes in the standard model and its performance is even comparable with the one from the random-oracle based Boneh/Franklin IBE scheme. Our proposed...
This thesis gives an overview of Multivariate Quadratic polynomial equations and their use in public key cryptography. In the first chapter, some general terms of cryptography are introduced. In particular, the need for public key cryptography and alternative schemes is motivated, i.e., systems which neither use factoring (like RSA, Rivest-Shamir-Adleman) nor the discrete logarithm (like ECC, elliptic curve cryptography). This is followed by a brief introduction of finite fields and a...
Often an attacker tries to disconnect a network by destroying nodes or edges, while the defender counters using various resilience mechanisms. Examples include a music industry body attempting to close down a peer-to-peer file-sharing network; medics attempting to halt the spread of an infectious disease by selective vaccination; and a police agency trying to decapitate a terrorist organisation. Albert, Jeong and Barabasi famously analysed the static case, and showed that vertex-order...
Mundja is a MAC generation algorithm that has been designed for use together with a stream cipher. Mundja accumulates the message onto two independent registers: the first is a Cyclic Redundancy Checksum (CRC) that uses linear feedback; the second is a strengthened version of the SHA-256 register that uses nonlinear feedback. Mundja is fast (asymptotically about 4 times the speed of HMAC-SHA-256), and can generate MACs of any desired length. Mundja is designed to be secure at the equivalent...
It is found that Chang et al.'s signature scheme with message recovery is not as secure as they claimed, in fact. In this letter, two forgery attacks is proposed to show that the signature can be forged on any uncontrolled messages. To overcome these attacks, the one-way hash functions and the message redundancy schemes may be still used.
Recently, Chang \textit{et al}. \cite{Chang} proposed a new digital signature scheme with message recovery and claimed that neither one-way hash functions nor message redundancy schemes were employed in their scheme. However, in this letter, two forgery attacks are proposed to show that Chang \textit{et al.}'s signature scheme is not secure. To resist these attacks, the message redundancy schemes may be still used.
In extension of the bit commitment task and following work initiated by Crepeau and Kilian, we introduce and solve the problem of characterising the optimal rate at which a discrete memoryless channel can be used for bit commitment. It turns out that the answer is very intuitive: it is the maximum equivocation of the channel (after removing trivial redundancy), even when unlimited noiseless bidirectional side communication is allowed. By a well-known reduction, this result provides a lower...
We show the existence of a previously unknown linear redundancy property of the only nonlinear component of the AES block cipher. It is demonstrated that the outputs of the 8*8 Rijndael s-box (based on inversion in a finite field) are all equivalent under affine transformation. The method used to discover these affine relations is novel and exploits a new fundamental result on the invariance properties of local connection structure of affine equivalence classes. As well as increasing...