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.

Re:uncrackable encryption

[Anonymous Coward]

I was hoping that the website would explain this. Did you RTFM? Assuming you did not.

Actually, I did. It is far from clear. Can you please explain how this is using the benefits of a One Time Pad? Especially given that a One Time Pad requires non-deterministically created random numbers and a secure transfer method to actually be used properly.

It's easy to put down an idea. So what do you have to offer the world that might actually be useful?

I don't need to when there are already decent systems in place. I certainly won't be choosing some scheme like this. I have to shift ultimate trust to you, your systems and your delivery methods. I am not going to just trust you, or your systems, especially considering your delivery methods. I'll take tokens, biometric and strong locally administered passwords, thanks.

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.

So you're trying to fix human factors with a system which is more complicated and encourages the user to carry around a copy of their password in plaintext? Validating the actions of all those people who keep their password printed in the plain in their wallets?

If you have to do it through draconian methods, you lose.

Your method is draconian! So somebody witnesses the victims typed in username and then steals or clones his phone or sniffs the next usable password in transit. What then? You are actually advocating on your site that it is okay to send passwords through email, because it is often done for password resets by other sites? Just because some people do security poorly, does not mean you should be advocating a system that does it no more poorly. I would not be using the word draconian if I were you.

All I see at your site is this claim, "One time authentication (ota) is a means of adopting the known practices of One Time Pad encryption into a tool suitable for everyday web site authentication which provides a very high level of security while maintaining ease of use", and then a whole lot of complaining about how hard it is for people to adhere to decent password usage and then a short description of decent password usage, then another claim, "One Time Authentication is based on the historical One Time Pad encryption that's been used for passing secret messages. The difference is that it is applied to authentication or login. Here's how", then a vague description:

1. One username (That's one username to witness, to penetrate lots of sites).
2.1. Passwords only used once, like OTP encryption (Except it's not One Time Pad Encryption, rather it is a One Time Password, a system which already exists).
2.2. Passwords are pseudo random (exactly what OTP's are NOT supposed to use. If you are going to provide such a service, why not get some decent random numbers from a pretty cheap external device).
2.3. Previous password no longer valid (yeah, you covered that in 2.1).
2.4. Next passwords sent to you (where it will either travel and/or ultimately be stored in the plain under most cicumstances. Any crypto protections along the way will allow the system to only be as strong as those systems).
3. Just have to remember one username (yes, yes, you've covered that. One leaked username for all systems, that's great).
3.1 We're going to send you your next password in advance (so as to allow maximum chances that it will be read from you email, hard disk, a backup tape taken off-site, etc or maximize the risks if your phone is stolen, hacked, covertly "borrowed").
3.2 We advocate mobile phone delivery, since it is an out-of-band communication (but ignore the glaringly obvious risks that mobile phones are really easy to steal, crack, clone, etc).
3.3 Oh and we support the mos

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.

Never Understood the Logic of Galileo

[Aaron M. Renn]

I must confess I've never seen the logic of the Galileo system. This is so clearly about nothing but Euro-prestige, and it makes you wonder if the Europeans understand fundamental economics. Everything Galileo will do is done by GPS (which, btw, is not a generic name, though I'm sure the Euros would love it to be to confuse the marketplace) or will be done when planned upgrades are in place. Bogeyman scenarios of the US cutting off GPS are ridiculous as I'm not aware that the US military has ever shut off access even in Iraq - and the US military would jam Galileo if they wanted to in any case.

The Europeans could have had a free ride at the US taxpayers expense. Instead, they decide to spend billions to build a competitor system. So how to recoup that? It's obvious that the EU will force all mobile phones, cars, planes, etc. sold in Europe to use Galileo. The free market would never adopt a new alternative that is not technically or functionally superior, is going against an entrenched competitor with a huge install base, and costs money where the alternative is free. So you can bet it will be regulated into existence and the huge fees everyone is forced to pay for this (hidden inside the price you pay for these devices, of course, just like VAT) will be touted as how "successful" the system is - as if adding a multi-billion tax on your citizens while everyone else pays nothing is a benefit of the system. Look for rules requiring Galileo on any aircraft which uses EU airspace, necessitating costly refits to the worldwide fleet of planes that already have GPS installed and other costly items that will actually be an economic drag.

GPS is like an open source project or classic economic "public good". Galileo is a like a gratuitous fork. It's also the attempt to turn a public good into a private one by the use of new technologies like encryption/DRM.

Building Galileo also ignores the law of comparative advantage. Why not focus at where you have the greatest comparative advantage over other people instead of fighting to replicate everything everyone could ever do? No one questions that the Europeans have the technical expertise and financial resources to build this project. The question is whether Galileo is the best use of those resources. Better to put them towards something that would be game changing, not a "me too". Why not use that to figure out how to make hydrogen fuel cells really work? Or build a space probe to do something no one has every done before. There are a million potential projects that Europe could do that would benefit humanity and turn them into an unquestioned economic or scientific leaders in varios area. Unfortunately, the EU seems to consistently want to do these type of me-too project instead, whether that be Galileo, the A380 or A400M, Jacques Chirac's new French search engine, etc. The playbook seems to be cloning someone else's ideas, making them slightly bigger and better, then touting them as the best thing since sliced bread. All of these can be successful in a nominal sense, but I question whether they were the best economic use of the resources.

Europe has vast treasures of intellectual talent, largely top notch infrastructure (London transport excepted, thank you), awesome culture, high productivity, a mostly-common currency and open borders, and a history of great economic success. I've got to believe the ingrediants are there for a great boom - particularly with the influx of new Eastern European members - if the EU governments would just put the right policies in place to make it happen.

Meanwhile, the US economy has grown by 20% since 2003 - adding $2.2 trillion in GDP. In other words, we just added an entire China to our economy in the last three years while also adding millions of new jobs. Considering the doom and gloom generally reported in the media, that's something to think about.

Re:Never Understood the Logic of Galileo

[PenGun]

It's very simple. They not trust the US. That is why they built their own.

    PenGun
  Do What Now ??? ... Standards and Practices !

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: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: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: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: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.