IEICE TRANSACTIONS on Fundamentals
Achieving Higher Success Probability in Time-Memory Trade-Off Cryptanalysis without Increasing Memory Size
Summary :
The time-memory trade-off cryptanalysis for block ciphers with a search space of size 2N (N: key length) cannot achieve a success probability excceding 63%. This is caused by some unavoidable overlapping of keys in the space. For elavating the success probability of finding the correct key, a larger search space is necessary. That is, the increase of time complexity for precomputation would be inevitable. This paper theoretically shows, however, no further price is required for the size of look-up tables for the number of encryptions for searching for the key that matches the given ciphertext - plaintext pairs. This theory is confirmed by some empilical results.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E82-A No.1 pp.123-129
- Publication Date
- 1999/01/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Cryptography and Information Security)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Il-Jun KIM, Tsutomu MATSUMOTO, "Achieving Higher Success Probability in Time-Memory Trade-Off Cryptanalysis without Increasing Memory Size" in IEICE TRANSACTIONS on Fundamentals,
vol. E82-A, no. 1, pp. 123-129, January 1999, doi: .
Abstract: The time-memory trade-off cryptanalysis for block ciphers with a search space of size 2N (N: key length) cannot achieve a success probability excceding 63%. This is caused by some unavoidable overlapping of keys in the space. For elavating the success probability of finding the correct key, a larger search space is necessary. That is, the increase of time complexity for precomputation would be inevitable. This paper theoretically shows, however, no further price is required for the size of look-up tables for the number of encryptions for searching for the key that matches the given ciphertext - plaintext pairs. This theory is confirmed by some empilical results.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e82-a_1_123/_p
Copy
@ARTICLE{e82-a_1_123,
author={Il-Jun KIM, Tsutomu MATSUMOTO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Achieving Higher Success Probability in Time-Memory Trade-Off Cryptanalysis without Increasing Memory Size},
year={1999},
volume={E82-A},
number={1},
pages={123-129},
abstract={The time-memory trade-off cryptanalysis for block ciphers with a search space of size 2N (N: key length) cannot achieve a success probability excceding 63%. This is caused by some unavoidable overlapping of keys in the space. For elavating the success probability of finding the correct key, a larger search space is necessary. That is, the increase of time complexity for precomputation would be inevitable. This paper theoretically shows, however, no further price is required for the size of look-up tables for the number of encryptions for searching for the key that matches the given ciphertext - plaintext pairs. This theory is confirmed by some empilical results.},
keywords={},
doi={},
ISSN={},
month={January},}
Copy
TY - JOUR
TI - Achieving Higher Success Probability in Time-Memory Trade-Off Cryptanalysis without Increasing Memory Size
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 123
EP - 129
AU - Il-Jun KIM
AU - Tsutomu MATSUMOTO
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E82-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 1999
AB - The time-memory trade-off cryptanalysis for block ciphers with a search space of size 2N (N: key length) cannot achieve a success probability excceding 63%. This is caused by some unavoidable overlapping of keys in the space. For elavating the success probability of finding the correct key, a larger search space is necessary. That is, the increase of time complexity for precomputation would be inevitable. This paper theoretically shows, however, no further price is required for the size of look-up tables for the number of encryptions for searching for the key that matches the given ciphertext - plaintext pairs. This theory is confirmed by some empilical results.
ER -
English
