Blockwise p-Tampering Attacks on Cryptographic Primitives, Extractors, and Learners

Saeed Mahloujifar, Mohammad Mahmoody

TL;DR

This paper introduces a "blockwise p-tampering" model, extending previous "bitwise" attacks on randomized algorithms. The authors demonstrate how an attacker can efficiently bias the output of functions by tampering with blocks of randomness, with implications for breaking cryptographic primitives, improving attacks on randomness extractors, and increasing the error of machine learning algorithms.

What Problem Does This Paper Address?

Randomized algorithms often rely on perfectly uniform and untampered randomness for security and correctness. However, real-world systems might generate or use randomness in blocks rather than individual bits. This paper addresses the question of how an adversary can exploit this block-based randomness generation by introducing "blockwise p-tampering attacks." In this model, an attacker can tamper with each block of randomness with an independent probability p. This extends prior work on "bitwise p-tampering" attacks, which assumed an attacker could tamper with individual bits. The authors explore the power and limitations of these blockwise attacks against various computational tasks.

Methods

The core of the paper is the development of an efficient "blockwise p-tampering biasing attack." This attack is inspired by a "mild-greedy" approach from prior bitwise work but adapted for blocks. A key technique is a novel "one rejection sampling" attack that efficiently biases the output of bounded functions. The authors also introduce a "greedy" tampering algorithm for Boolean functions, which provides stronger bias bounds but is less efficient. They then apply these biasing attacks to specific problems:

  • Cryptographic Primitives: They show how blockwise tampering can break security games for primitives like public-key encryption, extending prior bitwise attack results.
  • Randomness Extractors: The attacks are used to demonstrate impossibility results for extracting randomness from certain types of sources (block Santha-Vazirani sources).
  • Machine Learning: They develop a "targeted poisoning attack" against deterministic learners, showing how to increase classification error by injecting tampered training data.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Blockwise Tampering is Powerful: The paper demonstrates that tampering with blocks of randomness, not just individual bits, is a significant threat to randomized algorithms.
  • Efficiency Matters: The authors emphasize the importance of efficient tampering algorithms, showing that even with limited computational power, an attacker can achieve substantial bias.
  • Robustness is Key: The attacks are designed to be "robust," meaning they work even if the tampering probability p is not exactly known or varies across blocks, as long as it's at least p. This is crucial for practical security.
  • Beyond Cryptography: The work extends beyond traditional cryptography to impact machine learning, highlighting vulnerabilities in learning algorithms to adversarial data manipulation.
  • Limitations Exist: The paper also explores the limits of these attacks, showing that in some scenarios, even computationally unbounded attackers cannot achieve optimal bias, especially for non-binary functions.

Key Results

  • General Biasing Attack: An efficient blockwise p-tampering attack is presented that can bias the average of any efficient bounded function by at least $\Omega(p \cdot \text{Var}[f(X)])$.
  • Cryptographic Primitive Attacks: The attack leads to efficient blockwise attacks that break CPA security for public-key encryption schemes.
  • Extractor Impossibility: The work provides an alternative proof for the impossibility of deterministic extraction from block Santha-Vazirani sources.
  • Learning Algorithm Attacks: A targeted poisoning attack is shown to increase the classification error of deterministic learners by $\Omega_s(p)$, where s is related to the variance of the learner's success probability.
  • Boolean Function Bias: For Boolean functions, a stronger bias bound of $\frac{p}{2+2p} \cdot \text{Var}[f(X)]$ is achieved, though with a less efficient attacker.
  • Limits on Bias: For certain scenarios, even computationally unbounded blockwise p-tampering attacks cannot achieve a bias of p for balanced functions, with a maximum achievable bias bounded by approximately $0.7p$.

Limitations and Future Work

  • Computational Unboundedness: While the paper focuses on efficient attacks, it also studies computationally unbounded attackers to understand fundamental limitations. The results suggest that achieving optimal bias efficiently might require new ideas beyond the greedy approach.
  • Optimal Constant: Finding the exact optimal constant c for which blockwise p-tampering attacks can always achieve a bias of c·p remains an open question.
  • Small k-Sampling Attacks: The power of attacks that use a small, constant number of samples (k-sampling attacks) is an area for further research.
  • "Very Efficient" Viruses: Investigating the power of tampering attacks with extremely limited computational resources (e.g., not able to sample blocks or compute functions) is a future direction.
  • Biasing Up vs. Down: The current attacks primarily focus on biasing functions upwards. Extending this to attacks that can bias in either direction is an open problem.

Summary updated

BibTeX
@article{mahloujifar2017blockwise,
  author = {Saeed Mahloujifar and Mohammad Mahmoody},
  title = {{Blockwise p-Tampering Attacks on Cryptographic Primitives, Extractors, and Learners}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2017},
}

Loading related content...

Figure