Lineair spoor
Een keten van lineaire benaderingen, één per ronde, die samen beschrijft hoe een bitmasker op de platte tekst correleert met een masker op de versleutelde tekst.
Lineaire cryptanalyse heeft een verband nodig tussen bits van platte tekst, versleutelde tekst en sleutel dat met een kans geldt die merkbaar afwijkt van ½. Je bouwt het ronde voor ronde op: benader elke S-box lineair, gebruik het uitvoermasker van de ene ronde als invoermasker van de volgende en bereken de bias van de hele keten met Matsui's piling-up-lemma. Matsui sprak van een lineaire karakteristiek; ‘trail’ is de latere term.
Eén enkel spoor onderschat vaak de werkelijkheid. Veel sporen delen dezelfde invoer- en uitvoermaskers en hun bijdragen tellen op: dat is de lineaire hull. Ontwerpers bewijzen daarom grenzen voor het beste spoor en hopen dat de hull geen verrassingen bevat.