#iacr — Public Fediverse posts

M. Albrecht et al., "Four Attacks and a Proof for Telegram"¹

We study the use of symmetric cryptography in the MTProto 2.0 protocol, Telegram's equivalent of the TLS record protocol. We give positive and negative results. On the one hand, we formally and in detail model a slight variant of Telegram's "record protocol" and prove that it achieves security in a suitable bidirectional secure channel model, albeit under unstudied assumptions; this model itself advances the state-of-the-art for secure channels. On the other hand, we first motivate our modelling deviation from MTProto as deployed by giving two attacks – one of practical, one of theoretical interest – against MTProto without our modifications. We then also give a third attack exploiting timing side channels, of varying strength, in three official Telegram clients. On its own this attack is thwarted by the secrecy of salt and id fields that are established by Telegram's key exchange protocol. We chain the third attack with a fourth one against the implementation of the key exchange protocol on Telegram's servers. This fourth attack breaks the authentication properties of Telegram's key exchange, allowing a MitM attack. More mundanely, it also recovers the id field, reducing the cost of the plaintext recovery attack to guessing the 64-bit salt field. In totality, our results provide the first comprehensive study of MTProto's use of symmetric cryptography, as well as highlight weaknesses in its key exchange.

#IACR #ResearchPapers #Telegram #MTProto #ProvableSecurity #SecureMessaging #BiDirectionalChannels #SecurityAnalysis

__
¹ https://eprint.iacr.org/2023/469

C. Li et al., "SALSA PICANTE: a machine learning attack on LWE with binary secrets"¹

The Learning With Errors (LWE) problem is one of the major hard problems in post-quantum cryptography. For example, 1) the only Key Exchange Mechanism KEM standardized by NIST [14] is based on LWE; and 2) current publicly available Homomorphic Encryption (HE) libraries are based on LWE. NIST KEM schemes use random secrets, but homomorphic encryption schemes use binary or ternary secrets, for efficiency reasons. In particular, sparse binary secrets have been proposed, but not standardized [2], for HE.
Prior work SALSA [49] demonstrated a new machine learning attack on sparse binary secrets for the LWE problem in small dimensions (up to n = 128) and low Hamming weights (up to h = 4). However, this attack assumed access to millions of LWE samples, and was not scaled to higher Hamming weights or dimensions.
Our attack, PICANTE, reduces the number of samples required to just m = 4n samples. Moreover, it can recover secrets with much larger dimensions (up to 350) and Hamming weights (roughly n/10, or h = 33 for n = 300). To achieve this, we introduce a preprocessing step which allows us to generate the training data from a linear number of samples and changes the distribution of the training data to improve transformer training. We also improve the distinguisher/secret recovery methods of SALSA and introduce a novel cross-attention recovery mechanism which allows us to read-off the secret directly from the trained models.

#ResearchPapers #IACR #LWE #Cryptanalysis
__
¹ https://eprint.iacr.org/2023/340

M. Macchetti, "A Novel Related Nonce Attack for ECDSA"¹

We describe a new related nonce attack able to extract the
original signing key from a small collection of ECDSA signatures generated with weak PRNGs. Under suitable conditions on the modulo order
of the PRNG, we are able to attack linear, quadratic, cubic as well as
arbitrary degree recurrence relations (with unknown coefficients) with
few signatures and in negligible time. We also show that for any collection of randomly generated ECDSA nonces, there is one more nonce that
can be added following the implicit recurrence relation, and that would
allow retrieval of the private key; we exploit this fact to present a novel
rogue nonce attack against ECDSA. Up to our knowledge, this is the
first known attack exploiting generic and unknown high-degree algebraic
relations between nonces that do not require assumptions on the value
of single bits or bit sequences (e.g. prefixes and suffixes).

#IACR #ResearchPapers #ECDSA #NonceAttack #PRNG #Cryptanalysis
__
¹ https://eprint.iacr.org/2023/305

J. Yamaguchi et al., "Estimation of Shor's Circuit for 2048-bit Integers based on Quantum Simulator"¹

Evaluating exact computational resources necessary for factoring large integers by Shor algorithm using an ideal quantum computer is difficult because simplified circuits were used in past experiments, in which qubits and gates were reduced as much as possible by using the features of the integers, though 15 and 21 were factored on quantum computers. In this paper, we implement Shor algorithm for general composite numbers, and factored 96 RSA-type composite numbers up to 9-bit using a quantum computer simulator. In the largest case, N=511 was factored within 2 hours. Then, based on these experiments, we estimate the number of gates and the depth of Shor's quantum circuits for factoring 1024-bit and 2048-bit integers. In our estimation, Shor's quantum circuit for factoring 1024-bit integers requires 2.78×10^11 gates, and with depth 2.24×10^11, while 2.23×10^12 gates, and with depth 1.80×10^12 for 2048-bit integers.

#ResearchPapers #IACR #ShorAlgorithm #IntegerFactorisation #QuantumComputer #QuantumComputerSimulator

__
¹ https://eprint.iacr.org/2023/092

S. Mathialagan and N. Vafa, "MacORAMa: Optimal Oblivious RAM with Integrity"¹

Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (J. ACM '96), is a primitive that allows a client to perform RAM computations on an external database without revealing any information through the access pattern. For a database of size N, well-known lower bounds show that a multiplicative overhead of
Ω(log N) in the number of RAM queries is necessary assuming
O(1) client storage. A long sequence of works culminated in the asymptotically optimal construction of Asharov, Komargodski, Lin, and Shi (CRYPTO '21) with O(log⁡ N) worst-case overhead and O(1) client storage. However, this optimal ORAM construction is known to be secure only in the honest-but-curious setting, where an adversary is allowed to observe the access patterns but not modify the contents of the database. In the malicious setting, where an adversary is additionally allowed to tamper with the database, this construction and many others in fact become insecure.

In this work, we construct the first maliciously secure ORAM protocol with worst-case O(log N) overhead and O(1) client storage assuming one-way functions, which are also necessary. By the
Ω(log N) ORAM lower bound, our construction is asymptotically optimal. We can also interpret our construction as an online memory checker that matches the bandwidth of the best known online memory checkers while additionally hiding the access pattern. To achieve this, we intricately interleave the ORAM construction of Asharov et al. with online and offline memory checking techniques.

#ResearchPapers #IACR #OblivousRAM #ORAM #MemoryChecking

__
¹ https://eprint.iacr.org/2023/083

S. Mathialagan and N. Vafa, "MacORAMa: Optimal Oblivious RAM with Integrity"¹

Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (J. ACM '96), is a primitive that allows a client to perform RAM computations on an external database without revealing any information through the access pattern. For a database of size N, well-known lower bounds show that a multiplicative overhead of
Ω(log N) in the number of RAM queries is necessary assuming
O(1) client storage. A long sequence of works culminated in the asymptotically optimal construction of Asharov, Komargodski, Lin, and Shi (CRYPTO '21) with O(log⁡ N) worst-case overhead and O(1) client storage. However, this optimal ORAM construction is known to be secure only in the honest-but-curious setting, where an adversary is allowed to observe the access patterns but not modify the contents of the database. In the malicious setting, where an adversary is additionally allowed to tamper with the database, this construction and many others in fact become insecure.

In this work, we construct the first maliciously secure ORAM protocol with worst-case O(log N) overhead and O(1) client storage assuming one-way functions, which are also necessary. By the
Ω(log N) ORAM lower bound, our construction is asymptotically optimal. We can also interpret our construction as an online memory checker that matches the bandwidth of the best known online memory checkers while additionally hiding the access pattern. To achieve this, we intricately interleave the ORAM construction of Asharov et al. with online and offline memory checking techniques.

#ResearchPapers #IACR #OblivousRAM #ORAM #MemoryChecking

__
¹ https://eprint.iacr.org/2023/083

S. Mathialagan and N. Vafa, "MacORAMa: Optimal Oblivious RAM with Integrity"¹

Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (J. ACM '96), is a primitive that allows a client to perform RAM computations on an external database without revealing any information through the access pattern. For a database of size N, well-known lower bounds show that a multiplicative overhead of
Ω(log N) in the number of RAM queries is necessary assuming
O(1) client storage. A long sequence of works culminated in the asymptotically optimal construction of Asharov, Komargodski, Lin, and Shi (CRYPTO '21) with O(log⁡ N) worst-case overhead and O(1) client storage. However, this optimal ORAM construction is known to be secure only in the honest-but-curious setting, where an adversary is allowed to observe the access patterns but not modify the contents of the database. In the malicious setting, where an adversary is additionally allowed to tamper with the database, this construction and many others in fact become insecure.

In this work, we construct the first maliciously secure ORAM protocol with worst-case O(log N) overhead and O(1) client storage assuming one-way functions, which are also necessary. By the
Ω(log N) ORAM lower bound, our construction is asymptotically optimal. We can also interpret our construction as an online memory checker that matches the bandwidth of the best known online memory checkers while additionally hiding the access pattern. To achieve this, we intricately interleave the ORAM construction of Asharov et al. with online and offline memory checking techniques.

#ResearchPapers #IACR #OblivousRAM #ORAM #MemoryChecking

__
¹ https://eprint.iacr.org/2023/083

S. Mathialagan and N. Vafa, "MacORAMa: Optimal Oblivious RAM with Integrity"¹

Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (J. ACM '96), is a primitive that allows a client to perform RAM computations on an external database without revealing any information through the access pattern. For a database of size N, well-known lower bounds show that a multiplicative overhead of
Ω(log N) in the number of RAM queries is necessary assuming
O(1) client storage. A long sequence of works culminated in the asymptotically optimal construction of Asharov, Komargodski, Lin, and Shi (CRYPTO '21) with O(log⁡ N) worst-case overhead and O(1) client storage. However, this optimal ORAM construction is known to be secure only in the honest-but-curious setting, where an adversary is allowed to observe the access patterns but not modify the contents of the database. In the malicious setting, where an adversary is additionally allowed to tamper with the database, this construction and many others in fact become insecure.

In this work, we construct the first maliciously secure ORAM protocol with worst-case O(log N) overhead and O(1) client storage assuming one-way functions, which are also necessary. By the
Ω(log N) ORAM lower bound, our construction is asymptotically optimal. We can also interpret our construction as an online memory checker that matches the bandwidth of the best known online memory checkers while additionally hiding the access pattern. To achieve this, we intricately interleave the ORAM construction of Asharov et al. with online and offline memory checking techniques.

#ResearchPapers #IACR #OblivousRAM #ORAM #MemoryChecking

__
¹ https://eprint.iacr.org/2023/083

A. Genêt, "On Protecting SPHINCS+ Against Fault Attacks"¹

SPHINCS+ is a hash-based digital signature scheme that was selected by NIST in their post-quantum cryptography standardization process. The establishment of a universal forgery on the seminal scheme SPHINCS was shown to be feasible in practice by injecting a fault when the signing device constructs any non-top subtree. Ever since the attack has been made public, little effort was spent to protect the SPHINCS family against attacks by faults. This paper works in this direction in the context of SPHINCS+ and analyzes the current algorithms that aim to prevent fault-based forgeries.

First, the paper adapts the original attack to SPHINCS+ reinforced with randomized signing and extends the applicability of the attack to any combination of faulty and valid signatures. Considering the adaptation, the paper then presents a thorough analysis of the attack. In particular, the analysis shows that, with high probability, the security guarantees of SPHINCS+ significantly drop when a single random bit flip occurs anywhere in the signing procedure and that the resulting faulty signature cannot be detected with the verification procedure. The paper shows both in theory and experimentally that the countermeasures based on caching the intermediate W-OTS+s offer a marginally greater protection against unintentional faults, and that such countermeasures are circumvented with a tolerable number of queries in an active attack. Based on these results, the paper recommends real-world deployments of SPHINCS+ to implement redundancy checks.

#IACR #ResearchPapers #SPHINCS+ #FaultAttacks #PQSignatures

__
¹ https://eprint.iacr.org/2023/042

A. Vadapalli et al., "Duoram: A Bandwidth-Efficient Distributed ORAM for 2- and 3-Party Computation"¹

We design, analyze, and implement Duoram, a fast and bandwidth-efficient distributed ORAM protocol suitable for secure 2- and 3-party computation settings. Following Doerner and shelat's Floram construction (CCS 2017), Duoram leverages (2,2)-distributed point functions (DPFs) to represent PIR and PIR-writing queries compactly—but with a host of innovations that yield massive asymptotic reductions in communication cost and notable speedups in practice, even for modestly sized instances. Specifically, Duoram introduces a novel method for evaluating dot products of certain secret-shared vectors using communication that is only logarithmic in the vector length. As a result, for memories with n addressable locations, Duoram can perform a sequence of m arbitrarily interleaved reads and writes using just O(m lg n) words of communication, compared with Floram's O(m n) words. Moreover, most of this work can occur during a data-independent preprocessing phase, leaving just O (m) words of online communication cost for the sequence—i.e., a constant online communication cost per memory access.

#IACR #ResearchPapers #ORAM #ObliviousRAM
__
¹ https://eprint.iacr.org/2022/1747

A. Vadapalli et al., "Duoram: A Bandwidth-Efficient Distributed ORAM for 2- and 3-Party Computation"¹

We design, analyze, and implement Duoram, a fast and bandwidth-efficient distributed ORAM protocol suitable for secure 2- and 3-party computation settings. Following Doerner and shelat's Floram construction (CCS 2017), Duoram leverages (2,2)-distributed point functions (DPFs) to represent PIR and PIR-writing queries compactly—but with a host of innovations that yield massive asymptotic reductions in communication cost and notable speedups in practice, even for modestly sized instances. Specifically, Duoram introduces a novel method for evaluating dot products of certain secret-shared vectors using communication that is only logarithmic in the vector length. As a result, for memories with n addressable locations, Duoram can perform a sequence of m arbitrarily interleaved reads and writes using just O(m lg n) words of communication, compared with Floram's O(m n) words. Moreover, most of this work can occur during a data-independent preprocessing phase, leaving just O (m) words of online communication cost for the sequence—i.e., a constant online communication cost per memory access.

#IACR #ResearchPapers #ORAM #ObliviousRAM
__
¹ https://eprint.iacr.org/2022/1747

A. Vadapalli et al., "Duoram: A Bandwidth-Efficient Distributed ORAM for 2- and 3-Party Computation"¹

We design, analyze, and implement Duoram, a fast and bandwidth-efficient distributed ORAM protocol suitable for secure 2- and 3-party computation settings. Following Doerner and shelat's Floram construction (CCS 2017), Duoram leverages (2,2)-distributed point functions (DPFs) to represent PIR and PIR-writing queries compactly—but with a host of innovations that yield massive asymptotic reductions in communication cost and notable speedups in practice, even for modestly sized instances. Specifically, Duoram introduces a novel method for evaluating dot products of certain secret-shared vectors using communication that is only logarithmic in the vector length. As a result, for memories with n addressable locations, Duoram can perform a sequence of m arbitrarily interleaved reads and writes using just O(m lg n) words of communication, compared with Floram's O(m n) words. Moreover, most of this work can occur during a data-independent preprocessing phase, leaving just O (m) words of online communication cost for the sequence—i.e., a constant online communication cost per memory access.

#IACR #ResearchPapers #ORAM #ObliviousRAM
__
¹ https://eprint.iacr.org/2022/1747

A. Vadapalli et al., "Duoram: A Bandwidth-Efficient Distributed ORAM for 2- and 3-Party Computation"¹

We design, analyze, and implement Duoram, a fast and bandwidth-efficient distributed ORAM protocol suitable for secure 2- and 3-party computation settings. Following Doerner and shelat's Floram construction (CCS 2017), Duoram leverages (2,2)-distributed point functions (DPFs) to represent PIR and PIR-writing queries compactly—but with a host of innovations that yield massive asymptotic reductions in communication cost and notable speedups in practice, even for modestly sized instances. Specifically, Duoram introduces a novel method for evaluating dot products of certain secret-shared vectors using communication that is only logarithmic in the vector length. As a result, for memories with n addressable locations, Duoram can perform a sequence of m arbitrarily interleaved reads and writes using just O(m lg n) words of communication, compared with Floram's O(m n) words. Moreover, most of this work can occur during a data-independent preprocessing phase, leaving just O (m) words of online communication cost for the sequence—i.e., a constant online communication cost per memory access.

#IACR #ResearchPapers #ORAM #ObliviousRAM
__
¹ https://eprint.iacr.org/2022/1747