Steganography 21 - The Wearable Turing Machine

• Download source - 3.8 KB

Introduction

As you possibly remember from school, a Turing Machine is a mathematical model of computation. It defines an abstract machine working with characters on an endless tape. In theory, a system that simulates a turing machine is able to support all tasks accomplishable by computers.

Each cell on the tape has to be writable only once. For a second write access, you can copy the used tape to a new segment. As every calculation can be done in binary, the alphabet of writable characters can be limited to {0, 1}, though a larger alphabet may be good to save tape. In this article we'll use {0, 1, 2, 3} to encode everything in base-4.

A cheap and simple way to simulate the endless, writable tape is a clew of yarn. You can write characters by knitting different stitches. If you need to overwrite a used position, just start a new row; that is like rewinding and copying the tape of the turing machine.

This article explains how to encode any content as stitches, render a knitting chart and decode the finished yarn-tape again. It uses the Apache Batik SVG Toolkit to draw the pattern.

You might want to feed the patterns into a knitting machine, turning it into a real hardware Turing Machine. You can as well knit them by hand to transmit secret messages just by letting your messenger wear a warm hat.

The Application

The Java application accepts a text, converts the characters to groups of base-4 numbers and translates those into a row of stitches:

• 0 = knit
• 1 = purl
• 2 = yarn over, knit
• 3 = yarn over, purl

The screenshot shows the knitting chart generated from the text "Hi CP!". Only the first row contains information. The second row is there to reduce the excess stitches created by the digits "2" and "3". All following rows are just repetitions to make the code look like decoration.

Such a pair of rows would look strange in a piece of cloth. But usually, knitted stuff has decorative patterns and everything looks like a pattern, if you just repeat if often enough. So, feel free to repeat the code row until the result looks pretty unsuspicious.

Encoding and Decoding

This little demonstration uses only latin text. As a character is a value between 0 and 255, it corresponds to four digits between 0 and 3. Those digits are concatenated to one long string and then sent to the graphics frame.

private void encode(String clearText){
	ByteBuffer bytes = Charset.forName("ISO-8859-15").encode(clearText);
	StringBuilder resultBuilder = new StringBuilder(clearText.length() * 4);

    // convert each character
	while(bytes.hasRemaining()){
		int currentValue = bytes.get();			
		String currentWord = Integer.toString(currentValue, 4);
		
		// pad the number to a length of 4
		while(currentWord.length() < 4){
			currentWord = "0" + currentWord;
		}
		
		resultBuilder.append(currentWord);
	}
	
	ChartFrame frame = new ChartFrame();
	frame.drawChart(clearText, resultBuilder.toString());
}

When reading a piece of cloth manually, you may note down digits for the kinds of stitches you recognize...

... then call the decoder with the row of stitches you found. They'll be decoded to the original text:

The decode method converts the chain of numbers back to the original message.

private String decode(String encodedText){
	int n = 0;
	StringBuilder resultBuilder = new StringBuilder(encodedText);

    // translate blockwise to characters
	while(n < resultBuilder.length()){
		String currentWord = resultBuilder.substring(n, n+4);
		
		int currentValue = Integer.parseInt(currentWord, 4);
		String currentClearChar;
		
		// decode or ignore
		if(currentValue < 256){
			ByteBuffer buffer = ByteBuffer.wrap(new byte[]{(byte)currentValue});
			currentClearChar = Charset.forName("ISO-8859-15").decode(buffer).toString();
		}else{
			currentClearChar = "?";
		}
		
		// compress 4 digits to 1 character		
		resultBuilder.replace(n, n+4, currentClearChar);
		n++;
	}
	
	return resultBuilder.toString();
}

Rendering the Chart

For each digit, the corresponding stitches have to be drawn. I used the knit chart symbols by the Craft Yarn Council, which are easy to render with geometric shapes.

The chart consists of three components: Column numbers, odd rows encoding the payload, even rows fixing the count of stitches.

public void drawChart(String title, String base4Digits){
	titleText = title;

    // prepare SVG document
	DOMImplementation impl = SVGDOMImplementation.getDOMImplementation();
	String svgNS = SVGDOMImplementation.SVG_NAMESPACE_URI;
	SVGDocument doc = (SVGDocument) impl.createDocument(svgNS, "svg", null);
	SVGGraphics2D g = new SVGGraphics2D(doc);
	g.setFont(new Font("sans serif", Font.PLAIN, 10));
	
	// calculate chart width
	countColumns = getCountCols(base4Digits);
	countRows = (int)(200 / boxSize);
	svgCanvas.setSize((2+countColumns)*boxSize, countRows*boxSize);
	
	// fill background
	g.setPaint(Color.darkGray);
	g.fillRect(0, 0, svgCanvas.getWidth(), svgCanvas.getHeight());
	
	// draw odd coding rows, even fixing rows
	for(int y = 0; y < (countRows-2); y+=2){
	    // code symbols may add stiches
    	drawOddRow(y, base4Digits, g);
    	
    	// fix excess stitches by knitting two together
    	drawEvenRow(y+1, base4Digits, g);	    	
    }
	
	// draw column numbers
	for(int x=0; x < countColumns; x++){
		drawColNumber(x+1, countRows-1, g);
	}
	
	// prepare and show frame
	titleText = titleText + " - " + "start with " + (base4Digits.length()+2) + " stitches";
	g.getRoot(doc.getDocumentElement());
	svgCanvas.setSVGDocument(doc);
	svgCanvas.getParent().setPreferredSize(svgCanvas.getSize());
	pack();
	setVisible(true);
}

Drawing a row is simple: Place one knit symbol at each end, then fill the space with symbols:

private void drawOddRow(int y, String base4Digits, SVGGraphics2D g){
	// label and left edge
	drawRowNumber(0, y, g);
	drawKnit(1, y, g);

    // append one or two symbols per digit
	int x = 2;
	for(int n=0; n < base4Digits.length(); n++){
		char currentChar = base4Digits.charAt(n);
		
		/* draw box
		   0 = knit
		   1 = purl
		   2 = yarn over, knit
		   3 = yarn over, purl
		*/
		switch(currentChar){
    		case '0': drawKnit(x, y, g); break;
    		case '1': drawPurl(x, y, g); break;
    		case '2': drawYarnOver(x, y, g);
    				  drawKnit(++x, y, g);
    		          break;
    		case '3': drawYarnOver(x, y, g);
    				  drawPurl(++x, y, g);
    				  break;
		}
		
		x++;
	}

	// right edge
	drawKnit(x, y, g);
} 

The chart symbols are primitive shapes. These are a few examples:

private void drawBox(int col, int row, SVGGraphics2D g){
	int x = col*boxSize;
	int y = row*boxSize;
	Rectangle2D.Double box = new Rectangle2D.Double(x, y, boxSize, boxSize);
	
	g.fill(box);    	
	g.setColor(Color.black);
	g.draw(box);
}

private void drawColNumber(int col, int row, SVGGraphics2D g){
	g.setColor(Color.black);
	g.setPaint(Color.cyan);
	drawBox(col, row, g);
	g.drawString(String.valueOf(col),
	       (col*boxSize)+boxPadding,
	       (row*boxSize)+boxSize-boxPadding);
}

private void drawYarnOver(int col, int row, SVGGraphics2D g){
	g.setColor(Color.black);
	g.setPaint(Color.white);
	
	int x = col*boxSize;
	int y = row*boxSize;
	int height = boxSize-(boxPadding*2);
	
	Ellipse2D circle = new Ellipse2D.Double(
				x+boxPadding, y+boxPadding, 
				height, height);
	
	drawBox(col, row, g);
	g.draw(circle);
}

Points of Interest

So far, all we did was encoding and decoding. We are able to fill the tape of our fluffy Turing Machine with characters.

That is good enough to hide text in plain sight wearing a woolen scarf, which may be your only chance to smuggle secrets from Alaska to Siberia.

The next step could be to program a knitting machine, to make it process a calculation line by line. I hope you enjoyed this article and take a closer look at other people's textiles.