Cryptanalysis by Machine Learning ?

[Enthalpy]

Hello everybody!

Cryptography uses one-way functions to compute a trace (or message digest) of some "message" (bunch of data). One use is to sign the shorter trace to authenticate a complete message.

An acceptable one-way function makes it practically impossible to choose a message to produce a given trace. Nor does it allow to choose two messages to produce any identical trace.

One-way functions combine many operations to make the trace a complicated function of the message. If an attacker finds some relation(s) of computer-manageable complexity between the message and the trace, he can produce a reduced set of messages that have better chances to obtain a given trace or identical traces, and ruin the one-way function. Said relations can just be slightly abnormal correlations.

==========

Traditional attack methods against one-way functions and other cryptographic algorithms include linear analysis and differential analysis. They are "linear" for the Xor, as arrays of bits are vector spaces with Xor and And operations, and this offers efficient computation algorithms from linear algebra. All present cryptographic algorithms are tested to resist linear and differential analysis.

Non-linear relations offer more possible attacks against one-way functions and other cryptographic algorithms. If the message is M (typically >= 128b including padding) and the trace T (usually 160 to 256b), such relations may look like, just more complicated:
(M₇ or M₂₃ or M₇₈) and (M₉₇ xor M₁₁₃) correlates abnormally with T₁₆ and T₅₃ or T₁₅₃ and T₁₉₂

I propose (but have an intuition other people already did) to let machine learning search for such relations. A neural network is a set of nonlinear relations, machine learning establishes them from a training set, here a set of messages and their traces.

The size of the needed neural network is banal presently. The training set must suffice to reduce the false positives, which are best eliminated by subsequent tests on different training sets. Looking for faintly abnormal correlations demands a bigger training set, checking only for more strongly abnormal correlations and searching for many of them seems a better bet.

The standard neural networks would only try to reproduce individual bits at the trace from logic functions of the message. On can expand the individual trace bits with a limited set of their logic combinations. Seeking for arbitrary logic functions of the trace bits would need to adapt the neural networks and their learning methods to be more symmetric, as far as I know (and I ignore much).

==========

All usual one-way functions I know are heirs of MD-2, MD-5 etc. They use too simple elementary operations: Add, Xor, Rot, from a time when these were faster on a computer. Consequently, the amount of diffusion and confusion of these functions is low - conceptually, the exact logic function from the message to the trace isn't complicated enough. I understand it as a consequence: all historical one-way functions have been broken, MD-2, MD-4, MD-5, in perfectly exploitable attacks, with examples of collisions. Even the early Sha is weakened. As opposed, no established symmetric encryption algorithm, relying on tables or multiplications that provide much diffusion and confusion, was efficiently broken (only the too small DES by brute-force, not by an inherent weakness).

That's why I suggest to attack one-way functions, not symmetric encryption algorithms, by machine learning.

Better one-way function design has been known for decades. Forget the historical schemes, use a symmetric encryption algorithm as a one-way function, for instance AES. Some fixed conventional value feeds the plaintext input, the message feeds the key input, the cyphertext output is the trace. Known layouts provide a trace wider than the ciphertext output if needed. Known methods cope with messages of varied length.

Marc Schaefer, aka Enthalpy