Allerdings bewegt sich der Zeitbedarf von Brute-Force-Angriffen in astronomischen Größenordnungen - bei ausreichend langen Schlüsseln einige hunderttausend bis Milliarden Jahre. Alle A5-Schlüssel durchzuprobieren, würde etwa 584 000 Jahre dauern, wenn man annimmt, dass sich eine Million Entschlüsselungsvorgänge je Sekunde durchführen und auf Erfolg prüfen lassen. Den Zeitbedarf für einen Einzelschritt unter den Tisch fallen lassend sagt man auch vereinfachend: Der Brute-Force-Angriff gegen A5 hat eine Komplexität von 2⁶⁴.

Von einem erfolgreichen Angriff gegen einen Kryptoalgorithmus spricht man, wenn sich durch theoretische Überlegungen die Angriffskomplexität wesentlich verkleinern lässt. Der 1999 beschriebene A5/1-Angriff von Biryukov, Shamir und Wagner reduzierte auf einen Schlag die Angriffskomplexität vom theoretischen Maximum 2⁶⁴ des Brute-Force auf 2⁴² bis 2⁴⁸. Ein Zurückrechnen des Schlüssels beschleunigt sich daher - etwa ähnlich aufwendige Einzelschritte vorausgesetzt - um den Faktor 2⁴² bis 2²⁴ und würde sich damit in dem überschaubaren Zeitrahmen von gerade einmal wenigen Monaten bewegen.

Erst durch Zeit/Speicher-Kompromisse (Time/Memory Tradeoffs, kurz TMTOs) nach Hellmann ergeben sich weitere Beschleunigungen. Je mehr Zwischenergebnisse der Berechnungen man etwa in sogenannten Rainbow-Tabellen sammelt, desto schneller lassen sich die einzelnen Knackvorgänge durchführen: derzeit voraussichtlich rund zwei Stunden je Schlüssel. Die nur einmal notwendige Berechnung der zwei Terabyte großen Rainbow-Tabellen dauert jedoch selbst auf Spezial-Hardware mehrere Monate.