Secret messages in 3D files

Background

If you are a reader of this blog you may or may not already know what steganography is.  According to Wikipedia, “steganography is the art and science of writing hidden messages in such a way that no one, apart from the sender and intended recipient, suspects the existence of the message, a form of security through obscurity… The advantage of steganography, over cryptography alone, is that messages do not attract attention to themselves.

It’s secret messages.  It’s writing what appears to be a regular letter to somebody, but then using the lemon juice invisible-ink trick to write the “real” message in the margins. In the computer world, there’s a lot of intrigue around it.  In theory, it can be used by super-spies to hide messages inside of pictures or music.  In practice, well, nobody really knows who uses it or why.

In the physical world, it’s easy to see how this would work with the lemon juice example.  In the computer world, there are more options, but they all boil down to adding or subtracting an insignificant piece of data that is not visible to the naked eye.  You do this enough and each addition, for instance, could count as a “1” and each subtraction could be a “0”.  There are ways to do this in text, pictures, audio, and all sorts of files.  Let’s look at an example or two.

Your browser doesn’t care (much) about whitespace when displaying text.  I could write “hello[space][space][space][space]world”, but web browsers end up collapsing all of those spaces down into one.  You can take advantage of that.

"The quick brown fox  jumps over the  lazy  dog."

Check out the above phrase. If that were in an HTML page, it would display just like a regular sentence. “The quick brown fox jumps over the lazy dog.”  No suspicious extra spaces.  But let’s suppose my co-conspirator and I have set up some rules.  One space between words is a zero and two spaces is a one.

"The quick brown fox  jumps over the  lazy  dog."
    0     0     0   1      0    0   1     1

That becomes 00010011 in binary, or 19 in decimal.  We have further agreed that we’re encoding A as 1, B as 2, C as 3, etc.  So 19 is “S”.  Using other encodings we could pass photographs (of enemy bases we’re spying on), sound files (of prisoners we’ve interrogated), or really any file as the payload.  As you can see, it’s not terribly efficient.  It took nine words to encode a single letter.  Using a similar scheme, this blog post (~1100 words) could hold about 137 letters of text.

You’re not limited to text, either.  In most pictures and video, your eyes are not able to see the difference between a single bit of color.  The following image has two shades of red.  One is an even number (254), the other is an odd number (255).  Your eyes can’t tell the difference, not even at the seam between the two colors.

If we took an entire photograph and just rounded the numbers representing each pixel of color up or down, you would have a picture that, to the naked eye, looked just like the original.  We could then use the same zero/one scheme to embed a secret message.

The 3D File Format

Most hobbyist 3D printing uses a file format called STL — or Stereo Lithography.  These files are effectively a list of triangles.  Each triangle also has a vector attached called a “normal,” which helps the 3D modeling program better determine “inside” from “outside.”  For instance, a cube is a bunch of triangles with perpendicular normal vectors:

This particular cube has an STL file that starts like this if you open it a text editor…

solid Exported from Blender-2.63 (sub 0)
facet normal 0 0 0
  outer loop
    vertex -1.000000 -1.000000 1.000000
    vertex -1.000000 1.000000 1.000000
    vertex -1.000000 1.000000 -1.000000
  endloop
endfacet
facet normal 0 0 0
  outer loop
    vertex -1.000000 1.000000 1.000000
    vertex 1.000000 1.000000 1.000000
    vertex 1.000000 1.000000 -1.000000
  endloop
endfacet
...etc...

(The normals are a little irregular in that they use a bit of a shorthand cheat — 0,0,0 implies that the 3D program should calculate the normal itself using “the right hand rule” on the ordering of the triangle’s points.  But that’s more detail than I want to get into here.)

Hiding in 3D Files

A clever fellow who goes by the name Zheng3 recently devised a game called Seej.  The rules of the game are freely available.  The pieces themselves are also freely available at Thingiverse — just add a 3D printer.  People are encouraged to devise both new rules and new pieces.  It’s a pretty cool little ecosystem.  The game itself feels like a variation of Crossbows & Catapults, a tabletop game I had as a kid.

Recently he posted a game piece on Thingiverse with a secret message coded into it, the Cryptstone.  There is a password of some sort in there that you can enter into his website to unlock a new game piece.  The implication is that there’s something about the model itself (e.g. the numbers that make up the triangles and/or normals) that encodes the data, versus using whitespace.  “This block will probably print, but your slicing software is likely to squawk at you.”  In fact, almost the whole model consists of non-manifold points.  The normals all look like they are point the right way, but the triangles don’t all quite line up down in the wee decimal places.  The blue lines are the normals, they should (and do) looks like a porcupine.  The orange indicates non-manifold (“bad”) points.

The file starts out a little something like this…

solid temp (repaired)
facet normal 0.000000 -0.002875 0.000000
  outer loop
   vertex -8.340000 -5.000000 24.98042
   vertex -8.340000 -5.000000 28.420000
   vertex -16.700001 -5.000000 28.420000
  endloop
 endfacet
facet normal 0.000000 -0.002876 0.000000
  outer loop
   vertex -16.700001 -5.000000 28.42042
   vertex -16.700001 -5.000000 24.980000
   vertex -8.340000 -5.000000 24.980000
  endloop
 endfacet
facet normal 0.000251 0.000000 -0.000000
  outer loop
   vertex -7.340001 0.499550 24.98042
   vertex -7.340000 -4.000000 28.420000
   vertex -7.340001 -0.229625 24.980001
  endloop
 endfacet
facet normal 0.001212 -0.000000 -0.000000
  outer loop
   vertex -7.340000 4.020000 24.98115
   vertex -7.340000 -4.000000 28.420000
   vertex -7.340001 0.499550 24.980001
  endloop
 endfacet
...etc...

Initially the values with a whole bunch of zeros but a trailing one jumped out at me.  Things like -16.700001 and -7.340001 look like they might have started as a very accurate “-16.7” and “-7.34” but got tweaked, so slightly out-of-true, so far out in the decimal, that your eye would not see it (much like it can’t see the two reds in the above example).  There are a few other suspicious numbers such as “28.42xxxx” and “24.98xxxx” which do not always end with the same four (or three) digits.

At this point, the rest is an exercise left to the reader.  I solved it with a ten-line Ruby script, though I could have just as easily solved it by hand with an ASCII chart.

I think this was a fun way of encoding a message.  I believe a true steg program that intelligently handled STL files would end up correlating points across triangles to keep the object manifold, though that could lead to encoding problems, with points earlier in the “message” interacting with points later in the message in unintended ways because the triangles of a 3D model share points.  Fortunately, this particular puzzle provided just enough surface area to tease out the correct answer.  I think a more “professional-grade” STL steg would have fewer obvious oddities to latch on to.

So, Zheng3, thank you!  I raise my (tenpenny) tankard in your general direction.

Posted in: MakerBot

Published by

Brian Enigma

Brian Enigma is a Portlander, manipulator of atoms & bits, minor-league blogger, and all-around great guy. He typically writes about the interesting “maker” projects he's working on, but sometimes veers off into puzzles, software, games, local news, and current events.

3 thoughts on “Secret messages in 3D files”

  1. This is really interesting, especially the idea of real-world steganography. Thanks also for the really clear explanation of how it works; it looks like some good detective work.

    I thought you might also be interested in the following work, which has looked at watermarking 3D models using similar techniques:

    M.C. Motwani, B.D. Bryant, S.M. Dascalu, F.C. Harris, “3D Multimedia Protection Using Artificial Neural Network,” 7th IEEE Consumer Communications and Networking Conference (CCNC), Las Vegas, NV, USA, January 2010.

    http://www.cse.unr.edu/~fredh/papers/conf/084-3dmpuann/paper.pdf

    This isn’t intended for printed models necessarily, but there are definite similarities.

Leave a Reply

Your email address will not be published. Required fields are marked *