272 results sorted by ID
Universal Context Commitment without Ciphertext Expansion
Arghya Bhattacharjee, Ritam Bhaumik, Chandranan Dhar
Secret-key cryptography
An ongoing research challenge in symmetric cryptography is to design an authenticated encryption (AE) with a commitment to the secret key or preferably to the entire context. One way to achieve this is to use a transform on an existing AE scheme, if possible with no output length expansion. At EUROCRYPT'22, Bellare and Hoang proposed the HtE transform, which lifts key-commitment to context-commitment. In the same year at ESORICS'22, Chan and Rogaway proposed the CTX transform, which works on...
Authenticity in the Presence of Leakage using a Forkcipher
Francesco Berti, François-Xavier Standaert, Itamar Levi
Secret-key cryptography
Robust message authentication codes (MACs) and authenticated encryption (AE) schemes that provide authenticity in the presence of side-channel leakage are essential primitives. These constructions often rely on primitives designed for strong leakage protection, among others including the use of strong-unpredictable (tweakable) block-ciphers.
This paper extends the strong-unpredictability security definition to the versatile and new forkcipher primitive. We show how to construct secure and...
Committing Wide Encryption Mode with Minimum Ciphertext Expansion
Yusuke Naito, Yu Sasaki, Takeshi Sugawara
Secret-key cryptography
We propose a new wide encryption (WE) mode of operation that satisfies robust authenticated encryption (RAE) and committing security with minimum ciphertext expansion. WE is attracting much attention in the last few years, and its advantage includes RAE security that provides robustness against wide range of misuses, combined with the encode-then-encipher (EtE) construction. Unfortunately, WE-based EtE does not provide good committing security, and there is a recent constant-time CMT-4...
Side-Channel and Fault Resistant ASCON Implementation: A Detailed Hardware Evaluation (Extended Version)
Aneesh Kandi, Anubhab Baksi, Peizhou Gan, Sylvain Guilley, Tomáš Gerlich, Jakub Breier, Anupam Chattopadhyay, Ritu Ranjan Shrivastwa, Zdeněk Martinásek, Shivam Bhasin
Implementation
In this work, we present various hardware implementations for the lightweight cipher ASCON, which was recently selected as the winner of the NIST organized Lightweight Cryptography (LWC) competition. We cover encryption + tag generation and decryption + tag verification for the ASCON AEAD and also the ASCON hash function. On top of the usual (unprotected) implementation, we present side-channel protection (threshold countermeasure) and triplication/majority-based fault protection. To the...
A new stand-alone MAC construct called SMAC
Dachao Wang, Alexander Maximov, Patrik Ekdahl, Thomas Johansson
Secret-key cryptography
In this paper, we present a new efficient stand-alone MAC construct based on processing using the FSM part of the stream cipher family SNOW, which in turn uses the AES round function. It offers a combination of very high speed in software and hardware with a truncatable tag. Three concrete versions of SMAC are proposed with different security levels, although other use cases are also possible. For example, SMAC can be combined with an external ciphering engine in AEAD mode. Every design...
Tight Multi-user Security of Ascon and Its Large Key Extension
Bishwajit Chakraborty, Chandranan Dhar, Mridul Nandi
Secret-key cryptography
The Ascon cipher suite has recently become the preferred standard in the NIST Lightweight Cryptography standardization process. Despite its prominence, the initial dedicated security analysis for the Ascon mode was conducted quite recently. This analysis demonstrated that the Ascon AEAD mode offers superior security compared to the generic Duplex mode, but it was limited to a specific scenario: single-user nonce-respecting, with a capacity strictly larger than the key size. In this paper, we...
CCA Secure Updatable Encryption from Non-Mappable Group Actions
Jonas Meers, Doreen Riepel
Cryptographic protocols
Ciphertext-independent updatable encryption (UE) allows to rotate encryption keys and update ciphertexts via a token without the need to first download the ciphertexts. Although, syntactically, UE is a symmetric-key primitive, ciphertext-independent UE with forward secrecy and post-compromise security is known to imply public-key encryption (Alamati, Montgomery and Patranabis, CRYPTO 2019).
Constructing post-quantum secure UE turns out to be a difficult task. While lattices offer the...
2024/343
Last updated: 2024-04-08
Partial Differential Fault Analysis on Ascon
Yang Gao
Attacks and cryptanalysis
Authenticated Encryption with Associated Data (AEAD) is a trend in applied cryptography because it combine confidentiality, integrity, and authentication into one algorithm and is more efficient than using block ciphers and hash functions separately. The Ascon algorithm, as the winner in both the CAESAR competition and the NIST LwC competition, will soon become the AEAD standard for protecting the Internet of Things and micro devices with limited computing resources. We propose a partial...
Constructing Committing and Leakage-Resilient Authenticated Encryption
Patrick Struck, Maximiliane Weishäupl
Secret-key cryptography
The main goal of this work is to construct authenticated encryption (AE) that is both committing and leakage-resilient. As a first approach for this we consider generic composition as a well-known method for constructing AE schemes. While the leakage resilience of generic composition schemes has already been analyzed by Barwell et al. (AC'17), for committing security this is not the case. We fill this gap by providing a separate analysis of the generic composition paradigms with respect to...
CCA Security with Short AEAD Tags
Mustafa Khairallah
Secret-key cryptography
The size of the authentication tag represents a significant overhead for applications that are limited by bandwidth or memory. Hence, some authenticated encryption designs have a smaller tag than the required privacy level, which was also suggested by the NIST lightweight cryptography standardization project. In the ToSC 2022, two papers have raised questions about the IND-CCA security of AEAD schemes in this situation. These papers show that (a) online AE cannot provide IND-CCA security...
When and How to Aggregate Message Authentication Codes on Lossy Channels?
Eric Wagner, Martin Serror, Klaus Wehrle, Martin Henze
Secret-key cryptography
Aggregation of message authentication codes (MACs) is a proven and efficient method to preserve valuable bandwidth in resource-constrained environments: Instead of appending a long authentication tag to each message, the integrity protection of multiple messages is aggregated into a single tag. However, while such aggregation saves bandwidth, a single lost message typically means that authentication information for multiple messages cannot be verified anymore. With the significant increase...
A note on ``HAKECC: highly efficient authentication and key agreement scheme based on ECDH for RFID in IOT environment''
Zhengjun Cao
Attacks and cryptanalysis
We show that the Nikooghadam-Shahriari-Saeidi authentication and key agreement scheme [J. Inf. Secur. Appl., 76, 103523 (2023)]
cannot resist impersonation attack, not as claimed. An adversary can impersonate the RFID reader to cheat the RFID tag. The drawback results from its simple secret key invoking mechanism. We also find it seems difficult to revise the scheme due to the inherent flaw.
CompactTag: Minimizing Computation Overheads in Actively-Secure MPC for Deep Neural Networks
Yongqin Wang, Pratik Sarkar, Nishat Koti, Arpita Patra, Murali Annavaram
Cryptographic protocols
Secure Multiparty Computation (MPC) protocols enable secure evaluation of a circuit by several parties, even in the presence of an adversary who maliciously corrupts all but one of the parties. These MPC protocols are constructed using the well-known secret-sharing-based paradigm (SPDZ and SPD$\mathbb{Z}_{2^k}$), where the protocols ensure security against a malicious adversary by computing Message Authentication Code (MAC) tags on the input shares and then evaluating the circuit with these...
About “$k$-bit security” of MACs based on hash function Streebog
Vitaly Kiryukhin
Secret-key cryptography
Various message authentication codes (MACs), including HMAC-Streebog and Streebog-K, are based on the keyless hash function Streebog. Under the assumption that the compression function of Streebog is resistant to the related key attacks, the security proofs of these algorithms were recently presented at CTCrypt 2022.
We carefully detail the resources of the adversary in the related key settings, revisit the proof, and obtain tight security bounds. Let $n$ be the bit length of the hash...
Nonlinear computations on FinTracer tags
Michael Brand, Tania Churchill, Carsten Friedrich
Applications
Recently, the FinTracer algorithm was introduced as a versatile framework for detecting economic crime typologies in a privacy-preserving fashion. Under the hood, FinTracer stores its data in a structure known as the ``FinTracer tag’’. One limitation of FinTracer tags, however, is that because their underlying cryptographic implementation relies on additive semi-homomorphic encryption, all the system's oblivious computations on tag data are linear in their input ciphertexts. This allows a...
Fuzzy Deduplication Scheme Supporting Pre-verification of Label Consistency
Zehui Tang, Shengke Zeng, Tao Li, Shuai Cheng, Haoyu Zheng
Applications
Efficiently and securely removing encrypted redundant data with cross-user in the cloud is challenging. Convergent Encryption (CE) is difficult to resist dictionary attacks for its deterministic tag. Server-aided mechanism is against such attacks while it may exist collusion. Focus on multimedia data, this paper proposes an efficient and secure fuzzy deduplication system without any additional servers. We also propose a notion of preverification of label consistency to compensate for the...
Conjunctive Searchable Symmetric Encryption from Hard Lattices
Debadrita Talapatra, Sikhar Patranabis, Debdeep Mukhopadhyay
Cryptographic protocols
Searchable Symmetric Encryption (SSE) supports efficient keyword searches over encrypted outsourced document collections while minimizing information leakage. All practically efficient SSE schemes supporting conjunctive queries rely crucially on quantum-broken cryptographic assumptions (such as discrete-log hard groups) to achieve compact storage and fast query processing. On the other hand, quantum-safe SSE schemes based on purely symmetric-key crypto-primitives either do not support...
Extending Updatable Encryption: Public Key, Tighter Security and Signed Ciphertexts
Chen Qian, Yao Jiang Galteland, Gareth T. Davies
Cryptographic protocols
Updatable encryption is a useful primitive that enables key rotation for storing data on an untrusted storage provider without the leaking anything about the plaintext or the key. In this work, we make two contributions. Firstly, we extend updatable encryption to the public-key setting, providing its security model and three different efficient constructions. Using a public-key updatable encryption scheme, a user can receive messages directly in the cloud from multiple senders without...
Exact Security Analysis of ASCON
Bishwajit Chakraborty, Chandranan Dhar, Mridul Nandi
Secret-key cryptography
The Ascon cipher suite, offering both authenticated encryption with associated data (AEAD) and hashing functionality, has recently emerged as the winner of the NIST Lightweight Cryptography (LwC) standardization process. The AEAD schemes within Ascon, namely Ascon-128 and Ascon-128a, have also been previously selected as the preferred lightweight authenticated encryption solutions in the CAESAR competition. In this paper, we present a tight and comprehensive security analysis of the Ascon...
Tagged Chameleon Hash from Lattices and Application to Redactable Blockchain
Yiming Li, Shengli Liu
Public-key cryptography
Chameleon hash (CH) is a trapdoor hash function. Generally it is hard to find collisions, but with the help of a trapdoor, finding collisions becomes easy. CH plays an important role in converting a conventional blockchain to a redactable one. However, most of existing CH schemes are too weak to support redactable blockchains. The currently known CH schemes serving for redactable blockchains have the best security of so-called ``full collision resistance (f-CR)'', but they are built either...
Statement-Oblivious Threshold Witness Encryption
Sebastian Faust, Carmit Hazay, David Kretzler, Benjamin Schlosser
Public-key cryptography
The notion of witness encryption introduced by Garg et al. (STOC'13) allows to encrypt a message under a statement $x$ from some NP-language $\mathcal{L}$ with associated relation $(x,w) \in \mathcal{R}$, where decryption can be carried out with the corresponding witness $w$. Unfortunately, known constructions for general-purpose witness encryption rely on strong assumptions, and are mostly of theoretical interest. To address these shortcomings, Goyal et al. (PKC'22) recently introduced a...
Padding-based forgeries in the mode XOCB
Jean Liénardy
Cryptographic protocols
In this note, we identify a minor flaw in the design of the XOCB mode, presented at Eurocrypt '23. This vulnerability enables trivial tag forgeries and arises from the padding applied to messages. We examine the security proof and pinpoint the presence of the flaw within it. Furthermore, we propose a simple fix for this issue, drawing upon the features of OCB3, and discuss the implications of this modification on the proof of security.
Efficient Zero-Knowledge Arguments for Some Matrix Relations over Ring and Non-malleable Enhancement
Yuan Tian
Cryptographic protocols
Various matrix relations widely appeared in data-intensive computations, as a result their zero-knowledge proofs/arguments (ZKP/ZKA) are naturally required in large-scale private computing applications.
In the first part of this paper, we concretely establish efficient commit-and-proof zero-knowledge arguments for linear matrix relation AU = B and bilinear relation UTQV = Y over the residue ring Zm with logarithmic message complexity. We take a direct, matrix-oriented (rather than...
Analyzing the Leakage Resistance of the NIST's Lightweight Crypto Competition's Finalists
Corentin Verhamme, Gaëtan Cassiers, François-Xavier Standaert
Implementation
We investigate the security of the NIST Lightweight Crypto Competition’s Finalists against side-channel attacks. We start with a mode-level analysis that allows us to put forward three candidates (As- con, ISAP and Romulus-T) that stand out for their leakage properties and do not require a uniform protection of all their computations thanks to (expensive) implementation-level countermeasures. We then implement these finalists and evaluate their respective performances. Our results confirm...
(Inner-Product) Functional Encryption with Updatable Ciphertexts
Valerio Cini, Sebastian Ramacher, Daniel Slamanig, Christoph Striecks, Erkan Tairi
Public-key cryptography
We propose a novel variant of functional encryption which supports ciphertext updates, dubbed ciphertext-updatable functional encryption (CUFE). Such a feature further broadens the practical applicability of the functional-encryption paradigm and allows for fine-grained access control even after a ciphertext is generated. Updating ciphertexts is carried out via so-called update tokens which a dedicated party can use to convert ciphertexts. However, allowing update tokens requires some care...
Cumulatively All-Lossy-But-One Trapdoor Functions from Standard Assumptions
Benoît Libert, Ky Nguyen, Alain Passelègue
Public-key cryptography
Chakraborty, Prabhakaran, and Wichs (PKC'20) recently introduced a new tag-based variant of lossy trapdoor functions, termed cumulatively all-lossy-but-one trapdoor functions (CALBO-TDFs). Informally, CALBO-TDFs allow defining a public tag-based function with a (computationally hidden) special tag, such that the function is lossy for all tags except when the special secret tag is used. In the latter case, the function becomes injective and efficiently invertible using a secret trapdoor. This...
Hybrid Post-Quantum Signatures in Hardware Security Keys
Diana Ghinea, Fabian Kaczmarczyck, Jennifer Pullman, Julien Cretin, Stefan Kölbl, Rafael Misoczki, Jean-Michel Picod, Luca Invernizzi, Elie Bursztein
Implementation
Recent advances in quantum computing are increasingly jeopardizing the security of cryptosystems currently in widespread use, such as RSA or elliptic-curve signatures. To address this threat, researchers and standardization institutes have accelerated the transition to quantum-resistant cryptosystems, collectively known as Post-Quantum Cryptography (PQC). These PQC schemes present new challenges due to their larger memory and computational footprints and their higher chance of latent...
Multi-Input Quadratic Functional Encryption: Stronger Security, Broader Functionality
Shweta Agrawal, Rishab Goyal, Junichi Tomida
Public-key cryptography
Multi-input functional encryption, MIFE, is a powerful generalization of functional encryption that allows computation on encrypted data coming from multiple different data sources. In a recent work, Agrawal, Goyal, and Tomida (CRYPTO 2021) constructed MIFE for the class of quadratic functions. This was the first MIFE construction from bilinear maps that went beyond inner product computation. We advance the state-of-the-art in MIFE, and propose new constructions with stronger security and...
A Sponge-Based PRF with Good Multi-user Security
Arghya Bhattacharjee, Ritam Bhaumik, Mridul Nandi
Secret-key cryptography
Both multi-user PRFs and sponge-based constructions have generated a lot of research interest lately. Dedicated analyses for multi-user security have improved the bounds a long distance from the early generic bounds obtained through hybrid arguments, yet the bounds generally don't allow the number of users to be more than birthday-bound in key-size. Similarly, known sponge constructions suffer from being only birthday-bound secure in terms of their capacity.
We present in this paper...
Secure Message Authentication in the Presence of Leakage and Faults
Francesco Berti, Chun Guo, Thomas Peters, Yaobin Shen, François-Xavier Standaert
Secret-key cryptography
Security against side-channels and faults is a must for the deployment of embedded cryptography. A wide body of research has investigated solutions to secure implementations against these attacks at different abstraction levels. Yet, to a large extent, current solutions focus on one or the other threat. In this paper, we initiate a mode-level study of cryptographic primitives that can ensure security in a (new and practically-motivated) adversarial model combining leakage and faults. Our...
Practical Related-Key Forgery Attacks on the Full TinyJAMBU-192/256
Orr Dunkelman, Eran Lambooij, Shibam Ghosh
Attacks and cryptanalysis
TinyJambu is one of the finalists in the NIST lightweight cryptography competition. It has undergone extensive analysis in the recent years as both the keyed permutation as well as the mode are new designs. In this paper we present a related-key forgery attackon the updated TinyJambu scheme with 256- and 192-bit keys. We introduce a high probability related-key differential attack were the differences are only introduced into the key state. Therefore, the characteristic is applicable to the...
On Non-uniform Security for Black-box Non-Interactive CCA Commitments
Rachit Garg, Dakshita Khurana, George Lu, Brent Waters
Foundations
We obtain a black-box construction of non-interactive CCA commitments against non-uniform adversaries. This makes black-box use of an appropriate base commitment scheme for small tag spaces, variants of sub-exponential hinting PRG (Koppula and Waters, Crypto 2019) and variants of keyless sub-exponentially collision-resistant hash function with security against non-uniform adversaries (Bitansky, Kalai and Paneth, STOC 2018 and Bitansky and Lin, TCC 2018).
All prior works on non-interactive...
Authentication in the Bounded Storage Model
Yevgeniy Dodis, Willy Quach, Daniel Wichs
Foundations
We consider the streaming variant of the Bounded Storage Model (BSM), where the honest parties can stream large amounts of data to each other, while only maintaining a small memory of size $n$. The adversary also operates as a streaming algorithm, but has a much larger memory size $m \gg n$. The goal is to construct unconditionally secure cryptographic schemes in the BSM, and prior works did so for symmetric-key encryption, key agreement, oblivious transfer and multiparty computation. In...
2022/511
Last updated: 2022-08-27
OOBKey: Key Exchange with Implantable Medical Devices Using Out-Of-Band Channels
Mo Zhang, Eduard Marin, David Oswald, Vassilis Kostakos, Mark Ryan, Benjamin Tag, Kleomenis Katevas
Cryptographic protocols
Implantable Medical Devices (IMDs) are widely deployed today and often use wireless communication. Establishing a secure
communication channel to these devices is vital, however, also challenging in practice. To address this issue, numerous
researchers have proposed IMD key exchange protocols, in particular ones that leverage an Out-Of-Band (OOB) channel
such as audio, vibration and physiological signals. These solutions have advantages over traditional key exchange, e.g.,...
Short Lattice Signature Scheme with Tighter Reduction under Ring-SIS Assumption
Kaisei Kajita, Go Ohtake, Kazuto Ogawa, Koji Nuida, Tsuyoshi Takagi
Public-key cryptography
We propose a short signature scheme under the ring-SIS assumption in the standard model.
Specifically, by revisiting an existing construction [Ducas and Micciancio, CRYPTO 2014], we demonstrate lattice-based signatures with improved reduction loss. As far as we know, there are no ways to use multiple tags in the signature simulation of security proof in the lattice tag-based signatures. We address the tag-collision possibility in the lattice setting, which improves reduction loss. Our scheme...
On the Security of TrCBC
Debrup Chakraborty, Samir Kundu
Attacks and cryptanalysis
TrCBC is a variant of CBC-MAC which appeared in Information Processing Letters, 112(7):302-307, 2012. The authors claimed TrCBC to be a secure message authentication code (MAC) with some interesting properties. If TrCBC is instantiated with a block cipher with block length n, then it requires ⌈λ/n⌉ block cipher calls for authenticating a λ-bit message and requires a single key, which is the block cipher key. The authors state that TrCBC can have tag lengths of size less than n/2. We show...
Related-Tweakey Impossible Differential Attack on Reduced-Round SKINNY-AEAD M1/M3
Yanhong Fan,Muzhou Li,Chao Niu,Zhenyu Lu,Meiqin Wang
Secret-key cryptography
SKINNY-AEAD is one of the second-round candidates of the Lightweight Cryptography Standardization project held by NIST. SKINNY-AEAD M1 is the primary member of six SKINNY-AEAD schemes, while SKINNY-AEAD M3 is another member with a small tag. In the design document, only security analyses of their underlying primitive SKINNY-128-384 are provided. Besides, there are no valid third-party analyses on SKINNY-AEAD M1/M3 according to our knowledge. Therefore, this paper focuses on constructing the...
Breaking Panther
Christina Boura, Rachelle Heim Boissier, Yann Rotella
Secret-key cryptography
Panther is a sponge-based lightweight authenticated encryption scheme published at Indocrypt 2021. Its round function is based on four Nonlinear Feedback Shift Registers (NFSRs). We show here that it is possible to fully recover the secret key of the construction by using a single known plaintext-ciphertext pair and with minimal computational ressources. Furthermore, we show that in a known ciphertext setting an attacker is able with the knowledge of a single ciphertext to decrypt all...
Security and Privacy Analysis of Recently Proposed ECC-Based RFID Authentication Schemes
Atakan Arslan, Muhammed Ali Bingöl
Cryptographic protocols
Elliptic Curve Cryptography (ECC) has been popularly used in RFID authentication protocols to efficiently overcome many security and privacy issues. Even if the strong cryptography primitives of ECC are utilised in the authentication protocols, the schemes are alas far from providing security and privacy properties as desired level. In this paper, we analyze four up-to-minute ECC based RFID authentication schemes proposed by Gasbi et al., Benssalah et al., Kumar et al., and Agrahari and...
Analyzing the Provable Security Bounds of GIFT-COFB and Photon-Beetle
Akiko Inoue, Tetsu Iwata, Kazuhiko Minematsu
Secret-key cryptography
We study the provable security claims of two NIST Lightweight Cryptography (LwC) finalists, GIFT-COFB and Photon-Beetle, and present several attacks whose complexities contradict their claimed bounds in their final round specification documents.
For GIFT-COFB, we show an attack using $q_e$ encryption queries and no decryption query to break privacy (IND-CPA). The success probability is $O(q_e/2^{n/2})$ for $n$-bit block while the claimed bound contains $O(q^2_e/2^{n})$. This positively...
A New Security Notion for PKC in the Standard Model: Weaker, Simpler, and Still Realizing Secure Channels
Wasilij Beskorovajnov, Roland Gröll, Jörn Müller-Quade, Astrid Ottenhues, Rebecca Schwerdt
Public-key cryptography
Encryption satisfying CCA2 security is commonly known to be unnecessarily strong for realizing secure channels. Moreover, CCA2 constructions in the standard model are far from being competitive practical alternatives to constructions via random oracle. A promising research area to alleviate this problem are weaker security notions—like IND-RCCA secure encryption or IND-atag-wCCA secure tag-based encryption—which are still able to facilitate secure message transfer (SMT) via authenticated...
TEDT2 - Highly Secure Leakage-resilient TBC-based Authenticated Encryption
Eik List
Secret-key cryptography
Leakage-resilient authenticated encryption (AE) schemes received considerable attention during the previous decade. Two core security models of bounded and unbounded leakage have evolved, where the latter has been motivated in a very detailed and practice-oriented manner. In that setting, designers often build schemes based on (tweakable) block ciphers due to the small state size, such as the recent two-pass AE scheme TEDT from TCHES 1/2020. TEDT is interesting due to its high security...
Downgradable Identity-Based Signatures and Trapdoor Sanitizable Signatures from Downgradable Affine MACs
Masahito Ishizaka, Shinsaku Kiyomoto
Public-key cryptography
Affine message authentication code (AMAC) (CRYPTO'14) is a group-based MAC with a specific algebraic structure. Downgradable AMAC (DAMAC) (CT-RSA'19) is an AMAC with a functionality that we can downgrade a message with an authentication tag while retaining validity of the tag. In this paper, we revisit DAMAC for two independent applications, namely downgradable identity-based signatures (DIBS) and trapdoor sanitizable signatures (TSS) (ACNS'08). DIBS are the digital signature analogue of...
Toward a Fully Secure Authenticated Encryption Scheme From a Pseudorandom Permutation (Full Version)
Wonseok Choi, Byeonghak Lee, Jooyoung Lee, Yeongmin Lee
Secret-key cryptography
In this paper, we propose a new block cipher-based authenticated encryption scheme, dubbed the Synthetic Counter with Masking~(SCM) mode. SCM follows the NSIV paradigm proposed by Peyrin and Seurin~(CRYPTO 2016), where a keyed hash function accepts a nonce N with associated data and a message, yielding an authentication tag T, and then the message is encrypted by a counter-like mode using both T and N. Here we move one step further by encrypting nonces; in the encryption part, the inputs to...
One-time Traceable Ring Signatures
Alessandra Scafuro, Bihan Zhang
Foundations
A ring signature allows a party to sign messages anonymously on behalf of a group, which is called ring. Traceable ring signatures are a variant of ring signatures that limits the anonymity guarantees, enforcing that a member can sign anonymously at most one message per tag. Namely, if a party signs two different messages for the same tag, it will be de-anomymized. This property is very useful in decentralized platforms to allow members to anonymously endorse statements in a...
The Boneh-Katz Transformation, Revisited: Pseudorandom/Obliviously-Samplable PKE from Lattices and Codes and Its Application
Keita Xagawa
Public-key cryptography
The Boneh-Katz transformation (CT-RSA 2005) converts a selectively-secure identity/tag-based encryption scheme into a public-key encryption scheme secure against chosen-ciphertext attacks. We show that if the underlying primitives are pseudorandom, then the public-key encryption scheme obtained by the Boneh-Katz transformation is also pseudorandom. A similar result holds for oblivious sampleability (Canetti and Fischlin (CRYPTO 2001)).
As applications, we can construct
* pseudorandom and...
AOT: Anonymization by Oblivious Transfer
Farid Javani, Alan T. Sherman
Cryptographic protocols
We introduce AOT, an anonymous communication system based on mix network architecture that uses oblivious transfer (OT) to deliver messages. Using OT to deliver messages helps AOT resist blending (n−1) attacks and helps AOT preserve receiver anonymity, even if a covert adversary controls all nodes in AOT. AOT comprises three levels of nodes, where nodes at each level perform a different function and can scale horizontally. The sender encrypts their payload and a tag, derived from a...
Security of COFB against Chosen Ciphertext Attacks
Mustafa Khairallah
Secret-key cryptography
COFB is a lightweight Authenticated Encryption with Associated Data (AEAD) mode based on block ciphers.
It was proposed in CHES 2017 and is the basis for GIFT-COFB, a finalist in the NIST lightweight standardization project.
It comes with provable security results that guarantee its security up to the birthday
bound in the nonce-respecting model. However, the designers offer multiple versions of the analysis with different details and the implications of attacks against the scheme are not...
Verified Multiple-Time Signature Scheme from One-Time Signatures and Timestamping
Denis Firsov, Henri Lakk, Ahto Truu
Cryptographic protocols
Buldas, Laanoja, and Truu designed a family of server-assisted digital
signature schemes (BLT signatures) built around cryptographic
timestamping and forward-resistant tag systems. The original
constructions had either expensive key generation phase or stateful
client-side computations.
In this paper, we construct a stateless tag system with efficient key
generation from one-time signature schemes. We prove that the proposed
tag system is forward-resistant and when combined with...
Leakage Resilient Value Comparison With Application to Message Authentication
Christoph Dobraunig, Bart Mennink
Side-channel attacks are a threat to secrets stored on a device, especially if an adversary has physical access to the device. As an effect of this, countermeasures against such attacks for cryptographic algorithms are a well-researched topic. In this work, we deviate from the study of cryptographic algorithms and instead focus on the side-channel protection of a much more basic operation, the comparison of a known attacker-controlled value with a secret one. Comparisons sensitive to...
Revisiting Updatable Encryption: Controlled Forward Security, Constructions and a Puncturable Perspective
Daniel Slamanig, Christoph Striecks
Public-key cryptography
Updatable encryption (UE) allows a third party to periodically rotate encryption keys from one epoch to another without the need to download, decrypt, re-encrypt and upload already encrypted data by a client. Updating those outsourced ciphertexts is carried out via the use of so-called update tokens which in turn are generated during key rotation and can be sent (publicly) to the third party. The arguably most efficient variant of UE is ciphertext-independent UE as the key rotation does not...
\(\chi\)perbp: a Cloud-based Lightweight Mutual Authentication Protocol
Morteza Adeli, Nasour Bagheri, Sadegh Sadeghi, Saru Kumari
Cryptographic protocols
Alongside the development of cloud computing and Internet of Things(IoT), cloud-based RFID is receiving more attention nowadays.
Cloud-based RFID system is specifically developed to providing real-time data that can be fed to the cloud for easy access and instant data interpretation.
Security and privacy of constrained devices in these systems is a challenging issue for many applications. To deal with this problem, we propose \(\chi\)perbp, a lightweight authentication protocol based on...
Gladius: LWR based efficient hybrid public key encryption with distributed decryption
Kelong Cong, Daniele Cozzo, Varun Maram, Nigel P. Smart
Cryptographic protocols
Standard hybrid encryption schemes based on the KEM-DEM framework are hard to implement efficiently in a distributed manner whilst maintaining the CCA security property of the scheme. This is because the DEM needs to be decrypted under the key encapsulated by the KEM, before the whole ciphertext is declared valid. In this paper we present a new variant of the KEM-DEM framework, closely related to Tag-KEMs, which sidesteps this issue. We then present a post-quantum KEM for this framework...
Combining Montgomery Multiplication with Tag Tracing for the Pollard's Rho Algorithm in Prime Order Fields
Madhurima Mukhopadhyay, Palash Sarkar
Foundations
In this paper, we show how to apply Montgomery multiplication to the tag tracing variant of the
Pollard's rho algorithm applied to prime order fields. This combines the advantages of tag tracing with
those of Montgomery multiplication. In particular, compared to the previous version of tag tracing,
the use of Montgomery multiplication entirely eliminates costly modular reductions and replaces these
with much more efficient divisions by a suitable power of two.
Revisiting the Security of DbHtS MACs: Beyond-Birthday-Bound in the Multi-User Setting
Yaobin Shen, Lei Wang, Dawu Gu, Jian Weng
Secret-key cryptography
Double-block Hash-then-Sum (DbHtS) MACs are a class of MACs that aim for achieving beyond-birthday-bound security, including SUM-ECBC, PMAC\_Plus, 3kf9 and LightMAC_Plus. Recently Datta et al. (FSE'19), and then Kim et al. (Eurocrypt'20) prove that DbHtS constructions are secure beyond the birthday bound in the single-user setting. However, by a generic reduction, their results degrade to (or even worse than) the birthday bound in the multi-user setting.
In this work, we revisit the...
Proofs of non-Supermajority: the missing link for two-phase BFT with responsive view-change and linear complexity
Christophe Levrat, Matthieu Rambaud
Applications
We consider leader-based Byzantine state machine replication, a.k.a. "BFT", under partial synchrony. We provide a generic solution enabling to match simultaneously, for the first time, three arguably gold standards of BFT: in two phases, with a responsive view change and a linear complexity per view.
It is based on a new threshold primitive, which we call Proofs of non-Supermajority (or PnS for short). A PnS system enables players, each with an input number, to report their input to a...
Secure Cloud Auditing with Efficient Ownership Transfer (Full Version)
Jun Shen, Fuchun Guo, Xiaofeng Chen, Willy Susilo
Cloud auditing with ownership transfer is a provable data possession scheme meeting verifiability and transferability simultaneously. In particular, not only cloud data can be transferred to other cloud clients, but also tags for integrity verification can be transferred to new data owners. More concretely, it requires that tags belonging to the old owner can be transformed into that of the new owner by replacing the secret key for tag generation while verifiability still remains. We found...
The MAGIC Mode for Simultaneously Supporting Encryption, Message Authentication and Error Correction
Michael Kounavis, David Durham, Sergej Deutsch, Krystian Matusiewicz, David Wheeler
Foundations
We present MAGIC, a mode for authenticated encryption that simultaneously supports encryption, message authentication and error correction, all with the same code. In MAGIC, the same code employed for cryptographic integrity is also the parity used for error correction. To correct errors, MAGIC employs the Galois Hash transformation, which due to its bit linearity can perform corrections in a similar way as other codes do (e.g., Reed Solomon). To provide a cryptographically strong MAC, MAGIC...
Interactive Aggregate Message Authentication Equipped with Detecting Functionality from Adaptive Group Testing
Shingo Sato, Junji Shikata
Secret-key cryptography
In this paper, we propose a formal security model and a construction methodology of interactive aggregate message authentication with detecting functionality (IAMD). The IAMD is an interactive aggregate MAC protocol which can identify invalid messages with a small amount of tag-size. Several aggregate MAC schemes that can specify invalid messages has been proposed so far by using non-adaptive group testing in the prior work. In this paper, we utilize adaptive group testing to construct IAMD...
Black-Box Non-Interactive Non-Malleable Commitments
Rachit Garg, Dakshita Khurana, George Lu, Brent Waters
Cryptographic protocols
There has been recent exciting progress on building non-interactive non-malleable commitments from judicious assumptions. All proposed approaches proceed in two steps. First, obtain simple "base'' commitment schemes for very small tag/identity spaces based on a various sub-exponential hardness assumptions. Next, assuming sub-exponential non-interactive witness indistinguishable proofs (NIWIs), and variants of keyless collision resistant hash functions, construct non-interactive compilers...
Improved Security Analysis for Nonce-based Enhanced Hash-then-Mask MACs
Wonseok Choi, Byeonghak Lee, Yeongmin Lee, Jooyoung Lee
Secret-key cryptography
In this paper, we prove that the nonce-based enhanced hash-then-mask MAC ($\mathsf{nEHtM}$) is secure up to $2^{\frac{3n}{4}}$ MAC queries and $2^n$ verification queries (ignoring logarithmic factors) as long as the number of faulty queries $\mu$ is below $2^\frac{3n}{8}$, significantly improving the previous bound by Dutta et al. Even when $\mu$ goes beyond $2^{\frac{3n}{8}}$, $\mathsf{nEHtM}$ enjoys graceful degradation of security.
The second result is to prove the security of PRF-based...
Cryptanalysis of the permutation based algorithm SpoC
Liliya Kraleva, Raluca Posteuca, Vincent Rijmen
Secret-key cryptography
In this paper we present an analysis of the SpoC cipher, a second round candidate of the NIST Lightweight Crypto Standardization process. First we present a differential analysis on the sLiSCP-light permutation, a core element of SpoC. Then we propose a series of attacks on both versions of SpoC, namely round-reduced differential tag forgery and message recovery attacks, as well as a time-memory trade-off key-recovery attack on the full round version of Spoc-64. Finally, we present an...
The Exact Security of PMAC with Three Powering-Up Masks
Yusuke Naito
Secret-key cryptography
PMAC is a rate-1, parallelizable, block-cipher-based message authentication code (MAC), proposed by Black and Rogaway (EUROCRYPT 2002). Improving the security bound is a main research topic for PMAC. In particular, showing a tight bound is the primary goal of the research, since Luykx et al.'s paper (EUROCRYPT 2016). Regarding the pseudo-random-function (PRF) security of PMAC, a collision of the hash function, or the difference between a random permutation and a random function offers the...
Looking at the NIST Lightweight Candidates from a Masking Point-of-View
Lauren De Meyer
Secret-key cryptography
Cryptographic primitives have been designed to be secure against mathematical attacks in a black-box model. Such primitives can be implemented in a way that they are also secure against physical attacks, in a grey-box model. One of the most popular techniques for this purpose is masking. The increased security always comes with a high price tag in terms of implementation cost. In this work, we look at how the traditional design principles of symmetric primitives can be at odds with the...
Rotational Cryptanalysis on MAC Algorithm Chaskey
Liliya Kraleva, Tomer Ashur, Vincent Rijmen
Secret-key cryptography
In this paper we analyse the algorithm Chaskey - a lightweight MAC algorithm for 32-bit micro controllers - with respect to rotational cryptanalysis. We perform a related-key attack over Chaskey and find a distinguisher by using rotational probabilities. Having a message $m$ we can forge and present a valid tag for some message under a related key with probability $2^{-57}$ for 8 rounds and $2^{-86}$ for all 12 rounds of the permutation for keys in a defined weak-key class. This attack can...
2020/312
Last updated: 2021-05-05
Arcturus: efficient proofs for confidential transactions
Sarang Noether
Applications
Confidential transactions are used in distributed digital assets to demonstrate the balance of values hidden in commitments, while retaining signer ambiguity. Previous work describes a signer-ambiguous proof of knowledge of the opening of commitments to zero at the same index across multiple public commitment sets and the evaluation of a verifiable random function used as a linking tag, and uses this to build a linkable ring signature called Triptych that can be used as a building block for...
MCU intrinsic group features for component authentication
Frank Schuhmacher
Foundations
We provide a solution for the authentication of a component, accessory, smart card or tag by a main device via challenge-response-tests of two MCU intrinsic features: Progression in the execution of test programs (measured in processor clocks) and peripheral feedback to internal stimulation. The main device will be called challenger and the other device responder. Our solution requires that the authentic responders are characterized by a dedicated MCU model and a common responder ID...
Efficient Side-Channel Secure Message Authentication with Better Bounds
Chun Guo, François-Xavier Standaert, Weijia Wang, Yu Yu
Secret-key cryptography
We investigate constructing message authentication schemes from symmetric cryptographic primitives, with the goal of achieving security when most intermediate values during tag computation and verification are leaked (i.e., mode-level leakage-resilience). Existing efficient proposals typically follow the plain Hash-then-MAC paradigm $T=MAC_K(H(M))$. When the domain of the MAC function $MAC_K$ is $\{0,1\}^{128}$, e.g., when instantiated with the AES, forgery is possible within time $2^{64}$...
Strong Authenticity with Leakage under Weak and Falsifiable Physical Assumptions
Francesco Berti, Chun Guo, Olivier Pereira, Thomas Peters, François-Xavier Standaert
Secret-key cryptography
Authenticity can be compromised by information leaked via side-channels (e.g., power consumption). Examples of attacks include direct key recoveries and attacks against the tag verification which may lead to forgeries. At FSE 2018, Berti et al. described two authenticated encryption schemes which provide authenticity assuming a “leak-free implementation” of a Tweakable Block Cipher (TBC). Precisely, security is guaranteed even if all the intermediate computations of the target implementation...
A Subset Fault Analysis of ASCON
Priyanka Joshi, Bodhisatwa Mazumdar
Secret-key cryptography
ASCON is an authenticated encryption, selected as the first choice for a lightweight use case in the CAESAR competition in February 2019. In this work, we investigate vulnerabilities of ASCON against fault analysis. We observe that the use of 128-bit random nonce makes it resistant against many cryptanalysis techniques like differential, linear, etc. and their variants. However, XORing the key just before releasing the tag T (a public value) creates a trivial attack path. Also, the S-Box...
Variants of Wegman-Carter Message Authentication Code Supporting Variable Tag Lengths
Sebati Ghosh, Palash Sarkar
Secret-key cryptography
In this work, we study message authentication code (MAC) schemes supporting variable tag
lengths. We provide a formalisation of such a scheme. Several variants of the classical Wegman-
Carter MAC scheme are considered. Most of these are shown to be insecure by pointing out
detailed attacks. One of these schemes is highlighted and proved to be secure. We further build
on this scheme to obtain single-key variable tag length MAC schemes utilising either a stream
cipher or a short-output...
A New Secure and Efficient Ownership Transfer Protocol based on Quadric Residue and Homomorphic Encryption
Farokhlagha Moazami, Masoumeh Safkhani
Cryptographic protocols
In systems equipped with radio frequency identification (RFID) technology, several security concerns may arise when the ownership of a tag should be transferred from one owner to another, e.g., the confidentiality of information related to the old owner or the new owner. Therefore, this transfer is usually done via a security protocol called the ownership transfer protocol. If the ownership of several things together transmitted from one owner to another during a single session, the protocol...
2019/970
Last updated: 2019-09-02
Puncturable Signatures and Applications in Proof-of-Stake Blockchain Protocol
Xinyu Li, Jing Xu, Xiong Fan, Yuchen Wang, Zhenfeng Zhang
Applications
Proof-of-stake (PoS) blockchain protocols are emerging as one of the most promising alternative to the energy-consuming proof-of-work protocols. However, one particularly critical threat in the PoS setting is the well-known long-range attacks caused by secret key leakage (LRSL attack). Specifically, an adversary can attempt to corrupt the secret keys corresponding to accounts possessing substantial stake at some past moment such that double-spend or erase past transactions, violating the...
A Practical Forgery Attack on Lilliput-AE
Orr Dunkelman, Nathan Keller, Eran Lambooij, Yu Sasaki
Secret-key cryptography
Lilliput-AE is a tweakable block cipher submitted as a candidate to the NIST lightweight cryptography standardization process. It is based upon the lightweight block cipher Lilliput, whose cryptanalysis so far suggests that it has a large security margin.
In this note we present an extremely efficient forgery attack on Lilliput-AE: Given a single arbitrary message of length about 2^36 bytes, we can instantly produce another valid message that leads to the same tag, along with the...
On Designing Lightweight RFID Security Protocols for Medical IoT
Masoumeh Safkhani, Ygal Bendavid, Samad Rostampour, Nasour Bagheri
Cryptographic protocols
Recently, in IEEE Transactions on Industrial Informatics, Fan et al. proposed a lightweight RFID protocol which has been suggested to be employed for protecting the Medical Privacy in an IoT system. However, the protocol has trivial flaws, as it is shown recently by Aghili et al., in Future Generation Computer Systems. Aghili et al. also proposed an improved version of the protocol, based on the similar designing paradigm, called SecLAP. Although the protocol's designers claimed full...
Cryptanalysis of an Ultra lightweight Authentication Scheme based on Permutation Matrix Encryption for Internet of Vehicles
Morteza Adeli, Nasour Bagheri
Cryptographic protocols
Internet of Things (IoT) has various applications such as healthcare, supply chain, agriculture, etc. Using the Internet of Vehicles(IoV) to control traffic of the cities is one of the IoT applications to construct smart cities. Recently Fan et al. proposed an authentication protocol to provide security of the IoV networks. They claimed that their scheme is secure and can resist against various known attacks. In this paper, we analyze more deeply the proposed scheme and show that their...
Privacy of Stateful RFID Systems with Constant Tag Identifiers
Cristian Hristea, Ferucio Laurentiu Tiplea
Cryptographic protocols
There is a major interest in designing RFID schemes based on symmetric-key cryptography and ensuring efficient tag identification. These requirements taken together often lead to a decrease in the degree of privacy provided by the scheme.
This issue, as we know, has been treated in an ad-hoc manner so far.
In this paper, we introduce the class of stateful RFID schemes with constant tag identifiers, that ensure tag identification in no more than logarithmic time. In order to study their...
Design of Anonymous Endorsement System in Hyperledger Fabric
Subhra Mazumdar, Sushmita Ruj
Applications
Permissioned Blockchain has become quite popular with enterprises forming consortium since it prioritizes trust over privacy. One of the popular platforms for distributed ledger solution, Hyperledger Fabric, requires a transaction to be endorsed or approved by a group of special members known as endorsers before undergoing validation. To endorse a transaction, an endorser mentions its identity along with the signature so that it can be verified later. However, for certain transactions,...
A New Approach to Constructing Digital Signature Schemes (Extended Paper)
Ahto Buldas, Denis Firsov, Risto Laanoja, Henri Lakk, Ahto Truu
Cryptographic protocols
A new hash-based, server-supported digital signature scheme was proposed recently. We decompose the concept into forward-resistant tags and a generic cryptographic time-stamping service. Based on the decomposition, we propose more tag constructions which allow efficient digital signature schemes with interesting properties to be built. In particular, the new schemes are more suitable for use in personal signing devices, such as smart cards, which are used infrequently. We define the...
2019/612
Last updated: 2023-05-16
Simulation-Extractable SNARKs Revisited
Helger Lipmaa
Cryptographic protocols
The most efficient SNARKs (e.g., Groth, 2016) have a brittle and difficult-to-verify knowledge-soundness proof in the generic model, which makes it nontrivial to modify such SNARKs to, e.g., satisfy simulation-extractability or to implement some other language instead of QAP (Quadratic Arithmetic Program). We propose knowledge-sound and non-black-box tag-based strong any-simulation-extractable ($\tagSASE$) subversion-zero knowledge SNARKs for QAP that by design have a relatively simple...
ZOCB and ZOTR: Tweakable Blockcipher Modes for Authenticated Encryption with Full Absorption
Zhenzhen Bao, Jian Guo, Tetsu Iwata, Kazuhiko Minematsu
Secret-key cryptography
We define ZOCB and ZOTR for nonce-based authenticated encryption with associated data, and analyze their provable security. These schemes use a tweakable blockcipher (TBC) as the underlying primitive, and fully utilize its input to process a plaintext and associated data (AD). This property is commonly referred to as full absorption, and this has been explored for schemes based on a permutation or a pseudorandom function (PRF). Our schemes improve the efficiency of TBC-based counterparts of...
Security of the Suffix Keyed Sponge
Christoph Dobraunig, Bart Mennink
Secret-key cryptography
We formalize and analyze the general suffix keyed sponge construction, a pseudorandom function built on top of a cryptographic permutation. The construction hashes its data using the (keyless) sponge construction, transforms part of the state using the secret key, and generates the tag from the output of a final permutation call. In its simplest form, if the key and tag size are at most the rate of the sponge, one can see the suffix keyed sponge as a simple sponge function evaluation whose...
HMAKE: Legacy-Compliant Multi-factor Authenticated Key Exchange from Historical Data
Chenglu Jin, Zheng Yang, Sridhar Adepu, Jianying Zhou
Cryptographic protocols
In this paper, we introduce two lightweight historical data based multi-factor authenticated key exchange (HMAKE) protocols in the random oracle model. Our HMAKE protocols use a symmetric secret key, as their first authentication factor, together with their second authentication factor, historical data exchanged between the two parties in the past, and the third authentication factor, a set of secret tags associated with the historical data, to establish a secure communication channel...
Forgery Attack on SNEIKEN
Mustafa Khairallah
Secret-key cryptography
This document includes a collision/forgery attack against SNEIKEN128/192/256,
where every message with more than 128 bytes of associated data can be converted
into another message with different associated data and the same ciphertext/tag.
The attack is a direct application of the probability 1 differential of the SNEIK
permutation found by Léo Perrin in [Per19]. We verify the attack using the reference
implementation of SNEIKEN128 provided by the designers, providing an example of
such collisions.
Efficient Message Authentication Codes with Combinatorial Group Testing
Kazuhiko Minematsu
Secret-key cryptography
Message authentication code, MAC for short, is a symmetric-key cryptographic function for authenticity. A standard MAC verification only tells whether the message is valid or invalid, and thus we can not identify which part is corrupted in case of invalid message.
In this paper we study a class of MAC functions that enables to identify the part of corruption, which we call group testing MAC (GTM). This can be seen as an application of a classical (non-adaptive) combinatorial group testing to...
A Traceable Ring Signature Scheme based on Coding Theory
Pedro Branco, Paulo Mateus
Cryptographic protocols
Traceable ring signatures are a variant of ring signatures which allows the identity of a user to be revealed, when it signs two different messages with respect to the same group of users. It has applications in e-voting and in cryptocurrencies, such as the well-known Monero. We propose the first traceable ring signature scheme whose security is based on the hardness of the Syndrome Decoding problem, a problem in coding theory which is conjectured to be unsolvable by both classical and...
Improved Lattice-based CCA2-Secure PKE in the Standard Model
Jiang Zhang, Yu Yu, Shuqin Fan, Zhenfeng Zhang
Public-key cryptography
Based on the identity-based encryption (IBE) from lattices by Agrawal et al. (Eurocrypt'10), Micciancio and Peikert (Eurocrypt'12) presented a CCA1-secure public-key encryption (PKE), which has the best known efficiency in the standard model and can be used to obtain a CCA2-secure PKE from lattices by using the generic BCHK transform (SIAM J. Comput., 2006) with a cost of introducing extra overheads to both computation and storage for the use of other primitives such as signatures and...
Privacy and Reader-first Authentication in Vaudenay's RFID Model with Temporary State Disclosure
Ferucio Laurentiu Tiplea, Cristian Hristea
Cryptographic protocols
Privacy and mutual authentication under corruption with temporary state disclosure are two significant requirements for real-life
applications of RFID schemes. No RFID scheme is known so far to meet these two requirements. In this paper we propose two practical RFID schemes that fill this gap. The first one achieves destructive privacy, while the second one narrow destructive privacy, in Vaudenay's model with temporary state disclosure. Both of them provide mutual (reader-first)...
Destructive Privacy and Mutual Authentication in Vaudenay's RFID Model
Cristian Hristea, Ferucio Laurentiu Tiplea
Cryptographic protocols
With the large scale adoption of the Radio Frequency Identification (RFID) technology, a variety of security and privacy risks need to be addressed. Arguably, the most general and used RFID security and privacy model is the one proposed by Vaudenay. It considers concurrency, corruption (with or without destruction) of tags, and the possibility to get the result of a protocol session on the reader side. Security in Vaudenay's model embraces two forms, unilateral (tag) authentication and...
Non-Interactive Non-Malleability from Quantum Supremacy
Yael Tauman Kalai, Dakshita Khurana
Cryptographic protocols
We construct non-interactive non-malleable commitments without setup in the plain model, under well-studied assumptions.
First, we construct non-interactive non-malleable commitments with respect to commitment for $\epsilon \log \log n$ tags for a small constant $\epsilon > 0$, under the following assumptions:
- Sub-exponential hardness of factoring or discrete log.
- Quantum sub-exponential hardness of learning with errors (LWE).
Second, as our key technical contribution, we introduce a...
Non-Malleable Codes Against Bounded Polynomial Time Tampering
Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, Huijia Lin, Tal Malkin
Foundations
We construct efficient non-malleable codes (NMC) that are (computationally) secure against tampering by functions computable in any fixed polynomial time. Our construction is in the plain (no-CRS) model and requires the assumptions that (1) $\mathbf{E}$ is hard for $\mathbf{NP}$ circuits of some exponential $2^{\beta n}$ ($\beta>0$) size (widely used in the derandomization literature), (2) sub-exponential trapdoor permutations exist, and (3) $\mathbf{P}$ certificates with sub-exponential...
Reconsidering Generic Composition: the Tag-then-Encrypt case
Francesco Berti, Olivier Pereira, Thomas Peters
Secret-key cryptography
Authenticated Encryption ($\mathsf{AE}$) achieves confidentiality and authenticity, the two most fundamental goals of cryptography, in a single scheme. A common strategy to obtain $\mathsf{AE}$ is to combine a Message Authentication Code $(\mathsf{MAC})$ and an encryption scheme, either nonce-based or $\mathsf{iv}$-based. Out of the 180 possible combinations, Namprempre et al.~[25] proved that 12 were secure, 164 insecure and 4 were left unresolved: A10, A11 and A12 which use an $\iv$-based...
Universal Forgery and Multiple Forgeries of MergeMAC and Generalized Constructions
Tetsu Iwata, Virginie Lallemand, Gregor Leander, Yu Sasaki
Secret-key cryptography
This article presents universal forgery and multiple forgeries against MergeMAC that has been recently proposed to fit scenarios where bandwidth is limited and where strict time constraints apply. MergeMAC divides an input message into two parts, $m\|\tilde{m}$, and its tag is computed by $\mathcal{F}( \mathcal{P}_1(m) \oplus \mathcal{P}_2(\tilde{m}) )$, where $\mathcal{P}_1$ and $\mathcal{P}_2$ are PRFs and $\mathcal{F}$ is a public function. The tag size is 64 bits. The designers claim...
Bernstein Bound on WCS is Tight - Repairing Luykx-Preneel Optimal Forgeries
Mridul Nandi
In Eurocrypt 2018, Luykx and Preneel described hash-key-recovery and forgery attacks against polynomial hash based Wegman-Carter-Shoup (WCS) authenticators. Their attacks require $2^{n/2}$ message-tag pairs and recover hash-key with probability about $1.34 \times 2^{-n}$ where $n$ is the bit-size of the hash-key. Bernstein in Eurocrypt 2005 had provided an upper bound (known as Bernstein bound) of the maximum forgery advantages.
The bound says that all adversaries making $O(2^{n/2})$ queries...
Cryptanalysis of MORUS
Tomer Ashur, Maria Eichlseder, Martin M. Lauridsen, Gaëtan Leurent, Brice Minaud, Yann Rotella, Yu Sasaki, Benoît Viguier
Secret-key cryptography
MORUS is a high-performance authenticated encryption algorithm submitted to the CAESAR competition, and recently selected as a finalist.There are three versions of MORUS: MORUS-640 with a 128-bit key, and MORUS-1280 with 128-bit or 256-bit keys. For all versions the security claim for confidentiality matches the key size.In this paper, we analyze the components of this algorithm (initialization, state update and tag generation), and report several results.
As our main result, we present a...
Non-adaptive Group-Testing Aggregate MAC Scheme
Shoichi Hirose, Junji Shikata
Secret-key cryptography
This paper applies non-adaptive group testing to aggregate message
authentication code (MAC) and introduces non-adaptive group-testing
aggregate MAC.
After formalization of its syntax and security requirements,
simple and generic construction is presented, which can be applied to
any aggregate MAC scheme formalized by Katz and Lindell in 2008.
Then, two instantioations of the construction is presented.
One is based on the aggregate MAC scheme by Katz and Lindell
and uses addition for tag...
Message-locked Encryption with File Update
Suyash Kandele, Souradyuti Paul
Cryptographic protocols
Message-locked encryption (MLE) (formalized by Bellare, Keelveedhi and Ristenpart, 2013) is an important cryptographic primitive that supports deduplication in the cloud. Updatable block-level message-locked encryption (UMLE) (formalized by Zhao and Chow, 2017) adds the update functionality to the MLE. In this paper, we formalize and extensively study a new cryptographic primitive file-updatable message-locked encryption (FMLE). FMLE can be viewed as a generalization of the UMLE, in the...
DAWG: A Defense Against Cache Timing Attacks in Speculative Execution Processors
Vladimir Kiriansky, Ilia Lebedev, Saman Amarasinghe, Srinivas Devadas, Joel Emer
Foundations
Software side channel attacks have become a serious concern with the recent rash of attacks on speculative processor architectures. Most attacks that have been demonstrated exploit the cache tag state as their exfiltration channel. While many existing defense mechanisms that can be implemented solely in software have been proposed, these mechanisms appear to patch specific attacks, and can be circumvented. In this paper, we propose minimal modifications to hardware to defend against a broad...
Security Analysis of Fan et al. Lightweight RFID Authentication Protocol for Privacy Protection in IoT
Seyed Farhad Aghili, Hamid Mala
Cryptographic protocols
The designers of Radio-Frequency IDentification (RFID) systems have a challenging task for proposing secure mutual authentication protocols for Internet of Things (IoT) applications. Recently, Fan et al. proposed a new lightweight RFID mutual authentication protocol in the journal of IEEE Transactions on Industrial Informatics. They claimed that their protocol meets necessary security properties for RFID systems and can be applied for IoT. In this paper, we analyze
the security of this...
Weak-Unforgeable Tags for Secure Supply Chain Management
Marten van Dijk, Chenglu Jin, Hoda Maleki, Phuong Ha Nguyen, Reza Rahaeimehr
Foundations
Given the value of imported counterfeit and pirated goods, the need for secure supply chain management is pertinent. Maleki et al. (HOST 2017) propose a new management scheme based on RFID tags (with 2-3K bits NVM) which, if compared to other schemes, is competitive on several performance and security metrics. Its main idea is to have each RFID tag stores its reader events in its own NVM while moving through the supply chain. In order to bind a tag's identity to each event such that an...
An ongoing research challenge in symmetric cryptography is to design an authenticated encryption (AE) with a commitment to the secret key or preferably to the entire context. One way to achieve this is to use a transform on an existing AE scheme, if possible with no output length expansion. At EUROCRYPT'22, Bellare and Hoang proposed the HtE transform, which lifts key-commitment to context-commitment. In the same year at ESORICS'22, Chan and Rogaway proposed the CTX transform, which works on...
Robust message authentication codes (MACs) and authenticated encryption (AE) schemes that provide authenticity in the presence of side-channel leakage are essential primitives. These constructions often rely on primitives designed for strong leakage protection, among others including the use of strong-unpredictable (tweakable) block-ciphers. This paper extends the strong-unpredictability security definition to the versatile and new forkcipher primitive. We show how to construct secure and...
We propose a new wide encryption (WE) mode of operation that satisfies robust authenticated encryption (RAE) and committing security with minimum ciphertext expansion. WE is attracting much attention in the last few years, and its advantage includes RAE security that provides robustness against wide range of misuses, combined with the encode-then-encipher (EtE) construction. Unfortunately, WE-based EtE does not provide good committing security, and there is a recent constant-time CMT-4...
In this work, we present various hardware implementations for the lightweight cipher ASCON, which was recently selected as the winner of the NIST organized Lightweight Cryptography (LWC) competition. We cover encryption + tag generation and decryption + tag verification for the ASCON AEAD and also the ASCON hash function. On top of the usual (unprotected) implementation, we present side-channel protection (threshold countermeasure) and triplication/majority-based fault protection. To the...
In this paper, we present a new efficient stand-alone MAC construct based on processing using the FSM part of the stream cipher family SNOW, which in turn uses the AES round function. It offers a combination of very high speed in software and hardware with a truncatable tag. Three concrete versions of SMAC are proposed with different security levels, although other use cases are also possible. For example, SMAC can be combined with an external ciphering engine in AEAD mode. Every design...
The Ascon cipher suite has recently become the preferred standard in the NIST Lightweight Cryptography standardization process. Despite its prominence, the initial dedicated security analysis for the Ascon mode was conducted quite recently. This analysis demonstrated that the Ascon AEAD mode offers superior security compared to the generic Duplex mode, but it was limited to a specific scenario: single-user nonce-respecting, with a capacity strictly larger than the key size. In this paper, we...
Ciphertext-independent updatable encryption (UE) allows to rotate encryption keys and update ciphertexts via a token without the need to first download the ciphertexts. Although, syntactically, UE is a symmetric-key primitive, ciphertext-independent UE with forward secrecy and post-compromise security is known to imply public-key encryption (Alamati, Montgomery and Patranabis, CRYPTO 2019). Constructing post-quantum secure UE turns out to be a difficult task. While lattices offer the...
Authenticated Encryption with Associated Data (AEAD) is a trend in applied cryptography because it combine confidentiality, integrity, and authentication into one algorithm and is more efficient than using block ciphers and hash functions separately. The Ascon algorithm, as the winner in both the CAESAR competition and the NIST LwC competition, will soon become the AEAD standard for protecting the Internet of Things and micro devices with limited computing resources. We propose a partial...
The main goal of this work is to construct authenticated encryption (AE) that is both committing and leakage-resilient. As a first approach for this we consider generic composition as a well-known method for constructing AE schemes. While the leakage resilience of generic composition schemes has already been analyzed by Barwell et al. (AC'17), for committing security this is not the case. We fill this gap by providing a separate analysis of the generic composition paradigms with respect to...
The size of the authentication tag represents a significant overhead for applications that are limited by bandwidth or memory. Hence, some authenticated encryption designs have a smaller tag than the required privacy level, which was also suggested by the NIST lightweight cryptography standardization project. In the ToSC 2022, two papers have raised questions about the IND-CCA security of AEAD schemes in this situation. These papers show that (a) online AE cannot provide IND-CCA security...
Aggregation of message authentication codes (MACs) is a proven and efficient method to preserve valuable bandwidth in resource-constrained environments: Instead of appending a long authentication tag to each message, the integrity protection of multiple messages is aggregated into a single tag. However, while such aggregation saves bandwidth, a single lost message typically means that authentication information for multiple messages cannot be verified anymore. With the significant increase...
We show that the Nikooghadam-Shahriari-Saeidi authentication and key agreement scheme [J. Inf. Secur. Appl., 76, 103523 (2023)] cannot resist impersonation attack, not as claimed. An adversary can impersonate the RFID reader to cheat the RFID tag. The drawback results from its simple secret key invoking mechanism. We also find it seems difficult to revise the scheme due to the inherent flaw.
Secure Multiparty Computation (MPC) protocols enable secure evaluation of a circuit by several parties, even in the presence of an adversary who maliciously corrupts all but one of the parties. These MPC protocols are constructed using the well-known secret-sharing-based paradigm (SPDZ and SPD$\mathbb{Z}_{2^k}$), where the protocols ensure security against a malicious adversary by computing Message Authentication Code (MAC) tags on the input shares and then evaluating the circuit with these...
Various message authentication codes (MACs), including HMAC-Streebog and Streebog-K, are based on the keyless hash function Streebog. Under the assumption that the compression function of Streebog is resistant to the related key attacks, the security proofs of these algorithms were recently presented at CTCrypt 2022. We carefully detail the resources of the adversary in the related key settings, revisit the proof, and obtain tight security bounds. Let $n$ be the bit length of the hash...
Recently, the FinTracer algorithm was introduced as a versatile framework for detecting economic crime typologies in a privacy-preserving fashion. Under the hood, FinTracer stores its data in a structure known as the ``FinTracer tag’’. One limitation of FinTracer tags, however, is that because their underlying cryptographic implementation relies on additive semi-homomorphic encryption, all the system's oblivious computations on tag data are linear in their input ciphertexts. This allows a...
Efficiently and securely removing encrypted redundant data with cross-user in the cloud is challenging. Convergent Encryption (CE) is difficult to resist dictionary attacks for its deterministic tag. Server-aided mechanism is against such attacks while it may exist collusion. Focus on multimedia data, this paper proposes an efficient and secure fuzzy deduplication system without any additional servers. We also propose a notion of preverification of label consistency to compensate for the...
Searchable Symmetric Encryption (SSE) supports efficient keyword searches over encrypted outsourced document collections while minimizing information leakage. All practically efficient SSE schemes supporting conjunctive queries rely crucially on quantum-broken cryptographic assumptions (such as discrete-log hard groups) to achieve compact storage and fast query processing. On the other hand, quantum-safe SSE schemes based on purely symmetric-key crypto-primitives either do not support...
Updatable encryption is a useful primitive that enables key rotation for storing data on an untrusted storage provider without the leaking anything about the plaintext or the key. In this work, we make two contributions. Firstly, we extend updatable encryption to the public-key setting, providing its security model and three different efficient constructions. Using a public-key updatable encryption scheme, a user can receive messages directly in the cloud from multiple senders without...
The Ascon cipher suite, offering both authenticated encryption with associated data (AEAD) and hashing functionality, has recently emerged as the winner of the NIST Lightweight Cryptography (LwC) standardization process. The AEAD schemes within Ascon, namely Ascon-128 and Ascon-128a, have also been previously selected as the preferred lightweight authenticated encryption solutions in the CAESAR competition. In this paper, we present a tight and comprehensive security analysis of the Ascon...
Chameleon hash (CH) is a trapdoor hash function. Generally it is hard to find collisions, but with the help of a trapdoor, finding collisions becomes easy. CH plays an important role in converting a conventional blockchain to a redactable one. However, most of existing CH schemes are too weak to support redactable blockchains. The currently known CH schemes serving for redactable blockchains have the best security of so-called ``full collision resistance (f-CR)'', but they are built either...
The notion of witness encryption introduced by Garg et al. (STOC'13) allows to encrypt a message under a statement $x$ from some NP-language $\mathcal{L}$ with associated relation $(x,w) \in \mathcal{R}$, where decryption can be carried out with the corresponding witness $w$. Unfortunately, known constructions for general-purpose witness encryption rely on strong assumptions, and are mostly of theoretical interest. To address these shortcomings, Goyal et al. (PKC'22) recently introduced a...
In this note, we identify a minor flaw in the design of the XOCB mode, presented at Eurocrypt '23. This vulnerability enables trivial tag forgeries and arises from the padding applied to messages. We examine the security proof and pinpoint the presence of the flaw within it. Furthermore, we propose a simple fix for this issue, drawing upon the features of OCB3, and discuss the implications of this modification on the proof of security.
Various matrix relations widely appeared in data-intensive computations, as a result their zero-knowledge proofs/arguments (ZKP/ZKA) are naturally required in large-scale private computing applications. In the first part of this paper, we concretely establish efficient commit-and-proof zero-knowledge arguments for linear matrix relation AU = B and bilinear relation UTQV = Y over the residue ring Zm with logarithmic message complexity. We take a direct, matrix-oriented (rather than...
We investigate the security of the NIST Lightweight Crypto Competition’s Finalists against side-channel attacks. We start with a mode-level analysis that allows us to put forward three candidates (As- con, ISAP and Romulus-T) that stand out for their leakage properties and do not require a uniform protection of all their computations thanks to (expensive) implementation-level countermeasures. We then implement these finalists and evaluate their respective performances. Our results confirm...
We propose a novel variant of functional encryption which supports ciphertext updates, dubbed ciphertext-updatable functional encryption (CUFE). Such a feature further broadens the practical applicability of the functional-encryption paradigm and allows for fine-grained access control even after a ciphertext is generated. Updating ciphertexts is carried out via so-called update tokens which a dedicated party can use to convert ciphertexts. However, allowing update tokens requires some care...
Chakraborty, Prabhakaran, and Wichs (PKC'20) recently introduced a new tag-based variant of lossy trapdoor functions, termed cumulatively all-lossy-but-one trapdoor functions (CALBO-TDFs). Informally, CALBO-TDFs allow defining a public tag-based function with a (computationally hidden) special tag, such that the function is lossy for all tags except when the special secret tag is used. In the latter case, the function becomes injective and efficiently invertible using a secret trapdoor. This...
Recent advances in quantum computing are increasingly jeopardizing the security of cryptosystems currently in widespread use, such as RSA or elliptic-curve signatures. To address this threat, researchers and standardization institutes have accelerated the transition to quantum-resistant cryptosystems, collectively known as Post-Quantum Cryptography (PQC). These PQC schemes present new challenges due to their larger memory and computational footprints and their higher chance of latent...
Multi-input functional encryption, MIFE, is a powerful generalization of functional encryption that allows computation on encrypted data coming from multiple different data sources. In a recent work, Agrawal, Goyal, and Tomida (CRYPTO 2021) constructed MIFE for the class of quadratic functions. This was the first MIFE construction from bilinear maps that went beyond inner product computation. We advance the state-of-the-art in MIFE, and propose new constructions with stronger security and...
Both multi-user PRFs and sponge-based constructions have generated a lot of research interest lately. Dedicated analyses for multi-user security have improved the bounds a long distance from the early generic bounds obtained through hybrid arguments, yet the bounds generally don't allow the number of users to be more than birthday-bound in key-size. Similarly, known sponge constructions suffer from being only birthday-bound secure in terms of their capacity. We present in this paper...
Security against side-channels and faults is a must for the deployment of embedded cryptography. A wide body of research has investigated solutions to secure implementations against these attacks at different abstraction levels. Yet, to a large extent, current solutions focus on one or the other threat. In this paper, we initiate a mode-level study of cryptographic primitives that can ensure security in a (new and practically-motivated) adversarial model combining leakage and faults. Our...
TinyJambu is one of the finalists in the NIST lightweight cryptography competition. It has undergone extensive analysis in the recent years as both the keyed permutation as well as the mode are new designs. In this paper we present a related-key forgery attackon the updated TinyJambu scheme with 256- and 192-bit keys. We introduce a high probability related-key differential attack were the differences are only introduced into the key state. Therefore, the characteristic is applicable to the...
We obtain a black-box construction of non-interactive CCA commitments against non-uniform adversaries. This makes black-box use of an appropriate base commitment scheme for small tag spaces, variants of sub-exponential hinting PRG (Koppula and Waters, Crypto 2019) and variants of keyless sub-exponentially collision-resistant hash function with security against non-uniform adversaries (Bitansky, Kalai and Paneth, STOC 2018 and Bitansky and Lin, TCC 2018). All prior works on non-interactive...
We consider the streaming variant of the Bounded Storage Model (BSM), where the honest parties can stream large amounts of data to each other, while only maintaining a small memory of size $n$. The adversary also operates as a streaming algorithm, but has a much larger memory size $m \gg n$. The goal is to construct unconditionally secure cryptographic schemes in the BSM, and prior works did so for symmetric-key encryption, key agreement, oblivious transfer and multiparty computation. In...
Implantable Medical Devices (IMDs) are widely deployed today and often use wireless communication. Establishing a secure communication channel to these devices is vital, however, also challenging in practice. To address this issue, numerous researchers have proposed IMD key exchange protocols, in particular ones that leverage an Out-Of-Band (OOB) channel such as audio, vibration and physiological signals. These solutions have advantages over traditional key exchange, e.g.,...
We propose a short signature scheme under the ring-SIS assumption in the standard model. Specifically, by revisiting an existing construction [Ducas and Micciancio, CRYPTO 2014], we demonstrate lattice-based signatures with improved reduction loss. As far as we know, there are no ways to use multiple tags in the signature simulation of security proof in the lattice tag-based signatures. We address the tag-collision possibility in the lattice setting, which improves reduction loss. Our scheme...
TrCBC is a variant of CBC-MAC which appeared in Information Processing Letters, 112(7):302-307, 2012. The authors claimed TrCBC to be a secure message authentication code (MAC) with some interesting properties. If TrCBC is instantiated with a block cipher with block length n, then it requires ⌈λ/n⌉ block cipher calls for authenticating a λ-bit message and requires a single key, which is the block cipher key. The authors state that TrCBC can have tag lengths of size less than n/2. We show...
SKINNY-AEAD is one of the second-round candidates of the Lightweight Cryptography Standardization project held by NIST. SKINNY-AEAD M1 is the primary member of six SKINNY-AEAD schemes, while SKINNY-AEAD M3 is another member with a small tag. In the design document, only security analyses of their underlying primitive SKINNY-128-384 are provided. Besides, there are no valid third-party analyses on SKINNY-AEAD M1/M3 according to our knowledge. Therefore, this paper focuses on constructing the...
Panther is a sponge-based lightweight authenticated encryption scheme published at Indocrypt 2021. Its round function is based on four Nonlinear Feedback Shift Registers (NFSRs). We show here that it is possible to fully recover the secret key of the construction by using a single known plaintext-ciphertext pair and with minimal computational ressources. Furthermore, we show that in a known ciphertext setting an attacker is able with the knowledge of a single ciphertext to decrypt all...
Elliptic Curve Cryptography (ECC) has been popularly used in RFID authentication protocols to efficiently overcome many security and privacy issues. Even if the strong cryptography primitives of ECC are utilised in the authentication protocols, the schemes are alas far from providing security and privacy properties as desired level. In this paper, we analyze four up-to-minute ECC based RFID authentication schemes proposed by Gasbi et al., Benssalah et al., Kumar et al., and Agrahari and...
We study the provable security claims of two NIST Lightweight Cryptography (LwC) finalists, GIFT-COFB and Photon-Beetle, and present several attacks whose complexities contradict their claimed bounds in their final round specification documents. For GIFT-COFB, we show an attack using $q_e$ encryption queries and no decryption query to break privacy (IND-CPA). The success probability is $O(q_e/2^{n/2})$ for $n$-bit block while the claimed bound contains $O(q^2_e/2^{n})$. This positively...
Encryption satisfying CCA2 security is commonly known to be unnecessarily strong for realizing secure channels. Moreover, CCA2 constructions in the standard model are far from being competitive practical alternatives to constructions via random oracle. A promising research area to alleviate this problem are weaker security notions—like IND-RCCA secure encryption or IND-atag-wCCA secure tag-based encryption—which are still able to facilitate secure message transfer (SMT) via authenticated...
Leakage-resilient authenticated encryption (AE) schemes received considerable attention during the previous decade. Two core security models of bounded and unbounded leakage have evolved, where the latter has been motivated in a very detailed and practice-oriented manner. In that setting, designers often build schemes based on (tweakable) block ciphers due to the small state size, such as the recent two-pass AE scheme TEDT from TCHES 1/2020. TEDT is interesting due to its high security...
Affine message authentication code (AMAC) (CRYPTO'14) is a group-based MAC with a specific algebraic structure. Downgradable AMAC (DAMAC) (CT-RSA'19) is an AMAC with a functionality that we can downgrade a message with an authentication tag while retaining validity of the tag. In this paper, we revisit DAMAC for two independent applications, namely downgradable identity-based signatures (DIBS) and trapdoor sanitizable signatures (TSS) (ACNS'08). DIBS are the digital signature analogue of...
In this paper, we propose a new block cipher-based authenticated encryption scheme, dubbed the Synthetic Counter with Masking~(SCM) mode. SCM follows the NSIV paradigm proposed by Peyrin and Seurin~(CRYPTO 2016), where a keyed hash function accepts a nonce N with associated data and a message, yielding an authentication tag T, and then the message is encrypted by a counter-like mode using both T and N. Here we move one step further by encrypting nonces; in the encryption part, the inputs to...
A ring signature allows a party to sign messages anonymously on behalf of a group, which is called ring. Traceable ring signatures are a variant of ring signatures that limits the anonymity guarantees, enforcing that a member can sign anonymously at most one message per tag. Namely, if a party signs two different messages for the same tag, it will be de-anomymized. This property is very useful in decentralized platforms to allow members to anonymously endorse statements in a...
The Boneh-Katz transformation (CT-RSA 2005) converts a selectively-secure identity/tag-based encryption scheme into a public-key encryption scheme secure against chosen-ciphertext attacks. We show that if the underlying primitives are pseudorandom, then the public-key encryption scheme obtained by the Boneh-Katz transformation is also pseudorandom. A similar result holds for oblivious sampleability (Canetti and Fischlin (CRYPTO 2001)). As applications, we can construct * pseudorandom and...
We introduce AOT, an anonymous communication system based on mix network architecture that uses oblivious transfer (OT) to deliver messages. Using OT to deliver messages helps AOT resist blending (n−1) attacks and helps AOT preserve receiver anonymity, even if a covert adversary controls all nodes in AOT. AOT comprises three levels of nodes, where nodes at each level perform a different function and can scale horizontally. The sender encrypts their payload and a tag, derived from a...
COFB is a lightweight Authenticated Encryption with Associated Data (AEAD) mode based on block ciphers. It was proposed in CHES 2017 and is the basis for GIFT-COFB, a finalist in the NIST lightweight standardization project. It comes with provable security results that guarantee its security up to the birthday bound in the nonce-respecting model. However, the designers offer multiple versions of the analysis with different details and the implications of attacks against the scheme are not...
Buldas, Laanoja, and Truu designed a family of server-assisted digital signature schemes (BLT signatures) built around cryptographic timestamping and forward-resistant tag systems. The original constructions had either expensive key generation phase or stateful client-side computations. In this paper, we construct a stateless tag system with efficient key generation from one-time signature schemes. We prove that the proposed tag system is forward-resistant and when combined with...
Side-channel attacks are a threat to secrets stored on a device, especially if an adversary has physical access to the device. As an effect of this, countermeasures against such attacks for cryptographic algorithms are a well-researched topic. In this work, we deviate from the study of cryptographic algorithms and instead focus on the side-channel protection of a much more basic operation, the comparison of a known attacker-controlled value with a secret one. Comparisons sensitive to...
Updatable encryption (UE) allows a third party to periodically rotate encryption keys from one epoch to another without the need to download, decrypt, re-encrypt and upload already encrypted data by a client. Updating those outsourced ciphertexts is carried out via the use of so-called update tokens which in turn are generated during key rotation and can be sent (publicly) to the third party. The arguably most efficient variant of UE is ciphertext-independent UE as the key rotation does not...
Alongside the development of cloud computing and Internet of Things(IoT), cloud-based RFID is receiving more attention nowadays. Cloud-based RFID system is specifically developed to providing real-time data that can be fed to the cloud for easy access and instant data interpretation. Security and privacy of constrained devices in these systems is a challenging issue for many applications. To deal with this problem, we propose \(\chi\)perbp, a lightweight authentication protocol based on...
Standard hybrid encryption schemes based on the KEM-DEM framework are hard to implement efficiently in a distributed manner whilst maintaining the CCA security property of the scheme. This is because the DEM needs to be decrypted under the key encapsulated by the KEM, before the whole ciphertext is declared valid. In this paper we present a new variant of the KEM-DEM framework, closely related to Tag-KEMs, which sidesteps this issue. We then present a post-quantum KEM for this framework...
In this paper, we show how to apply Montgomery multiplication to the tag tracing variant of the Pollard's rho algorithm applied to prime order fields. This combines the advantages of tag tracing with those of Montgomery multiplication. In particular, compared to the previous version of tag tracing, the use of Montgomery multiplication entirely eliminates costly modular reductions and replaces these with much more efficient divisions by a suitable power of two.
Double-block Hash-then-Sum (DbHtS) MACs are a class of MACs that aim for achieving beyond-birthday-bound security, including SUM-ECBC, PMAC\_Plus, 3kf9 and LightMAC_Plus. Recently Datta et al. (FSE'19), and then Kim et al. (Eurocrypt'20) prove that DbHtS constructions are secure beyond the birthday bound in the single-user setting. However, by a generic reduction, their results degrade to (or even worse than) the birthday bound in the multi-user setting. In this work, we revisit the...
We consider leader-based Byzantine state machine replication, a.k.a. "BFT", under partial synchrony. We provide a generic solution enabling to match simultaneously, for the first time, three arguably gold standards of BFT: in two phases, with a responsive view change and a linear complexity per view. It is based on a new threshold primitive, which we call Proofs of non-Supermajority (or PnS for short). A PnS system enables players, each with an input number, to report their input to a...
Cloud auditing with ownership transfer is a provable data possession scheme meeting verifiability and transferability simultaneously. In particular, not only cloud data can be transferred to other cloud clients, but also tags for integrity verification can be transferred to new data owners. More concretely, it requires that tags belonging to the old owner can be transformed into that of the new owner by replacing the secret key for tag generation while verifiability still remains. We found...
We present MAGIC, a mode for authenticated encryption that simultaneously supports encryption, message authentication and error correction, all with the same code. In MAGIC, the same code employed for cryptographic integrity is also the parity used for error correction. To correct errors, MAGIC employs the Galois Hash transformation, which due to its bit linearity can perform corrections in a similar way as other codes do (e.g., Reed Solomon). To provide a cryptographically strong MAC, MAGIC...
In this paper, we propose a formal security model and a construction methodology of interactive aggregate message authentication with detecting functionality (IAMD). The IAMD is an interactive aggregate MAC protocol which can identify invalid messages with a small amount of tag-size. Several aggregate MAC schemes that can specify invalid messages has been proposed so far by using non-adaptive group testing in the prior work. In this paper, we utilize adaptive group testing to construct IAMD...
There has been recent exciting progress on building non-interactive non-malleable commitments from judicious assumptions. All proposed approaches proceed in two steps. First, obtain simple "base'' commitment schemes for very small tag/identity spaces based on a various sub-exponential hardness assumptions. Next, assuming sub-exponential non-interactive witness indistinguishable proofs (NIWIs), and variants of keyless collision resistant hash functions, construct non-interactive compilers...
In this paper, we prove that the nonce-based enhanced hash-then-mask MAC ($\mathsf{nEHtM}$) is secure up to $2^{\frac{3n}{4}}$ MAC queries and $2^n$ verification queries (ignoring logarithmic factors) as long as the number of faulty queries $\mu$ is below $2^\frac{3n}{8}$, significantly improving the previous bound by Dutta et al. Even when $\mu$ goes beyond $2^{\frac{3n}{8}}$, $\mathsf{nEHtM}$ enjoys graceful degradation of security. The second result is to prove the security of PRF-based...
In this paper we present an analysis of the SpoC cipher, a second round candidate of the NIST Lightweight Crypto Standardization process. First we present a differential analysis on the sLiSCP-light permutation, a core element of SpoC. Then we propose a series of attacks on both versions of SpoC, namely round-reduced differential tag forgery and message recovery attacks, as well as a time-memory trade-off key-recovery attack on the full round version of Spoc-64. Finally, we present an...
PMAC is a rate-1, parallelizable, block-cipher-based message authentication code (MAC), proposed by Black and Rogaway (EUROCRYPT 2002). Improving the security bound is a main research topic for PMAC. In particular, showing a tight bound is the primary goal of the research, since Luykx et al.'s paper (EUROCRYPT 2016). Regarding the pseudo-random-function (PRF) security of PMAC, a collision of the hash function, or the difference between a random permutation and a random function offers the...
Cryptographic primitives have been designed to be secure against mathematical attacks in a black-box model. Such primitives can be implemented in a way that they are also secure against physical attacks, in a grey-box model. One of the most popular techniques for this purpose is masking. The increased security always comes with a high price tag in terms of implementation cost. In this work, we look at how the traditional design principles of symmetric primitives can be at odds with the...
In this paper we analyse the algorithm Chaskey - a lightweight MAC algorithm for 32-bit micro controllers - with respect to rotational cryptanalysis. We perform a related-key attack over Chaskey and find a distinguisher by using rotational probabilities. Having a message $m$ we can forge and present a valid tag for some message under a related key with probability $2^{-57}$ for 8 rounds and $2^{-86}$ for all 12 rounds of the permutation for keys in a defined weak-key class. This attack can...
Confidential transactions are used in distributed digital assets to demonstrate the balance of values hidden in commitments, while retaining signer ambiguity. Previous work describes a signer-ambiguous proof of knowledge of the opening of commitments to zero at the same index across multiple public commitment sets and the evaluation of a verifiable random function used as a linking tag, and uses this to build a linkable ring signature called Triptych that can be used as a building block for...
We provide a solution for the authentication of a component, accessory, smart card or tag by a main device via challenge-response-tests of two MCU intrinsic features: Progression in the execution of test programs (measured in processor clocks) and peripheral feedback to internal stimulation. The main device will be called challenger and the other device responder. Our solution requires that the authentic responders are characterized by a dedicated MCU model and a common responder ID...
We investigate constructing message authentication schemes from symmetric cryptographic primitives, with the goal of achieving security when most intermediate values during tag computation and verification are leaked (i.e., mode-level leakage-resilience). Existing efficient proposals typically follow the plain Hash-then-MAC paradigm $T=MAC_K(H(M))$. When the domain of the MAC function $MAC_K$ is $\{0,1\}^{128}$, e.g., when instantiated with the AES, forgery is possible within time $2^{64}$...
Authenticity can be compromised by information leaked via side-channels (e.g., power consumption). Examples of attacks include direct key recoveries and attacks against the tag verification which may lead to forgeries. At FSE 2018, Berti et al. described two authenticated encryption schemes which provide authenticity assuming a “leak-free implementation” of a Tweakable Block Cipher (TBC). Precisely, security is guaranteed even if all the intermediate computations of the target implementation...
ASCON is an authenticated encryption, selected as the first choice for a lightweight use case in the CAESAR competition in February 2019. In this work, we investigate vulnerabilities of ASCON against fault analysis. We observe that the use of 128-bit random nonce makes it resistant against many cryptanalysis techniques like differential, linear, etc. and their variants. However, XORing the key just before releasing the tag T (a public value) creates a trivial attack path. Also, the S-Box...
In this work, we study message authentication code (MAC) schemes supporting variable tag lengths. We provide a formalisation of such a scheme. Several variants of the classical Wegman- Carter MAC scheme are considered. Most of these are shown to be insecure by pointing out detailed attacks. One of these schemes is highlighted and proved to be secure. We further build on this scheme to obtain single-key variable tag length MAC schemes utilising either a stream cipher or a short-output...
In systems equipped with radio frequency identification (RFID) technology, several security concerns may arise when the ownership of a tag should be transferred from one owner to another, e.g., the confidentiality of information related to the old owner or the new owner. Therefore, this transfer is usually done via a security protocol called the ownership transfer protocol. If the ownership of several things together transmitted from one owner to another during a single session, the protocol...
Proof-of-stake (PoS) blockchain protocols are emerging as one of the most promising alternative to the energy-consuming proof-of-work protocols. However, one particularly critical threat in the PoS setting is the well-known long-range attacks caused by secret key leakage (LRSL attack). Specifically, an adversary can attempt to corrupt the secret keys corresponding to accounts possessing substantial stake at some past moment such that double-spend or erase past transactions, violating the...
Lilliput-AE is a tweakable block cipher submitted as a candidate to the NIST lightweight cryptography standardization process. It is based upon the lightweight block cipher Lilliput, whose cryptanalysis so far suggests that it has a large security margin. In this note we present an extremely efficient forgery attack on Lilliput-AE: Given a single arbitrary message of length about 2^36 bytes, we can instantly produce another valid message that leads to the same tag, along with the...
Recently, in IEEE Transactions on Industrial Informatics, Fan et al. proposed a lightweight RFID protocol which has been suggested to be employed for protecting the Medical Privacy in an IoT system. However, the protocol has trivial flaws, as it is shown recently by Aghili et al., in Future Generation Computer Systems. Aghili et al. also proposed an improved version of the protocol, based on the similar designing paradigm, called SecLAP. Although the protocol's designers claimed full...
Internet of Things (IoT) has various applications such as healthcare, supply chain, agriculture, etc. Using the Internet of Vehicles(IoV) to control traffic of the cities is one of the IoT applications to construct smart cities. Recently Fan et al. proposed an authentication protocol to provide security of the IoV networks. They claimed that their scheme is secure and can resist against various known attacks. In this paper, we analyze more deeply the proposed scheme and show that their...
There is a major interest in designing RFID schemes based on symmetric-key cryptography and ensuring efficient tag identification. These requirements taken together often lead to a decrease in the degree of privacy provided by the scheme. This issue, as we know, has been treated in an ad-hoc manner so far. In this paper, we introduce the class of stateful RFID schemes with constant tag identifiers, that ensure tag identification in no more than logarithmic time. In order to study their...
Permissioned Blockchain has become quite popular with enterprises forming consortium since it prioritizes trust over privacy. One of the popular platforms for distributed ledger solution, Hyperledger Fabric, requires a transaction to be endorsed or approved by a group of special members known as endorsers before undergoing validation. To endorse a transaction, an endorser mentions its identity along with the signature so that it can be verified later. However, for certain transactions,...
A new hash-based, server-supported digital signature scheme was proposed recently. We decompose the concept into forward-resistant tags and a generic cryptographic time-stamping service. Based on the decomposition, we propose more tag constructions which allow efficient digital signature schemes with interesting properties to be built. In particular, the new schemes are more suitable for use in personal signing devices, such as smart cards, which are used infrequently. We define the...
The most efficient SNARKs (e.g., Groth, 2016) have a brittle and difficult-to-verify knowledge-soundness proof in the generic model, which makes it nontrivial to modify such SNARKs to, e.g., satisfy simulation-extractability or to implement some other language instead of QAP (Quadratic Arithmetic Program). We propose knowledge-sound and non-black-box tag-based strong any-simulation-extractable ($\tagSASE$) subversion-zero knowledge SNARKs for QAP that by design have a relatively simple...
We define ZOCB and ZOTR for nonce-based authenticated encryption with associated data, and analyze their provable security. These schemes use a tweakable blockcipher (TBC) as the underlying primitive, and fully utilize its input to process a plaintext and associated data (AD). This property is commonly referred to as full absorption, and this has been explored for schemes based on a permutation or a pseudorandom function (PRF). Our schemes improve the efficiency of TBC-based counterparts of...
We formalize and analyze the general suffix keyed sponge construction, a pseudorandom function built on top of a cryptographic permutation. The construction hashes its data using the (keyless) sponge construction, transforms part of the state using the secret key, and generates the tag from the output of a final permutation call. In its simplest form, if the key and tag size are at most the rate of the sponge, one can see the suffix keyed sponge as a simple sponge function evaluation whose...
In this paper, we introduce two lightweight historical data based multi-factor authenticated key exchange (HMAKE) protocols in the random oracle model. Our HMAKE protocols use a symmetric secret key, as their first authentication factor, together with their second authentication factor, historical data exchanged between the two parties in the past, and the third authentication factor, a set of secret tags associated with the historical data, to establish a secure communication channel...
This document includes a collision/forgery attack against SNEIKEN128/192/256, where every message with more than 128 bytes of associated data can be converted into another message with different associated data and the same ciphertext/tag. The attack is a direct application of the probability 1 differential of the SNEIK permutation found by Léo Perrin in [Per19]. We verify the attack using the reference implementation of SNEIKEN128 provided by the designers, providing an example of such collisions.
Message authentication code, MAC for short, is a symmetric-key cryptographic function for authenticity. A standard MAC verification only tells whether the message is valid or invalid, and thus we can not identify which part is corrupted in case of invalid message. In this paper we study a class of MAC functions that enables to identify the part of corruption, which we call group testing MAC (GTM). This can be seen as an application of a classical (non-adaptive) combinatorial group testing to...
Traceable ring signatures are a variant of ring signatures which allows the identity of a user to be revealed, when it signs two different messages with respect to the same group of users. It has applications in e-voting and in cryptocurrencies, such as the well-known Monero. We propose the first traceable ring signature scheme whose security is based on the hardness of the Syndrome Decoding problem, a problem in coding theory which is conjectured to be unsolvable by both classical and...
Based on the identity-based encryption (IBE) from lattices by Agrawal et al. (Eurocrypt'10), Micciancio and Peikert (Eurocrypt'12) presented a CCA1-secure public-key encryption (PKE), which has the best known efficiency in the standard model and can be used to obtain a CCA2-secure PKE from lattices by using the generic BCHK transform (SIAM J. Comput., 2006) with a cost of introducing extra overheads to both computation and storage for the use of other primitives such as signatures and...
Privacy and mutual authentication under corruption with temporary state disclosure are two significant requirements for real-life applications of RFID schemes. No RFID scheme is known so far to meet these two requirements. In this paper we propose two practical RFID schemes that fill this gap. The first one achieves destructive privacy, while the second one narrow destructive privacy, in Vaudenay's model with temporary state disclosure. Both of them provide mutual (reader-first)...
With the large scale adoption of the Radio Frequency Identification (RFID) technology, a variety of security and privacy risks need to be addressed. Arguably, the most general and used RFID security and privacy model is the one proposed by Vaudenay. It considers concurrency, corruption (with or without destruction) of tags, and the possibility to get the result of a protocol session on the reader side. Security in Vaudenay's model embraces two forms, unilateral (tag) authentication and...
We construct non-interactive non-malleable commitments without setup in the plain model, under well-studied assumptions. First, we construct non-interactive non-malleable commitments with respect to commitment for $\epsilon \log \log n$ tags for a small constant $\epsilon > 0$, under the following assumptions: - Sub-exponential hardness of factoring or discrete log. - Quantum sub-exponential hardness of learning with errors (LWE). Second, as our key technical contribution, we introduce a...
We construct efficient non-malleable codes (NMC) that are (computationally) secure against tampering by functions computable in any fixed polynomial time. Our construction is in the plain (no-CRS) model and requires the assumptions that (1) $\mathbf{E}$ is hard for $\mathbf{NP}$ circuits of some exponential $2^{\beta n}$ ($\beta>0$) size (widely used in the derandomization literature), (2) sub-exponential trapdoor permutations exist, and (3) $\mathbf{P}$ certificates with sub-exponential...
Authenticated Encryption ($\mathsf{AE}$) achieves confidentiality and authenticity, the two most fundamental goals of cryptography, in a single scheme. A common strategy to obtain $\mathsf{AE}$ is to combine a Message Authentication Code $(\mathsf{MAC})$ and an encryption scheme, either nonce-based or $\mathsf{iv}$-based. Out of the 180 possible combinations, Namprempre et al.~[25] proved that 12 were secure, 164 insecure and 4 were left unresolved: A10, A11 and A12 which use an $\iv$-based...
This article presents universal forgery and multiple forgeries against MergeMAC that has been recently proposed to fit scenarios where bandwidth is limited and where strict time constraints apply. MergeMAC divides an input message into two parts, $m\|\tilde{m}$, and its tag is computed by $\mathcal{F}( \mathcal{P}_1(m) \oplus \mathcal{P}_2(\tilde{m}) )$, where $\mathcal{P}_1$ and $\mathcal{P}_2$ are PRFs and $\mathcal{F}$ is a public function. The tag size is 64 bits. The designers claim...
In Eurocrypt 2018, Luykx and Preneel described hash-key-recovery and forgery attacks against polynomial hash based Wegman-Carter-Shoup (WCS) authenticators. Their attacks require $2^{n/2}$ message-tag pairs and recover hash-key with probability about $1.34 \times 2^{-n}$ where $n$ is the bit-size of the hash-key. Bernstein in Eurocrypt 2005 had provided an upper bound (known as Bernstein bound) of the maximum forgery advantages. The bound says that all adversaries making $O(2^{n/2})$ queries...
MORUS is a high-performance authenticated encryption algorithm submitted to the CAESAR competition, and recently selected as a finalist.There are three versions of MORUS: MORUS-640 with a 128-bit key, and MORUS-1280 with 128-bit or 256-bit keys. For all versions the security claim for confidentiality matches the key size.In this paper, we analyze the components of this algorithm (initialization, state update and tag generation), and report several results. As our main result, we present a...
This paper applies non-adaptive group testing to aggregate message authentication code (MAC) and introduces non-adaptive group-testing aggregate MAC. After formalization of its syntax and security requirements, simple and generic construction is presented, which can be applied to any aggregate MAC scheme formalized by Katz and Lindell in 2008. Then, two instantioations of the construction is presented. One is based on the aggregate MAC scheme by Katz and Lindell and uses addition for tag...
Message-locked encryption (MLE) (formalized by Bellare, Keelveedhi and Ristenpart, 2013) is an important cryptographic primitive that supports deduplication in the cloud. Updatable block-level message-locked encryption (UMLE) (formalized by Zhao and Chow, 2017) adds the update functionality to the MLE. In this paper, we formalize and extensively study a new cryptographic primitive file-updatable message-locked encryption (FMLE). FMLE can be viewed as a generalization of the UMLE, in the...
Software side channel attacks have become a serious concern with the recent rash of attacks on speculative processor architectures. Most attacks that have been demonstrated exploit the cache tag state as their exfiltration channel. While many existing defense mechanisms that can be implemented solely in software have been proposed, these mechanisms appear to patch specific attacks, and can be circumvented. In this paper, we propose minimal modifications to hardware to defend against a broad...
The designers of Radio-Frequency IDentification (RFID) systems have a challenging task for proposing secure mutual authentication protocols for Internet of Things (IoT) applications. Recently, Fan et al. proposed a new lightweight RFID mutual authentication protocol in the journal of IEEE Transactions on Industrial Informatics. They claimed that their protocol meets necessary security properties for RFID systems and can be applied for IoT. In this paper, we analyze the security of this...
Given the value of imported counterfeit and pirated goods, the need for secure supply chain management is pertinent. Maleki et al. (HOST 2017) propose a new management scheme based on RFID tags (with 2-3K bits NVM) which, if compared to other schemes, is competitive on several performance and security metrics. Its main idea is to have each RFID tag stores its reader events in its own NVM while moving through the supply chain. In order to bind a tag's identity to each event such that an...