Click here to Skip to main content
Click here to Skip to main content

Steganography 18 - GPS Tracks and Waypoints

, 1 Aug 2009
Rate this:
Please Sign up or sign in to vote.
Encode a message as waypoints in a GPX file.

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.

screen.gif

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[My Place]]></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:

encode.gif

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.

openstreetmap.jpg

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:

// find all track point nodes
XmlNodeList trackPoints = gpxDocument.GetElementsByTagName("trkpt");
// convert the nodes to points
ScalablePoint[] track = GeoNodeToPoints(trackPoints);
// move the track to the upper left corner
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);

    // Avoid floating point variables. A precision of 10 cm is enough.
    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++)
 {
   // move track to upper left corner
   track[n].X -= minLon;
   track[n].Y -= minLat;

   // scale track to width = height = 256 = one column per possible message byte
   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);

    // write GPX header
    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))
       {  // pick one of the points with x = messageByte
         Collection<ScalablePoint> points = pointsByLon[messageByte];
         int pointIndex = random.Next(points.Count - 1);
         Point waypoint = points[pointIndex].Original;

         // format the waypoint
         float lon = (float)waypoint.X / 1000000;
         float lat = (float)waypoint.Y / 1000000;
         string strLon = lon.ToString(CultureInfo.InvariantCulture);
         string strLat = lat.ToString(CultureInfo.InvariantCulture);

         // add the waypoint
         gpxWriter.WriteStartElement("wpt");
         gpxWriter.WriteAttributeString("lat", strLat);
         gpxWriter.WriteAttributeString("lon", strLon);
         gpxWriter.WriteEndElement();
       }
       // else: ignore characters that cannot be
       // represented by any point of the track
    }

    if (chkIncludeTrace.Checked)
    {  // add original track to the file
       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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Corinna John
Software Developer
Germany Germany
Corinna lives in Hannover/Germany (CeBIT City) and works as a Delphi developer, though her favorite language is C#.

Comments and Discussions

 
GeneralNice Article PinmemberWisam E. Mohammed23-Jun-10 9:12 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web04 | 2.8.140827.1 | Last Updated 1 Aug 2009
Article Copyright 2009 by Corinna John
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid