Tue, 10 May 2022 08:21AM UTC
##### Distributed Shuffling in Adversarial Environments
###### Kasper Green Larsen, Maciej Obremski, Mark Simkin
foundations / Shuffling, Leader Election, Mix-Nets

We formalize and study the problem of distributed shuffling in adversarial environments. In this setting, there are $m$ shufflers that have access to a public bulletin board that stores a vector $(c_1, \dots, c_n)$ of re-randomizable commitments. The shufflers repeatedly read $k$ of the $n$ commitments, with $k$ potentially much smaller than $n$, and shuffle them. An adversary has the ability to initially corrupt and then track some of the commitments throughout the shuffles and can adaptively corrupt a bounded number of shufflers in every single round. The goal of the distributed shuffling protocol is to hide the output locations of commitments that are not corrupted by the adversary. We present and analyze a protocol that solves this problem with essentially optimal shuffling complexity. As an exemplary data point, our protocol can shuffle a list of length $n$ with shuffles of size $k$, where $k \in \Omega(\lg^2 n)$, in the presence of an adversary that can corrupt $4n/5$ many shufflers in each round and can corrupt $4n/5$ commitments in the input vector. Our $m$-party shuffling protocol with $m \in \Omega(n/k)$ terminates in $\mathcal{O}(\lg n)$ rounds. We provide numerical benchmarks that validate our theoretically proven guarantees and in fact show that the number of rounds is not just theoretically, but also concretely small. Our shuffling protocol can either improve efficiency or lead to more secure solutions in multiple research domains, such as the design of mix-nets, single secret leader election protocols, and electronic voting.

Tue, 10 May 2022 08:21AM UTC
##### Survey on the Effectiveness of DAPA-Related Attacks against Shift Register Based AEAD Schemes
###### Shivam Bhasin, Dirmanto Jap, Wei Cheng Ng, Siang Meng Sim
secret-key cryptography / Side-channel analysis, DAPA, LFSR, NFSR, Grain-128AEADv2, TinyJAMBU

-

Tue, 10 May 2022 08:22AM UTC
##### Orientations and cycles in supersingular isogeny graphs
###### Sarah Arpin, Mingjie Chen, Kristin E. Lauter, Renate Scheidler, Katherine E. Stange, Ha T. N. Tran
public-key cryptography / supersingular, isogeny, elliptic curve, orientation

The paper concerns several theoretical aspects of oriented supersingular l-isogeny volcanoes and their relationship to closed walks in the supersingular l-isogeny graph. Our main result is a bijection between the rims of the union of all oriented supersingular l-isogeny volcanoes over $\overline{\mathbb{F}}_p$ (up to conjugation of the orientations), and isogeny cycles (non-backtracking closed walks which are not powers of smaller walks) of the supersingular l-isogeny graph modulo p. The exact proof and statement of this bijection are made more intricate by special behaviours arising from extra automorphisms and the ramification of p in certain quadratic orders. We use the bijection to count isogeny cycles of given length in the supersingular l-isogeny graph exactly as a sum of class numbers, and also give an explicit upper bound by estimating the class numbers.

Tue, 10 May 2022 08:22AM UTC
##### Find the Bad Apples: An efficient method for perfect key recovery under imperfect SCA oracles – A case study of Kyber
###### Muyan Shen, Chi Cheng, Xiaohan Zhang, Qian Guo, Tao Jiang
public-key cryptography / Lattice-based cryptography; Side-channel attacks; Plaintext-checking oracle; NIST Post-Quantum cryptography standardization; Kyber; Key mismatch attacks

Side-channel resilience is a crucial feature when assessing whether a post-quantum cryptographic proposal is sufficiently mature to be deployed. In this paper, we propose a generic and efficient adaptive approach to improve the sample complexity (i.e., the required number of traces) of plaintext-checking (PC) oracle-based side-channel attacks (SCAs), a major class of key recovery chosen-ciphertext SCAs on lattice-based key encapsulation mechanisms. This new approach is preferable when the constructed PC oracle is imperfect, which is common in practice, and its basic idea is to design new detection codes that can determine erroneous positions in the initially recovered secret key. These secret entries are further corrected with a small number of additional traces. This work benefits from the generality of PC oracle and thus is applicable to various schemes and implementations. We instantiated the proposed generic attack framework on Kyber512 and fully implemented this attack instance. Through extensive computer simulations and also a real-world experiment with electromagnetic (EM) leakages from an ARM-Cortext-M4 platform, we demonstrated that the newly proposed attack could greatly improve the state-of-the-art in terms of the required number of traces. For instance, the new attack requires only 41% of the EM traces needed in a majority-voting attack in our experiments, where the raw oracle accuracy is fixed.

Tue, 10 May 2022 08:23AM UTC
##### FAPRIL: Towards Faster Privacy-Preserving Fingerprint-Based Localization
###### Christopher van der Beets, Raine Nieminen, Thomas Schneider
applications / fingerprint-based localization, indoor localization, location privacy, data privacy, secure two-party computation, smartphones

Fingerprinting is a commonly used technique to provide accurate localization for indoor areas, where global navigation satellite systems, such as GPS and Galileo, cannot function or are not precise enough. Although fingerprint-based indoor localization has gained wide popularity, existing solutions that preserve privacy either rely on non-colluding servers or have high communication which hinder deployment. In this work we present FAPRIL, a privacy-preserving indoor localization scheme, which takes advantage of the latest secure two-party computation protocol improvements. We can split our scheme into two parts: an input independent setup phase and an online phase. We concentrate on optimizing the online phase for mobile clients who run on a mobile data plan and observe that recurring operands allow to optimize the total communication overhead even further. Our observation can be generalized, e.g., to improve multiplication of Arithmetic secret shared matrices. We implement FAPRIL on mobile devices and our benchmarks over a simulated LTE network show that the online phase of a private localization takes under 0.15 seconds with less than 0.20 megabytes of communication even for large buildings. The setup phase, which can be pre-computed, depends heavily on the setting but stays in the range 0.28 - 4.14 seconds and 0.69 - 16.00 megabytes per localization query. The round complexity of FAPRIL is constant for both phases.

Tue, 10 May 2022 08:24AM UTC
##### Power Contracts: Provably Complete Power Leakage Models for Processors
###### Roderick Bloem, Barbara Gigerl, Marc Gourjon, Vedad Hadžić, Stefan Mangard, Robert Primas
foundations / Power Side-Channel, Leakage Model, Verification, Contract, Domain-Specific Language, Masking, Probing Security

The protection of cryptographic software implementations against power-analysis attacks is critical for applications in embedded systems. A commonly used algorithmic countermeasure against these attacks is masking, a secret-sharing scheme that splits a sensitive computation into computation on multiple random shares. In practice, the security of masking schemes relies on several assumptions that are often violated by microarchitectural side-effects of CPUs. Many past works address this problem by studying these leakage effects and building corresponding leakage models that can then be integrated into a software verification workflow. However, these models have only been derived empirically, putting the otherwise rigorous security statements made with verification in question. We solve this problem in two steps. First, we introduce a contract layer between the (CPU) hardware and the software that allows the specification of microarchitectural side-effects on masked software in an intuitive language. Second, we present a method for proving the correspondence between contracts and CPU netlists to ensure the completeness of the specified leakage models. Then, any further security proofs only need to happen between software and contract, which brings benefits such as reduced verification runtime, improved user experience, and the possibility of working with vendor-supplied contracts of CPUs whose design is not available on netlist-level due to IP restrictions. We apply our approach to the popular RISC-V IBEX core, provide a corresponding formally verified contract, and describe how this contract could be used to verify masked software implementations.

Tue, 10 May 2022 08:25AM UTC
##### AntMan: Interactive Zero-Knowledge Proofs with Sublinear Communication
###### Chenkai Weng, Kang Yang, Zhaomin Yang, Xiang Xie, Xiao Wang
cryptographic protocols / zero-knowledge proofs

Recent works on interactive zero-knowledge (ZK) protocols provide a new paradigm with high efficiency and scalability. However, these protocols suffer from high communication overhead, often linear to the circuit size. In this paper, we proposed two new ZK protocols with communication sublinear to the circuit size, while maintaining a similar level of computational efficiency. -- We designed a ZK protocol that can prove $B$ executions of any circuit $C$ in communication $O(B + |C|)$ field elements (with free addition gates), while the best prior work requires a communication of $O(B|C|)$ field elements. Our protocol is enabled by a new tool called as information-theoretic polynomial authentication code, which may be of independent interest. -- We developed an optimized implementation of this protocol which shows high practicality. For example, with $B=2048$, $|C|=2^{20}$, and under 50 Mbps bandwidth and 16 threads, QuickSilver, a state-of-the-art ZK protocol based on vector oblivious linear evaluation (VOLE), can only prove $0.78$ million MULT gates per second (mgps) and send one field element per gate; our protocol can prove $14$ mgps ($18\times$ improvement) and send $0.0064$ field elements per gate ($156\times$ improvement) under the same hardware configuration. -- Extending the above idea, we constructed a ZK protocol that can prove a single execution of any circuit $C$ in communication $O(|C|^{3/4})$. This is the first ZK protocol with sublinear communication for an arbitrary circuit in the VOLE-based ZK family.

Tue, 10 May 2022 08:25AM UTC
##### Improved MITM Cryptanalysis on Streebog
###### Jialiang Hua, Xiaoyang Dong, Siwei Sun, Zhiyu Zhang, Lei Hu, Xiaoyun Wang
secret-key cryptography / Preimage, MITM Attack, Streebog and MILP

At ASIACRYPT 2012, Sasaki et al. introduced the guess-and-determine approach to extend the meet-in-the-middle (MITM) preimage attack. At CRYPTO 2021, Dong et al. proposed a technique to derive the solution spaces of nonlinear constrained neutral words in the MITM preimage attack. In this paper, we try to combine these two techniques to further improve the MITM preimage attacks. Based on the previous MILP-based automatic tools for MITM attacks, we introduce new constraints due to the combination of guess-and-determine and nonlinearly constrained neutral words to build a new automatic model. As a proof of work, we apply it to the Russian national standard hash function Streebog, which is also an ISO standard. We find the first 8.5-round preimage attack on Streebog-512 compression function and the first 7.5-round preimage attack on Streebog-256 compression function. In addition, we give the 8.5-round preimage attack on Streebog-512 hash function. Our attacks extend the best previous attacks by one round. We also improve the time complexity of the 7.5-round preimage attack on Streebog-512 hash function and 6.5-round preimage attack on Streebog-256 hash function.

Tue, 10 May 2022 07:02PM UTC
##### On Seedless PRNGs and Premature Next
###### Sandro Coretti, Yevgeniy Dodis, Harish Karthikeyan, Noah Stephens-Davidowitz, Stefano Tessaro
foundations / Mathematical foundations of cryptography; Information-theoretic techniques; Pseudorandomness and derandomization; seedless PRNG; premature next; root PRNG

Pseudorandom number generators with input (PRNGs) are cryptographic algorithms that generate pseudorandom bits from accumulated entropic inputs (e.g., keystrokes, interrupt timings, etc.). This paper studies in particular PRNGs that are secure against premature next attacks (Kelsey et al., FSE '98), a class of attacks leveraging the fact that a PRNG may produce an output (which could be seen by an adversary!) before enough entropy has been accumulated. Practical designs adopt either unsound entropy-estimation methods to prevent such attacks (as in Linux's /dev/random) or sophisticated pool-based approaches as in Yarrow (MacOS/FreeBSD) and Fortuna (Windows). The only prior theoretical study of premature next attacks (Dodis et al., Algorithmica '17) considers either a seeded setting or assumes a constant entropy rate, and thus falls short of providing and validating practical designs. Assuming the availability of random seed is particularly problematic, first because this requires us to somehow generate a random seed without using our PRNG, but also because we must ensure that the entropy inputs to the PRNG remain independent of the seed. Indeed, all practical designs are seedless. However, prior works on seedless PRNGs (Coretti et al., CRYPTO '19; Dodis et al., ITC '21, CRYPTO'21) do not consider premature next attacks. The main goal of this paper is to investigate the feasibility of theoretically sound seedless PRNGs that are secure against premature next attacks. To this end, we make the following contributions: -- We prove that it is impossible to achieve seedless PRNGs that are secure against premature-next attacks, even in a rather weak model. Namely, the impossibility holds even when the entropic inputs to the PRNG are independent. In particular, our impossibility result holds in settings where seedless PRNGs are otherwise possible. -- Given the above impossibility result, we investigate whether existing seedless pool-based approaches meant to overcome premature next attacks in practical designs provide meaningful guarantees in certain settings. Specifically, we show the following. * We introduce a natural condition on the entropic input and prove that it implies security of the round-robin entropy accumulation PRNG used by Windows 10, called Fortuna. Intuitively, our condition requires the input entropy not to vary too wildly'' within a given round-robin round. * We prove that the root pool'' approach (also used in Windows 10) is secure for general entropy inputs, provided that the system's state is not compromised after system startup.

Thu, 12 May 2022 04:19AM UTC
##### FC1: A Powerful, Non-Deterministic, Symmetric Key Cipher
###### Michele Fabbrini
secret-key cryptography / symmetric key cipher, non-deterministic algorithm

In this paper we describe a symmetric key algorithm that offers an unprecedented grade of confidentiality. Based on the uniqueness of the modular multiplicative inverse of a positive integer a modulo n and on its computability in a polynomial time, this non-deterministic cipher can easily and quickly handle keys of millions or billions of bits that an attacker does not even know the length of. The algorithm’s primary key is the modulo, while the ciphertext is given by the concatenation of the modular inverse of blocks of plaintext whose length is randomly chosen within a predetermined range. In addition to the full specification, we present a working implementation of it in Julia Programming Language, accompanied by real examples of encryption and decryption.

Thu, 12 May 2022 10:12AM UTC
##### DeCAF: Decentralizable Continuous Group Key Agreement with Fast Healing
###### Joël Alwen, Benedikt Auerbach, Miguel Cueto Noval, Karen Klein, Guillermo Pascual-Perez, Krzysztof Pietrzak
cryptographic protocols / group messaging, CGKA, MLS

Continuous group key agreement (CGKA) allows a group of users to maintain a continuously updated shared key in an asynchronous setting where parties only come online sporadically and their messages are relayed by an untrusted server. CGKA captures the basic primitive underlying group messaging schemes. Current solutions including TreeKEM (Message Layer Security'' (MLS) IETF draft) cannot handle concurrent requests while retaining low communication complexity. The exception being CoCoA, which is concurrent while having extremely low communication complexity (in groups of size $n$ and for $m$ concurrent updates the communication per user is $\log(n)$, i.e., independent of $m$). The main downside of CoCoA is that in groups of size $n$, users might have to do up to $\log(n)$ update requests to the server to ensure their (potentially corrupted) key material has been refreshed. We present a new fast healing'' concurrent CGKA protocol, named DeCAF, where users will heal after at most $\log(t)$ requests, with $t$ being the number of corrupted users. Our new protocol is particularly interesting to realize decentralized group messaging, where protocol messages (add/remove/update) are being posted on a blockchain rather than sent to a server. In this setting, concurrency is crucial once requests are more frequent than blocks. Our new protocol significantly outperforms (the only alternative with sub-linear communication and PCS) CoCoA in this setting: it heals much faster ($\log(t)$ vs. $\log(n)$ rounds). The communication per round and user is $m\cdot\log(n)$, but in this setting -- where there is no server who can craft specific messages to users depending on their position in the tree -- CoCoA requires the same communication.