Cracking the GPS Galileo Satellite

Glyn writes "Newswise is reporting the the encryption in the Galileo GPS signal has been broken. The pseudo random number generator used to obscure the information stored in the Galileo GPS signal has been broken. From the article: 'Members of Cornell's Global Positioning System (GPS) Laboratory have cracked the so-called pseudo random number (PRN) codes of Europe's first global navigation satellite, despite efforts to keep the codes secret. That means free access for consumers who use navigation devices -- including handheld receivers and systems installed in vehicles -- that need PRNs to listen to satellites.'"

Comments

Offtopic but....

[rolfwind]

Afraid that cracking the code might have been copyright infringement, Psiaki's group consulted with Cornell's university counsel. "We were told that cracking the encryption of creative content, like music or a movie, is illegal, but the encryption used by a navigation signal is fair game," said Psiaki.

Sigh, how did READING the bits on your own CDs/DVDs ever become illegal? Freedom of speech implies a freedom to read what you want. (Yes, I understand the DMCA, but I'm still in shock - I always considered laws making it illegal to read "signals", etcetera "not intended for you" very British but very unAmerican. And I say British because I'm getting those quotes from British laws circa WW2 and probably before.)

Props to Cornell.

Re:and North Korean rocket scientists appreciate t

[Anonymous Coward]

Why? So they know where exactly their rocket was when it failed? Don't you think that positioning a nuclear bomb with sub meter precision is a little too control-freakish?

uncrackable encryption

[Nikademus]

PRN is not really encryption.

But anyway, there is no such thing as an encryption scheme that cannot be cracked. It is just a matter on how much time it will take to crack it.
Encryption will always be crackable, we are just playing with the fact it would take 512 or so years to crack a particular scheme with the actual technology.

Re:uncrackable encryption

[Groo Wanderer]

"But anyway, there is no such thing as an encryption scheme that cannot be cracked. It is just a matter on how much time it will take to crack it.
Encryption will always be crackable, we are just playing with the fact it would take 512 or so years to crack a particular scheme with the actual technology."

Actually, there is almost no encryption scheme that can stand up for a weekend to the 'suitcase full of cash' cracking methodology.

                -Charlie

Re:uncrackable encryption

[SillyNickName4me]

2^128 is a very big number. If the entire planet was turned into a vast computer with circuits an atom across it would take longer than the life of the universe to break an AES key by brute force.

First of all, yes, 2^128 is a very big number indeed. The rest of your statement however makes absolutely no sense whatsoever.

The size of a computer and the circuits within have little to do with how capable that computer is of performign the specific operations for breaking AES efficiently. Neither does your statement take into account the potential of weaknesses in the algorithm that might eliminate part of the keyspace. Do I have proof of such weaknesses? Nope, but the question is if I need that, the large majority of algorithms turns out to have such flaws. so unless you have mathematical proof that they do not exist in this case, the assumption that they exist is a safe one.

I vaguely remember people arguing that breaking DES was not feasable only some 25 years ago, and at the time they were probably somewhat right. Yet, nowadays it is breakable in hours by the kind of technology that private civilians can afford.

So all in all, it is safe to assume that AES is safe for the moment, but there is no telling what future technology will do. The likelyhood however is that both a breach of AES will be found, and hardware will be made that makes the AES problem relatively simple to solve.

Re:uncrackable encryption

[nojayuk]

"...the cluelessness of the Gallileo business model. Charging for something someone else is giving away is so 1990s. It only makes sense if there is something going on here we have not been told about."

Galileo makes high-precision access available to paying customers, the US NAVSTAR reserves that level of accuracy only for US and allied military systems. Some of the Galileo cluster will orbit at higher inclinations than the existing NAVSTAR cluster, making GPS more usable in the far North and far South (although I understand some planned future NAVSTAR satellite deployments will fill in the gaps here too). Galileo can't be switched off or degraded on a whim by a single government unlike the NAVSTAR system, allowing it to be trusted to control civilian aircraft in crowded skies.

The users of GPS will end up with multi-function receivers that can work interoperably with NAVSTAR and Galileo since it would be pointless commercially to do otherwise. Unless NAVSTAR goes commercial or the DoD stops degrading the signal the high-precision customers like airlines and such will use Galileo and pay for the convenience and predictability.

Re:uncrackable encryption

[NormalVisual]

Unless NAVSTAR goes commercial or the DoD stops degrading the signal the high-precision customers like airlines and such will use Galileo and pay for the convenience and predictability.

Selective availability (intentional degradation) was turned off on the Navstar system back in 2000, although there's nothing that says it won't get turned back on again sometime in the futures. In addition, differential GPS transmitters cover a large portion of the U.S., and DGPS is quite a bit more accurate than the data you get directly from the satellites, and works even when selective availability is active.

Re:uncrackable encryption

[Anonymous Coward]

And before you go running off to make a patent, white papers exist on the internet dating back to 1990 on using One Time Pads for internet/computer authentication mechanisms. And the fact that I wrote all this up here also serves as prior art.

This is laughable. You are trying to use the only perfectly secure encryption scheme, while breaking the rules which allow it to be the only perfectly secure encryption scheme.

So your mechanism is only as secure as the weakest parts, which in this case is plain text email or maybe SSL encrypted email, in which case, just use SSL and have the user provide their own strong password. You are getting NO GAIN for something which is MORE of a PAIN.

BTW, specifically in regards to GSM mobile phones (I don't know about others), GSM phone crypto uses a small Linear Feedback Shift Register configuration (40bit equivalent) for Pseudo Random Number Generation. To make matters worse, it is seeded (partially or fully?) with the IMEI number of that phone. IMEI numbers can be broken down a great deal if you know the make of the phone and then more if you know the model. The bit depth of IMEI suddenly drops. In 1999 GSM could be cracked in less than a second on a basic home PC. In addition to that, I personally know of a GSM eavesdropping/recording device being used outside of government/law-enforcement and I also know of someone who makes a similar device which is separate from the other I have mentioned. GSM at least, can hardly be considered to be providing strong comms. GSM crypto only "protects" the wireless link between the mobile phone and base station, NOT the wired link between cells or landlines, etc, so you trust your Telco? BTW, do you trust the French? This is their crypto scheme (A5) and they intentionally made it weak. Germany, try as they might, being so close the then Soviet Union, wanted it to be strong. The fact is, most governments don't want their people having strong crypto and you are essentially providing nothing.

Why bother? You are taking the strengths of OTP, weakening them to something ranging from plain text to strengths we already have (SSL) and yet you are keeping the impracticalities of OTP. I have to wait to have my password broadcast to the World before I can log in? What exactly are you providing again?

Really, why bother?

Hate to make a plug for myself but I came up with a one time pad authentication method for logging into websites. It's as secure as can be socially accepted. Key words there.

Every single time, in the past 11 years or so that I've been into crypto and crypto forums, that I heard someone say something like, "I think I have a good scheme", it has turned out to be a complete joke. I now get a chuckle whenever I read something like that, before I go on and read the "good scheme". So thank you for the chuckle. By the way, you can't have prior art when someone before you has it. It's not yours, it's thiers. Even if it does suck.

Get your filthy American hands off our data!

[Anonymous Coward]

If a European tried doing something like this with a US GPS satellite, they'd get arrested for being a terrorist long before they had chance to write a paper on it.

Accuracy not critical with nukes on soft targets

[Goonie]

You don't need sub-metre accuracy to be lethal with an ICBM tipped with a nuclear warhead. Land a rocket with a nuke within five miles of here, here, or here and you kill tens, probably hundreds of thousands of people.

Or, alternatively, you could just about hit here with a trebuchet from North Korea, and there are 11 million people there.

North Korean nuclear strategy is likely to revolve around killing lots of people, not taking out hardened military targets with precision weapons. For that, accuracy measured in miles will do just fine.

How about the US GPS encrypted channels?

[KDN]

The US GPS system also has two encrypted channels, P1 and P2, which use undocumented PRN generators (or at least I've never found them). Has anyone ever cracked them? The CA signal is what the civilian systems use.

Re:How about the US GPS encrypted channels?

[Vreejack]

NAVSTAR encryption serves two purposes, reduction of precision for outsiders and anti-jamming. Bill Clinton removed the precision constraints, but the anti-spoofing/jamming codes are changed very often.

Two caveats: the anti-jam/spoof feature can improve reception in areas of high interference caused by physical geometry (reflective surfaces, for example), and the US gov. can always cripple precision in local areas if it wishes (e.g., Baghdad).

Isnt That Illegal?

[omegashenron]

Given that these codes are in place to sell premium products to consumers and recoup the investment made with putting the satellites in orbit - how is this any different to breaking codes for satellite TV and/or DRM?

I really hope the folks at Cornell start working on something that would have a legitimate use such as the ability to make a backup of a legally purchased HD-DVD movie... oh wait... that would be illegal :-(

Re:much ado about nothing

[Barnoid]

That's ridiculous. They put a satellite up in orbit to broadcast this information to the whole globe. What do they have to lose by letting people use it? It's not like somebody could break their service just by listening to it.

You're right, it can't be broken. Maybe they don't want to get sued during the test phase by some guy who drove his car in a trench because he was feeding his navigator with the Galileo signal.

Legal second opinion (from an engineer)

[justthisdude]

I'm no big fan of copyright, but I think Cornell needs a better lawyer. Clearly, no one can copyright a location (although this would make for a great scene: "Where am I?" "I can't tell you; it's copyrighted." I bet Dick Cheney is already drooling, but I digress). What they are protecting is the output signal from their satellites' atomic clocks, and measurements of their exact orbits. A mobile device computes its own position by comparing path delays to themselves from many satellites' known locations. The timing signal and satellite ephemeris are creative content that can be protected just like a map or satellite picture can be copyrighted, while the location depicted isn't. TFA compares decoding the timing signal to looking at a lighthouse and deducing your own position, which is clearly free. That same arguement would support decoding satellite signals of CNN to deduce world events. World events are clearly free, but the video isn't.

A stronger arguement can be made: since they have agreed to make the codes open source they have no right to enforce copyright. You just can't say they aren't creating anything.

Re:and North Korean rocket scientists appreciate t

[feyhunde]

For a nuclear warhead, traditional GPS' 5m-accuracy should be quite sufficient. It's not like they'd be trying to avoid "collateral damage"

In wartime the US can, will and does turn off the GPS in the warzone. Galilieo isn't under the same controls, and for that reason is popular with some governments for their guided weapons programs. Further, the civilian GPS receivers still have certain height and velocity restrictions artificially put in by the US to prevent guided missile uses. Only recently was an agreement made that would allow the US and EU to block signals in warzones without disabling the opposing system.

Re:Accuracy not critical with nukes on soft target

[Jah-Wren Ryel]

The assumption is that the North Korean government is sane.

Lol! I was just going to post a joke about how we are suppossed to believe the standard demonization that our enemy is a "madman."

I seriously doubt any government that systematically starves its own people to death over a few decades would have any trouble watching the same people die in a "glorious" fire.

You should doubt it.

Only in movies do insane people end up runnning countries. Letting the population starve is not a symptom of insanity - it is a symptom of a ruling class lacking accountability to the citizens.

The North Koreans are not insane, they just have a different perspective than the one our news media feeds us. Were Bush and Rumsfeld insane because they ignored counsel from the pentagon about how securing Iraq would require 2x-3x more troops than they wanted to allocate? No, they just saw the facts differently - incorrect they were, but not insane.

Same thing goes for North Korea's government. For example - they still consider themselves to be at war, no truce was ever signed - only an armistice which is just a little bit stronger than a "cease fire." To an American, 10,000 miles away, it sure seems like the korean war is over - but anyone who gets near the DMZ and sees the patrols on both sides (or has even just seen the movie Joint Security Area), it isn't so clear any more. North Korea has always felt like it needs to be prepared for an attack at any time and has thus kept its military at a full state of rediness.

North Korea has made a lot of dumb decisions, but that doesn't mean they are insane any more than Bush's (mis)handling of the war in Iraq means he is insane.

Re:Never Understood the Logic of Galileo

[Concerned Onlooker]

The free market would never adopt a new alternative that is not technically or functionally superior...

I suppose a free market wouldn't, but it's hard to say, given how we don't really have a working model of a free market to study. Except perhaps the truly lawless places on the planet.

And that GDP growth you're talking about? It's gone mostly to the people who are already wealthy. To the average American that statistic is a lie.

Regarding job creation:

• Private-sector jobs created by defense spending, 2001-2006: 1.5 million (Bureau of Labor Statistics)
• Private-sector jobs created by other government spending, 2001-2006: 1.3 million (Department of Defense)
• Private-sector jobs lost, 2001-2006: 1 million (Economic Policy Institute)

So you see, the jobs created are actually just government spending, not "free market" economics.

Re:Nope

[FireFury03]

I would venture to say that disabling GPS, at this point, would cause more economic damage in the short term than a medium-sized war.

I dare say that turning off or seriously degrading GPS would cause a few deaths too. That said, it wouldn't be the first stupid thing governments and millitaries have done. I would much prefer to get my positining data from a variety of sources, not just a single millitary system, that way no one organisation could decide to pull the plug. Also, ESA aren't millitary, so using Gallileo would make me feel much happier.

you don't really "jam" global satellite transmissions.

Yes, you do

What you do is remotely disable or degrade them at the source, which is what all this is about: who has the authority and ability to do just that.

Despite NAVSTAR's ability to do selective availability, this has been turned off since 2000 (although only a fool would trust it could never be turned back on). Selective availability affects the whole GPS system, not just a localised area so the millitaries now favour localised jamming. Besides, it had got to the point where selective availability is next to useless over a large chunk of the planet because anyone who cares has access to DGPS or SBAS data which easilly corrects the artificial errors.

The EU may have granted the United States the power to turn off Galileo

That's not what I said - I said the EU had given into US demands and modified the system so it is easilly jammable. As far as I know (I damned well hope!) the US doesn't have the ability to actually control the service itself, just interfere with it in a localised area.

Re:Digital road tolling

[alphakappa]

The Euro-peons are thinking about using the Galileo system as part of an electronic road tolling scheme... So, bearing in mind the surveillance potential of such a scheme, I'd think the best way to "crack" one of the Galileo satellites would be an ASAT missile...

Ohh, those silly Europeans... that kind of thing would never happen in the US!

Re:Never Understood the Logic of Galileo

[DrPepper]

Your comments are pretty much just troll, fortunately you only make a few points really:

1. Galileo is not just a copy of the GPS system. It has higher precision than GPS and so opens up new applications that simply aren't possible at the moment. It also works better in some countries where GPS simply doesn't work very well. In fact the two systems will coexist, and future receivers are likely to support both which will give even better accuracy.

2. The A380 isn't just a "me-too" project - there isn't a similar competitor in the world. Even Boeing admit that it falls into a different market segment than anything they have. However Boeing don't think it is a segment worth going after and have decided to put their resources elsewhere.

3. The US economy may have grown 20% (I've not verified this), but so have other economies. IIRC China is growing faster than either the USA or Europe at the moment.

Re:and North Korean rocket scientists appreciate t

[Marcos Eliziario]

Basically, a dictatorship doesn't care too much about sub-meter precision for their bombs. If the miss a target and destroy a child hospital instead of a command center, they have no media to complain about it and make them risk loosing an election (which, by definition, are also non-existent or fake in a dictatorship) And for atom bombs, well.... Do you think it really makes a difference it you miss the target even for 1 or two kilometers. Of course we are not talking about the kind of atom bombs designed to blast underground bunkers, but also, in that case, the north-korean death doctors still have a lot of more pressing developments to acchieve before they have to care about sub-meter precision.

As opposed to the psycho US country

[themusicgod1]

Where they just ban rave music, send swat teams to raves, try to ban all forms of live electronic music(including rock and roll) in florida, assault marching bands, consider heavy metal (along with most punk and industrial music) as 'satan worshiping' music fit for blacklisting, keep european musicians from being able to enter the country, and choosing the wrong media to listen to music through as a music fan can get you sued into the gutter. You are left with music in america, it's true, and you can say 'well, those kinds of music are illegal there for a purpose' to any of the above, I suppose, but that would be hypocritical.