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.'"

Amateur Galileo receiver?

[Goonie]

If I read this, and the GPS [wikipedia.org] article in the Wikipedia, it would now be possible to build a Galileo system out of off-the-shelf parts and some moderately clever software. Is this the case, or is there something I'm missing?

Re:uncrackable encryption

[Gorath99]

I fact, that is pretty much the only attack that will work against a correct implementation of OTP [wikipedia.org], an encryption scheme that actually is unbreakable (though rather unpractical for most applications).

Re:Accuracy not critical with nukes on soft target

[Znork]

"North Korean nuclear strategy"

Actually, like most such strategies, North Korean nuclear strategy is most likely to revolve around not having to actually fire such weapons; if you at any point need to actually launch, you've already lost, they can only be used to make the enemy and the rest of the world lose too.

Taken to the natural conclusion, see the Dr Strangelove version of Doomsday Machine. No precision needed at all, and you dont even need a trebuchet.

Re:and North Korean rocket scientists appreciate t

[Anonymous Coward]

It's used for setting course early on. Most of the way, warheads are just coasting. So little direction and position errors early on are magnified at the other end. Still may be overkill, as you suggested, but maybe not for all we know.

Re:How about the US GPS encrypted channels?

[steve_l]

I think the US encryption system changes on a regular (monthly?) basis; you need new keys in your receiver. So even if you manage to pick up an military GPS rx on ebay or somewhere else, you wont get the military fix.

which is a pity -apparently it works better under tree cover than civilian GPS.

Algorithm is being replaced

[joshua42]

Acoording to a friend working on the Galileo project they came up with a new encryption algorithm specification a week ago. Quite annoying with such changes this late in the project, they thought. I guess this news kind of explains it.

Re:uncrackable encryption

[dnoyeb]

Beautiful. I have tried to explain for a time that this is not just the measure of encryption but the measure of security itself.

Security is the difference in access-pain for those with permisison vs. those without. Putting something where nobody can get to it is not ultimate security, thats no security at all.

As for the satellite, I presume the European one is offering more accuracy and that it can't be shut off by the US Government. Well not because they unilaterally decide to.

Also I'm surprised if anyone in US would be able to use this cracked satellite data in the US due to DMCA. But everyone else in the world can, lol.

I don't understand

[MrShaggy]

Why it was necessary to break up someone's business like this? Now instead of paying monthly for access, they are going to have to license the access right to the manufacturer. Space is expensive. So when satellites need repair or replacement, how is this going to happen ?? All you will see is either the company will figure out a way to update the codes all the time(Like sat. tv) or, a massive increase in the cost of GPS units, to cover the license cost. Now someone that has a small hobby like geocaching might not be able to afford it.

What about the DMCA? How likely would this company try to sue the university, and the students, for breaking the code. I'm sure that they would go after the magazine as well. Why did they have to name the company? Why couldn't they just say they cracked a type of code this way? Did they even inform the company that the code was cracked in order to give them time to fix it? Just because you don't like the Pay-per-use model, doesn't mean that you have to use it.

Re:uncrackable encryption

[tacocat]

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.

http://www.tacocat.net/

The idea is to get your password sent to you by some method and upon successful authentication, the password is reset and retransmitted. The socially accepted part is sending the password to you in such a way that you'll actually be able to use it. The most common form of sending new passwords today is via email. I'll pass on any discussion about how secure this is, it's too common to ignore. But the better alternative is via SMS to your phone.

• Just about everyone has a phone.
• Just about everyone with a phone also has SMS support.
• Those who don't can still use email.

Even if someone has access to your SMS messages (good luck) they still don't know your username. That's only paired when you sign up and when you authenticate. Forget your username and well.... you are pretty screwed. Forget your password and you can have a new one sent to your phone.

Almost as good as biometric authentication but you can run it on websites. No need for HTTPS authentication schemes since the password expires immediately. No need for each website to come up with their own password authentication modules (PAM) -- It's just a proxy pass to a central server (me) to authenticate.

I ginned up something as a proof of concept out there and it works well enough.

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.

Re:Nope

[FireFury03]

No, the US doesn't like the Euro Gallileo, because as far as we know, they lack the ability to block, or change the signal.

This is not true (anymore). ISTR the sequence of events went something like:

1. EU announced Gallileo
2. US started complaining that they didn't see why the EU wanted to do this since there was an already perfectly good GPS system in operation.
3. EU pointed out that NAVSTAR is under the control of the US millitary and they didn't trust the US not to turn it off or "adjust" it
4. US said that this would never happen and the EU should just use GPS
5. Some time later it was obvious the EU had ignored the US "recommendation" and continued working on Gallileo so the US then made a lot of fuss about how it would be bad because the US wouldn't have control of it and thus couldn't block it (strange - isn't that what they said they would never do?). Lots of words like "terrorism" were thrown around.
6. EU caved and modified Gallileo so that the US (and anyone else for that matter) could easilly block it.

Now personally, I think this is a very Bad Thing - if I'm using a global positioning system for safety critical purposes I want it to be as damned bulletproof as possible, I don't want it purposefully designed to be easilly jammable just to please a paranoid foreign government.

Re:Two Interesting Points

[Anonymous Coward]

Absolutely correct. As someone who worked at a business geographics company that provided data to Google, Yahoo, and in-car nav systems (including the first stock system in the Prius), I can say that the multi-million dollar data set we produced was most certainly copyrighted. They even went so far as to insert fake "ghost streets" to catch other companies copying their data. Single datasets that fit on a CD and covered a single county were worth over $50,000. (Oddly enough, they weren't locked down and often resided at personal workstations for weeks at a time)

If you don't believe all that, just go to Google Maps and read the copyright in the corner. It will usually be either Nav-Tech or Geographic Data Technology (my former employer).

Re:Quantum encryption

[ATinyMouse]

If the GP is talking about the same article I read, I believe it was covered in Discover Magazine a couple years ago. According to the article, a man in the middle attack would be discovered due to the attacker having to rebroadcast the transmission and not knowing which way to spin the atoms. The two ends of the connection would then have an error correction rate that may exceed a certain threshold and know that something is up.

Re:uncrackable encryption

[tacocat]

Really, why bother?

I was hoping that the website would explain this. Did you RTFM? Assuming you did not. The advantage that still exists is that OTP, even over SMS is much harder to intercept than standing behind someone at an airport kioske or sniffing wireless networks... I didn't say it was 100% secure, in fact I think I even make mention that it is still not perfect. But it's a hell of a lot better than common practice today.

I would think it would be preferred if someone would be willing to move towards a better solution than waiting for the perfect solution and damning all others.

The key problems that are addressed are:

• periodically changing passwords. Changed every time.
• making passwords reasonably complex. Pseudo-random beats birthdays and pets names.
• simplifying username/password management.

It's easy to put down an idea. So what do you have to offer the world that might actually be useful? The biggest problem to security isn't all this hype about encryption keys and SSL and crypto-this and crypto-that. It's getting people to use it in the first place. Social Engineering is the weakest part of security bar none. If you can get people to willingly improve their security position than you have a win. If you have to do it through draconian methods, you lose.

As as far as my idea sucking. Fuck you. I don't see you coming up with anything but vinegar. You're not even trying.

what non-military use?

[r00t]

I'm not seeing to many peaceful uses that aren't already covered by one of:

a. standard GPS
b. standard GPS plus a differential signal (good for airport approaches)
c. carrier-phase (sub-centimeter but slow, for surveying)

I'll grant that differential signals can make airports easy targets. :-)

For what are you needing the combination of precision, accuracy, fast measurements, and a location that hasn't been set up with a differential transmitter?