An informal discussion on Malicious Cryptographic Design
A short discussion after Ralf-Philipp Weinmann's talk on Malicious Cryptographic Design.
AB: Alex Biryukov
DB: Dan Bernstein
GL: Gaetan Leurent
SL: Stefan Lucks
We wanted to explore how big could be an advantage of the designer of the primitive over the users of that primitive. Both in terms of positive public-key like features and in terms of malicious backdoor properties. One can speak of backdoors -- additional properties of the design which give the designer an advantage over the ordinary user of the primitive, and bugdoors -- intentional brittleness of the design, allowing malicious mis-implementation, which is plausibly deniable. We are probably more interested in the former.
Is this direction of research interesting?
What could be potential areas to search for new constructions?
JPA: RC4 could be an example of a brittle construction in terms of implementation. See for example an implementation by [Wagner-Biondi]. Another example is a cipher with large tables, in which malicious implementation changes a few rarely accessed elements.
DB/TL: There is a relevant article by Matt Blaze and Susan Landau on government using [bugdoors instead of wiretaps].
JPA: SipHash-like design (?)
CR: The more rotation constants you use in ARX, the more chance to hide something?
SL: We've seen for Skein that rotation constants that cause a peak in probability are obvious (rotations by powers of 2, for example).
RPW: Is it possible to hide cube testers in large numbers of queries?
JPA: I thought about it, but couldn't find efficient way to embed cubes...
CR/GL: iterative characteristics/ constant cancellations... (?) rotation constants in ChaCha (?)
AB: RK attacks: especially vulnerability to related subkeys could be an example of brittleness or malicious design. Such weakness can be exploited with a "proper" key-derivation function.
AB: We know well how to construct ciphers with very low probabilities of characteristics, but it does not prevent those characteristics from bundling into good differentials or truncated differentials.
CR: For ciphers like AES, truncated differentials are well understood. With [weak Keccak alignment], could it be easier to hide good truncated differentials in such constructions?
DB: In general such backdoor constructions would require large description, seems hard to hide something in small description.
AB: What about stream ciphers, description can be fairly small, but design space can be very large. For example something similar to Grain, with properly chosen number of initialization rounds to allow for cube distinguishers.