A Timing Attack on Blakley's Modular Multiplication Algorithm, and Applications to DSA
Pages 129 - 140
Abstract
In this paper, we introduce a timing attack scheme against a 160-bit modular multiplication with Blakley's algorithm. It is assumed that a set of public inputs are multiplied by a secret parameter and running time of each multiplication is given, but the multiplication result is not known and a machine similar to victim machine isn't available. The proposed attack extracts all 160 bits of the secret parameter. Running time of Blakley's algorithm is analyzed and it is shown that running time of each step is dependent on the running time of other steps. The dependencies make the parameters of the attack be dependent on the secret key, while it makes the attack rather complicated. A heuristic algorithm is used to find the parameters of the attack. As a real scenario, the attack is applied against on-line implementation of Digital Signature Algorithm, which employs Blakley's modular multiplication. Practical results show that secret key of DSA will be found using 1,000,000 timing samples.
References
[1]
G. R. Blakley. "A computer algorithm for calculating the product AB modulo M". IEEE Transactions on Computers, 32(5):497-500, May 1983.
[2]
D. Brumley, D. Boneh, "Remote Timing Attacks are Practical", Proceedings of the 12th Usenix Security Symposium, 2003.
[3]
J. Cathalo, F. Koeune, and J.-J. Quisquater, "A New Type of Timing Attack: Application to GPS", Cryptographic Hardware and Embedded Systems - CHES 2003, LNCS 2779, 2003, pp. 291-303.
[4]
J. F. Dhem, F. Koeune, P. A. Leroux, P. Mestre, J. J. Quisquater and J. L. Willems, "A Practical Implementation of the Timing Attack", 3rd Working Conference on Smart Card Research and Advanced Applications - CARDIS 1998, Springer-Verlag, LNCS No. 1820, 1998.
[5]
E. W. Felten, and M. A. Schneider, "Timing Attacks on Web Privacy", CCS 2000, Athens, Greece, 2000.
[6]
R. Focardi, R. Gorrieri, R. Lanotte, A. Maggiolo-Schettini, F. Martinelli, S. Tini, E. Tronci, "Formal Models of Timing Attacks on Web Privacy", Electronic Notes in Theoretical Computer Science, vol. 62, 2001.
[7]
H. Handschuh, and H. M. Heys, "A Timing Attack on RC5", SAC'98, LNCS 1556, 1999, pp. 306-318.
[8]
A. Hevia, M. Kiwi, "Strength of Two Data Encryption Standard Implementations Under Timing Attacks", LATIN'98, LNCS 1380, 1998, pp. 192-205.
[9]
Intel, "Using the RDTSC instruction for performance monitoring", Technical report, 1997.
[10]
P. C. Kocher, "Timing Attacks on Implementations of Diffie-Hellman, RSA, DSA, and Other Systems", Advances in Cryptology - CRYPTO'96, Springer-Verlag, LNCS No. 1109, 1996, pp. 104-113.
[11]
F. Koeune, J. J. Quisquater, "A Timing Attack against Rijndael", Technical Report CG-1999/1, June 1999.
[12]
Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, "Handbook of Applied Cryptography", CRC Press, 1996.
[13]
National Institute of Standard and Technology (NIST), "Digital Signature Standard", FIPS PUB 186-2, http://csrc.nist.gov/publications/fips/fips186-2/ fips186-2.pdf
[14]
W. Schindler, "A Combined Timing and Power Attack", PKC 2002, LNCS 2274, 2002, pp. 263-279.
[15]
W. Schindler, C. D. Walter, "More Detail for a Combined Timing and Power Attack against Implementations of RSA", 9th IMA International Conference on Cryptography and Coding, LNCS No. 2898, 2003, pp. 245-263.
[16]
W. Schindler, "A Timing Attack against RSA with the Chinese Remainder Theorem", Cryptographic Hardware and Embedded Systems - CHES 2000, Springer-Verlag, LNCS No. 1965, 2000, pp. 109-124.
[17]
W. Schindler, "Optimized timing attacks against public key cryptosystems", Statistics and Decisions, volume 20, 2002, pp. 191-210.
[18]
W. Schindler, "On the Optimization of Side-Channel Attacks by Advanced Stochastic Methods", 8th International Workshop on Practice and Theory in Public Key Cryptography PKC 2005, Springer-Verlag, LNCS No. 3386, 2005, pp. 85-103.
- A Timing Attack on Blakley's Modular Multiplication Algorithm, and Applications to DSA
Recommendations
A Hardware Algorithm for Modular Multiplication/Division
A mixed radix-4/2 algorithm for modular multiplication/division suitable for VLSI implementation is proposed. The algorithm is based on Montgomery method for modular multiplication and on the extended Binary GCD algorithm for modular division. Both ...
A Hardware Algorithm for Modular Multiplication/Division Based on the Extended Euclidean Algorithm
A hardware algorithm for modular multiplication/division which performs modular division, Montgomery multiplication, and ordinary modular multiplication is proposed. The modular division in our algorithm is based on the extended Euclidean algorithm. We ...
An RNS Montgomery Modular Multiplication Algorithm
We present a new RNS modular multiplication for very large operands. The algorithm is based on Montgomery's method adapted to mixed radix, and is performed using a Residue Number System. By choosing the moduli of the RNS system reasonably large and ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 05 June 2007
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 23 Feb 2025