Introduction
This article explains one of many possible approaches to hiding extra information in GPS data files, especially the GPX format. The messages are encoded as points just the way you know from elliptical curves cryptography. A long GPS track plays the role of the key, the encoded message is a set of points on that track with specific longitude values.
GPX is an XML format for storing geographical data. It is primarily used by GPS devices to record and exchange tracks, routes, and waypoints. The file structure is wonderfully simple. A file can contain traces of points (tracks or routes) and named points (waypoints).
<gpx version="1.0"/>
<trk>
<name>My Way</name>
<trkseg>
<trkpt lat="52.311389" lon="9.787149">
[some optional data]
</trkpt>
<trkpt lat="52.311276" lon="9.787381">
[some optional data]
</trkpt>
</trkseg>
</trk>
<wpt lat="52.310218" lon="9.791205">
<name><![CDATA[</name>
[some optional data]
</wpt>
</trk>
The latitude and longitude values are more precise than common receivers are: a change of the sixth decimal means a change of 10 centimeters. So, the first idea about where to hide additional information must be to change the least significant decimals. That would be some kind of Geo LSB with decimeters instead of pixel colours.
In this article, we'll do something completely different.
Secret Places
There's a well known method of encoding any data as points on a given curve. You divide the x-axis into equal columns, number those columns, and then pick a point from the corresponding column for each value you want to encode. For plain text messages, you could even divide the map like that:
For example, in elliptical curves cryptography, weird calculations are done with the selected points. But if you know my articles, you know that I keep them free of complicated math. We'll also pick points from a given pool, but leave them as they are and make them look innocent.
Run for a Key File
Usually, GPX files are either recorded while walking, or drawn on a map. People also mark special places as waypoints. Of course, every waypoint is also part of the (recorded, not drawn) track: The tracks' author has to go there to record the waypoint. This is some GPS data I've recorded yesterday. There are a lot of paths and two waypoints.
You don't know that area, do you? I could have placed the waypoints anywhere. I could even publish a waypoints file to load onto a GPS device - as long as there's something pretty around (for the case somebody actually walks there), that would not look strange at all. The idea is to mark waypoints that encode a message. The points are taken from the track according to a text or binary stream, and then written to a blank waypoints file or to the track's GPX file. People are free to view those files on maps or import them onto their GPS devices. But only those who decode certain points' longitudes will see the hidden message.
The raw coordinates we get from the track are float
values with six decimals. Before we can encode byte values between 0 and 255, we have to squeeze them somehow. I decided to scale the whole track so that the smallest longitude is 0 and the highest one is 255. This code reads the points from the XML nodes and gets the minimum and maximum coordinates:
XmlNodeList trackPoints = gpxDocument.GetElementsByTagName("trkpt");
ScalablePoint[] track = GeoNodeToPoints(trackPoints);
ScaleTrack(track);
[...].
private ScalablePoint[] GeoNodeToPoints(XmlNodeList geoNodes)
{
ScalablePoint[] points = new ScalablePoint[geoNodes.Count];
int index = 0;
float floatLon = 0;
int intLon = 0;
float floatLat = 0;
int intLat = 0;
foreach (XmlNode geoNode in geoNodes)
{
string strLon = geoNode.Attributes["lon"].Value;
string strLat = geoNode.Attributes["lat"].Value;
floatLon = float.Parse(strLon, CultureInfo.InvariantCulture);
floatLat = float.Parse(strLat, CultureInfo.InvariantCulture);
intLon = (int)Math.Round(floatLon * 1000000);
intLat = (int)Math.Round(floatLat * 1000000);
if (intLon < minLon) minLon = intLon;
if (intLon > maxLon) maxLon = intLon;
if (intLat < minLat) minLat = intLat;
if (intLat > maxLat) maxLat = intLat;
points[index] = new ScalablePoint(intLon, intLat);
index++;
}
return points;
}
Here's the code to squeeze the track into a 255 x 255 matrix. I scale the latitudes as well, because the track will be displayed in a picture box.
private void ScaleTrack(ScalablePoint[] track)
{
int scaledMaxLon = maxLon - minLon;
int scaledMaxLat = maxLat - minLat;
for (int n = 0; n < track.Length; n++)
{
track[n].X -= minLon;
track[n].Y -= minLat;
track[n].X = (int)Math.Round((track[n].X / (float)scaledMaxLon) * 255);
track[n].Y = (int)Math.Round((track[n].Y / (float)scaledMaxLat) * 255);
}
}
When the track is scaled to longitudes between 0 and 255, we are ready to encode! For each byte of the secret message, we take a point with just that scaled longitude. Then, we write that point to a waypoints GPX file and upload it to a well known website.
This code creates a new GPX file and fills it with waypoints. If the user feels safe, it also adds the key track. The latter is only recommended when there's no other way to exchange a track: key and message are stored in the same file! On the other hand, it is quite handy, if you only want to cover some data that already is encrypted.
private void btnEncode_Click(object sender, EventArgs e)
{
Random random = new Random();
Stream message = sbEncodeMessage.Stream;
int messageByte;
XmlTextWriter gpxWriter =
new XmlTextWriter(fsEncode.FileName, Encoding.UTF8);
gpxWriter.Formatting = Formatting.Indented;
gpxWriter.WriteStartDocument(true);
gpxWriter.WriteStartElement("gpx");
gpxWriter.WriteAttributeString("version", "1.0");
gpxWriter.WriteAttributeString("xmlns",
"http://www.topografix.com/GPX/1/0");
gpxWriter.WriteAttributeString("xmlns:xsi",
"http://www.w3.org/2001/XMLSchema-instance");
gpxWriter.WriteAttributeString("xsi:schemaLocation",
"http://www.topografix.com/GPX/1/0" +
" http://www.topografix.com/GPX/1/0/gpx.xsd");
while ((messageByte = message.ReadByte()) > 0)
{
if (pointsByLon.Keys.Contains(messageByte))
{
Collection<ScalablePoint> points = pointsByLon[messageByte];
int pointIndex = random.Next(points.Count - 1);
Point waypoint = points[pointIndex].Original;
float lon = (float)waypoint.X / 1000000;
float lat = (float)waypoint.Y / 1000000;
string strLon = lon.ToString(CultureInfo.InvariantCulture);
string strLat = lat.ToString(CultureInfo.InvariantCulture);
gpxWriter.WriteStartElement("wpt");
gpxWriter.WriteAttributeString("lat", strLat);
gpxWriter.WriteAttributeString("lon", strLon);
gpxWriter.WriteEndElement();
}
}
if (chkIncludeTrace.Checked)
{
XmlDocument trackDocument = new XmlDocument();
trackDocument.Load(fsTrack.FileName);
XmlNodeList trkNodes = trackDocument.GetElementsByTagName("trk");
foreach (XmlNode trkNode in trkNodes)
{
gpxWriter.WriteNode(trkNode.CreateNavigator(), false);
}
}
gpxWriter.WriteEndDocument();
gpxWriter.Close();
MessageBox.Show("Finished");
}
}
Don't Visit the Place, Decode it!
So, you've downloaded a GPX file from an outdoor fanatics website. You are the one who knows where to look. You don't open it with the trip planner, but with the decoder application. This code gets the waypoints from the file and scales them with the same parameters used before to scale the key track. Then, the message can be read from the x-values.
private void btnDecode_Click(object sender, EventArgs e)
{
XmlDocument gpxDocument = new XmlDocument();
gpxDocument.Load(fsWaypoints.FileName);
XmlNodeList wayPointNodes = gpxDocument.GetElementsByTagName("wpt");
ScalablePoint[] wayPoints = GeoNodeToPoints(wayPointNodes);
ScaleTrack(wayPoints);
char[] messageChars = new char[wayPoints.Length];
for (int n = 0; n < messageChars.Length; n++)
{
messageChars[n] = (char)wayPoints[n].X;
}
txtDecodedMessage.Text = new string(messageChars);
}
Known Issues
I've tested the application with short geo tracks recorded by PathAway on my mobile phone and longer tracks found at www.openstreetmap.org. The resulting GPX files were called correct when the XML looked fine, and this GPS Track Viewer displayed them as expected.
This article is meant to show the idea of GPS stego. The following problems will be fixed, if there'll ever be another version:
- The same waypoint gets selected multiple times. Points that have already been used to encode a value should be removed from the key.
- For every x-value, there's a point on the track, but only those noted down in the track file are actually used. The application doesn't calculate the lines between two given track points.