As cybergibbons notes in his answer, the court decision itself is quite interesting reading. In particular, while the details of the "Megamos algorithm" itself are obviously not given in the court decision, the manner in which it is used is described in a surprisingly clear manner in paragraphs 4 and 5:
"In detail the way this works is as follows: both the car computer and the transponder know a secret number. The number is unique to that car. It is called the "secret key". Both the car computer and the transponder also know a secret algorithm. That is a complex mathematical formula. Given two numbers it will produce a third number. The algorithm is the same for all cars which use the Megamos Crypto chip. Carrying out that calculation is what the Megamos Crypto chip does.
"When the process starts the car generates a random number. It is sent to the transponder. Now both computers perform the complex mathematical operation using two numbers they both should know, the random number and the secret key. They each produce a third number. The number is split into two parts called F and G. Both computers now know F and G. The car sends its F to the transponder. The transponder can check that the car has correctly calculated F. That proves to the transponder that the car knows both the secret key and the Megamos Crypto algorithm. The transponder can now be satisfied that the car is genuinely the car it is supposed to be. If the transponder is happy, the transponder sends G to the car. The car checks that G is correct. If it is correct then the car is happy that the transponder also knows the secret key and the Megamos Crypto algorithm. Thus the car can be satisfied that the transponder is genuine. So both devices have confirmed the identity of the other without actually revealing the secret key or the secret algorithm. The car can safely start. The verification of identity in this process depends on the shared secret knowledge. For the process to be secure, both pieces of information need to remain secret - the key and the algorithm."
Translated (back) into standard crypto terminology, it appears that the "Megamos algorithm" is an (evidently failed) attempt to implement a pseudorandom function family (PRF).
Specifically, the authentication protocol described in the paragraphs above can be rephrased as follows:
Both the car computer $\rm C$ and the transponder $\rm T$ hold a shared secret key $K$ and a pseudorandom function family (implemented using the Megamos algorithm) $\sf PRF$, of which ${\sf PRF}_K$ is a specific instance parametrized by the key $K$. The PRF outputs a bitstring that is split into two parts, $F$ and $G$. To perform an authentication exchange:
- $\rm C$ chooses a random number $r$ and computes $(F,G) = {\sf PRF}_K(r)$.
- ${\rm C \to T:}\ r, F$
- $\rm T$ computes $(F',G') = {\sf PRF}_K(r)$ and aborts unless $F = F'$.
- ${\rm T \to C:}\ G'$
- $\rm C$ verifies that $G = G'$.
Now $\rm C$ and $\rm T$ have verified that they can each compute ${\sf PRF}_K$, and therefore hold the same key $K$.
An interesting feature of this protocol is that, since $r$ is chosen solely by $\rm C$, an attacker who manages to eavesdrop on a legitimate exchange could easily impersonate $\rm C$ by replaying the earlier $r$ and $F$, and could even verify $\rm T$'s response by comparing it with the earlier $G$. Under the expected usage scenario, this might not be considered a major security risk, since the important part is presumably authenticating $\rm T$ to $\rm C$; on the other hand, since the protocol evidently does try to also authenticate $\rm C$ to $\rm T$, it might simply be that the summary above is incomplete, and that the actual protocol uses some additional mechanism to prevent such replay attacks.
That said, other than the flaw described above, the protocol seems solid provided that $\sf PRF$ is indeed a secure pseudorandom function family. In particular the assertion in the court decision that "[f]or the process to be secure, both pieces of information need to remain secret - the key and the algorithm" appears patently false: if the algorithm were a secure PRF, such as, say, AES-CMAC-PRF-128, the protocol described above would be secure as long as just the key $K$ was kept secure.
Indeed, the same holds regardless of the details of the protocol: by definition, any instance of a secure pseudorandom function family is indistinguishable from a truly random function, as long as one does not know the key used to choose the instance. Thus, by definition, the choice of the algorithm, or the manner in which it is used, does not matter as long as it's a secure PRF: they all look identical to anyone who doesn't know the key. Indeed, there are many published and freely usable PRF algorithms that have withstood extensive public scrutiny and cryptanalysis, and are in common use worldwide. By failing to publish their own algorithm (or to use one of the already published algorithms), the makers of the Megamos Crypto chip have not only violated Kerckhoffs' principle, but also deprived themselves of this scrutiny by the global crypto research community.
All that said, I can easily enough understand why they may have chosen to do so: the Megamos Crypto chip is designed to be embedded into a car key, with all the attendant limitations on memory capacity and power consumption. Implementing standard crypto primitives like AES on such small, low power devices is often a challenge, and of the few crypto algorithms specifically designed for such devices, most are new and still poorly analyzed, not to mention that even the published designs often end up making questionable tradeoffs in speed vs. security. The designers of Megamos Crypto may have been hoping that, by designing their own algorithm and keeping it secret, any security weaknesses it may have might not be so easily exploited.
Alas, Kerckhoffs' principle has a habit of reaffirming itself: if there's profit to be made in discovering the algorithm, someone will do so and profit from it. Indeed, based on the court decision, in this case this appears to have happened long ago, by 2009 (when the algorithm was included in the Tango Programmer tool, sold for €1000 by a Bulgarian company and described in the court decision as being of "clearly murky origin") if not earlier.
By the way, the court decision even quotes some interesting parts of the redacted paper, including the following, which sheds some light on the nature of the weaknesses discovered in the Megamos algorithm:
"Unfortunately, our first attack is hard to mitigate. It seems unfeasible to prevent an adversary from gathering two authentication traces. Furthermore, this attack exploits weaknesses in the course of the cipher's design - e.g. the size of the internal state. It would require a complete re-design of the cipher to fix these weaknesses. To that purpose, lightweight ciphers, like grain, and so on, have been proposed in the literature and could be considered as suitable replacements for the Megamos Crypto. On the positive side, our first attack is more computationally intensive than the attacks in section 6 and 7, which makes it important to take the aforementioned mitigating measures in order to prevent the more inexpensive attacks."
Earlier in the text, the defendants also note in their case (paragraph 19(xiv)) that:
"The attack based on the Megamos Crypto algorithm still requires the criminals to have a car, plus a key, plus two days to use a computer program which tries out a lot of possibilities."
From the phrasing, and from the suggestion of Grain as an alternative, it appears that the "Megamos algorithm" may in fact be some kind of a stream cipher. This does make sense, insofar as, with the input somehow combined with the key, a stream cipher may be regarded as PRF with arbitrary-length output. Stream ciphers, despite their limitations as crypto building blocks, also still remain very popular as crypto primitives for low-end systems.
The attack itself appears to be some kind of a related-key attack based on comparing the output of the cipher for two different random nonces (which are made known during the authentication process) and presumably involving some kind of "informed brute force" enumeration of the internal cipher state in order to recover the secret (fixed) part of the cipher key. Or at least, that's what it looks like based on the court decision.
