There has been published work looking at algebraic attacks against A5.1 (the GSM cipher for most people). Look at: http://www.springerlink.com/content/eu97gk8786h7tj25/ and obtain this paper for full details.

Essentially, A5.1 and other similar ciphers are immune to algebraic attacks because the irregular clocking introduces many non-linear terms, and the order of the terms grows very quickly.

There was work published 2-3 years ago on this also: so this is not really new.

If anyone is interested in an actual explanation of the attack, rather than the half-assed speculation that (per usual) we're getting from most of the commentators here, there was a fairly informative thread on sci.crypt not long ago.

See in particular:

http://groups.google.com/group/sci.crypt/msg/9dd2a8224203caeb

(Greg Rose's informal description of the underlying principle)

http://groups.google.com/group/sci.crypt/msg/7065f9a4289581f1

(David Wagner's short explanation of the basics of the attack)

Basically, as I understand it from Wagner's description, the Cube attack uses appropriate plaintext/ciphertext pairs to extract a set of linear functions of the key bits. Once you have enough of them, you can solve for the key bits just as you would with any system of N independent linear equations of N unknowns. (Wagner says that much of the actual Cube attack consists of clever ways of performing these operations.)

Incidentally, as you can see in Wagner's description, for this sort of thing we typically talk about polynomials in GF(2), where there aren't any exponents. A boolean variable times itself equals itself, so (positive integer) exponents are no-ops in GF(2). References here to "higher degree" and "lower degree" refer not to polynomial terms with exponents (as in the little example at the end of the article) but to terms that are products of different variables: x*y*z rather than x**3.

(That doesn't mean the Cube attack only applies to polynomials in GF(2) - just that that's how most of the discussion will probably be framed.)