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.
Wow! What an interesting post. Thanks for sharing Brian – that’s really cool.
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.
David — thank you for the link. Coincidentally enough, I am currently doing work on watermarking video files, so that paper is a wonderfully serendipitous find.