A Practical Key Recovery Attack on Basic TCHo
Mathias Herrmann, Gregor Leander
Download-PDF
Abstract:
TCHo is a public key encryption scheme based on a stream cipher component, which is particular suitable for low cost devices like RFIDs. In its basic version, TCHo offers no IND-CCA2 security, but the authors suggest to use a generic hybrid construction to achieve this security level. The implementation of this method however, significantly increases the hardware complexity of TCHo and thus annihilates the advantage of being suitable for low cost devices. In this paper we show, that TCHo cannot be used without this construction. We present a chosen ciphertext attack on basic TCHo that recovers the secret key after approximately d^3/2 decryptions, where d is the number of bits of the
secret key polynomial. The entropy of the secret key is log2(binomial(d,w), where w is the weight of the secret key polynomial, and w is usually small compared to d. In particular, we can break all of the parameters proposed
for TCHo within hours on a standard PC.
BibTex:
@INPROCEEDINGS{DBLP:conf/pkc/HerrmannL09,
author = {Herrmann, Mathias and Leander, Gregor},
title = {A Practical Key Recovery Attack on Basic TCHo},
booktitle = {Public Key Cryptography},
year = {2009},
pages = {411-424},
crossref = {DBLP:conf/pkc/2009},
bibsource={DBLP, http://dblp.uni-trier.de},
}
crossreferenced publications:
@PROCEEDINGS{DBLP:conf/pkc/2009,
editor = {Jarecki, Stanislaw and Tsudik, Gene},
title = {Public Key Cryptography - PKC 2009, 12th International Workshop on Practice and Theory in Public-Key Cryptography, Irvine, CA, USA, March 18-20, 2009. Proceedings},
booktitle = {Public Key Cryptography},
series = {Lecture Notes in Computer Science},
volume = {5443},
year = {2009},
publisher = {Springer},
isbn = {978-3-642-00467-4},
bibsource={DBLP, http://dblp.uni-trier.de},
}