Paper 2012/092

Tolerant Algebraic Side-Channel Analysis of {AES}

Yossef Oren and Avishai Wool

Abstract

We report on a Tolerant Algebraic Side-Channel Analysis (TASCA) attack on an AES implementation, using an optimizing pseudo- Boolean solver to recover the secret key from a vector of Hamming weights corresponding to a single encryption. We first develop a boundary on the maximum error rate that can be tolerated as a function of the set size output by the decoder and the number of measurements. Then, we show that the TASCA approach is capable of recovering the secret key from errored traces in a reasonable time for error rates approaching this theoretical boundary – specifically, the key was recovered in 10 hours on average from 100 measurements with error rates of up to 20%. We discovered that, perhaps counter-intuitively, there are strong incentives for the attacker to use as few leaks as possible to recover the key. We describe the equation setup, the experiment setup and discuss the results.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Unknown where it was published
Keywords
Algebraic attackspower analysisside-channel attacks
Contact author(s)
yos @ eng tau ac il
History
2012-02-23: received
Short URL
https://ia.cr/2012/092
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/092,
      author = {Yossef Oren and Avishai Wool},
      title = {Tolerant Algebraic Side-Channel Analysis of {AES}},
      howpublished = {Cryptology ePrint Archive, Paper 2012/092},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/092}},
      url = {https://eprint.iacr.org/2012/092}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.