Paper 2020/838

PudgyTurtle: variable-length, keystream-dependent encoding to resist time-memory tradeoff attacks

David A August and Anne C Smith

Abstract

PudgyTurtle is a way to use keystream to encode plaintext before XOR-based (stream cipher-like) encryption. It makes stream ciphers less efficient -- a typical implementation requiring about five times as much keystream and producing about twice as much ciphertext -- but also more robust against time-memory-data tradeoff attacks. PudgyTurtle can operate alongside any keystream generator, and thus functions somewhat like an encryption mode for stream ciphers. Here, we introduce the mechanics or PudgyTurtle and discuss its design motivations.

Note: This companion manuscript to a longer publication about PudgyTurtle introduces a new formula describing the plaintext-to-keystream matching process; discusses implementations with different parameter sets, and how these parameters affect things like ciphertext- and keystream-expansion; gives a graphical interpretation of PudgyTurtle's output statistics; and provides a focused, qualitative discussion about why PudgyTurtle can make time-memory-data tradeoff attacks more difficult.